一种基于动态slot分配的公平调度算法

苏涛涛，郑 禄

(1. 中南民族大学计算机科学学院，湖北 武汉 430074; 2. 中南民族大学实验教学与实验室管理中心，湖北 武汉 430074)

一种基于动态slot分配的公平调度算法

苏涛涛1，郑 禄2

(1. 中南民族大学计算机科学学院，湖北 武汉 430074; 2. 中南民族大学实验教学与实验室管理中心，湖北 武汉 430074)

Hadoop框架中基于缺额的公平调度算法以统一的固定配置设置定时计算和更新作业信息，在一定程度上影响了其作业调度的公平性，同时也不能满足作业的资源需求。针对基于缺额的公平调度算法配置方式的不足,提出一种基于公平性的动态slot分配算法，通过实时计算更新缺额进行slot分配以确保真正的公平性。

公平调度；缺额；公平性；slot分配

0 引言

作业调度算法是Hadoop集群中的核心算法，作业调度算法的改进可以大大提高整个集群中资源的利用率[1]。Hadoop自带的有几个简单的作业调度算法。同时，为了满足各种不同类型或不同目的的复杂作业的调度，Hadoop基为一个开源框架的设计思想以插件式的形式集成了新的作业调度算法[2-3]。公平调度算法是一种赋予作业资源的方法，其目的是让所有的作业随着时间的推移，都能平均的获取等同的集群中的共享资源[4]。但基于缺额的公平调度算法中以统一的配置方式设置定时计算和更新时间，并不能保证缺额的实时性，进而会影响到资源分配时的公平性。针对该算法配置方式的不足,提出一种基于动态slot分配的公平调度算法，通过实时计算更新缺额进行slot分配以确保真正的公平性。

1 公平调度

1.1 基本概念

基本概念定义如表1所示：

表1 变量定义Tab.1 Variable Definition

1.2 基于缺额的公平调度算法

公平调度器（Fair Scheduler）是由Facebook开发，是一种适合于多用户共享集群环境的调度器，其吞吐率高于先进先出调度器（FIFO）[5]。公平调度器的基本思想是随着时间推移平均分配工作，这样每个作业都能平均地分配到资源（Hadoop集群中资源以Slot为单位进行组织）。公平调度器是按资源池（pool）来组织作业，并把资源公平的分配到这些资源池里。在每一个资源池内，同样也会使用公平策略给资源池中的作业分配slot。当然，用户也可以给资源池或者资源池中的作业设置相应的权重，以不按比例的方式共享集群中的资源。

Hadoop-0.20.2版本的公平调度器，采用了基于缺额调度算法[6-8]，其核心算法是当出现空闲Slot时，公平调度器会将此Slot分配给缺额最大的作业（系统默认情况下会每隔500毫秒更新一次Job信息，包括：作业缺额等信息）。核心算法的主要思想是：将作业的优先级转化成权重，优先级越高权重越大，而权重越大，获得的资源越多，通过权重计算出的资源就是“公平共享量”，当然，这是理想状态下，每个作业应得到的资源，而在实际情况下，由于种种原因而获取不到这些资源，因而产生一个差值，为了使这个差值更能体现实际意义，又将时间融合进去，即差值与时间的乘积，这就是缺额（缺额是累加的，如果一个作业为获得资源，其缺额会随着时间不断增大，直到能够排到队列首位为止），计算公式如下：

每次出现空闲Slot时，优先选择缺额大的作业，以便达到公平调度的目的。

1.3 该算法的不足之处

Hadoop是一种m/s模式框架，主节点上运行Job-Tracker，主要用来监控整个集群中作业的运行情况并对资源进行管理和调度；从节点上运行Task-Tracker，主要负责监控任务执行和报告进度等。TaskTracker通过心跳会定期汇报信息给Job-Tracker，包括内存使用量，内存剩余量，正在运行的task，资源情况等。主节点中的调度即发生在心跳到达时，若TaskTracker汇报自己有空闲资源，则JobTracker使用调度算法选择一个任务发射到该节点运行。调度的实质是slot的分配，而作业调度的触发条件是每次心跳信息中有空闲slot。

基于缺额的公平调度器在Yahoo等大公司内部均被采用，但在使用过程中，会存在一些问题表现为：由于基于缺额的公平调度过程中更新缺额是按照固定配置设置的时间△T进行更新，并不能保证当产生新的空闲Slot的时得到的Job就是当前缺额最大的Job，其次，由于作业调度过程中在task处理完成之后才会释放该task所占用的资源，在处理的作业都是大作业的情况下，数据分块后分配给每个task进行处理，则会出现作业占用资源的时间较久的情况，在每次汇报心跳信息时空闲资源出现的频率会降低，从而导致调度频率会降低，这种情况下定时更新Job信息的频率并没有改变，从另外一个角度，Job处理时间较久，定时更新Job信息的次数就会增加，反而会增大所占用的系统资源比例。

定义Jobs为作业队列中所有作业的集合，Jobs={job1,job2,job3,…}，假设集群是由一个master节点和若干个slave节点组成，定义JobTracker为该master节点，slave节点定义为TaskTrackers={T1,T2, T3,…}。其大致算法过程如表2：

表2 基于缺额的公平调度算法Tab.2 The Fair Scheduling Algorithm Based On The Deficiency

上述算法中的步骤3和3均是在其他线程中定期执行。设时间点T1，T2，且T2 - T1=△T，根据固定配置则会在T1时间点计算出当前缺额最大的作业记为Job1，在T2时间点计算出当前缺额最大的作业记为Job2，TaskTracker汇报信息中有空闲slot的时间点在T1和T2之间记为时间点T3，按照上述算法则会将产生的空闲slot分配给Job1，而这一过程并不符合公平调度中“公平性”的原则。图形描述如图1所示：

图1 基于缺额的公平调度算法图形描述Fig.1 the graph description of The Fair Scheduling Algorithm Based On The Deficiency

针对上述出现的情况，可以取消固定配置中的定时更新缺额，在当TaskTracker汇报自己有空闲slot时去计算每个剩余Job的缺额，从而将该slot分配给缺额最大的Job。图形描述如图2所示：

图2 基于动态slot分配的调度算法图形描述Fig.2 the graph description of The Fair Scheduling Algorithm Based On Dynamic Slot Allocation

2 基于动态slot分配的公平调度算法

图1可以看出，当产生出新的空闲Slot时得到的缺额最大的Job只是上一个计算更新的时间节点的结果（即：Job1），并不是当前时间节点的结果，因此难以真正意义上的保证作业分配资源的公平性。

在调度过程中，为了弥补基于缺额调度算法中出现的作业公平性的不足，提出一种改进算法——基于动态slot分配的公平调度算法，该算法丢弃掉算法原有的固定配置，在当有空闲slot产生时才进行计算更新，计算公式保持不变。改进后的算法如表3：

表3 基于动态slot分配的公平调度算法Tab.3 The Fair Scheduling Algorithm Based On Dynamic Slot Allocation

基于缺额的公平调度算法是通过为上个时间周期内没有受到公平分配资源的Job，分配资源来实现作业间的公平性，这种公平性往往显得滞后。同时，在处理的作业都是大作业的情况下，作业分块后分配给task的则会造成空闲slot产生的频率会降低，这种情况下定时更新操作就会显得较为频繁，其占用系统资源的比例也会有所显现。而基于动态slot分配的公平调度算法是在有新的空闲slot产生的情况下才进行Job信息的更新，首先保证了作业的公平性，其次，去除固定配置在需要的情况下才去计算更新Job的信息，在处理大作业的过程中也释放了定时计算更新所需要的资源，减少计算更新Job信息的次数，在一定程度上提高了对大作业处理效率。

3 实验结果对比及分析

为了验证针对基于缺额的作业调度算法假设，并且为了使实验结果更能明显，实验时将固定配置的参数放大一定的倍数，设计若干个小作业（对10个1M文件进行字数统计，记对每10个文件的统计为1个Job）。在产生空闲slot时使用基于缺额的作业调度算法算法所处理的Job与当前时间节点计算缺额最大的Job不同的个数（误差Job的个数）如表4所示：

表4 误差Job个数Tab.4 the number of error Jobs

从上表的实验结果中可以得知，当有空闲slot产生时基于缺额公平调度算法计算出来缺额最大的作业与当前时间点计算缺额最大的作业是不一致的，这也就说明，基于缺额的作业调度算法有失公平性的准则。

本组实验的目的是比较在处理大作业的情况下基于缺额的调度算法和基于动态slot分配的调度算法的运行效率，设计若干个大作业（对10个20M文件进行字数统计，记对每10个文件的统计为1个Job），处理相同作业量大作业的情况下，系统运用两种算法完成所有作业所消耗的总体时间对比如图3所示：

图3 实验结果Fig.3 the experimental result

图4为两种公平调度算法在处理相同作业数量（10个Job）大作业的过程中，进行计算更新剩余待执行Job信息次数的对比结果，两种算法各执行10次：

图4 实验结果Fig.4 the experimental result

由上图可知在处理大作业的情况下空闲slot产生的频率降低，这种情况下使用基于缺额公平调度的固定配置去定时计算更新Job信息时，计算更新的次数比动态slot分配算法的计算更新次数多。根据上述的结果,在处理大作业的情况下，将两种调度算法的性能进行对比，如表5所示。

分析总结：在实验对比结果中，通过比较可以发现，基于公平调度的动态slot分配算法虽然在效率上与基于缺额的公平调度算法相比比较接近，但在公平性上却有所提高，与提出改进的初衷是相符的，并且在处理大作业的情况下改进后的算法效率也在一定程度上高于基于缺额的公平调度算法。

表5 算法比较Tab.5 the algorithm comparison

4 结束语

本文针对Hadoop中基于缺额的公平调度算法所存在的问题和现象提出一种基于公平性的动态slot分配算法，后者在作业调度的过程中不影响算法效率的同时又在一定程度上保证了作业选择“公平性”的原则。

[1] 姜淼. Hadoop云平台下调度算法的研究[D]. 长春: 吉林大学, 2012. JIANG M. The Research of Scheduling Algorithm on Hadoop Cloud Platform[D]. ChangChun: Jilin University, 2012.

[2] Shanjiang Tang, Bu-Sung Lee, and Bingsheng He. DynamicMR: A Dynamic Slot Allocation Optimization Framework for MapReduce Clusters[J], IEEE Trans. Cloud Comput., 2014, pp. 333-347.

[3] 王峰. Hadoop集群作业的调度算法[J]. 程序员, 2009 (12): 119-121. WANG F. The Scheduling Algorithm in Hadoop Cluster Jobs[J]. PROGRAMMER, 2009(12): 119-121

[4] 张青. 网格环境下任务调度算法的应用研究[D]. 大连: 大连海事大学, 2009. ZHANG Q. The Research of Task Scheduling in The Grid Environment[D]. Dalian: Dalian Maritime University, 2009.

[5] Zaharia M, Borthakur D, Sarma J S, et al. Job scheduling for multi-user mapreduce clusters[R]. EECS Department, University of California, Berkeley, Tech. Rep. UCB/EECS-2009-55, 2009.

[6] Dong. Hadoop-0.20.2 Fair Scheduler Algorithm[OL]. [2011-3]. http: //dongxicheng. org/mapreduce/hadoop-fair-scheduler/

[7] Dong. Hadoop-0.21.0 Fair Scheduler Algorithm[OL]. [2011- 12]. http: //dongxicheng.org/mapreduce/hadoop-0-21-0-fair-scheduler/

[8] 董西成. Hadoop技术内幕: 深入解析MapReduce架构设计与实现原理[M]. 北京: 机械工业出版社, 2013, 5. DONG XC. Hadoop Technology on An Insider: In-depth Analyze on Architecture Design and Implementation Principle[M]. Beijing: China Machine Press, 2013, 5.

A Fair Scheduling Algorithm Based on Dynamic Slot Allocation

SU Tao-tao1, ZHENG Lu2
(1. Computer Science Department, South-Central University For Nationalities, Wuhan Hubei 430074; 2. Experimental Teaching and Laboratory Management Center, South-Central University For Nationalities, Wuhan Hubei 430074)

The fair scheduling algorithm based on the deficit in Hadoop framework sets the timing compute and update the job information by a unified configuration. It has affected to some extent the fairness of the job scheduling, and it can’t meet the resource requirements of the job at the same time. In view of the lack of the fair scheduling algorithm based on the deficit about the configuration, propose a fair scheduling algorithm based on dynamic slot allocation, it can undertake the slot allocation to ensure the real fairness by real-time computing and updating the job deficit.

Fair scheduling; Deficit; Fairness; Dynamic slot allocation.

TP301.6

A

10.3969/j.issn.1003-6970.2017.01.011

中南民族大学中央高校基本科研业务费专项资金项目资助(CZZ15002)

苏涛涛(1991-)，男，河南周口人，中南民族大学计算机学院硕士研究生，研究方向为大数据分析及分布式处理；郑禄(1989-)，男，硕士，中南民族大学实验教学中心助理实验师，主要研究方向为实验室建设、计算机技术(通讯作者)。

本文著录格式：苏涛涛，郑禄. 一种基于动态slot分配的公平调度算法[J]. 软件，2017，38（1）：49-52