蘇濤濤，鄭 祿

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

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

蘇濤濤1，鄭 祿2

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

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

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

0 引言

作業(yè)調(diào)度算法是Hadoop集群中的核心算法，作業(yè)調(diào)度算法的改進(jìn)可以大大提高整個集群中資源的利用率[1]。Hadoop自帶的有幾個簡單的作業(yè)調(diào)度算法。同時，為了滿足各種不同類型或不同目的的復(fù)雜作業(yè)的調(diào)度，Hadoop基為一個開源框架的設(shè)計思想以插件式的形式集成了新的作業(yè)調(diào)度算法[2-3]。公平調(diào)度算法是一種賦予作業(yè)資源的方法，其目的是讓所有的作業(yè)隨著時間的推移，都能平均的獲取等同的集群中的共享資源[4]。但基于缺額的公平調(diào)度算法中以統(tǒng)一的配置方式設(shè)置定時計算和更新時間，并不能保證缺額的實時性，進(jìn)而會影響到資源分配時的公平性。針對該算法配置方式的不足,提出一種基于動態(tài)slot分配的公平調(diào)度算法，通過實時計算更新缺額進(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)度器的基本思想是隨著時間推移平均分配工作，這樣每個作業(yè)都能平均地分配到資源（Hadoop集群中資源以Slot為單位進(jìn)行組織）。公平調(diào)度器是按資源池（pool）來組織作業(yè)，并把資源公平的分配到這些資源池里。在每一個資源池內(nèi)，同樣也會使用公平策略給資源池中的作業(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時，公平調(diào)度器會將此Slot分配給缺額最大的作業(yè)（系統(tǒng)默認(rèn)情況下會每隔500毫秒更新一次Job信息，包括：作業(yè)缺額等信息）。核心算法的主要思想是：將作業(yè)的優(yōu)先級轉(zhuǎn)化成權(quán)重，優(yōu)先級越高權(quán)重越大，而權(quán)重越大，獲得的資源越多，通過權(quán)重計算出的資源就是“公平共享量”，當(dāng)然，這是理想狀態(tài)下，每個作業(yè)應(yīng)得到的資源，而在實際情況下，由于種種原因而獲取不到這些資源，因而產(chǎn)生一個差值，為了使這個差值更能體現(xiàn)實際意義，又將時間融合進(jìn)去，即差值與時間的乘積，這就是缺額（缺額是累加的，如果一個作業(yè)為獲得資源，其缺額會隨著時間不斷增大，直到能夠排到隊列首位為止），計算公式如下：

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

1.3 該算法的不足之處

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實驗結(jié)果對比及分析

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

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

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

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

圖3 實驗結(jié)果Fig.3 the experimental result

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

圖4 實驗結(jié)果Fig.4 the experimental result

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

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

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

4 結(jié)束語

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

[1] 姜淼. Hadoop云平臺下調(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è)計與實現(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é)中央高校基本科研業(yè)務(wù)費專項資金項目資助(CZZ15002)

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

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