基于蟻群算法的Storm集群資源感知任務調(diào)度

劉夢青，王少輝

(1.南京郵電大學 計算機學院，江蘇 南京 210003；2.江蘇省無線傳感網(wǎng)高技術研究重點實驗室，江蘇 南京 210003)

基于蟻群算法的Storm集群資源感知任務調(diào)度

劉夢青1,2，王少輝1,2

(1.南京郵電大學 計算機學院，江蘇 南京 210003；2.江蘇省無線傳感網(wǎng)高技術研究重點實驗室，江蘇 南京 210003)

實時計算系統(tǒng)Storm是當前十分流行的開源流式系統(tǒng)，在處理流式數(shù)據(jù)時具有明顯的優(yōu)勢，但也存在默認調(diào)度器在任務調(diào)度時難以將節(jié)點資源與任務需求相結(jié)合、節(jié)點資源利用率不高、節(jié)點內(nèi)存不足以及網(wǎng)絡堵塞等問題。為了解決這些問題，提出了一種基于蟻群算法的Storm集群資源感知任務調(diào)度算法及其實現(xiàn)方案。該算法將節(jié)點的資源動態(tài)變化表示為螞蟻運動所需的信息素，將任務調(diào)度過程模擬為螞蟻覓食過程，以此對任務調(diào)度進行優(yōu)化，保證了Storm任務調(diào)度的有效性。實驗結(jié)果表明，該算法能夠找到與當前任務所需資源最匹配的節(jié)點，從而實現(xiàn)資源的合理分配；與默認調(diào)度相比，具有更優(yōu)的任務調(diào)度效率、更少的平均處理時間和更高的集群吞吐量，有利于集群負載均衡，優(yōu)化集群的性能。

Storm；資源感知；蟻群算法；負載均衡

1 概 述

隨著互聯(lián)網(wǎng)的快速發(fā)展和云計算等技術的興起，數(shù)據(jù)正以前所未有的速度暴增，數(shù)據(jù)處理問題成為了當前不可忽視的問題。其中以多源并發(fā)、數(shù)據(jù)匯聚、在線處理為特征的流式數(shù)據(jù)(Data Stream)，已經(jīng)成為當前的研究熱點。Storm是當前十分流行的分布式流式數(shù)據(jù)處理系統(tǒng)[1]，其強大的分布式集群管理、便捷的針對流式數(shù)據(jù)的編程模型、高容錯非功能保障，是它成為業(yè)界主流的首要原因。

為了能快速有效地處理數(shù)據(jù)，Storm集群中任務調(diào)度的合理設置十分關鍵。任務調(diào)度是Storm集群的重要組成部分，集群里有獨立存在的默認調(diào)度器(Scheduler)。集群在用戶提交作業(yè)(Topology)后，啟動調(diào)度器，將作業(yè)分配到工作節(jié)點中執(zhí)行。Storm集群的默認調(diào)度策略在判斷節(jié)點資源是否足夠時，更關注節(jié)點的CPU資源，而忽略內(nèi)存、磁盤、網(wǎng)絡等其他類型的節(jié)點資源，這樣有可能造成工作節(jié)點發(fā)生內(nèi)存不足、網(wǎng)絡堵塞等問題。另外，默認調(diào)度器沒能和任務的實際需求相結(jié)合，導致在任務調(diào)度的過程中，未能取得很好的調(diào)度效果。

對Storm默認調(diào)度算法改進的研究受到越來越多研究者的關注。Aniello等[2]設計了在線自適應調(diào)度器，通過監(jiān)控作業(yè)運行時間，減少節(jié)點間的通信來改善調(diào)度。該方案只在作者設計的作業(yè)中有效，不具備普遍性。Long等[3]針對作業(yè)的實際場景的不同來改進調(diào)度算法，如恢復歷史調(diào)度任務、單節(jié)點任務調(diào)度、資源需求調(diào)度等。Wang等[4]提出多層調(diào)度算法，通過減少組件的長尾時延(the long tail delay)來提高任務調(diào)度的效率。Eskandari等[5]提出了自適應分層調(diào)度算法，使得資源分配更加有效，并且提高了集群的性能。雖然這些改進對提高Storm集群的資源管理和任務調(diào)度具有一定的效果，但是并未考慮任務需求和當前集群資源相結(jié)合的問題，這是研究的著眼點。

任務調(diào)度是典型的NP-hard問題，通過模仿自然界生物行為特征的智能優(yōu)化算法，是解決這類問題的有效方法。常見的智能化任務調(diào)度算法有遺傳算法、微粒群算法、蟻群算法等[6]，其中蟻群算法在資源感知方面具有顯著的優(yōu)勢。為此，針對Storm集群默認調(diào)度不能對任務進行合理調(diào)度(即合理分配資源)的問題，結(jié)合蟻群算法對默認調(diào)度進行優(yōu)化，提出了基于蟻群算法的Storm資源感知任務調(diào)度算法。

2 Storm默認調(diào)度策略

如圖1所示，在Storm集群中，用戶提交的程序稱為Topology，表現(xiàn)為有向無環(huán)圖，由Spout和Bolt構(gòu)成。Spout和Bolt統(tǒng)稱為component，在集群中運行實例的單位是task。Topology啟動后，component的task數(shù)目固定不變。

圖1 用戶提交的Topology

Storm集群由一個主控節(jié)點Nimbus，多個協(xié)調(diào)節(jié)點Zookeeper和多個工作節(jié)點Supervisor組成，每個工作節(jié)點上都配置有slot數(shù)[7]。Storm的默認調(diào)度器Scheduler在主控節(jié)點上，負責為用戶提交上來的Topology分配資源，將任務分配到工作節(jié)點上。默認調(diào)度器的任務分配調(diào)度策略如下：

(1)在集群機器slot資源足夠的情況下，能均勻地將所有Topology的task分配到整個集群的所有工作節(jié)點上；

(2)當slot資源不夠時，會將所有Topology的task全部分配到僅有的slot上，由有限進程處理這些任務，此時的分配不理想。一旦出現(xiàn)新的空閑slot，又會重新分配Topology的task，以達到理想的狀態(tài)；

(3)沒有空閑slot，Nimbus什么也不做。

以圖1的Topology為例，假設此時集群有三個工作節(jié)點Supervisor，并且節(jié)點資源足夠，當用戶提交Topology后，默認調(diào)度器對任務的分配情況如下。

(1)Supervisor1：T1，T4，T7；

(2)Supervisor2：T2，T5，T8；

(3)Supervisor3：T3，T6，T9。

用戶提交的Topology中的components可分成三類：輸入層、計算層、輸出層，而每一層對資源的需求都不一樣[8]：

(1)輸入層：如果數(shù)據(jù)來自于磁盤，則需要更多的磁盤資源；若來自于網(wǎng)絡，則需要更多的帶寬資源。

(2)計算層：該層任務的特點是要進行大量的計算，消耗CPU資源，需要更多的CPU和內(nèi)存。

(3)輸出層：類似于輸入層，可能需要更多的磁盤將數(shù)據(jù)存入本地或者是更多網(wǎng)絡帶寬將數(shù)據(jù)傳輸給別的服務器。

Storm默認調(diào)度器在調(diào)度時沒能將集群節(jié)點所擁有的資源和任務的實際需求相結(jié)合，以致沒有取得很好的任務調(diào)度效果。另外，采用默認調(diào)度，在判斷資源分配是否均勻時，幾乎只考慮了節(jié)點的CPU使用情況，而節(jié)點其他類型的資源，比如內(nèi)存、磁盤、網(wǎng)絡等未做考慮。

若一個component屬于I/O密集型的輸入層，這種類型任務的特點是對網(wǎng)絡、磁盤資源消耗很多，CPU資源消耗很少，這類任務執(zhí)行期間99%的時間都花在I/O上，花在CPU上的時間很少。按照默認調(diào)度器，將其分配到某個工作節(jié)點上，很有可能該節(jié)點擁有的資源更多是CPU，而不是該component最需要的I/O資源，這必然會造成不合理的資源分配現(xiàn)象。也就是說，默認調(diào)度器實際上并不能均勻有效地分配資源，可能會造成Supervisor節(jié)點發(fā)生內(nèi)存不足、網(wǎng)絡堵塞等問題，對集群的性能造成嚴重影響。

3 基于蟻群算法的Storm任務調(diào)度

蟻群算法由Marco Dorigo等于1991年提出[9]，該算法是對自然界螞蟻的尋徑方式進行模擬而得出的一種仿生算法。經(jīng)過20多年的發(fā)展，蟻群算法廣泛應用于車間調(diào)度問題[10]、車輛路徑問題[11]、分配問題、決策支持以及仿真和系統(tǒng)辨別等領域，為這些NP-hard的組合優(yōu)化問題的解決提供了有效且高效的辦法。利用蟻群算法來解決Storm集群默認調(diào)度策略不能對資源進行合理分配的問題，提出基于蟻群算法的Storm資源感知任務調(diào)度算法，將Storm任務調(diào)度過程效仿螞蟻覓食過程，將任務比作螞蟻，對任務調(diào)度的過程進行優(yōu)化。

3.1Storm任務調(diào)度問題描述

在Storm平臺上，將一個Topology中的n個tasks分配到m個Supervisors工作節(jié)點上執(zhí)行(m

(1)

其中，etij為第i個任務在第j個Supervisor節(jié)點上的預測完成時間，假設Topology的每個task的完成時間已經(jīng)預測得到。

3.2算法描述

提出算法基于蟻群算法的思想，通過效仿螞蟻覓食的過程，將任務比作螞蟻，對任務調(diào)度的過程進行優(yōu)化，當螞蟻找到食物時，也意味著完成了任務分配。算法中通過計算節(jié)點的信息素濃度來決定分配給某任務的節(jié)點，并且總是選擇信息素最濃的節(jié)點即資源豐富的節(jié)點進行分配。該算法的執(zhí)行步驟如下：

Step1：初始化算法參數(shù)，設置各Supervisor節(jié)點的信息素；

Step2：設置算法的最大迭代次數(shù)；

Step3：將n只螞蟻隨機發(fā)送到m個節(jié)點上；

Step4：每只螞蟻根據(jù)預測時間閾值限制和節(jié)點選擇概率選擇下一節(jié)點；

Step5：當所有任務都分配完后，更新全局信息素，否則跳轉(zhuǎn)至Step4；

Step6：算法達到最大循環(huán)次數(shù)，輸出最優(yōu)解，否則跳轉(zhuǎn)至Step3。

算法流程如圖2所示。

圖2 基于蟻群算法的Storm任務調(diào)度流程

下面給出算法中涉及的一系列參數(shù)的設定方法。

(1)Supervisor節(jié)點的信息素表示。

在Storm中，Supervisor、Worker、executor等組件的心跳信息會同步至Zookeeper，Nimbus會周期性地利用Zookeeper上關于Supervisor的心跳信息得到Supervisor節(jié)點svi(i=1,2,…,m)的可用資源情況。分別用c,m,d,n代表節(jié)點的CPU、內(nèi)存、磁盤和網(wǎng)絡的信息素，并且每個參數(shù)的閾值定為c0，m0，d0，n0，即節(jié)點可提供資源的最大值，用于防止節(jié)點超負載?？蓪⑿畔⑺爻跏蓟癁椋害觟c(0)=c/c0；τim(0)=m/m0；τid(0)=d/d0；τin(0)=n/n0。

節(jié)點i的信息素是各信息素的帶權(quán)和，其中a,b,c,d(a+b+c+d=1)分別表示不同任務所需CPU、內(nèi)存、磁盤、網(wǎng)絡資源的權(quán)重。例如，對于內(nèi)存密集型任務，可適當增加內(nèi)存信息素所對應的權(quán)重b，此時，內(nèi)存資源相對豐富的節(jié)點更容易被選中。

τi(t)=aτic(0)+bτim(0)+cτid(0)+dτin(0)

(2)

在任務調(diào)度的過程中，很有可能出現(xiàn)這樣的情況：某些節(jié)點因為具備最優(yōu)資源(即最濃信息素)，一直被分配任務，始終處于過于忙碌狀態(tài)；而那些信息素濃度較低的節(jié)點可能一直都沒有分配到任務而處于閑置狀態(tài)，這樣也會造成負載不均衡的現(xiàn)象。為了解決這個問題，增加控制負載系數(shù)s=Sc/Ssum，Sc表示已經(jīng)完成的任務，Ssum表示任務的總量。因此，節(jié)點的信息素更新公式為:

τi=s×τi(t)

(3)

(2)任務預測完成時間。

在使用蟻群調(diào)度時，需計算出所有節(jié)點上每個任務的預測完成時間，生成ET矩陣，并將該矩陣作為蟻群算法的啟發(fā)信息之一。隨著任務不停地分配完成，還沒完成的任務隨之會減少，任務完成時間也會發(fā)生變化，因此，各任務的預測完成時間的更新公式定義為：

(4)

其中，ETjnpredict (Jpredict(t2))表示在t2時刻新任務Jpredict在j節(jié)點上的預測完成時間；npredict表示在t2時刻j節(jié)點上運行的任務數(shù)。

另外，為了判斷節(jié)點是否為有效節(jié)點，設置了一個有效區(qū)間，如果新任務的預測完成時間在該區(qū)間內(nèi)，則該節(jié)點為有效節(jié)點；如果節(jié)點是沒有分配過任務的節(jié)點，則需要根據(jù)節(jié)點的資源自動生成任務的預測完成時間，如果該時間在有效區(qū)間內(nèi)，則節(jié)點為有效節(jié)點。

(3)蟻群算法節(jié)點的選擇。

在算法運行過程中，螞蟻會根據(jù)啟發(fā)信息及信息素的濃度進行節(jié)點間的轉(zhuǎn)移。螞蟻h由節(jié)點i轉(zhuǎn)移到節(jié)點j的狀態(tài)轉(zhuǎn)移概率公式[12]如下：

(5)

經(jīng)過一段時間后，所有螞蟻都遍歷了所有的有效節(jié)點，并且有屬于自己的路徑Lh，將螞蟻當前所在節(jié)點列入禁忌表，計算時間最短的路徑Lhmin(minLh,h=1,2,…,m)，在該路徑上選擇信息素最濃的節(jié)點，將任務分配給該節(jié)點。

(4)信息素更新。

當有新的任務分配到節(jié)點上時，節(jié)點的資源被消耗，信息素值會隨之減少，此時信息素更新如下：

τi(t+n)=τi(t)-ρτi(t),0<ρ<1

(6)

其中，τi(t+n)為t+n時刻新任務到達i節(jié)點上的信息素濃度；τi(t)為節(jié)點i在時刻t的信息素濃度；ρ為調(diào)節(jié)因子。

當節(jié)點上的任務執(zhí)行完成(成功或者失敗)時，節(jié)點的資源便會被釋放，信息濃度也隨之增加，公式如下：

τi(t+m)=τi(t+n)+ρ1τi(t+n),0<ρ1<1

(7)

另外，增加一個調(diào)節(jié)因子ρ2，用來鼓勵成功執(zhí)行任務的節(jié)點或者是懲罰執(zhí)行任務失敗的節(jié)點，達到引導螞蟻行為的目的。

τi(t+m)=(1+ρ2)(τi(t+n)+ρ1τi(t+n))

(8)

如果執(zhí)行任務成功，則 0<ρ2<1；如果執(zhí)行任務失敗，則 -1<ρ2<0。

4 實驗及分析

在Storm0.8.0版本之后，Storm提供了可插拔的調(diào)度器(Pluggable Scheduler)[13]，可用于自定義任務的分配調(diào)度算法，以實現(xiàn)特定需求。該實驗利用Pluggable Scheduler實現(xiàn)自定義的調(diào)度。另外，用Ganglia[14]來監(jiān)控Storm集群的各節(jié)點狀態(tài)，如：CPU、內(nèi)存、硬盤利用率，I/O負載，網(wǎng)絡流量等。

實驗中，集群的環(huán)境配置由5臺物理機器組成，硬件配置如表1所示。

表1 集群硬件配置信息

主控節(jié)點Master上運行Nimbus和Zookeeper守護進程，從節(jié)點Slave上運行Supervisor守護進程，每個節(jié)點上的系統(tǒng)為Ubuntu 12.0.4，每個節(jié)點上配置4個slot。

相對于現(xiàn)有的改進方案，文中算法旨在改善任務需求和當前集群資源相結(jié)合中存在的問題，故設計了三個對資源種類需求不一樣的Topology。通過觀察執(zhí)行情況來分析該算法的使用情況。Topology_1屬于內(nèi)存密集型作業(yè)，Topology_2屬于網(wǎng)絡密集型作業(yè)，Topology_3屬于CPU密集型作業(yè)。數(shù)字1～10代表資源使用量，各作業(yè)的估計資源使用值如表2所示。

表2 各Topology估計資源使用值

先將3個不同Topology分別提交到Storm集群中，它們的平均處理時間如圖3所示?？梢园l(fā)現(xiàn)，在提交上去的三個作業(yè)中，開始階段節(jié)點可提供的資源都一樣，改進調(diào)度算法不如默認調(diào)度算法，執(zhí)行一段時間后，節(jié)點的可提供資源發(fā)生變化，這時改進調(diào)度算法表現(xiàn)得比默認算法要好很多，相對于默認調(diào)度算法，改進調(diào)度算法會將作業(yè)平均處理時間減少56.8%左右，并且隨著時間的推移逐漸穩(wěn)定，對提高作業(yè)的執(zhí)行效率具有很好的效果。接著，將三個Topology都提交到集群中，分別調(diào)用默認調(diào)度算法和改進調(diào)度算法對任務進行分配，最后收集每個Topology的吞吐量，結(jié)果如圖3所示?？梢园l(fā)現(xiàn)，和默認調(diào)度算法相比，改進調(diào)度算法可以明顯提高Topology的吞吐量，集群的整體吞吐量大概提高了37%。

圖3 實驗結(jié)果

另外，從Ganglia的監(jiān)控數(shù)據(jù)可以看到，在調(diào)用改進調(diào)度算法的過程中，集群中節(jié)點的CPU、內(nèi)存、磁盤等使用都較為均衡，沒有出現(xiàn)過忙或過閑的節(jié)點，整個集群的負載較為均衡。

由實驗結(jié)果可知，所提出的基于蟻群算法的資源感知調(diào)度算法，在調(diào)度執(zhí)行過程中節(jié)點資源和任務的實際需求資源更契合，不僅考慮到節(jié)點的CPU，還考慮到了節(jié)點的內(nèi)存、磁盤、網(wǎng)絡等資源，在減少Topology的平均處理時間和提高吞吐量方面具有比默認調(diào)度算法更好的表現(xiàn)，并且在Topology執(zhí)行期間，集群節(jié)點沒有超負載，集群負載較為均衡。

5 結(jié)束語

圍繞Storm集群任務調(diào)度問題，針對Storm默認調(diào)度不能解決不同任務在資源需求和占用上的差別和不能有效利用節(jié)點資源的問題，提出一種基于蟻群算法的資源感知算法。該算法將感知到的集群節(jié)點資源作為信息素，將要進行分配執(zhí)行的任務比作螞蟻，任務分配的過程類似螞蟻尋食的過程。資源越豐富的節(jié)點分配到更多的任務，優(yōu)化了任務分配過程，降低了任務平均完成時間，提高了集群的吞吐量。該算法在任務調(diào)度初期會耗費一些時間搜集信息素并進行迭代操作，因此如何減少時間是進一步研究的方向。

[1] 丁維龍,趙卓峰,韓燕波.Storm：大數(shù)據(jù)流式計算及應用實踐[M].北京:電子工業(yè)出版社,2015:27-33.

[2] Aniello L,Baldoni R,Querzoni L.Adaptive online scheduling in storm[C]//Proceedings of the 7th ACM international conference on distributed event-based systems.[s.l.]:ACM,2013:207-218.

[3] Long S,Rao R,Miao W,et al.An improved topology schedule algorithm for storm system[C]//Proceedings of the 2014 Asia-Pacific conference on computer science and applications.[s.l.]:CRC Press,2014:187-192.

[4] Wang J,Hang S,Liu J,et al.Multi-level scheduling algorithm based on Storm[J].KSII Transactions on Internet & Informa-tion Systems,2016,10(3):1091-1110.

[5] Eskandari L,Huang Z,Eyers D.P-Scheduler:adaptive hierarchical scheduling in apache storm[C]//Australasian computer science week multiconference.[s.l.]:ACM,2016:26-31.

[6] 鐘一文.智能優(yōu)化方法及其應用研究[D].杭州：浙江大學,2005.

[7] Toshniwal A,Taneja S,Shukla A,et al.Storm@twitter[C]//ACM SIGMOD international conference on management of data.[s.l.]:ACM,2014:147-156.

[8] Dena D, Bucicoiu M, Bardac M. A managed distributed processing pipeline with Storm and Mesos[C]//International conference on networking in education and research.[s.l.]:IEEE,2013:1-6.

[9] Dorigo M, Maniezzo V, Colomi A.The ant system:optimization by a colony of cooperation agents[J].IEEE Transactions on Systems,Man and Cybemetics,1996,26(1):29-41.

[10] 黃亞平,熊 婧.基于改進蟻群算法作業(yè)車間調(diào)度問題仿真研究[J].計算機仿真,2009,26(8):278-282.

[12] 李德啟,田素貞.一種基于云環(huán)境下蟻群優(yōu)化算法的改進研究[J].陜西科技大學學報:自然科學版,2012,30(1):64-68.

[13] Playmud.Twitter Storm的新利器Pluggable Scheduler[EB/OL].2012-05-21.http://blog.chinaunix.net/uid-233938-id-3216108.html.

[14] Massie M L,Chun B N,Culler D E.The ganglia distributed monitoring system:design,implementation,and experience[J].Parallel Computing,2004,30(7):817-840.

Research on Storm Resource-aware Task Scheduling with Ant Colony Algorithm

LIU Meng-qing1,2,WANG Shao-hui1,2

(1.College of Computer,Nanjing University of Posts and Telecommunications,Nanjing 210003,China;2. Key Laboratory of High Technology Research for Wireless Sensor Networks of Jiangsu Province,Nanjing 210003,China)

Storm is the popular open source real-time computing system,which has a great advantage in handling data stream.However,there are some problems in its default scheduler when scheduling tasks,such as difficultly in combining node resources and mission requirements,ineffectiveness in node resource utilization,lack of memory and network congestion and so on.In order to solve them,a resource-aware scheduler based on ant colony algorithm and its implementation scheme is proposed,in which the dynamic changes of the node resource can be expressed as the pheromones of ant movement required and the task scheduling process is similar to ant foraging process,to optimize the task scheduling and ensure the effectiveness of the Storm task scheduling.Experimental results show that it has found the most suitable node for the current task and achieved the reasonable allocation of resources and that compared with the default scheduling,it has better task scheduling efficiency,less average processing time and higher throughput of the cluster,which can benefit the load balance and optimize the performance for the cluster.

Storm;resource-aware;ant colony algorithm;load balance

2016-10-01

：2017-02-14 < class="emphasis_bold">網(wǎng)絡出版時間

時間：2017-07-11

國家自然科學基金資助項目(61572260)；江蘇省科技支撐計劃項目(BE2015702)

劉夢青(1992-),女,碩士研究生,研究方向為信息系統(tǒng)的安全與隱私;王少輝,博士,副教授,研究方向為信息安全、密碼學。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170711.1454.038.html

TP39

:A

:1673-629X(2017)09-0092-05

10.3969/j.issn.1673-629X.2017.09.020