一種基于動態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