基于布谷鳥算法的Storm集群動態(tài)負載均衡策略

龍 笑，周 良，鄭洪源

(南京航空航天大學 計算機科學與技術學院，江蘇 南京 210016)

0 引 言

隨著物聯(lián)網和社交網絡的快速發(fā)展，流數據的規(guī)模不斷增長，流處理在交通監(jiān)測、氣象觀測和銀行交易管理等領域都有著廣泛的應用。以無人機貨運實時流數據為例，其產生的流數據具有到達速度快、到達時間持續(xù)和動態(tài)改變等特點，傳統(tǒng)地大數據批處理框架已無法滿足實時性的需求。Storm作為分布式實時數據計算系統(tǒng)，可以同時對數以億計的流數據進行計算，比其他大數據計算框架更適合于實時流數據的處理。在數據處理要求實時性和高效率的情況下，節(jié)點的有效管理和資源的合理分配顯得愈發(fā)重要，負載均衡的重要性也愈發(fā)突出。Storm實時計算應用程序通常是計算密集型應用程序，負載平衡在Storm實時計算應用程序的性能中起著決定性作用。

然而Storm默認調度在負載均衡方面的表現卻無法令人滿意，存在著較多的問題。首先，Storm平臺在默認的任務調度上采用的是輪詢調度(round robin scheduling)，該算法將用戶提交的拓撲中包含的任務平均分配給每個工作流程，再將各工作進程平均分配到各工作節(jié)點上。由于其忽視了節(jié)點間性能和負載的差異，致使集群的資源利用率不高。其次，在集群節(jié)點動態(tài)增刪后，Storm無法根據集群計算資源的變化做出有效的策略調整，影響負載均衡。此外，Storm默認任務調度算法只關心CPU利用率，而忽視了內存、磁盤IO、網絡帶寬等節(jié)點資源，這可能導致工作節(jié)點內存不足和網絡阻塞等問題。

針對Storm集群動態(tài)負載實時調度優(yōu)化問題，文中提出了一種基于布谷鳥搜索算法的Storm集群動態(tài)負載均衡策略(DLBSCSA)。該策略綜合考慮了節(jié)點的CPU、內存、網絡帶寬、磁盤IO等資源，根據實時監(jiān)測到的負載數據為集群的節(jié)點性能賦予權值，通過布谷鳥搜索算法的尋優(yōu)過程動態(tài)調整權值，計算出節(jié)點上任務的分配權重，從而完成資源的動態(tài)分配，以此達到節(jié)點負載的均衡。

1 相關工作

截止目前，愈來愈多的人開始關注Storm默認調度算法的優(yōu)化。文獻[1]提出了一種資源感知在線調度算法RStorm，它利用任務需要與工作節(jié)點的靜態(tài)資源之間的關系來實現調度，但是，由于資源需求完全依賴于人工設置，因此無法在數據流快速變化的情況下實現在線調度。文獻[2]根據監(jiān)測到的數據實現實時調度，但改進后的系統(tǒng)延遲略有提高。文獻[3]提出在線調度算法TStorm，通過實時監(jiān)測任務負載將通信開銷大的任務動態(tài)分配至空閑資源較多的節(jié)點上，但需人為設定拓撲所需的節(jié)點數量。

文獻[4]結合對歷史任務的恢復和對單個節(jié)點的任務調度等不同情況針對Storm進行了改進。文獻[5]提出了針對服務質量感知的調度算法，使Storm適用于地理信息系統(tǒng)的研究。文獻[6]提出Storm環(huán)境下離線和在線的兩種自適應調度算法，分別用于拓撲運行前后的結構分析和實時負載監(jiān)測，但執(zhí)行時未將當前任務與其直接通信的所有任務全部考慮進來，容易陷入局部最優(yōu)。

文獻[7]引入拓撲熱邊的概念，為減少通信開銷，將熱邊關聯(lián)的源和目標任務調度到同一節(jié)點，但忽略了非熱邊的調度。文獻[8]提出一種兩階段調度算法，分別降低了進程間和節(jié)點間的通信開銷，但并未考慮到各任務自身計算開銷的差異性。文獻[9]中提出了一種基于權重的任務調度算法，該算法根據每個任務的CPU資源和任務之間的數據流大小確定拓撲的點權重和邊權重，并構造每個節(jié)點承載的任務集，但其資源權重為靜態(tài)的，在面對集群節(jié)點資源變化的情況中表現不佳。

任務調度是非常有代表性的NP難問題，對其他物種行為特點進行模仿能夠較好地解決此類問題，其中比較典型的有蟻群算法、遺傳算法及PSO算法，但它們存在諸如實時性差、早熟收斂、后期震蕩的問題。而布谷鳥搜索算法是Yang等[10]在2009年提出的一種智能優(yōu)化算法，該算法具有模型簡單、可調參數少及收斂速度快等優(yōu)點，目前已被許多領域應用。文獻[11]針對作業(yè)調度問題提出一種模擬退火下布谷鳥算法；文獻[12]基于布谷鳥搜索算法，提出一種新的多處理器任務調度算法；文獻[13]針對當前云計算資源調度開銷大等難題,提出了改進布谷鳥搜索算法的云計算任務調度方法。

2 DLBSCSA相關描述及定義

2.1 Storm默認調度機制

Storm的計算結構[14]是Topology，即一個有向無環(huán)圖，其分別由stream，spout和bolt組成。Topology的核心數據結構是tuple，數據流就是由無數的tuple組成的實序序列。spout及bolt構成了組件，spout把stream分割為無數拓撲，并依據Topology轉發(fā)相關拓撲。bolt則是數據計算單位，由上游獲取拓撲并在處理后將結果轉送下游bolt。Storm正是利用無數Topology來執(zhí)行實時流處理的。

Storm的默認調度機制有兩個主要步驟：

(1)將executor線程分配至worker；

(2)將worker分配至工作節(jié)點。

默認調度使用輪詢的方式，將executor分送到相應worker上，然后當集群slot資源足夠時,可以把任務均衡地分派到集群工作節(jié)點中。若slot缺少時，當前已有的slot將被分派所有任務。

圖1 用戶提交的Topology

以圖1中用戶提交的Topology為例，假定當前集群有3個工作節(jié)點且節(jié)點資源均很豐富，則在用戶提交Topology后默認調度算法對任務的分配如下：

(1)工作節(jié)點1:T1,T4,T7；

(2)工作節(jié)點2:T2，T5，T8；

(3)工作節(jié)點3:T3，T6，T9。

默認調度算法未考慮到不同工作節(jié)點的性能和負載差異，致使節(jié)點資源利用率不高，這將對Storm處理的實時性產生較大影響。同時，默認調度策略更關心節(jié)點的CPU資源使用情況,而忽視了內存、磁盤、網絡等其他類型的資源，這樣可能會造成工作節(jié)點內存不足、網絡堵塞等問題。

2.2 動態(tài)負載相關定義

Storm中的任務分配過程可描述為將一個Topology中的n個tasks分配到m個Supervisors工作節(jié)點上執(zhí)行的過程。初始描述為:

T={t1,t2,…,tn}表示n個任務集，其中ti(i=1,2,…,n)表示第i個task。

S={s1,s2,…,sm}表示m個Supervisor節(jié)點集，其中sj(j=1,2,…,m)表示第j個Supervisor節(jié)點。

為反應CPU占用率、內存占用率等資源的利用情況，用向量L表示m個節(jié)點的動態(tài)負載向量L=[l1,l2,…,lm]。設集群系統(tǒng)的節(jié)點sj的負載為L(sj)，為計算L，引入集群節(jié)點性能向量U，有：

(1)

計算節(jié)點負載后，即可計算節(jié)點分配的權重(占比)向量W，W=[W1,W2,…,Wm]，其中Wi的計算定義為：

(2)

根據節(jié)點分配的占比向節(jié)點分配任務。

3 DLBSCSA設計

3.1 問題建模

根據DLBSCSA相關描述及定義，DLBSCSA設計的實質是根據系統(tǒng)當前或最近狀態(tài)決定如何給分布式系統(tǒng)的每個節(jié)點分配任務，即找到最優(yōu)的節(jié)點任務分配權重。所以，當集群節(jié)點的負載達到其最大承受程度時，集群能夠以最佳方式運作，系統(tǒng)的整體性能最好。而為了達到資源的動態(tài)負載均衡，最主要的是根據集群運轉情況實時地計算出最優(yōu)的資源分配權重。

動態(tài)負載均衡模型可以描述為：向m個節(jié)點分配n個任務，綜合多個性能指標加權計算反映節(jié)點的負載向量L，通過尋找最優(yōu)的權重向量α，使負載向量L能夠正確地反映集群系統(tǒng)的負載。再利用選擇函數，根據歷史信息和動態(tài)權重合理而均衡地選取節(jié)點來對負載進行處理，使整個任務具有最短的處理時間和最大的吞吐量。由于權重向量α隨集群的負載情況而變化，需要對其進行實時檢測并動態(tài)地計算最新的α。動態(tài)負載均衡模型如圖2所示。

圖2 動態(tài)負載均衡模型

動態(tài)負載均衡的最終目的是減少集群響應時間，做到任務的實時處理。為此將目標函數定義為集群系統(tǒng)的平均響應時間，目標函數越小表示集群系統(tǒng)的總體性能越好。即

F=∑Res/m

(3)

其中，F為目標函數；Res為集群系統(tǒng)響應時間向量。由上文知，Res由節(jié)點負載向量L，任務向量T和選擇函數Sel來確定，即：

Res=(L,T,Sel)

(4)

其中選擇函數Sel定義任務和節(jié)點間的映射關系，根據當前任務c、負載分配歷史向量h及節(jié)點任務分配權重向量W來選取恰當的節(jié)點對當前任務進行處理，若選擇的節(jié)點為sup，則有

sup=Sel(c,h,W)

(5)

根據式3知，目標函數值越小說明集群的整體性能越好，即當布谷鳥搜索算法求得的權重向量α收斂時目標函數最?。?/p>

(6)

因此，基于布谷鳥搜索算法的Storm集群動態(tài)負載均衡策略即找到目標函數的最優(yōu)解，從而可以將節(jié)點的性能權重α作為目標，通過布谷鳥搜索算法尋求α的最優(yōu)解。

3.2 權重向量的尋優(yōu)

根據上文，為實現資源的動態(tài)負載均衡，文中引入了布谷鳥搜索算法，通過其尋優(yōu)過程為節(jié)點的CPU、內存、磁盤IO及網絡帶寬等資源賦予動態(tài)的權值，即尋找節(jié)點性能權重向量α的最優(yōu)解。

布谷鳥搜索算法是一種隨機搜索算法，它將布谷鳥寄生孵育雛鳥的生物學行為與一些鳥類和果蠅的萊維飛行行為結合起來。在本質上，布谷鳥找到宿主鳥巢的過程是隨機的，為了對其進行模擬，需要先設定以下幾個規(guī)則：

(1)布谷鳥每次產卵一枚，并采用隨機方式尋找宿主巢穴；

(3)可搜尋的巢穴數量是固定的，宿主鳥巢主人可以發(fā)覺外來卵的概率是P，鳥蛋一經發(fā)現即會被宿主移除，或直接遺棄該鳥巢。

基于以上3個理想狀態(tài)，布谷鳥尋找宿主鳥巢的位置更新公式如下：

(7)

在實際應用中，鳥巢的位置表示問題的解的有效取值范圍，鳥巢的適應度函數值表示目標函數的值。文中算法由于尋優(yōu)的目標是一個矢量，因此假定每個鳥巢中有若干個卵，分別代表一種解決方案，在更優(yōu)新解代替舊解的過程中尋找到權重向量的最優(yōu)解。因此位置更新公式為：

(8)

布谷鳥標準算法中的初始步長因子通常被設計為固定值，而之后步長的設定在尋優(yōu)過程中缺乏自適應，這樣會導致算法收斂性能下降，影響算法準確性。因此文中在萊維飛行中加入自適應方法設置動態(tài)的步長因子。將步長設置為第t次迭代中第j個解集中各解與初始值之間距離的平均值，即：

(9)

為最大限度地避免因步長過大而產生的算法最優(yōu)解的遺漏，則位置更新公式最終可表示為：

(10)

若想對產生的解進行優(yōu)越性的評估，目標函數需經計算以具體數字形式體現，由此定義了一個適應度函數：

(11)

函數fitness作為評價解的數值基準，評估解在時間效率方面的優(yōu)越性，適應度越小表示解越優(yōu)。其中矩陣ETC中的值表示任務i在第j個節(jié)點上完成所需的理論時間，因此ETC矩陣可表示為：

美國官員和一些科學家希望到21世紀20年代中期能形成一種有效的治療方案，但臨床試驗的挫折加劇了人們的擔憂。紐約市西奈山伊坎醫(yī)學院阿爾茨海默病研究員塞繆爾·甘迪（Samuel Gandy）說：“我確信我們無法實現2025年的目標，看來我們的承諾要落空了?！睂τ诎堰@么多錢僅僅集中于阿爾茨海默病的研究上，有些研究人員也表示出擔心。加州諾瓦托市巴克老齡化研究所的生物學家朱蒂·坎皮西（Judy Campisi）想知道，是否應該多拿出一些資金來支持基礎研究，對于這樣有針對性的資助，生物醫(yī)學界“懷有復雜的心情”。

(12)

文中ETC矩陣的初始值通過幾次測試求均值后得到，由于任務不斷分派，未完成的任務數將越來越少，任務理論完成時間也會發(fā)生變化[15]。因此，任務的理論完成時間的更新公式定義為:

(13)

文中的布谷鳥搜索算法可以描述為：

(1)初始化算法相關參數，確定宿主鳥巢的數目n，搜索空間維數d，外來鳥蛋被發(fā)現的概率P，設定全局最大迭代次數Max，步長初值a0，適應度閾值Val。隨機選擇鳥窩的位置，設定t初值為0，鳥蛋代表的就是權重的解

(2)利用fitness函數(式11)對鳥窩位置的優(yōu)越性進行評估，并對最佳鳥窩進行記錄

(3)While(未達到最大迭代次數Max或適應度函數大于閾值Val) do

(4)根據式9計算萊維飛行的動態(tài)步長因子

(5)根據式10更新鳥巢位置

(6)將當前解作為計算負載向量L的參數，代入模型中得到理論完成時間矩陣ETC，并根據適應度函數(式11)評估鳥巢位置優(yōu)劣，若更優(yōu)則接受步驟中更新后的位置，否則保持位置不變

(7)if(K>P) then

(8)對當前的鳥窩位置進行隨機更新

(9)end if

(10)對鳥窩位置優(yōu)越性進行評價，方法與步驟6中相同，若更優(yōu)則接受步驟8中更新后的位置，否則保持位置不變

(11)記錄迭代完成產生的最佳鳥窩位置

(12)end while

(13)輸出最優(yōu)值

經過以上迭代，算法最終將收斂至一個最優(yōu)的性能權重向量α，能夠使該負載均衡模型正確計算集群當前負載，并合理地分配新到達的負載。

3.3 動態(tài)分配負載

根據布谷鳥搜索算法尋找到的最佳性能權重能夠得到集群節(jié)點當前負載，從而得出分配權重向量W，文中通過實時監(jiān)聽節(jié)點的負載數據對任務的分配進行動態(tài)調整。根據式2可求出節(jié)點上任務的分配權重，為進一步確定任務處理的節(jié)點，需要綜合目前任務、負載分配歷史及節(jié)點任務分配權重來確定節(jié)點對當前任務進行處理，因此引入選擇函數來定義任務和節(jié)點間的映射關系，做出合理且平穩(wěn)的分配方案。通過一個判斷向量ThrVal來描述選擇函數，對于集群節(jié)點有：

Hissu/ResTol≈Wsu/∑w

(14)

式14可作為負載平衡的目標，其中ResTol表示負載任務總數，Hissu表示歷史任務分配向量的一個分量，即某個單個節(jié)點的歷史任務分配。計算節(jié)點的判斷向量ThrVal，單個節(jié)點的判斷分向量定義為：

ThrValsu=Wsu×ResTol-∑w×Hissu

(15)

因此選擇函數Sel可以描述為：

{δ=Sel(T,h,W)ThrValδ=max(ThrVal)}

(16)

利用選擇函數能夠準確地根據任務分配權重進行節(jié)點任務分派，實現集群的負載均衡，從而實現資源的合理分配。

4 實驗結果及分析

實驗目的是在Storm集群環(huán)境中，分別測試文中動態(tài)負載均衡算法與Storm默認調度算法的處理延遲、系統(tǒng)吞吐量和負載均衡情況。比較和分析相關結果，驗證文中算法在性能上的先進性。

實驗利用Pluggable Scheduler對Storm任務調度算法進行自定義，而對于集群節(jié)點狀態(tài)的監(jiān)測則使用Ganglia，監(jiān)測諸如CPU、內存、磁盤I/O和網絡帶寬等資源的利用情況，并根據Ganglia生成的數據對實驗結果進行輔助分析。實驗采用5臺物理機器組成的Storm分布式集群，各個節(jié)點的硬件配置如表1所示。

表1 節(jié)點配置信息

每個節(jié)點運行Ubuntu 12.04操作系統(tǒng)。其中一個作為主節(jié)點運行Nimbus進程，實現資源分配以及任務調度；從節(jié)點執(zhí)行Nimbus分派的任務,啟動和停止由其自身管理的Worker進程。同時還搭建了Zookeeper集群，它們始終處于運行狀態(tài)。

文中選擇典型的大數據處理應用WordCount來進行實驗，分別實現了默認算法與文中算法的WordCount程序并提交到Storm集群運行。同時，為了避免其他不確定性對實驗結果的干擾，將2個程序進行多次實驗，計算結果的平均值完成實驗的結果分析。

所有節(jié)點硬盤為20 GB，網卡為10 G bit。

在處理時延方面，文中算法與默認調度算法的處理時延如圖3所示?？梢钥闯?，較之于默認調度算法，文中算法的處理時延大體上有所下降，約降低20%～25%左右。

圖3 算法時延比較

在系統(tǒng)吞吐量方面，文中基于布谷鳥搜索算法的Storm集群動態(tài)負載均衡算法與默認調度算法的吞吐量如圖4所示?？梢钥闯?，較之于默認調度算法，文中算法的吞吐量在整體上有所提高，約提高了20%左右。

針對負載均衡性能的測試，設計了四種對資源種類需求不一樣的Topology以評估文中算法在不同資源使用情況集群下的處理能力。其中，Topology1～Topology4分別屬于CPU密集型作業(yè)、內存密集型作業(yè)、磁盤密集型作業(yè)、網絡密集型作業(yè)。各作業(yè)的估計資源使用值向量按CPU、內存、磁盤IO和網絡帶寬的次序分別為：[9,4,4,3],[5,8,3,4],[2,4,5,9],[5,3,8,4]。將以上Topology均提交至Storm集群，其平均處理時間分別如圖5所示。

圖4 算法吞吐量比較

(a)Topology 1

(b)Topology 2

(c)Topology 3

從圖中可以看出，提交的四個Topology進行初始時表現均不如默認調度，而隨著節(jié)點資源的變化，文中算法平均處理時間逐漸降低并低于默認算法。這是由于在作業(yè)初始時節(jié)點可提供資源相同，默認的輪詢算法更有優(yōu)勢，而隨著節(jié)點資源的變化，默認算法則表現乏力。較之于默認調度算法，文中算法的作業(yè)平均處理時間縮短了一半左右，并且伴隨著時間推移逐步趨于穩(wěn)定，有助于提升作業(yè)的執(zhí)行效率。

5 結束語

針對Storm默認任務調度算法存在的節(jié)點資源利用率不高及難以將節(jié)點資源與任務實際相結合等問題，提出了一種基于布谷鳥搜索算法的Storm集群動態(tài)負載均衡策略。通過引入布谷鳥搜索算法并稍作修改，將任務調度模擬為布谷鳥尋窩產卵的過程，通過算法的尋優(yōu)過程為集群的CPU、內存及網絡帶寬等資源賦予動態(tài)權值，以完成資源的動態(tài)分配，達到節(jié)點負載的均衡。實驗結果表明，該算法可以實現資源的合理分配，與默認算法相比具有更優(yōu)的任務調度效率，更高的集群吞吐量和更少的平均處理時間。