Storm啟發(fā)式均衡圖劃分調(diào)度優(yōu)化方法

簡(jiǎn)琤峰,盧 濤,張美玉

(浙江工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院 數(shù)字媒體技術(shù)研究所,杭州 310023)

1 引 言

面向移動(dòng)互聯(lián)網(wǎng)和大數(shù)據(jù)應(yīng)用的實(shí)時(shí)數(shù)據(jù)流式處理技術(shù)[1,2]成為近年來(lái)相關(guān)研究領(lǐng)域的熱點(diǎn).Storm[3]提供了一種優(yōu)秀的實(shí)時(shí)大數(shù)據(jù)流式計(jì)算模式得以廣泛應(yīng)用.但隨著深入應(yīng)用,其在資源和任務(wù)的調(diào)度策略上存在的問(wèn)題也越來(lái)越突出:通信代價(jià)作為影響流式數(shù)據(jù)處理效率的重要因素,Storm調(diào)度器沒(méi)有將其作為考慮因素;自帶的均衡調(diào)度器會(huì)導(dǎo)致負(fù)載不均;并行度參數(shù)需要手動(dòng)配置;無(wú)法根據(jù)集群運(yùn)行狀況對(duì)任務(wù)重調(diào)度等問(wèn)題直接影響Storm集群的運(yùn)行性能.

針對(duì)上述問(wèn)題,文獻(xiàn)[4]提出基于Topology結(jié)構(gòu)的Offline調(diào)度器與基于Traffic的Online實(shí)時(shí)調(diào)度器,其中Offline調(diào)度器通過(guò)檢測(cè)Topoloy結(jié)構(gòu)一次性分配任務(wù),而Online調(diào)度算法則實(shí)時(shí)檢測(cè)負(fù)載與延時(shí)并應(yīng)用了改進(jìn)的貪心算法,優(yōu)化Storm實(shí)時(shí)計(jì)算性能,實(shí)現(xiàn)動(dòng)態(tài)調(diào)度;該文提出的算法僅考慮了通訊代價(jià),而沒(méi)有考慮到負(fù)載均衡.文獻(xiàn)[5]設(shè)計(jì)了一個(gè)基于流量感知(Traffic aware)而優(yōu)化調(diào)度的改進(jìn)了整個(gè)Storm框架,事實(shí)上也是重點(diǎn)優(yōu)化了通信代價(jià)這個(gè)維度,改進(jìn)后的框架稱(chēng)之為T(mén)-Storm,相同任務(wù)下能夠減少30%的服務(wù)延時(shí).文獻(xiàn)[6]借助Metis工具對(duì)任務(wù)的Topology進(jìn)行多層K劃分[7,8],自適應(yīng)分層調(diào)度改進(jìn)Storm.文獻(xiàn)[9]通過(guò)感知本地資源的利用率以及網(wǎng)絡(luò)延時(shí)來(lái)最大化Storm的吞吐量.文獻(xiàn)[10]提出利用GPU來(lái)提升Storm計(jì)算能力的方法.在國(guó)內(nèi),阿里云對(duì)Storm進(jìn)行的優(yōu)化,稱(chēng)之為JStorm;其在網(wǎng)絡(luò)IO、線(xiàn)程模型、資源調(diào)度、可用性及穩(wěn)定性上做了持續(xù)改進(jìn),已被越來(lái)越多企業(yè)使用.

但是已有文獻(xiàn)的優(yōu)化中尚存在一些問(wèn)題,如文獻(xiàn)[4]使用貪心策略減小通信代價(jià)容易導(dǎo)致局部最優(yōu);文獻(xiàn)[5]的基于流量感知(Traffic aware)的調(diào)度優(yōu)化策略,僅優(yōu)化了通信代價(jià)這個(gè)維度;文獻(xiàn)[6]采用的圖分方式相比于前面的方式有更好的全局優(yōu)勢(shì),但圖分時(shí)沒(méi)有考慮頂點(diǎn)權(quán)重,負(fù)載均衡上存在問(wèn)題.

本文首先為Storm建立調(diào)度模型,將Topology歸結(jié)于帶權(quán)圖,以減小通信代價(jià)并保證負(fù)載均衡為目標(biāo),提出基于啟發(fā)式均衡圖劃分算法的調(diào)度策略;以負(fù)載檢測(cè)數(shù)據(jù)作為調(diào)度器的輸入,實(shí)現(xiàn)動(dòng)態(tài)調(diào)度、動(dòng)態(tài)并行參數(shù)優(yōu)化和重調(diào)度優(yōu)化;通過(guò)Topology結(jié)構(gòu)分析實(shí)現(xiàn)靜態(tài)任務(wù)分配.最終減少集群節(jié)點(diǎn)間的數(shù)據(jù)發(fā)送率,并且保持節(jié)點(diǎn)間負(fù)載均衡;實(shí)現(xiàn)減少數(shù)據(jù)處理延時(shí),提升集群吞吐量,優(yōu)化整體性能的目標(biāo).

2 問(wèn)題與建模

2.1 問(wèn)題

1)不考慮通信代價(jià)

Storm的EvenScheduler的調(diào)度策略沒(méi)有考慮通信代價(jià).通過(guò)一個(gè)簡(jiǎn)單的實(shí)驗(yàn)來(lái)分析通信代價(jià)對(duì)集群性能的影響.實(shí)驗(yàn)環(huán)境參閱第四部分說(shuō)明.實(shí)驗(yàn)使用Throughput Test topology,它是一個(gè)共有4個(gè)組件的鏈?zhǔn)絋opology,用于吞吐量測(cè)試.實(shí)驗(yàn)測(cè)量一個(gè)消息元組Tuple從Spout出發(fā)到最后處理完成所花費(fèi)的平均時(shí)延,在實(shí)驗(yàn)中為保證節(jié)點(diǎn)不會(huì)過(guò)載,因此將Spout的發(fā)送間隔時(shí)間設(shè)置為了5 ms,還設(shè)置的組件的并行度為1,即一個(gè)組件實(shí)例只有一個(gè)Executor負(fù)責(zé),這樣該Topology一共需要8個(gè)Executor(1 spout+3 bolt+4 ack個(gè)).觀察和分析如下:

圖1 通信代價(jià)對(duì)Tuple時(shí)延的影響

實(shí)驗(yàn)結(jié)果如圖1,所有實(shí)驗(yàn)組都為Executor分配4個(gè)Worker,其中n1組表示這4個(gè)Worker分在同一節(jié)點(diǎn),因此這些Worker之間沒(méi)有網(wǎng)絡(luò)間通信;n2組表示4個(gè)Worker被均分到2個(gè)節(jié)點(diǎn),開(kāi)始出現(xiàn)網(wǎng)絡(luò)間通信;n4組表示4個(gè)Worker被均分到4個(gè)節(jié)點(diǎn),網(wǎng)絡(luò)間通信的代價(jià)進(jìn)一步增大.從圖中可以看出Tuple處理時(shí)延由n1至n4依次增大,在這個(gè)試驗(yàn)中n1與n4組由于增加的通信代價(jià),Tuple處理時(shí)延增加了75%至近2.5倍.

2)負(fù)載不均

EvenScheduler中的排序策略的缺陷會(huì)導(dǎo)致任務(wù)分配失衡,這個(gè)均衡策略對(duì)于單個(gè)Topology的組件是均衡分配的,但無(wú)法保證每個(gè)節(jié)點(diǎn)的計(jì)算負(fù)載相對(duì)均衡.

3)參數(shù)配置難

在實(shí)際Topology t提交時(shí),有兩個(gè)需要手動(dòng)設(shè)置的參數(shù)Worker并行度NUMw(t)和組件并行度NUMe(t).其中NUMe(t)的值則由公式(2)根據(jù)每個(gè)組件的并行度設(shè)置得到.

由于不清楚具體Topology的資源占用,在Topology應(yīng)用開(kāi)發(fā)時(shí)無(wú)法知道這些參數(shù)的最優(yōu)配置.因此開(kāi)發(fā)者在開(kāi)發(fā)完Topology時(shí)需要手動(dòng)監(jiān)視運(yùn)行時(shí)負(fù)載情況,然后根據(jù)經(jīng)驗(yàn)調(diào)整.此外一些應(yīng)用的負(fù)載跟用戶(hù)訪(fǎng)問(wèn)有關(guān),這些配置可能需要隨時(shí)改變.

4)無(wú)法根據(jù)運(yùn)行情況調(diào)整分配

Storm的調(diào)度器都是靜態(tài)的分配任務(wù),沒(méi)有辦法根據(jù)集群的運(yùn)行狀態(tài)動(dòng)態(tài)調(diào)度.在集群運(yùn)行時(shí),Storm默認(rèn)的調(diào)度器的作用除了為新提交的Topology,就是對(duì)異常掛起的Worker而被擱置的Task重新分配Worker.我們還需要在集群運(yùn)行過(guò)程中根據(jù)負(fù)載情況實(shí)現(xiàn)實(shí)時(shí)調(diào)整分配.

2.2 優(yōu)化目標(biāo)

針對(duì)上述問(wèn)題,本文提出以最小化通信代價(jià)為前提,盡量保持負(fù)載均衡的優(yōu)化目標(biāo),以此來(lái)改進(jìn)Storm集群的運(yùn)行效率,提高整體性能.并且通過(guò)對(duì)集群節(jié)點(diǎn)的性能檢測(cè),可以隨時(shí)重調(diào)度以調(diào)整分配結(jié)構(gòu),同時(shí)根據(jù)性能數(shù)據(jù)還可以調(diào)整Topology中的并行度參數(shù),實(shí)現(xiàn)Topology結(jié)構(gòu)的并行優(yōu)化.

2.3 調(diào)度模型及優(yōu)化方案

為達(dá)成上述優(yōu)化目標(biāo),首先需要確立Storm的調(diào)度模型.Storm集群為主從結(jié)構(gòu),集群上運(yùn)行的應(yīng)用是Topology.如圖2所示,Topology結(jié)構(gòu)為一個(gè)有向無(wú)環(huán)圖,箭頭為數(shù)據(jù)傳遞方向.

圖2 Topology結(jié)構(gòu)示例

對(duì)于一個(gè)含有m個(gè)工作節(jié)點(diǎn)Storm集群N={nx|x∈[1,m]},每個(gè)節(jié)點(diǎn)nx配置有Sx個(gè)Slot,那么集群的計(jì)算資源即Slot集合R表示為:R={sxy=|x∈[1,k],y∈[1,Sx]},sxy為節(jié)點(diǎn)nx的第y個(gè)Slot.集群中一共有NUMr(N)個(gè)Slot資源:

(1)

對(duì)于即將提交至集群的Topologyt,若組件數(shù)量為NUMc(t),第i個(gè)組件ci的并行度參數(shù)記作PARALL(ci).即運(yùn)行的Task數(shù)量,為了簡(jiǎn)單起見(jiàn),本文約定一個(gè)Executer執(zhí)行一個(gè)Task.在這種情況下,t的實(shí)例Task數(shù)量等于其所需的Executer數(shù)量,為:

(2)

對(duì)于t而言,若它的Worker并行度參數(shù)配置為NUMw(t),那么資源調(diào)度要做的就是:對(duì)于t的NUMt(t)個(gè)Task實(shí)例均分配給NUMw(t)個(gè)Worker,并將Worker分配到相應(yīng)節(jié)點(diǎn)的相應(yīng)Slot.這樣,對(duì)t的資源調(diào)度可以表示為:

f(E)→W,g(W)→R

(3)

其中,函數(shù)f表示Executor到Worker的映射,函數(shù)g表示W(wǎng)orker到Slot的映射.上述E、W分別表示執(zhí)行Task的Executor集合和容納Executor的Worker集合.一次資源調(diào)度需要滿(mǎn)足以下要求:1)t占用的Worker數(shù)應(yīng)該小于等于集群的Slot數(shù)量;2)而對(duì)于函數(shù)f來(lái)說(shuō),t的Executer一般均勻地分配到Worker;3)當(dāng)前研究版本(即0.9.0)的Storm不允許兩個(gè)不是同一個(gè)Topology的Executor被分配到同一個(gè)Worker.

為優(yōu)化該調(diào)度過(guò)程,需要建立性能采集器,并實(shí)現(xiàn)一個(gè)動(dòng)態(tài)調(diào)度器以根據(jù)運(yùn)行情況實(shí)時(shí)調(diào)度.Topology在Storm集群運(yùn)行過(guò)程中會(huì)產(chǎn)生一些運(yùn)行狀態(tài)數(shù)據(jù),通過(guò)建立性能采集器,可以獲取組件的Executor之間在單位時(shí)間發(fā)送的Tuple數(shù)量、Executor線(xiàn)程的CPU時(shí)間.

其中性能檢測(cè)采集器[4]設(shè)計(jì)如圖3所示,Worker是運(yùn)行Topology的工作進(jìn)程,Executor是執(zhí)行Task的線(xiàn)程.通過(guò)在每個(gè)Worker進(jìn)程中注冊(cè)一個(gè)性能監(jiān)視線(xiàn)程,就可以檢測(cè)這些Worker中各Executor工作負(fù)載及Tuple轉(zhuǎn)發(fā)量.

圖3 負(fù)載檢測(cè)模型

Topology在附加了運(yùn)行時(shí)的檢測(cè)數(shù)據(jù)后,得到如圖4所示的t的拓?fù)浣Y(jié)構(gòu).其中橢圓表示一個(gè)Topology組件,小圓表示運(yùn)行組件實(shí)例Task,小圓內(nèi)數(shù)字則是計(jì)算代價(jià)(Executor線(xiàn)程的CPU時(shí)間),小圓的角標(biāo)“[]”是其頂點(diǎn)ID;有向箭頭是數(shù)據(jù)流向,而箭頭上的數(shù)字則表示通信代價(jià)(Executor之間在單位時(shí)間發(fā)送的Tuple數(shù)量).假設(shè)NUMw(t)=k,表示根據(jù)配置t分到了k個(gè)Worker.

圖4 一個(gè)鏈?zhǔn)絋opology

我們將計(jì)算代價(jià)視作有向圖的頂點(diǎn)權(quán)重,通信代價(jià)視作有向圖的邊權(quán),那么調(diào)度問(wèn)題可以視作一個(gè)圖均衡劃分問(wèn)題,而動(dòng)態(tài)體現(xiàn)在這張圖需要隨著性能檢測(cè)數(shù)據(jù)的變化調(diào)整劃分方式.由于有了性能數(shù)據(jù),在動(dòng)態(tài)調(diào)度器中還可以根據(jù)這些數(shù)據(jù)對(duì)Topology的并行度參數(shù)做一定的優(yōu)化.

3 基于圖劃分的動(dòng)態(tài)調(diào)度

3.1 啟發(fā)式圖劃分算法

1)相關(guān)定義

上述方案指明了Topology的調(diào)度可以視作圖劃分.約定如下定義:

定義(3-1).帶權(quán)圖的最小化割權(quán)均衡k劃分(本文中簡(jiǎn)稱(chēng)均衡圖劃分):給定一個(gè)帶權(quán)圖G=(V,E)和劃分?jǐn)?shù)k,k是正整數(shù).其中V為圖G的頂點(diǎn)集,E為其邊集;代表了連接頂點(diǎn)u和頂點(diǎn)v的邊,給定頂點(diǎn)u,ω(u)表示頂點(diǎn)u上的權(quán)值.同樣,給定頂點(diǎn)u、v,ω(u,v)表示連接頂點(diǎn)u和v的邊的權(quán)值.將V劃分成k個(gè)不相交子集Vi,i=1…k,連接不同子集的邊權(quán)之和最小化,且每個(gè)子集Vi中的子集點(diǎn)權(quán)滿(mǎn)足:

(4)

ω(Vi)=ωe+α

(5)

其中上述的ωe即頂點(diǎn)子集權(quán)重的期望值,因此α越小,表示劃分得越均衡.

定義(3-2).將帶權(quán)圖劃分后,連接兩個(gè)不同子集的邊權(quán)之和稱(chēng)為割權(quán).

2)均衡劃分算法

針對(duì)上述提出的調(diào)度模型,本節(jié)提出了啟發(fā)式算法K-PART來(lái)尋找?guī)?quán)的劃分.根據(jù)優(yōu)化目標(biāo),要求劃分后各分組計(jì)算量差異最小,且最小化通信代價(jià).因此所提算法K-PART劃分策略是保證子集點(diǎn)權(quán)近似均衡的條件下,采用最大化子集內(nèi)邊權(quán)的策略[11]來(lái)最小化子集間的割權(quán).假設(shè)要構(gòu)建的k個(gè)子集分別是V1…Vk,算法首先將所有頂點(diǎn)移動(dòng)到Vk中,同時(shí)計(jì)算子集點(diǎn)權(quán)的期望值ωe;然后逐個(gè)構(gòu)建k-1個(gè)子集.構(gòu)建子集Vi,i=1…k-1時(shí),每次從Vk中取出使Vi子集邊權(quán)增益最大的頂點(diǎn)v,放入Vi,直到Vi的子集點(diǎn)權(quán)到達(dá)條件.

構(gòu)建子集Vi流程如下:輸入?yún)?shù)是圖G(V,E),k為劃分?jǐn)?shù).首先是初始化計(jì)算,根據(jù)參數(shù)計(jì)算頂點(diǎn)子集點(diǎn)權(quán)的期望值ωe,初始化一個(gè)空的子集Vi,并且將圖G所有的頂點(diǎn)都放在子集Vk中.然后開(kāi)始為Vi分配頂點(diǎn),為保證結(jié)果多樣性,先隨機(jī)從Vk中選擇一個(gè)頂點(diǎn)vi到Vi;此時(shí)vi∈Vi,在Vk中與vi有鄰接關(guān)系的點(diǎn)都被加入候選頂點(diǎn)的集合S,從S中選擇一個(gè)vj,使得Vi子集邊權(quán)增益最大,同時(shí)Vk中所有vj的鄰接頂點(diǎn)被加入到S中.然后接著從S中取下一個(gè)使Vi子集邊權(quán)增益最大頂點(diǎn),直到滿(mǎn)足條件ωe+α.到子集V1…Vk-1建立完成后,Vk中剩余頂點(diǎn)都屬于Vk.其中頂點(diǎn)vj帶給Vi的子集邊權(quán)的增益是指,頂點(diǎn)vj從候選集S移動(dòng)到Vi后,與移動(dòng)之前所有屬于Vi的頂點(diǎn)的邊權(quán)和之差,即:

gain(v)=∑u∈Viω(u,v)-∑u∈Vkω(u,v)

(6)

算法形式化描述如下:

Input:G(V,E)、k

Output:Result={V1,…,Vk}

1 Start:

3 FOR(i=1;i<=k-1;i++)

4 S=?,Vi=?,v=null;

5 WHILE (ω(Vi)<=ωe)

6 IF(Vi==?)

7 v=random(Vk);

8 ELSE

9 v=MAX(gain(u),u∈S);

10 ENDIF

11 Vi+=v,Vk-=v;

12 S+=Neighbor(v,u,u∈Vk);

13 END WHILE

14 Result+= Vi;

15 ENDFOR

16 END

3)平衡性調(diào)整策略

使用K-PART調(diào)度之后還是會(huì)帶來(lái)分配不均的問(wèn)題,還是由劃分策略導(dǎo)致的.因?yàn)閳D是按照頂點(diǎn)來(lái)劃分的,特別是在頂點(diǎn)數(shù)和劃分?jǐn)?shù)的比值接近1的時(shí)候(當(dāng)然我們不考慮小于1的情況,這樣沒(méi)有意義),由于挑選的時(shí)候僅按照子集邊權(quán)增益選取,并且每個(gè)子集都會(huì)在大于期望值時(shí)停止,當(dāng)劃分Vk-1時(shí)候選集已沒(méi)有可分頂點(diǎn)了或者沒(méi)有剩余頂點(diǎn)給Vk,亦或者Vk的子集點(diǎn)權(quán)遠(yuǎn)小于期望值.

因此本文再提出一個(gè)K-PART之后的平衡性調(diào)整策略,基本思想是:在最大子集點(diǎn)權(quán)的子集(作為候選集)中,選擇一個(gè)使那個(gè)最小子集點(diǎn)權(quán)的子集的邊權(quán)增益最大的點(diǎn),移動(dòng)到最小子集點(diǎn)權(quán)的子集中.迭代次數(shù)為圖的頂點(diǎn)數(shù)量的倍數(shù),稱(chēng)之為迭代倍率.這里用倍率來(lái)計(jì)算迭代次數(shù),是為了期望每個(gè)點(diǎn)在單位迭代倍率下都有可能被遍歷到.此外,當(dāng)最大子集點(diǎn)權(quán)的子集僅包含一個(gè)元素時(shí),則將次大子集點(diǎn)權(quán)的集合作為候選集.

定義(3-3)迭代倍率:在本文的平衡性調(diào)整策略中,迭代倍率就是被劃分圖頂點(diǎn)數(shù)量的倍數(shù).

具體流程如下:K-PART的劃分結(jié)果Result和迭代倍率Mul作為平衡性調(diào)整策略的參數(shù).將Result={V1,…,Vk}結(jié)果集中的元素按照子集點(diǎn)權(quán)從小到大排序,那么Vmax=Result[k-1],Vmin=Result[0];它們分別對(duì)應(yīng)公式(4-5)中的Vk和Vi,取Vmax中元素代入公式,找出一個(gè)使增益最大的頂點(diǎn)v,將v移動(dòng)到Vmin,完成一次迭代;當(dāng)Vmax中僅一個(gè)元素,則將次大集賦給Vmax.重復(fù)上述操作直到迭代NUM(V)*Mul次.

算法形式化描述如下:

Input:Result={V1,…,Vk}、Mul

Output:Result={V1,…,Vk}

1 Start:

2 FOR(i=0;i<=Mul*NUM(V);i++)

3 Result=sort(Result);//sort by ∑v∈Viω(v)

4 Vmax=Result[k-1];

5 Vmin=Result[0],idx=Result.size();

6 WHILE(Vmax.size==1&&idx--!=1)

7 Vmax=Result[idx];

8 ENDWHILE

9 v=MAX(gain(u),u∈Vmax);

10 Vmin+=v,Vmax-=v;

11 ENDFOR

12 END

當(dāng)然,這個(gè)策略也會(huì)影響劃分在通信代價(jià)上的優(yōu)化,需要有一定的權(quán)衡.參閱第四章的實(shí)驗(yàn).

3.2 仿真實(shí)驗(yàn)

1)實(shí)驗(yàn)條件描述

實(shí)驗(yàn)中采用隨機(jī)帶權(quán)圖,給定數(shù)量的定點(diǎn)數(shù)與邊數(shù),它們的邊隨機(jī)與頂點(diǎn)關(guān)聯(lián),邊權(quán)和頂點(diǎn)權(quán)重都被隨機(jī)設(shè)置為1～100的整數(shù).并且以如下指標(biāo)來(lái)評(píng)價(jià)結(jié)果的優(yōu)劣:

①割權(quán)比:衡量通信代價(jià)的優(yōu)化程度,割權(quán)比是割權(quán)與圖的總邊權(quán)之比,值越小表示通信代價(jià)越小.割權(quán)比計(jì)算如下

cutRate:

(7)

②標(biāo)準(zhǔn)差與最大偏差率

這兩個(gè)指標(biāo)用戶(hù)衡量劃分均衡度.這里的標(biāo)準(zhǔn)差特指圖劃分子集后,將每個(gè)子集的子集點(diǎn)權(quán)作為統(tǒng)計(jì)樣本計(jì)算得到的標(biāo)準(zhǔn)差.而這個(gè)最大偏差率則用來(lái)評(píng)價(jià)某些個(gè)體相比于期望負(fù)載的最大偏差,最大偏差率計(jì)算方式如下:

(8)

2)自身對(duì)比實(shí)驗(yàn)

自身對(duì)比實(shí)驗(yàn)用于測(cè)試迭代倍率對(duì)K-PART算法對(duì)劃分效果的影響.自身對(duì)比實(shí)驗(yàn)的基本流程如下:1)隨機(jī)生成帶權(quán)圖10張;2)每張圖在不同迭代倍率的情況下分別做10次劃分對(duì)比;3)整理實(shí)驗(yàn)結(jié)果,統(tǒng)計(jì)計(jì)算每次實(shí)驗(yàn)的各個(gè)指標(biāo).實(shí)驗(yàn)中隨機(jī)生成的10張圖都為G(24,36);劃分?jǐn)?shù)固定為k=3,迭代次數(shù)Mul從0增長(zhǎng)到9倍,其中0表示不進(jìn)行迭代.實(shí)驗(yàn)結(jié)果如圖5所示.

從圖5(a)的結(jié)果反映了隨著迭代倍率增加,割權(quán)比會(huì)有少量的增加;從圖5(b)和圖5(c)的結(jié)果看出,隨著迭代倍率的增加,子集點(diǎn)權(quán)的標(biāo)準(zhǔn)差和最大偏差率都有大幅度減小.

3)對(duì)照組實(shí)驗(yàn)

對(duì)照組實(shí)驗(yàn)用于比對(duì)本文算法與其他調(diào)度策略在輸入不同復(fù)雜度的帶權(quán)圖及不同劃分?jǐn)?shù)的情況下的分配效果.比較對(duì)象是:1)K-PART:本文算法;2)T-PART:文獻(xiàn)[4]基于Traffic的OnlineScheduler中的劃分算法;3)M-PART:文獻(xiàn)[6]基于Metis的P-Scheduler;

為了方便對(duì)比,本文統(tǒng)一重新實(shí)現(xiàn)對(duì)照組調(diào)度器的算法,并且輸入相同格式的Topology圖數(shù)據(jù)進(jìn)行實(shí)驗(yàn).

圖5 迭代倍率對(duì)劃分效果的影響

實(shí)驗(yàn)1.流程如下:1)隨機(jī)生成10張帶權(quán)圖,劃分?jǐn)?shù)k逐漸增加;2)分別使用上述算法進(jìn)行調(diào)度,每個(gè)算法都會(huì)對(duì)每張圖作10次劃分;3)對(duì)調(diào)度結(jié)果進(jìn)行評(píng)估統(tǒng)計(jì),計(jì)算每組指標(biāo)的平均值.實(shí)驗(yàn)中圖都為G(24,36),劃分?jǐn)?shù)k從2增加到24,平衡性調(diào)整的迭代次數(shù)Mul=0或者M(jìn)ul=5.實(shí)驗(yàn)結(jié)果如圖6所示.

從圖6的實(shí)驗(yàn)結(jié)果可以看出,當(dāng)劃分?jǐn)?shù)從2開(kāi)始增加到接近總的頂點(diǎn)數(shù)時(shí),各個(gè)算法的割權(quán)比和最大偏差率都會(huì)有上升趨勢(shì),權(quán)重標(biāo)準(zhǔn)差相對(duì)穩(wěn)定(除了M-PART),這意味著劃分的通信代價(jià)優(yōu)化和均衡度都會(huì)變差.在劃分?jǐn)?shù)為頂點(diǎn)數(shù)的1/2及以下時(shí),K-PART(Mul=0)的劃分效果都是比較優(yōu)秀的;K-PART(Mul=5)和T-PART次之,而M-PART也不錯(cuò),但其結(jié)果非常不穩(wěn)定.當(dāng)劃分?jǐn)?shù)比頂點(diǎn)數(shù)趨向于1時(shí),K-PART(Mul=5)的割權(quán)比也趨向于1.這是因?yàn)檫@里圖劃分算法是按頂點(diǎn)為單位開(kāi)始劃分的,因此在劃分?jǐn)?shù)比頂點(diǎn)數(shù)趨向于1時(shí),由于K-PART平衡性調(diào)整策略的作用,使得每個(gè)子集僅包含1個(gè)元素,因此割權(quán)等于總邊權(quán).K-PART(Mul=0)和T-PART以減少割權(quán)比優(yōu)先,因此在達(dá)到一定程度時(shí)優(yōu)先保證了割權(quán)比;M-PART似乎走了減少割權(quán)比的極端,割權(quán)比占優(yōu)的M-PART在均衡度上將會(huì)大打折扣,分析發(fā)現(xiàn)其產(chǎn)生大量空集.

實(shí)驗(yàn)2.流程如下:1)隨機(jī)生成10組固定頂點(diǎn)數(shù),邊數(shù)依

圖6 劃分?jǐn)?shù)對(duì)劃分效果影響

次增加的帶權(quán)圖,每組10張圖;2)分別使用上述算法進(jìn)行調(diào)度劃分,每個(gè)算法都會(huì)對(duì)每張圖作10次劃分;3)對(duì)調(diào)度結(jié)果進(jìn)行評(píng)估統(tǒng)計(jì),計(jì)算每組指標(biāo)的平均值.實(shí)驗(yàn)中帶權(quán)圖頂點(diǎn)數(shù)固定12,邊數(shù)從15開(kāi)始增加,步進(jìn)3;每個(gè)邊數(shù)的小組各10張圖,劃分?jǐn)?shù)k固定為3,平衡性調(diào)整的迭代次數(shù)Mul=0或者M(jìn)ul=5.實(shí)驗(yàn)結(jié)果如圖7所示.

圖7 圖連接復(fù)雜度對(duì)劃分效果的影響

由圖7的實(shí)驗(yàn)結(jié)果可以看出,圖的連接復(fù)雜度并沒(méi)有明顯影響算法對(duì)劃分結(jié)果中的割權(quán)比、標(biāo)準(zhǔn)差與最大偏差率指標(biāo).同時(shí)上述10組實(shí)驗(yàn)中,本文算法K-PART在平衡性調(diào)整迭代倍率Mul=0的實(shí)驗(yàn)組的劃分割權(quán)比一直是最小的,因此它對(duì)通信代價(jià)的優(yōu)化程度在這幾組中是最好的;在平衡性調(diào)整迭代倍率Mul=5的實(shí)驗(yàn)組中,劃分的均衡度一直是最優(yōu)的.

4)實(shí)驗(yàn)結(jié)論

①在所對(duì)比的試驗(yàn)中,本文算法的劃分效果優(yōu)于對(duì)比算法;其中Mul>0時(shí),在均衡度上占優(yōu),Mul=0則在割權(quán)比上占優(yōu);②所有對(duì)比的算法中,劃分?jǐn)?shù)與頂點(diǎn)數(shù)的比值越小,劃分效果越好;③對(duì)于本文算法,平衡性調(diào)正策略迭代次數(shù)越多,分配越趨于均衡;但是會(huì)損失一些割權(quán)比上的優(yōu)化.

3.3 動(dòng)態(tài)調(diào)度策略

1)調(diào)度策略

根據(jù)前文對(duì)調(diào)度的定義,它包含f(E)→W和g(W)→R兩步.在滿(mǎn)足調(diào)度必要性的條件判斷之后開(kāi)始執(zhí)行調(diào)度.第一步f(E)→W的本質(zhì)上是根據(jù)t的配置生成E、W,利用前文提出的K-PART算法將E均勻劃分,分配到W中.第二步g(W)→R則需要完成將第一步中得到的Worker總集合W按照設(shè)定目標(biāo)分配到物理節(jié)點(diǎn)集N.

最后在調(diào)度生效之前,還需做進(jìn)一步調(diào)整.算法遍歷各節(jié)點(diǎn)的Worker,如果在同一個(gè)節(jié)點(diǎn)存在多個(gè)同一Topology的Worker,還可對(duì)其Executor執(zhí)行一次均分.滿(mǎn)足調(diào)度必要規(guī)則條件時(shí)生效這次調(diào)度.

調(diào)度生效的必要規(guī)則如下:在調(diào)度之前,調(diào)度器根據(jù)性能監(jiān)測(cè)數(shù)據(jù)計(jì)算節(jié)點(diǎn)間Tuple發(fā)送率和均衡度指標(biāo);調(diào)度器計(jì)算新的分配方案之后,利用舊的性能監(jiān)測(cè)數(shù)據(jù)估算這兩個(gè)性能指標(biāo),當(dāng)估算值都優(yōu)于原指標(biāo)時(shí),開(kāi)始實(shí)施重調(diào)度.算法形式化描述如下:

2)動(dòng)態(tài)并行參數(shù)優(yōu)化

Storm的并行度參數(shù)主要有三個(gè):Worker并行度參數(shù)和Executor并行度參數(shù)以及Task并行度參數(shù),后兩者的乘積為組件的并行度;由于本文只考慮一個(gè)Executor只運(yùn)行一個(gè)Task的情況,則Executor并行度等于組件的并行度.Worker并行度參數(shù)表示為一個(gè)Topology分配的Worker數(shù)量,對(duì)于這個(gè)參數(shù),只要在資源允許的條件下是越大越好的.同一個(gè)Topology的不同組件的并行度參數(shù)就不能像上述Worker并行度參數(shù)那樣設(shè)置了.

本文實(shí)現(xiàn)的動(dòng)態(tài)調(diào)度器中,對(duì)于組件的并行度參數(shù)優(yōu)化策略如下:

①輸入:Executor負(fù)載數(shù)據(jù),Topology結(jié)構(gòu)t;

②分組計(jì)算:對(duì)Executor按照所屬組件分組求和,得到組件的CPU計(jì)算量L;

③求比:對(duì)于屬于t的任意組件ci和組件cj,如果數(shù)據(jù)由ci向cj傳遞,且L(ci):L(cj)=a:b,則PARALL(ci):PARALL(cj)=a:b;

④整合優(yōu)化:整合組件間并行化參數(shù)比,將并行化參數(shù)之和等比擴(kuò)大到Worker進(jìn)程的線(xiàn)程數(shù)推薦值(10～15,該值是Storm開(kāi)源軟件作者Nathan給出);

⑤生效:遍歷t的組件,修改其并行度參數(shù).

3)重調(diào)度優(yōu)化

動(dòng)態(tài)調(diào)度策略根據(jù)當(dāng)前的性能數(shù)據(jù)計(jì)算出新的分配方案后,面臨一個(gè)Worker重新分配部署的問(wèn)題.重新部署時(shí)需要先將相應(yīng)Worker關(guān)閉,在新的節(jié)點(diǎn)的相應(yīng)Slot重新開(kāi)啟.這是一個(gè)相對(duì)消耗資源的過(guò)程,并且會(huì)帶來(lái)服務(wù)中斷.因此在實(shí)施重調(diào)度優(yōu)化的目標(biāo)是:減少重調(diào)度對(duì)計(jì)算服務(wù)的影響,實(shí)現(xiàn)平滑的重新分配.

本文提出的重調(diào)度優(yōu)化的基本思想是減少Worker遷移數(shù),在遷移數(shù)不能減少的情況下優(yōu)先移動(dòng)計(jì)算量小的Worker,并且對(duì)Worker分批遷移.

具體流程如下:

①輸入:以集群當(dāng)前分配表Acur與動(dòng)態(tài)調(diào)度策略得到的新分配表Anew為輸入;

②待重調(diào)度集Sreassign:Acur中的每個(gè)Worker遍歷比較Anew中Worker的Task分配,Acur中Worker的Task發(fā)生變化的Worker移動(dòng)到待重調(diào)度集Sreassign;

③待重調(diào)度集Sreassign:Acur中的Worker按照Node分組,并按照Worker數(shù)量對(duì)Node分組由大到小排序;每次取出第一組,如果該組中的Worker在Anew中位于同一個(gè)Part,則不操作繼續(xù)取下一組;否則取出改組中計(jì)算量最小的Worker放入Sreassign,直到該組中的Worker都對(duì)應(yīng)到Anew中的同一個(gè)Part;

④遷移Worker:首先從Sreassign中隨機(jī)取出一個(gè)Worker記作當(dāng)前遷移對(duì)象Q,根據(jù)Anew找到Q應(yīng)當(dāng)分配到的Acur中Node分組,如Q的Task與Acur中不一致則重新分配Task,然后關(guān)閉一個(gè)Node分組中一個(gè)屬于Sreassign的Worker,并由Q替換且從Sreassign移除,分配完后將被關(guān)閉的Worker記作Q.直到為Sreassign空.

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

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

實(shí)驗(yàn)在一個(gè)由安裝ESXI6.0系統(tǒng)的Dell R710服務(wù)器上的虛擬化集群進(jìn)行.服務(wù)器的基本配置如下:CPU:Intel(R)Xeon(R)X5650,2.67GHz×6 core×2;RAM:128GB;1Gbps×4的網(wǎng)卡以及2個(gè)1T硬盤(pán)組成的磁盤(pán)陣列.

虛擬節(jié)點(diǎn)的配置是:每個(gè)虛擬節(jié)點(diǎn)CPU為2.67GHz×4 core、RAM為4GB,并用1Gbps的網(wǎng)絡(luò)連接;操作系統(tǒng)是Ubuntu 14.04 X86_64(Linux 4.2.0).集群布置如表1所示.

表1 Storm節(jié)點(diǎn)配置

為了記錄Topology運(yùn)行時(shí)數(shù)據(jù),專(zhuān)門(mén)設(shè)計(jì)了一個(gè)Topology,該Topology基于Word Count Topology[12].該Topology一共有4個(gè)組件,Worker的默認(rèn)配置數(shù)為8,組件的默認(rèn)設(shè)為并行度為4.為方便實(shí)驗(yàn),本文對(duì)其進(jìn)行了以下改造:1)在該Topology的每個(gè)組件初始化方法中增加性能監(jiān)視器的注冊(cè),每個(gè)處理方法中通信Tuple統(tǒng)計(jì);2)為了采集Tuple處理時(shí)延和吞吐量,在Spout發(fā)送消息時(shí)增加發(fā)送時(shí)間戳字段,并在Storm的可靠性保障中的ACK接口實(shí)現(xiàn)中增加時(shí)間差計(jì)算和消息計(jì)數(shù).另外,為保證時(shí)間相關(guān)的測(cè)量數(shù)據(jù)的準(zhǔn)確性,集群所有節(jié)點(diǎn)配置了NTP時(shí)間同步協(xié)議來(lái)同步集群時(shí)間.

4.2 評(píng)價(jià)指標(biāo)

本文用如下指標(biāo)評(píng)價(jià)性能:1)Tuple處理時(shí)延,即指一個(gè)Tuple從Spout發(fā)出后,直到處理完全后Spout收到Ack信號(hào)所花費(fèi)的時(shí)間,反映集群的響應(yīng)效率,該指標(biāo)越小越好；2)單位時(shí)間Tuple處理量,即每秒處理的Tuple個(gè)數(shù),反映集群的吞吐量,該指標(biāo)越大越好.

本文用均衡度與節(jié)點(diǎn)間Tuple轉(zhuǎn)發(fā)率指標(biāo)評(píng)價(jià)調(diào)度效果.均衡度是性能采集器采集的各節(jié)點(diǎn)的CPU計(jì)算量的標(biāo)準(zhǔn)差,節(jié)點(diǎn)間Tuple轉(zhuǎn)發(fā)率的值等于通過(guò)網(wǎng)絡(luò)發(fā)送Tuple數(shù)量和集群所有Tuple數(shù)量之比.這兩個(gè)指標(biāo)相當(dāng)于圖均衡劃分中的標(biāo)準(zhǔn)差與割權(quán)比,調(diào)度效果的評(píng)價(jià)指標(biāo)越好,越有利于實(shí)際性能指標(biāo)的提升.

4.3 對(duì)比實(shí)驗(yàn)

實(shí)驗(yàn)中給出的指標(biāo)數(shù)據(jù)由本文實(shí)現(xiàn)的性能監(jiān)視器保存在性能數(shù)據(jù)庫(kù)中的數(shù)據(jù)整理得到.比較對(duì)象是:

1)KPartScheduler:由本文算法實(shí)現(xiàn)的動(dòng)態(tài)調(diào)度器;

2)OnlineScheduler:文獻(xiàn)[8]基于Traffic的在線(xiàn)實(shí)時(shí)調(diào)度器;

3)EvenScheduler:Storm中自帶的均衡調(diào)度器.

1)調(diào)度器指標(biāo)

圖8為集群運(yùn)行時(shí)的節(jié)點(diǎn)間CPU計(jì)算量的標(biāo)準(zhǔn)差.由圖可知,在當(dāng)前給定實(shí)驗(yàn)環(huán)境下KPartScheduler和OnlineScheduler在均衡度方面相差不大,但是EvenScheduler在均衡度上要明顯差于前兩者.

圖9為集群運(yùn)行時(shí)的節(jié)點(diǎn)間Tuple發(fā)送率.由圖可知,在當(dāng)前給定實(shí)驗(yàn)環(huán)境下KPartScheduler在通信代價(jià)優(yōu)化上要優(yōu)于OnlineScheduler,EvenScheduler對(duì)通信代價(jià)的優(yōu)化是最差的,分別比KPartScheduler、OnlineScheduler調(diào)度器差5、3個(gè)百分點(diǎn).

2)性能指標(biāo)對(duì)比

圖10為集群運(yùn)行時(shí)的Tuple處理時(shí)延.由圖可知,在當(dāng)前給定實(shí)驗(yàn)環(huán)境下,KPartScheduler調(diào)度器下的集群Tuple處理時(shí)延隨著系統(tǒng)運(yùn)行中的不斷重調(diào)度,處理時(shí)延越來(lái)越小;OnlineScheduler在前期收斂速度快,迅速達(dá)到的較優(yōu)狀態(tài),但是系統(tǒng)最終穩(wěn)定時(shí),KPartScheduler調(diào)度下的Tuple處理時(shí)延要低于OnlineScheduler.而EvenScheduler在分配Topology后一直保持相對(duì)穩(wěn)定的運(yùn)行狀態(tài),且最終在Tuple處理時(shí)延性能上被前兩者超越.

圖8 集群節(jié)點(diǎn)間計(jì)算量標(biāo)準(zhǔn)差

圖9 節(jié)點(diǎn)間Tuple發(fā)送率

圖10 運(yùn)行時(shí)Tuple處理時(shí)延

單位時(shí)間Tuple處理量就是集群吞吐量的反映.圖11為集群運(yùn)行時(shí)單位時(shí)間Tuple處理量.由Topology開(kāi)始運(yùn)行到運(yùn)行狀態(tài)趨于穩(wěn)定,KPartScheduler和OnlineScheduler下的吞吐量相差不大,到后期KPartScheduler出現(xiàn)一定的優(yōu)勢(shì).運(yùn)行前期OnlineScheduler以最快的速度達(dá)到較優(yōu)狀態(tài).

圖11 運(yùn)行時(shí)單位時(shí)間消息處理量

5 結(jié) 論

本文針對(duì)Storm大數(shù)據(jù)流式框架中自身調(diào)度算法以及已有優(yōu)化方案存在的負(fù)載不均、資源利用率不高等問(wèn)題,提出基于啟發(fā)式圖均衡劃分算法的動(dòng)態(tài)調(diào)度策略.動(dòng)態(tài)調(diào)度器可根據(jù)性能數(shù)據(jù)進(jìn)行實(shí)時(shí)動(dòng)態(tài)的調(diào)度,并實(shí)現(xiàn)并行參數(shù)優(yōu)化和重調(diào)度優(yōu)化.

實(shí)驗(yàn)測(cè)試用Topology在本文調(diào)度器調(diào)度下的運(yùn)行時(shí)均衡度和節(jié)點(diǎn)間Tuple發(fā)送率的優(yōu)化效果都比對(duì)比算法有小幅度提升,最終隨著調(diào)度效果的優(yōu)化,使得集群的吞吐量比對(duì)比調(diào)度器提升了近20%以上,而在Tuple處理延時(shí)上減少了1～2ms.因此,本文調(diào)度器在一定程度上可以提升Storm集群運(yùn)行的性能.