基于蟻群算法的Storm集群資源感知任務調度

劉夢青，王少輝

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

基于蟻群算法的Storm集群資源感知任務調度

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

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

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

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

1 概 述

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

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

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

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

2 Storm默認調度策略

如圖1所示，在Storm集群中，用戶提交的程序稱為Topology，表現為有向無環圖，由Spout和Bolt構成。Spout和Bolt統稱為component，在集群中運行實例的單位是task。Topology啟動后，component的task數目固定不變。

圖1 用戶提交的Topology

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

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

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

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

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

(1)Supervisor1：T1，T4，T7；

(2)Supervisor2：T2，T5，T8；

(3)Supervisor3：T3，T6，T9。

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

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

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

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

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

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

3 基于蟻群算法的Storm任務調度

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

3.1Storm任務調度問題描述

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

(1)

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

3.2算法描述

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

Step1：初始化算法參數，設置各Supervisor節點的信息素；

Step2：設置算法的最大迭代次數；

Step3：將n只螞蟻隨機發送到m個節點上；

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

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

Step6：算法達到最大循環次數，輸出最優解，否則跳轉至Step3。

算法流程如圖2所示。

圖2 基于蟻群算法的Storm任務調度流程

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

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

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

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

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

(2)

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

τi=s×τi(t)

(3)

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

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

(4)

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

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

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

在算法運行過程中，螞蟻會根據啟發信息及信息素的濃度進行節點間的轉移。螞蟻h由節點i轉移到節點j的狀態轉移概率公式[12]如下：

(5)

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

(4)信息素更新。

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

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

(6)

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

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

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

(7)

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

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

(8)

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

4 實驗及分析

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

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

表1 集群硬件配置信息

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

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

表2 各Topology估計資源使用值

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

圖3 實驗結果

另外，從Ganglia的監控數據可以看到，在調用改進調度算法的過程中，集群中節點的CPU、內存、磁盤等使用都較為均衡，沒有出現過忙或過閑的節點，整個集群的負載較為均衡。

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

5 結束語

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

[1] 丁維龍,趙卓峰,韓燕波.Storm：大數據流式計算及應用實踐[M].北京:電子工業出版社,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] 鐘一文.智能優化方法及其應用研究[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] 黃亞平,熊 婧.基于改進蟻群算法作業車間調度問題仿真研究[J].計算機仿真,2009,26(8):278-282.

[12] 李德啟,田素貞.一種基于云環境下蟻群優化算法的改進研究[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">網絡出版時間

時間：2017-07-11

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

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

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