Storm啟發式均衡圖劃分調度優化方法

簡琤峰,盧 濤,張美玉

(浙江工業大學 計算機學院 數字媒體技術研究所,杭州 310023)

1 引 言

面向移動互聯網和大數據應用的實時數據流式處理技術[1,2]成為近年來相關研究領域的熱點.Storm[3]提供了一種優秀的實時大數據流式計算模式得以廣泛應用.但隨著深入應用,其在資源和任務的調度策略上存在的問題也越來越突出:通信代價作為影響流式數據處理效率的重要因素,Storm調度器沒有將其作為考慮因素;自帶的均衡調度器會導致負載不均;并行度參數需要手動配置;無法根據集群運行狀況對任務重調度等問題直接影響Storm集群的運行性能.

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

但是已有文獻的優化中尚存在一些問題,如文獻[4]使用貪心策略減小通信代價容易導致局部最優;文獻[5]的基于流量感知(Traffic aware)的調度優化策略,僅優化了通信代價這個維度;文獻[6]采用的圖分方式相比于前面的方式有更好的全局優勢,但圖分時沒有考慮頂點權重,負載均衡上存在問題.

本文首先為Storm建立調度模型,將Topology歸結于帶權圖,以減小通信代價并保證負載均衡為目標,提出基于啟發式均衡圖劃分算法的調度策略;以負載檢測數據作為調度器的輸入,實現動態調度、動態并行參數優化和重調度優化;通過Topology結構分析實現靜態任務分配.最終減少集群節點間的數據發送率,并且保持節點間負載均衡;實現減少數據處理延時,提升集群吞吐量,優化整體性能的目標.

2 問題與建模

2.1 問題

1)不考慮通信代價

Storm的EvenScheduler的調度策略沒有考慮通信代價.通過一個簡單的實驗來分析通信代價對集群性能的影響.實驗環境參閱第四部分說明.實驗使用Throughput Test topology,它是一個共有4個組件的鏈式Topology,用于吞吐量測試.實驗測量一個消息元組Tuple從Spout出發到最后處理完成所花費的平均時延,在實驗中為保證節點不會過載,因此將Spout的發送間隔時間設置為了5 ms,還設置的組件的并行度為1,即一個組件實例只有一個Executor負責,這樣該Topology一共需要8個Executor(1 spout+3 bolt+4 ack個).觀察和分析如下:

圖1 通信代價對Tuple時延的影響

實驗結果如圖1,所有實驗組都為Executor分配4個Worker,其中n1組表示這4個Worker分在同一節點,因此這些Worker之間沒有網絡間通信;n2組表示4個Worker被均分到2個節點,開始出現網絡間通信;n4組表示4個Worker被均分到4個節點,網絡間通信的代價進一步增大.從圖中可以看出Tuple處理時延由n1至n4依次增大,在這個試驗中n1與n4組由于增加的通信代價,Tuple處理時延增加了75%至近2.5倍.

2)負載不均

EvenScheduler中的排序策略的缺陷會導致任務分配失衡,這個均衡策略對于單個Topology的組件是均衡分配的,但無法保證每個節點的計算負載相對均衡.

3)參數配置難

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

由于不清楚具體Topology的資源占用,在Topology應用開發時無法知道這些參數的最優配置.因此開發者在開發完Topology時需要手動監視運行時負載情況,然后根據經驗調整.此外一些應用的負載跟用戶訪問有關,這些配置可能需要隨時改變.

4)無法根據運行情況調整分配

Storm的調度器都是靜態的分配任務,沒有辦法根據集群的運行狀態動態調度.在集群運行時,Storm默認的調度器的作用除了為新提交的Topology,就是對異常掛起的Worker而被擱置的Task重新分配Worker.我們還需要在集群運行過程中根據負載情況實現實時調整分配.

2.2 優化目標

針對上述問題,本文提出以最小化通信代價為前提,盡量保持負載均衡的優化目標,以此來改進Storm集群的運行效率,提高整體性能.并且通過對集群節點的性能檢測,可以隨時重調度以調整分配結構,同時根據性能數據還可以調整Topology中的并行度參數,實現Topology結構的并行優化.

2.3 調度模型及優化方案

為達成上述優化目標,首先需要確立Storm的調度模型.Storm集群為主從結構,集群上運行的應用是Topology.如圖2所示,Topology結構為一個有向無環圖,箭頭為數據傳遞方向.

圖2 Topology結構示例

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

(1)

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

(2)

對于t而言,若它的Worker并行度參數配置為NUMw(t),那么資源調度要做的就是:對于t的NUMt(t)個Task實例均分配給NUMw(t)個Worker,并將Worker分配到相應節點的相應Slot.這樣,對t的資源調度可以表示為:

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

(3)

其中,函數f表示Executor到Worker的映射,函數g表示Worker到Slot的映射.上述E、W分別表示執行Task的Executor集合和容納Executor的Worker集合.一次資源調度需要滿足以下要求:1)t占用的Worker數應該小于等于集群的Slot數量;2)而對于函數f來說,t的Executer一般均勻地分配到Worker;3)當前研究版本(即0.9.0)的Storm不允許兩個不是同一個Topology的Executor被分配到同一個Worker.

為優化該調度過程,需要建立性能采集器,并實現一個動態調度器以根據運行情況實時調度.Topology在Storm集群運行過程中會產生一些運行狀態數據,通過建立性能采集器,可以獲取組件的Executor之間在單位時間發送的Tuple數量、Executor線程的CPU時間.

其中性能檢測采集器[4]設計如圖3所示,Worker是運行Topology的工作進程,Executor是執行Task的線程.通過在每個Worker進程中注冊一個性能監視線程,就可以檢測這些Worker中各Executor工作負載及Tuple轉發量.

圖3 負載檢測模型

Topology在附加了運行時的檢測數據后,得到如圖4所示的t的拓撲結構.其中橢圓表示一個Topology組件,小圓表示運行組件實例Task,小圓內數字則是計算代價(Executor線程的CPU時間),小圓的角標“[]”是其頂點ID;有向箭頭是數據流向,而箭頭上的數字則表示通信代價(Executor之間在單位時間發送的Tuple數量).假設NUMw(t)=k,表示根據配置t分到了k個Worker.

圖4 一個鏈式Topology

我們將計算代價視作有向圖的頂點權重,通信代價視作有向圖的邊權,那么調度問題可以視作一個圖均衡劃分問題,而動態體現在這張圖需要隨著性能檢測數據的變化調整劃分方式.由于有了性能數據,在動態調度器中還可以根據這些數據對Topology的并行度參數做一定的優化.

3 基于圖劃分的動態調度

3.1 啟發式圖劃分算法

1)相關定義

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

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

(4)

ω(Vi)=ωe+α

(5)

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

定義(3-2).將帶權圖劃分后,連接兩個不同子集的邊權之和稱為割權.

2)均衡劃分算法

針對上述提出的調度模型,本節提出了啟發式算法K-PART來尋找帶權的劃分.根據優化目標,要求劃分后各分組計算量差異最小,且最小化通信代價.因此所提算法K-PART劃分策略是保證子集點權近似均衡的條件下,采用最大化子集內邊權的策略[11]來最小化子集間的割權.假設要構建的k個子集分別是V1…Vk,算法首先將所有頂點移動到Vk中,同時計算子集點權的期望值ωe;然后逐個構建k-1個子集.構建子集Vi,i=1…k-1時,每次從Vk中取出使Vi子集邊權增益最大的頂點v,放入Vi,直到Vi的子集點權到達條件.

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

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)平衡性調整策略

使用K-PART調度之后還是會帶來分配不均的問題,還是由劃分策略導致的.因為圖是按照頂點來劃分的,特別是在頂點數和劃分數的比值接近1的時候(當然我們不考慮小于1的情況,這樣沒有意義),由于挑選的時候僅按照子集邊權增益選取,并且每個子集都會在大于期望值時停止,當劃分Vk-1時候選集已沒有可分頂點了或者沒有剩余頂點給Vk,亦或者Vk的子集點權遠小于期望值.

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

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

具體流程如下:K-PART的劃分結果Result和迭代倍率Mul作為平衡性調整策略的參數.將Result={V1,…,Vk}結果集中的元素按照子集點權從小到大排序,那么Vmax=Result[k-1],Vmin=Result[0];它們分別對應公式(4-5)中的Vk和Vi,取Vmax中元素代入公式,找出一個使增益最大的頂點v,將v移動到Vmin,完成一次迭代;當Vmax中僅一個元素,則將次大集賦給Vmax.重復上述操作直到迭代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

當然,這個策略也會影響劃分在通信代價上的優化,需要有一定的權衡.參閱第四章的實驗.

3.2 仿真實驗

1)實驗條件描述

實驗中采用隨機帶權圖,給定數量的定點數與邊數,它們的邊隨機與頂點關聯,邊權和頂點權重都被隨機設置為1～100的整數.并且以如下指標來評價結果的優劣:

①割權比:衡量通信代價的優化程度,割權比是割權與圖的總邊權之比,值越小表示通信代價越小.割權比計算如下

cutRate:

(7)

②標準差與最大偏差率

這兩個指標用戶衡量劃分均衡度.這里的標準差特指圖劃分子集后,將每個子集的子集點權作為統計樣本計算得到的標準差.而這個最大偏差率則用來評價某些個體相比于期望負載的最大偏差,最大偏差率計算方式如下:

(8)

2)自身對比實驗

自身對比實驗用于測試迭代倍率對K-PART算法對劃分效果的影響.自身對比實驗的基本流程如下:1)隨機生成帶權圖10張;2)每張圖在不同迭代倍率的情況下分別做10次劃分對比;3)整理實驗結果,統計計算每次實驗的各個指標.實驗中隨機生成的10張圖都為G(24,36);劃分數固定為k=3,迭代次數Mul從0增長到9倍,其中0表示不進行迭代.實驗結果如圖5所示.

從圖5(a)的結果反映了隨著迭代倍率增加,割權比會有少量的增加;從圖5(b)和圖5(c)的結果看出,隨著迭代倍率的增加,子集點權的標準差和最大偏差率都有大幅度減小.

3)對照組實驗

對照組實驗用于比對本文算法與其他調度策略在輸入不同復雜度的帶權圖及不同劃分數的情況下的分配效果.比較對象是:1)K-PART:本文算法;2)T-PART:文獻[4]基于Traffic的OnlineScheduler中的劃分算法;3)M-PART:文獻[6]基于Metis的P-Scheduler;

為了方便對比,本文統一重新實現對照組調度器的算法,并且輸入相同格式的Topology圖數據進行實驗.

圖5 迭代倍率對劃分效果的影響

實驗1.流程如下:1)隨機生成10張帶權圖,劃分數k逐漸增加;2)分別使用上述算法進行調度,每個算法都會對每張圖作10次劃分;3)對調度結果進行評估統計,計算每組指標的平均值.實驗中圖都為G(24,36),劃分數k從2增加到24,平衡性調整的迭代次數Mul=0或者Mul=5.實驗結果如圖6所示.

從圖6的實驗結果可以看出,當劃分數從2開始增加到接近總的頂點數時,各個算法的割權比和最大偏差率都會有上升趨勢,權重標準差相對穩定(除了M-PART),這意味著劃分的通信代價優化和均衡度都會變差.在劃分數為頂點數的1/2及以下時,K-PART(Mul=0)的劃分效果都是比較優秀的;K-PART(Mul=5)和T-PART次之,而M-PART也不錯,但其結果非常不穩定.當劃分數比頂點數趨向于1時,K-PART(Mul=5)的割權比也趨向于1.這是因為這里圖劃分算法是按頂點為單位開始劃分的,因此在劃分數比頂點數趨向于1時,由于K-PART平衡性調整策略的作用,使得每個子集僅包含1個元素,因此割權等于總邊權.K-PART(Mul=0)和T-PART以減少割權比優先,因此在達到一定程度時優先保證了割權比;M-PART似乎走了減少割權比的極端,割權比占優的M-PART在均衡度上將會大打折扣,分析發現其產生大量空集.

實驗2.流程如下:1)隨機生成10組固定頂點數,邊數依

圖6 劃分數對劃分效果影響

次增加的帶權圖,每組10張圖;2)分別使用上述算法進行調度劃分,每個算法都會對每張圖作10次劃分;3)對調度結果進行評估統計,計算每組指標的平均值.實驗中帶權圖頂點數固定12,邊數從15開始增加,步進3;每個邊數的小組各10張圖,劃分數k固定為3,平衡性調整的迭代次數Mul=0或者Mul=5.實驗結果如圖7所示.

圖7 圖連接復雜度對劃分效果的影響

由圖7的實驗結果可以看出,圖的連接復雜度并沒有明顯影響算法對劃分結果中的割權比、標準差與最大偏差率指標.同時上述10組實驗中,本文算法K-PART在平衡性調整迭代倍率Mul=0的實驗組的劃分割權比一直是最小的,因此它對通信代價的優化程度在這幾組中是最好的;在平衡性調整迭代倍率Mul=5的實驗組中,劃分的均衡度一直是最優的.

4)實驗結論

①在所對比的試驗中,本文算法的劃分效果優于對比算法;其中Mul>0時,在均衡度上占優,Mul=0則在割權比上占優;②所有對比的算法中,劃分數與頂點數的比值越小,劃分效果越好;③對于本文算法,平衡性調正策略迭代次數越多,分配越趨于均衡;但是會損失一些割權比上的優化.

3.3 動態調度策略

1)調度策略

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

最后在調度生效之前,還需做進一步調整.算法遍歷各節點的Worker,如果在同一個節點存在多個同一Topology的Worker,還可對其Executor執行一次均分.滿足調度必要規則條件時生效這次調度.

調度生效的必要規則如下:在調度之前,調度器根據性能監測數據計算節點間Tuple發送率和均衡度指標;調度器計算新的分配方案之后,利用舊的性能監測數據估算這兩個性能指標,當估算值都優于原指標時,開始實施重調度.算法形式化描述如下:

2)動態并行參數優化

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

本文實現的動態調度器中,對于組件的并行度參數優化策略如下:

①輸入:Executor負載數據,Topology結構t;

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

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

④整合優化:整合組件間并行化參數比,將并行化參數之和等比擴大到Worker進程的線程數推薦值(10～15,該值是Storm開源軟件作者Nathan給出);

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

3)重調度優化

動態調度策略根據當前的性能數據計算出新的分配方案后,面臨一個Worker重新分配部署的問題.重新部署時需要先將相應Worker關閉,在新的節點的相應Slot重新開啟.這是一個相對消耗資源的過程,并且會帶來服務中斷.因此在實施重調度優化的目標是:減少重調度對計算服務的影響,實現平滑的重新分配.

本文提出的重調度優化的基本思想是減少Worker遷移數,在遷移數不能減少的情況下優先移動計算量小的Worker,并且對Worker分批遷移.

具體流程如下:

①輸入:以集群當前分配表Acur與動態調度策略得到的新分配表Anew為輸入;

②待重調度集Sreassign:Acur中的每個Worker遍歷比較Anew中Worker的Task分配,Acur中Worker的Task發生變化的Worker移動到待重調度集Sreassign;

③待重調度集Sreassign:Acur中的Worker按照Node分組,并按照Worker數量對Node分組由大到小排序;每次取出第一組,如果該組中的Worker在Anew中位于同一個Part,則不操作繼續取下一組;否則取出改組中計算量最小的Worker放入Sreassign,直到該組中的Worker都對應到Anew中的同一個Part;

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

4 實驗與分析

4.1 實驗環境

實驗在一個由安裝ESXI6.0系統的Dell R710服務器上的虛擬化集群進行.服務器的基本配置如下:CPU:Intel(R)Xeon(R)X5650,2.67GHz×6 core×2;RAM:128GB;1Gbps×4的網卡以及2個1T硬盤組成的磁盤陣列.

虛擬節點的配置是:每個虛擬節點CPU為2.67GHz×4 core、RAM為4GB,并用1Gbps的網絡連接;操作系統是Ubuntu 14.04 X86_64(Linux 4.2.0).集群布置如表1所示.

表1 Storm節點配置

為了記錄Topology運行時數據,專門設計了一個Topology,該Topology基于Word Count Topology[12].該Topology一共有4個組件,Worker的默認配置數為8,組件的默認設為并行度為4.為方便實驗,本文對其進行了以下改造:1)在該Topology的每個組件初始化方法中增加性能監視器的注冊,每個處理方法中通信Tuple統計;2)為了采集Tuple處理時延和吞吐量,在Spout發送消息時增加發送時間戳字段,并在Storm的可靠性保障中的ACK接口實現中增加時間差計算和消息計數.另外,為保證時間相關的測量數據的準確性,集群所有節點配置了NTP時間同步協議來同步集群時間.

4.2 評價指標

本文用如下指標評價性能:1)Tuple處理時延,即指一個Tuple從Spout發出后,直到處理完全后Spout收到Ack信號所花費的時間,反映集群的響應效率,該指標越小越好；2)單位時間Tuple處理量,即每秒處理的Tuple個數,反映集群的吞吐量,該指標越大越好.

本文用均衡度與節點間Tuple轉發率指標評價調度效果.均衡度是性能采集器采集的各節點的CPU計算量的標準差,節點間Tuple轉發率的值等于通過網絡發送Tuple數量和集群所有Tuple數量之比.這兩個指標相當于圖均衡劃分中的標準差與割權比,調度效果的評價指標越好,越有利于實際性能指標的提升.

4.3 對比實驗

實驗中給出的指標數據由本文實現的性能監視器保存在性能數據庫中的數據整理得到.比較對象是:

1)KPartScheduler:由本文算法實現的動態調度器;

2)OnlineScheduler:文獻[8]基于Traffic的在線實時調度器;

3)EvenScheduler:Storm中自帶的均衡調度器.

1)調度器指標

圖8為集群運行時的節點間CPU計算量的標準差.由圖可知,在當前給定實驗環境下KPartScheduler和OnlineScheduler在均衡度方面相差不大,但是EvenScheduler在均衡度上要明顯差于前兩者.

圖9為集群運行時的節點間Tuple發送率.由圖可知,在當前給定實驗環境下KPartScheduler在通信代價優化上要優于OnlineScheduler,EvenScheduler對通信代價的優化是最差的,分別比KPartScheduler、OnlineScheduler調度器差5、3個百分點.

2)性能指標對比

圖10為集群運行時的Tuple處理時延.由圖可知,在當前給定實驗環境下,KPartScheduler調度器下的集群Tuple處理時延隨著系統運行中的不斷重調度,處理時延越來越小;OnlineScheduler在前期收斂速度快,迅速達到的較優狀態,但是系統最終穩定時,KPartScheduler調度下的Tuple處理時延要低于OnlineScheduler.而EvenScheduler在分配Topology后一直保持相對穩定的運行狀態,且最終在Tuple處理時延性能上被前兩者超越.

圖8 集群節點間計算量標準差

圖9 節點間Tuple發送率

圖10 運行時Tuple處理時延

單位時間Tuple處理量就是集群吞吐量的反映.圖11為集群運行時單位時間Tuple處理量.由Topology開始運行到運行狀態趨于穩定,KPartScheduler和OnlineScheduler下的吞吐量相差不大,到后期KPartScheduler出現一定的優勢.運行前期OnlineScheduler以最快的速度達到較優狀態.

圖11 運行時單位時間消息處理量

5 結 論

本文針對Storm大數據流式框架中自身調度算法以及已有優化方案存在的負載不均、資源利用率不高等問題,提出基于啟發式圖均衡劃分算法的動態調度策略.動態調度器可根據性能數據進行實時動態的調度,并實現并行參數優化和重調度優化.

實驗測試用Topology在本文調度器調度下的運行時均衡度和節點間Tuple發送率的優化效果都比對比算法有小幅度提升,最終隨著調度效果的優化,使得集群的吞吐量比對比調度器提升了近20%以上,而在Tuple處理延時上減少了1～2ms.因此,本文調度器在一定程度上可以提升Storm集群運行的性能.