基于DHT的key-value存储的范围查询技术研究

论文摘要

Key-value类型的数据库是一种非关系型的数据库，它有着广泛的应用领域。尤其是在大规模和高并发类型的应用场景下，以及处理大量非结构化内容信息时，key-value存储系统发挥了重要作用。DHT（Distributed Hash Table，分布式散列表）模型可谓是由来已久，其最初来源可能要追溯到P2P系统中。本文的一个基本的立足点是把DHT模型应用于key-value存储中。数据的查询技术是key-value存储中的一个关键技术。本文研究基于DHT模型的key-value存储中的范围查询问题。首先，从分析现有的资源搜索技术入手，对典型的DHT资源搜索、基于树结构的范围查询以及多属性的范围查询等技术进行了分析与研究，总结了这些查询技术的特点。在此基础之上，针对范围查询所独有的特点，本文提出了基于资源探测机制的范围查询策略。该方法考虑到了多属性上的范围查询，利用Hilbert空间填充曲线将多维属性空间映射到一维key值，采用一致哈希法解决了节点分布及资源的存放等问题；在构建索引信息时，利用Bloom Filter及资源分布邻居表增大了单个节点的信息掌握量，在查询时有利于节省网络跳数。本文详细说明了基于资源探测机制的范围查询方法，给出了索引信息的部署以及索引更新方案，并描述了与索引策略相适应的范围查询算法，简要分析了该算法的性能。最后，对基于资源探测机制的范围查询算法进行了仿真实验，仿真结果表明，基于资源探测机制的范围查询算法是有效的。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 研究背景
• 1.1.1 RDBMS 面临的挑战
• 1.1.2 NoSQL 的诞生
• 1.1.3 基于 DHT 模型的 NoSQL 数据库
• 1.2 研究现状
• 1.3 本文主要研究内容
• 第二章 DHT 资源搜索
• 2.1 DHT 存储技术
• 2.1.1 DHT 存储的概念
• 2.1.2 DHT 查找
• 2.2 典型 DHT 搜索方法
• 2.2.1 Chord 方法
• 2.2.2 CAN 方法
• 2.2.3 Tapestry 方法
• 2.2.4 搜索特性分析
• 2.3 基于树结构的范围查询
• 2.3.1 前缀哈希树
• 2.3.2 分布式分段树
• 2.3.3 性能分析
• 2.4 多属性的范围查询
• 2.4.1 分布式倒排索引
• 2.4.2 d-to-d 的映射机制
• 2.4.3 d-to-one 的映射机制
• 2.4.4 特点分析
• 2.5 本章小结
• 第三章 基于资源探测机制的范围查询策略
• 3.1 引言
• 3.2 资源映射方法
• 3.2.1 Hilbert 曲线法
• 3.2.2 映射过程
• 3.3 资源组织方式
• 3.3.1 一致哈希法
• 3.3.2 节点变更处理
• 3.4 索引策略
• 3.4.1 问题分析
• 3.4.2 Bloom Filter 原理
• 3.4.3 索引构建
• 3.4.4 索引更新
• 3.5 范围查询算法
• 3.5.1 算法描述
• 3.5.2 性能分析
• 3.6 本章小结
• 第四章 算法仿真与结果分析
• 4.1 仿真软件
• 4.2 仿真目标
• 4.3 仿真实现
• 4.4 仿真结果与分析
• 4.5 本章小结
• 第五章 总结与展望
• 致谢
• 参考文献
• 研究成果