异构环境下改进的LATE调度算法

王少娟

摘要：针对异构环境下LATE算法在选择备份任务及执行节点时的不足，提出一个改进的IR-LATE调度算法。算法通过计算为剩余完成时间最长、最需要备份的慢任务启动备份，并将其按负载不同进行分类，结合轮询算法，将备份任务分配到负载最小且成功/负载比高的节点上执行。实验结果表明，该算法与LATE算法比较，有效的将作业完成时间缩短了30%左右，提高了执行效率，进而促进系统的负载均衡。

关键词：异构环境；LATE；调度算法；慢任务；负载均衡

中图分类号：TP301.6文献标识码：A

Abstract：Analyzing the existing scheduler in the heterogeneous environment， and considering the lack of LATE scheduling algorithm in allocating TaskTracker to execute backup tasks， this paper put forward an improved IRLATE scheduling algorithm. The slow tasks with the longest time remaining and the most needing the backup were found out by calculating. They were classified according to the different load. Then the backup tasks were assigned to the TaskTracker with a minimum workload and high success/workload ratio combined with RoundRobin algorithm. The experimental results show that， compared with LATE algorithm， the algorithm is effective in shortening the operation execution time by 30% and improving the execution efficiency， thus contributing to the loadbalancing system.

Key words：heterogeneous environment； LATE； scheduling algorithm； slow task； load balancing

1引言

互联网的迅猛崛起给人们带来了丰富的网络生活，随之也加剧了海量数据亟待处理和存储的需求，于是专家们将并行计算的思想迁移到集群计算上，云计算[1]应运而生。Hadoop[2]是一个云环境下开源的大数据处理平台，是MapReduce[3]调度方式和GFS[4]数据存储方式的开源实现，无疑成为大数据时代的宠儿。

由硬件配置迥异的节点组成的Hadoop集群，其中运行着多个Job，如何让调度器对资源进行合理分配，以期使得集群资源能被更有效的利用成为一个不可忽视的方面，而其中的关键点就是调度策略的合理设计。Hadoop自带的调度算法：FIFO算法、Fair算法[5]、Capacity算法[6]及金嘉晖等人提出的等待时间阈值的自适应模型[7]均是以同构系统为前提的，而未考虑其异构性。LATE[8]调度算法，由M Zaharia等人研究，针对异构环境下的慢任务探测提出一种通过估计任务剩余完成时间，选择快节点为最长剩余完成时间的任务启动备份的调度策略，虽然其计算效率有所提高，却不曾考虑任务及节点的负载类型。

本文在分析研究前人成果的基础上，对LATE调度算法在备份任务及执行节点的选择方面提出了改进。首先将提交的作业按负载类型进行分类，获取慢任务中剩余时间最长的slowTask并为其启动备份，然后在选择执行备份任务的快节点时，根据负载类型，结合轮询算法，选择存在空闲槽且成功/负载比高的最快节点，以期达到缩短作业完成时间，提高资源利用率，优化集群负载。

2相关工作分类及定义

2.1作业负载分类

按照文献[9]的负载分类机制，将任务负载分为CPU_bound和I/O_bound两类。在Hadoop环境中运行的作业，只有全部的Map任务结束才会执行Reduce任务，因此本文仅考虑Map任务。Map任务执行可分解为3步操作：

（1）初始化输入数据；

（2）计算Map任务；

（3）将输出结果存储到本地磁盘。

任务负载分类所用到的符号定义见表1。

3.2算法描述

每个节点将自身的CCPU，Cmem，Cdisk，Cnw信息、任务成功率和节点的负载信息通过Heartbeat发送给JobTracker，JobTracker在接收到这些信息后重新计算workload值，并更新BurdenforCPUList和BurdenforIOList两个链表。利用上述信息计算并选择当前执行任务中剩余时间最长的slowTask，并记录下该任务所在节点的成功/负载比；选择执行备份任务的TaskTracker时，根据任务负载类型的不同，CPU_bound遍历BurdenforCPUList，IO_bound遍历BurdenforIOList，结合轮询算法选择存在空闲槽点且其workload值小于落后节点负载值的高成功/负载比的节点执行，加快任务的完成。IR-LATE算法流程图如图1所示。

IRLATE算法执行过程如下：

1）用户提交作业到JobTracker。

2）JobTracker根据公式判断作业的负载类型。

3）记录节点信息，计算慢任务的剩余完成时间，选取最长剩余时间的slowTask并为其启动备份任务。

4）选择执行备份任务的TaskTracker时，结合轮询算法，根据任务类型，若其为CPU_bound，则遍历BurdenforCPUList，若为IO_bound则遍历BurdenforIOList，选择存在空闲槽且成功/负载比最高的最快节点执行。

4实验结果及性能分析

4.1实验环境

实验集群由5台PC机，通过虚拟机的方式构建测试环境。4台PC机上安装不同数量的虚拟机来模拟异构环境，每个虚拟机分配600M内存、6GB硬盘，使用VirtualBox4.3.20，安装Ubuntu14.04.02，JDK版本为1.8.0_40，Hadoop版本为2.6.0。配置见表2。

4.2实验仿真及结果分析

本文选用Hadoop自带的性能测试集：TeraSort和GrepCount为测试数据，在Hadoop平台下进行仿真实验。文献[9]已论证TeraSort为I/O_bound作业，GrepCount为CPU_bound作业。实验中设定参数值：SpeculativeCap为20%，SlowTaskThreshold为25%，SlowNodeThreshold为25%，其已在文献[12]中论证的最佳。2个测试集分别用LATE算法和IR-LATE算法执行，实验将每个作业执行10次取其平均完成时间来保证数据的有效性。通过比较作业完成时间及备份任务完成时间来体现改进算法的优势。

实验结果如图2所示，输入5GB数据，IR-LATE调度算法执行时间比LATE调度算法执行的时间少30%左右。

图3和图4描述了TeraSort、GrepCount作业输入数据分别为1GB、3GB、5GB时，用3台服务器分别执行LATE算法和改进的LATE算法时工作完成时间的对比图。由图3和图4可以得知，当输入数据量较小，集群较小时两种算法完成时间相差无几。图3TeraSort（3台服务器）完成时间

由图5和图6可知，当输入数据量增大，集群规模变大时，IRLATE调度算法的优势就表现出来了。因为数据量剧增导致集群负载加剧，与此同时slowTask出现的概率也会加大。而LATE算法对剩余完成时间估算不够准确，会导致为不必要的慢任务启动备份，反而延迟了作业完成时间，耽误整体进度。IRLATE算法能准确估算剩余时间，并为剩余时间最长的slowTask启动备份，将其调度到负载低且成功/负载比高的节点上执行。这样不仅节约了系统资源，而且能使真正的slowTask尽快完成，有效缩短工作完成时间。

5结束语

文章针对LATE算法在为慢任务启动备份及选择执行节点时的不足，提出了改进的IR-LATE算法。该算法通过准确计算任务的剩余完成时间找出剩余时间最长的slowTask并为其启动备份，根据任务负载及节点负载的不同分类，为备份任务选择负载低、成功率高的节点执行。实验结果表明，IR-LATE算法相比LATE算法，不仅缩短了任务的完成时间，而且在数据量增大，集群规模增大时有更好的执行效率。但本文算法只考虑了同机架集群问题，今后将扩展文中算法，进一步研究跨机架的调度算法。

参考文献

[1]VAQUERO L M， RODEROMERINO L，CACERES J， etal.A breakin the clouds：towards a cloud definition[J].ACM SIGCOMMComputer Communication Review，2009，39（1）：50-55.

[2]Hadoop [EB/OL]. http：//hadoop.apache.org/.

[3]DEAN J，GHEMAWAT S.MapReduce：simplified data processingon large cluster[C]//Proc of the 6th Symposium on OperatingSystems Design and Implementation.San Francisco：GoogleInc，2004.

[4]GHEMAWAT S，GOGIOFF H，LEUNG P T.The google file system[C]//Proc of the 19th ACM Symp on Operating SystemsPrinciples，2003：29-43.

[5]Fair_scheduler [EB/OL]. http：//hadoop.apache.org/common/docs/stable/fair_scheduler.html.

[6]Capacity_scheduler[EB/OL].http：//hadoop.apache.org/common/docs/current/hadoopyarn/h aadoopyarnsite/CapacityScheduler.html.

[7]金嘉晖，罗军舟.基于数据中心负载分析的自适应延迟调度算法[J].通信学报，2011，32（7）：47-56.

[8]ZAHARIA M，KONWINSKI A， JOSEPH A D， et al. Improving MapReduce Performance in Heterogeneous Environments.[J]. Osdi， 2008：29-42.

[9]CHAO T，ZHOU H，HE Y， et al. A dynamic MapReduce scheduler for heterogeneous workloads[C]// Proc of the 8th International Conference on Grid and Cooperative Computing， China， 2009：218-224.

[10]胡丹， 于炯， 英昌甜，等. Hadoop平台下改进的LATE调度算法[J]. 计算机工程与应用， 2014， （4）：86-89. DOI：10.3778/j.issn.1002-8331.1204-0040.

[11]赵晓冰， 王世卿. 异构环境下调度任务备份的改进算法[J]. 计算机应用与软件， 2013， （12）：105-107. DOI：10.3969/j.issn.1000-386x.2013.12.027.

[12]CHEN Quan，ZHANG Daqiang， et al. SAMR： A selfadaptive mapreducescheduling algorithm in heterogeneous environment[C]//Proc of IEEE International Conference on Computer and Information Technology. LosAlamitos： IEEE computer society，2010： 2736-2743.

[13]董西成.Hadoop技术内幕：深入解析MapReduce架构设计与实现原理[M].北京：机械工业出版社，2013.5.

[14]李春艳， 何一舟， 戴彬. Hadoop平台的多队列作业调度优化方法研究[J]. 计算机应用研究， 2014， 31（3）：705-707. DOI：10.3969/j.issn.1001-3695.2014.03.015.

[15]栾亚建， 黄翀民， 龚高晟，等. Hadoop平台的性能优化研究[J]. 计算机工程，2010，36（14）： 262-263. DOI：10.3969/j.issn.1000-3428.2010.14.095.