基于數據遷移策略的反壓問題解決方法①

孫一佳, 丁 箐, 徐 云

1(中國科學技術大學 軟件學院, 合肥 230026)

2(安徽省高性能計算重點實驗室, 合肥 230036)

隨著實時計算需求的迅速增長, 對于分布式流計算框架的要求越來越高[1], 如何提高框架的效率已經成為學術界和工業(yè)界的研究熱點. 在流計算框架的應用場景中, 反壓問題[2]是已知的難點之一, 該問題輕則導致數據丟失, 重則導致系統(tǒng)崩潰, 亟需好的解決方法.

目前, 常見的流計算框架(如Flink[3]、Spark Streaming[4]和Storm[5])都有應對反壓問題的解決機制. Storm框架默認的反壓機制是在輸入的Tuple 無法被及時處理時直接丟掉后續(xù)的Tuple, 以此觸發(fā)限流控制, 并向上傳遞以限制數據源的發(fā)送速率, 該機制屬于被動響應, 在處理突發(fā)性大數據流時, 壓力最終集中在數據源處, 數據源的發(fā)送速率降低使得系統(tǒng)延遲增加. Flink框架在舊版本的TCP 滑動窗口機制上提出了Credit 機制, 該機制解決了多個子任務共享TCP 連接時由于單一子任務產生反壓, 阻塞整條TCP 連接的問題, 但該機制在單任務出現反壓問題時仍需將壓力向上游傳遞,限制上游速率, 增加了系統(tǒng)的延遲. Spark Streaming 是基于微批次的流計算框架, 框架內設置了rate 參數來控制數據批次的發(fā)送速率, 通過下游節(jié)點向上游反饋rate 值, 上游根據rate 值動態(tài)調節(jié)數據的發(fā)送速率, 避免產生反壓問題, 但Spark Streaming 由于其微批次的設計, 在實時性上差于Storm 和Flink 框架, 同樣在遇到突發(fā)性大數據流時, 也是通過限制數據源的發(fā)送速率將壓力集中在數據源, 嚴重影響任務處理的實時性.

上述這些機制在處理反壓問題時, 都是快速地向上游和數據源傳遞減速信息, 將壓力向上游傳遞, 限制上游數據的發(fā)送速率, 這也導致了系統(tǒng)的吞吐量降低、延遲增加. 通過研究, 大部分反壓問題是由系統(tǒng)內節(jié)點處理能力差異、鏈路帶寬差異和數據分布不均所導致, 壓力往往集中在局部區(qū)域, 系統(tǒng)內其他區(qū)域的負載壓力很小, 上述機制沒有很好地利用到這些輕載區(qū)域. 本文提出了一種基于數據遷移策略的反壓解決方法, 目的是通過其他輕載節(jié)點分散壓力來解決局部反壓問題, 在維持數據源的高發(fā)送速率前提下降低系統(tǒng)的延遲.

1 相關工作

1.1 調度策略研究現狀

調度策略是分布式系統(tǒng)扮演著重要的角色, 系統(tǒng)的性能很大程度取決于調度策略的合理性. 分布式系統(tǒng)調度算法一直是分布式系統(tǒng)研究領域的一個熱點問題[6].

Lopes 等人[7]從3 個維度出發(fā), 并進一步對每個維度進行細分, 對分布式系統(tǒng)中的調度策略分類討論和描述. Gautam 等人[8]針對Hadoop 分布式系統(tǒng), 從多個角度(任務優(yōu)先級、資源類型、網絡異構性等)對調度策略分類, 詳細地分析了各策略的優(yōu)勢和劣勢. Hammoud等人[9]主要考慮數據局部性的問題, 通過研究網絡對系統(tǒng)和任務的影響, 對MapReduce 中的Reduce 任務調度進行優(yōu)化, 使得數據優(yōu)先在本地處理, 提高了系統(tǒng)性能. Arslan 等人[10]主要考慮文件讀寫代價的問題, 通過研究CPU 負載對任務的影響, 同樣對MapReduce 中Reduce 任務進行了優(yōu)化. 劉夢青等人[11]基于分布式流計算系統(tǒng)Storm 將動態(tài)的計算資源看作信息素, 將資源調度問題轉化為最佳路徑尋找算法并通過蟻群算法求解, 效果優(yōu)于Storm 的默認調度策略. 劉粟等人[12]同樣針對 Storm 系統(tǒng), 主要考慮任務調度中的流計算任務拓撲圖, 通過拓撲中組件并行度進行分配排序, 并將上下游直接連接的子任務部署到相同的計算節(jié)點以減少網絡傳輸次數, 提高系統(tǒng)的處理性能.

1.2 反壓問題研究現狀

在分布式流計算框架中, 流計算過程被抽象成一個有向圖, 有向圖中的節(jié)點(部分框架稱這些節(jié)點為算子)代表對數據的操作, 有向邊代表數據流方向[2]. 在數據流的處理過程中, 當上游數據流的輸入速率比向下游發(fā)送數據流速率快時, 某個算子或多個算子所處的節(jié)點將無法及時地將數據發(fā)送出去, 此時數據積壓在緩沖區(qū)并逐漸耗盡緩沖區(qū)資源, 該數據層面上的壓力將會逐層向數據源方向傳遞, 這種與數據流方向相反的數據壓力稱為反壓(backpressure, BP).

反壓問題存在于許多常見的場景, 如節(jié)假日搶購火車票、購物網站的促銷活動、熱點新聞的發(fā)布等,反壓所帶來的問題是非常嚴重的, 其耗盡緩沖區(qū)資源,輕則丟失數據, 重則系統(tǒng)崩潰. 反壓問題的原因可分為3 大類: 第1 種是流量峰值, 數據量在短暫的時間內達到峰值, 此時數據源流入的數據量高于框架承受能力造成系統(tǒng)級反壓; 第2 種是數據分布不均勻, 由于輸入數據的分布不均勻, 經由Map 操作和Shuffle 操作, 導致下游不同算子計算任務負載不均衡, 此時將造成局部反壓; 第3 種是計算的拓撲結構, 當某個算子是分支結構或者出現性能問題, 該算子不能及時地向下游輸出數據流, 流入數據量保持不變, 導致數據堆積在算子的緩沖區(qū), 此時將造成該算子的反壓.

目前, 針對反壓問題的解決方法并不豐富, 都依托了具體的框架中進行部署測試. 針對Strom 框架, 熊安萍等人[2]提出一種能夠靈活調節(jié)Topology中各環(huán)節(jié)數據負載的反壓機制, 該機制采用可變隊列, 并根據當前Tuple 負載動態(tài)地調整隊列大小, 該反壓機制可以避免反壓過程中的數據流震蕩、提高性能和穩(wěn)定性. 針對Flink 框架, Hanif 等人[13]提出了一種反壓機制, 該機制使用閾值檢查反壓位置并通過動態(tài)調度緩解反壓. 針對 Spark 框架, Chen 等人[14]提出了Governor 控制機制, 該機制增加了將檢查點成本考慮到反壓機制中的控制器, 從而減少了由于檢查點的干擾而造成的吞吐量損失.

本文旨在解決數據分布不均勻導致的局部反壓問題, 分布式系統(tǒng)目前大多采用MapReduce 方法, 在這個過程中, 相同的數據將交由同一算子節(jié)點進行處理,當輸入數據分布不均勻時, 下游的處理節(jié)點將要處理的數據量也是有很大差異的. 由此, 整個系統(tǒng)處理任務的耗時取決于處理時間最長的支路, 而其他支路將會處在資源空閑的狀態(tài), 這樣, 整個系統(tǒng)的資源利用率并沒有達到理想的狀態(tài). 為了讓系統(tǒng)達到理想的狀態(tài), 可以采取靜態(tài)分配的方法, 通過預處理得到不同節(jié)點的計算能力、緩沖能力、網絡帶寬以及數據的分布規(guī)律帶入模型, 得到不同節(jié)點的數據處理能力, 手動將占比大的數據分配給處理能力較強的節(jié)點, 這樣能更大限度地發(fā)揮系統(tǒng)的利用率. 但是靜態(tài)方法依然存在弊端,比如無法獲知下游節(jié)點的處理能力和無法獲知數據的分布情況等, 為了彌補靜態(tài)方法的不足, 本文提出了一種基于數據遷移的方法, 動態(tài)地解決了局部反壓問題.

2 方法設計

本文的算法設計如圖1 所示, 首先確定系統(tǒng)是否存在反壓節(jié)點, 然后鎖定反壓節(jié)點所在的網絡拓撲支路, 通過數據遷移策略算法找到輕載支路, 并將重載支路要處理的數據遷移到該輕載支路處理, 分散重載支路的壓力, 在反壓問題解決后, 將系統(tǒng)恢復成原有的調度策略繼續(xù)運行.

圖1 數據遷移調度方法概述

本文算法的關注點有二: 第一點是如何判斷反壓節(jié)點和鎖定重載支路之后如何對其他支路進行打分并排序得到壓力最小的輕載支路, 第二點是如何將重載支路的數據遷移輕載支路, 同時數據遷移后, 要保證整個任務的計算結果準確. 算法的具體步驟如算法1.

算法1. 數據遷移策略算法步驟1. 確定分布式流計算任務, 定義此次任務的網絡拓撲信息和每個節(jié)點的資源信息, 分配每個節(jié)點的任務, 生成模擬數據, 設定壓力閾值, 運行任務.步驟2. 持續(xù)監(jiān)測系統(tǒng), 對每個節(jié)點的內存狀態(tài)和輸入輸出速率進行監(jiān)測, 檢測是否存在節(jié)點的壓力超過預設反壓閾值, 如有則存在反壓節(jié)點.

步驟3. 如存在反壓節(jié)點, 向上游追溯支路, 直至到達分支節(jié)點, 將該支路定義為重載支路, 并將反壓節(jié)點記錄到反壓列表中; 然后, 統(tǒng)計各條支路備將的壓力情況進行打分排序, 將壓力最小的支路作為輕載支路, 準 送往重載支路的數據遷移到輕載支路.步驟4. 使用數據遷移策略的計算方法, 數據遷移過程中, 記錄遷移數據段在源數據中的偏移位置和長度, 并在輸出節(jié)點進行統(tǒng)計計算,以保證任務結果的準確和一致.步驟5. 每間隔一段時間檢測反壓列表中各節(jié)點的壓力情況, 如存在節(jié)點壓力低于預設恢復閾值, 則停止數據遷移策略, 并恢復默認的數據調度策略; 如重載支路未緩解, 數據遷移策略繼續(xù)運行, 并返回步驟2, 繼續(xù)監(jiān)測系統(tǒng).步驟6. 恢復默認策略, 返回步驟2, 繼續(xù)監(jiān)測系統(tǒng).

2.1 反壓節(jié)點的識別和支路的打分機制

反壓節(jié)點的識別參考了Cicotti 等人[15]的研究工作,節(jié)點是否能處理施加任務或數據的4 個指標是: CPU,內存, I/O 和網絡帶寬. 相比于王成章等人[16]的工作,本文方法比較全面考慮了影響反壓問題的可能因素(內存、CPU 性能、I/O 速度和網絡帶寬), 并用簡潔的公式進行量化. 由于本實驗是在模擬環(huán)境NS-3 網絡仿真器下運行, 本實驗使用定長異步隊列模擬了CPU 和內存的效果, 通過對每個節(jié)點中隊列的使用率以及輸入輸出的速率差異時別節(jié)點的壓力情況. 當隊列的使用率超過80%, 且該節(jié)點上游數據的輸入速率高于向下游發(fā)送的輸出速率時, 將該節(jié)點定義為反壓節(jié)點, 并將該節(jié)點所在支路定義為重載支路.

對各支路進行打分的目的是快速計算出各個支路的資源使用情況, 再據此做出調度策略. 因此本實驗考慮3 個如下指標:

這3 個指標可以綜合地代表CPU 性能、內存使用率、I/O 性能和網絡帶寬4 種指標的效果. 式(1)是將該支路各節(jié)點的隊列使用率的最大值作為支路隊列使用率的代表; 式(2)是通過支路輸入數據總量減去支路輸出數據總量再除以間隔時間作為支路I/O 速率差異的代表; 式(3)則是將該支路各連接的網絡帶寬最小值作為支路網絡帶寬的代表, 主要關注鏈路中的瓶頸.

2.2 數據遷移策略的結果準確性

數據遷移策略依賴于分布式系統(tǒng)的MapReduce框架, 基于MapReduce 框架的分布式系統(tǒng)在處理任務時, 會將一個任務拆分成多個關聯(lián)的子任務進行處理,并抽象出有向圖的拓撲結構. 如圖2 所示, 通過定義Map、Shufflue 和Reduce 等操作, 將一個WordCount任務拆分, 子任務通過并行處理改善效率. 在拓撲圖中,通過子任務劃分層次關系, 同層處理相同的子任務, 上游子任務的輸出傳遞給下游子任務作為輸入, 最終完成整個任務. 在實際計算機節(jié)點中, 單個子任務可能占據一個計算機節(jié)點, 也可能多個子任務占據一個計算機節(jié)點, 并通過系統(tǒng)的進程和線程機制區(qū)分子任務后計算.

圖2 WordCount 任務拓撲圖

在實際應用中, 由于分布式系統(tǒng)中節(jié)點性能差異和輸入數據分布差異會導致部分節(jié)點的數據負載過重,數據遷移策略是將重載節(jié)點要處理的數據發(fā)送給輕載節(jié)點, 以此緩解重載節(jié)點的負載壓力, 同時在遷移數據過程中要考慮子任務的類型以保證遷移后計算結果的正確性. 相比于文獻[17-20]提出的方法, 本文方法主要是解決反壓問題, 一般情況下不改變系統(tǒng)中的節(jié)點并行度和拓撲結構, 在我們的設計和實現中遷移操作的粒度更細, 開銷更小. 已有的其他相關工作主要是針對整個系統(tǒng)進行負載均衡, 需要改變節(jié)點并行度甚至系統(tǒng)拓撲結構, 因此兩類方法有不一樣的前提要求.

在不同類型的操作中, 通常Reduce 操作是計算子任務中影響最大的操作, 也是計算耗時最長的操作. 數據遷移策略的針對點是Reduce 操作的類型, Reduce 操作類型是根據任務定義的, 如累積加和、取平均值、取極值、統(tǒng)計特定量、去重等. 不同的類型具有不同的特性, 其中結合律特性決定了其計算操作(如加法、減法、乘法、矩陣乘法等操作元)處理的次序是否影響最終結果, 交換律特性決定了其數據計算的次序是否影響最終結果. 對于數據遷移策略, 由于數據將會出現分段分節(jié)點處理, 算子和數據的計算次序都將會被打亂, 為了使計算結果準確無誤, Reduce 操作的類型通常需要同時滿足結合律和交換律.

對于累積加和、取極值等同時滿足結合律和交換律的計算方法, 無需特別處理, 直接應用遷移調度策略即可; 但是對于取平均值、統(tǒng)計特定量、去重等計算方法, 它們并不直接滿足結合律和交換律, 此時需要記錄額外信息使得計算結果準確無誤. 以取平均值為例,見式(5).

由此, 通過對不同計算方法的分析, 記錄額外的數據信息, 如偏移量、長度等等, 通過在輸出節(jié)點的額外處理, 即可使得不滿足結合律和交換律的計算方法, 經過數據遷移策略的計算后仍然保證計算結果的準確性.

3 實驗結果與分析

3.1 實驗環(huán)境與配置

本文實驗為模擬仿真實驗, 實驗所用的環(huán)境是NS-3 網絡仿真器[21]. NS-3 仿真器具有良好的體系結構, 易于搭建網絡中各種實體模型, 同時其自帶的Callback 機制以及Tracing 機制可以將網絡行為清晰地展示出來, 便于使用者進行研究分析.

本文實驗首先建立了網絡拓撲, 如圖3, 網絡中共有5 個節(jié)點, 6 條信道, 不同信道的帶寬和延遲都有所不同. 由于NS-3 不支持CPU 和內存的模擬, 本實驗采用了異步定長隊列作為二者的模擬.

圖3 模擬網絡拓撲圖

如圖4 所示, 每個節(jié)點都維護一個私有的隊列, 網絡中傳輸進來的數據先由生產者線程壓入隊列, 然后再由一個消費者線程取出隊列頭的元素進行處理并向下游發(fā)送. 當數據充滿定長隊列時, 節(jié)點向上游發(fā)送停止信號, 避免后續(xù)數據的丟失; 當隊列占有量下降到50%再向上游反饋恢復信號.

圖4 網絡節(jié)點結構圖

在NS-3 仿真平臺上實現了Flink 框架的Credit 反壓機制, 并以此作為實驗參照. 如圖5, 每隔一段時間,下游的節(jié)點向上游節(jié)點反饋其定長隊列所剩余的數據空間大小, 上游節(jié)點根據反饋回來的credit 值判斷是否繼續(xù)傳輸數據.

圖5 Credit 機制

實驗采用流量統(tǒng)計作為測試用例, 流量統(tǒng)計與常見的詞統(tǒng)計類似, 其中數據流是以數據包的形式向下游發(fā)出, 每個數據包大小為1 MB 并擁有一個標識符用來指明它將被3 個支路中哪一路進行處理, 數據源節(jié)點根據該標識符進行指定分發(fā). 在常見的反壓場景中, 輸入數據通常具備兩個特點: 突發(fā)性和不均勻性. 其中突發(fā)性是指在流量速率會突然地增加或減少, 不均勻性是指具有相同標識符的數據堆積不利于并行處理. 本實驗的源數據通過控制發(fā)送速率來滿足突發(fā)性, 通過控制數據包的分布來滿足不均勻性. 以1 GB 的流量總值為例, 圖6展示源數據在處理時各節(jié)點負載分布情況, 其中每個區(qū)域展示了隨時間變化各節(jié)點的負載變化情況. 從負載分布中可以看出, 節(jié)點接收的數據會在某段時間內突發(fā)性的增加和減少, 并且數據的分布不均導致了不同節(jié)點在相同時間段接收到的數據量差異很大, 這將使系統(tǒng)產生反壓問題. 需要注意的是, 該負載分布模型是在不受限的網絡拓撲中生成的, 是理想的不產生反壓問題的情況下各節(jié)點的負載情況, 但實際上數據發(fā)送會在收到下游節(jié)點反饋的停止信號時停止, 直到接收到恢復信號再繼續(xù)模擬生成, 負載也會據此變化.

圖6 各節(jié)點負載分布

最后本實驗的測試實例共有4 個, 流量總值分別是500 MB、1 GB、2 GB 和5 GB. 實驗結果以兩個指標作為對比參考, 其一為延遲時間, 其二為完成通量占比.延遲時間是整個任務從開始到結束的整體時間比較,可以從整體上比較數據遷移策略的性能; 完成通量占比是當前處理的數據量占總數據量的比例, 它可以清晰地看出隨著時間變化系統(tǒng)處理的性能差異以及吞吐量的變化趨勢, 展示出反壓問題出現時系統(tǒng)的反應速率.

3.2 實驗結果與分析

實驗首先對壓力評分公式中的 α 和 β參數進行了范圍測試. 表1 展示了數據量為5 GB 時, α 和 β參數選擇不同的值時, 系統(tǒng)的延遲時間對比, 通過實驗可以看出在 α =0.3 , β =0.5的情況下延遲改善效果最好. 這個結果表明在本實驗的情況下, 網絡帶寬的重要性比其他兩項較小, 支路的 I/O 速度差異重要性更大. 如果在其他環(huán)境下, 可能需要根據計算任務的不同或網絡拓撲的具體情況對α和β的值進行測試調整. 下文的實驗結果均在α =0.3 , β=0.5的情況下完成.

表1 延遲時間對比表(s)

表2 展示了本文方法和Credit 機制對在4 個不同負載下的延遲時間對比. 當總體流量較小時, 整體處理時間較短, 數據遷移策略的啟動和恢復都需要時間, 此時本文方法與Credit 機制在延遲上相差不大; 當總體流量繼續(xù)增大時, 本文方法的效果逐漸明顯并產生了穩(wěn)定影響, 平均能將延遲時間提高15%左右.

表2 延遲時間對比表(s)

通過累積統(tǒng)計每5 s 內系統(tǒng)的流量輸出與流量總值的對比, 得到完成通量占比變化. 圖7、圖8 分別展示了在1 GB 流量和5 GB 流量下Credit 機制和本文方法在不同時間段的完成通量占比變化情況, 其中折線的斜率變化代表了系統(tǒng)的吞吐量變化. 在吞吐量的角度上看, 當反壓問題剛出現時, 兩種方法都出現了斜率趨于平緩即吞吐量下降的情況, 但是本文方法更快速地分散壓力, 使得吞吐量增加, 折線更快地拉升, 表明本文方法在出現反壓問題時能更快地處理壓力. 在完成通量占比的角度上看, 隨著時間變化, 本文方法的完成通量占比始終高于Credit 機制, 更早地達到100%完成, 這表明本文方法降低了反壓問題產生的延遲, 提高了系統(tǒng)性能.

圖7 流量為1 GB 時完成通量占比

圖8 流量為5 GB 時完成通量占比

4 結論與展望

本文對分布式流計算系統(tǒng)中存在的反壓問題進行分析, 基于系統(tǒng)中輕載節(jié)點分散重載節(jié)點壓力的思路,提出了一種基于數據遷移策略的反壓問題解決方法.實驗結果表明, 本文提出的方法可以有效地降低系統(tǒng)的延遲并提高系統(tǒng)性能, 更高效地解決了系統(tǒng)中的反壓問題. 下一步的工作重點是對帶有Map 和Reduce操作的任務以及多任務系統(tǒng)進行優(yōu)化, 并將方法實現在實際的分布式流計算框架中進行驗證.