基于Mapreduce框架可扩展数据索引的研究与实现

摘要

随着信息时代的到来，生活生产中会产生海量的数据，其中移动互联网、物联网和科学研究等领域会产生结构更为复杂、体量更为庞大的数据。虽然传统的数据库技术日益成熟，但在解决数据量大、数据结构复杂等问题时稍显不足，其扩展性和容错性也面临着挑战。而云计算技术在易扩展性和高可用性等方面的优势正好可以弥补传统数据库的不足，因此Google提出的Mapreduce等技术得到了广泛的使用。随着研究和实践的深入，Mapreduce框架的一些问题逐渐显现出来，例如Mapreduce框架不支持数据索引，导致复杂查询类型相关计算的效率低就是问题之一，也是近年来研究的热点。一些研究工作在特定领域取得了不错的效果，但是它们都局限于解决特定的数据查询问题，导致数据索引方法不具备可扩展性；并且依赖于Hadoop技术而不是Mapreduce框架本身，因此不具有平台独立性。
　　本文对Mapreduce框架的分布式数据索引进行深入的研究，为研究目标建立了模型，总结现阶段相关研究的不足，分析本次工作的难点，设计实现了一种基于通用搜索树和Raft算法的可扩展数据索引方法即MRIndexer。使得MRIndexer具备索引结构可扩展性、高效的查询效率、高可用性和平台独立性。本文主要工作如下：
　　首先，将MRIndexer设计为非侵入式的索引服务，将Mapreduce框架与通用搜索树相结合，设计实现了在分布式文件系统和内存中建立、使用和更新维护索引的算法，通过向用户暴露接口的方式，实现底层索引结构的可扩展，使得用户可以根据查询计算的特点实现例如B+树、R树等不同的底层索引结构，同时建立了多个索引结构配合工作的机制，使得MRIndexer可以完成诸如多维查询等复杂的查询计算任务。
　　其次，通过对Raft算法的研究，设计实现了MRIndexer各模块间的消息传递机制，保证数据索引服务的一致性和高可用性。在此基础上结合Mapreduce框架的特点，借鉴传统数据库和分布式计算研究的相关经验，对MRIndexer提供索引服务的方法进行优化，设计实现了一种高效的内存管理及查询优化方法，保证MRIndexer可以长时间连续提供高效稳定的索引服务。
　　最后，在Hadoop和MPI+Phoenix两个Mapreduce环境中测试MRIndexer原型，使用R树和B+树索引结构，设计多种实验，进行多组横向和纵向测试。实验结果表明MRIndexer在查询效率、索引可扩展性、高可用性和平台独立性四个方面上具有良好的表现，证明本文设计实现的数据索引方法具有良好效果。

目录

声明

插图索引

表格索引

符号对照表

缩略语对照表

第一章 绪论

1.1 研究背景与意义

1.2 研究内容与目标

1.3 论文组织结构

1.4 本章小结

第二章 相关研究与技术

2.1 分布式数据索引相关研究

2.2 关键技术

2.3 本章小结

第三章 Mapreduce框架数据索引研究

3.1 研究目标建模

3.2 难点分析与解决方案

3.3 MRIndexer总体设计

3.4 本章小结

第四章 MRIndexer的设计与实现

4.1 MRIndexer关键接口设计

4.2 索引操作方法

4.3 MRIndexer的消息传递机制

4.4 内存管理及查询优化

4.5 本章小结

第五章 实验设计与测试分析

5.1 实验环境说明

5.2 查询效率及可扩展性测试

5.3 高可用及平台独立性测试

5.4 本章小结

第六章 总结与展望

6.1 总结

6.2 展望

参考文献

致谢

作者简介