Hadoop云平臺(tái)下基于LATE改進(jìn)的推測(cè)執(zhí)行算法

盧　慧，高弘博，張豐滿，王　梅, 翟嘉伊，肖　震

(1.成都紡織高等?？茖W(xué)校軟件測(cè)試中心,四川 成都 611731；2.中國(guó)建設(shè)銀行武漢數(shù)據(jù)中心，湖北 武漢 430070)

?

Hadoop云平臺(tái)下基于LATE改進(jìn)的推測(cè)執(zhí)行算法

盧慧1，高弘博1，張豐滿1，王梅1, 翟嘉伊1，肖震2

(1.成都紡織高等?？茖W(xué)校軟件測(cè)試中心,四川 成都 611731；2.中國(guó)建設(shè)銀行武漢數(shù)據(jù)中心，湖北 武漢 430070)

摘要：為解決Hadoop云平臺(tái)下推測(cè)執(zhí)行算法的不足，基于LATE算法提出一種新的任務(wù)進(jìn)度計(jì)算方法，并且采用更細(xì)粒度的方式選擇執(zhí)行備份任務(wù)的節(jié)點(diǎn)。實(shí)驗(yàn)結(jié)果表明，該算法能夠更精準(zhǔn)的選定掉隊(duì)者任務(wù)并選擇合適的執(zhí)行節(jié)點(diǎn)，縮短作業(yè)的執(zhí)行時(shí)間，提高云平臺(tái)的效率。

關(guān)鍵詞：Hadoop云平臺(tái)LATE算法掉隊(duì)者任務(wù)

隨著Internet和Web技術(shù)的高速發(fā)展，大數(shù)據(jù)時(shí)代已經(jīng)來(lái)臨，如何從大數(shù)據(jù)中獲取有價(jià)值的信息，成為科研機(jī)構(gòu)和業(yè)界的研究熱點(diǎn)[1-3]。Hadoop是一個(gè)分布式云計(jì)算平臺(tái)， 其核心思想源自于Google公司的MapReduce編程模型和GFS文件系統(tǒng)模型。由于Hadoop的代碼開源，目前各大IT公司均采用其作為云計(jì)算運(yùn)行框架，并結(jié)合應(yīng)用需求進(jìn)行改進(jìn)，針對(duì)海量數(shù)據(jù)的處理取得了良好的效果。但是在實(shí)際的使用中，Hadoop云計(jì)算還存在著一些不足[4-5]。

為了進(jìn)一步提高Hadoop集群的運(yùn)行效率，減小作業(yè)的完成時(shí)間，Hadoop系統(tǒng)提供了一種推測(cè)執(zhí)行機(jī)制。但是在實(shí)際使用中，集群中機(jī)器存在一定的異構(gòu)性，針對(duì)異構(gòu)的集群環(huán)境，Hadoop的調(diào)度算法還有待改進(jìn)。通常在同構(gòu)環(huán)境下該機(jī)制的確起到了一定效果，但是在實(shí)際的生產(chǎn)環(huán)境中，由于集群異構(gòu)等問(wèn)題，會(huì)出現(xiàn)straggler問(wèn)題[6]。該機(jī)制不但沒(méi)有起到提高作業(yè)效率的作用，反而由于過(guò)多的執(zhí)行備份任務(wù)占用了過(guò)多的資源，影響了整體作業(yè)的執(zhí)行效率。

近年來(lái)，相關(guān)學(xué)者針對(duì)Hadoop云平臺(tái)下推測(cè)執(zhí)行機(jī)制提出一些新的調(diào)度算法，其中文獻(xiàn)[7]提出了一種基于LATE的推測(cè)執(zhí)行算法，該算法采用任務(wù)帶寬的方式計(jì)算任務(wù)的剩余時(shí)間，并且加入了節(jié)省集群資源的策略。但是該算法使用任務(wù)的平均速度計(jì)算任務(wù)的剩余完成時(shí)間，會(huì)造成掉隊(duì)者任務(wù)的誤判斷,并且沒(méi)有考慮執(zhí)行備份任務(wù)的節(jié)點(diǎn)的質(zhì)量。隨著Hadoop使用場(chǎng)景的擴(kuò)展，相關(guān)學(xué)者隨之提出了各種改進(jìn)的資源調(diào)度算法。改進(jìn)算法的設(shè)計(jì)目標(biāo)因需求而異，主要包括降低作業(yè)執(zhí)行時(shí)間、提升系統(tǒng)吞吐率、滿足作業(yè)時(shí)間限制、提升數(shù)據(jù)本地性以及適應(yīng)異構(gòu)環(huán)境等[8-11]。改進(jìn)算法的目標(biāo)不同，且針對(duì)的資源調(diào)度層次不同，有的是針對(duì)作業(yè)層改進(jìn)，有的是針對(duì)任務(wù)層改進(jìn)，所以沒(méi)有一個(gè)固定的指標(biāo)。

針對(duì)上述問(wèn)題，本文提出一種基于LATE改進(jìn)的推測(cè)執(zhí)行算法，實(shí)現(xiàn)更精準(zhǔn)的定位掉隊(duì)者任務(wù)并選擇更合適的節(jié)點(diǎn)執(zhí)行備份任務(wù)。

1Hadoop推測(cè)執(zhí)行算法

1.1推測(cè)執(zhí)行過(guò)程

推測(cè)執(zhí)行算法的思路是以空間換時(shí)間，同時(shí)啟動(dòng)多個(gè)相同任務(wù)然后選取先執(zhí)行完畢的任務(wù)的結(jié)果，這樣可以提高任務(wù)計(jì)算速度。推測(cè)執(zhí)行算法的核心在于選擇需要推測(cè)執(zhí)行的任務(wù)以及選擇在執(zhí)行推測(cè)備份任務(wù)的節(jié)點(diǎn)[12]。

在Hadoop默認(rèn)的推測(cè)執(zhí)行算法中，為了判定掉隊(duì)者任務(wù)即執(zhí)行進(jìn)度低于平均水平的任務(wù)，TaskTracker會(huì)實(shí)時(shí)記錄其運(yùn)行的任務(wù)的進(jìn)度，并周期性的發(fā)送給JobTracker。

為了避免落隊(duì)者任務(wù)影響整體作業(yè)的運(yùn)行效率，Hadoop提出了Speculative task機(jī)制。該機(jī)制的思想如下：在任務(wù)運(yùn)行后，開始對(duì)任務(wù)的運(yùn)行進(jìn)度進(jìn)行實(shí)時(shí)預(yù)測(cè)，如果有任務(wù)的進(jìn)步明顯落后與所有任務(wù)的平均水平，則判定這類任務(wù)為掉隊(duì)者任務(wù)，從而對(duì)此任務(wù)重新申請(qǐng)資源，針對(duì)此任務(wù)執(zhí)行一個(gè)備份任務(wù)。

推測(cè)執(zhí)行算法分別針對(duì)Map任務(wù)和Reduce任務(wù)提出了進(jìn)度估算方式。針對(duì)Map任務(wù)，任務(wù)的進(jìn)度即為當(dāng)前處理的數(shù)據(jù)量與輸入文件數(shù)據(jù)量的比值。而針對(duì)Redcue任務(wù)，則將Redcue任務(wù)的三個(gè)階段的等值劃分，即Copy、sort、reduce三個(gè)階段各占進(jìn)度的1/3。算法根據(jù)公式(1)計(jì)算一個(gè)任務(wù)的進(jìn)度，其中 是一個(gè)范圍為0到1的正數(shù)，代表任務(wù)的進(jìn)度值。M為Map任務(wù)已經(jīng)處理的數(shù)據(jù)量，N為Map任務(wù)輸入文件的數(shù)據(jù)量。K為Reduce任務(wù)已完成的階段數(shù)。

(1)

通過(guò)上述方式即可估算出一個(gè)任務(wù)的進(jìn)度，如當(dāng)一個(gè)Redcue任務(wù)正處于sort階段并且已經(jīng)拷貝了大概一半的數(shù)據(jù)時(shí)，該任務(wù)的進(jìn)度按照公式計(jì)算為(1/3)×(1+1/2)=1/2。推測(cè)執(zhí)行算法通過(guò)公式(2)計(jì)算所有運(yùn)行任務(wù)進(jìn)度的平均值，根據(jù)公式(3)判定任務(wù)是否為掉隊(duì)者任務(wù)。如果任務(wù)的進(jìn)度值滿足公式(3)，其中Threshols默認(rèn)設(shè)為0.2，則認(rèn)為該任務(wù)落后于所有任務(wù)的平均進(jìn)度，判定該任務(wù)為掉隊(duì)者任務(wù)。如果判定為掉隊(duì)者任務(wù)，那么當(dāng)有TaskTracker請(qǐng)求任務(wù)時(shí)，則會(huì)針對(duì)掉隊(duì)者任務(wù)執(zhí)行其備份任務(wù)。

(2)

ProgressScorei

(3)

1.2Late調(diào)度算法

LATE算法是在Hadoop默認(rèn)推測(cè)執(zhí)行算法的基礎(chǔ)上，針對(duì)異構(gòu)集群提出的一種改進(jìn)算法，其思想是減少默認(rèn)推測(cè)執(zhí)行算法中執(zhí)行備份任務(wù)的數(shù)目，從而降低推測(cè)執(zhí)行帶來(lái)的不必要的資源消耗。

根據(jù)任務(wù)的執(zhí)行進(jìn)度推測(cè)出任務(wù)的完成時(shí)間，LATE算法中優(yōu)先執(zhí)行那些能夠在最快時(shí)間內(nèi)完成的備份任務(wù)。在LATE算法中設(shè)置了如下三個(gè)參數(shù)，來(lái)實(shí)現(xiàn)控制備份任務(wù)執(zhí)行數(shù)目。

1)SpeculateCap：備份任務(wù)總數(shù)的閥值。若同一時(shí)間內(nèi)系統(tǒng)中運(yùn)行的備份任務(wù)的總數(shù)大于該閥值，則不能進(jìn)行備份任務(wù)的執(zhí)行；

2)SlowNodeThreshold：慢節(jié)點(diǎn)判斷的閥值。若節(jié)點(diǎn)的處理速率小于該閥值，則判定節(jié)點(diǎn)為慢節(jié)點(diǎn)。

3)SlowTaskThresHold：掉隊(duì)者任務(wù)判斷的閥值。若任務(wù)的執(zhí)行速率小于該閥值，則判定任務(wù)為掉隊(duì)者任務(wù)。

LATE算法中根據(jù)公式(4)計(jì)算任務(wù)的運(yùn)行速率 ，其中 按照Hadoop默認(rèn)推測(cè)執(zhí)行算法計(jì)算，T是任務(wù)已經(jīng)運(yùn)行的時(shí)間。然后根據(jù)公式(5)計(jì)算任務(wù)的剩余時(shí)間。

(4)

(5)

LATE算法的工作流程如下：

1)如果有一個(gè)節(jié)點(diǎn)請(qǐng)求新的任務(wù)，判斷全局備份任務(wù)數(shù)是否大于SpeculateCap值，若大于該值則返回結(jié)束推測(cè)執(zhí)行算法，否則進(jìn)行下一步。

3)對(duì)正在執(zhí)行的任務(wù)(不包括已經(jīng)在備份執(zhí)行的任務(wù))計(jì)算其預(yù)計(jì)完成時(shí)間并排序，選擇預(yù)計(jì)完成時(shí)間最小且任務(wù)執(zhí)行速率低于SlowTaskThresHold的任務(wù)，執(zhí)行其備份任務(wù)。

2算法描述

2.1估算任務(wù)進(jìn)度

本文算法受到文獻(xiàn)[7]的啟發(fā)，利用TaskTracker記錄的任務(wù)運(yùn)行歷史信息，計(jì)算各作業(yè)的任務(wù)階段耗時(shí)比例。并且加入自校正的思想，即當(dāng)有新的任務(wù)運(yùn)行完后，會(huì)及時(shí)的針對(duì)該任務(wù)所屬的作業(yè)進(jìn)行階段耗時(shí)比例的更新。SMAR算法相對(duì)于LATE算法能夠更合理的估算出任務(wù)各階段的耗時(shí)比例，但是由于其沒(méi)有考慮不同類型作業(yè)的特性、處理數(shù)據(jù)的大小，會(huì)造成估算結(jié)果的不準(zhǔn)確。本文利用任務(wù)運(yùn)行歷史信息的進(jìn)行了更小粒度的計(jì)算，針對(duì)每個(gè)作業(yè)進(jìn)行階段耗時(shí)比例預(yù)估計(jì)算。

每個(gè)TaskTracker需要在任務(wù)成功運(yùn)行后記錄其執(zhí)行階段的相關(guān)信息，根據(jù)任務(wù)的類型分為兩種：Map任務(wù)的執(zhí)行階段相關(guān)信息MapTaskInfo(JobId，TaskId，MP1，MP2)，Reduce任務(wù)的執(zhí)行階段相關(guān)信息ReduceTaskInfo(JobId，TaskId，RP1，RP2，RP3)。其中JobID和TaskID分別是任務(wù)所屬作業(yè)的全局ID號(hào)、作業(yè)中該任務(wù)的ID號(hào)。MP1、MP2分別代表Map任務(wù)的map階段和combine階段的耗時(shí)比例，RP1、RP2、RP3分別代表Reduce任務(wù)的copy、sort和reduce階段的耗時(shí)比例。每當(dāng)TaskTracker向JobTracker周期發(fā)送心跳信息時(shí)，會(huì)將TaskTracker上新完成的任務(wù)的執(zhí)行階段信息一并發(fā)送。JobTracker在接受到心跳信息后，會(huì)在歷史記錄模塊中添加這些新完成任務(wù)的信息，然后更新各任務(wù)的階段耗時(shí)比例值，用于任務(wù)進(jìn)度的判斷。

每當(dāng)TaskTracker中有任務(wù)運(yùn)行結(jié)束后，會(huì)將該任務(wù)的運(yùn)行情況記錄為MapTaskInfo或RedcueTaskInfo記錄在本地磁盤上，然后發(fā)送給TaskTracker。例如MapTask1運(yùn)行完畢，會(huì)將(001，001，0.65，0.35)記錄下來(lái)并發(fā)送給TaskTracker。TaskTracker則會(huì)周期性的向JobTrakcer發(fā)送心跳信息，JobTracker受到心跳信息后會(huì)解析出任務(wù)的MapTaskInfo和ReduceTaskInfo。解析出后根據(jù)作業(yè)ID對(duì)各個(gè)作業(yè)的Map任務(wù)、Reduce任務(wù)的階段耗時(shí)比進(jìn)行更新。由于在未有任務(wù)完成之前，MP1、MP2、RP1、RP2、RP3采用默認(rèn)值1、0、0.6、0.3、0.1。當(dāng)每次JobTrakcer收到心跳信息且MapTaskInfo和ReduceTaskInfo中有內(nèi)容時(shí)則進(jìn)行階段耗時(shí)比例的更新操作。更新操作的具體方式是對(duì)同一作業(yè)的Map任務(wù)和Redcue任務(wù)的同一階段的耗時(shí)進(jìn)行平均值處理。例如MapTask1運(yùn)行結(jié)束后，由于開始沒(méi)有其他任務(wù)運(yùn)行結(jié)束，則JobTrakcer會(huì)對(duì)MapTask1對(duì)應(yīng)的001作業(yè)的Map任務(wù)的階段耗時(shí)比值進(jìn)行更新，更新為MP1=(1+0.65)/2=0.83，MP2=(0+0.35)/2=0.17。

通過(guò)對(duì)歷史信息的分析與自學(xué)習(xí)更新操作，可以更加精確的確定各個(gè)作業(yè)的不同階段比例耗時(shí)。

那么在此基礎(chǔ)上，我們可以更精準(zhǔn)的計(jì)算任務(wù)的進(jìn)度。將Map任務(wù)和Reduce任務(wù)的進(jìn)度分開計(jì)算，公式如下：

MapProcessScorej=

(6)

(7)

(8)

通過(guò)公式(6)、(7)可以分別計(jì)算出Map中任務(wù)和Reduce任務(wù)的進(jìn)度。公式中的任務(wù)各階段耗時(shí)比例值由JobTracker通過(guò)對(duì)任務(wù)的歷史信息自學(xué)習(xí)計(jì)算得到，N是任務(wù)要處理數(shù)據(jù)中鍵值對(duì)的數(shù)目，M是已經(jīng)處理了的數(shù)據(jù)的數(shù)目。最后，通過(guò)根據(jù)作業(yè)類型由公式(8)可以確定任務(wù)的進(jìn)度。

2.2定位掉隊(duì)者任務(wù)

在Hadoop推測(cè)執(zhí)行算法中，若一個(gè)任務(wù)的進(jìn)度值低于所有運(yùn)行任務(wù)進(jìn)度的平均值，且差值大于一個(gè)固定的閾值，則此任務(wù)判定為掉隊(duì)者任務(wù)。在LATE算法中通過(guò)任務(wù)運(yùn)行的速率對(duì)任務(wù)的運(yùn)行時(shí)間進(jìn)行預(yù)估，選擇剩余時(shí)間最大的任務(wù)進(jìn)行備份執(zhí)行。但是其沒(méi)有考慮實(shí)際運(yùn)行中任務(wù)的不同批次問(wèn)題。例如一個(gè)map任務(wù)task1已經(jīng)運(yùn)行了90%，預(yù)估的剩余時(shí)間為100s，同時(shí)運(yùn)行著map任務(wù)task2，其實(shí)在task1任務(wù)運(yùn)行了一段時(shí)間后才獲得資源開始調(diào)度，運(yùn)行進(jìn)度只有30%，預(yù)估剩余時(shí)間為200s。那么按照LATE算法則會(huì)選擇task2進(jìn)行備份執(zhí)行。這種不考慮任務(wù)運(yùn)行批次的調(diào)度方式是不符合實(shí)際情況的，不能真正的定位到需要備份執(zhí)行的strggler任務(wù)。本文通過(guò)結(jié)合任務(wù)速率和任務(wù)剩余預(yù)估時(shí)間兩個(gè)因素，從而完成掉隊(duì)者任務(wù)的判定。

CA153是人乳腺癌患者的組織碎片及細(xì)胞質(zhì)中提取的糖類抗原物質(zhì)，屬于乳腺癌相關(guān)抗原, 對(duì)乳腺癌患者隨診有一定意義，主要用于治療后監(jiān)測(cè)乳腺癌患者的疾病復(fù)發(fā)和轉(zhuǎn)移。有研究表明[9]，較高水平的CA153可作為乳腺癌可靠的預(yù)后標(biāo)記，與晚期和復(fù)發(fā)直接相關(guān)。此外，在乳腺癌患者中，CA153的持續(xù)升高與HER2陽(yáng)性相關(guān)。CA153也可用于轉(zhuǎn)移性乳腺癌的輔助診斷, 乳腺癌術(shù)后CA153陽(yáng)性率可達(dá)80%,肝、骨處轉(zhuǎn)移可引起血清CA153顯著升高。CA153對(duì)早期乳腺癌的敏感性及特異性較差，可潛在地用于檢測(cè)高危人群乳腺癌的發(fā)生。

在計(jì)算任務(wù)的運(yùn)行速率時(shí)，本文只考慮正在運(yùn)行階段的運(yùn)行速率。因?yàn)橐淹瓿傻碾A段已經(jīng)沒(méi)有預(yù)估價(jià)值，而未進(jìn)入的階段則由于過(guò)于復(fù)雜且有隨機(jī)性是無(wú)法預(yù)估的。所以本文只考慮正在運(yùn)行階段的速率。

ProgressSpeed=ProgressScore/T

(9)

計(jì)算完任務(wù)的運(yùn)行速率之后，需要完成任務(wù)剩余時(shí)間的預(yù)估。剩余時(shí)間最長(zhǎng)(且運(yùn)行速率小于平均速率)的節(jié)點(diǎn)將會(huì)獲得最高的優(yōu)先級(jí)被執(zhí)行備份任務(wù)。

一個(gè)任務(wù)的剩余運(yùn)行時(shí)間是所有未完成階段的剩余運(yùn)行時(shí)間之和，本文將任務(wù)的剩余運(yùn)行時(shí)間劃分為正在運(yùn)行階段的剩余時(shí)間和未運(yùn)行階段的剩余時(shí)間兩部分。如果一個(gè)任務(wù)正運(yùn)行在階段cp(current phase)，則cp階段剩余時(shí)間由其剩余處理數(shù)據(jù)量和該階段運(yùn)行速率決定。然而，cp階段之后的各階段fp(follow phase)的剩余時(shí)間很難預(yù)估，因?yàn)槿蝿?wù)還未進(jìn)入這些階段。因此，我們使用階段平均進(jìn)程速率預(yù)估fp階段的剩余時(shí)間。階段平均運(yùn)行速率是指進(jìn)入該階段的所有進(jìn)程速率的平均值。如果某階段沒(méi)有任何任務(wù)已經(jīng)進(jìn)入，我們不計(jì)算其階段的時(shí)間，這對(duì)所有任務(wù)都是公平的。由于每個(gè)任務(wù)處理的數(shù)據(jù)量不一樣，計(jì)算fp階段的剩余時(shí)間需要考慮本任務(wù)的數(shù)據(jù)量和已進(jìn)入該階段任務(wù)的數(shù)據(jù)量的比例。可以通過(guò)公式求導(dǎo)出任務(wù)的剩余運(yùn)行時(shí)間：

(10)

掉隊(duì)者任務(wù)的選擇流程如下：

1)按公式算任務(wù)的運(yùn)行速率，如果運(yùn)行速率低于所有任務(wù)的平均速率，則進(jìn)行下一步；

2)計(jì)算任務(wù)的剩余運(yùn)行時(shí)間，將任務(wù)按剩余時(shí)間由大到小排序；

3)將剩余時(shí)間最大的任務(wù)判定為掉隊(duì)者任務(wù)。

2.3選擇執(zhí)行備份任務(wù)節(jié)點(diǎn)

在判定完掉隊(duì)者任務(wù)后，需要對(duì)掉隊(duì)者任務(wù)進(jìn)行備份執(zhí)行，即在另外一個(gè)節(jié)點(diǎn)上重新執(zhí)行該任務(wù)。但是由于在異構(gòu)的環(huán)境下，重新執(zhí)行掉隊(duì)者任務(wù)的節(jié)點(diǎn)的性能可能比當(dāng)前節(jié)點(diǎn)的性能更差，則會(huì)導(dǎo)致備份任務(wù)依舊會(huì)是一個(gè)掉隊(duì)者任務(wù)。這樣不僅不會(huì)提升作業(yè)的執(zhí)行時(shí)間，反而會(huì)消耗系統(tǒng)的可用資源。所以在選擇執(zhí)行備份任務(wù)節(jié)點(diǎn)的時(shí)候應(yīng)該過(guò)濾掉這種節(jié)點(diǎn)，下文稱之為慢節(jié)點(diǎn)。

在實(shí)際運(yùn)行環(huán)境中，由于Map任務(wù)和Reduce任務(wù)運(yùn)行的特點(diǎn)和階段都不相同，所以節(jié)點(diǎn)執(zhí)行Map任務(wù)和Reduce任務(wù)的速率也是不同的。LATE算法中僅僅在判定節(jié)點(diǎn)的快慢時(shí)沒(méi)有對(duì)任務(wù)的類型進(jìn)行區(qū)分，這樣對(duì)導(dǎo)致備份任務(wù)的執(zhí)行效率。本文針對(duì)此問(wèn)題將慢節(jié)點(diǎn)區(qū)分為：Map任務(wù)慢節(jié)點(diǎn)和Redcue任務(wù)慢節(jié)。

假設(shè)一個(gè)TaskTracker上運(yùn)行的Map任務(wù)數(shù)為 MapNum，運(yùn)行的Reduce任務(wù)數(shù)為 ReduceNum。根據(jù)公式(11)、(12)可以分別計(jì)算出該TaskTracker上Map任務(wù)和Reduce任務(wù)的平均運(yùn)行速率。

(11)

(12)

假設(shè)系統(tǒng)中運(yùn)行的TaskTracker的總數(shù)為TTNum，可以根據(jù)公式(13)、(14)分別計(jì)算出整個(gè)集群中Map任務(wù)和Reduce任務(wù)的平均運(yùn)行速率。

(13)

(14)

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

3.1實(shí)驗(yàn)環(huán)境

本實(shí)驗(yàn)集群的硬件采用10臺(tái)商用測(cè)試服務(wù)器，其分別部署在三個(gè)機(jī)架上，采用1gbps以太網(wǎng)連接。

其中，每臺(tái)服務(wù)器上部署了OpenStack云計(jì)算管理系統(tǒng)，并且采用KVM軟件負(fù)責(zé)劃分虛擬機(jī)資源。每個(gè)虛擬機(jī)配置 2個(gè)虛擬核，4gb內(nèi)存，40GB磁盤空間。由于其具備異構(gòu)的特點(diǎn)，所以通過(guò)在每臺(tái)服務(wù)器上劃分不同數(shù)目的虛擬機(jī)來(lái)模擬異構(gòu)的運(yùn)行環(huán)境，具體如表1所示。

表1　集群虛擬機(jī)配置表

3.2不同負(fù)載性能驗(yàn)證

本節(jié)通過(guò)在異構(gòu)Hadoop集群中運(yùn)行三種不同類型的作業(yè)，對(duì)Hadoop默認(rèn)推測(cè)算法、LATE算法、本文提出的ISSL算法進(jìn)行了實(shí)驗(yàn)，并對(duì)比分析了實(shí)驗(yàn)結(jié)果，驗(yàn)證了本文算法在異構(gòu)環(huán)境下能夠減小作業(yè)的執(zhí)行時(shí)間、有效提升系統(tǒng)吞吐WordCount、Sort、Grep是Hadoop中最典型的三類作業(yè)，可以代表Hadoop中最常用的各類作業(yè)。本節(jié)分別針對(duì)這三類類型不同的作業(yè)，對(duì)Hadoop默認(rèn)推測(cè)執(zhí)行算法、LATE算法和本文算法進(jìn)行實(shí)驗(yàn)。每一類實(shí)驗(yàn)都運(yùn)行6次，為了減小隨機(jī)因素的影響，本文對(duì)每次實(shí)驗(yàn)用例結(jié)果的最好、最差、平均情況都進(jìn)行了統(tǒng)計(jì)。由于每次實(shí)驗(yàn)中作業(yè)類型相同且輸入數(shù)據(jù)量相等，本文和文獻(xiàn)[12]采用同樣的方式度量系統(tǒng)的吞吐率，即系統(tǒng)每秒處理作業(yè)的數(shù)量。

3.2.1WordCount測(cè)試

WordCount作業(yè)用于計(jì)算輸入文件中各單詞的出現(xiàn)的次數(shù)，是Hadoop中最常處理的作業(yè)。本實(shí)驗(yàn)測(cè)試用例的輸入文件大小為8GB，每隔30s提交一個(gè)WordCount作業(yè)，一共提交6次。

圖1是三種算法執(zhí)行Wordcount作業(yè)的實(shí)驗(yàn)結(jié)果，其中(a)是三種算法的作業(yè)執(zhí)行時(shí)間的結(jié)果對(duì)比圖，(b)是三種算法執(zhí)行時(shí)系統(tǒng)吞吐量的結(jié)果對(duì)比圖。通過(guò)實(shí)驗(yàn)結(jié)果可以發(fā)現(xiàn)，本文提出的ISSL算法的在平均情況下，作業(yè)執(zhí)行時(shí)間比Late算法、Hadoop默認(rèn)算法降低了10%，而且相對(duì)于Late算法、Hadoop默認(rèn)執(zhí)行算法分別提升了5%、6%的系統(tǒng)吞吐率。

在WordCount作業(yè)中，本文算法針對(duì)作業(yè)的執(zhí)行時(shí)間及系統(tǒng)吞吐量?jī)蓚€(gè)方面并沒(méi)有獲得很明顯的提升。因?yàn)樽鳂I(yè)處理的是純文本文件，間接數(shù)據(jù)和最終輸出的數(shù)據(jù)會(huì)比較小，所以WordCount作業(yè)大部分時(shí)間用于在map階段，即CPU密集型作業(yè)。一旦Map任務(wù)運(yùn)行結(jié)束，Reduce任務(wù)只需要很短的時(shí)間。因此，wordcount作業(yè)的性能由Map任務(wù)的執(zhí)行效率決定。由于wordcount作業(yè)中map任務(wù)的平均執(zhí)行時(shí)間只有70s，在快的節(jié)點(diǎn)上執(zhí)行和在慢的節(jié)點(diǎn)上執(zhí)行差異不大，所以導(dǎo)致提升度比較小。

(a)作業(yè)執(zhí)行時(shí)

(b)系統(tǒng)吞吐量

3.2.2Sort測(cè)試

Sort作業(yè)主要是對(duì)點(diǎn)擊率排序等，其和wordcount作業(yè)有著很大的不同，其Map任務(wù)會(huì)產(chǎn)生的大量中間數(shù)據(jù)會(huì)通過(guò)網(wǎng)絡(luò)傳遞到Reduce任務(wù)節(jié)點(diǎn)，同時(shí)Reduce任務(wù)產(chǎn)生的結(jié)果數(shù)據(jù)也比較大，并需要寫到磁盤上。因此，Sort作業(yè)屬于I/O密集型作業(yè)。測(cè)試用例采用的得數(shù)據(jù)集是點(diǎn)擊率文件，大小為30GB。每一個(gè)sort作業(yè)有100個(gè)reduce任務(wù)，本文每個(gè)150s提交一個(gè)作業(yè)，一共提交3次。

下頁(yè)圖2是三種算法執(zhí)行Sort作業(yè)的實(shí)驗(yàn)結(jié)果，其中(a)是三種算法的作業(yè)執(zhí)行時(shí)間的結(jié)果對(duì)比圖，其中(b)是三種算法執(zhí)行時(shí)系統(tǒng)吞吐量的結(jié)果對(duì)比圖。本文提出額ISSL算法的作業(yè)平均執(zhí)行時(shí)間低于LATE算法19%，低于Hadoop默認(rèn)算法37%。并且本文提出的ISSL算法相對(duì)于LATE算法、Hadoop默認(rèn)算法分別提高了15%、32%的系統(tǒng)吞吐量。

在作業(yè)執(zhí)行時(shí)間和系統(tǒng)吞吐量?jī)蓚€(gè)方面，本文算法ISSL在處理sort作業(yè)時(shí)相較于Wordcount作業(yè)都獲得了很大的提升，主要是由于sort作業(yè)中reduce任務(wù)的工作量大于map任務(wù)，mao任務(wù)只占據(jù)了整個(gè)作業(yè)執(zhí)行時(shí)間的一小部分。在map和reduce階段，本文算法有更多的機(jī)會(huì)執(zhí)行高效的推測(cè)任務(wù)，導(dǎo)致更高的吞吐量。

(a)作業(yè)執(zhí)行時(shí)間

(b)系統(tǒng)吞吐量

3.2.3Grep測(cè)試用例

Grep作業(yè)主要是在輸入文件中通過(guò)正則匹配找到包含指定串的表達(dá)式，當(dāng)表達(dá)式出現(xiàn)的比較頻繁時(shí)，Grep作業(yè)類似于Sort作業(yè)，是一個(gè)I/O密集型作業(yè)；當(dāng)表達(dá)式出現(xiàn)很稀疏時(shí)，Grep作業(yè)者類似wordcount作業(yè)，是一個(gè)CPU密集型作業(yè)。本用例的測(cè)試輸入文件大小為23g，每個(gè)150s提交一個(gè)作業(yè)，一共提交3次。

圖3是三種算法執(zhí)行Grep作業(yè)的實(shí)驗(yàn)結(jié)果，其中(a)是三種算法的作業(yè)執(zhí)行時(shí)間的結(jié)果對(duì)比圖，(b)是三種算法執(zhí)行時(shí)系統(tǒng)吞吐量的結(jié)果對(duì)比圖。通過(guò)實(shí)驗(yàn)結(jié)果可以發(fā)現(xiàn)，在平均情況下，相對(duì)于LATE算法、Hadoop默認(rèn)執(zhí)行算法，本文提出的ISSL分別降低了39%、48%的作業(yè)執(zhí)行時(shí)間，提升了38%、42%的系統(tǒng)吞吐量。

在Grep作業(yè)中，map任務(wù)工作量大于Sort作業(yè)中map任務(wù)的工作量，平均執(zhí)行時(shí)間是sort任務(wù)的1.3倍。因此，推測(cè)執(zhí)行針對(duì)map任務(wù)可以取得更好的效果。

(a)作業(yè)執(zhí)行時(shí)間

(b)系統(tǒng)吞吐量

通過(guò)上述三種不同類型的實(shí)驗(yàn)，可以發(fā)現(xiàn)本文算法相對(duì)于Hadoop默認(rèn)推測(cè)執(zhí)行算法、LATE算法，均能有效的降低作業(yè)的執(zhí)行時(shí)間，提升系統(tǒng)的吞吐率。這些性能的提升主要是由于本文算法通過(guò)新的進(jìn)度估算方式提升了掉隊(duì)者任務(wù)的判定準(zhǔn)確性，這樣會(huì)避免系統(tǒng)執(zhí)行不必要的備份任務(wù)，浪費(fèi)系統(tǒng)的資源。同時(shí)，本文算法相對(duì)于LATE算法在選擇執(zhí)行備份任務(wù)的節(jié)點(diǎn)時(shí)進(jìn)行了更細(xì)粒度的區(qū)分，使不同類型的任務(wù)在最適合的快節(jié)點(diǎn)上執(zhí)行，從而提升了備份任務(wù)的執(zhí)行效率，減小整個(gè)作業(yè)的執(zhí)行時(shí)間。并且，在多次試驗(yàn)中最差、平均、最壞的情況下，本文算法的性能都優(yōu)于Hadoop默認(rèn)算法、LATE算法，證明本算法是非常穩(wěn)定的。

4結(jié)束語(yǔ)

伴隨大數(shù)據(jù)時(shí)代的到來(lái)，Hadoop云平臺(tái)的使用場(chǎng)景不斷擴(kuò)展，通過(guò)對(duì)Hadoop資源調(diào)度框架的研究本文構(gòu)建了資源預(yù)估模型，在此基礎(chǔ)上對(duì)作業(yè)調(diào)度算法的推測(cè)執(zhí)行算法進(jìn)行了改進(jìn)。由于Hadoop的不斷發(fā)展，下一步將針對(duì)實(shí)時(shí)調(diào)度及數(shù)據(jù)放置策略等進(jìn)行研究。

參考文獻(xiàn)

[1]K Kambatla, A Pathak, and H. Proc. of the First Workshop on Hot Topics in Cloud Computing: Pucha.Towards optimizing hadoop provisioning in the cloud[C]. Washington DC, 2009.

[2]林闖,蘇文博,孟坤,等. 云計(jì)算安全:架構(gòu)、機(jī)制與模型評(píng)價(jià)[J]. 計(jì)算機(jī)學(xué)報(bào),2013(9):1765-1784.

[3]孟小峰,慈祥. 大數(shù)據(jù)管理:概念、技術(shù)與挑戰(zhàn)[J]. 計(jì)算機(jī)研究與發(fā)展,2013(1):146-169.

[4]H. Chang, M. Kodialam, R. Kompella, T. Lakshman, et al. INFOCOM 2011 Proceedings IEEE :Scheduling in mapreduce-like systems for fast completion time[C]. Inforcm,2011.

[5]欒亞建,黃翀民,龔高晟,等. Hadoop平臺(tái)的性能優(yōu)化研究[J]. 計(jì)算機(jī)工程,2010(14):262-266.

[6]Daewoo Lee,Jin-Soo Kim,Seungryoul Maeng. Large-scale incremental processing with MapReduce[J]. Future Generation Computer Systems,2013,10:130-139.

[7]Huo Tang, Junqing Zhou, Kenli Li, et al. A MapReduce task scheduling algorithm for deadline constraints[J]. Cluster Computing,2013,164:109-112.

[8]Wei Dai,Mostafa Bassiouni. An improved task assignment scheme for Hadoop running in the clouds[J]. Journal of Cloud Computing,2013,21：231-240.

[9]Ezerra A，Hernndez P，Espinosa A，et a1．Proc of the 20th European MPI Use Group Meeting :Job scheduling for optimizing data locality in Hadoop clusters[C]． ACM Press,2013．

[10]Zhuo Tang, Junqing Zhou, Kenli Li,et al. A MapReduce task scheduling algorithm for deadline constraints[J]. Cluster Computing,2013:164-173.

[11]Z Guo, G Fox, M Zhou. IEEE International Conference :Improving Resource Utilization in MapReduce[C]. Washington DC ,2012.

[12]N Maheshwari, R Nanduri, V Varma. Future Generation Computer Systems :Dynamic energy efficient data placement and cluster reconfiguration algorithm for MapReduce framework[C]. IEEE Computer Society,2012.

Improved Speculated Scheduling Algorithm Based on LATE of Hadoop Cloud Platform

LUHui1,GAOHong-bo1,ZHANGFeng-man1,WANGMei1,ZHAIJia-yi1,XIAOZhen2

(1.SoftwareTestingCenter,ChengduTextileCollege,Chengdu611731;2.WuhanDataCenter,ChinaConstructionBank,Wuhan430070)

Abstract:In order to improve the limitation of speculated scheduling algorithm of Hadoop cloud platform, a new task process algorithm based on LATE was proposed and notes of backup task were selected by adopting more fine-grained way. The experiment results showed that such algorithm could more accurately select the stragglers and choose proper executing mote, shorten executing time and improve the efficiency of cloud platform.

Key words:Hadoopcloud platformLATE algorithmstraggler

中圖分類號(hào)：TP393

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1008-5580(2016)02-0200-07

基金項(xiàng)目：基于云計(jì)算的蜀錦蜀繡綜合服務(wù)平臺(tái)(2012FZ0081)

收稿日期：2015-12-20

第一作者：盧慧(1970-),女,碩士,高級(jí)講師,研究方向：云計(jì)算、大數(shù)據(jù)分析、物聯(lián)網(wǎng)。