Hadoop平台公平调度算法研究与优化

张连义 杜中军 李震

摘  要： Hadoop MapReduce框架的公平调度算法以统一的固定配置文件管理计算节点上计算槽的数量，这不能保障集群负载均衡，亦不能满足不同用户的资源需求。针对公平调度算法配置方式的不足，提出一种动态反馈的调度算法。该算法结合公平调度算法预先分配的特性，能够对计算节点上的计算槽进行动态调整。实验结果表明，基于动态反馈的改进算法有效地提高了集群的执行效率。

关键词： Hadoop; MapReduce; 公平调度算法; 动态反馈

中图分类号：TP311          文献标志码：A     文章编号：1006-8228（2014）12-45-03

Research and improve of fair scheduling algorithms based on Hadoop platform

Zhang Lianyi， Du Zhongjun， Li Zhen

（Sichuan university， college of computer science， Chengdu， Sichuan 610065， China）

Abstract： Unified fixed configuration file is utilized in fair scheduling algorithm of the Hadoop MapReduce framework to calculate the number of slots in computing nodes. It cant guarantee the load balancing cluster especially in heterogeneous environment and satisfy the different requirement on the resource of different users. Aiming at the shortcomings of the existing configuration ways in fair scheduling algorithm， a dynamic feedback scheduling algorithm is proposed. Combined with the characteristics of pre-allocated algorithm， the computing nodes on the slots can be adjusted dynamically. The experimental results shows that the improved algorithm based on dynamic feedback can efficiently improve the execution efficiency of the cluster.

Key words： Hadoop; MapReduce; fair scheduling; dynamic feedback

0 引言

作业调度算法是一个集群的核心[1]，其主要功能是分配集群资源和对任务执行顺序进行有效控制，多以插件的形式集成到Hadoop中[2-3]。当前较常用的公平调度算法（Fair Scheduling）因未考虑计算节点负载与任务失败率之间的关系，在多用户多任务环境下易导致资源负载不均衡，任务失败率高。为此提出一种动态反馈的改进算法，通过不断观察学习任务执行过程中计算资源的占有情况，对计算节点上的计算槽进行动态调整，以提高MapReduce计算框架的整体性能和集群资源利用率。

1 Hadoop MapReduce框架

1.1 Hadoop MapReduce概述

Hadoop MapReduce是一种处理海量数据的并行编程模型，用户选择自定义的Map函数和Reduce函数即可并行处理海量数据。

Hadoop MapReduce将分布式计算形象的描述为key/value键值对，以键值对的形式在集群中进行操作。MapReduce运算包括Map和Reduce两个过程。Map阶段计算节点从输入数据块中提取key/value键值对，传递给自定义的Map函数，由Map函数来产生中间key/value键值对。通过哈希函数将键值对分成R份并写入本地磁盘。Reduce阶段对Map函数产生的中间键值对进行规约，Reduce函数从远端复制对应的key/value，并依据key进行value排序、结果合并、数据块输出。

1.2 Hadoop MapReduce中的调度算法

Hadoop中的作业调度指Job Tracker指派任务（Tasks）到Task Tracker上执行的过程。现有的调度算法主要有先进先出调度算法[4]（FIFO）、计算能力调度算法（Capacity） 和公平调度算法（Fair）。

1.2.1 FIFO调度算法

FIFO调度算法（First In First Out）是最早出现在Hadoop MapReduce计算框架中的调度算法。所有用户的作业都提交到一个队列中，由Job Tracker依此按照作业的优先级和提交时间控制作业的执行顺序。FIFO调度算法简单方便，易于实现，减轻了JobTracker的负担，但未考虑作业的紧迫程度，忽略了不同作业的需求差异。

1.2.2 计算能力调度算法

计算能力调度算法（Capacity Scheduler）的核心思想是为每一个作业队列定义一个指标——队列中正在运行的作业数与其应该分得的计算资源之间的比值。当系统出现空闲的Task Tracker，算法优先选择比值最低的作业执行。计算能力调度算法必须对用户数量进行限制，否则将出现多个用户严重不公平的情况。新作业运行前，首先考虑作业所属用户是否超出资源限制。

1.2.3 公平调度算法

公平调度算法是Facebook提出的一种调度算法。公平调度的目的是让所有作业能获取等同的共享资源。一个作业单独运行将使用整个集群，其他作业提交时，系统将任务空闲时间片（Slot）赋给新的作业，以使每一个作业获取到等量的CPU时间。公平调度器按资源池（Pool）来组织作业，并把资源公平的分到资源池里。默认每一个用户拥有一个独立的资源池，以保障无论用户提交多少作业都能获得等同的集群资源。

2 基于动态反馈策略的改进算法

公平调度算法通过设置最小资源共享量和公平份额进行任务分配，较适合小作业的执行，但算法未考虑计算节点负载与任务失败率的关联，以致在多用户多任务环境下，资源负载不平衡，任务失败率高，不利于缩短任务的执行时间和提高系统吞吐量。

2.1 公平调度算法分析

公平调度算法通过预先配置的方式将任务分配至计算节点。

首先，集群管理员需配置计算节点最大slot，若slot配置过高，将导致资源间竞争激烈，备份任务和失败任务增多;若slot配置的过低，将导致资源利用率过低，集群性能无法充分发挥。对集群尤其是存在大量异构计算节点的集群，配置合理的slot数难于把握。

其次，分配到计算节点上的task所消耗的计算资源各不相同，有些CPU占用率高，有些内存消耗大，有些I/O繁忙，而大部分task混合使用资源。如何在多用户多任务情况下合理分配资源，既要满足不同用户资源需求，又能保障集群特别是异构环境下的集群负载均衡？本文提出一种动态反馈的调度算法，算法结合公平调度算法预先分配的特性，通过不断观察学习任务执行过程中计算资源的占有情况决定TaskTracker向JobTracker请求任务的时间。

2.2 改进算法参数定义及评价函数

在异构集群环境中，R={r1…rj… rn}表示计算节点（rj表示第j个计算节点，集群中共有n个计算节点）。L={l1…lj…ln}表示节点的负载值（lj表示计算节点rj的负载值）。节点rj上CPU使用率、内存利用率、I/O吞吐量分别为C%、M%、I%，则计算节点rj的动态负载值lj可以表示为：

⑴

其中λn表示各参数的重要性，j=1，2，…，m，m值为3时，。

延迟调度实验表明，任务的平均失败率与节点的负载成正比。文献[5]通过大量实验对节点的动态负载情况进行曲线拟合得到的函数表达式为：

⑵

Ej表示计算节点j的平均失败率，表示节点的负载情况。

以LloadRate表示负载轻度值， HloadRate表示负载重度值。计算节点周期性收集CPU，MEM，I/O等信息，根据公式2计算负载值LoadRate，通过LoadRate与HloadRate和LloadRate值的比较决定是否向JobTracker发送task申请。

当LoadRate=LloadRate并且LoadRate<=HloadRate时，只有存在空闲slot，计算节点才向JobTracker请求task;当LoadRate>HloadRate时，节点负载过重，如果TaskTracker继续向JobTracker请求task，将造成计算节点上存在慢任务，甚至出现错误任务。此时若出现空闲slot，延迟T1时间TaskTracker向JobTracker请求task。

2.3 改进算法描述

以下是改进的公平调度算法描述。

⑴ 收集计算节点资源信息负载情况，包括CPU使用率、空闲物理内存I/O读写频率、网络传输速率、磁盘剩余空间等。

⑵ 根据计算节点的实时负载值LoadRate判断：若LoadRate小于LloadRate转向步骤⑶，大于LloadRate并且小于HloadRate转向步骤⑷，大于HloadRate转向步骤⑸。

⑶ 计算节点部分资源处于空闲状态，无论计算节点是否出现空闲slot， TaskTracker都以心跳的形式向JobTracker请求一个task 。

⑷ 计算节点处于正常负载，任务执行和资源利用处于最佳状态。仅当计算节点中出现空闲slot时，TaskTracker才向JobTracker请求task。

⑸ 计算节点处于负载过重状态，TaskTracker延迟T1的时间再次计算该节点的负载值。若经过T1时间计算节点中出现空闲slot，计算节点重新计算该节点的负载值后决定是否向JobTracker请求task。

3 实验

3.1 实验环境

四台计算机通过一台普通路由器连接，操作系统为redhat-server-6.0-i386，java jdk版本1.6.0_17，hadoop版本hadoop-1.0.4，开发工具：MyEclipse8.5。

3.2 响应时间实验

对先进先出调度算法（FIFO）、公平调度算法（FS）、基于动态反馈的公平调度算法（DFFS）进行测试。测试程序采用hadoop提供的基准测试程序，选择GrepCount、TeraSort和WordCount作为测试用例。在三种算法中分别进行GrepCount、TeraSort和WordCount应用运行程序10次，实验统计完成时间如图1所示。

从实验结果可知，基于动态反馈的公平调度算法平均任务完成时间最少，当集群中计算节点出现过载的情况时，备份任务或出错任务都会被重新执行，增加了集群资源的利用进而减少了作业完成时间。

图1  三种不同算法响应时间对比

3.3 失败任务测试

图2  三种不同算法在不同负载情况下的任务失败率

定义失败任务为fail，超时任务数量为TimeoutNum，失败任务数量为ErrorNum，集群中任务总数为SumNum，超时任务影响因子为λ1，失败任务的影响因子为λ2，这里λ1、λ2的取值分别为0.5、1.0。则任务失败率Fail（λ）可以表示为公式⑶。

Fail（λ）=  ⑶

失败任务测试结果如图2所示，实验结果表明，节点负载率小于30%时，三种算法任务失败率接近。当节点负载超过30%时，基于动态反馈的公平调度算法在高负载的情况下自动调节计算节点上计算槽的数目，保障了计算槽上的任务有资源可用，任务失败率明显低于其他两种算法。

4 结束语

针对公平调度算法的不足，提出了一种动态反馈的改进调度算法。但基于动态反馈策略的评价函数是不固定的，不同用户的不同任务有不同的评价标准。不恰当的评价函数可能导致集群资源利用不充分，对于如何根据任务及集群资源选择恰当的评价函数是后续需要解决的问题。

参考文献：

[1] 张青.网格环境下任务调度算法的应用研究[D].大连海事大学，2009.

[2] 陈全，邓倩妮.异构环境下自适应的Map-Reduce调度[J].计算机工

程与科学，2009.31（z1）：5

[3] 王凯，吴泉源，杨树强.一种多用户MapReduce集群的作业调度算法

的设计与实现[J].计算机与现代化，2010.10.

[4] Bryant R E. Data-Intensive Supercomputing： the Case forDISC[R].

CMU Technical Report CMU-CS-07-128，Depart-ment of Computer Science， Carnegie Mellon University，2007.

[5] CHERKASOVA L. Performance modeling in mapreduce environ-

ments [C]// Proceeding of the second joint WOSP/SIPEW international conference on Performance engineering： March 14-16， 2011. Karlsruhe， Germany. NY， USA： ACM press，2011：5-6

[6] 周锋，李旭伟.一种改进的MapReduce并行编程模型[J].科协论坛（下

半月），2009.2.

[7] 李鑫，张鹏.Hadoop集群公平调度算法的改进与实现[J].计算机工程

应用技术，2012.8.