Hadoop平臺下改進的推測任務調度算法*

陳明麗， 劉旭敏

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

Hadoop平臺下改進的推測任務調度算法*

陳明麗， 劉旭敏

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

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

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

0 引 言

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

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

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

1 相關工作分析

1.1 Hadoop默認推測調度算法

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

Hadoop默認推測調度算法存在如下假設：

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

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

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

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

1.2 LATE推測調度算法

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

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

2 改進的推測調度算法

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

2.1 落后任務判定方法

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

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

Copy:PSnow=R1×(M/N)

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

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

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

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

(1)

prt=(PSt-PSt-d)/d

(2)

(3)

式中d為心跳間隔。

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

(4)

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

avgPR-PR>SlowTaskThre×δ

(5)

式中SlowTraskThre為慢任務閾值，δ為所有任務進度增長率標準方差。

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

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

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

(6)

(7)

(8)

(9)

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

avgNR-NR>SlowNodeThre×δ

(10)

式中SlowNodeThre為慢節(jié)點閾值，δ為所有任務進度增長率標準方差。

2.3 有效推測任務調度算法

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

ETE=(1-PS)/PR

(11)

備份任務完成時間STE為

STE=1/NR

(12)

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

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

(13)

γ=pending_tasks/free_slots

(14)

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

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

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

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

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

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

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

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

3 實驗驗證與結果分析

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

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

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

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

調度算法BackupMBackupRSuccMSuccRHadoop4013187LATE4112268ELATE379318

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

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

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

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

4 結束語

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

[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)境下異構無限傳感器網絡節(jié)點調度算法改進算法[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

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

TP 393

A

1000—9787(2016)02—0134—04

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