劉夢青，王少輝

(1.南京郵電大學(xué) 計(jì)算機(jī)學(xué)院，江蘇 南京 210003；2.江蘇省無線傳感網(wǎng)高技術(shù)研究重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210003)

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

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

(1.南京郵電大學(xué) 計(jì)算機(jī)學(xué)院，江蘇 南京 210003；2.江蘇省無線傳感網(wǎng)高技術(shù)研究重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210003)

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

Storm；資源感知；蟻群算法；負(fù)載均衡

1 概 述

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

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

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

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

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

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

圖1 用戶提交的Topology

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

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

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

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

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

(1)Supervisor1：T1，T4，T7；

(2)Supervisor2：T2，T5，T8；

(3)Supervisor3：T3，T6，T9。

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

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

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

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

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

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

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

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

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

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

(1)

其中，etij為第i個(gè)任務(wù)在第j個(gè)Supervisor節(jié)點(diǎn)上的預(yù)測完成時(shí)間，假設(shè)Topology的每個(gè)task的完成時(shí)間已經(jīng)預(yù)測得到。

3.2算法描述

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

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

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

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

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

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

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

算法流程如圖2所示。

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

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

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

在Storm中，Supervisor、Worker、executor等組件的心跳信息會(huì)同步至Zookeeper，Nimbus會(huì)周期性地利用Zookeeper上關(guān)于Supervisor的心跳信息得到Supervisor節(jié)點(diǎn)svi(i=1,2,…,m)的可用資源情況。分別用c,m,d,n代表節(jié)點(diǎn)的CPU、內(nèi)存、磁盤和網(wǎng)絡(luò)的信息素，并且每個(gè)參數(shù)的閾值定為c0，m0，d0，n0，即節(jié)點(diǎn)可提供資源的最大值，用于防止節(jié)點(diǎn)超負(fù)載。可將信息素初始化為：τic(0)=c/c0；τim(0)=m/m0；τid(0)=d/d0；τin(0)=n/n0。

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

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

(2)

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

τi=s×τi(t)

(3)

(2)任務(wù)預(yù)測完成時(shí)間。

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

(4)

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

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

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

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

(5)

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

(4)信息素更新。

當(dāng)有新的任務(wù)分配到節(jié)點(diǎn)上時(shí)，節(jié)點(diǎn)的資源被消耗，信息素值會(huì)隨之減少，此時(shí)信息素更新如下：

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

(6)

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

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

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

(7)

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

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

(8)

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

4 實(shí)驗(yàn)及分析

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

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

表1 集群硬件配置信息

主控節(jié)點(diǎn)Master上運(yùn)行Nimbus和Zookeeper守護(hù)進(jìn)程，從節(jié)點(diǎn)Slave上運(yùn)行Supervisor守護(hù)進(jìn)程，每個(gè)節(jié)點(diǎn)上的系統(tǒng)為Ubuntu 12.0.4，每個(gè)節(jié)點(diǎn)上配置4個(gè)slot。

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

表2 各Topology估計(jì)資源使用值

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

圖3 實(shí)驗(yàn)結(jié)果

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

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

5 結(jié)束語

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

[1] 丁維龍,趙卓峰,韓燕波.Storm：大數(shù)據(jù)流式計(jì)算及應(yīng)用實(shí)踐[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)化方法及其應(yīng)用研究[D].杭州：浙江大學(xué),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ìn)蟻群算法作業(yè)車間調(diào)度問題仿真研究[J].計(jì)算機(jī)仿真,2009,26(8):278-282.

[12] 李德啟,田素貞.一種基于云環(huán)境下蟻群優(yōu)化算法的改進(jìn)研究[J].陜西科技大學(xué)學(xué)報(bào):自然科學(xué)版,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)絡(luò)出版時(shí)間

時(shí)間：2017-07-11

國家自然科學(xué)基金資助項(xiàng)目(61572260)；江蘇省科技支撐計(jì)劃項(xiàng)目(BE2015702)

劉夢青(1992-),女,碩士研究生,研究方向?yàn)樾畔⑾到y(tǒng)的安全與隱私;王少輝,博士,副教授,研究方向?yàn)樾畔踩?、密碼學(xué)。

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