改進(jìn)蟻群算法的Storm任務(wù)調(diào)度優(yōu)化

(西安理工大學(xué) 自動(dòng)化與信息工程學(xué)院，西安 710048)

0 引言

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

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

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

1 Apache storm

1.1 Storm作業(yè)模型

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

圖1 Storm拓?fù)?/p>

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

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

2 標(biāo)準(zhǔn)蟻群算法

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

(1)

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

為了防止信息素?zé)o限制累加，引入信息素?fù)]發(fā)機(jī)制，當(dāng)螞蟻完成一次從起點(diǎn)到終點(diǎn)搜索后，對(duì)每一條邊上面的信息素濃度進(jìn)行更新操作。具體為：

(2)

(3)

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

3 蟻群算法的改進(jìn)

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

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

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

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

(4)

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

圖2 Sigmoid函數(shù)

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

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

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

(5)

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

(6)

4 算法描述

4.1 算法預(yù)完成時(shí)間

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

(7)

式中，etij=Ti/Rj。

4.2 改進(jìn)后蟻群算法的概率計(jì)算公式

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

(8)

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

4.3 算法步驟

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

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

第三步：將任務(wù)分配到各個(gè)節(jié)點(diǎn)；

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

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

5 實(shí)驗(yàn)結(jié)果和分析

5.1 實(shí)驗(yàn)環(huán)境

集群由8臺(tái)物理機(jī)器組成：master、slave1、slave2、slave3、slave4、slave5、slave6、slave7；每個(gè)節(jié)點(diǎn)配置4個(gè)slot；每一個(gè)節(jié)點(diǎn)的資源配置都為2.7 GHz CPU，4 GB內(nèi)存，2 TB硬盤，10 Gbit帶寬的LAN。各個(gè)節(jié)點(diǎn)IP等信息如圖3所示。主服務(wù)進(jìn)程部署在master節(jié)點(diǎn)，子服務(wù)進(jìn)程都在其余7個(gè)slave節(jié)點(diǎn)上。經(jīng)過調(diào)研和測(cè)試采用以下版本組合系統(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 集群信息

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

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

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

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

圖5 改進(jìn)蟻群算法的收斂速度與任務(wù)完成時(shí)間

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

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

簡(jiǎn)琤峰等[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之間。上述文獻(xiàn)并沒有指定α與β分別具體取什么值時(shí)效果最優(yōu)，為此進(jìn)行實(shí)驗(yàn)測(cè)試。使用RandomTextWriter隨機(jī)生成600 MB測(cè)試數(shù)據(jù)，對(duì)改進(jìn)的蟻群算法進(jìn)行測(cè)試。首先進(jìn)行粗粒度篩選，讓?duì)僚cβ分別由1到10以1為間隔取值，計(jì)算出任務(wù)完成時(shí)間。統(tǒng)計(jì)結(jié)果得出當(dāng)α∈[3,7]，β∈,[2,6]時(shí)任務(wù)完成時(shí)間最短。其次細(xì)粒度篩選，分別讓?duì)?、β從?.1為間隔從α∈[3,7]，β∈,[2,6]中取值計(jì)算出任務(wù)完成時(shí)間實(shí)驗(yàn)結(jié)果如圖6所示。

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

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

5.4 負(fù)載均衡對(duì)比

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

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

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

5.5 任務(wù)完成時(shí)間分析

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

圖8 算法完成時(shí)間對(duì)比

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

6 結(jié)束語(yǔ)

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