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

楊立身，余麗萍

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

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

本文針對(duì)以上算法進(jìn)行改進(jìn)，在SAMR算法的基礎(chǔ)上提出了一個(gè)增強(qiáng)的自適應(yīng)K-SAMR調(diào)度算法。考慮到其他影響任務(wù)進(jìn)程的因素，該算法記錄了每個(gè)節(jié)點(diǎn)的歷史信息并采用K-means聚類算法動(dòng)態(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]通過(guò)任務(wù)進(jìn)度值Progress Score對(duì)推測(cè)執(zhí)行任務(wù)進(jìn)行選擇，常使用0到1之間的值來(lái)標(biāo)識(shí)每個(gè)任務(wù)的進(jìn)度。由AvgProgress來(lái)表示每個(gè)作業(yè)的平均進(jìn)度值，Progress Score[i]表示第i個(gè)任務(wù)的任務(wù)進(jìn)度值。設(shè)定已經(jīng)處理完成的任務(wù)條數(shù)為M，總共需要處理的任務(wù)條數(shù)N，所處的階段的序列號(hào)為K，任務(wù)數(shù)量為P。Hadoop默認(rèn)調(diào)度算法首先根據(jù)公式（1）和公式（2）獲得PS的值，然后根據(jù)公式（3）判斷任務(wù)是否為落后任務(wù)，并在另一個(gè)快節(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)境中會(huì)造成任務(wù)進(jìn)度估計(jì)的失真。其次，Hadoop默認(rèn)調(diào)度器根據(jù)任務(wù)進(jìn)度值來(lái)啟動(dòng)備份任務(wù)是不合理的，該方式?jīng)]有考慮異構(gòu)環(huán)境下不同節(jié)點(diǎn)執(zhí)行任務(wù)的速率之間的差異性。最后，Hadoop默認(rèn)調(diào)度器可能啟動(dòng)不必要的備份任務(wù)。

2.2 LATE調(diào)度器

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

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

2.3 SAMR調(diào)度器

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

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

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

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

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

3.1 K-SAMR算法的基本思想

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

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

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

3.3 使用歷史信息和臨時(shí)信息

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

圖2 使用Map臨時(shí)信息和歷史信息的方法

圖3 使用Reduce臨時(shí)信息和歷史信息的方法

具體步驟如下：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

需要通過(guò)大量的實(shí)驗(yàn)來(lái)確定SNT的值。如果SNT取值太小，那么將會(huì)把一些正常的TaskTracker誤判為慢Task-Tracker；如果SNT取值過(guò)大，則將會(huì)把一些慢的TaskTracker誤判為正常TaskTracker。只有當(dāng)申請(qǐng)任務(wù)的TaskTracker不是掉隊(duì)者時(shí)，它才把慢的任務(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)是將一個(gè)數(shù)據(jù)集劃分為若干個(gè)聚簇，使聚簇內(nèi)的對(duì)象盡可能相似，而類之間盡可能相異。

在K-SAMR中的K-means聚類算法的步驟為：（1）K-SAMR任意選擇K個(gè)樣本作為聚簇初始的中心點(diǎn)；（2）根據(jù)每個(gè)聚簇的中心坐標(biāo)，把每個(gè)樣本分配給距離其最近的聚簇；（3）更新聚簇的中心點(diǎn)坐標(biāo)，即計(jì)算每個(gè)聚簇中所有樣本的均值；（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)測(cè)試程序WordCount去評(píng)估算法的性能。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 總結(jié)

針對(duì)現(xiàn)有Hadoop調(diào)度算法推測(cè)執(zhí)行機(jī)制的不足，本文通過(guò)研究當(dāng)前存在的MapReduce調(diào)度算法，提出了一種在異構(gòu)環(huán)境下增強(qiáng)自適應(yīng)性的MapReduce調(diào)度算法。該算法記錄了每個(gè)節(jié)點(diǎn)的歷史信息，采用機(jī)器學(xué)習(xí)技術(shù)K-means聚類算法將歷史信息劃分為K個(gè)聚蔟，并且動(dòng)態(tài)地調(diào)節(jié)階段進(jìn)度值參數(shù)，平衡節(jié)點(diǎn)上的負(fù)載并準(zhǔn)確地查找慢任務(wù)。最后，通過(guò)實(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].中國(guó)科技論文，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]王凱，吳泉源，楊樹(shù)強(qiáng).一種多用戶MapReduce集群的作業(yè)調(diào)度算法的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)與現(xiàn)代化，2010（10）：23-25.

[10]王昊，王向前，鄭啟龍.推測(cè)執(zhí)行技術(shù)在HPMR系統(tǒng)通信優(yōu)化中的應(yīng)用[J].中國(guó)科學(xué)技術(shù)大學(xué)學(xué)報(bào)，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]黃敏，何中市，邢欣來(lái)，等.一種新的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

針對(duì)Hadoop默認(rèn)調(diào)度算法和異構(gòu)環(huán)境下LATE調(diào)度算法的不足，在SAMR調(diào)度算法的基礎(chǔ)上提出了一種增強(qiáng)的自適應(yīng)MapReduce調(diào)度算法。該算法記錄了每個(gè)節(jié)點(diǎn)的歷史信息，采用K-means聚類算法動(dòng)態(tài)地調(diào)整階段進(jìn)度值以找到真正需要啟動(dòng)備份的落后任務(wù)。實(shí)驗(yàn)結(jié)果表明，增強(qiáng)自適應(yīng)的MapReduce調(diào)度算法在提高任務(wù)執(zhí)行時(shí)間的估算誤差以及準(zhǔn)確識(shí)別慢任務(wù)方面具有一定的有效性。

MapReduce；推測(cè)執(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.

國(guó)家自然科學(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)，過(guò)程控制；余麗萍（1984—），女，碩士研究生，主要研究領(lǐng)域?yàn)樵朴?jì)算，云存儲(chǔ)。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