異構(gòu)環(huán)境下MapRuduce任務(wù)調(diào)度算法優(yōu)化

魏巍，劉釗遠(yuǎn)

異構(gòu)環(huán)境下MapRuduce任務(wù)調(diào)度算法優(yōu)化

魏巍，劉釗遠(yuǎn)

Hadoop作為世界領(lǐng)先的大數(shù)據(jù)平臺(tái)，其性能更多地依賴于MapReduce任務(wù)調(diào)度機(jī)制。通過(guò)對(duì)MapReduce任務(wù)調(diào)度機(jī)制中推測(cè)算法的研究，提出一種高效、準(zhǔn)確和基于優(yōu)先級(jí)的改進(jìn)Hadoop調(diào)度算法。通過(guò)測(cè)試發(fā)現(xiàn)，改進(jìn)后的Hadoop調(diào)度算法在異構(gòu)環(huán)境下能夠?qū)β浜笕蝿?wù)判定準(zhǔn)確，更好地維持系統(tǒng)的負(fù)載平衡，減少系統(tǒng)對(duì)任務(wù)的響應(yīng)時(shí)間，增加對(duì)高優(yōu)先級(jí)任務(wù)的響應(yīng)速度，提高M(jìn)apReduce任務(wù)調(diào)度算法的性能。

異構(gòu)環(huán)境；推測(cè)算法；負(fù)載均衡；優(yōu)先級(jí)

0 引言

近些年來(lái)，在大數(shù)據(jù)背景下，ApacheHadoop已經(jīng)逐漸成為研究的熱點(diǎn)，業(yè)界對(duì)于開(kāi)源Hadoop的應(yīng)用也在不斷的加深。Google、IBM、Microsoft、Amazon、Yahoo、Alibaba等IT互聯(lián)網(wǎng)公司都推出了自己的云計(jì)算服務(wù)平臺(tái)，并把云計(jì)算作為未來(lái)重要的戰(zhàn)略目標(biāo)[1-2]。大多數(shù)的開(kāi)源云計(jì)算系統(tǒng)都是基于Hadoop應(yīng)用平臺(tái)，尤其在應(yīng)用研究領(lǐng)域發(fā)展更為廣泛。Hadoop應(yīng)用框架最核心的設(shè)計(jì)是HDFS[3]（分布式文件系統(tǒng)）和MapReduce，HDFS負(fù)責(zé)海量數(shù)據(jù)的存儲(chǔ)，而MapReduce負(fù)責(zé)海量數(shù)據(jù)的計(jì)算。

MapReduce的優(yōu)勢(shì)之一在于容錯(cuò)機(jī)制對(duì)于用戶透明化，并不需要用戶去參與實(shí)現(xiàn)。當(dāng)一個(gè)節(jié)點(diǎn)出現(xiàn)崩潰時(shí)，其上的任務(wù)被分配給其它的節(jié)點(diǎn)繼續(xù)運(yùn)行。類似情況，如果一個(gè)任務(wù)在一個(gè)節(jié)點(diǎn)上被執(zhí)行的時(shí)間過(guò)長(zhǎng)，則這個(gè)任務(wù)被稱作掉隊(duì)者任務(wù)或后備任務(wù)。把這個(gè)掉隊(duì)者任務(wù)放在另外一個(gè)節(jié)點(diǎn)去執(zhí)行，以便快速完成，這個(gè)過(guò)程稱之為推測(cè)執(zhí)行[4]。Hadoop現(xiàn)有的調(diào)度算法對(duì)于推測(cè)執(zhí)行這一部分并不是很完善，主要體現(xiàn)在對(duì)后備任務(wù)的判定上。目前常用的調(diào)度算法有Hadoop默認(rèn)的調(diào)度算法FIFO（先進(jìn)先出），這種算法并不能體現(xiàn)出作業(yè)的優(yōu)先級(jí)和推測(cè)任務(wù)的執(zhí)行；Facebook提出的Fair Schedule（公平調(diào)度），對(duì)于權(quán)值高的任務(wù)多分配資源，并且支持搶占，如果作業(yè)數(shù)過(guò)多，可能會(huì)頻繁的進(jìn)行上下文切換，增加后備任務(wù)的執(zhí)行時(shí)間；Yahoo公司提出的Capacity Schedule（計(jì)算能力調(diào)度），雖然不支持搶占，但是通過(guò)設(shè)定一些閾值來(lái)判定后備任務(wù)，這在異構(gòu)集群中誤差較大。針對(duì)以上Hadoop調(diào)度算法不足的基礎(chǔ)上，提出一種基于優(yōu)先級(jí)的改進(jìn)Hadoop調(diào)度算法，并同其它的調(diào)度算法進(jìn)行比較研究。

1 現(xiàn)有MapReduce任務(wù)調(diào)度算法

在Hadoop集群中，當(dāng)一個(gè)空閑Slave節(jié)點(diǎn)請(qǐng)求分配任務(wù)時(shí)，有三種任務(wù)類別會(huì)被調(diào)度器所調(diào)度[5]。（1）處于等待狀態(tài)還沒(méi)有被執(zhí)行的任務(wù)，若是本地任務(wù)，則會(huì)優(yōu)先選擇。（2）執(zhí)行失敗的任務(wù)，優(yōu)先級(jí)高的先被執(zhí)行。（3）需要推測(cè)執(zhí)行的掉隊(duì)者任務(wù)。為了挑選和執(zhí)行掉隊(duì)者任務(wù)，Hadoop平臺(tái)上使用的是推測(cè)式執(zhí)行算法。

Hadoop對(duì)于集群中作業(yè)的處理主要分為Map和Reduce兩個(gè)過(guò)程，如圖1所示：

圖1 Map/Reduce task運(yùn)行過(guò)程

Map Task過(guò)程，存儲(chǔ)在HDFS上的Input split經(jīng)過(guò)用戶自定義map函數(shù)處理，得到一個(gè)個(gè)鍵值對(duì)[6]。這些鍵值對(duì)被收集后存放在環(huán)形內(nèi)存緩沖區(qū)中，當(dāng)緩沖區(qū)滿后，數(shù)據(jù)經(jīng)過(guò)排序，由MapReduce將其寫(xiě)入本地磁盤(pán)，生成一個(gè)臨時(shí)文件，并在必要時(shí)對(duì)數(shù)據(jù)進(jìn)行合并和壓縮操作。Reduce Task過(guò)程，數(shù)據(jù)的處理被分成3個(gè)階段：復(fù)制、排序和歸并。復(fù)制階段，從磁盤(pán)中得到所有map的輸出結(jié)果；排序階段，將map的輸出結(jié)果按某種規(guī)則進(jìn)行排序；歸并階段，將排序后的數(shù)據(jù)按照用戶自定義的reduce函數(shù)處理。

Hadoop使用0到1之間進(jìn)度分?jǐn)?shù)來(lái)表示任務(wù)的完成情況。在Map階段，進(jìn)度分?jǐn)?shù)等于已經(jīng)完成的任務(wù)量與輸入的總?cè)蝿?wù)量的比值。在Reduce階段，復(fù)制、排序和歸并3個(gè)小階段各占整個(gè)Reduce任務(wù)執(zhí)行時(shí)間的1/3，在每個(gè)小階段，進(jìn)度分?jǐn)?shù)表示已經(jīng)處理的數(shù)據(jù)量與輸入的總的數(shù)據(jù)量的比值。例如，設(shè)完成Reduce階段總的任務(wù)進(jìn)度1，當(dāng)一個(gè)任務(wù)完成了復(fù)制階段的一半，則任務(wù)的進(jìn)度分?jǐn)?shù)為，當(dāng)一個(gè)任務(wù)完成了排序階段的一半，則任務(wù)的進(jìn)度分?jǐn)?shù)為。

在MapReduce任務(wù)調(diào)度算法中，用任務(wù)的運(yùn)行時(shí)間、任務(wù)的平均進(jìn)度和當(dāng)前進(jìn)度來(lái)預(yù)測(cè)掉隊(duì)者任務(wù)，即當(dāng)活躍任務(wù)的數(shù)量大于1，任務(wù)的平均進(jìn)度分?jǐn)?shù)減去當(dāng)前進(jìn)度分?jǐn)?shù)的值大于或等于0.2，且任務(wù)的運(yùn)行時(shí)間超過(guò)一分鐘時(shí)，則該任務(wù)被視為掉隊(duì)者。這種推測(cè)算法是基于以下假設(shè)：（1）每一個(gè)節(jié)點(diǎn)都是按照同樣的速度處理任務(wù)；（2）在整個(gè)運(yùn)行過(guò)程中，每個(gè)任務(wù)按照同樣的速率運(yùn)行；（3）運(yùn)行后備任務(wù)不消耗系統(tǒng)額外資源；（4）Map階段，用任務(wù)的進(jìn)度分?jǐn)?shù)表示任務(wù)的完成情況，Reduce階段，任務(wù)的排序、復(fù)制、歸并3個(gè)小階段分別占總?cè)蝿?wù)量的1/3。集群的異構(gòu)性使得以上的假設(shè)失效。

集群中的節(jié)點(diǎn)由于配置不同，處理性能不同，總是存在著差異，這些差異影響了Hadoop調(diào)度器的性能。在MapReduce任務(wù)調(diào)度算法中，推測(cè)任務(wù)的判定和執(zhí)行都是通過(guò)任務(wù)的進(jìn)度值確定的，但是在異構(gòu)環(huán)境中由于節(jié)點(diǎn)的差異性，用任務(wù)的平均進(jìn)度分?jǐn)?shù)減去0.2來(lái)判斷推測(cè)任務(wù)顯的不足。很多任務(wù)的進(jìn)度都低于這個(gè)閾值。例如：假設(shè)異構(gòu)集群中有A、B、C3個(gè)節(jié)點(diǎn)，A節(jié)點(diǎn)硬件配置最高，性能很好，B節(jié)點(diǎn)硬件配置中等，性能一般，C節(jié)點(diǎn)硬件配置最差，性能最低。當(dāng)給這個(gè)集群中每個(gè)節(jié)點(diǎn)分配相同任務(wù)，一段時(shí)間后，A節(jié)點(diǎn)的進(jìn)度為0.9，B節(jié)點(diǎn)的進(jìn)度為0.5，任務(wù)的平均進(jìn)度為(0.9+0.5)/2=0.7。此時(shí)，Hadoop默認(rèn)B節(jié)點(diǎn)為慢節(jié)點(diǎn)，則會(huì)調(diào)度空閑節(jié)點(diǎn)C啟動(dòng)推測(cè)任務(wù)，由于節(jié)點(diǎn)C性能較低，這個(gè)后備任務(wù)完成時(shí)間肯定不會(huì)在節(jié)點(diǎn)B完成任務(wù)之前完成，因此，這個(gè)后備任務(wù)就沒(méi)有什么意義。

綜上所述，執(zhí)行后備任務(wù)的推測(cè)算法可能在同構(gòu)環(huán)境下比較適用，但是在異構(gòu)環(huán)境下，調(diào)度程序?？赡苓x擇不到正確的后備任務(wù)，造成了過(guò)多的后備任務(wù)執(zhí)行，占用了系統(tǒng)大量的資源，影響了系統(tǒng)對(duì)任務(wù)的響應(yīng)時(shí)間。

2 同構(gòu)環(huán)境下的任務(wù)推測(cè)算法

Hadoop默認(rèn)的推測(cè)執(zhí)行調(diào)度策略中設(shè)置一些閾值來(lái)判定一個(gè)任務(wù)是否是后備任務(wù)。比如，設(shè)置SPECULATIVE_LAP=60*1000，表示后備任務(wù)的運(yùn)行時(shí)間閾值；SPECULATIVE_GAP=0.2，表示后備任務(wù)的進(jìn)度分?jǐn)?shù)閾值等等。這些閾值的設(shè)置在異構(gòu)環(huán)境下并不準(zhǔn)確。當(dāng)一個(gè)任務(wù)請(qǐng)求執(zhí)行時(shí)，JobTracker會(huì)根據(jù)空閑節(jié)點(diǎn)的心跳請(qǐng)求分配TaskTracker執(zhí)行任務(wù)。如果這些任務(wù)在被處理過(guò)程中滿足以上閾值，則會(huì)被視為掉隊(duì)者任務(wù)，其后備任務(wù)將被執(zhí)行。后備任務(wù)如果被分配到到性能較差的節(jié)點(diǎn)上執(zhí)行，會(huì)再次滿足以上閾值，產(chǎn)生第二個(gè)后備任務(wù)，造成了系統(tǒng)資源的浪費(fèi)。由于調(diào)度算法不能根據(jù)系統(tǒng)的負(fù)載量動(dòng)態(tài)的調(diào)整提交的task數(shù)量，這樣就產(chǎn)生了任務(wù)間相互競(jìng)爭(zhēng)系統(tǒng)資源現(xiàn)象，又由于節(jié)點(diǎn)的處理能力不同，產(chǎn)生的后備任也加入了與已經(jīng)提交的新任務(wù)產(chǎn)生競(jìng)爭(zhēng)。最終，導(dǎo)致系統(tǒng)負(fù)載量過(guò)大，不足以快速地完成任務(wù)。為了使后備任務(wù)的推測(cè)執(zhí)行更加準(zhǔn)確?？梢詮膬蓚€(gè)方面加以改進(jìn)，第一是正確判定后備任務(wù)；第二是選取性能較好的節(jié)點(diǎn)執(zhí)行后備任務(wù)。

2.1 任務(wù)執(zhí)行剩余時(shí)間預(yù)測(cè)算法

對(duì)于Hadoop默認(rèn)調(diào)度策略對(duì)后備任務(wù)判定不足的基礎(chǔ)上，提出一種新的判定方法，即把運(yùn)行時(shí)間最久的task作為后備任務(wù)[7]。因此，要判定后備任務(wù)，就必須知道任務(wù)完成的剩余時(shí)間。設(shè)Pa表示任務(wù)執(zhí)行的平均速率，T_left表示任務(wù)運(yùn)行的剩余時(shí)間。Pr表示任務(wù)的進(jìn)度分?jǐn)?shù)，t表示已運(yùn)行的時(shí)間，則Pa=Pr/t，任務(wù)執(zhí)行的剩余進(jìn)度為1–Pr。用平均速率計(jì)算任務(wù)完成的剩余時(shí)間[8]，如公式（1）：

用任務(wù)運(yùn)行開(kāi)始到當(dāng)前時(shí)間的平均值來(lái)預(yù)測(cè)任務(wù)的剩余完成時(shí)間，充分考慮到集群的異構(gòu)性，任務(wù)提交的順序不同運(yùn)行時(shí)間也不同，不會(huì)產(chǎn)生后提交的任務(wù)產(chǎn)生新的后備任務(wù)情況。

2.2 快慢節(jié)點(diǎn)判定算法

產(chǎn)生的后備任務(wù)如果運(yùn)行的速度比原任務(wù)慢，則后備任務(wù)失去了意義。需要選擇一個(gè)性能良好的節(jié)點(diǎn)來(lái)運(yùn)行后備任務(wù)。選擇節(jié)點(diǎn)的基本策略是給請(qǐng)求執(zhí)行任務(wù)的節(jié)點(diǎn)按照某一個(gè)閾值分為快節(jié)點(diǎn)和慢節(jié)點(diǎn)。閾值設(shè)定為節(jié)點(diǎn)平均進(jìn)度的25%[8]?？紤]到集群的異構(gòu)性，節(jié)點(diǎn)的平均進(jìn)度是由整個(gè)系統(tǒng)所有節(jié)點(diǎn)上的所有任務(wù)的進(jìn)度分?jǐn)?shù)決定，這樣就能較為準(zhǔn)確的判定節(jié)點(diǎn)的處理能力和計(jì)算性能，達(dá)到了準(zhǔn)確地判斷快慢節(jié)點(diǎn)的目的。設(shè)節(jié)點(diǎn)的數(shù)量為n，每個(gè)節(jié)點(diǎn)處理的任務(wù)量（已完成和正在完成的task）為m，判斷快慢節(jié)點(diǎn)的閾值為SNT。則有公式（2）：

其中Task[j]表示節(jié)點(diǎn)上的第j個(gè)任務(wù)。Hadoop集群可用的系統(tǒng)資源有限，處理后備任務(wù)的能力受到制約。因此，需要計(jì)算系統(tǒng)當(dāng)前能夠承載后備任務(wù)的最大值[9]（spectask）?？紤]到集群的異構(gòu)性，可以用在開(kāi)始到某時(shí)刻系統(tǒng)處理Map和Reduce任務(wù)個(gè)數(shù)總和減去系統(tǒng)處理任務(wù)個(gè)數(shù)的平均值來(lái)計(jì)算spectask。其計(jì)算過(guò)程為：設(shè)某時(shí)刻T，系統(tǒng)正在處理的Map和Reduce任務(wù)總數(shù)為S1，則有公式（3）：

S1=NmapTask[T]+NreduceTask[T]（3）設(shè)系統(tǒng)從開(kāi)始時(shí)刻到當(dāng)前時(shí)刻（T）所處理任務(wù)的平均值為S2，則有公式（4）：

有公式（3）和公式（4）得到公式（5）：

其中NmapTask[T]，NreduceTask[T]分別表示T時(shí)刻Map和Reduce階段所執(zhí)行的任務(wù)的數(shù)量。

3 后備任務(wù)推測(cè)算法改進(jìn)

在改進(jìn)的后備任務(wù)調(diào)度算法中需要定義兩個(gè)隊(duì)列，一個(gè)是存放快節(jié)點(diǎn)信息的隊(duì)列（QueueForNode），另一個(gè)是存放按剩余完成時(shí)間排序的task隊(duì)列（QueueForTask）。提交給Hadoop集群的任務(wù)運(yùn)行一分鐘后，開(kāi)始選擇后備任務(wù)的運(yùn)行。改進(jìn)推測(cè)算法中后備任務(wù)的選擇如圖2所示：

圖2 后備任務(wù)的選擇流程圖

后備任務(wù)選擇開(kāi)始時(shí)，由式1計(jì)算系統(tǒng)所有正在運(yùn)行任務(wù)的剩余時(shí)間，按照剩余完成時(shí)間的大小進(jìn)行排序并把task存放在QueueForTask隊(duì)列中。按照式5計(jì)算集群中能夠處理的最大備份任務(wù)數(shù)量，若spectask大于0，將前parseInt((1+20%)*spectask)個(gè)任務(wù)按所屬Job的優(yōu)先級(jí)排序。parseInt(變量)函數(shù)表示不大于變量的最大整數(shù)，按優(yōu)先級(jí)排序是為了使優(yōu)先級(jí)高的后備任務(wù)可以先得到執(zhí)行。排完序后，取前spectask個(gè)任務(wù)等待執(zhí)行。

為了使備份任務(wù)得到較快執(zhí)行，選取性能良好的快節(jié)點(diǎn)很關(guān)鍵。選取快節(jié)點(diǎn)執(zhí)行流程如圖3所示：

圖3 快節(jié)點(diǎn)選擇執(zhí)行流程圖

當(dāng)JobTracker收到TaskTracker心跳請(qǐng)求時(shí)，為了確保系統(tǒng)預(yù)留足夠可用資源，檢查系統(tǒng)中可用的slots（槽）數(shù)量是否大于slots總數(shù)的百分之十。若不滿足條件，忽略節(jié)點(diǎn)請(qǐng)求，否則判斷節(jié)點(diǎn)的任務(wù)進(jìn)度是否大于閾值（SNT），若不大于，忽略節(jié)點(diǎn)請(qǐng)求，否則將節(jié)點(diǎn)信息加入到快節(jié)點(diǎn)請(qǐng)求隊(duì)列（QueueForNode）。將QueueForTask隊(duì)列中前Min(QueueForTask.size，spectask)個(gè) 任 務(wù) 分 配 給QueueForNode前面的節(jié)點(diǎn)執(zhí)行，QueueForTask.size表示隊(duì)列中任務(wù)的數(shù)量，并更新QueueForTask隊(duì)列和QueueForNode隊(duì)列的信息。

4 實(shí)驗(yàn)設(shè)計(jì)及結(jié)果分析

為了實(shí)驗(yàn)方便和計(jì)算簡(jiǎn)單，采用Hadoop源碼包中自帶的單詞統(tǒng)計(jì)實(shí)例來(lái)測(cè)試改進(jìn)MapReduce任務(wù)調(diào)度算法的性能。實(shí)驗(yàn)原理為：用戶上傳到HDFS的文檔，經(jīng)過(guò)map和reduce過(guò)程，統(tǒng)計(jì)輸出結(jié)果，計(jì)算任務(wù)的完成時(shí)間，并和原有的任務(wù)調(diào)度算法進(jìn)行對(duì)比。

（1）實(shí)驗(yàn)一由于實(shí)驗(yàn)條件限制，Hadoop集群由三臺(tái)異構(gòu)普通PC組成，其組成如表1所示：

表1 集群配置

每臺(tái)PC的操作系統(tǒng)為ubuntu14.04，java版本為JDK 1.7.0_65，Hadoop平臺(tái)為Hadoop 1.0.0。在此次實(shí)驗(yàn)中，用戶同時(shí)提交三個(gè)job，每個(gè)job的大小為300M，集群中設(shè)定的物理塊（block）塊大小為64M，因此每個(gè)job被分成5個(gè)Map子任務(wù)。三個(gè)job分別在無(wú)推測(cè)執(zhí)行，Hadoop自帶的推測(cè)算法（以Capacity Schedule為例）和改進(jìn)Hadoop推測(cè)算法三種情況下處理，結(jié)果如圖4所示：

圖4 異構(gòu)環(huán)境下推測(cè)算法性能比較

由圖4分析，異構(gòu)環(huán)境中，在處理相同任務(wù)量的情況下，無(wú)推測(cè)算法相比推測(cè)算法，作業(yè)的完成的時(shí)間長(zhǎng)；改進(jìn)的推測(cè)算法比Hadoop自帶的推測(cè)算法完成時(shí)間短，且隨著job數(shù)量的增加變的明顯。這是因?yàn)楫?dāng)任務(wù)量過(guò)多時(shí)，后提交的任務(wù)執(zhí)行的時(shí)間較長(zhǎng)，產(chǎn)生推測(cè)任務(wù)，改進(jìn)的推測(cè)算法通過(guò)預(yù)測(cè)推測(cè)任務(wù)的剩余完成時(shí)間，動(dòng)態(tài)的分配系統(tǒng)資源，使推測(cè)任務(wù)得到快速的執(zhí)行，提高了系統(tǒng)處理作業(yè)的性能。

（2）實(shí)驗(yàn)二先后向Hadoop集群中提交4個(gè)job，每個(gè)job的大小是300M。同時(shí)設(shè)置第三次提交的作業(yè)（job3）的優(yōu)先級(jí)為HIGH，其余job的優(yōu)先級(jí)是NORMAL，在改進(jìn)的推測(cè)算法下，處理任務(wù)的情況，如圖5所示：

圖5 不同優(yōu)先級(jí)job完成時(shí)間比較

由圖5分析，job3作業(yè)的完成時(shí)間最短，job1、job2、job4作業(yè)完成時(shí)間依次增加。因?yàn)閖ob3的優(yōu)先級(jí)大于其它job的優(yōu)先級(jí)，在改進(jìn)推測(cè)算法中，優(yōu)先級(jí)高的任務(wù)優(yōu)先獲得系統(tǒng)資源，優(yōu)先被執(zhí)行；優(yōu)先級(jí)低的job按提交的先后順序依次被執(zhí)行。綜上所述，改進(jìn)的推測(cè)算法能夠較好地處理優(yōu)先級(jí)較高的作業(yè)。

5 總結(jié)

針對(duì)Hadoop自帶的推測(cè)算法對(duì)于后備任務(wù)判定的不足，提出了更具公平性的改進(jìn)Hadoop推測(cè)算法。算法通過(guò)預(yù)測(cè)提交給集群中所有任務(wù)的剩余完成時(shí)間，結(jié)合作業(yè)的優(yōu)先級(jí)，找到優(yōu)先級(jí)較高，可能運(yùn)行時(shí)間較長(zhǎng)的任務(wù)，并視為推測(cè)任務(wù)。同時(shí)，對(duì)于異構(gòu)集群中所有節(jié)點(diǎn)處理能力的不同，把節(jié)點(diǎn)分為快慢節(jié)點(diǎn)，并調(diào)用快節(jié)點(diǎn)處理推測(cè)任務(wù)，保證了推測(cè)任務(wù)得到較快的處理。實(shí)驗(yàn)表明，改進(jìn)Hadoop推測(cè)算法相比原有的推測(cè)算法，縮短了任務(wù)完成時(shí)間，更好地維持系統(tǒng)的負(fù)載平衡，提高了系統(tǒng)處理作業(yè)的能力。

[1]VAQUEROLM,RODEO Merinol,CACERES J,et al.A break in the cloud:Toward a Cloud Definition[J].ACM SIGCOMM Computer Commutitication Review,2009,39(1):50-55.

[2]GUNARAYHNE T and WUTL,QIU,etal.MapReduce in the clouds for sicence:2th IEEE Internation conference on cloud computing Technology and science[C].New York:IEEE Scocienty,2010:565-572.

[3]Tom White.Hadoop權(quán)威指南[M].北京:清華大學(xué)出版社,2011:75-84.

[4]董西成.Hadoop技術(shù)內(nèi)幕[M].北京:機(jī)械工業(yè)出版社,2013.5:152-156.

[5]梁建武,周揚(yáng).一種異構(gòu)環(huán)境下的Hadoop調(diào)度算法[J].中國(guó)科技論文.2012,7(7):495-500.

[6]劉鵬.實(shí) 戰(zhàn)Hadoop[M].北京:電 子 工業(yè)出 版社,2011:60-62.

[7]MateiZaharia,Andy Konwinski,Anthony D Joseph. Improving MapReduce Performancein Heterogeneous Environments[C].8thUSENIX Symposium on Operating System Design and Implementation,2009:29-42.

[8]余影,吳斌.基于Hadoop的大規(guī)模數(shù)據(jù)交換的研究[D].北京:北京郵電大學(xué),2011.

[9]何文峰,王多強(qiáng).基于任務(wù)特征和公平策略的Hadoop作業(yè)調(diào)度算法研究[D].武漢:華中科技大學(xué),2013:40-50.

AMapRuducetask Scheduling Mechanism in Heterogeneous Environment

Wei Wei,Liu Zhaoyuan
(School of Computer Science and Technology,Xi’an University of Posts and Telecommunications,Xi’an710061,China)

As the world's leading data platform,Hadoop’s performance deeply depends on the MapReduce scheduling mechanism. In this paper,through a speculative algorithm research on MapReduce scheduling mechanism,an efficient,accurate and priority-based advanced Hadoop scheduling mechanism algorithm is proposed.This algorithm can make exactly judgment to backward task in heterogeneous environment by testing.It maintains the balance of the system load better and reduces the system response time to the tasks.The algorithm also improves the response speed to the tasks of high priority and the performance of MapReduce scheduling mechanism.

Heterogeneous Environment;Speculative Algorithm;Load Balancing;Priority

TP338

A

1007-757X(2015)06-0055-04

2014.12.31）

魏 ?。?988-），男，漢族，河南信陽(yáng)，西安郵電大學(xué)，碩士研究生，研究方向：計(jì)算機(jī)應(yīng)用技術(shù)，西安，710061

劉釗遠(yuǎn)（1963-），男，漢族，陜西銅川，西安郵電大學(xué)，教授，研究方向：嵌入式系統(tǒng)應(yīng)用研究，西安，710061