《MapReduce并行计算技术发展综述》由会员分享，可在线阅读，更多相关《MapReduce并行计算技术发展综述（6页珍藏版）》请在金锄头文库上搜索。
1、MapReduce并行计算技术发展综述摘要:经过几年的发展,并行编程模型MapReduce产生了若干个改进框架,它们都是针对传统MapReduce的不足进行的修正或重写.本文阐述和分析了这些研究成果,包括:以HaLoop为代表的迭代计算框架、以Twitter为代表的实时计算框架、以ApacheHama为代表的图计算框架以及以ApacheYARN为代表的框架管理平台.这些专用系统在大数据领域发挥着越来越重要的作用.MapReduce1是Google公司于2004年提出的能并发处理海量数据的并行编程模型,其特点是简单易学、适用广泛,能够降低并行编程难度,让程序员从繁杂的并行编程工作中解脱出来,轻松
2、地编写简单、高效的并行程序.针对上述问题,MapReduce并行编程模型的最大优势在于能够屏蔽底层实现细节,有效降低并行编程难度,提高编程效率.其主要贡献在于:使用廉价的商用机器组成集群,费用较低,同时又能具有较高的性能;松耦合和无共享结构使之具有良好的可扩展性;用户可根据需要自定义Map、Reduce和Partition等函数;提供了一个运行时支持库,它支持任务的自动并行执行.提供的接口便于用户高效地进行任务调度、负载均衡、容错和一致性管理等;MapReduce适用范围广泛,不仅适用于搜索领域,也适用于满足MapReduce要求的其它领域计算任务2MapReduce总体研究状况最近几年,在处
3、理TB和PB级数据方面,MapReduce已经成为使用最为广泛的并行编程模型之一.国内外MapReduce相关的研究成果主要有以下几方面:(1)在编程模型改进方面:MapReduce存在诸多不足.目前,典型研究成果有Barrier-lessMapReduce6、MapReduceMerge7、Oivos8、Kahnprocessnetworks9等.但这些模型均仅针对MapReduce某方面的不足,研究片面,并且都没有得到广泛应用,部分模型也不成熟(2)在模型针对不同平台的实现方面:典型研究成果包括:Hadoop10、Phoenix11,12、Mars13、CellMapRe-duce14、M
4、isco15和Ussop16部分平台(例如:GPUs和Cell/B.E.)由于底层硬件比较复杂,造成编程难度较大,增加了用户编程的负担.(3)在运行时支持库(包括:任务调度、负载均衡和容错)方面:常用的任务调度策略是任务窃取,但该策略有时会加大通信开销.典型的研究成果包括:延迟调度策略17、LATE调度策略18和基于性能驱动的任务调度策略19等.在容错方面的典型研究成果是reduce对象20.目前,运行时支持库中针对一致性管理和资源分配等方面的研究相对较少.(4) 在性能分析与优化方面: 目前, 文献 21主要研究在全虚拟环境下MapReduce 性能分析, 文献 22则提出了名为MRBenc
5、h 的性能分析评价指标. 性能优化典型成果包括: 几何规划 23、 动态优先级管理 24和硬件加速器 25等. 着眼于性能, 结合运行时支持库, 将是MapReduce研究的热点之一.(5) 在安全性和节能方面: 安全性方面典型研究成果是 Sec ureMR模型 2 6. 文献 27和文献 28 则在节能方面做了相应的研究. 目前国内外在安全性和节能方面的研究成果相对较少, 但是这方面研究的重要性已经得到了越来越多的重视. 如果一个模型没有很高的安全性, 同时也没有很好地考虑功耗问题, 那对其大范围推广将产生致命的影响.(6) 在实际应用方面: MapReduce 应用范围广泛,Google
6、等诸多公司都在使用MapReduce 来加速或者简化各自公司的业务 29. MapReduce 还广泛应用于云计算 3 0和图像处理 31等领域. 随着科技的进步, MapRe -duc e 将会得到越来越广泛的应用.国内学者MapReduce 相关研究成果主要集中在实际应用方面. 例如, 把MapReduce 应用于模式发现 32和数据挖掘 3 3等领域. 部分研究成果涉及模型针对不同平台的实现、 任务调度、 容错和性能评估优化. 例如, 文献 34提出了名为 FPMR 的基于FPGA 平台的 MapRe -duc e 实现, 文献 35提出了基于已知数据分布的任务调度策略, 文献 36提出
7、了名为 SAMR的异构环境下自适应任务调度策略, 文献 37提出了基于目录的双阶段错误恢复机制, 文献 38提出了名为The HiBench Bench -mark Sui te 的性能评估指标, 文献 39提出利用分布式的研究起步稍晚, 绝大部分研究集中在应用方面. 对MapReduce 关键技术也进行了研究. 但是相对于国外,国内在这些方面的研究成果较少.3 MapReduce模型及其改进 Google 公司最早提出了MapReduce 并行编程模型,当用户程序调用MapReduce运行时支持库时, 其执行过程如下(如图1 所示) :( 1)首先, 用户程序把输入数据分割成 M 份, 每份
8、为16MB到64MB大小的数据块(可通过参数来设定) .然后, 开始在集群上进行程序的拷贝. 这些程序拷贝中有一份是Master,其余都是向Maste r 请求任务的Worker;( 2)一旦分配到Map任务,Worke r 便从相应的输入数据中分析出 ke y/ value 对, 并把每个 key/ value 对作为用户定义的 Map函数的输入. Map函数产生的中间值key/ value 对被存储在内存中;( 3)存储在内存里的中间值 key/ value 对会被定期写入本地磁盘中, 用户定义的Parti tion函数将其划分为多个部分,Master 负责把这些中间值key/ value
9、对在本地磁盘上的存储位置传送给执行Reduce 任务的Worker;( 4)通过远程过程调用, 执行Reduce 任务的Worker从执行Map任务的Worker 的本地磁盘读取中间值 ke y/value对;( 5)当一个执行Reduce 任务的Worker 从远程读取到所有所需的中间值 key/ value 对之后, 通过排序将具有相同key的中间值key/ value对聚合在一起, 形成ke y/value s 对, 作为Reduce 函数的输入;( 6)每个Reduc e 函数的输出分别放到相应的输出文件中. 当所有的Map和Reduce 任务都执行完毕,Mas -ter 唤醒用户程序
10、. 此时, 用户程序中的MapReduce 调用返回用户代码.MapReduce 可以处理TB和PB量级的数据, 能很方便地在许多机器上实现数据密集型计算的并行化. 算法1 给出基于MapReduce 的单词统计程序伪代码, 程序功能是统计文本中所有单词出现的次数.Map函数产生每个词和这个词的出现次数(在本例中就是 1) . Reduce函数把产生的每一个特定词的计数加在一起.上述要求MapReduce 缺乏支持处理多个相关异构数据集的能力. 为此, 文献 7 提出了MapReduceMerge 并行编程模型, 对多个异构数据集分别执行Map和Reduce 操作,之后在Merge 阶段把Re
11、duce 阶段已分割和分类融合的数据进行有效地合并.MapReduceMerge尽管能够处理多个相关异构数据集, 但是并不支持自动执行多次MapReduceMerge 过程.当用户手动执行多次 MapReduce 或者 MapReduceMe rge过程时, 用户需要解决任务调度、 同步性和容错等问题, 编程负担过重. 为此, 文献 8 提出了 Oivos 并行编程模型, Oivos 利用抽象层来实现自动管理执行多次MapReduce 或者MapReduceMe rge过程. Oivos需要用户指定处理多个相关异构数据集所需 MapReduce 或者MapReduceMe rge过程的个数,
12、并通过检测逻辑时间戳来自动发现哪些任务需要重新执行.MapReduce 并行编程模型死板, 且不能很好地适应小规模集群. 为此, 基于消息传递和无共享模型, 文献 9提出了名为KPNs ( Kahn process ne tworks)的并行编程模型. KPNs可自动执行迭代计算, 且编程灵活(例如:KPNs的输入不必抽象成 key/ value 对的形式) . 同时, 把串行算法改写成 KPNs 形式仅需在恰当的地方插入通信状态. 但是该模型仍需大量的实验来验证其性能与可扩展性.表 1显示了MapReduce 并行编程模型及其改进研究对比. 通过比较不难看出, 以 Google 公司提出的M
13、apReduce为基础, 针对其不足, 很多研究学者进行了相关研究, 并取得了一定的研究成果. 但是仍存在着一些不足: 首先, 这些模型均仅针对MapReduce 某个方面的不足, 研究较为片面, 并且都没有得到广泛的应用.其次, 部分模型并不成熟, 仍需要进一步的实验来验证其性能与可扩展性.最后, 没有研究结合不同模型的特点, 得出一个全面优化的并行编程模型3.2 针对不同平台实现方面的研究受到 Google 公司提出的MapReduce 并行编程模型启发, 目前被广泛使用的代表是Hadoop. 它是一个开源的可运行于大型分布式集群上的并行编程框架, 提供了一个支持MapReduce并行编程
14、模型的部件.Hadoop具有良好的存储和计算可扩展性; 具有分布式处理的可靠性和高效性; 具有良好的经济性(运行在普通 PC 机上) .Hadoop也存在一些不足: 小块数据处理由于系统开销等原因处理速度并不一定比串行程序快; 如果计算产生的中间结果文件非常巨大, Reduce 过程需要通过远程过程调用来获取这些中间结果文件, 会加大网络传输的开销; Hadoop 作为一个比较新的项目,性能和稳定性的提升还需一定时间.随着科技的进步与硬件平台的发展, 许多研究学者在不同的实验平台上实现了MapReduce, 并取得了一定的研究成果. 其主要的研究成果包括:(1)在共享内存平台上: 斯坦福大学计
15、算机系统实验室在共享内存系统上实现了 MapReduce, 被称为Phoenix. Phoenix 采用线程来实现Map和Reduce任务, 同时利用共享内存缓冲区实现通信, 从而避免了因数据拷贝产生的开销. 但Phoenix 也存在不能自动执行迭代计算、 没有高效的错误发现机制等不足.(2)在GPUs 平台上: Mars 是基于GPUs( 图形处理器)的MapReduce 实现.Ma rs也具有Map与Reduce 这两个步骤. 在每个步骤开始之前, Mars对线程配置进行初始化 (包括:线程组的个数、 每个线程组中线程的个数等) . 由于GPU线程不支持运行时动态调度, 所以给每个GPU
16、线程分配的任务是固定的. 若输入数据划分不均匀, 必将导致Map或者Reduce 阶段的负载不均衡, 使得整个系统性能急剧降低. 同时由于 GPU 不支持运行时在设备内存中分配空间, 需要预先在设备内存中分配好输入数据和输出数据的存放空间. 但是在 Map 和Reduce阶段输出数据大小是未知的, 并且当多个 GPU线程同时向共享输出区域中写数据时, 易造成写冲突.另外, 由于Mars的编程接口是为图形处理而专门设计的, 因此用户编程较为复杂.(3) 在 Cell / B. E. 平台上: Cell MapReduce 是基于Cell / B. E. (Cell宽带引擎)的MapReduce 实现. 将MapRe -duc e 移植到Cell / B. E. 架构主要存在三个
