Hadoop负载树任务调度算法

朱洁 顾烨君 柳飞 李思成 刘瑞

摘要：针对现有异构任务调度算法存在负载不均衡、数据本地性问题，提出基于树结构的负载树任务调度算法。该算法通过量化节点计算能力构造节点集最小堆，利用堆排序生成计算能力逆序树，并依据节点负载率将逆序树调整为左节点优先的负载树，为任务计算包含完成时间、负载率、延迟因子的决策值，最终完成任务与树节点的匹配。实验结果表明，取不同负载率与延迟权值比时，该算法的任务执行效率均能获得一定程度提高。该算法可利用树结构的调度优势，在获得更高集群负载均衡度时，有效缩短作业集执行时间。

关键词：Hadoop;负载树;任务调度;负载均衡;数据本地性

Hadoop Load Tree Task Scheduling Algorithm

ZHU Jie1，2， GU Ye jun LIU Fei LI Si cheng LIU Rui 1

（1.School of Information Engineering， Nanjing Xiaozhuang University;

2.Key Laboratory of Trusted Cloud Computing and Big Data Analysis， Nanjing 211171， China）

Abstract：Aiming at the problems of the load imbalance and data locality of existing heterogeneous tasks scheduling algorithm， an load tree task scheduling algorithm was proposed. Firstly， the computation capacities of nodes were calculated to build the minimum heap of the node set. The reverse tree was constructed after heap sort. Secondly， the reverse tree was adjusted to the left node preferential load tree through the load rate of nodes. Finally， the decision values of nodes consist of complete time factor， load rate factor and delay factor were calculated to match tasks and nodes. The experimental results showed that the tasks execution efficiency of the proposed algorithm was improved when different factor proportions of load rate and delay were defined. The proposed algorithm can utilize the scheduling advantage of the tree structure and reduce the job set execution time effectively while achieving the higher cluster load balance degree.

Key Words：Hadoop; load tree; task scheduling; load balance; data locality

0 引言

Hadoop分布式計算平台因其可靠、高效而广泛应用于大数据处理。MapReduce是其实现分布式处理的计算模型，其中任务调度算法为作业任务匹配计算资源，通过获得更短作业集执行时间提升平台计算性能。传统的先来先服务调度算法[1 2]、容量调度算法[3]与公平调度算法[4 5]及其改进主要应用于同构集群环境[6 7]。随着集群应用发展，节点间配置差异使同构前提不再成立，设计适应异构环境的调度算法成为必要。针对异构环境的推测式执行机制通过为进度落后任务启用备份任务以缩短任务执行时间，但其节点速度、任务进度恒定假设并不符合实际异构环境[8 9]。在此基础上，改进最长近似结束时间（Longest Approximate Time to End，LATE）算法[10]，定义备份任务数、慢节点与慢任务阈值，通过在出现资源空闲的快节点上启用备份任务，有效缩短了落后任务的执行时间。但仍存在问题：①Hadoop分布式文件系统使用冗余存储，任务数据不在本地时，移动数据的代价远高于移动计算;②应用领域扩展、用户需求多样、计算节点资源异构与链路带宽差异将导致集群负载不均衡，算法中并未涉及。

现有研究集中于对问题①的改进：文献[11]提出允许任务放弃调度机会，等待调度到距离数据最近节点的延迟调度算法;文献[12]使用任务进度探测方式区分快慢节点以提高推测执行效率;文献[13]从总体性能考虑，通过网络与负载状况动态调整数据本地性;文献[14]引入排队论模型，利用单队列多资源池服务窗口设计提高调度效率;文献[15]采用预取任务输入数据的方式减少作业响应时间。不少改进采用了智能调度算法，寻求多样性搜索与集中性搜索平衡，虽然有效减少了任务执行时间，但容易陷入局部最优解，使任务聚集在最快的几个节点上，延长了快节点上任务的排队时间，使慢节点的资源得不到充分利用，降低了任务并行率，导致负载不均衡，影响了作业集执行时间。

针对问题②，需要在任务调度算法中充分考虑可能引起负载不均衡的因素，进而进行预处理与实时控制。已有云计算环境下动态负载均衡算法研究主要涉及任务完成时间、资源利用率、能源消耗、云系统性能等方面的改进。文献[16]通过计算触发条件中集群负载实现资源的弹性调度。文献[17]建立成本函数模型，引入动态调节因子，改进蚁群算法用于降低任务成本，实现资源负载均衡。文献[18]定义了任务完成时间成本的约束函数和负载均衡度函数，通过改进蚁群算法获得全局最优解。文献[19]采用禁忌搜索和贪心原则选择任务交换，从而在优化任务调度初始解执行时间的同时改善负载均衡性能。文献[20]通过虚拟机分组和任务选择算法减少任务的迁移次数，提高负载均衡指标。

本文针对以上问题，借鉴树结构调度优势，提出负载树算法（Load Tree Algorithm，LTA）。该算法通过基于计算能力的最小堆排序构建自平衡逆序树，利用完成时间、负载率、时延因子将逆序树调整为左节点优先的负载树，实现任务与节点匹配。算法优先考虑数据本地性，充分利用树索引优势实现任务并行度与资源利用率之间的平衡，使异构环境任务调度趋于合理。

1 负载树构造

异构集群中，不同计算能力会使同一任务在不同节点上的执行时间各有差异。首先，量化节点计算能力。设 n∈N为树节点数，定义节点集P={P i|i∈[0，n-1]}，节点计算能力集P cap={P cap（i）|i∈[0，n-1]}，节点资源集PR={（PRc i， PRm i）|i∈[0，n-1]}，節点速率集PS={PS i（j）|i∈[0，n-1]， j∈[1，n t]}，n t为节点P i上已完成的任务数。为支持多资源类型，资源集值定义了处理器资源值PRc i与内存资源值PRm i，根据式（1）计算节点速率初始值PS i（0），ω r为资源权值。

集群运行后，通过任务历史数据反馈更新节点速率，动态调整节点状态。定义节点任务执行时间集TT={TT i，j|i∈[0，n-1]， j∈[1，n t]}，节点P i当前速率PS i（n t）为已完成任务在单位时间内处理的任务数与资源量，通过式（2）计算。

每有任务完成，更新节点速率。节点计算能力通过式（3）计算，其中ω c为计算能力因子权值。

利用堆结构在构造优先级队列时的高效性，通过最小堆构造逆序树。首先，按序构造完全二叉树，并自底向顶逐步调整为符合定义1的最小堆。

定义1 P cap（i）≤P cap（2i+1）∧P cap（i）≤P cap（2i+2） （i∈[0，|（n-2）/2|]）

完全二叉树从最后一个非叶子节点 P |n/2|到根节点P 0，依次调用下滑调整算法比较本轮父节点与左右孩子节点的P cap值。逐步将P cap值最小的节点上浮为堆顶节点，得到初始最小堆。调用堆排序算法将初始最小堆调整为逆序树，其特征为：①下标i为奇数时，节点为左孩子，i为偶数时，节点为右孩子;②采用层次遍历，得到节点计算能力逆序值集;③具有n个节点的逆序树深度k=| log 2n|+1。堆排序过程在最坏情况下时间复杂度为O（n log 2n） 。

基于节点负载率动态调整逆序树，利用节点计算能力，实现资源调度平衡。定义节点负载率集为 L={L i|i∈[0，n-1]}。负载率计算涉及节点性能状态，进而影响任务分配，利用处理器与内存资源值完成计算。定义节点已用资源量集为PRa={（PRac i， PRam i）|i∈[0，n-1]}，负载率计算如式（4）所示。

负载率升高可能导致节点性能下降，还需进一步判别节点速率。若节点速率同时出现下降，则可判别节点性能下降。节点速率下降条件式为 PS i（n t）>PS i（n t+1） ，将式（2）代入其中，推导可得条件式（5）。

逆序树调整为负载树后，需要对树节点的负载均衡度进行判定。判定时，若将负载率相近但计算能力不同的节点视为同等均衡度，将会降低强节点的资源利用率。因此，判定还需考虑节点计算能力的影响。设节点均衡度集 DB={DB i|i∈[0，n-1]}，计算如式（6）所示。

节点均衡度集的标准差用于描述集群均衡度，计算如式（7）所示。

σ值正常范围在[0，1]内，值越小，集群均衡度越高。负载树算法侧重于比较均衡效果，通过条件式DB i>DB判别节点过载。

改善逆序树负载不均衡与弱节点资源利用率低的问题，可以通过在复制的逆序树中引入负载率因子构造动态负载树实现。负载树须符合定义2，同层节点中负载更轻的节点将成为左孩子。

定义2 L 2i+1≤L 2i+2 （i=0，1，…，|（n-2）/2|）

节点上每有任务分配或完成，若其父节点不符合定义2，则交换同层节点。定义节点P i上任务预计完成时间集为TF={TF i，j|i∈[0，n-1]， j∈[1，n p]}，n p为节点并行任务数阈值。根据式（8）计算根节点与左孩子节点的决策值D i，以优先选择计算能力更强、完成时间更短、负载更轻、延迟更短的节点。其中，w d为决策值因子权值。TF i，j的计算如式（9）所示。

其中，PP={PP i，j|i∈[0，n-1]， j∈[1，n p]}为任务已完成的进度比例集;任务进度比例采用传统任务调度算法规定;TA={TA i，j|i∈[0，n-1]， j∈[1，n p]}为任务已运行时间集;TP i，j为任务优先级，优先级越高，决策值越小，越早获得执行。

2 基于负载树的任务调度算法

负载树算法构造可动态调整的集群节点负载树，通过比较左节点决策值为任务选择执行节点，算法流程如图1所示。

算法适应负载率变化，支持拓扑改变、节点性能变化等情况。通过式（5）判别出有节点性能下降时，为保持逆序树相对稳定，将该节点标记为不参与调度。若此节点为左节点，则判断同层右节点是否过载，若过载，则仅标记;若不过载，则交换两节点。若此节点为右节点，则仅标记。该节点上每有任务完成，即判别性能是否恢复，若恢复，则撤销标记，节点重新参与调度。当拓扑变化或节点计算能力变化时，须调整逆序树，进行负载树再构造。对于集群拓扑异构与可扩展支持，增强了负载树算法的适应性。

3 实验结果与分析

建立集群，测试负载树算法效果。选取6台计算机构建异构环境，其中3台配置处理器四核3.0GHz、内存8GB，3台减配为处理器双核2.4GHz、内存2GB，在CentOS上部署Hadoop。4个节点连接同一交换机，通过路由器连接其余2个节点，并通过修改链路带宽值模拟为远程节点。作业集由不同资源需求量、数据量的典型作业WordCount、TeraSort、Grep组合构成。作业数100，3种作业各占约1/3，且每种作业数据量由少到多比例为3∶4∶3，作业以随机顺序提交。通过实验获取负载树算法在异构集群中采用不同负载率与时延权值时的作业集执行时间，并与LATE算法进行对比。

算法固定完成时间因子权值，调整负载率与时延权值比例。实验1-3中负载率与延迟权值依次为（0.35，0.35）、（0.5，0.2）、（0.2，0.5）。实验4中负载率与延迟权值为（0.4，0.3）时，作业集执行时间最短。作业集执行时间对比如图2所示。

实验结果中，当负载与延迟权值相当时，调度效果较好。其中，实验1、实验4中负载树算法比LATE算法的作业集执行时间分别缩短了30.53%、33.1%。在延迟权值较小的实验2中，负载树算法比LATE算法的作业集执行时间缩短了17.88%，调度效果一般。在延迟权值较大的实验3中，负载树算法使作业集执行时间缩短了23.59%。因此，负载率与延迟因子均需有所考虑，且比例应相当。图3给出了实验1-4的均衡度标准差，其中实验2的负载均衡效果最为明显。

实验分析：

（1）任务完成时间受节点性能参数影响，完成时间因子可使任务优先选择计算能力强的节点，缩短任务执行时间。通过前期实验发现，该因子权值大时，任务将集中于高性能节点，加重了强节点负载，使弱节点空闲;反之，任务将被均匀分配，虽然优先分配到负载轻、具有本地数据的节点，但任务执行时间仍相对较长。传统算法使任务趋向于在强节点执行，而少考虑负载的影响。因此，实验设计固定完成时间因子权值，弱化节点性能对任务执行效率的影响，主要分析负载均衡策略与数据本地性的调度效果。

（2）实验结果表明集群均衡度与负载率因子权值关系密切，均衡度标准差与负载率权值正相关，与算法设计相符。

（3）集群中不具有本地数据的节点需要耗费较多网络延迟获取数据备份。延迟因子的使用在于为任务找到更快获得数据备份的节点。从实验结果看，延迟因子权值小时，任务被分配到远程节点的几率增加，增加的延迟影响了任务执行时间;延迟因子权值大时，任务很少被分配到遠程节点，从而使任务集中于高带宽链路节点，增加了该节点的负载，使远程节点利用率降低，影响并行度，使均衡度下降;在负载与延迟比例相当时，作业集获得了较好的执行时间。

因此，在固定完成时间因子前提下，集群执行效果的主导为负载率因子。延迟因子作为补充，在权值比例合适时，能较好地与负载率因子协同，获得更好的调度效果。

4 结语

本文分析了现有异构任务调度算法存在负载不均衡、数据本地性问题，研究已有动态负载均衡算法性能改进方法，对在任务调度中引入负载均衡策略进行探讨，提出了借助树结构提高任务调度效率的负载树算法。首先量化节点计算能力，并据此构造节点集最小堆，堆排序后形成计算能力逆序树。通过节点资源使用情况计算负载率，将逆序树调整为负载树，并据此定义节点性能判别式与节点集均衡度标准差。通过任务完成时间、负载率、延迟因子计算决策值后，为任务确定执行节点。算法中树结构具有自平衡能力，逆序树可根据拓扑及节点计算能力变化动态调整，负载树也可根据节点负载率变化及时调整。通过实验选取不同负载率与延迟权值的作业集执行时间进行比较，并与LATE算法执行结果对比。实验结果表明，负载树算法能有效缩短作业集执行时间，在取得适合的因子权值比时，可进一步提升调度效率并使集群拥有较好的负载均衡度。

负载树算法在并行效率与负载均衡间提供了协同调度途径，但算法主要侧重在节点选择上，进一步研究工作是融入任务端优化策略，使节点与任务选择共同作用于调度算法，并研究权值比例的自动取值实现。

参考文献：

[1] WIKIPEDIA. Apache hadoop [EB/OL]. http：//en.wikipedia.org/wiki/Apache_Hadoop.

[2] ZAHARIA M. Job scheduling with the fair and capacity schedulers [EB/OL]. http：//www.cs.berkeley.edu/～matei/talks/2009/hadoop_summit_fair_scheduler.pdf.

[3] THE APACHE SOFTWARE FOUNDATION. Capacity scheduler guide [EB/OL]. http：//hadoop.apache.org/docs/r1.2.1/capacity_scheduler.html.

[4] ZAHARIA M， BORTHAKUR D， SARMA J S， et al. Job scheduling for multi-user MapReduce clusters[R]. Berkeley： EECS Department， University of California， 2009：1 16.

[5] THE APACHE SOFTWARE FOUNDATION. Fair scheduler guide [EB/OL]. http：//hadoop.apache.org/docs/r1.2.1/fair_scheduler.html.

[6] 范杰，彭舰，黎红友.基于蚁群算法的云计算需求弹性算法[J].计算机应用，2011，31（1）：1 7.

[7] 杨镜，吴磊，武德安，等.云平台下动态任务调度人工免疫算法[J].计算机应用，2014，34（2）：351 356.

[8] FISCHER M， SU X， YIN Y. Assigning tasks for efficiency in Hadoop： extended abstract[C]. Proceedings of the 22nd ACM Symposium on Parallelism in Algorithms and Architectures， 2010：30 39.

[9] GE Y， WEI G. GA based task scheduler for the cloud computing systems[C]. Proceedings of 2010 International Conference on Web Information Systems and Mining， 2010：181 186.

[10] ZAHARIA M， KONWINSKI A， JOSEPH A D， et al. Improving MapReduce performance in heterogeneous environments[C].Proceedings of the 8th USENIX Symposium on Operating Systems Design Implementation，2008：29 42.

[11] ZAHARIA M， BORTHAKUR D， SARMA J S， et al. Delay scheduling： a simple technique for achieving locality and fairness in cluster scheduling[C]. Proceedings of the 5th European Conference on Computer Systems，2010：265 278.

[12] 刘奎，刘向东，马宝来，等.基于数据局部性的推测式Hadoop任务调度算法研究[J].计算机应用研究，2014，31（1）：182 187.

[13] THAWARI V W， BABAR S D， DHAWAS N A， et al. An efficient data locality driven task scheduling algorithm for cloud computing[J]. International Journal In Multidisciplinary and Academic Research， 2012，1（3）：151 158.

[14] 馬莉，唐善成，王静，等.云计算环境下的动态反馈作业调度算法[J].西安交通大学学报，2014，48（7）：77 82.

[15] XIE J， MENG F， WANG H， et al. Research on scheduling scheme for Hadoop clusters[C]. Proceedings of the Procedia Computer Science， 2013：49 52.

[16] 戴炳荣，李超，旷志光，等.基于多策略的私有云资源弹性调度方法[J].计算机应用，2017，37（S1）：34 38.

[17] 张继荣，陈琛.基于负载均衡的云计算资源分配算法[J].微电子学与计算机，2017，34（9）：43 47.

[18] 葛君伟，郭强，方义秋.一种基于改进蚁群算法的多目标优化云计算任务调度策略[J].微电子学与计算机，2017，34（11）：63 67.

[19] 孙凌宇，冷明，朱平，等.云计算环境下基于禁忌搜索的负载均衡任务调度优化算法[J].小型微型计算机系统，2015，36（9）：1948 1952.

[20] 刘亚秋，孙新越，景维鹏.一种异构云环境下的负载均衡算法[J].计算机应用研究，2018（12）：1 2.