異構環境下增強的自適應MapReduce調度算法

楊立身，余麗萍

河南理工大學計算機科學與技術學院，河南焦作 454000

異構環境下增強的自適應MapReduce調度算法

楊立身，余麗萍

河南理工大學計算機科學與技術學院，河南焦作 454000

1 引言

MapReduce[1]是一個編程模型，也是一個處理和生成超大數據集的算法模型的相關實現。Hadoop[2]是MapReduce的開源實現，它不僅廣泛應用于批量大作業同時也用于處理相應低效率的短作業。MapReduce的一個關鍵的優勢是它能夠自動處理故障，隱藏容錯的復雜性，對用戶完全透明。如果一個節點崩潰，MapReduce將其運行的任務分配給其他節點繼續運行[3]。更重要的是如果節點可用但是其性能低下時，稱低性能機器上處理的任務為掉隊者，MapReduce會在另外一個節點運行一個推測執行任務，以更快地完成計算，該機制稱為推測執行機制[4-5]。現有的Hadoop調度算法都是建立在同構集群的假設前提下的，并使用這些假設決定何時推測式地執行落后隊列的任務，但是這種同構的假設在實踐中是行不通的。

目前，要解決的問題是如何高效地通過運行推測執行機制將系統性能最大化。國外學者針對此現象提出了多種改進方法。文獻[6]提出了LATE調度算法，核心思想是基于一個異構環境，使用靜態的方法去計算任務的進度，對系統性能的提升效果甚微。文獻[7-8]針對LATE調度算法的不足提出了SAMR調度算法，核心思想是基于歷史信息動態地調整Map和Reduce任務各階段的時間比例，找到真正需要啟動備份任務的執行任務。以上幾種算法都未考慮作業類型、數據集的大小對任務進度值的影響，因此并不能最大化地提高系統的性能。

本文針對以上算法進行改進，在SAMR算法的基礎上提出了一個增強的自適應K-SAMR調度算法。考慮到其他影響任務進程的因素，該算法記錄了每個節點的歷史信息并采用K-means聚類算法動態地調整階段進度值參數，準確地查找慢任務。并將慢節點分為Map任務慢節點和Reduce慢節點，有效地提高了系統資源利用率。

2 研究現狀分析

2.1 Hadoop默認調度器

Hadoop默認的調度器[9]通過任務進度值Progress Score對推測執行任務進行選擇，常使用0到1之間的值來標識每個任務的進度。由AvgProgress來表示每個作業的平均進度值，Progress Score[i]表示第i個任務的任務進度值。設定已經處理完成的任務條數為M，總共需要處理的任務條數N，所處的階段的序列號為K，任務數量為P。Hadoop默認調度算法首先根據公式（1）和公式（2）獲得PS的值，然后根據公式（3）判斷任務是否為落后任務，并在另一個快節點上執行該任務的后備任務。

文獻[10]指出該調度器的主要缺陷：首先，Hadoop默認調度器使用固定的階段進度值M1=1，M2=0，R1=R2=R3=1/3，該方式沒有考慮集群節點的異構性，在現實環境中會造成任務進度估計的失真。其次，Hadoop默認調度器根據任務進度值來啟動備份任務是不合理的，該方式沒有考慮異構環境下不同節點執行任務的速率之間的差異性。最后，Hadoop默認調度器可能啟動不必要的備份任務。

2.2 LATE調度器

LATE調度器[11]通過重啟剩余時間最長任務的備份任務來解決默認調度器的不足，假設任務已經運行的時間為Tr，任務的處理速度為ProgressRate，任務的最長剩余完成時間為TTE。LATE調度算法首先利用公式（1）計算任務的進度值PS，然后利用公式（4）和（5）計算任務的最長剩余完成時間：

盡管LATE選取剩余時間最長的任務去啟動備份任務，但它仍然頻繁地選擇錯的任務去備份。這是因為LATE調度算法仍然使用Hadoop默認調度算法的設定，并且未區分Map慢節點和Reduce慢節點，導致LATE調度算法對任務的剩余時間的估計不精確。

2.3 SAMR調度器

圖1 在SAMR調度器中使用和更新歷史信息

SAMR調度器通過估計任務執行時間來識別慢任務，但不采用固定的階段進度值。如圖1所示，當SAMR調度器估計一個節點上正運行任務的剩余時間時，它存儲每個節點上的階段進度值，讀取存儲在節點上的歷史信息然后動態地設置階段進度值。由于SAMR采用歷史信息記錄每個節點的階段取值更貼近實際，因此，相對于Hadoop默認調度器、LATE調度器，SAMR調度器更能夠適用于異構環境。

SAMR只考慮影響任務階段進度值的其中一個因素，沒有考慮在同一個節點上運行不同MapReduce作業的任務可以有不同的階段進度值。原因是當執行不同MapReduce作業時，執行Map和Reduce階段花費的時間不同，并且它們產生的大量中間數據也不同。另外，當處理大小不同的數據集時，相同的MapReduce作業的任務也會有不同的階段進度值。例如，大的輸入數據集會造成大的中間數據，這些將導致其需要花費更多的時間在Shuffle階段[12]。

本文提出的K-SAMR算法是一個增強的自適應MapReduce調度算法。除了考慮硬件異構性的因素以外，還考慮了其他影響任務階段進度值的因素。因此，K-SAMR算法在記錄每個節點上歷史信息的同時采用K-means聚類算法動態調整階段進度值，估計任務的執行時間，查找慢任務。

3 K-SAMR調度器

3.1 K-SAMR算法的基本思想

K-SAMR算法使用機器學技術把存儲在每個節點上的歷史信息歸類為K個聚蔟。如果正在運行的作業的Map任務完成量達到閥值PFM，K-SAMR算法將根據節點上完成的Map任務記錄作業的臨時Map階段進度值M1。臨時進度值M1用于查找與進度值M1最接近的聚蔟。然后，K-SAMR用聚蔟的階段進度值估計節點上作業的Map任務的剩余完成時間，分析需要被重新執行的慢任務。如果正在運行的作業已經完成節點上所有的Map任務，那么所有K聚蔟的階段進度值的平均值將被用于整個作業。在Reduce階段，K-SAMR執行類似的進程。一個作業完成之后，K-SAMR計算每個節點的作業的階段進度值，并保存這些新的進度值作為歷史信息的一部分。最終，K-SAMR利用K-means聚類算法和機器學技術重新去歸類存儲在每個工作節點上的歷史信息，并保存每個K聚蔟更新后的平均階段進度值。通過利用更精確的階段進度值來估計正在運行任務的剩余時間，和另外三種算法相比，K-SAMR算法能更準確地識別慢任務，K-SAMR具體算法如下：

3.2 Map任務完成的比例（PFM）和Reduce任務完成的比例（PFR）

K-SAMR調度算法利用PFM和PFR決定何時去計算臨時階段進度值。假設N代表一個集群中TaskTrackers的全部數量，FM代表一個作業中Map任務的總數量，FM[i]代表第i個TaskTracker中Map任務完成的數量，TR代表一個作業中Reduce任務的全部數量，FR[i]代表第i個Task-Tracker中Reduce任務的完成數量。當公式（5）和（6）滿足條件時，K-SAMR算法才能計算每個作業的Map和Reduce階段的臨時進度值。

3.3 使用歷史信息和臨時信息

K-SAMR算法首先計算臨時階段進度值，然后同歷史記錄信息進行比較，最后找出適合作業階段進度值的最佳組合。圖2展示了在K-SAMR算法中使用Map臨時信息和歷史信息的方式；圖3展示了在K-SAMR中使用Reduce臨時信息和歷史信息的方式。

圖2 使用Map臨時信息和歷史信息的方法

圖3 使用Reduce臨時信息和歷史信息的方法

具體步驟如下：

（1）JobTracker首先查看PFM是否達到閥值。如果達到，K-SAMR算法將計算每個節點上Map任務完成的階段進度值，并生成一個臨時文件MapWeight來記錄臨時階段進度M1。

（2）每個TaskTracker從本地節點讀取歷史信息（M1，M2，R1，R2，R3）。

（3）K-SAMR算法將歷史信息與存儲在臨時文件Map Weight里面的信息進行比較。在Map階段，K-SAMR算法將M1與K個歷史信息聚簇中的平均結果進行比較，并找到最接近進度值的聚蔟的中心蔟，同時設置M1作為該組的平均結果；M2=1-M1。

（4）K-SAMR利用新的Map階段進度值計算出正在執行的任務的速度和剩余時間，并判斷出哪些是慢任務。

（5）在Reduce階段中，K-SAMR首先查看PFR是否達到閥值。如果達到閥值，K-SAMR算法將計算每個節點上完成Reduce任務的階段進度值，并生成一個臨時文件ReduceWeights去記錄臨時進度值R1和R2。K-SAMR算法將R1和R2與K個歷史信息聚簇中的平均結果進行比較，并找到最接近進度值的組，同時設置R1和R2作為該組的平均結果；R3=1-R1-R2。

（6）K-SAMR利用Reduce階段進度值計算出正在執行的任務的速度和剩余時間，并判斷出哪些是慢任務。

（7）當一個作業完成時，K-SAMR計算作業的所有Map和Reduce任務階段的平均值，同時生成一個新的階段進度值的聚簇作為歷史信息的一部分。

（8）K-SAMR運用K-means算法去重新歸類階段進度的聚蔟，并且存儲重新歸類的歷史信息。

3.4 慢任務探索算法

STT代表一個閥值，它用來判斷一個任務是否為慢任務。假設第i個任務的剩余時間為TTEi，所用任務的剩余時間為ATTE，一個作業當前正在運行的Map數量和當前正在運行的Reduce數量是N。如果滿足公式（8）和（9），則第i個任務被判斷為慢任務。

根據公式（8）可得：如果STT太小以至于接近0，那么將會誤判快的任務為慢的任務；如果STT太大以至于接近1，那么就發現不了慢的任務，從而不能啟動備份任務。因此，需要去選擇一個合適的STT的慢任務。

3.5 慢節點探索算法

SNT代表一個閥值，它用來判斷一個任務是否為慢節點，假設系統中有N個TaskTrackers，第i個TaskTracker的節點Map任務的進度率為TRmi，Reduce階段的進度率為TRri，平均進度率是為ATRm、ATRr。如果有M個Map任務和R個Reduce任務運行在第i個TaskTracker節點上，TRmi、TRri、ATRm、ATRr的計算公式如下：

對于第i個TaskTracker如果滿足式（14），它是一個慢的Map TaskTracker，如果滿足式（15），它就是一個慢的Reduce TaskTracker。

需要通過大量的實驗來確定SNT的值。如果SNT取值太小，那么將會把一些正常的TaskTracker誤判為慢Task-Tracker；如果SNT取值過大，則將會把一些慢的TaskTracker誤判為正常TaskTracker。只有當申請任務的TaskTracker不是掉隊者時，它才把慢的任務的后備任務交給該Task-Tracker執行。

3.6 K-means算法在K-SAMR中的應用

在統計和數據挖掘方面，K-means聚類算法是一種聚類分析方法[13]。K-means聚類算法的主要目標是將一個數據集劃分為若干個聚簇，使聚簇內的對象盡可能相似，而類之間盡可能相異。

在K-SAMR中的K-means聚類算法的步驟為：（1）K-SAMR任意選擇K個樣本作為聚簇初始的中心點；（2）根據每個聚簇的中心坐標，把每個樣本分配給距離其最近的聚簇；（3）更新聚簇的中心點坐標，即計算每個聚簇中所有樣本的均值；（4）不斷重復（2）、（3）步驟直至收斂。圖4給出了K-means算法在K-SAMR中的使用流程圖。

圖4 K-SAMR中的K-means算法流程圖

4 實驗結果及性能分析

本文利用異構環境下已有的兩種改進算法SAMR和LATE算法與K-SAMR算法相比較。在這三種調度算法的基礎上改寫Hadoop默認調度器，在新的三種調度器上，運行Hadoop自帶的基準測試程序WordCount去評估算法的性能。

首先搭建有6臺普通PC機組成的集群，其中1臺為主節點，5臺為工作節點，它們運行在同一個機架上。表1列出了集群的硬件環境和配置。其次設置合適的參數，提高系統的效率。實驗設置了4個文獻[6]中已經論證的最佳參數值，如下：PFM設置為20%，PFR設置為20%，K設置為10，STT設置為40%。其中，相同的PFM、PFR、STT參數值也應用于設置算法SAMR和LATE。HP對于SAMR算法是一個重要的配置，文獻[8]表明HP為0.2時SAMR達到最佳的性能，所以把HP的值設置為0.2。最后，通過三個方面驗證K-SAMR算法的性能：估計階段進度值的能力；估計剩余時間的能力；鑒別慢任務的能力。

表1 Hadoop集群的硬件環境和配置

4.1 估計階段進度值的能力

為了驗證通過K-SAMR算法估計的Map和Reduce階段進度值的準確性，對比表2和表3可以發現，通過K-SAMR算法估計Map和Reduce各階段進度值和從系統收集的Map和Reduce階段實際的階段進度值相差不大，但是其與利用固定階段進度值的LATE算法的結果相差很大；并且，通過SAMR算法估計的結果和從系統收集來的實際進度值之間的差值，比采用K-SAMR算法獲得的進度值大得多。

表2 K-SAMR算法與真實進度值的比較

表3 SAMR算法與真實進度值的比較

4.2 估計剩余時間的能力

圖5 Map任務剩余時間估計誤差（WordCount 10 GB）

圖6 Reduce任務剩余時間估計誤差（WordCount 10 GB）

圖7 Map任務執行時間

為了驗證算法估計任務剩余時間的準確性，首先，通過運行10次WordCount程序來比較三個MapReduce調度算法的任務剩余時間；其次，分別設置PFM的值為20%，PFR的值為20%，K的值為10，STT的值為40%，SNT的值為30%；最后，比較三種調度策略的剩余時間估計誤差。圖5和圖6分別顯示了通過K-SAMR、SAMR、LATE算法運行1個10 GB大小的WordCount作業時，Map和Reduce階段的剩余時間估計誤差。一個作業有100個Map任務和20個Reduce任務，由于20個Map任務已經足夠去說明差異，為了方便起見選取100個Map任務中的前20個Map任務，選取全部Reduce任務。在三種算法中，K-SAMR算法導致最小的估計誤差。使用K-SAMR算法估計Map和Reduce任務剩余時間和真實的剩余時間的差異，分別小于4 s和5 s。使用SAMR算法估計Map和Reduce任務剩余時間和真實的剩余時間的差異，分別小于38 s和37 s。使用LATE算法估計Map和Reduce任務剩余時間和真實的剩余時間的差異，分別小于64 s和129 s。

4.3 鑒別慢任務的能力

為了驗證算法鑒別Map掉隊任務的能力，將K-SAMR、SAMR、LATE三個調度算法執行Map任務的時間與真實執行時間相互對比，從圖7可以看到，K-SAMR選擇第8個和第9個的Map任務為最慢的任務，SAMR選擇第10個Map任務為最慢的任務，LATE選擇第一個Map任務為最慢的任務。但是真正最慢的任務是第8個和第9個的Map任務，所以只有K-SAMR準確地鑒定了慢任務。

為了驗證算法鑒別Reduce慢任務的能力，將K-SAMR、SAMR、LATE三個調度算法執行Reduce任務的時間與真實執行時間的相對比，從圖8可以看到K-SAMR選擇第1個Reduce任務為最慢的任務，SAMR選擇第8個Reduce任務為最慢的任務，LATE選擇第8個和第9個 Reduce任務為最慢的任務。但是真正最慢的任務是第1個的Reduce任務，因此只有K-SAMR準確地鑒定了慢任務。

圖8 Reduce任務執行時間

5 總結

針對現有Hadoop調度算法推測執行機制的不足，本文通過研究當前存在的MapReduce調度算法，提出了一種在異構環境下增強自適應性的MapReduce調度算法。該算法記錄了每個節點的歷史信息，采用機器學習技術K-means聚類算法將歷史信息劃分為K個聚蔟，并且動態地調節階段進度值參數，平衡節點上的負載并準確地查找慢任務。最后，通過實驗結果表明了本文K-SAMR算法的有效性。

[1]Jiang Dawei，Ooi Bengchin，Shi Lei，et al.The Performance ofMapReduce：anin-depthstudy[C]//Proceedingsofthe International Conference on Very Large Data Bases，2010：472-483.

[2]Dean J，Ghemawat S.Map reduce：a flexible data processing tool[J].ACM Transactions on Accessible Computing，2010，53（1）：72-77.

[3]梁建武，周揚.一種異構環境下的Hadoop調度算法[J].中國科技論文，2012，7（7）：495-502.

[4]張密密.MapReduce模型在Hadoop實現中的性能分析及改進優化[D].成都：電子科技大學，2010.

[5]Riedel E，Faloutsos C，Gibson G A.Active disks for large scale data processing[J].IEEE Computer，2001，34：68-74.

[6]Zaharia M，Konwinski A，Joseph A D.Improving MapReduce performanceinheterogeneous environments[C]//Proceedings of the 8th Conference on Operating Systems Design and Implementation，2008：29-42.

[7]陳全，鄧倩妮.異構環境下自適應的Map-Reduce調度[J].計算機工程與科學，2009，26（1）：2-6.

[8]Chen Quan，Zhang Daqiang，Guo Minyi，et al.SAMR：a selfadaptive MapReduce scheduling algorithm in heterogeneous environment[C]//Proceedings of the 10th IEEE International Conference on Computer and Information Technology（CIT-2010），2010：2736-2743.

[9]王凱，吳泉源，楊樹強.一種多用戶MapReduce集群的作業調度算法的設計與實現[J].計算機與現代化，2010（10）：23-25.

[10]王昊，王向前，鄭啟龍.推測執行技術在HPMR系統通信優化中的應用[J].中國科學技術大學學報，2010，40（11）：1191-1196. [11]李麗英.基于LATE的Hadoop數據局部性改進調度算法[J].計算機科學，2011，38（11）：67-70.

[12]Seo Sangwon.HPMR：prefetching and pre-shuffling shared MapReduce computation environment[C]//Proceedings of the 11th IEEE International Conference on Cluster Computing，Sep 2009.

[13]黃敏，何中市，邢欣來，等.一種新的K-means聚類中心選取算法[J].計算機工程與應用，2011，47（35）：132-134.

YANG Lishen,YU Liping

College of Computer Sciences and Technology,Henan Polytechnic University,Jiaozuo,Henan 454000,China

Aiming at the shortage of Hadoop default scheduling algorithm and LATE scheduling algorithm of heterogeneous environment,this paper proposes an enhanced adaptive MapReduce scheduling algorithm on the basis of SAMR scheduling algorithm.The algorithm records the history information of each node,and usesK-means clustering algorithm to dynamically adjust the progress value,aims to find the slow tasks which are really need begin back-up.Finally,the experimental results show that the enhanced MapReduce scheduling algorithm has some validity in the aspect of improving the estimation error of the tasks’execution time and accurately identifying the slow tasks.

MapReduce;speculative execution;heterogeneous environment;K-means algorithm

針對Hadoop默認調度算法和異構環境下LATE調度算法的不足，在SAMR調度算法的基礎上提出了一種增強的自適應MapReduce調度算法。該算法記錄了每個節點的歷史信息，采用K-means聚類算法動態地調整階段進度值以找到真正需要啟動備份的落后任務。實驗結果表明，增強自適應的MapReduce調度算法在提高任務執行時間的估算誤差以及準確識別慢任務方面具有一定的有效性。

MapReduce；推測執行；異構環境；K-means算法

A

TP393

10.3778/j.issn.1002-8331.1302-0126

YANG Lishen,YU Liping.Enhanced adaptive MapReduce scheduling algorithm in heterogeneous environment.Computer Engineering and Applications,2013,49（19）：39-43.

國家自然科學基金（No.12A520021）；河南省科學和技術部財政支持重點項目（No.122102310309，No.122102210117）。

楊立身（1963—），男，教授，碩士生導師，主要研究領域為計算機網絡與安全，管理信息系統，過程控制；余麗萍（1984—），女，碩士研究生，主要研究領域為云計算，云存儲。E-mail：yulipingl520@163.com

2013-02-22

2013-04-17

1002-8331（2013）19-0039-05

CNKI出版日期：2013-04-26http://www.cnki.net/kcms/detail/11.2127.TP.20130426.1018.008.html