唐玮峰 赵振戟

摘要：不断增大的数据规模给Hadoop集群处理能力带来了挑战，而合理的作业调度方式与策略能够提高集群的运行效率。通过对Hadoop MapReduce的任务调度机制进行研究，设计了节点负载能力与动态优先级的计算方式，提出了一种动态优先级的负载均衡调度算法，并搭建小型Hadoop平台进行了实验分析。结果表明，该算法在集群负载均衡方面的效果要优于传统调度算法。

关键词：Hadoop；负载均衡；MapReduce；调度算法

DOIDOI：10.11907/rjdk.161358

中图分类号：TP312

文献标识码：A 文章编号：1672-7800（2016）005-0047-03

0 引言

Hadoop[1]执行MapReduce的过程主要分为Map和Reduce两个阶段[2]，前者对数据进行划分和键值对处理，后者对划分后的数据片进行规约计算。然而Reducer所处理的数据是根据数据片的Key值分配的，由于数据本身特点的不确定性，Key值的分布通常不均衡，从而导致Reducer分配到的数据量与资源也容易出现不均衡状况，在数据量较大的情况下会严重影响MapReduce的任务处理效率[3]。

针对该问题，本文通过研究Hadoop的任务调度原理，结合相关负载均衡调度算法，提出了一种新的动态优先级负载均衡算法（DPLB），实现集群作业的动态负载，提高了Hadoop集群的资源利用率和系统响应速度。

1 MapReduce在Hadoop上的任务调度

Hadoop MapReduce的任务调度主要由JobTracker和TaskTracker两个进程来完成。JobTracker的作用是作业控制、状态监控以及资源管理，TaskTracker的作用是执行JobTracker下达的命令，并且周期性地将节点资源使用情况以及任务运行状态等信息通过心跳机制[4]汇报给JobTracker。Hadoop MapReduce的任务执行过程如图1所示。

在作业调度过程中，当一个Maptask完成之后并不会主动将输出的数据发送给Reducer，而是由Reducetask通过向JobTracker询问自身的节点状态是否能接受工作任务，得到JobTracker允许后会通过http协议从完成的Maptask获取属于自己的数据块，并根据Key值进行排序，最后调用用户定义的Reduce函数进行处理并输出结果。合理的调度算法能够更充分地利用集群中的TaskTracker，提高集群的并行处理效率。

2 常用Hadoop作业调度算法

2.1 FIFO调度算法

FIFO调度算法[5]通过单队列结构来存放提交的作业，新到达的作业排在队列尾，队列头部的作业拥有最高的执行优先级。该算法的缺点是不利于多作业的并行执行，另外时间先后优先级的方式没有考虑作业之间的差异性，容易导致小作业的长时间等待，无法充分利用系统资源。

2.2 Capacity Scheduler调度算法

基于容量的调度[6]算法采用多队列结构，每个队列配置一定比例的资源，当JobTracker接到一个作业时，会对各队列当前可用资源比重进行比较，将作业分配给可用资源最多的队列。Capacity Scheduler算法灵活性较好，但在队列的资源配置上依赖经验设置，管理难度较大。

2.3 Fair Scheduler 调度算法

公平调度算法[7]也采用多队列结构，不同的是该算法为每个用户配置了一个资源池，不管提交的作业有多少都能够保证每个用户分得均等的资源，并且允许每个资源池选择自己的调度方式。但该算法在分配资源池之前需要针对不同用户的数据特性做出不同的参数配置策略，因而在异构集群情况下的管理会变得十分复杂。

3 动态优先级负载均衡调度算法（DPLB）

3.1 算法思想

针对传统Hadoop集群调度算法的不足，提出DPLB（Dynamic Priority Load Balance，动态优先级负载均衡）算法。该算法利用TaskTracker周期性反馈的心跳信息计算节点负载情况与队列的任务承担能力，结合作业在队列中的等待时间与作业规模设计一种动态优先级，使小作业的等待时间减少，提高调度效率。

3.2 算法相关定义

3.2.1 节点负载能力NL与队列承载能力QL

其中，Twait表示作业在队列中的等待时间，Tres表示作业需要的资源量，由式（3）可以看出，作业的优先级会随着在队列中等待时间的增加而提高，同时考虑到了小作业优先执行的情况，作业需求的资源比越小，则优先级越高。

3.3 算法描述

基于心跳反馈的Hadoop动态负载均衡调度算法描述如下：

Step1：计算队列承载能力QL与当前并行的作业数TaskNum，若TaskNum达到最大并行作业数maxTask则转到Step10，否则转到Step2；

Step2：JobTracker将作业放入QL值最大的队列中；

Step3：遍历队列，根据Pri优先级进行作业排序；

Step4：计算各健康节点的负载能力NL，选出NL最高的健康节点；

Step5：判断该节点是否满足队列中一个作业的执行资源需求，满足则转Step6，否则转到Step9；

Step6：检查该节点的TaskTracker启动记录与任务失败记录，判断该节点是否健康，状态为true则转Step7，为false则转Step8；

Step7：将该节点的资源分配给该作业，转到Step1；

Step8：将该节点的健康状态标记为false，转到Step4；

Step9：将该作业转移至其它队列，转到Step3；

Step10：JobTask停止作业调度，算法结束。

过多的并行作业数量会对JobTracker造成很大负担，因此当并行的作业数量达到maxNum时会终止调度算法。另外，节点的健康与否主要由该节点执行上一个作业的失败次数来判断，若JobTracker检测到该节点在执行同一个任务时失败多次，则会将其标记为非健康节点，暂时脱离集群工作，直到管理员对该节点进行修复后将其重新分配给队列。

4 仿真实验结果与分析

4.1 实验环境与数据

根据实验室条件与设备情况，采用虚拟机搭建了4个节点的Hadoop集群，其中一个节点作为Master，其余3个节点作为Slave。为了体现异构环境，其中两台Slave虚拟主机配置为AMD单核CPU，主频2.9Gz，内存512M，硬盘大小为64G，另一台Slave与Master配置均为AMD双核CPU，主频2.9Gz，内存1G，系统采用Linux Redhat9.0，Hadoop版本为Hadoop1.2，代码编译采用Java jdk1.6.0_24。实验数据使用路透社的14 578条新闻集数据，在集群上运行K-均值聚类算法，聚类中心数设为200[8]。

4.2 实验结果与分析

实验使用DPLB算法与常用的3种Hadoop调度算法分别进行不同数据规模下的聚类分析，通过记录不同调度方式下的运行时间与节点负载情况来分析算法对Hadoop集群负载均衡的效果，结果如图2、图3所示。

从图2可以看出，DPLB算法在Hadoop作业执行的效率上与公平调度算法相当，但要优于FIFO算法与基于容量的调度算法。而在集群节点的负载均衡方面，DPLB算法取得了很好的效果。图3结果显示，DPLB算法在作业执行过程中对资源的占有量较高，究其原因在于实验中采用的数据集是条目较多的小文件，在DPLB的小作业相对优先的调度模式中使得并行的作业数增多，增加了节点压力，但在作业执行的整体效率上有明显提升。

5 结语

本文针对传统Hadoop作业调度模式可能出现的节点负载不均衡，以及资源利用率不高等问题，提出了一种动态优先级的负载均衡调度算法DPLB，通过实验证明了该算法在Hadoop集群作业的执行效率上要高于传统调度算法，并且能够有效实现集群节点的负载均衡。该算法在节点负载优化方面还有很大提升空间，后续将在此基础上重点研究如何降低TaskTracker的通信开销。

参考文献：

[1]WHITE T.Hadoop：the definitive guide[M].O'Reilly，2012.

[2]DEAN B J.Mapreduce：simplified data processing on large clusters[J].Osdi，2010， 51（1）：107-113.

[3]万聪，王翠荣，王聪，等.MapReduce模型中reduce阶段负载均衡分区算法研究[J].小型微型计算机系统，2015（2）：240-243.

[4]关国栋，滕飞，杨燕.基于心跳超时机制的Hadoop实时容错技术[J].计算机应用，2015，35（10）：2784-2788.

[5]王峰.Hadoop集群作业的调度算法[J].程序员，2009（12）：119-121.

[6]CHEN H，CUI D.SLa-based hadoop capacity scheduler algorithm[C].2015 International Conference on Electronic Science and Automation Control，2015.

[7]潘旭明.Map Reduce Fair Scheduler的高性能优化及超大规模集群模拟器设计及实现[D].杭州：浙江大学，2012.

[8]赵卫中，马慧芳，傅燕翔，等.基于云计算平台Hadoop的并行K-means聚类算法设计研究[J].计算机科学，2011，38（10）：166-168.

（责任编辑：孙 娟）