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

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

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

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

實時流計算系統及負載均衡、調度技術的研究向來是大數據處理領域不可回避的研究熱點.面對企業生產對流式數據實時處理快速增長的需求,如何根據運行時環境動態調度流算子任務,滿足低處理時延并最有效利用計算資源具有巨大的研究價值.

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

1 Storm現有調度機制在負載均衡問題分析

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

在Storm集群中,用戶提交的作業是一個topology,其表現為有向無環圖,會被調度器進行任務的劃分.Storm默認調度策略采用sort-slot將任務(Task)輪流分配給節點,如圖1所示.

圖1 Storm 默認任務調度示意圖

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

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

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

(3)Storm默認的調度機制未充分考慮節點負載情況,計算容器的固定配置使其不能根據數據輸入率實現有效的負載均衡.

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

2 基于性能感知的負載均衡策略

本文提出了一種基于性能感知的負載均衡策略.該策略可及時感知節點負載波動,并可根據節點負載能力分配任務,在充分利用系統的資源同時,達到負載均衡的目的.

2.1 算法改進分析及思想

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

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

2.2 性能感知方法

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

表1 負載與 PAV 的對比

基于上述發現,本文將r(t)/τ(t)的值稱為性能感知值(PAV).PAV與任務在某段時間內的輸入率成正比,與相應時間段內的節點平均處理延遲成反比.

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

算法1.計算節點PAV輸入:任務運行時信息輸出: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)

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

圖2 節點 PAV 計算流程圖

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

2.3 基于PAV的負載均衡算法實現

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

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

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

表3 實驗環境配置

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

3.1 不同數據輸入率下平均處理時延

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

圖4 處理時延對比

3.2 系統吞吐量測試

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

圖5 系統吞吐量比較

3.3 固定數據輸入率下CPU負載均衡性測試

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

圖6 集群節點 CPU 負載分布

3.4 動態數據流下CPU資源利用率測試

為了能夠滿足在真實的生產環境下系統隨著數據到達率的變化而處理數據,實驗四在實驗三的基礎上,通過Python數據發生器作為數據源產生數據流,且到達的時間遵循泊松分布.公式如下:

測試數據泊松分布參數λ從1000開始,分別增至2000、3000,統計不同性能節點的CPU資源使用率.

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

表4 動態數據流下集群CPU資源平均利用率(%)

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

4 結束語

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