Storm集群下基于性能感知的負(fù)載均衡策略①

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 性能感知方法

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

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

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

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

算法1.計(jì)算節(jié)點(diǎn)PAV輸入:任務(wù)運(yùn)行時(shí)信息輸出: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)

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

圖2 節(jié)點(diǎn) PAV 計(jì)算流程圖

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

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

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

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

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

表3 實(shí)驗(yàn)環(huán)境配置

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

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

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

圖4 處理時(shí)延對(duì)比

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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