魏巍，劉釗遠

異構(gòu)環(huán)境下MapRuduce任務(wù)調(diào)度算法優(yōu)化

魏巍，劉釗遠

Hadoop作為世界領(lǐng)先的大數(shù)據(jù)平臺，其性能更多地依賴于MapReduce任務(wù)調(diào)度機制。通過對MapReduce任務(wù)調(diào)度機制中推測算法的研究，提出一種高效、準(zhǔn)確和基于優(yōu)先級的改進Hadoop調(diào)度算法。通過測試發(fā)現(xiàn)，改進后的Hadoop調(diào)度算法在異構(gòu)環(huán)境下能夠?qū)β浜笕蝿?wù)判定準(zhǔn)確，更好地維持系統(tǒng)的負載平衡，減少系統(tǒng)對任務(wù)的響應(yīng)時間，增加對高優(yōu)先級任務(wù)的響應(yīng)速度，提高MapReduce任務(wù)調(diào)度算法的性能。

異構(gòu)環(huán)境；推測算法；負載均衡；優(yōu)先級

0 引言

近些年來，在大數(shù)據(jù)背景下，ApacheHadoop已經(jīng)逐漸成為研究的熱點，業(yè)界對于開源Hadoop的應(yīng)用也在不斷的加深。Google、IBM、Microsoft、Amazon、Yahoo、Alibaba等IT互聯(lián)網(wǎng)公司都推出了自己的云計算服務(wù)平臺，并把云計算作為未來重要的戰(zhàn)略目標(biāo)[1-2]。大多數(shù)的開源云計算系統(tǒng)都是基于Hadoop應(yīng)用平臺，尤其在應(yīng)用研究領(lǐng)域發(fā)展更為廣泛。Hadoop應(yīng)用框架最核心的設(shè)計是HDFS[3]（分布式文件系統(tǒng)）和MapReduce，HDFS負責(zé)海量數(shù)據(jù)的存儲，而MapReduce負責(zé)海量數(shù)據(jù)的計算。

MapReduce的優(yōu)勢之一在于容錯機制對于用戶透明化，并不需要用戶去參與實現(xiàn)。當(dāng)一個節(jié)點出現(xiàn)崩潰時，其上的任務(wù)被分配給其它的節(jié)點繼續(xù)運行。類似情況，如果一個任務(wù)在一個節(jié)點上被執(zhí)行的時間過長，則這個任務(wù)被稱作掉隊者任務(wù)或后備任務(wù)。把這個掉隊者任務(wù)放在另外一個節(jié)點去執(zhí)行，以便快速完成，這個過程稱之為推測執(zhí)行[4]。Hadoop現(xiàn)有的調(diào)度算法對于推測執(zhí)行這一部分并不是很完善，主要體現(xiàn)在對后備任務(wù)的判定上。目前常用的調(diào)度算法有Hadoop默認的調(diào)度算法FIFO（先進先出），這種算法并不能體現(xiàn)出作業(yè)的優(yōu)先級和推測任務(wù)的執(zhí)行；Facebook提出的Fair Schedule（公平調(diào)度），對于權(quán)值高的任務(wù)多分配資源，并且支持搶占，如果作業(yè)數(shù)過多，可能會頻繁的進行上下文切換，增加后備任務(wù)的執(zhí)行時間；Yahoo公司提出的Capacity Schedule（計算能力調(diào)度），雖然不支持搶占，但是通過設(shè)定一些閾值來判定后備任務(wù)，這在異構(gòu)集群中誤差較大。針對以上Hadoop調(diào)度算法不足的基礎(chǔ)上，提出一種基于優(yōu)先級的改進Hadoop調(diào)度算法，并同其它的調(diào)度算法進行比較研究。

1 現(xiàn)有MapReduce任務(wù)調(diào)度算法

在Hadoop集群中，當(dāng)一個空閑Slave節(jié)點請求分配任務(wù)時，有三種任務(wù)類別會被調(diào)度器所調(diào)度[5]。（1）處于等待狀態(tài)還沒有被執(zhí)行的任務(wù)，若是本地任務(wù)，則會優(yōu)先選擇。（2）執(zhí)行失敗的任務(wù)，優(yōu)先級高的先被執(zhí)行。（3）需要推測執(zhí)行的掉隊者任務(wù)。為了挑選和執(zhí)行掉隊者任務(wù)，Hadoop平臺上使用的是推測式執(zhí)行算法。

Hadoop對于集群中作業(yè)的處理主要分為Map和Reduce兩個過程，如圖1所示：

圖1 Map/Reduce task運行過程

Map Task過程，存儲在HDFS上的Input split經(jīng)過用戶自定義map函數(shù)處理，得到一個個鍵值對[6]。這些鍵值對被收集后存放在環(huán)形內(nèi)存緩沖區(qū)中，當(dāng)緩沖區(qū)滿后，數(shù)據(jù)經(jīng)過排序，由MapReduce將其寫入本地磁盤，生成一個臨時文件，并在必要時對數(shù)據(jù)進行合并和壓縮操作。Reduce Task過程，數(shù)據(jù)的處理被分成3個階段：復(fù)制、排序和歸并。復(fù)制階段，從磁盤中得到所有map的輸出結(jié)果；排序階段，將map的輸出結(jié)果按某種規(guī)則進行排序；歸并階段，將排序后的數(shù)據(jù)按照用戶自定義的reduce函數(shù)處理。

Hadoop使用0到1之間進度分?jǐn)?shù)來表示任務(wù)的完成情況。在Map階段，進度分?jǐn)?shù)等于已經(jīng)完成的任務(wù)量與輸入的總?cè)蝿?wù)量的比值。在Reduce階段，復(fù)制、排序和歸并3個小階段各占整個Reduce任務(wù)執(zhí)行時間的1/3，在每個小階段，進度分?jǐn)?shù)表示已經(jīng)處理的數(shù)據(jù)量與輸入的總的數(shù)據(jù)量的比值。例如，設(shè)完成Reduce階段總的任務(wù)進度1，當(dāng)一個任務(wù)完成了復(fù)制階段的一半，則任務(wù)的進度分?jǐn)?shù)為，當(dāng)一個任務(wù)完成了排序階段的一半，則任務(wù)的進度分?jǐn)?shù)為。

在MapReduce任務(wù)調(diào)度算法中，用任務(wù)的運行時間、任務(wù)的平均進度和當(dāng)前進度來預(yù)測掉隊者任務(wù)，即當(dāng)活躍任務(wù)的數(shù)量大于1，任務(wù)的平均進度分?jǐn)?shù)減去當(dāng)前進度分?jǐn)?shù)的值大于或等于0.2，且任務(wù)的運行時間超過一分鐘時，則該任務(wù)被視為掉隊者。這種推測算法是基于以下假設(shè)：（1）每一個節(jié)點都是按照同樣的速度處理任務(wù)；（2）在整個運行過程中，每個任務(wù)按照同樣的速率運行；（3）運行后備任務(wù)不消耗系統(tǒng)額外資源；（4）Map階段，用任務(wù)的進度分?jǐn)?shù)表示任務(wù)的完成情況，Reduce階段，任務(wù)的排序、復(fù)制、歸并3個小階段分別占總?cè)蝿?wù)量的1/3。集群的異構(gòu)性使得以上的假設(shè)失效。

集群中的節(jié)點由于配置不同，處理性能不同，總是存在著差異，這些差異影響了Hadoop調(diào)度器的性能。在MapReduce任務(wù)調(diào)度算法中，推測任務(wù)的判定和執(zhí)行都是通過任務(wù)的進度值確定的，但是在異構(gòu)環(huán)境中由于節(jié)點的差異性，用任務(wù)的平均進度分?jǐn)?shù)減去0.2來判斷推測任務(wù)顯的不足。很多任務(wù)的進度都低于這個閾值。例如：假設(shè)異構(gòu)集群中有A、B、C3個節(jié)點，A節(jié)點硬件配置最高，性能很好，B節(jié)點硬件配置中等，性能一般，C節(jié)點硬件配置最差，性能最低。當(dāng)給這個集群中每個節(jié)點分配相同任務(wù)，一段時間后，A節(jié)點的進度為0.9，B節(jié)點的進度為0.5，任務(wù)的平均進度為(0.9+0.5)/2=0.7。此時，Hadoop默認B節(jié)點為慢節(jié)點，則會調(diào)度空閑節(jié)點C啟動推測任務(wù)，由于節(jié)點C性能較低，這個后備任務(wù)完成時間肯定不會在節(jié)點B完成任務(wù)之前完成，因此，這個后備任務(wù)就沒有什么意義。

綜上所述，執(zhí)行后備任務(wù)的推測算法可能在同構(gòu)環(huán)境下比較適用，但是在異構(gòu)環(huán)境下，調(diào)度程序?？赡苓x擇不到正確的后備任務(wù)，造成了過多的后備任務(wù)執(zhí)行，占用了系統(tǒng)大量的資源，影響了系統(tǒng)對任務(wù)的響應(yīng)時間。

2 同構(gòu)環(huán)境下的任務(wù)推測算法

Hadoop默認的推測執(zhí)行調(diào)度策略中設(shè)置一些閾值來判定一個任務(wù)是否是后備任務(wù)。比如，設(shè)置SPECULATIVE_LAP=60*1000，表示后備任務(wù)的運行時間閾值；SPECULATIVE_GAP=0.2，表示后備任務(wù)的進度分?jǐn)?shù)閾值等等。這些閾值的設(shè)置在異構(gòu)環(huán)境下并不準(zhǔn)確。當(dāng)一個任務(wù)請求執(zhí)行時，JobTracker會根據(jù)空閑節(jié)點的心跳請求分配TaskTracker執(zhí)行任務(wù)。如果這些任務(wù)在被處理過程中滿足以上閾值，則會被視為掉隊者任務(wù)，其后備任務(wù)將被執(zhí)行。后備任務(wù)如果被分配到到性能較差的節(jié)點上執(zhí)行，會再次滿足以上閾值，產(chǎn)生第二個后備任務(wù)，造成了系統(tǒng)資源的浪費。由于調(diào)度算法不能根據(jù)系統(tǒng)的負載量動態(tài)的調(diào)整提交的task數(shù)量，這樣就產(chǎn)生了任務(wù)間相互競爭系統(tǒng)資源現(xiàn)象，又由于節(jié)點的處理能力不同，產(chǎn)生的后備任也加入了與已經(jīng)提交的新任務(wù)產(chǎn)生競爭。最終，導(dǎo)致系統(tǒng)負載量過大，不足以快速地完成任務(wù)。為了使后備任務(wù)的推測執(zhí)行更加準(zhǔn)確。可以從兩個方面加以改進，第一是正確判定后備任務(wù)；第二是選取性能較好的節(jié)點執(zhí)行后備任務(wù)。

2.1 任務(wù)執(zhí)行剩余時間預(yù)測算法

對于Hadoop默認調(diào)度策略對后備任務(wù)判定不足的基礎(chǔ)上，提出一種新的判定方法，即把運行時間最久的task作為后備任務(wù)[7]。因此，要判定后備任務(wù)，就必須知道任務(wù)完成的剩余時間。設(shè)Pa表示任務(wù)執(zhí)行的平均速率，T_left表示任務(wù)運行的剩余時間。Pr表示任務(wù)的進度分?jǐn)?shù)，t表示已運行的時間，則Pa=Pr/t，任務(wù)執(zhí)行的剩余進度為1–Pr。用平均速率計算任務(wù)完成的剩余時間[8]，如公式（1）：

用任務(wù)運行開始到當(dāng)前時間的平均值來預(yù)測任務(wù)的剩余完成時間，充分考慮到集群的異構(gòu)性，任務(wù)提交的順序不同運行時間也不同，不會產(chǎn)生后提交的任務(wù)產(chǎn)生新的后備任務(wù)情況。

2.2 快慢節(jié)點判定算法

產(chǎn)生的后備任務(wù)如果運行的速度比原任務(wù)慢，則后備任務(wù)失去了意義。需要選擇一個性能良好的節(jié)點來運行后備任務(wù)。選擇節(jié)點的基本策略是給請求執(zhí)行任務(wù)的節(jié)點按照某一個閾值分為快節(jié)點和慢節(jié)點。閾值設(shè)定為節(jié)點平均進度的25%[8]?？紤]到集群的異構(gòu)性，節(jié)點的平均進度是由整個系統(tǒng)所有節(jié)點上的所有任務(wù)的進度分?jǐn)?shù)決定，這樣就能較為準(zhǔn)確的判定節(jié)點的處理能力和計算性能，達到了準(zhǔn)確地判斷快慢節(jié)點的目的。設(shè)節(jié)點的數(shù)量為n，每個節(jié)點處理的任務(wù)量（已完成和正在完成的task）為m，判斷快慢節(jié)點的閾值為SNT。則有公式（2）：

其中Task[j]表示節(jié)點上的第j個任務(wù)。Hadoop集群可用的系統(tǒng)資源有限，處理后備任務(wù)的能力受到制約。因此，需要計算系統(tǒng)當(dāng)前能夠承載后備任務(wù)的最大值[9]（spectask）?？紤]到集群的異構(gòu)性，可以用在開始到某時刻系統(tǒng)處理Map和Reduce任務(wù)個數(shù)總和減去系統(tǒng)處理任務(wù)個數(shù)的平均值來計算spectask。其計算過程為：設(shè)某時刻T，系統(tǒng)正在處理的Map和Reduce任務(wù)總數(shù)為S1，則有公式（3）：

S1=NmapTask[T]+NreduceTask[T]（3）設(shè)系統(tǒng)從開始時刻到當(dāng)前時刻（T）所處理任務(wù)的平均值為S2，則有公式（4）：

有公式（3）和公式（4）得到公式（5）：

其中NmapTask[T]，NreduceTask[T]分別表示T時刻Map和Reduce階段所執(zhí)行的任務(wù)的數(shù)量。

3 后備任務(wù)推測算法改進

在改進的后備任務(wù)調(diào)度算法中需要定義兩個隊列，一個是存放快節(jié)點信息的隊列（QueueForNode），另一個是存放按剩余完成時間排序的task隊列（QueueForTask）。提交給Hadoop集群的任務(wù)運行一分鐘后，開始選擇后備任務(wù)的運行。改進推測算法中后備任務(wù)的選擇如圖2所示：

圖2 后備任務(wù)的選擇流程圖

后備任務(wù)選擇開始時，由式1計算系統(tǒng)所有正在運行任務(wù)的剩余時間，按照剩余完成時間的大小進行排序并把task存放在QueueForTask隊列中。按照式5計算集群中能夠處理的最大備份任務(wù)數(shù)量，若spectask大于0，將前parseInt((1+20%)*spectask)個任務(wù)按所屬Job的優(yōu)先級排序。parseInt(變量)函數(shù)表示不大于變量的最大整數(shù)，按優(yōu)先級排序是為了使優(yōu)先級高的后備任務(wù)可以先得到執(zhí)行。排完序后，取前spectask個任務(wù)等待執(zhí)行。

為了使備份任務(wù)得到較快執(zhí)行，選取性能良好的快節(jié)點很關(guān)鍵。選取快節(jié)點執(zhí)行流程如圖3所示：

圖3 快節(jié)點選擇執(zhí)行流程圖

當(dāng)JobTracker收到TaskTracker心跳請求時，為了確保系統(tǒng)預(yù)留足夠可用資源，檢查系統(tǒng)中可用的slots（槽）數(shù)量是否大于slots總數(shù)的百分之十。若不滿足條件，忽略節(jié)點請求，否則判斷節(jié)點的任務(wù)進度是否大于閾值（SNT），若不大于，忽略節(jié)點請求，否則將節(jié)點信息加入到快節(jié)點請求隊列（QueueForNode）。將QueueForTask隊列中前Min(QueueForTask.size，spectask)個 任 務(wù) 分 配 給QueueForNode前面的節(jié)點執(zhí)行，QueueForTask.size表示隊列中任務(wù)的數(shù)量，并更新QueueForTask隊列和QueueForNode隊列的信息。

4 實驗設(shè)計及結(jié)果分析

為了實驗方便和計算簡單，采用Hadoop源碼包中自帶的單詞統(tǒng)計實例來測試改進MapReduce任務(wù)調(diào)度算法的性能。實驗原理為：用戶上傳到HDFS的文檔，經(jīng)過map和reduce過程，統(tǒng)計輸出結(jié)果，計算任務(wù)的完成時間，并和原有的任務(wù)調(diào)度算法進行對比。

（1）實驗一由于實驗條件限制，Hadoop集群由三臺異構(gòu)普通PC組成，其組成如表1所示：

表1 集群配置

每臺PC的操作系統(tǒng)為ubuntu14.04，java版本為JDK 1.7.0_65，Hadoop平臺為Hadoop 1.0.0。在此次實驗中，用戶同時提交三個job，每個job的大小為300M，集群中設(shè)定的物理塊（block）塊大小為64M，因此每個job被分成5個Map子任務(wù)。三個job分別在無推測執(zhí)行，Hadoop自帶的推測算法（以Capacity Schedule為例）和改進Hadoop推測算法三種情況下處理，結(jié)果如圖4所示：

圖4 異構(gòu)環(huán)境下推測算法性能比較

由圖4分析，異構(gòu)環(huán)境中，在處理相同任務(wù)量的情況下，無推測算法相比推測算法，作業(yè)的完成的時間長；改進的推測算法比Hadoop自帶的推測算法完成時間短，且隨著job數(shù)量的增加變的明顯。這是因為當(dāng)任務(wù)量過多時，后提交的任務(wù)執(zhí)行的時間較長，產(chǎn)生推測任務(wù)，改進的推測算法通過預(yù)測推測任務(wù)的剩余完成時間，動態(tài)的分配系統(tǒng)資源，使推測任務(wù)得到快速的執(zhí)行，提高了系統(tǒng)處理作業(yè)的性能。

（2）實驗二先后向Hadoop集群中提交4個job，每個job的大小是300M。同時設(shè)置第三次提交的作業(yè)（job3）的優(yōu)先級為HIGH，其余job的優(yōu)先級是NORMAL，在改進的推測算法下，處理任務(wù)的情況，如圖5所示：

圖5 不同優(yōu)先級job完成時間比較

由圖5分析，job3作業(yè)的完成時間最短，job1、job2、job4作業(yè)完成時間依次增加。因為job3的優(yōu)先級大于其它job的優(yōu)先級，在改進推測算法中，優(yōu)先級高的任務(wù)優(yōu)先獲得系統(tǒng)資源，優(yōu)先被執(zhí)行；優(yōu)先級低的job按提交的先后順序依次被執(zhí)行。綜上所述，改進的推測算法能夠較好地處理優(yōu)先級較高的作業(yè)。

5 總結(jié)

針對Hadoop自帶的推測算法對于后備任務(wù)判定的不足，提出了更具公平性的改進Hadoop推測算法。算法通過預(yù)測提交給集群中所有任務(wù)的剩余完成時間，結(jié)合作業(yè)的優(yōu)先級，找到優(yōu)先級較高，可能運行時間較長的任務(wù)，并視為推測任務(wù)。同時，對于異構(gòu)集群中所有節(jié)點處理能力的不同，把節(jié)點分為快慢節(jié)點，并調(diào)用快節(jié)點處理推測任務(wù)，保證了推測任務(wù)得到較快的處理。實驗表明，改進Hadoop推測算法相比原有的推測算法，縮短了任務(wù)完成時間，更好地維持系統(tǒng)的負載平衡，提高了系統(tǒng)處理作業(yè)的能力。

[1]VAQUEROLM,RODEO Merinol,CACERES J,et al.A break in the cloud:Toward a Cloud Definition[J].ACM SIGCOMM Computer Commutitication Review,2009,39(1):50-55.

[2]GUNARAYHNE T and WUTL,QIU,etal.MapReduce in the clouds for sicence:2th IEEE Internation conference on cloud computing Technology and science[C].New York:IEEE Scocienty,2010:565-572.

[3]Tom White.Hadoop權(quán)威指南[M].北京:清華大學(xué)出版社,2011:75-84.

[4]董西成.Hadoop技術(shù)內(nèi)幕[M].北京:機械工業(yè)出版社,2013.5:152-156.

[5]梁建武,周揚.一種異構(gòu)環(huán)境下的Hadoop調(diào)度算法[J].中國科技論文.2012,7(7):495-500.

[6]劉鵬.實 戰(zhàn)Hadoop[M].北京:電 子 工業(yè)出 版社,2011:60-62.

[7]MateiZaharia,Andy Konwinski,Anthony D Joseph. Improving MapReduce Performancein Heterogeneous Environments[C].8thUSENIX Symposium on Operating System Design and Implementation,2009:29-42.

[8]余影,吳斌.基于Hadoop的大規(guī)模數(shù)據(jù)交換的研究[D].北京:北京郵電大學(xué),2011.

[9]何文峰,王多強.基于任務(wù)特征和公平策略的Hadoop作業(yè)調(diào)度算法研究[D].武漢:華中科技大學(xué),2013:40-50.

AMapRuducetask Scheduling Mechanism in Heterogeneous Environment

Wei Wei,Liu Zhaoyuan
(School of Computer Science and Technology,Xi’an University of Posts and Telecommunications,Xi’an710061,China)

As the world's leading data platform,Hadoop’s performance deeply depends on the MapReduce scheduling mechanism. In this paper,through a speculative algorithm research on MapReduce scheduling mechanism,an efficient,accurate and priority-based advanced Hadoop scheduling mechanism algorithm is proposed.This algorithm can make exactly judgment to backward task in heterogeneous environment by testing.It maintains the balance of the system load better and reduces the system response time to the tasks.The algorithm also improves the response speed to the tasks of high priority and the performance of MapReduce scheduling mechanism.

Heterogeneous Environment;Speculative Algorithm;Load Balancing;Priority

TP338

A

1007-757X(2015)06-0055-04

2014.12.31）

魏 巍（1988-），男，漢族，河南信陽，西安郵電大學(xué)，碩士研究生，研究方向：計算機應(yīng)用技術(shù)，西安，710061

劉釗遠（1963-），男，漢族，陜西銅川，西安郵電大學(xué)，教授，研究方向：嵌入式系統(tǒng)應(yīng)用研究，西安，710061