一種Hadoop Yarn的資源調(diào)度方法研究

李媛禎,楊　群,賴尚琦,李博涵

(1.南京航空航天大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院,江蘇南京 210016;2.香港大學(xué)計算機(jī)科學(xué)與技術(shù)系,香港)

?

一種Hadoop Yarn的資源調(diào)度方法研究

李媛禎1,楊群1,賴尚琦2,李博涵1

(1.南京航空航天大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院,江蘇南京 210016;2.香港大學(xué)計算機(jī)科學(xué)與技術(shù)系,香港)

針對Hadoop Yarn資源調(diào)度問題,為提高集群作業(yè)執(zhí)行效率,提出一種基于蟻群算法與粒子群算法的自適應(yīng)Hadoop資源調(diào)度算法SRSAPH.SRSAPH中,通過Hadoop Yarn跳通信機(jī)制獲取負(fù)載、內(nèi)存、CPU速度等屬性信息初始化信息素矩陣;同時,將粒子群算法的自我認(rèn)知能力與社會認(rèn)知能力引入到蟻群算法,提高算法的收斂速度;此外,根據(jù)蟻群算法全局最優(yōu)解的波動趨勢動態(tài)調(diào)整信息素?fù)]發(fā)系數(shù),提高解的精度.實驗表明,采用SRSAPH進(jìn)行資源調(diào)度,集群的作業(yè)執(zhí)行時間縮短至少10%.

資源調(diào)度;蟻群算法;粒子群算法;Hadoop Yarn

1　引言

自2006年Yahoo發(fā)布Hadoop平臺以來,越來越多的應(yīng)用程序采用Hadoop作為處理平臺.要發(fā)揮Hadoop的作用,合理進(jìn)行資源分配和調(diào)度是關(guān)鍵問題之一[1,2].在最新Hadoop Yarn中,為解決主節(jié)點(diǎn)故障、資源分配不合理等問題,采用資源調(diào)度器取代原有的任務(wù)調(diào)度器,Hadoop Yarn調(diào)度器以層級隊列方式組織資源,并讓這些隊列共享所有節(jié)點(diǎn)上的資源.當(dāng)節(jié)點(diǎn)上存在空閑資源時,節(jié)點(diǎn)NM向調(diào)度器發(fā)送空閑資源通知.調(diào)度器實際是一個事件處理器,處理來自其他組件的事件,從而統(tǒng)一管理和調(diào)度集群資源,其中,提供了三個內(nèi)置調(diào)度算法,實現(xiàn)了三種資源調(diào)度器,即FIFO,Capacity和Fair調(diào)度器.但是,由于應(yīng)用的多樣性,這些調(diào)度器并不能很好地滿足用戶合理分配資源與減低作業(yè)執(zhí)行時間的需求[3,4].

資源調(diào)度問題是一個NP難問題,采用傳統(tǒng)的調(diào)度算法并不能很好地分配系統(tǒng)資源,由于智能算法是求解最優(yōu)化問題的一種有效手段,為得到資源分配問題的最優(yōu)解,本文采用智能優(yōu)化算法設(shè)計和實現(xiàn)Hadoop Yarn資源調(diào)度器以達(dá)到降低集群作業(yè)執(zhí)行時間的目標(biāo).

2　相關(guān)工作

由于資源調(diào)度的重要性,自Hadoop出現(xiàn)以來,工業(yè)界和學(xué)術(shù)界圍繞其調(diào)度問題進(jìn)行了大量工作[5～14].例如:Sandholm[7]將資源分配過程分解成許多個可以在NA (Autonomous Node Agents)上以MCDA (Multiple Criteria Decision Analysis)方式并行執(zhí)行的獨(dú)立任務(wù),提高了資源分配的效率,但算法只考慮了硬件資源約束且實現(xiàn)復(fù)雜,限制了方法的可擴(kuò)展性.Zhao[8]提出了一種適用于分布式系統(tǒng)的線性矩陣不等式資源調(diào)度算法,但該算法的適用范圍小且實際應(yīng)用意義不大.Ergu[9]提出了一種面向任務(wù)的資源調(diào)度算法,然而異常元素的不確定性降低了該算法的準(zhǔn)確度,尤其是異構(gòu)環(huán)境中,使用偏差矩陣方法易使正常元素誤識為異常元素.

相較于上述傳統(tǒng)算法,智能優(yōu)化算法因其求解組合優(yōu)化問題的有效性,在資源調(diào)度領(lǐng)域應(yīng)用更廣.Merkle[12]采用一種基于蟻群算法的資源調(diào)度模型,提高了啟發(fā)式因子在后代信息素?fù)]發(fā)變化率上的影響力度,但信息素的大量堆積易造成算法陷入局部最優(yōu)解而降低算法的尋優(yōu)能力.Yin[13]的調(diào)度策略有效降低算法的停滯性,然而,算法的性能會隨著問題復(fù)雜度的提高而降低,且該算法僅適應(yīng)于受限資源環(huán)境.Chang[14]提出了一種基于蟻群算法的均衡資源調(diào)度算法,通過全局信息素更新與局部信息素更新機(jī)制達(dá)到資源負(fù)載平衡的效果,以便減小作業(yè)執(zhí)行總時間.但算法將作業(yè)執(zhí)行時間作為已知量參與計算,實際環(huán)境下作業(yè)執(zhí)行時間是無法通過現(xiàn)有方法進(jìn)行精確計算的,這在一定程度上降低了資源分配方案的可信度與準(zhǔn)確性.

基于上述分析,本文針對目前最新的Hadoop Yarn提出一種基于蟻群算法和粒子群算法[15]的自適應(yīng)資源調(diào)度算法(SRSAPH).首先,針對蟻群算法雖具有較好的尋優(yōu)能力但收斂速度慢且易陷入局部最優(yōu)解的不足,將蟻群算法與粒子群算法認(rèn)知能力相結(jié)合,彌補(bǔ)了蟻群算法在收斂速度慢上的缺陷;然后,根據(jù)全局信息素的波動趨勢動態(tài)調(diào)整信息素?fù)]發(fā)系數(shù),避免信息素大量堆積,以此提高蟻群算法的全局搜索能力,避免陷入局部最優(yōu)解,最后設(shè)計SRSARH算法資源調(diào)度器,通過信息素評價集群資源,為每個空閑資源尋求最優(yōu)的分配策略,從而達(dá)到降低集群作業(yè)執(zhí)行時間的目標(biāo).

3　基于蟻群算法和粒子群算法的自適應(yīng)Hadoop資源調(diào)度算法

3.1集群環(huán)境描述

集群環(huán)境模型表示為G={A,R,J,C},其中,A為螞蟻的集合;R為節(jié)點(diǎn)資源集合;J為作業(yè)集,C為容器集.具體特征描述如下:

資源集合R={R1,R2,…,Rn}由n個節(jié)點(diǎn)及其資源構(gòu)成,其中,第i個節(jié)點(diǎn)上的資源Ri={cpuSpeedi,Mi,resMi,loadi}.cpuSpeedi為節(jié)點(diǎn)i上的CPU運(yùn)行速率,節(jié)點(diǎn)i的總資源量用Mi表示,resMi為節(jié)點(diǎn)i的空閑資源量,resMi≤Mi,0≤i

作業(yè)集J={J1,J2,…,Js}表示當(dāng)前集群上運(yùn)行的作業(yè)量為s,第j個作業(yè)Jj={resTotalJj,resTotalMJj,progj},0≤j

容器集C={C1,C2,…,Ct}由t個容器構(gòu)成,表示集群中所有申請了資源的容器集合,第m個容器Cm={Jm,j,resMCm},0≤j

3.2SRSAPH算法模型

本文將蟻群算法應(yīng)用于資源調(diào)度問題,算法各參數(shù)與資源調(diào)度各參數(shù)的對應(yīng)關(guān)系如下.

定義1(資源分配)?Ri∈R,Cm∈C,如果資源Ri可以滿足容器Cm的調(diào)度要求,則記為Θ(Ri,Cm)>0,表示允許Ri為容器Cm分配資源以執(zhí)行任務(wù).滿足容器Cm的資源Ri可能有多個,為實現(xiàn)集群最大程度的性能優(yōu)化,Cm以概率pi,m被調(diào)度到資源Ri上.

定義2(信息素矩陣)信息素矩陣由一個n×t維矩陣構(gòu)成,記為PHn×t=(phi,m)n×t,其中,矩陣元素phi,m(0≤i

定義5(容器允許矩陣)容器允許矩陣由一個n×t維矩陣構(gòu)成,記為ATn×t=(yi,m)n×t.對于矩陣元素yi,m,如果Θ(Ri,Cm)>0,則yi,m=1,否則yi,m=0.因為同一個容器最多只能在一個資源上啟動,所以容器對應(yīng)的禁忌矩陣元素與允許矩陣元素之和不能大于1,該約束條件表示為式(1)、式(2),如下所示.同時,假設(shè)容器Cm申請在資源Ri上啟動,那么容器Cm所需資源量不能大于資源Ri上的實際空閑資源量,該約束條件表示為式(3),如下所示.

總之,為保證容器的資源請求被順利響應(yīng),需要滿足約束條件式(1),(2);為了保證資源Ri所接受的容器在其可執(zhí)行范圍內(nèi),需要滿足約束條件式(3);

(1)

?xi,m∈TB,yi,m∈AT,xi,m+yi,m≤1

(2)

(3)

定義6(終止條件)為保證集群正常運(yùn)行,文中規(guī)定:當(dāng)算法滿足約束條件(4)或(5)時,單個螞蟻的一次迭代過程結(jié)束.

當(dāng)為Ri選擇容器分配資源時,為避免Ri因無法選擇到滿足調(diào)度條件的容器而陷入死循環(huán),算法增加了控制參數(shù)attemptContainer,每次選擇容器后attemptContainer加1,當(dāng)算法中控制參數(shù)attemptContainer≥3或滿足約束條件(5)或(6)時,資源Ri的分配操作結(jié)束.

(4)

(5)

(6)

3.3SRSAPH算法思想

本文提出的SRSAPH算法中,螞蟻表示調(diào)度者,負(fù)責(zé)分配資源給申請資源的容器以獲取資源分配方案.下面詳細(xì)介紹本文算法的具體流程.

(1)初始化信息素

根據(jù)Hadoop資源調(diào)度框架,本文設(shè)計并實現(xiàn)了一個資源調(diào)度器,通過該資源調(diào)度器從NM(NodeManager)獲取節(jié)點(diǎn)CPU速率、作業(yè)失敗記錄、內(nèi)存容量及負(fù)載情況等信息,在獲取全部相關(guān)信息后計算各容器在節(jié)點(diǎn)上的執(zhí)行能力,并將結(jié)果以信息素值的形式存儲于信息素矩陣,完成信息素矩陣PHn×t=(phi,m)n×t的初始化.其中,phi,m表示容器Cm在資源Ri上所展現(xiàn)出的執(zhí)行能力,由節(jié)點(diǎn)CPU速率、內(nèi)存、容器所屬作業(yè)失敗記錄的相對權(quán)重和乘Ri資源剩余利用率計算而來,其表達(dá)式如公式(7):

(7)

(8)

上述公式中:failNotem,j代表Cm所屬作業(yè)Jj在節(jié)點(diǎn)Ri上的失敗記錄;a,b,c均為常數(shù),分別對應(yīng)節(jié)點(diǎn)CPU速率、內(nèi)存、容器所屬作業(yè)失敗記錄的權(quán)重值,且a+b+c=1.對于單個節(jié)點(diǎn),作業(yè)失敗的概率很小,所以c的值設(shè)定為0.1.a,b的取值由作業(yè)類型決定:對于計算密集型任務(wù),CPU對任務(wù)執(zhí)行能力的影響更大,本文設(shè)定a=0.6,b=0.3,c=0.1;而對于數(shù)據(jù)密集型任務(wù),內(nèi)存對任務(wù)執(zhí)行能力的影響更顯著,故設(shè)定a=0.3,b=0.6,c=0.1.對于具體的作業(yè)任務(wù)可以進(jìn)一步調(diào)節(jié)參數(shù)以優(yōu)化調(diào)度效果.節(jié)點(diǎn)上任務(wù)執(zhí)行失敗因子ψ為常數(shù),表示節(jié)點(diǎn)上執(zhí)行失敗的任務(wù)對后續(xù)節(jié)點(diǎn)資源的影響.

(2)狀態(tài)轉(zhuǎn)移概率

一次迭代過程中,資源的分配由多次“節(jié)點(diǎn)-容器”操作完成.“節(jié)點(diǎn)-容器”操作即為:首先螞蟻antk(0≤k0,則Ri為Cm分配資源同時修改xi,m=1;反之則重新選擇容器,直到滿足約束條件(5)或(6).antk在t時刻選擇Cm的轉(zhuǎn)移概率為:

pi,m(t+1)=

(9)

上式中,針對蟻群算法尋解收斂速度慢問題,改進(jìn)的狀態(tài)轉(zhuǎn)移概率機(jī)制引入粒子速度更新時的三要素:慣性、自身認(rèn)知、社會認(rèn)知.與傳統(tǒng)蟻群算法相比,蟻群算法狀態(tài)轉(zhuǎn)移概率機(jī)制中第一部分信息素量phi,m(t)代表資源i相較于容器m的信息素量,即“慣性”;而第二部分啟發(fā)式期望信息素分為兩步進(jìn)行:自身認(rèn)知期望信息素與社會認(rèn)知期望信息素.下面對改進(jìn)的狀態(tài)轉(zhuǎn)移概率更新機(jī)制中三部分進(jìn)行詳細(xì)介紹:

(Ⅰ)phi,mα(t):螞蟻資源分配的“慣性”部分,反映了在選擇容器時Ri受當(dāng)前信息素的影響能力;phi,m(t)代表Ri選擇Cm的信息素;α為信息啟發(fā)式因子,表示信息素的相對重要性.

(Ⅱ)[c1r1|EPl-progm,j(t)|]β:螞蟻“自身認(rèn)知”部分,表示螞蟻本身的思考;c1為加速常數(shù),表示螞蟻對自身經(jīng)驗的認(rèn)知能力,調(diào)節(jié)螞蟻選擇優(yōu)于自身的容器;r1為隨機(jī)數(shù);EPl為螞蟻尋解所得方案的局部最優(yōu)解;progm,j(t)表示Cm所屬作業(yè)Jj的運(yùn)行進(jìn)度;β為自我認(rèn)知期望啟發(fā)式因子,表示progm,j與局部最優(yōu)解偏差的自我認(rèn)知能力,progm,j(t)距EPl的偏差越大,progm,j(t+1)越大,越傾向于選擇當(dāng)前Cm.

(Ⅲ) [c2r2|EPg-progm,j(t)|]γ:螞蟻“社會認(rèn)知”部分,表示螞蟻間社會信息共享;c2為加速常數(shù),表示螞蟻對社會經(jīng)驗的認(rèn)知能力,調(diào)節(jié)螞蟻選擇傾向全局最優(yōu)解發(fā)展的容器;r2為隨機(jī)數(shù);EPg為螞蟻尋解所得全局最優(yōu)解;γ為社會認(rèn)知期望啟發(fā)式因子,表示progm,j(t) 與全局最優(yōu)解偏差的社會認(rèn)知能力,progm,j(t)與EPg的偏差越大,progm,j(t+1)越大,越傾向于選擇當(dāng)前Cm.

由公式(9)可知,antk每次選擇容器時,若容器Cm與資源Ri所對應(yīng)的信息素phi,m越大,則容器被選擇的概率越大.同時,當(dāng)作業(yè)進(jìn)度progm,j(t)與全局最優(yōu)解EPg、局部最優(yōu)解EPl間的偏差較大時,亦會增加Cm被選擇的可能性.這在一定程度上避免了作業(yè)進(jìn)度較低且信息素不具優(yōu)勢的容器長時間不被選擇而降低集群作業(yè)集進(jìn)度的情況.

(3)自適應(yīng)信息素更新機(jī)制

當(dāng)滿足終止條件式(4)或式(5)時,螞蟻antk一次迭代結(jié)束,根據(jù)下式(10)計算當(dāng)前所得解的目標(biāo)函數(shù)EPk的值:

(10)

(11)其中:ωj代表Jj運(yùn)行進(jìn)度權(quán)重值,計算方法如公式(11).

將當(dāng)前解分別與局部最優(yōu)解、全局最優(yōu)解作比較,如果當(dāng)前解優(yōu)于局部最優(yōu)解和全局最優(yōu)解,則用當(dāng)前解更新局部最優(yōu)解和全局最優(yōu)解,否則不更新.具體更新機(jī)制如下:(1)當(dāng)?shù)螖?shù)小于8時,揮發(fā)系數(shù)ρ設(shè)為定值0.3[16];(2)當(dāng)?shù)螖?shù)大于或等于8時,采用自適應(yīng)信息素更新機(jī)制.如果連續(xù)8次迭代中全局最優(yōu)解的變化趨于平穩(wěn),適當(dāng)增大信息素?fù)]發(fā)系數(shù),反之減小信息素?fù)]發(fā)系數(shù).以上更新只對本次迭代所得解決方案中包含的資源分配項進(jìn)行.

上述自適應(yīng)信息素更新機(jī)制可分為下述三步進(jìn)行:(1)收集antk最近連續(xù)8次迭代解決方案作業(yè)進(jìn)度EPk;(2)計算目標(biāo)函數(shù)的標(biāo)準(zhǔn)差σ以求得動態(tài)揮發(fā)系數(shù)ρa(bǔ)nt;(3)將ρa(bǔ)nt代入公式(14)更新信息素.接下來詳細(xì)介紹自適應(yīng)更新機(jī)制.

在獲取連續(xù)8次作業(yè)進(jìn)度EPk后,算法計算目標(biāo)函數(shù)的標(biāo)準(zhǔn)差σ,計算公式如下:

(12)

將σ代入公式(13)計算動態(tài)揮發(fā)系數(shù)ρa(bǔ)nt,計算公式如下:

(13)

其中,調(diào)控參數(shù)ε為常量.若算法計算所得目標(biāo)函數(shù)的標(biāo)準(zhǔn)差較小時,即算法尋解過程趨于穩(wěn)定,由式(13)計算所得的動態(tài)信息素?fù)]發(fā)系數(shù)ρa(bǔ)nt較大(0<ρa(bǔ)nt<1),反之亦然.自適應(yīng)信息素更新機(jī)制正是通過調(diào)節(jié)信息素的揮發(fā)量來增強(qiáng)螞蟻的全局搜索能力,避免螞蟻陷入局部最優(yōu)解.

接下來,算法利用ρa(bǔ)nt更新信息素,計算公式(14)如下所示:

ifΓ(Ri,Cm)>0

(14)

(15)

其中:ρa(bǔ)nt表示信息素?fù)]發(fā)系數(shù);flagm表示Cm的狀態(tài).Δph(t)表示信息素增量,代表螞蟻在本次迭代搜索中留在資源分配項上的信息量.

由公式(14)可知,信息素的更新只在Γ(Ri,Cm)>0的條件下進(jìn)行.這是因為,Hadoop中,若一個容器所申請資源已獲批準(zhǔn),但容器尚未被應(yīng)用程序管理者注銷,此時容器仍會進(jìn)入下一次資源調(diào)度申請,而所申請資源即為零.當(dāng)容器所申請資源量為零時,容器狀態(tài)設(shè)為F,反之即為T.對于Γ(Ri,Cm)>0,若flagm=T,信息素的更新不僅包括信息素的揮發(fā),還包括信息素積累量的增加,反之只進(jìn)行信息素的揮發(fā).

由(15)可以看出,算法在分配資源時更趨向于選擇大容器.在分配集群資源時,如果將空閑資源大量分配給小容器會產(chǎn)生大量小容量資源碎片,大容量容器無法搜尋到滿足條件的資源量,造成資源浪費(fèi).公式(14),(15)所示的信息素更新方式可以避免上述問題,從而在集群性能允許的范圍內(nèi)最大程度的將資源分配給容器.

4　實驗

資源調(diào)度是一個NP難問題,解決此類問題,蟻群算法是一種較優(yōu)的解決方案[17，18].本文在蟻群算法的基礎(chǔ)上引入粒子群算法,設(shè)計并實現(xiàn)了SRSAPH算法.以下介紹本文實驗,并對結(jié)果進(jìn)行分析.

4.1實驗環(huán)境及參數(shù)設(shè)置

實驗硬件環(huán)境為8臺主機(jī)構(gòu)成的Hadoop異構(gòu)集群,主要參數(shù)為:螞蟻個數(shù)NUM=20,信息素影響力因子α=1.0,啟發(fā)式信息素影響因子β=0.8,γ=0.8,加速常數(shù)c1=c2=0.5,隨機(jī)數(shù)r1=r2=2,每次進(jìn)行資源調(diào)度時蟻群算法執(zhí)行的迭代次數(shù)itrStep=1000,以上參數(shù)均根據(jù)前人研究成果,取通用經(jīng)驗值[19].節(jié)點(diǎn)上任務(wù)執(zhí)行失敗因子ψ表示同一作業(yè)中任務(wù)在節(jié)點(diǎn)上執(zhí)行失敗的情況,受任務(wù)數(shù)量與嘗試啟動次數(shù)的限制,故ψ取10.為使動態(tài)揮發(fā)系數(shù)ρa(bǔ)nt能夠充分發(fā)揮其信息素調(diào)整作用,故調(diào)控參數(shù)ε取100.

本文選取4種Hadoop基準(zhǔn)實例為測試對象,包括PI、WordCount、Sort及Grep實例.文中對比實驗的選取依據(jù)如下:(1)圍繞Hadoop資源調(diào)度所進(jìn)行的工作集中在HadoopYarn發(fā)布之前,HadoopYarn發(fā)布以后其自身提供的默認(rèn)調(diào)度器更具有代表性;(2)本文所提的算法是基于蟻群算法進(jìn)行的.因此,本文對比實驗對象為HadoopYarn提供的默認(rèn)Capacity調(diào)度器和前人實現(xiàn)的HadoopACO調(diào)度器(以下簡稱ACO調(diào)度器)[20].

本文實驗將從下面三方面分析本文SRSAPH算法的實驗結(jié)果:(1)作業(yè)集的平均時間、最優(yōu)時間、最差時間的對比;(2)SRSAPH算法在作業(yè)集執(zhí)行過程中所占成本分析;(3)作業(yè)重復(fù)運(yùn)行20次中執(zhí)行時間的波動趨勢.其中,平均時間取作業(yè)集重復(fù)運(yùn)行20次的執(zhí)行時間的平均值.

4.2實驗與結(jié)果分析

下面對實驗結(jié)果所獲得的數(shù)據(jù)進(jìn)行對比與分析.

(1)作業(yè)集執(zhí)行時間對比

表1　四種測試對象在不同作業(yè)量下的實驗結(jié)果

(b)WordCount實例在不同作業(yè)集下的執(zhí)行時間

(c)Sort實例在不同作業(yè)集下的執(zhí)行時間

(d)Grep實例在不同作業(yè)集下的執(zhí)行時間

表1列出8節(jié)點(diǎn)集群下,采用SRSAPH、ACO與Capacity調(diào)度器處理不同規(guī)模的測試對象所展示出的實驗性能.表1(a)中,N/M1*M2表示作業(yè)集由N個M1* M2的作業(yè)組成,其中M1*M2表示每單位范圍內(nèi)投擲的點(diǎn)總數(shù),M1為map數(shù)量,M2為每個map中投擲的點(diǎn)數(shù).表1(b)中,WordCount實驗測試數(shù)據(jù)為2013年11月中國新聞匯總,下載自數(shù)據(jù)堂網(wǎng)站[21].每個作業(yè)處理一天的數(shù)據(jù)信息,每一天的信息數(shù)據(jù)由至少500個txt文檔組成,每個文檔對應(yīng)一個map任務(wù),故每個作業(yè)在執(zhí)行時需創(chuàng)建并處理至少500個map.表1(c)中,利用RandomWrite生成不同數(shù)量的數(shù)據(jù),然后使用Sort實例來進(jìn)行排序.表1(d)中,Grep實例測試數(shù)據(jù)為7、14、21與28天的新聞數(shù)據(jù)經(jīng),處理后放入HDFS指定文檔中,然后對指定文檔中指定單詞的詞頻進(jìn)行計算.

為了更形象的展示不同調(diào)度器在集群上的執(zhí)行效果,現(xiàn)選取表1(a)，(b)，(c)，(d)中平均時間作柱狀圖,如圖1中(a)，(b)，(c)，(d).由表1可知,與ACO、Capacity調(diào)度器相比,SRSAPH的作業(yè)集執(zhí)行時間更短.在圖1(a)中4/20*20與圖1(c)中512M情況下,SRSAPH與ACO、Capacity的平均執(zhí)行時間相差不大,這是因為小作業(yè)中的任務(wù)執(zhí)行時間短,且在此情況下集群內(nèi)存未被完全消耗.隨著作業(yè)量的增加,SRSAPH的優(yōu)勢逐漸體現(xiàn)出來.如圖1(a)中8/200*200、圖1(b)中4個WordCount、圖1(c)中3096M數(shù)據(jù)集及圖1(d)中由28天新聞數(shù)據(jù)組成的數(shù)據(jù)集,此時集群的負(fù)載處于超額狀態(tài),此時,集群資源競爭激烈,合理的分配策略可以有效的降低作業(yè)的執(zhí)行時間.故SRSAPH的平均執(zhí)行時間比ACO、Capacity的更短,從而可證明SRSAPH算法具有較好的求解效果.

綜合表1與圖1可知,在集群負(fù)載滿額的情況下,Capacity作業(yè)執(zhí)行時間急劇增長,且SRSAPH比ACO具有更好的實驗性能效果.

(2)SRSAPH資源調(diào)度成本分析

本文SRSAPH調(diào)度器下,作業(yè)集的執(zhí)行時間可以分為前期迭代設(shè)計資源分配方案時間和后期作業(yè)運(yùn)行時間.圖2中作業(yè)執(zhí)行時間與前期額外成本時間均為平均時間.從圖2(a)，圖2(c)中可以看出,4/20*20下,前期額外成本時間至少為12s,而512M數(shù)據(jù)下,前期額外成本時間至少為30s,占總執(zhí)行時間的比例至少為20%.從圖2可知,(a)中8/200*200作業(yè)下額外成本時間所占比例為31s,(b)中8個WordCount作業(yè)下為62s,(c)中3096M數(shù)據(jù)集下為70s,(d)中由28天新聞數(shù)據(jù)組成的作業(yè)集下為65s,占總執(zhí)行時間的比例最大為8%.隨著作業(yè)的增大,占總執(zhí)行時間的比例明顯減小,且集群作業(yè)量在一定范圍內(nèi)時,前期額外成本時間變化不大.綜合圖2可知,SRSAPH在處理較大規(guī)模作業(yè)時所表現(xiàn)出的性能更優(yōu).

(3)調(diào)度器的穩(wěn)定性對比

為了觀察作業(yè)完成時間的波動趨勢,了解SRSAPH的穩(wěn)定性,實驗分別從4種測試對象中選取一組含有任務(wù)數(shù)量相似的作業(yè),即8個200*200作業(yè)、4個WordCount作業(yè)、3096M數(shù)據(jù)及28天新聞數(shù)據(jù)作業(yè)集,在不同調(diào)度器條件下運(yùn)行并分析執(zhí)行20次的時間變化趨勢.

由圖3(a),(b),(c),(d)可知,隨著任務(wù)數(shù)量的增加,Capacity的波動幅度增大,圖3(a)中6點(diǎn)、18點(diǎn),圖3(b)中3點(diǎn)、6點(diǎn)、7點(diǎn)、16點(diǎn),圖3(c)中6點(diǎn)、13點(diǎn)、16點(diǎn)及圖3(d)中7點(diǎn)、19點(diǎn)均為奇異點(diǎn),在這些點(diǎn)上,Capacity的執(zhí)行時間相對較長且與前后點(diǎn)的差值急劇增大,這是因為Capacity的每個隊列在分配資源時采用的是先到先得方式,若將任務(wù)分配給性能較差的節(jié)點(diǎn),則集群作業(yè)執(zhí)行時間較長,反之較短,這時系統(tǒng)作業(yè)執(zhí)行時間所表現(xiàn)出的性能差距較大;而SRSAPH與ACO采用智能優(yōu)化算法分配資源,根據(jù)集群的實際物理情況,動態(tài)調(diào)優(yōu),使系統(tǒng)資源性能盡量達(dá)到最優(yōu),但是SRSAPH有效的解決了ACO中容易陷入局部最優(yōu)解的缺陷,故SRSAPH的波動率始終較小.故相較于ACO與Capacity,SRSAPH的作業(yè)執(zhí)行時間基本趨于平穩(wěn),最優(yōu)時間與最差時間波動較小,具有較好的魯棒性.

從上述實驗分析中可以得出,本文SRSAPH算法的性能均優(yōu)于Capacity調(diào)度器與ACO調(diào)度器,是一種行之有效的Hadoop資源分配策略.

5　結(jié)論

本文針對Hadoop環(huán)境下資源調(diào)度問題,提出了一種基于蟻群算法和粒子群算法的自適應(yīng)Hadoop資源調(diào)度算法.本文算法主要特點(diǎn)表現(xiàn)在:(1)算法較全面的考慮了各個因素對信息素的影響,包括節(jié)點(diǎn)內(nèi)存、負(fù)載、CPU速率及容器所屬作業(yè)在節(jié)點(diǎn)上失敗率,對整個集群性能做出較為系統(tǒng)的評估,以此指導(dǎo)螞蟻資源探索過程;(2)引入粒子群算法更新規(guī)則中的三要素:粒子慣性、自身經(jīng)驗、社會經(jīng)驗,吸收了其精度高、收斂快的特點(diǎn),提高了蟻群算法的收斂速度,結(jié)合Hadoop環(huán)境下資源調(diào)度的特性,設(shè)計適合Hadoop下資源請求與分配的調(diào)度器;(3)針對蟻群算法易陷入局部最優(yōu)解的弊端,本文引入自適應(yīng)揮發(fā)因子,當(dāng)算法波動較大時,揮發(fā)系數(shù)較小,而當(dāng)算法分配方案的波動趨于穩(wěn)定時,揮發(fā)系數(shù)增大,從而動態(tài)調(diào)整揮發(fā)系數(shù)以避免算法陷入局部最優(yōu)解.通過實驗證明,根據(jù)本文上述思想提出的算法SRSAPH資源調(diào)度器不僅降低了集群作業(yè)執(zhí)行時間,同時具有較好的魯棒性.

[1]Elghoneimy E,Bouhali O,Alnuweiri H.Resource allocation and scheduling in cloud computing[A].2012 International Conference on Computing,Networking and Communications[C].Hawaii:IEEE,2012.309-314.

[2]Gokilavani M,SelviS,Udhayakumar C.A survey on resource allocation and task scheduling algorithms in cloud environment[J].International Journal of Engineering and Innovative Technology,2013,3(4):173-179.

[3]Chauhan J.Simulation and performance evaluation of hadoop capacity scheduler[D].Saskatoon:University of Saskatchewan,2013:93-96.

[4]Fair Scheduler Guide[R/OL].http://hadoop.apache.org/common/docs/r0.20.2/fair_shcehduler.html,2013-08-04.

[5]Rasooli A,Down D G.A hybrid scheduling approach for scalable heterogeneous hadoop systems[A].2012 High Performance Computing,Networking,Storage and Analysis[C].Salt Lake City:IEEE,2012.1284-1291.

[6]Rasooli A,Down D G.COSHH:A classification and optimization based scheduler for heterogeneous Hadoop systems[J].Future Generation Computer Systems,2014,36(7):1-15.

[7]Yazir Y O,Matthews C,Farahbod R,et al.Dynamic resource allocation in computing clouds using distributed multiple criteria decision analysis[A].3thIEEE 2010 International Conference on Cloud Computing[C].Florida:IEEE,2010.91-98.

[8]Yue Z,Xu Q.Resource allocation and scheduling theory based on distributed environment[A].16thInternational Conference on Advanced Communication Technology[C].PyeongChang Korea:IEEE,2014.1124-1128.

[9]Ergu D,Kou G,Peng Y,et al.The analytic hierarchy process:task scheduling and resource allocation in cloud computing environment[J].The Journal of Supercomputing,2013,64(3):835-848.

[10]Senouci A B,Eldin N N.Use of genetic algorithms in resource scheduling of construction projects[J].Journal of Construction Engineering and Management,2004,130(6):869-877.

[12]Merkle D,Middendorf M,Schmeck H.Ant colony optimization for resource-constrained project scheduling[J].IEEE Transactions on Evolutionary Computation,2002,6(4):333-346.

[13]Yin P Y,Wang J Y.Ant colony optimization for the nonlinear resource allocation problem[J].Applied mathematics and computation,2006,174(2):1438-1453.

[14]Chang R S,Chang J S,Lin P S.An ant algorithm for balanced job scheduling in grids[J].Future Generation Computer Systems,2009,25(1):20-27.

[15]Gandomi A H,Yun G J,Yang X S,et al.Chaos-enhanced accelerated particle swarm optimization[J].Communications in Nonlinear Science and Numerical Simulation,2013,18(2):327-340.

[16]Chaharsooghi S K,Meimand Kermani A H.An effective ant colony optimization algorithm (ACO) for multi-objective resource allocation problem (MORAP)[J].Applied Mathematics and Computation,2008,200(1):167-177.

[17]Achary R,Vityanathan V,Raj P,et al.Dynamic Job Scheduling Using Ant Colony Optimization for Mobile Cloud Computing[M].Switzerland:Springer International Publishing,2015:71-82.

[18]Zhang Z,Zhang N,Feng Z.Multi-satellite control resource scheduling based on ant colony optimization[J].Expert Systems with Applications,2014,41(6):2816-2823.

[19]Dorigo M,Blum C.Ant colony optimization theory:A survey[J].Theoretical Computer Science,2005,344(1):243-278.

[20]Hengliang S,Guanyi B,Zhenmin T.Aco algorithm-based parallel job scheduling investigation on hadoop[J].International Journal of Digital Content Technology and Its Applications,2011,5(7):283-288.

[21]數(shù)據(jù)堂.2013年11月中國新聞匯總[DB/OL].http://www.datatang.com/data/45718,2013-12-23.

李媛禎女,1990年出生,碩士研究生,研究方向為資源調(diào)度、并行計算.

E-mail:liyuanzhen0724@163.com

楊群(通信作者)女,1971年出生,副教授,博士,研究方向為新型程序設(shè)計、軟件方法學(xué).

E-mail:qun.y@163.com

A Study on Scheduling Method of Hadoop Yarn

LI Yuan-zhen1,YANG Qun1,LAI Shang-qi2,LI Bo-han1

(1.ComputerScienceandTechnologyCollege,NanjingUniversityofAeronauticsandAstronautics,Nanjing,Jiangsu210016,China; 2.DepartmentofComputerScience,TheUniversityofHongKong,HongKong,China)

In view of the resource scheduling problem of Hadoop Yarn,to improve the execution efficiency of the cluster job,we propose a Self-adapt Resource Scheduling algorithm based on Ant Colony Algorithm and Particle Swarm Algorithm in Hadoop (SRSAPH).In SRSAPH,we initialize the pheromone matrix of SRSAPH by using the attribute information of load,memory,and CPU speed obtained through the heartbeat message transfer mechanism.Meanwhile,we introduce the self-cognitive ability and social cognition ability of particle swarm algorithm into the ant colony algorithm to speed up the rate of convergence of the algorithm.Moreover,we dynamically adjust the pheromone evaporation rate based on the fluctuation trends of global optimal solution to enhance the accuracy of the solutions.Experimental result shows that by using SRSAPH in resource scheduling,the execution time of cluster job is shorten by 10%.

resource scheduling;ant colony algorithm;particle swarm algorithm;Hadoop Yarn

2014-11-15;

2015-04-09；責(zé)任編輯：馬蘭英

國家自然科學(xué)基金(No.41301407);江蘇省自然科學(xué)基金(No.BK20130819)

TP301.6

A

0372-2112 (2016)05-1017-08

電子學(xué)報URL:http://www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.05.002