楊立身，余麗萍

河南理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，河南焦作 454000

異構(gòu)環(huán)境下增強(qiáng)的自適應(yīng)MapReduce調(diào)度算法

楊立身，余麗萍

河南理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，河南焦作 454000

1 引言

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

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

本文針對以上算法進(jìn)行改進(jìn)，在SAMR算法的基礎(chǔ)上提出了一個增強(qiáng)的自適應(yīng)K-SAMR調(diào)度算法?？紤]到其他影響任務(wù)進(jìn)程的因素，該算法記錄了每個節(jié)點(diǎn)的歷史信息并采用K-means聚類算法動態(tài)地調(diào)整階段進(jìn)度值參數(shù)，準(zhǔn)確地查找慢任務(wù)。并將慢節(jié)點(diǎn)分為Map任務(wù)慢節(jié)點(diǎn)和Reduce慢節(jié)點(diǎn)，有效地提高了系統(tǒng)資源利用率。

2 研究現(xiàn)狀分析

2.1 Hadoop默認(rèn)調(diào)度器

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

文獻(xiàn)[10]指出該調(diào)度器的主要缺陷：首先，Hadoop默認(rèn)調(diào)度器使用固定的階段進(jìn)度值M1=1，M2=0，R1=R2=R3=1/3，該方式?jīng)]有考慮集群節(jié)點(diǎn)的異構(gòu)性，在現(xiàn)實(shí)環(huán)境中會造成任務(wù)進(jìn)度估計(jì)的失真。其次，Hadoop默認(rèn)調(diào)度器根據(jù)任務(wù)進(jìn)度值來啟動備份任務(wù)是不合理的，該方式?jīng)]有考慮異構(gòu)環(huán)境下不同節(jié)點(diǎn)執(zhí)行任務(wù)的速率之間的差異性。最后，Hadoop默認(rèn)調(diào)度器可能啟動不必要的備份任務(wù)。

2.2 LATE調(diào)度器

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

盡管LATE選取剩余時間最長的任務(wù)去啟動備份任務(wù)，但它仍然頻繁地選擇錯的任務(wù)去備份。這是因?yàn)長ATE調(diào)度算法仍然使用Hadoop默認(rèn)調(diào)度算法的設(shè)定，并且未區(qū)分Map慢節(jié)點(diǎn)和Reduce慢節(jié)點(diǎn)，導(dǎo)致LATE調(diào)度算法對任務(wù)的剩余時間的估計(jì)不精確。

2.3 SAMR調(diào)度器

圖1 在SAMR調(diào)度器中使用和更新歷史信息

SAMR調(diào)度器通過估計(jì)任務(wù)執(zhí)行時間來識別慢任務(wù)，但不采用固定的階段進(jìn)度值。如圖1所示，當(dāng)SAMR調(diào)度器估計(jì)一個節(jié)點(diǎn)上正運(yùn)行任務(wù)的剩余時間時，它存儲每個節(jié)點(diǎn)上的階段進(jìn)度值，讀取存儲在節(jié)點(diǎn)上的歷史信息然后動態(tài)地設(shè)置階段進(jìn)度值。由于SAMR采用歷史信息記錄每個節(jié)點(diǎn)的階段取值更貼近實(shí)際，因此，相對于Hadoop默認(rèn)調(diào)度器、LATE調(diào)度器，SAMR調(diào)度器更能夠適用于異構(gòu)環(huán)境。

SAMR只考慮影響任務(wù)階段進(jìn)度值的其中一個因素，沒有考慮在同一個節(jié)點(diǎn)上運(yùn)行不同MapReduce作業(yè)的任務(wù)可以有不同的階段進(jìn)度值。原因是當(dāng)執(zhí)行不同MapReduce作業(yè)時，執(zhí)行Map和Reduce階段花費(fèi)的時間不同，并且它們產(chǎn)生的大量中間數(shù)據(jù)也不同。另外，當(dāng)處理大小不同的數(shù)據(jù)集時，相同的MapReduce作業(yè)的任務(wù)也會有不同的階段進(jìn)度值。例如，大的輸入數(shù)據(jù)集會造成大的中間數(shù)據(jù)，這些將導(dǎo)致其需要花費(fèi)更多的時間在Shuffle階段[12]。

本文提出的K-SAMR算法是一個增強(qiáng)的自適應(yīng)MapReduce調(diào)度算法。除了考慮硬件異構(gòu)性的因素以外，還考慮了其他影響任務(wù)階段進(jìn)度值的因素。因此，K-SAMR算法在記錄每個節(jié)點(diǎn)上歷史信息的同時采用K-means聚類算法動態(tài)調(diào)整階段進(jìn)度值，估計(jì)任務(wù)的執(zhí)行時間，查找慢任務(wù)。

3 K-SAMR調(diào)度器

3.1 K-SAMR算法的基本思想

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

3.2 Map任務(wù)完成的比例（PFM）和Reduce任務(wù)完成的比例（PFR）

K-SAMR調(diào)度算法利用PFM和PFR決定何時去計(jì)算臨時階段進(jìn)度值。假設(shè)N代表一個集群中TaskTrackers的全部數(shù)量，F(xiàn)M代表一個作業(yè)中Map任務(wù)的總數(shù)量，F(xiàn)M[i]代表第i個TaskTracker中Map任務(wù)完成的數(shù)量，TR代表一個作業(yè)中Reduce任務(wù)的全部數(shù)量，F(xiàn)R[i]代表第i個Task-Tracker中Reduce任務(wù)的完成數(shù)量。當(dāng)公式（5）和（6）滿足條件時，K-SAMR算法才能計(jì)算每個作業(yè)的Map和Reduce階段的臨時進(jìn)度值。

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

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

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

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

具體步驟如下：

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

（2）每個TaskTracker從本地節(jié)點(diǎn)讀取歷史信息（M1，M2，R1，R2，R3）。

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

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

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

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

（7）當(dāng)一個作業(yè)完成時，K-SAMR計(jì)算作業(yè)的所有Map和Reduce任務(wù)階段的平均值，同時生成一個新的階段進(jìn)度值的聚簇作為歷史信息的一部分。

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

3.4 慢任務(wù)探索算法

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

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

3.5 慢節(jié)點(diǎn)探索算法

SNT代表一個閥值，它用來判斷一個任務(wù)是否為慢節(jié)點(diǎn)，假設(shè)系統(tǒng)中有N個TaskTrackers，第i個TaskTracker的節(jié)點(diǎn)Map任務(wù)的進(jìn)度率為TRmi，Reduce階段的進(jìn)度率為TRri，平均進(jìn)度率是為ATRm、ATRr。如果有M個Map任務(wù)和R個Reduce任務(wù)運(yùn)行在第i個TaskTracker節(jié)點(diǎn)上，TRmi、TRri、ATRm、ATRr的計(jì)算公式如下：

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

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

3.6 K-means算法在K-SAMR中的應(yīng)用

在統(tǒng)計(jì)和數(shù)據(jù)挖掘方面，K-means聚類算法是一種聚類分析方法[13]。K-means聚類算法的主要目標(biāo)是將一個數(shù)據(jù)集劃分為若干個聚簇，使聚簇內(nèi)的對象盡可能相似，而類之間盡可能相異。

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

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

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

本文利用異構(gòu)環(huán)境下已有的兩種改進(jìn)算法SAMR和LATE算法與K-SAMR算法相比較。在這三種調(diào)度算法的基礎(chǔ)上改寫Hadoop默認(rèn)調(diào)度器，在新的三種調(diào)度器上，運(yùn)行Hadoop自帶的基準(zhǔn)測試程序WordCount去評估算法的性能。

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

表1 Hadoop集群的硬件環(huán)境和配置

4.1 估計(jì)階段進(jìn)度值的能力

為了驗(yàn)證通過K-SAMR算法估計(jì)的Map和Reduce階段進(jìn)度值的準(zhǔn)確性，對比表2和表3可以發(fā)現(xiàn)，通過K-SAMR算法估計(jì)Map和Reduce各階段進(jìn)度值和從系統(tǒng)收集的Map和Reduce階段實(shí)際的階段進(jìn)度值相差不大，但是其與利用固定階段進(jìn)度值的LATE算法的結(jié)果相差很大；并且，通過SAMR算法估計(jì)的結(jié)果和從系統(tǒng)收集來的實(shí)際進(jìn)度值之間的差值，比采用K-SAMR算法獲得的進(jìn)度值大得多。

表2 K-SAMR算法與真實(shí)進(jìn)度值的比較

表3 SAMR算法與真實(shí)進(jìn)度值的比較

4.2 估計(jì)剩余時間的能力

圖5 Map任務(wù)剩余時間估計(jì)誤差（WordCount 10 GB）

圖6 Reduce任務(wù)剩余時間估計(jì)誤差（WordCount 10 GB）

圖7 Map任務(wù)執(zhí)行時間

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

4.3 鑒別慢任務(wù)的能力

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

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

圖8 Reduce任務(wù)執(zhí)行時間

5 總結(jié)

針對現(xiàn)有Hadoop調(diào)度算法推測執(zhí)行機(jī)制的不足，本文通過研究當(dāng)前存在的MapReduce調(diào)度算法，提出了一種在異構(gòu)環(huán)境下增強(qiáng)自適應(yīng)性的MapReduce調(diào)度算法。該算法記錄了每個節(jié)點(diǎn)的歷史信息，采用機(jī)器學(xué)習(xí)技術(shù)K-means聚類算法將歷史信息劃分為K個聚蔟，并且動態(tài)地調(diào)節(jié)階段進(jìn)度值參數(shù)，平衡節(jié)點(diǎn)上的負(fù)載并準(zhǔn)確地查找慢任務(wù)。最后，通過實(shí)驗(yàn)結(jié)果表明了本文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]梁建武，周揚(yáng).一種異構(gòu)環(huán)境下的Hadoop調(diào)度算法[J].中國科技論文，2012，7（7）：495-502.

[4]張密密.MapReduce模型在Hadoop實(shí)現(xiàn)中的性能分析及改進(jìn)優(yōu)化[D].成都：電子科技大學(xué)，2010.

[5]Riedel E，F(xiàn)aloutsos 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]陳全，鄧倩妮.異構(gòu)環(huán)境下自適應(yīng)的Map-Reduce調(diào)度[J].計(jì)算機(jī)工程與科學(xué)，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]王凱，吳泉源，楊樹強(qiáng).一種多用戶MapReduce集群的作業(yè)調(diào)度算法的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)與現(xiàn)代化，2010（10）：23-25.

[10]王昊，王向前，鄭啟龍.推測執(zhí)行技術(shù)在HPMR系統(tǒng)通信優(yōu)化中的應(yīng)用[J].中國科學(xué)技術(shù)大學(xué)學(xué)報，2010，40（11）：1191-1196. [11]李麗英.基于LATE的Hadoop數(shù)據(jù)局部性改進(jìn)調(diào)度算法[J].計(jì)算機(jī)科學(xué)，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].計(jì)算機(jī)工程與應(yīng)用，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默認(rèn)調(diào)度算法和異構(gòu)環(huán)境下LATE調(diào)度算法的不足，在SAMR調(diào)度算法的基礎(chǔ)上提出了一種增強(qiáng)的自適應(yīng)MapReduce調(diào)度算法。該算法記錄了每個節(jié)點(diǎn)的歷史信息，采用K-means聚類算法動態(tài)地調(diào)整階段進(jìn)度值以找到真正需要啟動備份的落后任務(wù)。實(shí)驗(yàn)結(jié)果表明，增強(qiáng)自適應(yīng)的MapReduce調(diào)度算法在提高任務(wù)執(zhí)行時間的估算誤差以及準(zhǔn)確識別慢任務(wù)方面具有一定的有效性。

MapReduce；推測執(zhí)行；異構(gòu)環(huán)境；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.

國家自然科學(xué)基金（No.12A520021）；河南省科學(xué)和技術(shù)部財(cái)政支持重點(diǎn)項(xiàng)目（No.122102310309，No.122102210117）。

楊立身（1963—），男，教授，碩士生導(dǎo)師，主要研究領(lǐng)域?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)與安全，管理信息系統(tǒng)，過程控制；余麗萍（1984—），女，碩士研究生，主要研究領(lǐng)域?yàn)樵朴?jì)算，云存儲。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