大规模数据比对的新型实现方法

摘要：MapReduce是一个“与处理以及生成大量数据集相关联的”程序模型。程序员用这种风格的程序写出的代码可以自动并行。运行时系统关注输入数据的分区，通过一系列机器的集合来规划程序的执行，处理程序失效以及把控必要的系统内部交互。详细描述了通过MapReduce框架实现传统应用的过程。

关键词：MapReduce；云计算；比对

中图分类号：TP392文献标识码：A文章编号：1009-3044(2012)13-2975-04

A New Method of Large Scale Data Comparison

YIN Xiao-ke1, ZHAN Mao-xi2

(1. R & D Division of Science and Technology Department of Shanghai Public Security Bureau, Shanghai 200042, China; 2. Department of Information Engineering, Changjiang Engineering Vocational College, Wuhan 430212, China)

Abstract: MapReduce is the program model associated with processing and generating large data sets. The program code wrote by programmers use this style can automatically parallel. Runtime system concerned about the partition of the input data, planning the implementation of the program through a series of collection of the machine, processing failure and controlling necessary within the system interact. Described the traditional application of the MapReduce framework in detailed.

Key words: MapReduce; cloud computing; comparison

MapReduce从技术特征上说，只是一类分布式并行计算的方法而已，而云计算的提出，本身只是一个按需提供计算能力的计算服务模式而已。二者是接口和实现的关系，并没有天然的必然联系。但是MapReduce对于很多典型的“分治法”适用的算法都可以有相当的效果。因此，对于很多云计算服务来说，MapReduce是一种合理的后台计算支撑架构，用这一计算模式来满足云计算对用户的服务质量承诺是个好选择[1]。

MapReduce适合于处理TB级或PB级的数据处理，因此对于目前信息爆炸的时代，我们有些利用传统的方法无法解决或者需要很长计算时间才能得出结果的问题需要引进MapReduce的方法进行处理。MapReduce把解决问题分成两个不同的步骤：

Map：初始化数据的读入和转换，在此期间，框架对互不依赖的输入记录进行并行处理。

Reduce：处理数据的组合和抽样，有关联的数据必须通过一个模块进行集中处理。

Map任务首先并行的对每一块进行单独的处理。这些逻辑块的处理结果会被重新组合成不同的排序的集合，这些集合最后由Reduce任务进行处理。图1是MapReduce的处理模型。

一个Map任务可以执行在集群中的任何一个计算机节点上。多个Map任务可以并行的执行在集群中的多个节点上。Map任务负责转换输入记录成为名值对。所有Map任务的输出会被重新组合成多个排序的集合，这里面的每一个排序的集合会被派发给一个单独的Reduce任务。Reduce任务会对集合中排序的关键词和关联在关键词的多个数据值进行处理。Reduce任务也是并行的运行在集群中的不同节点上的[2]。

目前在很多实际应用中，需要处理大量的比对任务，传统的解决方案是利用大型成熟关系型数据库在小型机上进行数据关联运算，目前，数据比对分前台比对与后台比对，但是比对方案都是利用了关系型数据库的关系运算来实现。如图2所示。

如图2所示，传统的比对算法将待比对的数据源中的数据表抽取到中间临时的比对数据库中，然后根据所需要比对的字段（Table1的value和Table2的value）进行是否相同的比对，比对的最终结果是保存在比对结果表中（Tableresult）。如上图中比对经过，计算机需要将其中一张表的所有的value值与另外一张表的value值进行比对，计算次数为Table1和Table2的被比对字段记录数的乘积，该方法可以通过数据库优化的方式实现，例如添加被比对列的索引和分区来实现，但是并不是所有的被比对列都已经加了索引和分区，如果需要临时加则索引和分区的创建时间更长。因此在遇到大的数据量比对的情况下，传统的比对方式显然力不从心，因为在传统的方式下，一个比对任务一般是由一个进程完成，在一个进程里利用的cpu仅仅是一个，因此不管是计算量多大，都考验着这个cpu的计算能力和相应的内存、I/O等，整个比对进程的执行时间是与被比对的数据量大小成正比的，如果想提高计算速度只能提高cpu的运算能力以及相关内存大小以及I/O的吞吐能力，如果其中一个速度慢则称为整个计算速度的瓶颈。

因此在数据量越来越大的情况下，比对运算单靠一个cpu已经无法满足实际需要，因此要引入成熟的并行计算框架，让比对任务分成多份，由多个cpu或多台机器实现相应的比对功能。Mapreduce正是为我们提供了这样一个成熟的计算框架，使我们的运算可以在多台机器上并行大数据比对，最终使这些机器实现我们大规模数据的比对运算。

图1

图2

1）在AB两个库里面的key值分别加上’A’和‘B’标记，这里是做map的过程，然后将两个库比对的数据进行汇总，把两个库的所有记录统一作为Map的输入。

2）然后将整理好的记录汇总表分割成若干小片，小片的大小以数据总量和需要进行并行计算的cpu来看。

3）上述的多个分割程序中的一个称之为master，其余的拷贝由Master赋予work，有称之为M的map任务和称之为R的Reduce任务。master将唤醒空闲状态的work线程，并赋予其map任务或Reduce任务。

4）每个map任务还根据自己的value对各自的记录进行排序。

5）reduce线程对经过排序的中间数据进行迭代遍历，将其遇到的每一个value值传送给用户定义的reduce功能，附带传送该键所对应的值的集合。

6）当所有的map任务和reduce任务全部结束，master将唤醒用户程序，经过集合好的数据重新整理如果两个记录同时又相同的value的则进行数据转换操作，最终形成比对结果。

①合并记录，如图3所示。

图3

②分割作MAP标记，如图4所示。

图4

③分别进行排序操作，以及进行REDUCE聚合，如图5所示。

④遍历整个记录并进行结果重组，如图6所示。

在实际应用中，往往是仅要输出某一种数据源的结果，则可以将输出再做一次MapReduce操作，即将数据源本身作为map标记，然后根据记录的value值进行分割操作，在每一个map里面做value的count操作，将count值更换原先的value值，然后根据将count值大于1的通过reduce操作输出出来，然后根据需要输出的数据源标记判定比对完成的数据源。

我们的数据如今大多存储在传统关系型数据库中，因此当用户程序调用MapReduce时，不是直接读取我们现有的数据库数据，而是通过一下几步完成整个计算：

1）将关系型数据库需要比对的数据按照MapReduce的要求导成一定格式的文件。

2）MapReduce首先将输入文件分割成M个小片，大小从16M到64M不等。

3）上述的多个集群节点的一个称之为master，其余的拷贝由Master赋予任务，有称之为M的map任务和称之为R的Reduce任务。master将唤醒空闲状态的线程，并赋予其map任务或Reduce任务。

4）被赋予了map任务的工作线程读取相应的输入分割文件的内容，并将产生的中间键值对被缓存在内存当中。

5）这些中间值会不断写到本地磁盘之上，在本地磁盘上缓存着的中间键值对的地址被传递回master，master此时通知Reduce进程通过远程调用的方式访问这些存储在磁盘上的中间键值对，并开始Reduce计算操作。

图5

图6

6）当所有的map任务和reduce任务全部结束，master将唤醒用户程序，用户程序将结果生成的数据文件导入再导入到关系数据库中。

通过以上方式，我们探索了在大数据量的情况下，利用现在流行的MapReduce计算框架实现对传统关系型数据库的数据的比对操作，该方法对于小规模数据比对的速度提升并不明显，因为其在数据比对过程中穿插做map和reduce操作，消耗了一定的cpu工作时，另外还会消耗部分的I/O操作，但是对于大规模数据比对，在一般串行计算的比对操作主要cpu工作时都在数据比较的情况下，该种并行计算框架随着参与计算的服务器的数量的增多则可以提供较快的比对输出结果。该种方式在对于跨节点的内存数据访问如果能够突破的话，则更加能够加快数据计算速度。

参考文献：

[1] Valiant L G.A bridging model for parallel computation[J].Communications of the ACM,1997,33(8):103-111.

[2] White T.Hadoop权威指南[M].2版.北京:清华大学出版社,2010.

（编辑：温州站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!