異構(gòu)環(huán)境下改進的LATE調(diào)度算法

王少娟

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

關(guān)鍵詞：異構(gòu)環(huán)境；LATE；調(diào)度算法；慢任務(wù)；負載均衡

中圖分類號：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引言

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

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

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

2相關(guān)工作分類及定義

2.1作業(yè)負載分類

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

（1）初始化輸入數(shù)據(jù)；

（2）計算Map任務(wù)；

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

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

3.2算法描述

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

IRLATE算法執(zhí)行過程如下：

1）用戶提交作業(yè)到JobTracker。

2）JobTracker根據(jù)公式判斷作業(yè)的負載類型。

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

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

4實驗結(jié)果及性能分析

4.1實驗環(huán)境

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

4.2實驗仿真及結(jié)果分析

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

實驗結(jié)果如圖2所示，輸入5GB數(shù)據(jù)，IR-LATE調(diào)度算法執(zhí)行時間比LATE調(diào)度算法執(zhí)行的時間少30%左右。

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

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

5結(jié)束語

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

參考文獻

[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]金嘉暉，羅軍舟.基于數(shù)據(jù)中心負載分析的自適應(yīng)延遲調(diào)度算法[J].通信學(xué)報，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調(diào)度算法[J]. 計算機工程與應(yīng)用， 2014， （4）：86-89. DOI：10.3778/j.issn.1002-8331.1204-0040.

[11]趙曉冰， 王世卿. 異構(gòu)環(huán)境下調(diào)度任務(wù)備份的改進算法[J]. 計算機應(yīng)用與軟件， 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技術(shù)內(nèi)幕：深入解析MapReduce架構(gòu)設(shè)計與實現(xiàn)原理[M].北京：機械工業(yè)出版社，2013.5.

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

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