陳明麗， 劉旭敏

(首都師范大學(xué) 信息工程學(xué)院,北京 100048)

Hadoop平臺下改進的推測任務(wù)調(diào)度算法*

陳明麗， 劉旭敏

(首都師范大學(xué) 信息工程學(xué)院,北京 100048)

研究對比Hadoop平臺下默認的推測任務(wù)調(diào)度算法和異構(gòu)環(huán)境下LATE調(diào)度算法的優(yōu)勢和不足，提出了一種基于Hadoop集群的改進的推測任務(wù)調(diào)度算法。該算法以節(jié)點歷史信息對Reduce任務(wù)各階段比例進行動態(tài)調(diào)整和更新，并對任務(wù)實時處理速率進行局部平滑處理來提高預(yù)估任務(wù)剩余完成時間的準(zhǔn)確性，最后采用MCP模型對備份任務(wù)有效性進行驗證。通過實驗結(jié)果分析可知:該算法能夠有效提升備份任務(wù)成功率，減少作業(yè)完成時間。

MapReduce; 異構(gòu)環(huán)境; 推測執(zhí)行; LATE

0 引 言

隨著信息量的指數(shù)級增長，使得云計算[1]這一新的商業(yè)計算模式得到了迅速發(fā)展，以Hadoop[2]為代表的開源云平臺被廣泛應(yīng)用于機器學(xué)習(xí)、數(shù)據(jù)挖掘、統(tǒng)計分析等海量數(shù)據(jù)處理場景[3]。其中，MapReduce[4]編程調(diào)度模型正是Hadoop平臺的核心成分。

Hadoop原有調(diào)度器在異構(gòu)集群下由于資源差異化致使作業(yè)執(zhí)行效率低下，為解決Hadoop默認推測調(diào)度策略的不足，LATE調(diào)度算法[5]通過為剩余完成時間最長的任務(wù)提供備份任務(wù)來改善集群異構(gòu)環(huán)境下的計算性能。文獻[6]針對LATE算法的不足提出了LATE-VPR算法，以實時任務(wù)處理速率預(yù)估任務(wù)完成時間，來提高Map階段落后任務(wù)判斷的準(zhǔn)確性。文獻[7]依據(jù)任務(wù)處理速率增大和減小的比例來動態(tài)調(diào)整集群節(jié)點的任務(wù)槽點數(shù)，通過優(yōu)化不同性能節(jié)點的任務(wù)分配來減少落后任務(wù)。然而，以上各調(diào)度算法均未考慮備份任務(wù)的有效性，若備份任務(wù)無法在落后任務(wù)之前完成，將無法達到優(yōu)化目的。

本文針對以上情況，提出以下解決方案：第一，以歷史信息對Reduce任務(wù)各階段比例進行更新和調(diào)整，更加準(zhǔn)確地找到Reduce落后任務(wù)；第二，根據(jù)集群負載和節(jié)點處理速率預(yù)估備份任務(wù)執(zhí)行時間，僅對可提高任務(wù)完成時間的落后任務(wù)執(zhí)行備份任務(wù)，提高推測執(zhí)行的有效性。通過實驗驗證表明，本文方法在預(yù)測成功率和優(yōu)化作業(yè)完成時間兩方面均較Hadoop和LATE算法有所提升和改善。

1 相關(guān)工作分析

1.1 Hadoop默認推測調(diào)度算法

在MapReduce框架中，多個任務(wù)并行計算，作業(yè)完成時間以最終任務(wù)完成時間為準(zhǔn)。當(dāng)部分任務(wù)由于資源異構(gòu)等問題執(zhí)行效率低下，遠遠落后于作業(yè)平均處理進度，將會影響系統(tǒng)性能。此類任務(wù)稱之為落后任務(wù)(straggler)。為避免此類情況發(fā)生，Hadoop會為其執(zhí)行備份任務(wù)，讓落后任務(wù)與備份任務(wù)同時運行，以先完成的運行結(jié)果為準(zhǔn)。Hadoop將以上優(yōu)化策略命名為推測執(zhí)行(speculation execution)。在Hadoop默認推測調(diào)度算法中，落后任務(wù)是依據(jù)任務(wù)處理進度值和作業(yè)平均處理進度值的差值來判斷，落后作業(yè)平均處理進度值20 %以上的任務(wù)即被判定為落后任務(wù)，需要為其啟動備份任務(wù)。

Hadoop默認推測調(diào)度算法存在如下假設(shè)：

1)各計算節(jié)點計算能力相同；

2)任務(wù)處理進度值線性增長，Reduce任務(wù)三階段Co-py,Sort,Reduce用時各占1/3；

3)啟動備份任務(wù)所產(chǎn)生的時間和資源消耗可忽略不計。

但在實踐環(huán)境中，異構(gòu)集群各節(jié)點執(zhí)行效率差異較大；任務(wù)處理速率因作業(yè)特性、集群配置等原因各有不同，且不同批次的任務(wù)在同一時間比較進度值可能導(dǎo)致處理速率較快的后期任務(wù)被判定為落后任務(wù)；集群資源為各作業(yè)任務(wù)共享，備份任務(wù)執(zhí)行必然導(dǎo)致任務(wù)間資源競爭。

1.2 LATE推測調(diào)度算法

為了能夠更加準(zhǔn)確地找到落后任務(wù)，文獻[5]提出新的LATE(longest approximate time to end)調(diào)度算法，該算法利用任務(wù)平均處理速率來預(yù)估任務(wù)剩余完成時間，選取最大的任務(wù)啟動備份任務(wù)。同時，增設(shè)多個配置選項，以便識別出快節(jié)點和慢節(jié)點，并將新啟動備份任務(wù)分配給快節(jié)點，從而保證備份任務(wù)執(zhí)行速度。

由于LATE算法同Hadoop調(diào)度算法一樣采用靜態(tài)方式計算任務(wù)進度，可能使得估算不準(zhǔn)確導(dǎo)致部分正常任務(wù)被誤認為是落后任務(wù)，造成資源浪費。盡管LATE算法可通過任務(wù)執(zhí)行速率識別出慢節(jié)點，但未分別針對Map任務(wù)和Reduce任務(wù)做更細的識別。而在實際應(yīng)用中，一些節(jié)點對于Map任務(wù)而言是慢節(jié)點，但對Reduce任務(wù)則是快節(jié)點。

2 改進的推測調(diào)度算法

本文在充分分析以上各算法的優(yōu)勢和不足后，從以下兩方面對推測任務(wù)調(diào)度算法進行改進：其一是落后任務(wù)判斷準(zhǔn)確性，唯有真正的落后任務(wù)才有執(zhí)行備份任務(wù)的必要；其二是備份任務(wù)分配有效性，集群負載、備份節(jié)點性能、落后任務(wù)的處理進度等都關(guān)系到備份任務(wù)能否優(yōu)先完成，以便縮短整體作業(yè)完成時間。

2.1 落后任務(wù)判定方法

異構(gòu)環(huán)境下的Hadoop集群，各節(jié)點的CPU、I/O、帶寬等差異均可能導(dǎo)致不同節(jié)點任務(wù)完成時間不同。但在某一特定節(jié)點上，上述資源基本能夠保持長期不變，相同類型的任務(wù)在處理過程中具有一致性。不同作業(yè)類型面對Reduce任務(wù)各階段并非以固定比例1/3進行，無法準(zhǔn)確預(yù)估任務(wù)處理進度。本文依據(jù)作業(yè)歷史信息動態(tài)調(diào)整Reduce任務(wù)各階段在總進度中所占比例。首先，TaskTracker獲取本地節(jié)點歷史信息；其次，根據(jù)Reduce任務(wù)各階段完成時間占任務(wù)總體完成時間的比例設(shè)置各階段比例參數(shù)R1、R2、R3，滿足R1+R2+R3=1；最后，當(dāng)任務(wù)完成后將任務(wù)各階段消耗時間的比例寫入本地。

采用線性模型計算各階段進度值，任務(wù)各階段采用已處理數(shù)據(jù)量M占總數(shù)據(jù)量N的比例來表示。對于Map任務(wù)，作為大的任務(wù)階段不可分解，當(dāng)前時刻t=now任務(wù)處理進度值為PSnow=M/N；對于Reduce任務(wù)，不同階段的處理進度值分別為

Copy:PSnow=R1×(M/N)

Sort:PSnow=R1+R2×(M/N)

Reduce:PSnow=R1+R2+R3×M/N

由于任務(wù)在執(zhí)行過程中處理速率不斷變化，采用平均處理速率PSnow/t無法準(zhǔn)確反映任務(wù)處理現(xiàn)狀，故采用局部平滑處理的方法計算任務(wù)處理速率PR，計算方法如式(1)～式(3)所示

PSt=PS0，PSd，PS2d，…,PSnow-d，PSnow

(1)

prt=(PSt-PSt-d)/d

(2)

(3)

式中d為心跳間隔。

假設(shè)一個作業(yè)當(dāng)前正在運行的Map/Reduce任務(wù)數(shù)為n，平均Map/Reduce任務(wù)處理速率為

(4)

當(dāng)Map/Reduce任務(wù)處理速率PR與集群Map/Reduce任務(wù)平均處理速率avgPR的差距滿足式(5)時，判定該任務(wù)為Map/Reduce慢任務(wù)

avgPR-PR>SlowTaskThre×δ

(5)

式中SlowTraskThre為慢任務(wù)閾值，δ為所有任務(wù)進度增長率標(biāo)準(zhǔn)方差。

2.2 落后節(jié)點判定方法

由于異構(gòu)環(huán)境下不同節(jié)點掌握的資源不同，同時受任務(wù)執(zhí)行過程中資源變化的影響，可能存在某節(jié)點Map任務(wù)處理速率較低但Reduce任務(wù)處理速率較高的情況。為了更好的實現(xiàn)優(yōu)化，需要將不同類型的備份任務(wù)分配到對應(yīng)類型的快節(jié)點執(zhí)行。

假設(shè)某計算節(jié)點的Map任務(wù)數(shù)為m(包含已完成任務(wù)數(shù)和正在運行任務(wù)數(shù))，Reduce任務(wù)數(shù)為n(包含已完成任務(wù)數(shù)和正在運行任務(wù)數(shù))，系統(tǒng)集群計算節(jié)點數(shù)為N，則該計算節(jié)點Map任務(wù)與Reduce任務(wù)的處理速率NRM,NRR和系統(tǒng)集群Map任務(wù)與Reduce任務(wù)的平均處理速率avgNRM,avgNRR計算公式如下

(6)

(7)

(8)

(9)

若某計算節(jié)點Map/Reduce任務(wù)處理速率與集群Map/Reduce任務(wù)平均處理速率的差距滿足式(10)，則判定該計算節(jié)點為Map/Reduce慢節(jié)點。

avgNR-NR>SlowNodeThre×δ

(10)

式中SlowNodeThre為慢節(jié)點閾值，δ為所有任務(wù)進度增長率標(biāo)準(zhǔn)方差。

2.3 有效推測任務(wù)調(diào)度算法

剩余時間較長的任務(wù)影響作業(yè)完成時間，卻并非都值得執(zhí)行備份。如何避免備份任務(wù)晚于落后任務(wù)完成最終被殺掉，取決于備份節(jié)點的任務(wù)處理速率。預(yù)估任務(wù)剩余完成時間ETE為

ETE=(1-PS)/PR

(11)

備份任務(wù)完成時間STE為

STE=1/NR

(12)

備份任務(wù)不僅僅是通過提前完成任務(wù)使得集群獲益，也需要占用集群資源。為了確保推測執(zhí)行的有效性，最大化資源開銷性能，本文采用MCP模型[8]對落后任務(wù)作進一步篩選，滿足式(13)的落后任務(wù)方能啟動備份任務(wù)

ETE/STE>(1+2γ)/(1+γ)

(13)

γ=pending_tasks/free_slots

(14)

式中γ為集群的負載因子，pending_tasks為排隊等待的任務(wù)數(shù)，free_slots為集群空閑槽點數(shù)。

2.4 改進算法的執(zhí)行流程

JobTracker接收各TaskTracker所發(fā)送心跳信息，當(dāng)某TaskTracker出現(xiàn)空閑槽點且無失敗任務(wù)和未分配任務(wù)，開始執(zhí)行以下推斷算法：

1)判斷TaskTracker是否為慢節(jié)點；

2)計算正在執(zhí)行任務(wù)的處理速率和剩余時間，依此篩選出慢任務(wù)，加入慢任務(wù)隊列并以剩余時間排序；

3)選出剩余時間最長的慢任務(wù)，根據(jù)任務(wù)類型預(yù)估在TaskTracker執(zhí)行備份任務(wù)的完成時間，由MCP模型判斷是否為有效推斷；

4)為滿足MCP模型的落后任務(wù)在TaskTracker啟動備份任務(wù)。

只有當(dāng)TaskTracker并非Map慢節(jié)點時方能為Map慢任務(wù)啟動備份任務(wù)，Reduce任務(wù)同理。

3 實驗驗證與結(jié)果分析

本文所采用實驗環(huán)境是由5臺PC機通過虛擬機的方式搭建而成的異構(gòu)集群。所有虛擬機均使用VMware 10.0.0 安裝Ubuntu12.04操作系統(tǒng)，JDK版本為1.8.0_65，Hadoop版本為1.2.1。每份數(shù)據(jù)有兩個副本，每個TaskTracker分別分配兩個Map任務(wù)槽和兩個Reduce任務(wù)槽。

測試用例為Sort和WordCount，數(shù)據(jù)來源是由RandomWriter自動生成。執(zhí)行測試用例時，通過統(tǒng)計各推測調(diào)度算法在相同條件下執(zhí)行測試用例所需完成時間來對算法進行性能對比和評估。每個測試作業(yè)各執(zhí)行5次，單個作業(yè)輸入數(shù)據(jù)為4 G。

為了驗證推測任務(wù)調(diào)度算法的有效性，本文通過對Sort作業(yè)下備份任務(wù)和成功任務(wù)數(shù)進行比較。表1展示了不同調(diào)度算法對備份任務(wù)成功率的影響，表中的任務(wù)數(shù)是5次重復(fù)實驗的總和。如表1所示，ELATE算法的備份任務(wù)數(shù)比較Hadoop和LATE算法有所下降，正是由于改進算法通過更加準(zhǔn)確的任務(wù)進度判定和備份任務(wù)判定策略，避免了部分不必要的備份任務(wù)，從而提高了備份任務(wù)成功率，同時也降低了任務(wù)的最大完成時間，有助于更加有效地利用集群資源。

表1 Sort作業(yè)推測結(jié)果對比

調(diào)度算法BackupMBackupRSuccMSuccRHadoop4013187LATE4112268ELATE379318

所有推測優(yōu)化的終極目的是縮短作業(yè)完成時間，圖1通過對不同調(diào)度算法下Sort作業(yè)完成時間進行對比分析。從圖中可以看出，相較于Hadoop默認推斷算法，LATE調(diào)度算法可減少作業(yè)執(zhí)行時間約15 %，改進后的ELATE調(diào)度算法可減少作業(yè)執(zhí)行時間約23 %，進一步驗證了改進算法的有效性。

圖1 Sort作業(yè)完成時間對比

針對WordCount作業(yè)，各調(diào)度算法的完成時間如圖2所示。ELATE算法作業(yè)完成時間與Hadoop和LATE算法相差不大。由于WordCount作業(yè)主要時間開銷用于Map階段對輸入數(shù)據(jù)的處理，作業(yè)性能由Map任務(wù)完成時間主導(dǎo)。ELATE算法對Reduce階段的優(yōu)化無法有效開展，使得系統(tǒng)對此類作業(yè)性能空間提升有限。

圖2 WordCount作業(yè)完成時間對比

4 結(jié)束語

本文針對Hadoop默認推測任務(wù)調(diào)度算法的不足，結(jié)合已有LATE算法的基礎(chǔ)上，提出了改進的ELATE算法。該算法采用更加準(zhǔn)確的任務(wù)進度和剩余時間預(yù)估方法，并引入MCP模型對推斷有效性進行預(yù)判。實驗結(jié)果顯示ELATE算法能夠有效提高備份任務(wù)成功率，縮短作業(yè)完成時間，實現(xiàn)系統(tǒng)性能優(yōu)化。下一步研究將從優(yōu)化集群資源配置角度出發(fā)，以期從源頭上減少落后任務(wù)的產(chǎn)生。

[1] Vaquero L M,Rodero-Merino L,Caceres J,et al.A break in the clouds: Towards a cloud definition[J].ACM SIGCOMM Compu-ter Communication Review,2009,39(1):50-55.

[2] Apache Hadoop[EB/OL].[2016—01—15].http:∥hadoop.apache.org/.

[3] 劉東平,馬利亞,楊 軍.云環(huán)境下異構(gòu)無限傳感器網(wǎng)絡(luò)節(jié)點調(diào)度算法改進算法[J].傳感器與微系統(tǒng),2015,34(10):128-132.

[4] Dean J,Ghemawat S.MapReduce: Simplified data processing on large cluster[C]∥Proc of the 6th Symposium on Operating Systems Design and Implementation,San Francisco: Google Inc,2004.

[5] Zaharia M,Konwinski A,Joseph A D.Improving MapReduce performance in heterogeneous environments[C]∥Proc of the 8th Conference on Operating Systems Design and Implementation,2008:29-42.

[6] Lin Chi Yi,Chen Ting Hau,Cheng Yi No.On improving fault tolerance for heterogeneous Hadoop MapReduce clusters[C]∥Proc of the 2013 International Conference on Cloud Computing and Big Data,2013:38-43.

[7] Zhao Xia,Kang Kai,Sun Yuzhong,et al.Insight and reduction of MapReduce stragglers in heterogeneous environment[C]∥Proc of the 15th IEEE International Conference on Cluster Computing,2013.

[8] Chen Qi,Liu Cheng,Xiao Zhen.Improving MapReduce perfor-mance using smart speculative execution strategy[J].IEEE Transactions on Computers,2014,63(4):954-967.

Improved speculative task scheduling algorithm on Hadoop platform*

CHEN Ming-li, LIU Xu-min

(College of Information Engineering,Capital Normal University,Beijing 100048,China)

After compare and analysis the advantage and disadvantage of the default speculative task scheduling algorithm on the Hadoop platform and LATE scheduling algorithm in heterogeneous environment,an improved speculative task scheduling algorithm based on Hadoop computer cluster is proposed.The algorithm dynamically adjusts and updates the proportion of stages in the Reduce task based on node history information,smoothes the real-time task progress rate to improve the forecast accuracy of the remaining completion time,and applies MCP model to verify the effectiveness for backup task.The experiment analysis show that the algorithm can improve the success rate of backup task and reduce job completion time.

MapReduce; heterogeneous environment; speculation execution; LATE

10.13873/J.1000—9787(2017)02—0134—04

2016—03—12

國家自然科學(xué)基金資助項目(61272029)

TP 393

A

1000—9787(2016)02—0134—04

陳明麗(1991-)，女，碩士研究生，主要研究方向為云計算。