一種基于動(dòng)態(tài)slot分配的公平調(diào)度算法

蘇濤濤，鄭 祿

(1. 中南民族大學(xué)計(jì)算機(jī)科學(xué)學(xué)院，湖北 武漢 430074; 2. 中南民族大學(xué)實(shí)驗(yàn)教學(xué)與實(shí)驗(yàn)室管理中心，湖北 武漢 430074)

一種基于動(dòng)態(tài)slot分配的公平調(diào)度算法

蘇濤濤1，鄭 祿2

(1. 中南民族大學(xué)計(jì)算機(jī)科學(xué)學(xué)院，湖北 武漢 430074; 2. 中南民族大學(xué)實(shí)驗(yàn)教學(xué)與實(shí)驗(yàn)室管理中心，湖北 武漢 430074)

Hadoop框架中基于缺額的公平調(diào)度算法以統(tǒng)一的固定配置設(shè)置定時(shí)計(jì)算和更新作業(yè)信息，在一定程度上影響了其作業(yè)調(diào)度的公平性，同時(shí)也不能滿足作業(yè)的資源需求。針對(duì)基于缺額的公平調(diào)度算法配置方式的不足,提出一種基于公平性的動(dòng)態(tài)slot分配算法，通過實(shí)時(shí)計(jì)算更新缺額進(jìn)行slot分配以確保真正的公平性。

公平調(diào)度；缺額；公平性；slot分配

0 引言

作業(yè)調(diào)度算法是Hadoop集群中的核心算法，作業(yè)調(diào)度算法的改進(jìn)可以大大提高整個(gè)集群中資源的利用率[1]。Hadoop自帶的有幾個(gè)簡單的作業(yè)調(diào)度算法。同時(shí)，為了滿足各種不同類型或不同目的的復(fù)雜作業(yè)的調(diào)度，Hadoop基為一個(gè)開源框架的設(shè)計(jì)思想以插件式的形式集成了新的作業(yè)調(diào)度算法[2-3]。公平調(diào)度算法是一種賦予作業(yè)資源的方法，其目的是讓所有的作業(yè)隨著時(shí)間的推移，都能平均的獲取等同的集群中的共享資源[4]。但基于缺額的公平調(diào)度算法中以統(tǒng)一的配置方式設(shè)置定時(shí)計(jì)算和更新時(shí)間，并不能保證缺額的實(shí)時(shí)性，進(jìn)而會(huì)影響到資源分配時(shí)的公平性。針對(duì)該算法配置方式的不足,提出一種基于動(dòng)態(tài)slot分配的公平調(diào)度算法，通過實(shí)時(shí)計(jì)算更新缺額進(jìn)行slot分配以確保真正的公平性。

1 公平調(diào)度

1.1 基本概念

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

表1 變量定義Tab.1 Variable Definition

1.2 基于缺額的公平調(diào)度算法

公平調(diào)度器（Fair Scheduler）是由Facebook開發(fā)，是一種適合于多用戶共享集群環(huán)境的調(diào)度器，其吞吐率高于先進(jìn)先出調(diào)度器（FIFO）[5]。公平調(diào)度器的基本思想是隨著時(shí)間推移平均分配工作，這樣每個(gè)作業(yè)都能平均地分配到資源（Hadoop集群中資源以Slot為單位進(jìn)行組織）。公平調(diào)度器是按資源池（pool）來組織作業(yè)，并把資源公平的分配到這些資源池里。在每一個(gè)資源池內(nèi)，同樣也會(huì)使用公平策略給資源池中的作業(yè)分配slot。當(dāng)然，用戶也可以給資源池或者資源池中的作業(yè)設(shè)置相應(yīng)的權(quán)重，以不按比例的方式共享集群中的資源。

Hadoop-0.20.2版本的公平調(diào)度器，采用了基于缺額調(diào)度算法[6-8]，其核心算法是當(dāng)出現(xiàn)空閑Slot時(shí)，公平調(diào)度器會(huì)將此Slot分配給缺額最大的作業(yè)（系統(tǒng)默認(rèn)情況下會(huì)每隔500毫秒更新一次Job信息，包括：作業(yè)缺額等信息）。核心算法的主要思想是：將作業(yè)的優(yōu)先級(jí)轉(zhuǎn)化成權(quán)重，優(yōu)先級(jí)越高權(quán)重越大，而權(quán)重越大，獲得的資源越多，通過權(quán)重計(jì)算出的資源就是“公平共享量”，當(dāng)然，這是理想狀態(tài)下，每個(gè)作業(yè)應(yīng)得到的資源，而在實(shí)際情況下，由于種種原因而獲取不到這些資源，因而產(chǎn)生一個(gè)差值，為了使這個(gè)差值更能體現(xiàn)實(shí)際意義，又將時(shí)間融合進(jìn)去，即差值與時(shí)間的乘積，這就是缺額（缺額是累加的，如果一個(gè)作業(yè)為獲得資源，其缺額會(huì)隨著時(shí)間不斷增大，直到能夠排到隊(duì)列首位為止），計(jì)算公式如下：

每次出現(xiàn)空閑Slot時(shí)，優(yōu)先選擇缺額大的作業(yè)，以便達(dá)到公平調(diào)度的目的。

1.3 該算法的不足之處

Hadoop是一種m/s模式框架，主節(jié)點(diǎn)上運(yùn)行Job-Tracker，主要用來監(jiān)控整個(gè)集群中作業(yè)的運(yùn)行情況并對(duì)資源進(jìn)行管理和調(diào)度；從節(jié)點(diǎn)上運(yùn)行Task-Tracker，主要負(fù)責(zé)監(jiān)控任務(wù)執(zhí)行和報(bào)告進(jìn)度等。TaskTracker通過心跳會(huì)定期匯報(bào)信息給Job-Tracker，包括內(nèi)存使用量，內(nèi)存剩余量，正在運(yùn)行的task，資源情況等。主節(jié)點(diǎn)中的調(diào)度即發(fā)生在心跳到達(dá)時(shí)，若TaskTracker匯報(bào)自己有空閑資源，則JobTracker使用調(diào)度算法選擇一個(gè)任務(wù)發(fā)射到該節(jié)點(diǎn)運(yùn)行。調(diào)度的實(shí)質(zhì)是slot的分配，而作業(yè)調(diào)度的觸發(fā)條件是每次心跳信息中有空閑slot。

基于缺額的公平調(diào)度器在Yahoo等大公司內(nèi)部均被采用，但在使用過程中，會(huì)存在一些問題表現(xiàn)為：由于基于缺額的公平調(diào)度過程中更新缺額是按照固定配置設(shè)置的時(shí)間△T進(jìn)行更新，并不能保證當(dāng)產(chǎn)生新的空閑Slot的時(shí)得到的Job就是當(dāng)前缺額最大的Job，其次，由于作業(yè)調(diào)度過程中在task處理完成之后才會(huì)釋放該task所占用的資源，在處理的作業(yè)都是大作業(yè)的情況下，數(shù)據(jù)分塊后分配給每個(gè)task進(jìn)行處理，則會(huì)出現(xiàn)作業(yè)占用資源的時(shí)間較久的情況，在每次匯報(bào)心跳信息時(shí)空閑資源出現(xiàn)的頻率會(huì)降低，從而導(dǎo)致調(diào)度頻率會(huì)降低，這種情況下定時(shí)更新Job信息的頻率并沒有改變，從另外一個(gè)角度，Job處理時(shí)間較久，定時(shí)更新Job信息的次數(shù)就會(huì)增加，反而會(huì)增大所占用的系統(tǒng)資源比例。

定義Jobs為作業(yè)隊(duì)列中所有作業(yè)的集合，Jobs={job1,job2,job3,…}，假設(shè)集群是由一個(gè)master節(jié)點(diǎn)和若干個(gè)slave節(jié)點(diǎn)組成，定義JobTracker為該master節(jié)點(diǎn)，slave節(jié)點(diǎn)定義為TaskTrackers={T1,T2, T3,…}。其大致算法過程如表2：

表2 基于缺額的公平調(diào)度算法Tab.2 The Fair Scheduling Algorithm Based On The Deficiency

上述算法中的步驟3和3均是在其他線程中定期執(zhí)行。設(shè)時(shí)間點(diǎn)T1，T2，且T2 - T1=△T，根據(jù)固定配置則會(huì)在T1時(shí)間點(diǎn)計(jì)算出當(dāng)前缺額最大的作業(yè)記為Job1，在T2時(shí)間點(diǎn)計(jì)算出當(dāng)前缺額最大的作業(yè)記為Job2，TaskTracker匯報(bào)信息中有空閑slot的時(shí)間點(diǎn)在T1和T2之間記為時(shí)間點(diǎn)T3，按照上述算法則會(huì)將產(chǎn)生的空閑slot分配給Job1，而這一過程并不符合公平調(diào)度中“公平性”的原則。圖形描述如圖1所示：

圖1 基于缺額的公平調(diào)度算法圖形描述Fig.1 the graph description of The Fair Scheduling Algorithm Based On The Deficiency

針對(duì)上述出現(xiàn)的情況，可以取消固定配置中的定時(shí)更新缺額，在當(dāng)TaskTracker匯報(bào)自己有空閑slot時(shí)去計(jì)算每個(gè)剩余Job的缺額，從而將該slot分配給缺額最大的Job。圖形描述如圖2所示：

圖2 基于動(dòng)態(tài)slot分配的調(diào)度算法圖形描述Fig.2 the graph description of The Fair Scheduling Algorithm Based On Dynamic Slot Allocation

2 基于動(dòng)態(tài)slot分配的公平調(diào)度算法

圖1可以看出，當(dāng)產(chǎn)生出新的空閑Slot時(shí)得到的缺額最大的Job只是上一個(gè)計(jì)算更新的時(shí)間節(jié)點(diǎn)的結(jié)果（即：Job1），并不是當(dāng)前時(shí)間節(jié)點(diǎn)的結(jié)果，因此難以真正意義上的保證作業(yè)分配資源的公平性。

在調(diào)度過程中，為了彌補(bǔ)基于缺額調(diào)度算法中出現(xiàn)的作業(yè)公平性的不足，提出一種改進(jìn)算法——基于動(dòng)態(tài)slot分配的公平調(diào)度算法，該算法丟棄掉算法原有的固定配置，在當(dāng)有空閑slot產(chǎn)生時(shí)才進(jìn)行計(jì)算更新，計(jì)算公式保持不變。改進(jìn)后的算法如表3：

表3 基于動(dòng)態(tài)slot分配的公平調(diào)度算法Tab.3 The Fair Scheduling Algorithm Based On Dynamic Slot Allocation

基于缺額的公平調(diào)度算法是通過為上個(gè)時(shí)間周期內(nèi)沒有受到公平分配資源的Job，分配資源來實(shí)現(xiàn)作業(yè)間的公平性，這種公平性往往顯得滯后。同時(shí)，在處理的作業(yè)都是大作業(yè)的情況下，作業(yè)分塊后分配給task的則會(huì)造成空閑slot產(chǎn)生的頻率會(huì)降低，這種情況下定時(shí)更新操作就會(huì)顯得較為頻繁，其占用系統(tǒng)資源的比例也會(huì)有所顯現(xiàn)。而基于動(dòng)態(tài)slot分配的公平調(diào)度算法是在有新的空閑slot產(chǎn)生的情況下才進(jìn)行Job信息的更新，首先保證了作業(yè)的公平性，其次，去除固定配置在需要的情況下才去計(jì)算更新Job的信息，在處理大作業(yè)的過程中也釋放了定時(shí)計(jì)算更新所需要的資源，減少計(jì)算更新Job信息的次數(shù)，在一定程度上提高了對(duì)大作業(yè)處理效率。

3 實(shí)驗(yàn)結(jié)果對(duì)比及分析

為了驗(yàn)證針對(duì)基于缺額的作業(yè)調(diào)度算法假設(shè)，并且為了使實(shí)驗(yàn)結(jié)果更能明顯，實(shí)驗(yàn)時(shí)將固定配置的參數(shù)放大一定的倍數(shù)，設(shè)計(jì)若干個(gè)小作業(yè)（對(duì)10個(gè)1M文件進(jìn)行字?jǐn)?shù)統(tǒng)計(jì)，記對(duì)每10個(gè)文件的統(tǒng)計(jì)為1個(gè)Job）。在產(chǎn)生空閑slot時(shí)使用基于缺額的作業(yè)調(diào)度算法算法所處理的Job與當(dāng)前時(shí)間節(jié)點(diǎn)計(jì)算缺額最大的Job不同的個(gè)數(shù)（誤差Job的個(gè)數(shù)）如表4所示：

表4 誤差Job個(gè)數(shù)Tab.4 the number of error Jobs

從上表的實(shí)驗(yàn)結(jié)果中可以得知，當(dāng)有空閑slot產(chǎn)生時(shí)基于缺額公平調(diào)度算法計(jì)算出來缺額最大的作業(yè)與當(dāng)前時(shí)間點(diǎn)計(jì)算缺額最大的作業(yè)是不一致的，這也就說明，基于缺額的作業(yè)調(diào)度算法有失公平性的準(zhǔn)則。

本組實(shí)驗(yàn)的目的是比較在處理大作業(yè)的情況下基于缺額的調(diào)度算法和基于動(dòng)態(tài)slot分配的調(diào)度算法的運(yùn)行效率，設(shè)計(jì)若干個(gè)大作業(yè)（對(duì)10個(gè)20M文件進(jìn)行字?jǐn)?shù)統(tǒng)計(jì)，記對(duì)每10個(gè)文件的統(tǒng)計(jì)為1個(gè)Job），處理相同作業(yè)量大作業(yè)的情況下，系統(tǒng)運(yùn)用兩種算法完成所有作業(yè)所消耗的總體時(shí)間對(duì)比如圖3所示：

圖3 實(shí)驗(yàn)結(jié)果Fig.3 the experimental result

圖4為兩種公平調(diào)度算法在處理相同作業(yè)數(shù)量（10個(gè)Job）大作業(yè)的過程中，進(jìn)行計(jì)算更新剩余待執(zhí)行Job信息次數(shù)的對(duì)比結(jié)果，兩種算法各執(zhí)行10次：

圖4 實(shí)驗(yàn)結(jié)果Fig.4 the experimental result

由上圖可知在處理大作業(yè)的情況下空閑slot產(chǎn)生的頻率降低，這種情況下使用基于缺額公平調(diào)度的固定配置去定時(shí)計(jì)算更新Job信息時(shí)，計(jì)算更新的次數(shù)比動(dòng)態(tài)slot分配算法的計(jì)算更新次數(shù)多。根據(jù)上述的結(jié)果,在處理大作業(yè)的情況下，將兩種調(diào)度算法的性能進(jìn)行對(duì)比，如表5所示。

分析總結(jié)：在實(shí)驗(yàn)對(duì)比結(jié)果中，通過比較可以發(fā)現(xiàn)，基于公平調(diào)度的動(dòng)態(tài)slot分配算法雖然在效率上與基于缺額的公平調(diào)度算法相比比較接近，但在公平性上卻有所提高，與提出改進(jìn)的初衷是相符的，并且在處理大作業(yè)的情況下改進(jìn)后的算法效率也在一定程度上高于基于缺額的公平調(diào)度算法。

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

4 結(jié)束語

本文針對(duì)Hadoop中基于缺額的公平調(diào)度算法所存在的問題和現(xiàn)象提出一種基于公平性的動(dòng)態(tài)slot分配算法，后者在作業(yè)調(diào)度的過程中不影響算法效率的同時(shí)又在一定程度上保證了作業(yè)選擇“公平性”的原則。

[1] 姜淼. Hadoop云平臺(tái)下調(diào)度算法的研究[D]. 長春: 吉林大學(xué), 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集群作業(yè)的調(diào)度算法[J]. 程序員, 2009 (12): 119-121. WANG F. The Scheduling Algorithm in Hadoop Cluster Jobs[J]. PROGRAMMER, 2009(12): 119-121

[4] 張青. 網(wǎng)格環(huán)境下任務(wù)調(diào)度算法的應(yīng)用研究[D]. 大連: 大連海事大學(xué), 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技術(shù)內(nèi)幕: 深入解析MapReduce架構(gòu)設(shè)計(jì)與實(shí)現(xiàn)原理[M]. 北京: 機(jī)械工業(yè)出版社, 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

中南民族大學(xué)中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金項(xiàng)目資助(CZZ15002)

蘇濤濤(1991-)，男，河南周口人，中南民族大學(xué)計(jì)算機(jī)學(xué)院碩士研究生，研究方向?yàn)榇髷?shù)據(jù)分析及分布式處理；鄭祿(1989-)，男，碩士，中南民族大學(xué)實(shí)驗(yàn)教學(xué)中心助理實(shí)驗(yàn)師，主要研究方向?yàn)閷?shí)驗(yàn)室建設(shè)、計(jì)算機(jī)技術(shù)(通訊作者)。

本文著錄格式：蘇濤濤，鄭祿. 一種基于動(dòng)態(tài)slot分配的公平調(diào)度算法[J]. 軟件，2017，38（1）：49-52