馮馨銳,謝 彬,唐 鵬,秦 健

(中國電子科技集團(tuán)公司第三十二研究所 信息服務(wù)平臺室,上海 201808)

隨著互聯(lián)網(wǎng)和大數(shù)據(jù)技術(shù)的快速發(fā)展,全球的數(shù)據(jù)正在以驚人的速度增長,因此數(shù)據(jù)的高時效性,可操作性需求已經(jīng)成為研究熱點[1].Storm作為Twitter開源的分布式實時流計算系統(tǒng),具有編程接口簡單[2],可拓展性良好和容錯機制可靠[3]的優(yōu)點,因此在實時推薦,金融分析和在線機器學(xué)習(xí)[4]等方面發(fā)揮著重要作用.

實時流計算系統(tǒng)及負(fù)載均衡、調(diào)度技術(shù)的研究向來是大數(shù)據(jù)處理領(lǐng)域不可回避的研究熱點.面對企業(yè)生產(chǎn)對流式數(shù)據(jù)實時處理快速增長的需求,如何根據(jù)運行時環(huán)境動態(tài)調(diào)度流算子任務(wù),滿足低處理時延并最有效利用計算資源具有巨大的研究價值.

本文闡述了Storm自帶的調(diào)度器調(diào)度策略,并對其現(xiàn)存的負(fù)載均衡問題進(jìn)行了分析.同時,本文針對流處理系統(tǒng)數(shù)據(jù)輸入率和數(shù)據(jù)處理延遲等不足,以集群的視角提出了一種基于性能感知的負(fù)載均衡策略并對其算法進(jìn)行了實驗驗證.結(jié)果表明,該算法能夠有效的提高集群資源的利用率,進(jìn)而達(dá)到動態(tài)的負(fù)載均衡.

1 Storm現(xiàn)有調(diào)度機制在負(fù)載均衡問題分析

Storm通常應(yīng)用在計算密集型場景中,負(fù)載均衡技術(shù)則是保證實時計算高性能和高吞吐量的有效手段,而任務(wù)調(diào)度策略又會直接影響負(fù)載均衡的性能.

在Storm集群中,用戶提交的作業(yè)是一個topology,其表現(xiàn)為有向無環(huán)圖,會被調(diào)度器進(jìn)行任務(wù)的劃分.Storm默認(rèn)調(diào)度策略采用sort-slot將任務(wù)(Task)輪流分配給節(jié)點,如圖1所示.

圖1 Storm 默認(rèn)任務(wù)調(diào)度示意圖

每次新提交的topology均會從第一個節(jié)點開始分配所劃分的任務(wù).但因每個topology的業(yè)務(wù)邏輯不同,其任務(wù)劃分?jǐn)?shù)量也是不定的.如果僅根據(jù)節(jié)點剩余slot數(shù)量進(jìn)行簡單負(fù)載均衡會存在以下三點問題:

(1)這種sort-slots會導(dǎo)致整個集群資源分配不均衡,排序靠前的supervisor分配出去的 slot數(shù)量多,而后面某些很少.

(2)在集群中添加、刪除節(jié)點或worker進(jìn)程后,集群的計算資源會發(fā)生變化,現(xiàn)有調(diào)度策略無法根據(jù)改變后的可用資源做出有效的調(diào)整策略.

(3)Storm默認(rèn)的調(diào)度機制未充分考慮節(jié)點負(fù)載情況,計算容器的固定配置使其不能根據(jù)數(shù)據(jù)輸入率實現(xiàn)有效的負(fù)載均衡.

針對Storm默認(rèn)調(diào)度算法進(jìn)行改進(jìn)的相關(guān)研究吸引了越來越多研究者的關(guān)注.Ding[5]等采用了改變worker內(nèi)部并行度方式應(yīng)對負(fù)載的波動,Navalho[6]等提出了依據(jù)數(shù)據(jù)輸入率動態(tài)變化調(diào)整worker等方法.這些技術(shù)仍然是基于計算資源分配量固定的情況下進(jìn)行的改進(jìn),并未考慮worker本身的資源需求和分配不匹配的問題,不一定適用于Storm集群運行時環(huán)境.Xiong[7]等以Task之間的Tuple傳輸速率作為判定條件,提出熱邊調(diào)度算法,將高頻熱邊關(guān)聯(lián)的Task作為整體來調(diào)度,以最大程度減輕節(jié)點之間通過網(wǎng)絡(luò)傳輸Tuple的數(shù)量.這種算法能夠在降低通信量和負(fù)載均衡之間有一個很好的權(quán)衡.然而在真實的生產(chǎn)環(huán)境中,往往是高速的局域網(wǎng)連接的計算機集群,并不會將帶寬視為一種限制資源.此外,Zhang[8]等采用權(quán)值分配策略為每個slot定義并且計算優(yōu)先級,優(yōu)化了Slot排序的問題,實現(xiàn)了節(jié)點之間的負(fù)載均衡.但是該策略并未考慮負(fù)載波動對計算資源的影響以及集群中不同節(jié)點之間的性能差異,只適合應(yīng)用于某些需要區(qū)分任務(wù)緊急度的領(lǐng)域中.

2 基于性能感知的負(fù)載均衡策略

本文提出了一種基于性能感知的負(fù)載均衡策略.該策略可及時感知節(jié)點負(fù)載波動,并可根據(jù)節(jié)點負(fù)載能力分配任務(wù),在充分利用系統(tǒng)的資源同時,達(dá)到負(fù)載均衡的目的.

2.1 算法改進(jìn)分析及思想

在storm集群中,一個topology的任務(wù)是分布到多個節(jié)點上執(zhí)行的,且負(fù)載會隨著數(shù)據(jù)輸入率的波動而波動.因各個節(jié)點的資源可用性和數(shù)據(jù)輸入率存在一定的差異[9],會導(dǎo)致任務(wù)的處理速度不一.其實,對于一個流應(yīng)用來說,計算資源供給的不穩(wěn)定性,數(shù)據(jù)輸入率不確定性等情況,終將反應(yīng)到節(jié)點對于任務(wù)的處理性能上[10].如果將數(shù)據(jù)輸入率,平均處理延遲等參數(shù)結(jié)合應(yīng)用在改進(jìn)的算法中,能夠更好地反映節(jié)點的具體負(fù)載情況,以此為依據(jù)來評估節(jié)點的處理能力,量化的重新分配任務(wù),則可以達(dá)到改進(jìn)負(fù)載均衡的目的.

算法思想如下:首先對Storm的監(jiān)控模塊進(jìn)行重用,使其可以采集任務(wù)部署后的運行信息.接著工作節(jié)點(supervisor)每隔一個周期向監(jiān)控模塊發(fā)送一個信息采集請求,監(jiān)控模塊會及時反饋當(dāng)前拓?fù)渲懈鱾€任務(wù)的流輸入率和平均處理時延.任務(wù)調(diào)度器會根據(jù)每個節(jié)點采集的信息來定義該節(jié)點的優(yōu)先級,以達(dá)到及時的性能感知.最后,調(diào)度器以集群的視角將任務(wù)的計算量與節(jié)點處理能力相匹配,產(chǎn)生新的任務(wù)映射方案,達(dá)到負(fù)載均衡的目的.

2.2 性能感知方法

在過去的研究中,系統(tǒng)負(fù)載的評價標(biāo)準(zhǔn)一般是CPU利用率,但是對于一個任務(wù)來說,該任務(wù)的CPU利用率僅僅表示了其占用了節(jié)點計算時間的比重,并不能體現(xiàn)節(jié)點的處理性能[11].如表一 所示,兩個負(fù)載相同的任務(wù),一個任務(wù)輸入率為 1000 tuples/s,在平均處理延遲為2 ms的node1上執(zhí)行,另一個任務(wù)輸入率為2000 tuples/s,在平均處理延遲為 1 ms的 node2 上執(zhí)行.雖然兩個任務(wù)的負(fù)載相同,但其所對應(yīng)的節(jié)點處理數(shù)據(jù)效率是明顯不同的.

表1 負(fù)載與 PAV 的對比

基于上述發(fā)現(xiàn),本文將r(t)/τ(t)的值稱為性能感知值(PAV).PAV與任務(wù)在某段時間內(nèi)的輸入率成正比,與相應(yīng)時間段內(nèi)的節(jié)點平均處理延遲成反比.

性能的計算首先要獲取監(jiān)控拓?fù)淙蝿?wù)的運行數(shù)據(jù),這個方法通過監(jiān)控模塊來完成.為了避免監(jiān)控的偶然因素,調(diào)度器將采用最近連續(xù)三次監(jiān)控的平均值.單個節(jié)點的PAV可以是其上各任務(wù)的PAV之和,也可是節(jié)點總數(shù)據(jù)輸入率和與平均處理延遲的商.本文從集群的視角來考慮,采用后者來計算,并對結(jié)果降序排列,為之后的負(fù)載均衡做準(zhǔn)備.具體的PAV計算方法如下,流程圖如圖2所示.

算法1.計算節(jié)點PAV輸入:任務(wù)運行時信息輸出:PAV_node[N]Step1:receive task runtime information Step2:FOR node belongs to cluster DO get the total rate:sum all task rate on node get the average latency END FOR Step3:PAV_ node[i] total rate/average latency Step4:Sort_down(PAV_node)

合理配置采樣周期對于調(diào)度性能的提高具有重要意義.如果采樣周期過短,集群信息的采集會帶來很大開銷,對任務(wù)實時性會有一定的影響,而如果周期過長,對于波動較大的數(shù)據(jù)流,會影響其性能感知準(zhǔn)確性.根據(jù)以往經(jīng)驗,數(shù)據(jù)平均到達(dá)率為3000 tuples/s且服從泊松概率分布時,采樣周期設(shè)置在 10 s～15 s 為佳[12].本文實驗環(huán)境設(shè)置的采樣周期為10 s.

圖2 節(jié)點 PAV 計算流程圖

我們可以根據(jù)PAV來評估一個節(jié)點當(dāng)前的處理性能,PAV高的節(jié)點應(yīng)該被分配更多任務(wù).一般而言,每個節(jié)點的計算資源是固定的,隨著提交任務(wù)的增多,節(jié)點處理性能會變差,即PAV會降低,此時需將某些任務(wù)提交給PAV高的節(jié)點去處理,可減小性能差節(jié)點的計算量.

2.3 基于PAV的負(fù)載均衡算法實現(xiàn)

結(jié)對交換算法是解決負(fù)載均衡的常用算法,如圖3所示,其基本思路是將N個節(jié)點分為N/2組,負(fù)載最小的節(jié)點與負(fù)載最大的在一組,負(fù)載次小的與負(fù)載次大的在一組,依此類推,若還剩中間節(jié)點,則忽略處理.在組內(nèi)通過任務(wù)的遷移,來減少節(jié)點之間的負(fù)載不平衡.

結(jié)對交換算法對性能有差異的節(jié)點任務(wù)交換,在一定程度上緩解了性能差節(jié)點上的處理壓力,但是不能以集群視角來分配任務(wù),且對有些情形不起作用.因此,本文以結(jié)對交換算法為啟發(fā)式優(yōu)化算法,提出了基于PAV的負(fù)載均衡算法.

負(fù)載均衡問題本質(zhì)上是一個NP完全問題[13],到目前為止還沒有完全有效的解法.對于這類問題,用貪心選擇策略有時候會設(shè)計出一個比較好的近似算法.本

表3 實驗環(huán)境配置

實驗的目的在于對性能感知的改進(jìn)方法做相關(guān)性測試,并且以典型的大數(shù)據(jù)應(yīng)用WordCount進(jìn)行了4組實驗.4組實驗分別針對Storm優(yōu)化的處理時延測試、系統(tǒng)吞吐量測試、固定數(shù)據(jù)輸入率下CPU負(fù)載均衡性測試以及滿足泊松概率分布的動態(tài)數(shù)據(jù)流下CPU資源利用率測試.

3.1 不同數(shù)據(jù)輸入率下平均處理時延

流處理系統(tǒng)最主要的是保證應(yīng)用的低處理時延,處理時延是衡量一個調(diào)度系統(tǒng)是否有效的重要指標(biāo).實驗一包括了4組對比實驗,分別以1000條/s、2000條/s、3000條/s、4000條/s的速率向Redis中寫入數(shù)據(jù),然后Spout從其中讀取數(shù)據(jù).圖4表示的是默認(rèn)調(diào)度和本文調(diào)度在對應(yīng)數(shù)據(jù)輸入率下的平均處理時延的比較.由實驗結(jié)果可知,默認(rèn)調(diào)度算法的處理時延會隨著發(fā)送端數(shù)據(jù)量的累積而增大,當(dāng)速率達(dá)到4000條/s時,時延增長約40%,而基于性能感知的調(diào)度算法可及時感知任務(wù)的計算量,并將其分配到性能最優(yōu)的節(jié)點上,因此整體平均時延并不會有顯著增大.

圖4 處理時延對比

3.2 系統(tǒng)吞吐量測試

實驗二通過改變topology中的task數(shù)量,對系統(tǒng)吞吐量進(jìn)行測試.從圖5可以看出,在task數(shù)量小于6時,默認(rèn)的算法效率略高于改進(jìn)算法,這主要是由于task數(shù)量較少時,集群負(fù)載很低,而默認(rèn)算法的實現(xiàn)較為簡單,因此性能好于改進(jìn)算法.隨著task數(shù)量的增加,改進(jìn)算法優(yōu)勢就體現(xiàn)出來了.這是因為基于PAV的調(diào)度能有效感知集群中每個節(jié)點的負(fù)載情況,將任務(wù)和節(jié)點處理能力相匹配,從而避免個別節(jié)點的過載.隨著task數(shù)量的繼續(xù)增加而超過10個時,兩種算法的吞吐量均出現(xiàn)了不同程度的下降.這是由于這些task通信所需的頻繁的序列化與反序列化操作及task所對應(yīng)的executor間的切換,均會消耗很多的計算資源,最終導(dǎo)致吞吐量下降.

圖5 系統(tǒng)吞吐量比較

3.3 固定數(shù)據(jù)輸入率下CPU負(fù)載均衡性測試

實驗三采集了在固定數(shù)據(jù)輸入率(2000條/s)下流處理過程中集群CPU資源在異構(gòu)節(jié)點上的負(fù)載分布,進(jìn)而考察基于性能感知負(fù)載均衡策略效果.如圖6所示,當(dāng)系統(tǒng)穩(wěn)定后,計算能力較好的節(jié)點(Slave2和Slave3)因其使用基于PAV的負(fù)載均衡調(diào)度,CPU使用率相較默認(rèn)調(diào)度有了顯著上升,而Slave5由于計算能力略低,調(diào)度器在感知性能后會將其上任務(wù)根據(jù)結(jié)對交換算法進(jìn)行遷移,因此與默認(rèn)調(diào)度策略相比,其CPU使用率會有顯著下降,約50%左右.

圖6 集群節(jié)點 CPU 負(fù)載分布

3.4 動態(tài)數(shù)據(jù)流下CPU資源利用率測試

為了能夠滿足在真實的生產(chǎn)環(huán)境下系統(tǒng)隨著數(shù)據(jù)到達(dá)率的變化而處理數(shù)據(jù),實驗四在實驗三的基礎(chǔ)上,通過Python數(shù)據(jù)發(fā)生器作為數(shù)據(jù)源產(chǎn)生數(shù)據(jù)流,且到達(dá)的時間遵循泊松分布.公式如下:

測試數(shù)據(jù)泊松分布參數(shù)λ從1000開始,分別增至2000、3000,統(tǒng)計不同性能節(jié)點的CPU資源使用率.

表4給出了各節(jié)點在λ參數(shù)遞增的動態(tài)數(shù)據(jù)流下,CPU資源平均利用率在默認(rèn)調(diào)度和基于性能感知的負(fù)載均衡調(diào)度下的對比.重點考察Slave2和Slave5.隨著λ的增大,性能較好的Slave2其PAV調(diào)度CPU利用率相較默認(rèn)調(diào)度會有顯著增加,當(dāng)λ=4000時,兩者相差近20%,而Slave5性能較差(見表3),其PAV會隨著λ增加而下降,依據(jù)本文貪心調(diào)度策略,上面的任務(wù)會被調(diào)度到別的節(jié)點.所以盡管輸入率動態(tài)增加,CPU資源利用率反而有所下降.這是改進(jìn)算法對節(jié)點性能感知后動態(tài)遷移任務(wù)的結(jié)果,進(jìn)一步體現(xiàn)了真實環(huán)境下動態(tài)的負(fù)載均衡.

表4 動態(tài)數(shù)據(jù)流下集群CPU資源平均利用率(%)

綜合以上4組實驗結(jié)果可以看出,通過對時延和流輸入率的感知,結(jié)合負(fù)載均衡遷移機制,使任務(wù)可以在集群間依據(jù)處理的需要調(diào)度到適合的節(jié)點,是提高Storm集群資源利用率和處理效率的有效途徑.

4 結(jié)束語

本文基于Storm實時流處理調(diào)度機制,針對默認(rèn)調(diào)度策略資源分配不均衡和無法動態(tài)感知數(shù)據(jù)的輸入率等問題,提出了基于性能感知的負(fù)載均衡策略.通過實驗驗證,結(jié)果表明基于性能感知的負(fù)載均衡策略可有效促進(jìn)Storm集群負(fù)載均衡,提高吞吐量,并降低處理時延.本文的局限性在于,對于性能感知的調(diào)度策略方面未考慮設(shè)置閾值和動態(tài)調(diào)整閾值以達(dá)到更好的調(diào)度性能,這也是下一步的研究方向.