王少娟

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

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

中圖分類號(hào)：TP301.6文獻(xiàn)標(biāo)識(shí)碼：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ù)亟待處理和存儲(chǔ)的需求，于是專家們將并行計(jì)算的思想遷移到集群計(jì)算上，云計(jì)算[1]應(yīng)運(yùn)而生。Hadoop[2]是一個(gè)云環(huán)境下開源的大數(shù)據(jù)處理平臺(tái)，是MapReduce[3]調(diào)度方式和GFS[4]數(shù)據(jù)存儲(chǔ)方式的開源實(shí)現(xiàn)，無疑成為大數(shù)據(jù)時(shí)代的寵兒。

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

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

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

2.1作業(yè)負(fù)載分類

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

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

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

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

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

3.2算法描述

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

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

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

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

3）記錄節(jié)點(diǎn)信息，計(jì)算慢任務(wù)的剩余完成時(shí)間，選取最長(zhǎng)剩余時(shí)間的slowTask并為其啟動(dòng)備份任務(wù)。

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

4實(shí)驗(yàn)結(jié)果及性能分析

4.1實(shí)驗(yàn)環(huán)境

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

4.2實(shí)驗(yàn)仿真及結(jié)果分析

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

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

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

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

5結(jié)束語

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

參考文獻(xiàn)

[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ù)中心負(fù)載分析的自適應(yīng)延遲調(diào)度算法[J].通信學(xué)報(bào)，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平臺(tái)下改進(jìn)的LATE調(diào)度算法[J]. 計(jì)算機(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ìn)算法[J]. 計(jì)算機(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è)計(jì)與實(shí)現(xiàn)原理[M].北京：機(jī)械工業(yè)出版社，2013.5.

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

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