Hadoop平台下MapReduce模型调度算法研究＊
刘 伟，杜永文，吕晓剑
【摘 要】针对Hadoop默认FIFO调度算法和Fair调度算法、Capacity调度算法的不足，引入了一种基于优先权的自适应MapReduce调度算法.该算法利用作业权值为不同的Job分配不同的系统资源，同时根据各TaskTracker节点反馈回来的消息调整可执行队列的长度，以达到各节点负载平衡，提高系统的执行效率.
【期刊名称】广西民族大学学报（自然科学版） 【年(卷),期】2014(020)003 【总页数】4
【关键词】Hadoop；MapReduce；调度算法；基于优先权的自适应调度算法 现代社会已经进入数据爆炸的时代，如何简化大型集群对海量数据做并行处理的编程方法成为一大热门研究课题.而云计算的出现为我们提供了一个可行性平台，其中Hadoop是一种开源实现了分布式调度模块MapReduce编程模型的分布式系统框架，主要用于对海量数据集进行分布式处理.从大方面来说，Hadoop平台由HadoopCore和 Hadoop子项目两部分共同组成，其中HadoopCore是系统框架的核心，主要包括分布式文件系统 HDFS和分布式处理框架 MapReduce.Hadoop集群架构如图1所示.
1 MapReduce处理流程
分布式调度框架MapReduce的核心思想采用了“分而治之”的理论，首先通过Map函数将海量数据分割成众多子任务，而这些个子任务分别交由集群中不同的计算结点进行并行处理，然后将得到的中间结果通过Reduce函数进行
合并就可以得到最终结果，MapReduce集群结构如图2所示.
MapReduce具体的实现框架主要是 Master，Worker与 Disk打交道［1－2］.用户将编好的 MapReduce应用程序同配置文件打包成Jar文件提交给系统.系统会载入该函数程序来执行运算任务，执行流程包括6个部分：数据分块、任务分派、MapWorker节点获取数据、本地存储、ReduceWorker节点读取数据和结果输出，流程图如图3所示.
与传统的移动数据计算方式相比，分布式调度算法MapReduce则巧妙的采用了移动计算的方式解决宽带受限的瓶颈问题.海量数据分布存储、计算随数据分散的原则，简化了并行程序开发难度的同时提高了集群整体的运行效率.但多任务的调度会带来宽带和时间的大量消耗，如何实现有效调度，国内外学者先后提出了多种算法.
2 现有调度算法研究
2.1 FIFO调度算法
带有优先级的FIFO（First In First Out）算法［3］是Hadoop默认的调度策略.所有的用户作业都被提交到一个队列当中保存，当Master收到一个Worker结点中TaskTracker的空闲信息时，按照提交时间的先后和优先级的高低选取一个满足要求的作业去执行.任务的执行分为map和reduce两个操作，MapReduce函数如表1所示，调度器按照最近原则来确定map任务. FIFO算法主要针对单用户单一类型作业设计，其中JobTracker实现机制简单且算法编程开销小，但伴随着Hadoop平台的使用率的快速增长，用户和作业多样性的现象也频繁出现，但是FIFO算法却忽略了多用户不同作业间的需求差异，这往往会造成系统资源和平台性能的利用率不高，甚至会造成作业的执
行失败，这严重影响了系统的交互能力和用户的使用体验. 2.2 Fair调度算法
Fair调度算法是Facebook提出来的［4］.算法的设计理想是想让所有的作业随着时间的推移都能够较为平均的获取到等量的CPU计算资源.
算法主要通过“作业池”来实现，整个调度过程可以从外到内分成两个级别： 第一级是“池间”资源调度，Fair调度算法为每个用户建立一个单独的“作业池（pool）”，池ID通过相应的用户ID进行标识，池的基本组成单元是作业.缺省情况下，系统可以根据用户数量按照最小共享额度机制分配系统资源，当集群繁忙时，闲的槽位可以通过资源调配，达到资源的优势互补，提高系统的工作效率；
第二级是“池内”的作业调度，通常采用公平共享（FairShare）、优先级权重等方法在单用户的多作业间合理分配共享资源容量. 2.3 Capacity调度算法
该算法是雅虎提出的，在最初提出之时虽然被怀疑，但实际证明该方法还是可取的.与FIFO算法不同的是，Capacity算法采用多个队列来维护用户作业任务，在每个队列内采用基于优先级、不支持抢占的FIFO算法. Capacity算法有以下4个特点：
1）每个Queue通过 mapred－site.xml和capacity－scheduler.xml配置文件获取相应的计算资源和一定数目来自Worker节点的TaskTracker任务请求. 2）系统会为每个队列设置一个百分比比值（即正在执行的任务数／分得的计算资源＊100%）用来显示当前队列的负载情况.当 Master节点中Job－Tracker接收到TaskTracker任务请求后，会选择一个比值最低的Queue，并从中挑选
Hadoop平台下MapReduce模型调度算法研究
