黃容++王賢穩(wěn)

摘要：Storm現(xiàn)有的負(fù)載均衡機(jī)制，會(huì)導(dǎo)致集群節(jié)點(diǎn)slot資源使用不均衡，而且在集群節(jié)點(diǎn)資源變化后，也無法動(dòng)態(tài)調(diào)度各節(jié)點(diǎn)負(fù)載。針對(duì)該問題，該文提出基于slot使用率低優(yōu)先的動(dòng)態(tài)負(fù)載均衡策略。該策略在給Topology分配slot計(jì)算資源時(shí)，優(yōu)先分配slot使用率低的節(jié)點(diǎn)；當(dāng)集群可用資源變化時(shí)，對(duì)節(jié)點(diǎn)按照負(fù)載從高到低排序，并將高負(fù)載節(jié)點(diǎn)上的任務(wù)動(dòng)態(tài)遷移到低負(fù)載節(jié)點(diǎn)上，實(shí)現(xiàn)動(dòng)態(tài)負(fù)載均衡。實(shí)驗(yàn)結(jié)果表明，基于slot使用率低優(yōu)先的動(dòng)態(tài)負(fù)載均衡策略能夠有效促進(jìn)Storm集群負(fù)載均衡，提升Storm集群的計(jì)算性能。

關(guān)鍵詞：Storm集群；實(shí)時(shí)計(jì)算；slot使用率；動(dòng)態(tài)遷移；負(fù)載均衡

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）36-0008-04

Dynamic Load Balance Strategy Based on Low Priority of Slot Usage

HUANG Rong，WANG Xian-wen

（Chongqing University of Posts and Telecommunications， Chongqing 400065， China）

Abstract： The default load balance mechanism of Storm can lead to the use of cluster node slot resources is not balanced. Besides， it can not dynamically schedule each node load after the resources in the cluster nodes changes. To solve this problem， this thesis proposes a dynamic load balance strategy based on the low priority of slot usage. When distribute slot computing resources for Topology， the strategy gives priority to slot with low rate of usage. When the cluster resource availability changes， the strategy will rank the nodes according to the load from high to low， and will dynamically migrate load from high load nodes to low load nodes， achieving dynamic load balance. The experimental results show that the strategy can effectively promote the Storm cluster load balance， and enhance the performance of the Storm cluster.

Key words： Storm cluster； real-time computing； slot usage； dynamic migration； load balance

1 背景

Storm[1-3]是一款分布式的、可擴(kuò)展的、容錯(cuò)性良好、可靠性高的開源實(shí)時(shí)計(jì)算系統(tǒng)，被廣泛應(yīng)用于實(shí)時(shí)計(jì)算、流式計(jì)算[4]、分布式RPC、機(jī)器學(xué)習(xí)、ETL等方面，受到國內(nèi)外互聯(lián)網(wǎng)企業(yè)的青睞，有成熟的商用經(jīng)驗(yàn)。

負(fù)載均衡技術(shù)[5]是Storm集群高效率的保證，然而Storm在負(fù)載均衡方面的表現(xiàn)卻無法令人滿意，存在著較多的問題。主要表現(xiàn)為：Storm默認(rèn)的輪詢調(diào)度算法，會(huì)導(dǎo)致集群節(jié)點(diǎn)資源使用的不均衡；在集群中添加、刪除節(jié)點(diǎn)后，或者集群中添加、刪除worker進(jìn)程，從而導(dǎo)致集群計(jì)算資源的變化，Storm也無法根據(jù)改變后的可用資源做出有效調(diào)整策略。

針對(duì)Storm現(xiàn)存的負(fù)載均衡問題，本文提出基于slot使用率低優(yōu)先的動(dòng)態(tài)遷移負(fù)載均衡策略。該策略統(tǒng)計(jì)集群節(jié)點(diǎn)slot使用率，并標(biāo)記slot使用率最低的節(jié)點(diǎn)，優(yōu)先分配該節(jié)點(diǎn)上的slot資源。當(dāng)集群可用資源變化時(shí)，對(duì)節(jié)點(diǎn)按照負(fù)載從高到低排序，并將高負(fù)載節(jié)點(diǎn)上的負(fù)載動(dòng)態(tài)遷移到低負(fù)載節(jié)點(diǎn)上，實(shí)現(xiàn)動(dòng)態(tài)負(fù)載均衡。

2 相關(guān)工作

負(fù)載均衡技術(shù)是保證Storm實(shí)時(shí)計(jì)算應(yīng)用高性能和高吞吐量的有效手段。Storm實(shí)時(shí)計(jì)算應(yīng)用通常是計(jì)算密集型應(yīng)用，負(fù)載均衡對(duì)Storm實(shí)時(shí)計(jì)算應(yīng)用的執(zhí)行性能起著決定性的作用。

2.1 Storm在負(fù)載均衡方面的缺陷

1）Storm默認(rèn)的輪詢調(diào)度算法，會(huì)導(dǎo)致集群節(jié)點(diǎn)slot資源使用的不均衡。

2）Storm集群中資源變化后，無法動(dòng)態(tài)調(diào)度各節(jié)點(diǎn)負(fù)載。

2.2 相關(guān)研究

文獻(xiàn)[6]提出的動(dòng)態(tài)負(fù)載均衡技術(shù)，其核心思想概括如下：在執(zhí)行計(jì)算任務(wù)的多個(gè)節(jié)點(diǎn)上，將這個(gè)計(jì)算任務(wù)包含的所有算子都進(jìn)行多實(shí)例部署，當(dāng)其中一個(gè)算子實(shí)例出現(xiàn)負(fù)載過重時(shí)，動(dòng)態(tài)負(fù)載均衡技術(shù)會(huì)將該算子實(shí)例的部分負(fù)載分配給其他負(fù)載較輕的算子實(shí)例。然而，這種負(fù)載均衡技術(shù)適用于無狀態(tài)的算子，而比較難適用于有狀態(tài)的算子；并且一個(gè)算子存在著多個(gè)算子實(shí)例，且被分配到不同節(jié)點(diǎn)上運(yùn)行，則參與任務(wù)計(jì)算的算子實(shí)例和備用空閑的算子實(shí)例需要共享計(jì)算資源。

關(guān)于Storm負(fù)載均衡任務(wù)調(diào)度算法方面，有的針對(duì)Storm Topology組件運(yùn)行時(shí)分配角度來考慮，如文獻(xiàn)[7]提出了一個(gè)改進(jìn)的調(diào)度器——Online Scheduler，但是算法效率較低，而且缺乏實(shí)用性驗(yàn)證；有的研究側(cè)重從Storm應(yīng)用場景方面來考慮，如文獻(xiàn)[8-9]，但這類算法并沒有針對(duì)Storm自身的機(jī)制來做改進(jìn)；還有的研究偏向從Storm資源需求角度來入手，如文獻(xiàn)[10-11]，這類算法屬于靜態(tài)調(diào)度，并不一定適用于Storm集群運(yùn)行時(shí)環(huán)境?？偟膩碚f，這些算法從不同角度考慮，在一定程度上提升了Storm處理性能，但都存在各自的問題。

3 slot使用率低優(yōu)先策略

Storm把集群中各個(gè)節(jié)點(diǎn)可用的所有slot作為一個(gè)整體來調(diào)度，而沒有考慮到各個(gè)節(jié)點(diǎn)已使用的slot的情況，導(dǎo)致集群slot資源使用不均勻的情況，即集群負(fù)載不均衡。針對(duì)該問題，本方案結(jié)合當(dāng)前各個(gè)節(jié)點(diǎn)空閑的slot情況來調(diào)度，采用slot使用率低優(yōu)先策略，即優(yōu)先分配slot使用率低的節(jié)點(diǎn)，那么就可以在一定程度上使得集群的負(fù)載較為均衡。這里，我們定義slot使用率為已使用的slot數(shù)目除以總的slot數(shù)目。

slot使用率低優(yōu)先策略對(duì)應(yīng)的算法流程如圖1所示。

圖1 slot使用率低優(yōu)先算法流程

4 動(dòng)態(tài)遷移負(fù)載均衡算法

當(dāng)Storm集群運(yùn)行時(shí)間達(dá)到一定長度之后，集群中各個(gè)節(jié)點(diǎn)上可以使用的slot數(shù)目各不相同。某些情況下，還會(huì)進(jìn)行節(jié)點(diǎn)的添加和刪除操作。動(dòng)態(tài)地添加或者刪除節(jié)點(diǎn)，會(huì)引起集群負(fù)載變化，往往需要重新均衡負(fù)載。尤其是當(dāng)新的節(jié)點(diǎn)加入到集群后，該節(jié)點(diǎn)上可用的slot資源非常豐富，而此時(shí)集群中的某些節(jié)點(diǎn)可能出現(xiàn)幾乎沒有slot資源可用的情況。新加入節(jié)點(diǎn)上的負(fù)載與集群中現(xiàn)有節(jié)點(diǎn)上的負(fù)載明顯不均衡，所以需要對(duì)集群進(jìn)行負(fù)載均衡調(diào)度。算法用到的相關(guān)符號(hào)參照表如表1。

4.1 算法步驟

（1）統(tǒng)計(jì)集群中所有節(jié)點(diǎn)包含的slot的總數(shù)量，記作Ts；統(tǒng)計(jì)當(dāng)前所有Topology已使用的slot數(shù)量，記作Us。利用Ts和Us來計(jì)算當(dāng)前集群中slot的平均使用率，記作As。平均使用率所對(duì)應(yīng)的計(jì)算公式如式（1）所示：

[As=Us÷Ts] （1）

（2）遍歷集群中的節(jié)點(diǎn)，統(tǒng)計(jì)當(dāng)前節(jié)點(diǎn)所包含的slot數(shù)量，記作Ns；統(tǒng)計(jì)當(dāng)前節(jié)點(diǎn)已經(jīng)被使用的slot數(shù)量，記作Nus。利用Ns和Nus來計(jì)算當(dāng)前節(jié)點(diǎn)slot的平均使用率，記作Nas。當(dāng)前節(jié)點(diǎn)slot平均使用率計(jì)算公式如式（2）所示。

[Nas=Nus÷Ns] （2）

（3） 建立slot使用情況的四個(gè)隊(duì)列，分別為OverUsedNodes、AboveAvgUseNodes、BelowAvgUseNodes以及UnderUsedNodes。其中隊(duì)列OverUsedNodes說明該隊(duì)列內(nèi)的節(jié)點(diǎn)，slot使用率非常高，超過閾值Th（閾值大小一般為15%，可以更改）；隊(duì)列AboveAvgUseNodes說明該隊(duì)列內(nèi)的節(jié)點(diǎn)，slot使用率較高，超過了集群節(jié)點(diǎn)平均值；隊(duì)列BelowAvgUseNodes說明該隊(duì)列內(nèi)的節(jié)點(diǎn)，slot使用率較低，小于集群節(jié)點(diǎn)平均值；隊(duì)列UnderUsedNodes說明該隊(duì)列內(nèi)的節(jié)點(diǎn)，slot使用非常低低，遠(yuǎn)小于集群節(jié)點(diǎn)平均值。

（4）遍歷集群中的節(jié)點(diǎn)，并根據(jù)以下條件將當(dāng)前節(jié)點(diǎn)加入步驟3所對(duì)應(yīng)的隊(duì)列中：

1）如果當(dāng)前節(jié)點(diǎn)slot使用率滿足公式（3）

[Nas>As+Th] （3）

則將當(dāng)前節(jié)點(diǎn)加入到隊(duì)列OverUsedNodes中。

2）如果當(dāng)前節(jié)點(diǎn)slot使用率滿足公式（4）

[As

則將當(dāng)前節(jié)點(diǎn)加入到隊(duì)列AboveAvgUseNodes中。

3）如果當(dāng)前節(jié)點(diǎn)slot使用率滿足公式（5）

[As-Th<=Nas

則將當(dāng)前節(jié)點(diǎn)加入到隊(duì)列BelowAvgUseNodes中。

4）如果當(dāng)前節(jié)點(diǎn)slot使用率滿足公式（6）

[Nas

則將當(dāng)前節(jié)點(diǎn)加入到隊(duì)列UnderUsedNodes中。

（5）按以下步驟來調(diào)節(jié)集群節(jié)點(diǎn)的負(fù)載均衡：

1）將OverUsedNodes（Source）隊(duì)列內(nèi)節(jié)點(diǎn)的負(fù)載，平衡到UnderUsedNodes（Target）隊(duì)列內(nèi)的節(jié)點(diǎn)；

2）將AboveAvgUseNodes隊(duì)列內(nèi)節(jié)點(diǎn)的負(fù)載，平衡到BelowAvgUseNodes（Target）隊(duì)列內(nèi)的節(jié)點(diǎn)；

（6）對(duì)于步驟5中的操作，其每一步操作的方式為：

1）分別從Source隊(duì)列和Target隊(duì)列選擇一個(gè)節(jié)點(diǎn)S和節(jié)點(diǎn)T，組成節(jié)點(diǎn)對(duì)；重復(fù)上述操作，循環(huán)往復(fù)，知道Source隊(duì)列或Target隊(duì)列為空。

2）計(jì)算源節(jié)點(diǎn)S所需要平衡的負(fù)載量，記作Ls；計(jì)算目標(biāo)節(jié)點(diǎn)T所能接收的負(fù)載量，記作Lt。取Ls和Lt中較小的值，記作Lb，則Lb為從源節(jié)點(diǎn)S平衡到目標(biāo)節(jié)點(diǎn)T的負(fù)載量。在平衡過程中，還需要記錄源節(jié)點(diǎn)S已平衡的負(fù)載量和目標(biāo)節(jié)點(diǎn)T已接收的負(fù)載量。

3）最大化平衡節(jié)點(diǎn)對(duì)之間的負(fù)載量，如果源節(jié)點(diǎn)S平衡后，其對(duì)應(yīng)的已平衡負(fù)載量大于所需要平衡的負(fù)載量，則對(duì)于源節(jié)點(diǎn)S的平衡結(jié)束，將源節(jié)點(diǎn)S從Source隊(duì)列中刪除。如果目標(biāo)節(jié)點(diǎn)T已接收的負(fù)載量達(dá)到Lt，則對(duì)于目標(biāo)節(jié)點(diǎn)T的平衡結(jié)束，將目標(biāo)節(jié)點(diǎn)T從Target隊(duì)列中刪除。

4）源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)之間是多對(duì)多的關(guān)系，即一個(gè)源節(jié)點(diǎn)的負(fù)載，可以平衡到不同的目標(biāo)節(jié)點(diǎn)中；而一個(gè)目標(biāo)節(jié)點(diǎn)，也可以接收來自不同源節(jié)點(diǎn)的負(fù)載。

（7） 如果此時(shí)集群已經(jīng)達(dá)到負(fù)載均衡狀態(tài)，則負(fù)載均衡調(diào)節(jié)結(jié)束；否則，轉(zhuǎn)步驟1重新開始平衡。

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

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

實(shí)驗(yàn)環(huán)境搭建了6個(gè)節(jié)點(diǎn)的Storm完全分布式集群。實(shí)驗(yàn)平臺(tái)中，每個(gè)節(jié)點(diǎn)的具體硬件配置如表2所示。

實(shí)驗(yàn)環(huán)境所對(duì)應(yīng)的集群架構(gòu)如圖2所示。每個(gè)節(jié)點(diǎn)上都安裝運(yùn)行Ubuntu 12.04操作系統(tǒng)，JDK的版本為1.7.0_25，Storm安裝版本為storm-0.8.1，節(jié)點(diǎn)之間通過10 Gbit LAN網(wǎng)卡相連。集群中的主節(jié)點(diǎn)上運(yùn)行著Nimbus進(jìn)程，從節(jié)點(diǎn)上運(yùn)行這worker進(jìn)程，每個(gè)從節(jié)點(diǎn)上配置8個(gè)slot資源。主節(jié)點(diǎn)配置相比于其他節(jié)點(diǎn)較高，因?yàn)橹鞴?jié)點(diǎn)需要承擔(dān)任務(wù)的接受、部署、調(diào)度，是整個(gè)Storm集群的核心。從節(jié)點(diǎn)采用相同的硬件配置，以消除由工作節(jié)點(diǎn)的異構(gòu)帶來的負(fù)載不均衡。

5.2 實(shí)驗(yàn)方案

選取不同的4個(gè)Topology來進(jìn)行實(shí)驗(yàn)，Topology任務(wù)具體配置如表3所示。初始實(shí)驗(yàn)條件下，不使用集群中的從節(jié)點(diǎn)4和從節(jié)點(diǎn)5，將4個(gè)Topology依次提交到集群中計(jì)算。Topology提交完成并運(yùn)行一段時(shí)間后，將從節(jié)點(diǎn)4和從節(jié)點(diǎn)5啟用，增加集群可用的slot資源，做集群負(fù)載遷移實(shí)驗(yàn)。

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

1）實(shí)驗(yàn)一：slot使用率低優(yōu)先策略

將4個(gè)Topology依次提交到由主節(jié)點(diǎn)和從節(jié)點(diǎn)1、從節(jié)點(diǎn)2、從節(jié)點(diǎn)3組成的集群環(huán)境中，針對(duì)Storm默認(rèn)的slot使用機(jī)制以及slot使用率低優(yōu)先策略兩種情況，分別進(jìn)行30次實(shí)驗(yàn)，并統(tǒng)計(jì)實(shí)驗(yàn)中各從節(jié)點(diǎn)slot使用率，取30次實(shí)驗(yàn)的平均值來作為分析依據(jù)。

圖3顯示的是兩種實(shí)驗(yàn)條件下集群節(jié)點(diǎn)slot使用率的差別。從實(shí)驗(yàn)結(jié)果可以看到，在Storm默認(rèn)的slot機(jī)制中，從節(jié)點(diǎn)1的slot使用率高達(dá)65.5%，而從節(jié)點(diǎn)3的slot使用率僅達(dá)到12.5%，3個(gè)從節(jié)點(diǎn)之間slot使用率差別較大；在slot使用率低優(yōu)先策略中，從節(jié)點(diǎn)1的slot使用率為50%，而從節(jié)點(diǎn)2以及從節(jié)點(diǎn)3的使用率都為37.5%，3個(gè)從節(jié)點(diǎn)之間的slot使用率較為均等。

圖3 實(shí)驗(yàn)一slot使用率對(duì)比

實(shí)驗(yàn)結(jié)果表明，基于slot使用率低優(yōu)先策略改進(jìn)的任務(wù)分配機(jī)制，集群中各節(jié)點(diǎn)slot使用率較為均等，在一定程度上改善了集群負(fù)載均衡狀況。

2）實(shí)驗(yàn)二：節(jié)點(diǎn)負(fù)載均衡遷移

在實(shí)驗(yàn)一的基礎(chǔ)上，啟用集群中的從節(jié)點(diǎn)4和從節(jié)點(diǎn)5，繼續(xù)進(jìn)行負(fù)載均衡遷移實(shí)驗(yàn)。觀察實(shí)驗(yàn)過程中，從節(jié)點(diǎn)1、從節(jié)點(diǎn)2、從節(jié)點(diǎn)3上負(fù)載的遷移情況，并統(tǒng)計(jì)負(fù)載均衡遷移完成時(shí)所有從節(jié)點(diǎn)上slot使用率。

節(jié)點(diǎn)負(fù)載均衡遷移前后，各從節(jié)點(diǎn)slot使用率如圖4所示。從實(shí)驗(yàn)結(jié)果可以看到，節(jié)點(diǎn)負(fù)載均衡遷移之前，從節(jié)點(diǎn)1和從節(jié)點(diǎn)2的slot使用率較高，分別達(dá)到62.5%和50%；當(dāng)集群中加入新的可用節(jié)點(diǎn)從節(jié)點(diǎn)4和從節(jié)點(diǎn)5時(shí)，對(duì)集群進(jìn)行節(jié)點(diǎn)負(fù)載均衡遷移后，降低了原來從節(jié)點(diǎn)1和從節(jié)點(diǎn)2的slot使用率，且集群中的5個(gè)從節(jié)點(diǎn)slot使用率都相等，均為25%。

圖4 實(shí)驗(yàn)二slot使用率對(duì)比

實(shí)驗(yàn)結(jié)果表明，在集群中新加入節(jié)點(diǎn)后，利用節(jié)點(diǎn)負(fù)載均衡遷移機(jī)制，能夠較好地將原來節(jié)點(diǎn)上的負(fù)載分?jǐn)偟叫碌墓?jié)點(diǎn)上，實(shí)現(xiàn)集群中節(jié)點(diǎn)的整體負(fù)載均衡。

6 結(jié)束語

本文針對(duì)Storm默認(rèn)的輪詢調(diào)度算法導(dǎo)致集群節(jié)點(diǎn)資源使用率的不均衡以及在集群中添加、刪除節(jié)點(diǎn)后導(dǎo)致集群計(jì)算資源的變化而Storm無法根據(jù)改變后的可用資源做出有效調(diào)整策略的問題，提出了基于slot使用率低優(yōu)先的動(dòng)態(tài)遷移負(fù)載均衡策略。該策略在給Topology分配slot計(jì)算資源時(shí)，優(yōu)先分配slot使用率低的節(jié)點(diǎn)；當(dāng)集群中可用計(jì)算節(jié)點(diǎn)增加時(shí)，能夠在節(jié)點(diǎn)之間動(dòng)態(tài)遷移負(fù)載。實(shí)驗(yàn)結(jié)果表明，基于slot使用率低優(yōu)先及動(dòng)態(tài)遷移負(fù)載均衡策略能夠有效促進(jìn)Storm集群負(fù)載均衡，提升Storm集群的計(jì)算性能。

參考文獻(xiàn)：

[1] Toshniwal A， Taneja S， Shukla A， et al. Storm@ twitter[C]//Proceedings of the 2014 ACM SIGMOD international conference on Management of data. ACM， 2014： 147-156.

[2] Simoncelli D， Dusi M， Gringoli F， Niccolini S. Scaling out the performance of service monitoring applications with BlockMon. In： Proc. of the 14th Intl Conf. on Passive and Active Measurement （PAM 2013）. Hong Kong： IEEE Press， 2013. 253?255.

[3] 孫大為， 張廣艷， 鄭緯民. 大數(shù)據(jù)流式計(jì)算： 關(guān)鍵技術(shù)及系統(tǒng)實(shí)例[J]. 軟件學(xué)報(bào)， 2014， 25（4）： 839-862.

[4] 顧昕. 分布式流式計(jì)算框架關(guān)鍵技術(shù)的研究與實(shí)現(xiàn)[D]. 北京： 北京郵電大學(xué)， 2012.

[5] 彭書凱. 分布式流計(jì)算框架中負(fù)載管理功能的設(shè)計(jì)與實(shí)現(xiàn)[D]. 北京： 北京郵電大學(xué)， 2013.

[6] Collins R L， Carloni L P. Flexible filters： load balancing through backpressure for stream programs[C]// Proceedings of the seventh ACM international conference on Embedded software. ACM， 2009： 205-214.

[7] Aniello L， Baldoni R， Querzoni L. Adaptive online scheduling in storm[C]//Proceedings of the 7th ACM international conference on Distributed event-based systems. ACM， 2013： 207-218.

[8] Long Shaohang， Rao Ruonan， Miao Wangsheng， et al. An improved topology schedule algorithm for storm system[C]//Computer Science and Applications： Proceedings of the 2014 Asia-Pacific Conference on Computer Science and Applications （CSAC 2014）， Shanghai， China， 27-28 December 2014. CRC Press， 2015： 187.

[9] Cardellini V， Grassi V， Lo Presti F， et al. Distributed QoS-aware scheduling in storm[C]//Proceedings of the 9th ACM International Conference on Distributed Event-Based Systems. ACM， 2015： 344-347.

[10] Peng B， Hosseini M， Hong Z， et al. R-Storm： Resource-Aware Scheduling in Storm[C]//ACM MIDDLEWARE '15 Proceedings of the， ACM MIDDLEWARE Conference. 2015.

[11] Sun Dawei， Zhang Guangyan， Yang Songlin， et al. Re-Stream： Real-time and energy-efficient resource scheduling in big data stream computing environments[J]. Information Sciences， 2015.