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

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

?

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

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

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

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

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

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

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

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

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

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

1.1推測執(zhí)行過程

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

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

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

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

(1)

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

(2)

ProgressScorei

(3)

1.2Late調(diào)度算法

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

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

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

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

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

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

(4)

(5)

LATE算法的工作流程如下：

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

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

2算法描述

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

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

每個TaskTracker需要在任務(wù)成功運行后記錄其執(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號、作業(yè)中該任務(wù)的ID號。MP1、MP2分別代表Map任務(wù)的map階段和combine階段的耗時比例，RP1、RP2、RP3分別代表Reduce任務(wù)的copy、sort和reduce階段的耗時比例。每當(dāng)TaskTracker向JobTracker周期發(fā)送心跳信息時，會將TaskTracker上新完成的任務(wù)的執(zhí)行階段信息一并發(fā)送。JobTracker在接受到心跳信息后，會在歷史記錄模塊中添加這些新完成任務(wù)的信息，然后更新各任務(wù)的階段耗時比例值，用于任務(wù)進(jìn)度的判斷。

每當(dāng)TaskTracker中有任務(wù)運行結(jié)束后，會將該任務(wù)的運行情況記錄為MapTaskInfo或RedcueTaskInfo記錄在本地磁盤上，然后發(fā)送給TaskTracker。例如MapTask1運行完畢，會將(001，001，0.65，0.35)記錄下來并發(fā)送給TaskTracker。TaskTracker則會周期性的向JobTrakcer發(fā)送心跳信息，JobTracker受到心跳信息后會解析出任務(wù)的MapTaskInfo和ReduceTaskInfo。解析出后根據(jù)作業(yè)ID對各個作業(yè)的Map任務(wù)、Reduce任務(wù)的階段耗時比進(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)容時則進(jìn)行階段耗時比例的更新操作。更新操作的具體方式是對同一作業(yè)的Map任務(wù)和Redcue任務(wù)的同一階段的耗時進(jìn)行平均值處理。例如MapTask1運行結(jié)束后，由于開始沒有其他任務(wù)運行結(jié)束，則JobTrakcer會對MapTask1對應(yīng)的001作業(yè)的Map任務(wù)的階段耗時比值進(jìn)行更新，更新為MP1=(1+0.65)/2=0.83，MP2=(0+0.35)/2=0.17。

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

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

MapProcessScorej=

(6)

(7)

(8)

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

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

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

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

在計算任務(wù)的運行速率時，本文只考慮正在運行階段的運行速率。因為已完成的階段已經(jīng)沒有預(yù)估價值，而未進(jìn)入的階段則由于過于復(fù)雜且有隨機(jī)性是無法預(yù)估的。所以本文只考慮正在運行階段的速率。

ProgressSpeed=ProgressScore/T

(9)

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

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

(10)

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

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

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

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

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

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

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

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

(11)

(12)

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

(13)

(14)

3實驗及結(jié)果分析

3.1實驗環(huán)境

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

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

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

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

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

3.2.1WordCount測試

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

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

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

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

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

3.2.2Sort測試

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

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

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

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

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

3.2.3Grep測試用例

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

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

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

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

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

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

4結(jié)束語

伴隨大數(shù)據(jù)時代的到來，Hadoop云平臺的使用場景不斷擴(kuò)展，通過對Hadoop資源調(diào)度框架的研究本文構(gòu)建了資源預(yù)估模型，在此基礎(chǔ)上對作業(yè)調(diào)度算法的推測執(zhí)行算法進(jìn)行了改進(jìn)。由于Hadoop的不斷發(fā)展，下一步將針對實時調(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]林闖,蘇文博,孟坤,等. 云計算安全:架構(gòu)、機(jī)制與模型評價[J]. 計算機(jī)學(xué)報,2013(9):1765-1784.

[3]孟小峰,慈祥. 大數(shù)據(jù)管理:概念、技術(shù)與挑戰(zhàn)[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平臺的性能優(yōu)化研究[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

中圖分類號：TP393

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

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

基金項目：基于云計算的蜀錦蜀繡綜合服務(wù)平臺(2012FZ0081)

收稿日期：2015-12-20

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