異構環境下改進的LATE調度算法

王少娟

摘要：針對異構環境下LATE算法在選擇備份任務及執行節點時的不足，提出一個改進的IR-LATE調度算法。算法通過計算為剩余完成時間最長、最需要備份的慢任務啟動備份，并將其按負載不同進行分類，結合輪詢算法，將備份任務分配到負載最小且成功/負載比高的節點上執行。實驗結果表明，該算法與LATE算法比較，有效的將作業完成時間縮短了30%左右，提高了執行效率，進而促進系統的負載均衡。

關鍵詞：異構環境；LATE；調度算法；慢任務；負載均衡

中圖分類號：TP301.6文獻標識碼：A

Abstract：Analyzing the existing scheduler in the heterogeneous environment， and considering the lack of LATE scheduling algorithm in allocating TaskTracker to execute backup tasks， this paper put forward an improved IRLATE scheduling algorithm. The slow tasks with the longest time remaining and the most needing the backup were found out by calculating. They were classified according to the different load. Then the backup tasks were assigned to the TaskTracker with a minimum workload and high success/workload ratio combined with RoundRobin algorithm. The experimental results show that， compared with LATE algorithm， the algorithm is effective in shortening the operation execution time by 30% and improving the execution efficiency， thus contributing to the loadbalancing system.

Key words：heterogeneous environment； LATE； scheduling algorithm； slow task； load balancing

1引言

互聯網的迅猛崛起給人們帶來了豐富的網絡生活，隨之也加劇了海量數據亟待處理和存儲的需求，于是專家們將并行計算的思想遷移到集群計算上，云計算[1]應運而生。Hadoop[2]是一個云環境下開源的大數據處理平臺，是MapReduce[3]調度方式和GFS[4]數據存儲方式的開源實現，無疑成為大數據時代的寵兒。

由硬件配置迥異的節點組成的Hadoop集群，其中運行著多個Job，如何讓調度器對資源進行合理分配，以期使得集群資源能被更有效的利用成為一個不可忽視的方面，而其中的關鍵點就是調度策略的合理設計。Hadoop自帶的調度算法：FIFO算法、Fair算法[5]、Capacity算法[6]及金嘉暉等人提出的等待時間閾值的自適應模型[7]均是以同構系統為前提的，而未考慮其異構性。LATE[8]調度算法，由M Zaharia等人研究，針對異構環境下的慢任務探測提出一種通過估計任務剩余完成時間，選擇快節點為最長剩余完成時間的任務啟動備份的調度策略，雖然其計算效率有所提高，卻不曾考慮任務及節點的負載類型。

本文在分析研究前人成果的基礎上，對LATE調度算法在備份任務及執行節點的選擇方面提出了改進。首先將提交的作業按負載類型進行分類，獲取慢任務中剩余時間最長的slowTask并為其啟動備份，然后在選擇執行備份任務的快節點時，根據負載類型，結合輪詢算法，選擇存在空閑槽且成功/負載比高的最快節點，以期達到縮短作業完成時間，提高資源利用率，優化集群負載。

2相關工作分類及定義

2.1作業負載分類

按照文獻[9]的負載分類機制，將任務負載分為CPU_bound和I/O_bound兩類。在Hadoop環境中運行的作業，只有全部的Map任務結束才會執行Reduce任務，因此本文僅考慮Map任務。Map任務執行可分解為3步操作：

（1）初始化輸入數據；

（2）計算Map任務；

（3）將輸出結果存儲到本地磁盤。

任務負載分類所用到的符號定義見表1。

3.2算法描述

每個節點將自身的CCPU，Cmem，Cdisk，Cnw信息、任務成功率和節點的負載信息通過Heartbeat發送給JobTracker，JobTracker在接收到這些信息后重新計算workload值，并更新BurdenforCPUList和BurdenforIOList兩個鏈表。利用上述信息計算并選擇當前執行任務中剩余時間最長的slowTask，并記錄下該任務所在節點的成功/負載比；選擇執行備份任務的TaskTracker時，根據任務負載類型的不同，CPU_bound遍歷BurdenforCPUList，IO_bound遍歷BurdenforIOList，結合輪詢算法選擇存在空閑槽點且其workload值小于落后節點負載值的高成功/負載比的節點執行，加快任務的完成。IR-LATE算法流程圖如圖1所示。

IRLATE算法執行過程如下：

1）用戶提交作業到JobTracker。

2）JobTracker根據公式判斷作業的負載類型。

3）記錄節點信息，計算慢任務的剩余完成時間，選取最長剩余時間的slowTask并為其啟動備份任務。

4）選擇執行備份任務的TaskTracker時，結合輪詢算法，根據任務類型，若其為CPU_bound，則遍歷BurdenforCPUList，若為IO_bound則遍歷BurdenforIOList，選擇存在空閑槽且成功/負載比最高的最快節點執行。

4實驗結果及性能分析

4.1實驗環境

實驗集群由5臺PC機，通過虛擬機的方式構建測試環境。4臺PC機上安裝不同數量的虛擬機來模擬異構環境，每個虛擬機分配600M內存、6GB硬盤，使用VirtualBox4.3.20，安裝Ubuntu14.04.02，JDK版本為1.8.0_40，Hadoop版本為2.6.0。配置見表2。

4.2實驗仿真及結果分析

本文選用Hadoop自帶的性能測試集：TeraSort和GrepCount為測試數據，在Hadoop平臺下進行仿真實驗。文獻[9]已論證TeraSort為I/O_bound作業，GrepCount為CPU_bound作業。實驗中設定參數值：SpeculativeCap為20%，SlowTaskThreshold為25%，SlowNodeThreshold為25%，其已在文獻[12]中論證的最佳。2個測試集分別用LATE算法和IR-LATE算法執行，實驗將每個作業執行10次取其平均完成時間來保證數據的有效性。通過比較作業完成時間及備份任務完成時間來體現改進算法的優勢。

實驗結果如圖2所示，輸入5GB數據，IR-LATE調度算法執行時間比LATE調度算法執行的時間少30%左右。

圖3和圖4描述了TeraSort、GrepCount作業輸入數據分別為1GB、3GB、5GB時，用3臺服務器分別執行LATE算法和改進的LATE算法時工作完成時間的對比圖。由圖3和圖4可以得知，當輸入數據量較小，集群較小時兩種算法完成時間相差無幾。圖3TeraSort（3臺服務器）完成時間

由圖5和圖6可知，當輸入數據量增大，集群規模變大時，IRLATE調度算法的優勢就表現出來了。因為數據量劇增導致集群負載加劇，與此同時slowTask出現的概率也會加大。而LATE算法對剩余完成時間估算不夠準確，會導致為不必要的慢任務啟動備份，反而延遲了作業完成時間，耽誤整體進度。IRLATE算法能準確估算剩余時間，并為剩余時間最長的slowTask啟動備份，將其調度到負載低且成功/負載比高的節點上執行。這樣不僅節約了系統資源，而且能使真正的slowTask盡快完成，有效縮短工作完成時間。

5結束語

文章針對LATE算法在為慢任務啟動備份及選擇執行節點時的不足，提出了改進的IR-LATE算法。該算法通過準確計算任務的剩余完成時間找出剩余時間最長的slowTask并為其啟動備份，根據任務負載及節點負載的不同分類，為備份任務選擇負載低、成功率高的節點執行。實驗結果表明，IR-LATE算法相比LATE算法，不僅縮短了任務的完成時間，而且在數據量增大，集群規模增大時有更好的執行效率。但本文算法只考慮了同機架集群問題，今后將擴展文中算法，進一步研究跨機架的調度算法。

參考文獻

[1]VAQUERO L M， RODEROMERINO L，CACERES J， etal.A breakin the clouds：towards a cloud definition[J].ACM SIGCOMMComputer Communication Review，2009，39（1）：50-55.

[2]Hadoop [EB/OL]. http：//hadoop.apache.org/.

[3]DEAN J，GHEMAWAT S.MapReduce：simplified data processingon large cluster[C]//Proc of the 6th Symposium on OperatingSystems Design and Implementation.San Francisco：GoogleInc，2004.

[4]GHEMAWAT S，GOGIOFF H，LEUNG P T.The google file system[C]//Proc of the 19th ACM Symp on Operating SystemsPrinciples，2003：29-43.

[5]Fair_scheduler [EB/OL]. http：//hadoop.apache.org/common/docs/stable/fair_scheduler.html.

[6]Capacity_scheduler[EB/OL].http：//hadoop.apache.org/common/docs/current/hadoopyarn/h aadoopyarnsite/CapacityScheduler.html.

[7]金嘉暉，羅軍舟.基于數據中心負載分析的自適應延遲調度算法[J].通信學報，2011，32（7）：47-56.

[8]ZAHARIA M，KONWINSKI A， JOSEPH A D， et al. Improving MapReduce Performance in Heterogeneous Environments.[J]. Osdi， 2008：29-42.

[9]CHAO T，ZHOU H，HE Y， et al. A dynamic MapReduce scheduler for heterogeneous workloads[C]// Proc of the 8th International Conference on Grid and Cooperative Computing， China， 2009：218-224.

[10]胡丹， 于炯， 英昌甜，等. Hadoop平臺下改進的LATE調度算法[J]. 計算機工程與應用， 2014， （4）：86-89. DOI：10.3778/j.issn.1002-8331.1204-0040.

[11]趙曉冰， 王世卿. 異構環境下調度任務備份的改進算法[J]. 計算機應用與軟件， 2013， （12）：105-107. DOI：10.3969/j.issn.1000-386x.2013.12.027.

[12]CHEN Quan，ZHANG Daqiang， et al. SAMR： A selfadaptive mapreducescheduling algorithm in heterogeneous environment[C]//Proc of IEEE International Conference on Computer and Information Technology. LosAlamitos： IEEE computer society，2010： 2736-2743.

[13]董西成.Hadoop技術內幕：深入解析MapReduce架構設計與實現原理[M].北京：機械工業出版社，2013.5.

[14]李春艷， 何一舟， 戴彬. Hadoop平臺的多隊列作業調度優化方法研究[J]. 計算機應用研究， 2014， 31（3）：705-707. DOI：10.3969/j.issn.1001-3695.2014.03.015.

[15]欒亞建， 黃翀民， 龔高晟，等. Hadoop平臺的性能優化研究[J]. 計算機工程，2010，36（14）： 262-263. DOI：10.3969/j.issn.1000-3428.2010.14.095.