Flink 環境下基于負載預測的彈性資源調度策略

李梓楊 ，于炯，王躍飛，卞琛，蒲勇霖，張譯天，劉宇

（1.新疆大學軟件學院，新疆 烏魯木齊 830008；2.新疆大學信息科學與工程學院，新疆 烏魯木齊 830046；3.成都大學計算機學院，四川 成都 610106；4.廣東金融學院互聯網金融與信息工程學院，廣東 廣州 510521）

1 引言

隨著信息化時代與互聯網的高速發展，智能家居、智能醫療、智能工業、智能汽車等物聯網[1]場景下產生的數據量日益增多，并與互聯網共同成為各行各業大數據的主要來源。希捷（Seagate）公司與互聯網數據中心（IDC,Internet Data Center）聯合發布的《數據時代2025》白皮書中預測，2025 年全球數據量將達到163 ZB，其中，超過25%的數據為實時數據。

由此可見，對大規模數據的實時分析和處理具有非常廣闊的應用前景。就目前的研究成果來看，以MapReduce[2]為代表的批量計算框架[3-4]的計算時延較高，無法滿足業務的實時性要求。流式計算將處于活動狀態的數據持續發送至各工作節點，計算和傳輸不間斷發生，中間結果僅存在于內存而不需要持久存儲，為實時數據的處理提供了良好的解決方案[5]。作為一款開源、高性能、分布式的數據流處理平臺[6]，Flink[7]已經成為流數據處理領域的通用計算平臺。與傳統的流式計算平臺Apache Storm[8]相比，Flink 支持有狀態的流式計算[9]和Exactly-Once 的容錯機制[10]；與新興流式計算平臺Apache Heron[11]相比，Flink 具有更成熟的平臺架構和更廣泛的產業基礎。因此，Flink 已經成為集批處理與流處理為一體的統一數據分析平臺，得到學術界和產業界的廣泛關注。

然而，Flink 的發展也面臨一系列的挑戰。首先，Flink 和傳統流式計算平臺一樣，均面臨負載波動環境下資源不足導致性能下降的問題。其次，作業執行中集群的規模和算子的并行度是固定不變的，但計算負載是波動變化的，如果計算資源無法滿足計算負載的需求，就會嚴重影響計算的實時性，因此彈性資源調度策略的研究非常重要。最后，現有研究僅以當前的計算負載為依據制定彈性資源調度計劃，無法適應未來一段時間的負載變化，從而導致調度滯后的問題。因此，結合機器學習算法實現動態彈性資源調度策略，將是未來研究的新熱點[12]。但目前的主流預測方法對數據波動的抗干擾能力不足，在負載劇烈波動的流式計算環境中往往難以達到足夠的預測準確性。此外，目前主流的資源判定模型[13-14]主要從拓撲結構的全局角度判定資源與負載的相對關系，無法從局部發現集群的性能瓶頸，無法適用于彈性資源調度的應用場景。

針對上述問題，本文提出Flink 環境下基于負載預測的彈性資源調度（LPERS-Flink,load prediction based elastic resource scheduling in Flink）策略，本文的主要貢獻總結如下。

1) 提出將機器學習算法應用于流式計算平臺底層優化的思想，并在此基礎上提出基于時間序列的預測算法，在負載劇烈波動的場景中取得較高的預測準確性，為提出在線彈性資源調度策略提供了模型支撐。

2) 在負載預測模型的基礎上提出負載預測算法，根據已知的負載變化規律預測未來的變化趨勢，從而將作業的拓撲結構抽象為預測網絡模型，為提出基于負載變化趨勢的彈性資源調度策略提供數據基礎。

3) 在資源判定模型的基礎上提出資源判定算法，針對集群存在的資源瓶頸與資源過剩的問題，制定相應的彈性資源調度計劃，動態改變集群的規模與作業的拓撲結構，優化集群的資源配置。

4) 針對彈性資源調度開銷過高的問題，提出基于同步計算和異步狀態數據拉取的在線負載遷移算法，通過在線遷移計算負載和狀態數據，實現對用戶透明的高效彈性資源調度。

2 相關研究

在負載波動環境下，因集群資源不足產生性能下降的問題是目前流式計算平臺面臨的主要技術挑戰，其中Storm 平臺現有的資源調度策略存在調度開銷高和調度滯后的問題，新生Heron 平臺未提供針對負載波動場景的解決方案。因此，在負載劇烈波動環境下，集群因資源不足而遇到性能瓶頸的問題，是流式計算研究面臨的主要難點。

針對上述問題，國內外學者分別從不同的角度提出了解決方案。目前，現有的研究成果主要基于以下3 種方案來解決該問題：1) 通過優化任務調度策略提高集群性能；2) 通過降低通信開銷提高作業的執行效率；3) 通過提出彈性資源調度策略突破集群的性能瓶頸。

首先，傳統的流式計算平臺研究大多關注優化集群的任務調度策略，通過提高集群性能降低計算時延。文獻[14-15]分別根據作業拓撲結構的有向無環圖模型提出2 種不同的任務調度策略，在提高集群性能、降低計算時延的同時降低了集群的運行能耗[13,16]，取得了一定的優化效果。文獻[17-20]分別通過分析作業的拓撲結構及特點，從不同角度提出了相應的任務調度策略。然而，在面對持續波動的計算負載時，優化任務調度策略只能提高集群的資源利用率，并不能從根本上解決集群資源不足的問題。其次，降低通信開銷是提高作業執行效率的另一種有效方案。文獻[21]針對Storm 平臺提出的T3-Scheduler，通過尋找集群中數據傳輸量較大的2 個任務，并將其部署在同一個節點上，有效降低了任務之間的通信開銷。文獻[22]提出將機器學習算法應用于流式計算平臺優化的思想，通過監控與集群傳輸性能有關的指標，提出基于機器學習的任務重部署策略，有效降低了節點之間的數據傳輸開銷。文獻[23-25]以降低集群的通信開銷為目標，分別提出不同的任務調度策略，但這些調度策略有可能造成節點的CPU 或內存資源利用率急劇上升，進而導致節點資源溢出的問題，在計算負載急劇上升的場景中無法提供有效的解決方案。

與上述2 種方案相比，彈性資源調度策略通過動態增加計算資源突破集群性能瓶頸，是解決集群性能問題的最有效方案[26]。文獻[27]提出一種適用于Storm 平臺的彈性資源調度策略，通過區分有狀態數據流和無狀態數據流的應用場景，分別處理2種情況，實現了高效的彈性資源調度。文獻[28-29]提出基于強化學習的彈性資源調度策略，通過監控集群性能指標并執行強化學習算法，實現集群規模的動態自適應變化，創新性地提出將機器學習算法應用于分布式計算平臺優化的思想，但該策略在產業界的大規模應用仍面臨一定挑戰。文獻[30-34]從不同的角度提出彈性資源調度策略，但大多適用于傳統的Storm 平臺，受限于平臺架構的區別而無法應用于Flink 平臺。

此外，文獻[35]提出基于流網絡的離線彈性資源調度策略，通過建立流網絡模型定位集群性能瓶頸，并通過動態增加計算節點突破瓶頸，是本文研究的前提和基礎工作。但該策略使用離線的負載遷移算法，存在調度滯后和調度過程中作業停滯的問題，影響計算的實時性。文獻[36]提出適用于Flink平臺內核Nephel 的響應式資源調度策略，通過建立數學模型計算每個算子的最優并行度，并通過任務遷移實現集群資源的動態伸縮，與本文的研究目標緊密相關，但其負載遷移過程中的網絡傳輸開銷較大。文獻[37]提出的SRA（state and runtime-aware）-Stream 是一種有狀態數據流的彈性資源調度策略，該策略既考慮計算負載與響應時間的數學關系，也考慮狀態數據遷移的問題，是一種非常高效的彈性資源調度策略，但該策略僅適用于Storm 平臺。現有的研究成果大多面臨以下問題：1) 以當前的計算負載為依據進行彈性資源調度，忽略了未來負載可能出現的波動變化，存在調度滯后的問題；2) 離線的調度策略本身產生過高的資源開銷，存在調度過程中性能下降的問題；3) 現有研究多適用于傳統的Storm 平臺，受限于平臺架構之間的區別而無法移植于目前主流的Flink 平臺。

針對上述問題，本文提出基于負載預測的在線彈性資源調度策略，并將其應用于Flink 平臺。本文與現有研究成果的不同之處總結如下。

1) 現有研究成果大多基于當前時刻的計算負載進行彈性資源調度，存在調度滯后的問題。本文將機器學習算法應用于流式計算平臺的底層優化，基于負載預測結果進行提前調度，實現集群規模和資源配置對負載變化的及時響應。

2) 現有研究成果大多在計算資源不足時增加節點以避免出現資源瓶頸，但忽略了在資源過剩時出現的資源浪費問題。本文通過定位集群的資源瓶頸與資源過剩，動態擴大和縮小集群規模，從而優化集群的資源配置。

3) 現有研究成果大多采用離線資源調度的方式，調度過程中存在數據堆積和時延上升的問題。本文提出基于異步狀態數據拉取的在線彈性資源調度策略，有效解決調度過程中集群性能下降的問題。

3 問題建模與分析

針對大數據流式計算的突發性特征[5]，為了應對計算負載的波動變化，本節分別建立了基礎邏輯模型、負載預測模型和資源判定模型。首先，通過基礎邏輯模型對作業的拓撲結構進行抽象，量化集群資源與負載的數學關系；然后，通過負載預測模型預測計算負載的變化趨勢；最后，通過資源判定模型定位集群的資源瓶頸與資源過剩，為實現在線彈性資源調度策略提供理論依據。

3.1 基礎邏輯模型

作為目前主流的分布式數據流處理平臺，Apache Flink 采用主從式架構，如圖1 所示。主節點為JobManager，負責管理計算資源、接收用戶提交的作業并根據其拓撲結構部署任務。工作節點為TaskManager，負責根據JobManager 的調度，執行計算任務并完成數據處理。

圖1 Apache Flink 基礎架構

在TaskManager 中，每個任務槽（TaskSlot）都是一個線程，負責執行任務并完成數據處理，其計算的中間結果可能存儲在內存或輕量級數據庫等存儲介質中，作為節點的狀態數據。因此，主節點以任務槽為基本單位進行資源管理，每個任務槽代表任務執行中可能用到的CPU、內存等計算資源。在作業執行過程中，待處理的數據從源點發出，依次經過計算節點的處理，最終計算結果在匯點被持久化存儲。節點能夠處理數據的最高速率為節點的計算能力，從源點實際發出數據的速率為當前的計算負載，為了應對計算負載的波動變化，建立流網絡模型，量化集群計算能力與計算負載的數學關系。

預測網絡模型如圖2 所示。將流式計算的拓撲結構定義為有向無環圖模型，其中，節點表示處理數據的任務槽，邊表示節點之間的數據傳輸鏈路。為了量化計算能力與計算負載的關系，將每個節點能夠處理的最高計算負載定義為對應邊的容量c(vi,vj)，通過文獻[35]的流網絡構建算法可以計算每條邊的容量取值。節點實際的計算負載定義為當前時刻的流量f(vi,vj)，從而將有向無環圖模型轉化為流網絡模型。針對現有彈性資源調度策略存在調度滯后的問題，通過建立負載預測模型，預測未來負載的變化趨勢。

3.2 負載預測模型

假設一段時間內，以固定的時間間隔采集到源點發送數據的速率為F={f1,f2,…,ft}，且樣本的均值為μ，方差為σ2。為了使用差分整合移動平均自回歸（ARIMA,autoregressive integrated moving average）模型進行負載預測，要求計算負載的均值和方差保持基本穩定，即未來的計算負載與之前的負載取值具有相關關系，這樣的數據樣本是平穩的。通過建立不同時刻計算負載之間的函數關系，可以預測未來計算負載的變化趨勢。

然而，在實際應用中，計算負載是隨著時間的推移而劇烈波動的，通常無法滿足預測模型對樣本的平穩性要求。因此，通過分別計算t時刻與t?1 時刻負載的差值，可得到計算負載的一階差分，即

其中，ft為t時刻源點發送數據的速率。當一階差分仍然存在劇烈波動時，計算t時刻與t?1 時刻的差值，得到計算負載的二階差分。依次類推，負載的d階差分為

圖2 預測網絡模型

特別地，如果ρk>0.5，說明不同時刻的負載取值之間具有很強的相關關系，即當前的d階差分序列能夠滿足預測的平穩性要求。通過建立負載回歸模型，能夠描述不同時刻負載取值之間的依賴關系。

定義1負載回歸模型。計算負載的d階差分序列中，第t時刻的負載取值為，之前第t?i時刻的樣本取值為，則t時刻與之前i時刻負載的函數關系為

其中，λi是模型的參數，μt是常數項，λi和μt均可通過最大似然估計等方法計算得出；εi是預測過程中可能產生的隨機波動，可通過負載平均模型消除由波動產生的誤差。

由定義1 可知，負載回歸模型建立了不同時刻的計算負載之間的函數關系，從而可以根據過去一段時間的負載變化規律，預測未來負載的變化趨勢。然而，利用負載回歸模型進行預測的過程中，仍有可能因εi而產生誤差。因此，通過建立負載平均模型，消除負載變化過程中可能產生的隨機波動，從而降低誤差并提高預測的準確性。

定義2負載平均模型。計算負載的d階差分序列中，用εt表示t時刻計算負載可能產生的隨機波動，則

其中，εt?i表示t?i時刻負載的隨機波動。通過建立不同時刻負載變化的函數關系，消除隨機波動，從而建立更準確的負載預測模型。

定義3負載預測模型。計算負載的d階差分序列中，通過消除樣本產生的隨機波動，并將式(5)代入式(4)，可得預測t時刻的負載取值為

由定義3 可知，在負載預測模型中，λi、θi和μt可通過最大似然估計等方法計算得出，而三元組(d,p,q)則需要在建立模型之前通過外部輸入確定。其中，d表示對負載序列進行差分計算的階數，p表示當前時刻的負載取值與之前p時刻的取值有相關關系，q表示當前時刻的負載波動與之前q時刻負載波動有相關關系。本文通過自相關系數及偏自相關系數，確定三元組(d,p,q)取值。

設計算負載的d階差分序列中，t時刻的負載與t?k時刻負載的自相關系數為ρk，則t時刻與t?k時刻負載的偏自相關系數為

由式(9)可知，預測誤差描述了預測值與真實值之前的差別。

參數選擇依據如表1 所示。相關系數收斂于0表示該系數基本趨于穩定并無限接近于0；相關系數滿足置信區間，表示在該置信區間內樣本的相關系數都滿足設定的取值范圍。置信區間描述了在特定區間范圍內的樣本都滿足表1 設定的取值條件，置信區間過大會導致計算時間開銷過高且出現過擬合的現象，置信區間過小出現欠擬合導致預測的準確性降低。綜上所述，通過在平穩的負載序列上計算樣本的自相關系數和偏自相關系數作為參數選擇的依據，就可以確定參數p和q的理想取值范圍。

表1 參數選擇依據

3.3 資源判定模型

在負載預測模型的基礎上，為了定位預測網絡中可能出現的資源瓶頸與資源過剩，作為提出彈性資源調度算法的依據，需要進一步定義預測網絡的劃分和最小節點。預測網絡劃分如圖3 所示。

設預測網絡G=(V,E)，s是預測網絡的源點，t是匯點。則該預測網絡的一個劃分D=(X,Y)將節點集V分為2 個集合X和Y，其中Y=V?X，使s∈X，t∈Y，且X∩Y=?，X∪Y=V。對于作業拓撲結構中的任意算子O，?vi,vj∈O有vi,vj∈X或vi,vj∈Y，即同一個算子的不同實例不橫跨任意一個劃分。該劃分D=(X,Y)的容量值為

且下一時刻該劃分的預測流量值為

由此可知，預測網絡中每個算子對應唯一的劃分，表示集群中可能存在的資源瓶頸或資源過剩。

定義4最小節點。設預測網絡G=(V,E)有一個劃分D=(X,Y)，其中，vi∈Y，則vi的容量為所有對應輸入邊容量的累加和，記為

其中，c(vj,vi)是vi的輸入邊(vj,vi)的容量值。在劃分D=(X,Y)中容量值最小的一個節點稱為D的最小節點。

由定義4 可知，預測網絡的劃分代表了集群中可能存在的資源瓶頸和資源過剩，如果一個劃分代表的算子中存在資源過剩，則該劃分的最小節點是非必要的計算節點。通過遷移負載并刪除該節點，可以優化集群的資源配置，減少不必要的資源開銷。因此，通過預測負載的變化趨勢并判定資源與負載的數學關系，可以準確定位集群的資源瓶頸、資源過剩以及非必要節點。

圖3 預測網絡劃分

假設預測網絡G=(V,E)存在一個劃分為D=(X,Y)，且存在一個節點vi∈Y是D的最小節點。假設當前時刻的預測流量為′，接下來2 個時刻的預測流量分別為。若存在f′(X,Y)≥αc(X,Y)且，說明預測計算負載大于設定的閾值，且預測得出計算負載呈持續上升趨勢，D會因為計算資源不足而成為集群的性能瓶頸，因此需要通過增加計算節點，擴大D所對應算子的并行度，以保證集群性能 。反之，若存在，則D中存在資源過剩，由于vi是D的最小節點，c(X,Y) ?c(vi)表示在D中刪除最小節點后剩余節點的計算能力，當f′(X,Y)<α(c(X,Y) ?c(vi))時，說明刪除vi后，剩余節點的計算能力仍然大于設定的負載閾值，且預測得出計算負載呈持續下降趨勢，因此節點vi是D中冗余的計算資源，通過刪去vi可以優化集群的資源配置，避免出現資源浪費。由此可知，通過定義預測網絡的劃分和最小節點，設立判定集群資源配置的條件作為制定彈性資源調度計劃的依據，并通過在線負載遷移算法可以提高彈性資源調度策略的執行效率。

4 在線資源調度策略

在第3 節建立相關模型的基礎上，本節提出基于負載預測的在線彈性資源調度策略，通過預測計算負載的變化趨勢，定位集群的資源瓶頸與資源過剩，并通過在線負載遷移實現高效的彈性資源調度。該策略主要分為以下4 個步驟，具體執行流程如圖4 所示。

步驟 1建立負載預測模型并確定參數取值。

步驟2預測未來的負載變化趨勢并建立預測網絡。

步驟3定位集群中存在的資源瓶頸與資源過剩，制定相應的彈性資源調度計劃。

步驟4執行彈性資源調度計劃，在線遷移計算負載與狀態數據。

圖4 LPERS-Flink 策略執行流程

4.1 負載預測算法

為了實現集群規模對負載變化的及時響應，需要通過負載預測模型建立不同時刻計算負載之間的函數關系，根據過去的負載變化規律預測未來的變化趨勢，從而根據資源與負載的數學關系定位集群的資源瓶頸和資源過剩。

由3.2 節可知，在負載預測模型中，參數三元組(d,p,q)的取值對模型的建立非常重要，選擇合適的參數能夠有效提高預測的準確性，降低模型的復雜度。本節通過衡量負載樣本序列的平穩性，確定差分計算的次數求得d的取值；通過計算自相關系數ρk和偏自相關系數?k,k，以表1 為依據確定p和q的取值范圍。為了在該范圍內進一步確定參數的最優取值，需要通過貝葉斯信息準則（BIC,Bayesian information criterion）衡量預測的準確性和模型的復雜度，找到預測準確性最高且復雜度最低的預測模型。假設在一段時間內，以固定的時間間隔采集負載樣本的序列為F，則貝葉斯信息準則的計算式為

其中，k=p+q為待求解參數的數目，n=|F|為負載序列中的樣本總數，L為預測函數（如式(6)所示）。由此可知，BIC 表示預測準確性與模型復雜度之間的權衡，在參數范圍內尋找能夠使BIC 達到最小值的參數組合，即預測準確性最高且模型復雜度最低的參數取值，作為負載預測模型的最優參數。

接下來，通過建立預測函數，求解參數組λi和θi的取值，驗證模型的準確性并不斷執行預測，將作業拓撲的流網絡轉化為預測網絡模型。根據上述思想，負載預測算法的執行過程如算法1 所示。

算法1負載預測算法

輸入負載樣本序列F,流網絡G

輸出預測網絡G′

算法1 首先通過計算差分提高樣本的平穩性（第1)行）。其次，通過計算自相關系數和偏自相關系數確定參數的取值范圍（第2)行～第4)行），并通過貝葉斯信息準則確定參數的最優取值（第5)行～第7)行）。再次，建立基于ARIMA 的預測模型并驗證預測的準確性（第9)行～第11)行）。最后，預測每條邊上的未來負載，將流網絡轉化為預測網絡模型（第12)行～第15)行）。

在時間復雜度方面，建立和驗證模型的時間復雜度均為O(1)，確定最優參數時需要遍歷其取值范圍內的所有值，復雜度為O(pq)，建立預測網絡的復雜度為O(|E|)。因此算法1 的時間復雜度為T(n)=O(pq+|E|)。通常p和q的取值不超過10，預測網絡中邊的數目不超過500，因此算法1 的時間復雜度較低。

4.2 在線資源調度算法

負載預測算法通過預測未來負載的變化趨勢，將流網絡模型轉化為預測網絡。此外，通過建立資源判定模型，在預測網絡中定位集群的資源瓶頸與資源過剩，從而制定相應的彈性資源調度計劃。

由3.3 節可知，根據資源判定模型依次檢查預測網絡中的每一個算子，當算子對應的劃分滿足f′(X,Y)≥αc(X,Y)，且預測負載持續上升時，該算子成為集群的資源瓶頸，需要增加節點并擴大算子的并行度。反之，當算子對應的劃分滿足f′(X,Y)<α(c(X,Y) ?c(vi))，且預測負載持續下降時，該算子存在資源過剩，需要減去節點vi并縮小算子的并行度，從而避免出現資源浪費的現象。

根據上述判定規則，在線資源調度算法的執行過程如下。

算法2在線資源調度算法

輸入集群拓撲結構T,負載序列F

輸出完成資源調度后的預測網絡G′

在線資源調度算法需要基于之前的基礎工作來實現。首先，調用文獻[35]的構建算法構建流網絡模型（第1) 行），并調用算法1 將其更新為預測網絡（第2) 行）。其次，調用文獻[38]的最大流算法優化負載分配（第3) 行），最大化利用現有的計算資源。再次，根據資源判定模型定位集群的資源瓶頸與資源過剩，分別對資源瓶頸增加節點（第6)行～第9) 行），對資源過剩減少節點（第10) 行～第13) 行），從而優化集群的資源配置。最后，調用在線負載遷移算法，完成在線彈性資源調度（第9) 行和第12) 行）。

在時間復雜度方面，流網絡構建算法[35]的時間復雜度為O(|V|+|E|)，最大流算法[38]的時間復雜度為，負載預測算法的時間復雜度為O(pq+|E|)，判定集群資源利用情況和制定彈性資源調度計劃的時間復雜度均為O(1)，其中，線性級的時間復雜度可忽略。綜上所述，在線資源調度算法的整體時間復雜度為

實驗結果表明，算法2 的時間復雜度在合理可接受的范圍內，且能夠有效提升集群的性能。

傳統的離線資源調度策略中，資源和任務的調度總是伴隨著一定的時間開銷，離線的任務、負載和狀態數據遷移過程中作業有短暫的停滯，引發數據堆積和時延升高的問題。為了解決這一問題，本文提出在線負載遷移算法，從而實現高效、實時的彈性資源調度。

4.3 在線負載遷移算法

為了解決離線彈性資源調度策略存在數據堆積和時延升高的問題，本文提出在線負載遷移算法。通過同步執行任務、數據備份與緩存、異步狀態數據拉取的方式，結合Flink 平臺現有的檢查點策略，實現在線負載遷移技術。在線負載遷移過程如圖5 所示。

圖5 在線負載遷移示意

當算子從一個并行實例增加到2 個時，在每個計算節點中添加數據緩沖區（buffer），用于臨時存儲待處理的數據。完成第一個Checkpoint 后，節點的狀態數據已經存儲在Hadoop 分布式文件系統（HDFS,Hadoop distributed file system）中。在下一次Checkpoint 開始前，上游節點將待處理的數據復制2 份分別發送至2 個下游節點，原工作節點（圖5中的節點2）繼續處理數據，實時產生計算結果并發送給下游節點。同時，新增節點（圖5 中的節點3）以異步的方式從HDFS 中拉取對應的狀態數據，并通過同步處理緩沖區中的數據，執行狀態的合并，但不輸出計算結果。完成下一次Checkpoint后，上游節點將待處理的數據發送至新增工作節點，新增節點執行任務并向下游節點輸出計算結果，從而實現用戶無感知的透明負載遷移。具體步驟如算法3 所示。

算法3在線負載遷移算法

輸入執行彈性資源調度的算子Operator; 節點資源池pool

輸出完成資源調度后的預測網絡G′

算法3 描述了動態增加節點時的負載遷移過程。對于每個需要執行彈性資源調度的算子，首先從資源池中獲取一個計算節點（第3)行），修改Zookeeper 中狀態數據到節點的映射關系（第4)行）。然后，執行如圖5 所示的數據并行發送與緩存、HDFS 異步數據獲取（第5)行～第7)行）。最后，在完成下一次Checkpoint 之后，將上游發送的計算負載切換到新的計算節點中（第8)行～第9)行）。這樣，集群在兩次Checkpoint 之間完成了彈性資源調度，且不影響正常的數據處理，調度過程中保證了計算的實時性。此外，動態減少節點與增加節點的過程基本類似，其區別在于，動態增加節點時，先從資源池獲取節點，再遷移負載；動態減少節點時，先遷移負載，再向資源池歸還節點。

在時間復雜度方面，首先，負載遷移是一個分布式算法，上述過程由多個節點并行完成，并由JobManager 統一部署和監控，其時間開銷很低。其次，由于算法遍歷拓撲結構中每一個算子，其時間復雜度與拓撲結構中算子的數目相關，即T(n)=O(|G′.O|)。實驗證明，在線負載遷移算法有效降低了LPERS-Flink 策略的時間開銷，針對性解決了數據堆積和時延升高的問題。

4.4 算法實現與部署

在Flink 的基本架構中，一個完整的流式作業通常從Kafka 等數據源讀取數據，由不同的工作節點協同完成計算，并將計算結果寫入HDFS 等存儲系統中，通過Checkpoint 機制將節點的狀態數據存儲在HDFS 中。為了實現LPERS-Flink 策略，需要監控節點的計算負載，預測負載的變化趨勢，制定彈性資源調度計劃并存儲在Zookeeper 中，最后通過在線負載遷移實施調度計劃。

為了實現LPERS-Flink，需要對Flink 的基本架構進行改進，改進后的集群主要包含以下模塊：數據持久化模塊，用于存儲待處理的數據或計算結果；數據處理模塊，由Flink 集群承擔，主要依據用戶定義的業務邏輯完成數據處理；負載預測模塊，主要負責采集計算負載并預測變化趨勢，形成預測網絡模型并存儲在資源協調器中；資源協調模塊，負責同步各節點的執行狀態，存儲預測網絡及資源調度計劃。LPERS-Flink 部署架構如圖6 所示。

圖6 LPERS-Flink 部署架構

如圖6 所示，LPERS-Flink 在Flink 原系統的基礎上分別加入了負載監控節點、負載預測節點、資源協調節點、資源調度節點和負載遷移執行器。

1) 負載監控節點。負責監控和采集節點的計算負載，即節點輸入數據的速率，并寫入MySQL 數據庫。

2) 負載預測節點。執行算法1，根據MySQL數據庫中的負載序列，預測計算節點的負載變化趨勢，形成預測網絡并寫入資源協調節點。

3) 資源協調節點。由Zookeeper 集群承擔，存儲節點的元數據信息、預測網絡模型以及資源調度計劃。

4) 資源調度節點。執行算法2，基于資源判定模型確定集群資源瓶頸與資源過剩，制定資源調度計劃并寫入資源協調節點。

5) 負載遷移執行器。執行算法3，根據資源協調節點中的資源調度計劃，從HDFS 中拉取節點對應的狀態數據并完成負載遷移，從而實現在線資源調度。

5 實驗與分析

為了驗證LPERS-Flink 策略的有效性，本文對LPERS-Flink 與Flink v1.6.0 原系統及相關研究成果進行對比實驗。在相同的配置環境下分別執行3 個代表不同作業類型的標準Benchmark，驗證了負載預測的準確性和參數取值的合理性，討論了LPERS-Flink 策略的優化效果和執行開銷。

5.1 實驗環境

實驗搭建的集群由23 臺同構的PC 機組成。其中，Flink 集群包含一個JobManager 節點、6 個TaskManager 節點；資源池中包含4 個TaskManager備用節點，在需要彈性增加節點時啟動并部署計算任務；其他相關組件包括3 個節點構成的Hadoop集群、3 個節點構成的Kafka 集群和3 個節點構成的Zookeeper 集群。另外，由一個節點執行負載監控，一個節點執行負載預測，一個節點負責生成預測網絡和資源調度計劃。其中，每個節點的硬件配置參數和軟件配置參數分別如表2 和表3 所示。

表2 節點硬件配置參數

為了使集群達到最優性能，根據現有的軟硬件環境，對Flink 的相關配置參數進行了調整，其中重要的配置項及其參數值如表4 所示。關于預測模型的重要參數(d,p,q)的取值，在5.2 節進行了詳細介紹。

表3 節點軟件配置參數

根據3.2 節可知，在負載預測模型中，置信區間的設定對預測的準確性和預測算法的執行效率非常重要，為了確定合適的置信區間取值，實驗分別在不同的置信區間下，根據式(9)計算負載的預測誤差與預測時間，實驗結果如表5 所示。因此，實驗選取的置信區間為[0.95,1]，在該置信區間下的預測誤差δ=0.035，即δ<0.05，滿足預測的準確性要求，同時避免了過高的預測時間開銷。

表5 不同置信區間下的預測誤差與預測時間

文獻[35]提出的 FAR-Flink（flow network based auto rescale strategy for Flink）策略是本文的前提和基礎性工作。文獻[36]提出的EN（elastic nephel）策略與本文的研究目標緊密相關。為了驗證 LPERS-Flink 策略的優化效果，實驗將LPERS-Flink 與Flink 原系統（Flink v1.6.0）、FAR-Flink 和EN 進行對比實驗，在4 個平臺上分別 執 行 WordCount、TwitterSentiment 以 及Streaming-Benchmark 這3 種代表不同作業類型的典型Benchmark，分析了LPERS-Flink 策略的優化效果和執行開銷。

5.2 預測算法參數與性能

為了使用ARIMA 模型進行負載預測，根據未來的負載變化趨勢進行彈性資源調度，需要首先確定差分次數d的取值，再通過計算自相關系數和偏自相關系數確定p和q的取值，從而得到模型的參數三元組(d,p,q)，并建立負載預測模型。

本節實驗模擬了Twitter 公司線上業務中負載劇烈波動的現象，TwitterSentiment 作業中建立負載預測模型過程的差分計算結果如圖7 所示。從圖7 中可以看出，負載的一階差分序列無法滿足預測模型對樣本的平穩性要求，且序列中存在個別的奇異值。通過計算負載的二階差分，負載序列在一段時間內基本趨于平穩，且奇異值明顯減少，負載的自相關系數ρk=0.68，滿足預測模型對樣本的平穩性要求。因此，可確定預測模型的第一個參數d=2。

負載相關系數如圖8 所示，根據式(3)和式(7)分別計算了負載樣本序列的ACF 和PACF 取值，反映了負載序列中不同時刻的樣本之間的相關關系。由圖8 可知，在不考慮奇異值的前提下，ACF在2 階之后滿足置信區間，在8 階之后收斂于0，因此p的取值范圍為[2,8]；PACF 在2 階之后滿足置信區間，在3 階之后收斂于0，因此q的取值范圍為[2,3]。

通過算法1 計算BIC 指數確定參數三元組(d,p,q)的最優取值為(2,5,3)，從而建立負載預測模型，采集連續20 s 的預測負載和真實負載，結果如圖9所示。圖9 反映了一段時間內，負載預測值與真實值的偏離情況，為了更直觀地描述負載預測算法的準確性，將圖9 中關鍵時間點的負載預測值和真實值整理如表6 所示。

圖7 負載的差分計算結果

圖8 負載相關系數

圖9 預測負載與真實負載

表6 預測負載偏差取值

根據式(9)計算可得，在0～20 s，負載的預測誤差δ=0.035，即δ<0.05，且預測負載和真實值的變化趨勢基本一致，預測結果與真實取值足夠接近，預測負載能夠反映未來負載的變化規律和近似取值，能夠滿足彈性資源調度策略對負載預測算法的準確性要求。因此，LPERS-Flink 策略能夠以預測負載為依據制定相應的彈性資源調度計劃，且參數(d,p,q)的取值是合理的。

5.3 LPERS-Flink 性能測試

WordCount 是用于統計英文文本中單詞頻數的作業，作為CPU 密集型的標準Benchmark，其執行過程中消耗大量的CPU 資源。實驗在4 個平臺上使用相同的配置參數分別執行作業，每隔10 s 采集一次計算時延及源點的數據堆積情況，WordCount作業執行效率對比如圖10 所示。

由圖10 可知，LPERS-Flink 在CPU 密集型的作業中有較明顯的優勢，隨著計算負載的波動上升，原系統出現性能瓶頸，計算時延明顯上升。EN 和FAR-Flink 在彈性資源調度過程中，均存在調度滯后和開銷過大的問題。然而，LPERS-Flink 通過在線負載遷移實現實時彈性資源調度，預先增加計算資源以應對負載的變化，其計算時延存在輕微的波動，但沒有明顯上升的趨勢。在數據堆積方面，FAR-Flink 集群在彈性資源調度過程中出現了明顯的性能下降，導致數據堆積顯著上升（300～360 s）；EN 由于調度過程中性能下降，導致計算時延上升；而LPERS-Flink根據預測負載提前改變集群規模，及時處理源點發出的數據，有效緩解數據堆積的問題，同時通過在線負載遷移算法實現對用戶透明的彈性資源調度。

圖10 WordCount 作業執行效率對比

TwitterSentiment 是Twitter 公司開發的根據用戶發布的推文進行實時情感分析的作業，是實際應用場景中的標準Benchmark，其計算過程中產生較復雜的狀態數據，占用大量的內存資源。實驗監測集群的吞吐量和節點的內存占用情況，TwitterSentiment作業執行效率對比如圖11 所示。

圖11 TwitterSentiment 作業執行效率對比

由圖11 可知，隨著計算負載的持續上升，原系統遇到了內存資源的瓶頸，其吞吐量最高只能達到57 563 tuple/s。EN 和FAR-Flink 分別在660～720 s觸發了彈性資源調度，但這是在負載急劇上升之后才發生的調度，存在調度滯后的問題。LPERS-Flink在580～640 s 觸發調度，通過負載預測提前感知到負載上升的趨勢，通過提前觸發彈性資源調度及時響應負載的變化，集群的最高吞吐量達到78 523 tuple/s。此外，執行離線調度的時間內集群性能明顯下降，無法保證計算的實時性。LPERS-Flink 通過在線負載遷移技術降低了負載遷移的通信開銷，解決了集群性能下降的問題，執行調度的過程中仍然能保證計算的實時性。然而，LPERS-Flink 在調度過程中出現內存資源利用率輕微波動的現象，這是因為增加計算節點和拉取狀態數據的過程占用了一定的內存資源，但并不影響正常的數據處理過程。

Streaming-Benchmark 是Yahoo 公司開發的對廣告數據進行實時分析的作業，其計算邏輯復雜且存在大規模狀態數據，因此其執行過程中消耗大量的節點CPU 和內存資源，是實時計算領域的標準Benchmark。實驗分別采集了作業執行過程中的吞吐量、計算時延、數據堆積、節點的CPU 利用率和內存利用率，得到如圖12 所示的實驗結果。

實驗結果表明，在計算復雜度高的作業中，調度滯后和負載遷移開銷大的問題嚴重影響集群性能，無法保證計算的實時性。如圖12(a)和圖12(b)所示，隨著計算計算負載的波動上升，EN 和FAR-Flink 分別在660～720 s 發生彈性資源調度，存在明顯調度滯后的問題。而LPERS-Flink 在540～600 s 觸發彈性資源調度，預測算法使集群提前感知到了負載急劇上升的趨勢，且預測負載與實際負載基本一致，保證了調度計劃的準確性。此外，在執行彈性資源調度的過程中，EN 和FAR-Flink 均因為觸發彈性資源調整，在調度過程中出現了集群性能下降，導致其吞吐量分別降低至28 741 tuple/s 和13 257 tuple/s，而LPERS-Flink 并未因調度而導致集群性能明顯下降，其調度過程中的吞吐量能夠達到69 856 tuple/s。因此，在這一段時間內EN 和FAR-Flink 都分別出現數據堆積和時延升高的問題，無法滿足計算的實時性要求，而LPERS-Flink 基本沒有數據堆積，且計算時延穩定在300 ms 左右，這充分體現了在線負載遷移算法的優越性。在資源利用方面，如圖12(c)和圖12(d)所示，LPERS-Flink 的節點CPU 利用率和內存利用率均隨著計算負載的上升而上升，且在彈性資源調度的過程中出現輕微波動的現象，但這并不影響集群的整體性能。

綜上所述，實驗在一種彈性資源調度策略下分別執行3 個不同的標準Benchmark，通過對比不同的性能指標，得出算法的優缺點及適用場景，實驗結果如表7 所示。實驗結果表明，LPERS-Flink 通過提前預測計算負載，提高了集群對負載變化的感知能力；通過提前執行彈性資源調度及時響應計算負載的波動變化，避免調度滯后的問題；通過計算任務和狀態數據的在線遷移，降低了調度過程中由數據傳輸產生的網絡資源開銷，進而降低了任務調度的時間開銷，LPERS-Flink 的網絡傳輸開銷低于EN 和FAR-Flink，有效提升了彈性資源調度策略的執行效率。

圖12 Streaming-Benchmark 作業執行效率對比

表7 對比實驗結果

6 結束語

隨著大數據流式計算的不斷發展，Apache Flink已經成為數據分析領域的通用計算平臺，得到學術界和產業界的廣泛關注，但集群可擴展性和可伸縮性不足的問題成為制約平臺發展的瓶頸。本文提出Flink 環境下基于負載預測的彈性資源調度策略，通過準確預測負載變化、預先執行彈性資源調度以及在線負載遷移相結合的方式，從根本上解決了集群無法及時應對負載波動的問題。本文針對有狀態流式計算場景，結合Checkpoint 機制提出的彈性資源調度策略。由于Checkpoint 機制是分布式計算平臺容錯策略的主流和通用思想，除Flink 平臺外，LPERS-Flink 策略同樣適用于Apache Heron 等所有支持Checkpoint 機制的有狀態流式計算環境。

但本文算法也存在一定的局限性。首先，LPERS-Flink 策略對MySQL 和Zookeeper 有很強的依賴性，需要依靠外部組件的協助實現負載預測和彈性資源調度。其次，執行在線負載遷移的過程中，節點的資源利用率會出現輕微的波動，但不影響集群的整體性能。因此，未來的研究工作將主要集中于以下3 個方面。

1) 通過研究新的負載預測算法，進一步提高負載預測的效率和準確性，作為彈性資源調度的依據。

2) 降低調度策略對MySQL、Zookeeper 等外部組件的依賴性，實現獨立的彈性資源調度。

3) 通過優化在線負載遷移算法，減少調度過程中節點資源利用率的波動，提高集群穩定性。