基于Hadoop平台的三队列作业调度算法

宁菲菲，郑均辉

基于Hadoop平台的三队列作业调度算法

宁菲菲，郑均辉

针对Hadoop平台的作业调度问题，提出支持作业优先级、作业类型区分和资源抢占的三队列作业调度算法（TJSA）。为更好地满足用户需求，通过设置作业优先级细化作业差别，并按照优先级的高低依次进入等待队列；进而对作业类型进行区分，设置CPU密集型作业队列和I/O密集型作业队列，以提高作业的并行执行效率；当队列资源不足时可以基于节点特征对资源进行回收，从而提高平台的整体性能和节点资源利用率。实验结果表明：TJSA算法在作业运行时间和集群运行稳定性上都表现出较好的性能。

Hadoop；作业调度；三队列；作业优先级；资源抢占

0 引言

Hadoop是Apache基金会开发的基于Google文件系统和 MapReduce分布式编程模型等核心技术的开源云计算平台[1-2]，方便用户在由大量廉价硬件设备组成的集群上运行应用程序、进行大规模的数据处理。Hadoop具有低成本、高效率、高可靠性和较强的可伸缩性等优点[3]。作为Hadoop领域的重点研究内容之一，作业调度技术主要负责管控作业的执行顺序和计算资源的分配。合适的作业调度算法能够在满足用户作业请求的同时，有效提升Hadoop平台的整体性能和系统资源利用率[4]。

Hadoop 中常见调度算法有先入先出（FIFO）算法、公平调度算法（Fair Scheduler）和计算能力调度算法（Capacity Scheduler）3种。Hadoop默认采用的是支持优先级的先入先出调度算法，算法简单易实现且开销小，但不利于短作业的执行、不支持共享集群和多用户管理。由Facebook提出的公平调度算法充分考虑了不同用户与作业的资源需求差异、支持用户公平共享集群资源，但作业资源的配置策略不够灵活容易造成资源浪费并且不支持作业抢占。雅虎提出的计算能力调度算法支持多用户共享多队列、计算能力灵活，但不支持作业抢占且易陷入局部最优。伴随Hadoop的不断发展和应用，一些新的作业调度算法被提出。文献[5]对延迟调度算法进行改进，提出延迟—容量调度算法，在解决数据本地化问题的同时提高了作业执行的并行度。文献[6]针对云计算集群中的资源异构和节点稳定性问题，利用统计方法提出一种资源调度算法，有效减少了作业的周转时间，集群的整体性能得到提升。文献[7]根据作业对CPU和I/O资源的使用情况进行作业类型的划分，提出了三队列调度算法。

1 Hadoop作业调度

1.1 Hadoop集群框架模型

Hadoop集群框架遵循主从结构，由1个JobTracker主节点和若干个TaskTracker从节点组成。JobTracker主节点负责作业调度、作业划分、监听作业和任务运行情况等。TaskTracker从节点主要负责执行任务并报告资源占用情况与任务完成情况。TaskTracker通过心跳包向 JobTracker请求任务，在任务执行过程中通过向JobTracker发送心跳信息，将任务的执行情况和节点当前的运行状态发送给JobTracker。

1.2 Hadoop作业执行流程

来自客户端（JobClient）的作业提交给集群主节点JobTracker。JobTracker通过执行作业调度从中选择一个作业作为待运行作业，并将被选中的作业划分为若干 Map任务与 Reduce任务[8]。从节点 TaskTracker通过心跳包向JobTracker发送任务请求，JobTracker通过心跳包将任务分配到发送请求的从节点 TaskTracker上去执行。每个TaskTracker都拥有一定数量的资源槽（slot）用来执行分配的任务。资源槽分为 Map槽和 Reduce槽，分别用于执行Map任务和Reduce任务[9]。TaskTracker通过“心跳”程序向JobTracker告知资源槽的使用情况、任务的执行情况。作业完成后，JobTracker将结果返回JobClient。MapReduce工作框架如图1所示：

图1 MapReduce工作框架

2 三队列作业调度算法的设计

（1）作业优先级

Hadoop上用户数量庞大，为更好地满足不同用户的需求，提升服务满意度，通过设置作业优先级并进行量化，以便细化作业差别。选取作业紧急度、作业长度、等待因子和用户身份4项指标衡量作业优先级。

a）作业紧急度emergency：按照作业的实时性要求，可以分为批处理作业、生产性作业和交互式作业。其中，交互式作业实时性要求最高，需要立即完成，因此，具有较高的紧急度，emergency取值为5；生产性作业实时性要求一般，紧急度emergency取值为3；批处理作业的实时性要求最低，故紧急度也最低，emergency取值为1。

b）作业长度 length：根据作业所需执行时间的长度，将作业分为短作业与一般作业。短作业的length取值为1，一般作业的length取值为0。集群环境下作业执行时间的长短受作业启动时Map任务的并行度、从节点上任务的执行效率、数据本地性等众多因素的影响，计算方法较为复杂[10]。考虑到作业运行过程中所需的输入数据在作业启动前就已确定，并已按照固定的数据块大小进行分片，与此同时，文件分割器将作业划分为与数据块的个数相一致的任务。因此，为了简化对作业长度的判定，将JobTracker上分片数不超过阈值的作业判定为短作业，其余判定为一般作业。同等条件下，短作业的优先级高于一般作业，短作业将优先得到执行，集群资源的利用率和作业整体的执行效率将得到显著提升。

c）等待因子 time：在作业运行过程中，有些作业可能等待较长时间而一直未能得到执行，通过设置等待因子衡量作业的等待时间以有效防止此类情况的发生。

d）用户身份user：根据用户权限大小，将用户分为root用户、系统用户和普通用户3类。

上述 4项指标的取值和所占权值可以根据作业区分的具体需要由管理员设定。根据公式（1）计算作业优先级priority的取值，取值越大作业优先级越高。如公式（1）：

（2）作业类型划分

根据作业所需计算资源的不同对作业进行分类，以便为不同类型的作业分配合适的计算资源，从而提高资源使用效率。节点资源可以包括CPU资源和磁盘资源等。因此，可以将作业类型简单地划分成CPU密集型（PU-Bound）和I/O密集型（I/O-Bound）两类。文献[7]中给出了确定作业类型的方法，本文对该方法进行优化：满足公式（2）的作业为CPU 密集型，其他情况则为I/O密集型作业。如公式（2）：

其中，MID和MOD分别表示Map任务的输入数据量和输出数据量；RID表示Reduce任务的输入数据量；n表示从节点上当前运行的任务总数；MTCT为Map任务所需的完成时间；DIOR为磁盘I/O比率。

（3）作业队列

设立3个作业队列，分别为等待队列、CPU密集型作业队列和I/O密集型作业队列。本文在三队列作业调度中引入两级调度策略。当用户向集群主节点JobTracker提交新作业时，首先依据公式（1）计算其作业优先级，并按照优先级由高至低的顺序依次进入等待队列。接下来，作业调度器对位于等待队列队首位置的作业进行任务划分并从中选取一个 Map任务分配给每一个拥有空闲资源槽的从节点TaskTracker去执行。当这些Map任务执行完成后，运用公式（2）进行作业类型的判定，满足公式（2）则为CPU密集型作业，接下来将进入CPU密集型作业队列等待调度；否则为I/O密集型作业，进入I/O密集型作业队列。

（4）基于节点特征的资源回收抢占机制

节点在执行CPU密集型任务和I/O密集型任务时所表现出来的性能是有差异的。节点执行不同类型任务的历史平均时间可以代表该节点执行不同类型作业的能力，将其称为节点特征，对作业调度具有重要的参考价值[9]。

为每个节点各分配数据量为2GB的CPU密集型任务和I/O密集型任务，通过读取日志中任务的加载、完成信息及节点分配信息，获取各任务的执行时间。计算得到各节点执行CPU密集型任务和I/O密集型任务的所需平均时间，分别记为Tcb和Tiob。集群执行CPU密集型任务和I/O密集型任务的平均时间分别记为 AVGcb和 AVGiob。节点特征Ntype的取值可依据公式(3)计算得到，Ntype取值为1表示节点在执行CPU密集型任务时性能更优，取值为0则表示节点执行I/O密集型任务时性能更优。如公式（3）：

节点特征可能会随着集群工作的进行发生变化，因此可每隔一定的周期重新计算。

为CPU密集型作业队列和I/O密集型作业队列各分配一定的资源配额，配额管理方法与计算能力调度算法相同，但在资源配额回收的管理中应用了基于节点特征的资源回收抢占机制。

分别对CPU密集型作业队列和I/O密集型作业队列当前所持有的资源数进行定期检查，当所持有的资源数低于其配额额度，并且该作业队列中等待执行的任务数大于正在回收的资源总数时，调度算法查看该作业队列的资源回收列表，如有超时的资源回收对象，则进行调度并通过回收线程对其进行回收；否则根据该队列中作业的作业类型创建具有相应节点特征的资源回收对象，并将其加入到该作业队列的资源回收列表中。对于CPU密集型作业队列，则应创建节点特征Ntype取值为1的资源回收对象，这是因为节点特征Ntype取值为1的节点在执行CPU密集型任务时性能更优，因此，该类型节点中的资源在被回收时，应加入到CPU密集型作业队列的资源回收列表；而节点特征Ntype取值为0的节点在执行I/O密集型任务时性能更优，因此，该类节点中的资源在被回收时，应加入到I/O密集型作业队列的资源回收列表。资源回收对象包含了回收超时信息和所需回收的资源总数（配额额度与当前持有资源数的差值）。

3 算法实现

基于Hadoop的3队列作业调度算法的流程如图2所示：

该调度算法主要包含计算作业优先级、确定作业类型和基于节点特征的资源回收抢占3个阶段。JobClient将作业提交至JobTracker主节点后，通过计算作业优先级，按优先级由高至低的顺序依次进入等待队列；然后对等待队列中的作业进行类型判定，分别进入CPU密集型作业队列和I/O密集型作业队列；检查各作业队列当前所持有的资源数，如果达到配额额度则将作业划分为若干个Map任务和Reduce任务并将任务分配至具有相应节点特征的TaskTracker节点去执行，若未达到配额额度则先进行资源回收，再执行作业划分和任务分配。

4 实验与分析

为测试本文提出的作业调度算法对不同作业类型的区分调度性能，采用Hadoop Hive项目提供的基准测试程序，选择先入先出（FIFO）调度算法与本文算法TJSA作对比实验，测试输入数据选用各 10GB的 CPU密集型作业WordCount和I/O 密集型作业TeraGen。

实验的硬件设置如下：选取6台PC机，采用Red Hat Enterprise Linux 5.2操作系统和Hadoop 0.21.0版本集群管理软件搭建Hadoop集群。其中1 台机器作为JobTracker主节点，硬件配置为双核2.4GHz，内存16GB，硬盘4×250GB；其余5台作为TaskTracker从节点，硬件配置为双核2.4GHz，内存4GB，硬盘4×80GB。Hadoop默认为每个TaskTracker从节点配置2个资源槽。

在作业数量固定且作业提交顺序随机的前提下，每隔30s提交一轮测试，各进行10轮测试，对FIFO算法与TJSA算法的调度性能进行对比分析。

4.1 短作业高占比时的算法性能对比

在测试所选用作业中，短作业占90%，一般作业占10%。短作业的数据量在 64MB以内，一般作业的数据量为64MB～2GB。FIFO算法与TJSA算法在进行作业调度时的性能变化曲线如图3所示：

图3 短作业高占比时的作业执行时间对比

从图3中可以看出，在短作业占比较高时，就总体调度运行时间而言，TJSA算法比FIFO算法缩短10%左右，TJSA算法使得集群的执行时间更为稳定。

4.2 一般作业高占比时的算法性能对比

在测试所选用作业中，短作业占20%，一般作业占80%，短作业和一般作业的数据量大小与 4.1节所述保持一致。FIFO算法与TJSA算法在进行作业调度时的性能变化曲线如图4所示：

图4 一般作业高占比时的作业执行时间对比

从图4中可以看出，在一般作业占比较高时，就总体调度运行时间而言，TJSA算法比FIFO算法显著降低。这是由于TJSA算法对作业进行了优先级的设置，并通过将作业分散在CPU密集型队列和I/O密集型队列并行执行，有效提升了整体执行效率。

5 总结

本文在研究分析Hadoop现有作业调度算法的基础上，提出了一种三队列作业调度算法TJSA。TJSA通过对作业设置优先级以细化来自不同用户的不同作业的差别；根据作业类型的不同分设CPU密集型作业队列和I/O密集型作业队列，一方面提升了作业的并行执行效率；另一方面可以依据作业类型和节点特征，更为合理地进行节点资源的分配；依据节点特征对资源进行回收抢占，有效提升Hadoop平台的资源利用率。通过在自组搭建的Hadoop平台上进行实验测试和性能分析，本文所提出的TJSA算法在作业运行时间和集群稳定性上都表现出较好的性能。本文进一步的工作是对作业优先级的量化进行优化，同时考虑支持队列间的优先级设置。

[1] Cloud computing[EB/OL]. http://en.wikip-edia.org/wiki/ Cloud_computing, 2013-03-10.

[2] DEAN J, GHEMAWAT S. MapReduce: a Flexible Data Processing Tool[J]. Communications of the ACM, 2010,53(1):72-77.

[3] 邓自立.云计算中的网络拓扑设计和 Hadoop平台研究[D].合肥:中国科学技术大学,2009.

[4] 李千目,张晟骁,陆路等.一种Hadoop平台下的调度算法及混合调度策略[J].计算机研究与发展,2013,50:361-368.

[5] 柯何杨,杨群,王立松等.同构Hadoop集群环境下改进的延迟调度算法[J].计算机应用研究,2013,30(5):1397-1401.

[6] 邓传华,范通让,高峰.Hadoop下基于统计最优的资源调度算法[J].计算机应用研究,2013,30(2):417-419.

[7] TIAN Chao, ZHOU Hao-jie, HE Yong-qiang, et al. A dynamic MapReduce Scheduler for Heterogeneous Workloads[C]// Proc of the 8th International Conference on Grid and Cooperative Computing, 2009:218-224.

[8] 曹洁,曾国荪,钮俊等.云环境下可用性感知的并行任务调度方法[J].计算机研究与发展,2013,50(7):1563-1572.

[9] 郑晓薇,项明,张大为等.基于节点能力的Hadoop集群任务自适应调度方法[J].计算机研究与发展,2014,51(3):618-626.

[10] 朱洁,赵红,李雯睿.基于Hadoop的三队列作业调度算法[J].计算机应用,2014,34(11):3227-3230,3240.

TP393 文献标志码：A

2015.04.01）

1007-757X(2015)08-0019-03

河南省教育厅科学技术研究重点项目（14B520039）；平顶山学院青年基金研究项目（PDSU-QNJJ-2013009）

宁菲菲（1985-），女，汉族，平顶山人，平顶山学院软件学院，助教，硕士，研究方向：无线传感器网络与云计算,平顶山，467002郑均辉（1981-），男，汉族，四川叙永县人，平顶山学院，讲师，硕士，研究方向：算法分析，GPS数据处理等，平顶山，467002