(西安理工大學 自動化與信息工程學院，西安 710048)

0 引言

隨著大數(shù)據(jù)時代的到來和互聯(lián)網(wǎng)的飛速發(fā)展，我們生活中的一切都被數(shù)據(jù)所記錄，這些數(shù)據(jù)量已經(jīng)超過了我們的想象。為了分析和處理這些數(shù)據(jù)，學者們提出了許多種類的分布式框架，如Hadoop中的MapReduce框架等，但是大多數(shù)框架都是批處理框架。盡管這些框架擅長批處理，但其處理速度都難以保證延時低于5秒。這類批處理框架無法滿足許多項目當中對結(jié)果需要實時反饋的要求，這時Storm流計算框架應運而生。Storm是一個免費開源、分布式、高容錯的實時計算系統(tǒng)，可以使持續(xù)不斷的流計算變得容易，彌補了Hadoop批處理所不能滿足的實時要求；Storm經(jīng)常用于實時分析、在線機器學習、持續(xù)計算、分布式遠程調(diào)用和ETL等領(lǐng)域；Storm的部署管理簡單，而且Storm對于流數(shù)據(jù)處理的優(yōu)勢也是其它框架無法比擬的。

Apache Storm的默認任務調(diào)度機制是采用Round-Robin(輪詢)的方法，即Storm提交的拓撲作業(yè)按照總的任務數(shù)量平均分配給各個節(jié)點。其忽略了不同節(jié)點間的性能、負載及節(jié)點間的通信問題，使得各個節(jié)點間的資源不能充分利用。結(jié)果導致Storm工作時效率下降。所以Storm能夠合理快速的處理數(shù)據(jù)，其任務調(diào)度非常重要。針對Storm任務調(diào)度存在的優(yōu)化問題，國內(nèi)外已有學者對其進行研究。文獻[1]提出一個實現(xiàn)資源系統(tǒng)感知的資源調(diào)度優(yōu)化算法R-Storm，R-Storm是通過把資源分為兩類，針對內(nèi)存的計算資源和網(wǎng)絡(luò)的計算資源，根據(jù)兩種資源對不同節(jié)點的分配來實現(xiàn)調(diào)度任務，最終實現(xiàn)資源利用率最大化、提高總體吞吐量同時最小化網(wǎng)絡(luò)延遲。文獻[2]提出一個根據(jù)流量感知的資源調(diào)度優(yōu)化算法T-Storm，T-Storm利用加速數(shù)據(jù)處理用于分配和重新分配任務的有效流量感知調(diào)度，動態(tài)地減少節(jié)點間和進程間的流量，同時確保沒有工作節(jié)點過載。文獻[3]提出一種實時高效資源調(diào)度和優(yōu)化框架，稱為重新流(Re-Stream)，重新流描繪了能量消耗和響應之間的數(shù)學關(guān)系，利用分布式模型對數(shù)據(jù)流圖進行建模，重新分配利用高效的啟發(fā)式和關(guān)鍵路徑調(diào)度機制完成任務調(diào)度優(yōu)化。文獻[4]提出了一種低復雜度的隨機調(diào)度方法和優(yōu)化框架—云集群中的圖，這些圖表隨著時間的推移而變化，進而任務調(diào)度的優(yōu)化。文獻[5]提出一種分層階段調(diào)度算法，該算法是通過降低進程和進程節(jié)點與節(jié)點之間的開銷來完成優(yōu)化調(diào)度。文獻[6]提出了一種基于Topology的優(yōu)化調(diào)度策略。該策略比Storm自帶的默認調(diào)度策略擁有更高的流事件處理效率，且實施在分支結(jié)構(gòu)較多的Topology上效果比Storm默認調(diào)度策略更優(yōu)。文獻[7]提出了基于啟發(fā)式均衡圖劃分算法的調(diào)度策略，通過對Storm建立調(diào)度模型，將負載檢測作為調(diào)度器的輸入實現(xiàn)動態(tài)并行參數(shù)優(yōu)化和重調(diào)度優(yōu)化，最終減少集群節(jié)點間的數(shù)據(jù)發(fā)送率，并且保持節(jié)點間負載均衡。雖然以上這些算法對任務調(diào)度都有一定的效果，但是與各自還有些不足存在。

文獻[1，2，3]中的算法中的配置完全依賴工作人員去自己設(shè)定，不能通過算法自身反饋來獲得，不利于于實際應用；文獻[4]中的算法不能完全移植到storm系統(tǒng)當中；文獻[5]沒有考慮到自身計算開銷的大小；文獻[6]中的算法沒有考慮跨界點傳輸時的通信問題；文獻[7]再劃分圖時，沒有考慮慮頂點權(quán)重，負載均衡上存在問題。在已有文獻中對于Storm默認調(diào)度算法優(yōu)化中尚存在問題，針對這些問題本文提出本文提出一種改進蟻群算法的storm任務調(diào)度優(yōu)化算法。結(jié)合storm拓撲與蟻群算法，本文通過大量實驗得出蟻群算法在storm任務調(diào)度中迭代次數(shù)、啟發(fā)因子的最優(yōu)取值范圍，再引入Sigmoid函數(shù)對信息素揮發(fā)因子進行改進，信息素會隨迭代次數(shù)的變化自適應調(diào)節(jié)，最后把各節(jié)點的資源(CPU、內(nèi)存、磁盤等)與蟻群算法中信息素聯(lián)系起來從而優(yōu)化了storm任務調(diào)度。

1 Apache storm

1.1 Storm作業(yè)模型

Storm是Twitter開源的實時數(shù)據(jù)流計算系統(tǒng)，已經(jīng)收錄到Apache的孵化器中，由Clojure和Java語言開發(fā)。其借鑒了Hadoop的計算模型，Hadoop運行的是一個Job，而Storm運行的是一個Topology，Job是有生命周期的，而Topology是個Service，并且是不會停止的Job。圖1展示了一個簡單的Storm拓撲，包括一層輸入spout和兩層bolt。為了保持性能，Storm可以根據(jù)需要增加blot的并行性。拓撲是Storm的計算組織機制。它是用有向無環(huán)圖(DAG)來表示的。眾所周知，圖是由頂點(節(jié)點)以邊相互連接而成的結(jié)構(gòu)。在這里，邊是有向的，這意味著數(shù)據(jù)只能沿著邊單向流動。這里的圖是無環(huán)的，說明邊的連接不會形成回路。否則，數(shù)據(jù)會在拓撲中無限流動。

圖1 Storm拓撲

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

在Storm 集群中，Storm提交的拓撲作業(yè)按照總的任務數(shù)量平均分配到Supervisor的一作節(jié)點上，但是它忽略了不同節(jié)點的負載不同、性能不同，節(jié)點間的通信和進程間的通信問題。因此，Storm默認調(diào)度可能導致高性能的工作節(jié)點的資源空閑，低性能的工作節(jié)點負載過重等問題以至于資源不能有效的利用。

2 標準蟻群算法

在蟻群算法中設(shè)螞蟻的數(shù)量為m，從第一個節(jié)點開始出發(fā),每一只螞蟻都根據(jù)轉(zhuǎn)移概率來選擇下一個節(jié)點，該節(jié)點到下一個節(jié)點的轉(zhuǎn)移概率公式為：

(1)

式中，ηis為(i,j)相關(guān)的啟發(fā)函數(shù)，τis表示節(jié)點i到節(jié)點j之間路徑的信息素濃度，初始時刻各路徑的信息素濃度相同。α為信息素濃度啟發(fā)因子，代表信息素濃度的相對重要程度，該因子越大，螞蟻越傾向于選擇其它螞蟻走過的路程；β為啟發(fā)函數(shù)啟發(fā)因子，表示啟發(fā)函數(shù)的重要程度。

為了防止信息素無限制累加，引入信息素揮發(fā)機制，當螞蟻完成一次從起點到終點搜索后，對每一條邊上面的信息素濃度進行更新操作。具體為：

(2)

(3)

式中，Q為常數(shù),表示信息強度；Lk為第k只螞蟻在本次迭代中走過的路徑。

3 蟻群算法的改進

3.1 更改啟發(fā)因子α與β

啟發(fā)因子反映螞蟻在運動過程中所積累的信息量，指導蟻群搜索過程中的相對重要程度，其值越大，螞蟻選擇以前走過路徑的可能性就越大，搜索的隨機性減弱；而當啟發(fā)因子值過小時，則易使螞蟻的搜索過早限于局部最優(yōu)[8]。通過設(shè)置更改啟發(fā)因子，得出啟發(fā)因子α與β在storm任務調(diào)度中的最佳取值范圍，從而增加算法合理的搜索指向性。實驗結(jié)果分析具體在第5節(jié)有具體闡述，此處不再贅述。

3.2 揮發(fā)因子的ρ改進

信息素揮發(fā)因子ρ的的取值不僅影響到蟻群算法的搜索性能，而且不利于算法的收斂。ρ性質(zhì)為：ρ過大時，信息素揮發(fā)快；反之，ρ過小時，信息素揮發(fā)慢。在蟻群算法搜索的過程中，隨著迭代次數(shù)的不斷增加，信息素會在某些路徑上累積，所以引入揮發(fā)因子ρ對其削弱?；谧畛跣畔⑺乩鄯e不明顯到迭代完成時累積過大的這種特性，我們引入Sigmoid函數(shù)，由于其單增以及反函數(shù)單增等性質(zhì)，Sigmoid函數(shù)常被用作神經(jīng)網(wǎng)絡(luò)的閾值函數(shù)，將變量映射到0到1之間。依Sigmoid函數(shù)這種性質(zhì)我們將Sigmoid函數(shù)和信息素揮發(fā)因子ρ聯(lián)系起來，蟻群算法的迭代次數(shù)為自變量，信息素揮發(fā)因子ρ為因變量。這樣做剛好契合當蟻群算法在storm任務調(diào)度中的作用，在前期揮發(fā)因子對信息素的濃度削弱小，而到后期會增大對信息素的濃度削弱程度，隨著迭代次數(shù)的改變揮發(fā)因子ρ自適應改變。信息素揮發(fā)因子ρ的表達式如(4)：

(4)

式中，x代表迭代次數(shù)，當a取迭代次數(shù)的二分之一時效果最好，b可以控制s形曲線的胖瘦，引入變量b可以在工程當中去調(diào)節(jié)b的取值從而達到優(yōu)化的目的。在第5節(jié)測出最優(yōu)迭代次數(shù)，根據(jù)最優(yōu)迭代次數(shù)計算出b的最優(yōu)取值。信息素揮發(fā)因子ρ與迭代次數(shù)x的關(guān)系如圖2所示。

圖2 Sigmoid函數(shù)

在第5節(jié)測出蟻群算法的最優(yōu)迭代次數(shù)為50次左右，從而根據(jù)Sigmoid函數(shù)特性去設(shè)定(4)式中a取25。實驗嘗試了b的取值對算法結(jié)果的影響，找到b的最優(yōu)取值為6左右。

3.3 改進信息素濃度更新策略和負載均衡的優(yōu)化

ZooKeeper是Google開源的實現(xiàn)的分布式應用程序協(xié)調(diào)服務大數(shù)據(jù)組件，它可以為分布式應用提供一致性服務，包括:配置維護、域名服務、分布式同步、組服務等。Zookeeper可以得到各個節(jié)點的心跳信息，Nimbus周期性的利用Zookeeper上關(guān)于各個節(jié)點的可用資源情況。設(shè)節(jié)點上CPU信息素用c表示，內(nèi)存信息素用m表示，磁盤信息素用d表示，網(wǎng)絡(luò)信息素用n表示。為了防止超負載，把每一個參數(shù)的最大值設(shè)定為、、、。此時節(jié)點的信息素為該節(jié)點的各類信息素加權(quán)和，分別用e、f、g、h代表CPU、內(nèi)存、磁盤、網(wǎng)絡(luò)資源的權(quán)重，可以通過改變某類信息素的權(quán)重來增強或削弱該類資源對計算的影響。

(5)

蟻群算法在計算過程中會使得某些節(jié)點資源累積過高(表現(xiàn)為信息素累積較高)，這些節(jié)點會始終被分配任務；另外那些節(jié)點因為信息素濃度較低沒有被分配任務從而造成負載不均衡。為此，引入控制負載因子s，sc表示已經(jīng)完成任務量，ssun表示任務的總量，τk代表已經(jīng)完成了sc任務時的信息素，負載因子s通過優(yōu)化了信息素濃度來防止負載不均衡。

(6)

4 算法描述

4.1 算法預完成時間

在Storm任務調(diào)度中上，將Topology中的n個tasks線程分配到m個Supervisors工作節(jié)點上，有n>m。設(shè):n個任務集表示為T={t1,t2,…,tn}，其中ti(i=1,2,…,n)表示第i個task線程；用SV={sv1,sv1,…,svj}表示m個Supervisor節(jié)點集和，其中svj(j=1,2,…,m)表示第j個Supervisor節(jié)點。設(shè)etij為任務ti在節(jié)點svj上的預測完成時間，Ti代表i線程所需資源(CPU，內(nèi)存等)的多少，Rj代表j節(jié)點當前所剩余的資源。則整個Topology的tasks分配到Supervisor節(jié)點上的預測完成時間可組成矩陣ET[n，m] 可表示為：

(7)

式中，etij=Ti/Rj。

4.2 改進后蟻群算法的概率計算公式

蟻群算法中螞蟻由節(jié)點h轉(zhuǎn)移到節(jié)點j的狀態(tài)轉(zhuǎn)移概率公式如(8)：

(8)

式中，τij為從節(jié)點i到節(jié)點j的信息素；ηj=1/eti，其中eti為ti任務的預期完成時間；α和β為啟發(fā)因子；tabuh(h=1,2,…m)為不允許螞蟻在走的節(jié)點，tabuh會隨著作業(yè)進行而不斷的改變。

4.3 算法步驟

第一步：初始化所有參數(shù)；

第二步：設(shè)置最大迭代次數(shù)；

第三步：將任務分配到各個節(jié)點；

第四步：依據(jù)狀態(tài)轉(zhuǎn)移概率選擇下一節(jié)點；

第五步：算法達到最大迭代次數(shù)輸出結(jié)果，否則轉(zhuǎn)移到第三步。

5 實驗結(jié)果和分析

5.1 實驗環(huán)境

集群由8臺物理機器組成：master、slave1、slave2、slave3、slave4、slave5、slave6、slave7；每個節(jié)點配置4個slot；每一個節(jié)點的資源配置都為2.7 GHz CPU，4 GB內(nèi)存，2 TB硬盤，10 Gbit帶寬的LAN。各個節(jié)點IP等信息如圖3所示。主服務進程部署在master節(jié)點，子服務進程都在其余7個slave節(jié)點上。經(jīng)過調(diào)研和測試采用以下版本組合系統(tǒng)整體穩(wěn)定性比較高，基礎(chǔ)框架版本分別是：Centos：6.5、Hadoop：2.7.3、ZooKeeper：3.4.6、Hbase：1.2.4、Kafka：0.72、Storm：0.82、Storm-kafka：0.8.0-wip4。

圖3 集群信息

本實驗選擇使用RandomTextWriter[9]生成隨機單詞文本作為測試數(shù)據(jù)(數(shù)據(jù)量大小可以人為改變)，做WordCount單詞統(tǒng)計任務。因為單詞是隨機生成的，所以各單詞出現(xiàn)的頻率不盡相同，因此在實際生產(chǎn)環(huán)境中具有一定的代表性。

5.2 通過測試尋找迭代次數(shù)

夏蘭[8]在交通地理最佳路徑的研究中中指出蟻群算法的最優(yōu)在65次左右；侯守明等[10]在云任務調(diào)度優(yōu)化中指出蟻群算法的最優(yōu)在60次左右；堯海昌[11]在軌道交通集群調(diào)度問題中指出蟻群算法迭代次數(shù)最佳在57次左右。為了分析蟻群算法迭代次數(shù)與任務完成時間的關(guān)系?；谏鲜鑫墨I于此我們把迭代次數(shù)從1依次遞增到90，尋找最佳迭代次數(shù)。使用RandomTextWriter隨機生成300 MB測試數(shù)據(jù)，對傳統(tǒng)蟻群算法和改進的蟻群算法進行測試，測試結(jié)果如圖4、圖5所示。

圖4 傳統(tǒng)蟻群算法的收斂速度與任務完成時間

圖5 改進蟻群算法的收斂速度與任務完成時間

綜合分析圖4與圖5可知，傳統(tǒng)蟻群算法在迭代次數(shù)達到62次時開始收斂；改進蟻群算法在迭代次數(shù)達到49次時開始收斂；兩者相比較改進蟻群算法收斂速度快。傳統(tǒng)蟻群算法在收斂后任務完成時間大約為9 300 ms；改進蟻群算法在收斂后任務完成時間大約為7 300 ms；兩者相比較改進蟻群算法完成任務時間快，大約比傳統(tǒng)蟻群算法提高了21.5%。

5.3 測試尋找啟發(fā)因子α與β的最佳取值

簡琤峰等[7]在Storm啟發(fā)式均衡圖劃分調(diào)度優(yōu)化問題中指出α的最佳范圍在0.5～2.5之間，β的最佳范圍在4～5.5之間。堯海昌等[11]在基于蟻群算法的軌道交通集群調(diào)度算法研究中指出α的最佳范圍在3～5之間，β的最佳范圍在5～7之間。張志文[12]在AGV路徑規(guī)劃與避障問題中指出α的最佳范圍在2～3之間，β的最佳范圍在2～4之間。上述文獻并沒有指定α與β分別具體取什么值時效果最優(yōu)，為此進行實驗測試。使用RandomTextWriter隨機生成600 MB測試數(shù)據(jù)，對改進的蟻群算法進行測試。首先進行粗粒度篩選，讓α與β分別由1到10以1為間隔取值，計算出任務完成時間。統(tǒng)計結(jié)果得出當α∈[3,7]，β∈,[2,6]時任務完成時間最短。其次細粒度篩選，分別讓α、β從以0.1為間隔從α∈[3,7]，β∈,[2,6]中取值計算出任務完成時間實驗結(jié)果如圖6所示。

圖6 啟發(fā)因子α與β的最佳取值

在圖6中x軸代表啟發(fā)因子α，y軸代表啟發(fā)因子β，z軸代表平均任務完成時間。由圖6可以看出，α=4,β∈,[2,3,5]時算法最優(yōu)，此時任務完成時間大約在14 200 ms。當α與β分別取6和5，7和6左右時，任務完成時間對應為15 500 ms與16 700 ms，此時由于α與β取值過大造成出現(xiàn)局部最優(yōu)解；該問題與文獻[13]在蟻群算法中參數(shù)α、β、ρ設(shè)置的研究中得到的結(jié)果不謀而合。由實驗可知改進蟻群算法在Storm任務調(diào)度中α=4,β∈,[2,3,5]時算法達到最優(yōu)效果。

5.4 負載均衡對比

對于負載均衡我們來用對比測試各節(jié)點的CPU利用率來反映各個節(jié)點的負載情況。而WordCount業(yè)務邏輯處理隨機單詞的數(shù)據(jù)集可保證Topology上所有任務節(jié)點間的邏輯連線都有大量流事件經(jīng)過，因此實驗可客觀展示出不同調(diào)度策略在流事件處理過程的各節(jié)點在實驗當中CPU的使用情況。本實驗使用RandomTextWriter隨機生成300 MB測試數(shù)據(jù)，對Storm默認的輪詢調(diào)度算法和改進的蟻群算法進行測試。圖7為Storm默認的輪詢調(diào)度算法和改進的蟻群算法在運行程序時集群中各個節(jié)點CPU的使用情況。

圖7 各節(jié)點cpu利用率

根據(jù)圖7我們可以得到Storm默認的輪詢調(diào)度算法在運行WordCount單詞統(tǒng)計任務時，節(jié)點之間的CPU利用率的的標準差為0.052，均值為0.461。由標準差和均值可以看出Storm默認的輪詢調(diào)度算法執(zhí)行時，各工作節(jié)點的負載不均現(xiàn)象較為嚴重，其中slave7工作節(jié)點的CPU負載最高，slave4工作節(jié)點的CPU負載最低，二者差值為34%。執(zhí)行改進的蟻群算法時，節(jié)點之間的CPU利用率的標準差僅為0.017，均值為0.342。從以上實驗數(shù)據(jù)可以得出改進的蟻群算法和Storm默認輪的詢調(diào)度算法相比CPU使用標準差降低了3.5%，平均CPU負載降低了26%。

5.5 任務完成時間分析

在試驗中，使用RandomTextWriter隨機生成測試數(shù)據(jù)，生成200 MB、300 MB、400 MB、500 MB、600 MB的隨機單詞文本數(shù)據(jù)集進行實驗。默認的輪詢調(diào)度算法和改進的蟻群算法相應規(guī)模大小的任務完成時間關(guān)系圖如圖8所示。

圖8 算法完成時間對比

由圖8可以看出改進的蟻群算法比默認的輪詢調(diào)度算法在任務完成時間方面降低了大約21.6%，且隨著任務量的增加，輪詢調(diào)度算法完成時間與改進的蟻群算法差距越來越大。

6 結(jié)束語

本文針對Storm的默認任務調(diào)度機制中資源分配不合理而導致處理數(shù)據(jù)延遲問題，提出了改進蟻群算法在Storm任務調(diào)度中的優(yōu)化方案。通過實驗找出蟻群算法在Storm任務調(diào)度中的最佳迭代次數(shù)；測試得出啟發(fā)因子α與β的最佳取值；引入Sigmoid函數(shù)改進了揮發(fā)因子ρ，使其可以在算法運行時自適應的去調(diào)節(jié)。在文最后中將改進的蟻群算法和Storm默認的輪詢調(diào)度算法做比較，得出改進的蟻群算法比Storm默認的輪詢調(diào)度算法在平均CPU負載降低了26%同時CPU使用標準差降低了3.5%，在算法效率上Storm默認的輪詢調(diào)度算法提高了21.6%。得出改進蟻群算法的Storm任務調(diào)度明顯優(yōu)于Storm默認的任務調(diào)度。