一种基于MapReduce的分布式索引方法
扫描二维码
随时随地手机看文章
引言
海量数据的使用越来越受到人们的关注，如何实现为海量文本数据快速创建索引以供用户检索已经成为当前面临的一个重要课题。传统的集中式索引方案已经无法满足需求，随着MapReduce机制的出现，人们开始研究使用MapReduce进行分布式索引的方案。现有的基于MapReduce的方法都局限于MapReduce的原始框架，无法处理数据量大、不可分割的文档，也缺乏对海量索引的管理机制。因此，通过对现有方法的改进，本文设计了一种面向海量大文本的MapReduce索引方法，通过实验测试了改进方案的索引性能。
1 MapReduce简介
MapReduce是一种通过将任务分发到多台机器上来处理大规模数据的编程模式。它最初是由Google设计的,用于利用分布式架构来处理大数据集上的计算任务。一个MapReduce工作主要使用Map和Reduce两个函数。Map函数接收一个<key,value〉键值对作为输入，然后通过特定的计算输出一组中间键值对<key,value〉。所有Map函数的输出键值对将会自动按照key进行排序和分组，然后传送给Reduce函数。Reduce函数将有着相同key的所有中间键值对进行合并，得到最终的结果集。一般处理输入数据的Map任务会比较多，而处理Map任务输出数据的Reduce任务会少一点。Map任务和Reduce任务都可以运行在不同的机器上来实现并行化，每个任务都是独立于其他同类型的任务的，这就使得分布式应用的开发变得轻松了许多。
2 MI-RM索引方法
本文设计的分布式索引方法的主要思想是：在Map函数中执行文档的解析及索引，而在Reduce函数中合并这些索引数据，即“MapIndex-ReduceMerge”，简记为MI-RM方法。MI-RM方法采用的策略是，将文档平均分组，每个组内的文档的索引数据交给一个Reduce任务来合并。Map函数输出的中间键值对是〈DocGroup,DocIndex〉，其中DocGroup表示该文档所属的分组，DocIndex表示该文档的索引数据。这样,中间键值对的数量就会少了很多，排序的工作量会大大地减少。
Map算法的输入键值对是〈DocGroup,DocPath>,即一个文档的分组号及其存储路径。Map函数从HDFS文件系统得到该文档的输入流，并且用文档解析器来封装文档输入流,用以解析文档格式。然后，算法即可顺序读取文档的内容，并将其索引到DocIndex中。索引完成后，将该文档的索引数据按照〈DocGroup,DocIndex>键值对的格式输出。
Reduce函数对同组文档的索引嗷据进行归并。我们设计了支持自动分片的Reduce函数，将同组的文档索引再次分片,合并到不同的索引片中。Reduce在合并索引数据的时候，将会控制索弓片的大小；如果索弓片已经达到了阀值，那么就将其作为一个独立的索引片输出，然后再创建一个新的索弓片来存储剩余数据，如此往复。表1和表2分别展示了MI-RM的Map和Reduce函数及其算法流程。
3 测试结果
3.1 测试环境
首先，我们可以搭建包含3台机器的集群，部署Hadoop进行分布式索引测试。操作系统均Ubuntu8.10,HDFS版本是1.9.2。
本文使用数据生成器随机生成了18个大小为10MB的文本进行测试。因为测试环境有限,本文没有使用大的数据量,文本的数量选择为18是考虑到它正好是节点数的整数倍，可以使得任务在各节点上并行的运行。
3.2 结果与分析
在测试中，我们将MI-RM索引方法配置为18个Map任务和3个Reduce任务。其中每个节点上可以并发地执行6个任务，也就是说，Map任务的最大并发量为6。测试结果如下:Map执行的总时间为34.253s，Reduce执行的总时间为35.515s,总的执行时间为45.232s，而采用集中式索引方法处理同样的数据则需要97.232s，该结果体现了MI-RM索引方法的效率要优于传统的集中式索引方法。
4 结语
本文探讨了一种基于MapReduce的分布式索引方法，并与集中式索引方法做了测试比较，通过实验表明这种方法能够减化文档排序的工作量，从而提高建立文本索弓啲效率，能够满足海量文本数据检索的需求。
下载文档
