基于負載預測的HDFS動態負載均衡改進算法

邵必林，王莎莎

(西安建筑科技大學管理學院，陜西 西安 710055)

0 引言

HDFS[1-3]是Hadoop平臺中的分布式文件系統，采用分布式布局模型[4]，在大數據處理尤其是存儲方面具有非常高的可靠性、時效性。HDFS中有一個Balancer程序，是以存儲空間利用率來評估節點負載量，程序初始運行時，由用戶輸入一個閾值(threshold，范圍為0～100)，一般系統默認值為10，當數據節點中的負載值與平均負載最大差值小于閾值時，Balancer認為集群處于均衡狀態，否則就會通過遷移操作來使集群到達負載均衡[5]。

雖然HDFS以諸多優勢而被廣泛應用，但其在負載均衡過程中，只采用存儲空間利用率這單一指標來對集群做出均衡決策，并且采用設定靜態threshold的遷移判斷方法，對節點進行數據遷移和任務調度，很大程度影響了HDFS的存儲效率。文獻[6]在其默認均衡基礎上，定義了一個多指標負載衡量函數，但其參與計算的指標過多，容易帶來計算浪費和等待延遲問題。文獻[7]對Hadoop異構集群中各節點的性能差異給集群均衡帶來的影響進行綜合考慮，但卻忽略了集群整體狀態對負載均衡效果的影響。文獻[8]提出一種以存儲熵作為集群均衡判斷的新思路，有效提高了系統整體讀寫效率，但存儲熵的計算具有明顯的滯后性。

現有的HDFS負載均衡改進算法在解決負載狀態衡量的片面性、滯后性，以及閾值設定的靜態性問題等方面存在不足，本文針對此問題，提出了一種基于負載預測的HDFS動態負載均衡改進算法。

1 負載預測模型

1.1 節點負載計算函數

在分布式存儲系統研究中，研究者往往是以存儲空間使用情況來對集群中數據節點的負載進行評估，但實際上，單一指標并無法準確衡量每個節點所承受的真實負載，節點的繁忙程度對其負載狀態的影響也是至關重要的[9-10]。分析存儲節點的繁忙程度特征可知，在其運行過程中，CPU占用較少，主要存在大量的數據I/O操作，且數據的I/O快慢很大程度上取決于網絡帶寬的使用情況。

為了避免單一指標對負載狀態衡量的片面性，和對所有負載特征同時采集可能造成的資源浪費和響應延遲問題。本文選取存儲空間利用率Lstoragei、網絡帶寬占用率Lneti和I/O占用率LI/Oi三個重要指標來建立存儲節點負載計算函數，其相對于HDFS中的節點負載衡量更加全面，且契合存儲節點。設分布式存儲集群中S={S1,S2,…,Sn}，其中Si表示集群中第i個存儲節點，則存儲節點i的綜合負載值計算函數如下：

Li=ω1Lstoragei+ω2Lneti+ω3LI/Oi

(1)

式(1)中，ωi為各負載特征對存儲效率影響大小的權重系數，ω1+ω2+ω3=1且ωi>0。

1.2 二次指數平滑預測模型

分析大量的負載歷史值可知，負載變化存在短期上升或下降的線性波動。在對呈線性變化趨勢的負載時間序列采用一次指數平滑，結果會產生明顯偏差和滯后，二次指數平滑可以在此基礎上對其再做一次指數平滑來對其結果進行修正，使預測效果最佳。此外，由于三次指數平滑的時間復雜度過高，不適用于進行頻繁的負載預測[11-13]。所以本文的負載預測模型是建立在二次指數平滑算法的基礎上進行優化研究。假設t時刻的負載時間序列{Lt}(t=1,2,…)，則其二次指數平滑模型定義為：

(2)

其二次指數預測模型為：

(3)

1.3 二次指數平滑預測模型優化

對式(2)進行逐次展開得：

(4)

綜上所述可知，α需要隨著時間推進和數據更新進行不斷的動態調整，同時要舍棄掉距離當前t時刻較遠的負載歷史序列，才能使預測模型始終處于預測效果優化狀態且保持算法復雜度最低。

將式(4)中兩個公式各項系數之和進行歸一化處理，得到：

(5)

基于此，提出優化后的動態二次指數平滑新模型為：

(6)

式(6)中，vt作為相應的動態平滑參數；t0為保留的負載時間序列的{Lt}長度。

優化后的動態二次指數預測公式為：

(7)

考慮到初始值對負載預測效果影響非常小，為了將算法的復雜度降至最低，對其使用靜態值。

(8)

本文采用預測誤差平方和SSE最小為目標作為評價優化模型，即：

(9)

對上式非線性優化模型進行求解即可得到最優的平滑參數α，進而計算出相應的動態平滑參數使預測結果更準確。本文采用執行速度快，計算復雜度低的最速下降算法來求解最優的α值。過程如下：

1)分別給定初值α0和允許誤差X>0。

2)計算SSE′(α0)，如果‖SSE′(α0)‖≤X，則α0就是最優平滑參數，否則進行一維搜索，利用黃金分割法來計算最優步長λk-1，計算αk=αk-1-λk-1SSE′(αk-1)，(k≥1)，直至滿足近似最優解條件。

3)最后將αk代入式(5)求得動態平滑參數vt，使用改進后的指數平滑預測模型進行負載預測。

根據以往研究經驗，負載序列長期趨勢變化不大但存在上下波動，靜態算法中的α取值一般在0.3～0.5之間。優化模型中，為了使算法計算簡單且結果精確度高，在進行多次實驗后，最終確定了本文t0的最佳取值。圖1為二次指數平滑的靜態算法和本文優化后的動態算法與實際負載的預測結果對比，其中α=0.4，t0=6。分析可知靜態算法中由于α取值固定，預測過程中難以實現在復雜的集群環境中對負載的變化做出自適應的改變，預測結果偏差較大。本文優化后的動態算法中α是通過反復迭代尋求SSE的最優解得到，整體預測結果很大程度優于靜態算法，更適合建立負載預測模型來作為數據調度策略的一個重要依據。

圖1 預測結果對比分析Fig.1 Comparative analysis of prediction results

2 動態負載均衡改進算法

在異構分布式存儲系統中，各節點的資源和性能各不相同，負載均衡算法是將存儲資源合理的分配調度至各節點，使集群保持均衡的狀態[14-16]。HDFS中默認的負載均衡思路非常簡單，由用戶設置靜態閾值，將數據節點劃分為不同負載狀態的集合，最后將高負載狀態集合中的數據向低負載狀態集合中的節點進行遷移，直至所有節點負載與平均負載的差值小于設定的閾值，才會認為集群處于正常均衡狀態。其中閾值的設置是HDFS集群中負載均衡的關鍵，決定了系統達到平衡時所需要遷移的數據量和均衡效率。HDFS中閾值是人為設置的靜態參數，沒有考慮集群的整體狀態，也不能隨著集群環境的改變而動態的做出調整，具有較強的主觀性和靜態性。

2.1 動態閾值計算模型

基于以上分析可知，閾值的設定需要充分考慮集群的整體狀態和環境變化，時刻做出動態調整，才能使整體集群隨時處于最佳的均衡效果，且不會因為不必要的負載遷移而帶來的資源浪費，因此，本文提出一種動態閾值的獲取方式。動態閾值是根據節點的負載預測值和性能對集群的整體狀態進行綜合評估，其中包括集群的繁忙程度、響應效率、均衡程度等信息來動態計算閾值，其計算模型具體如下：

threshold=u1α+u2β+u3γ

(10)

式(10)中，μi>0且u1+u2+u3=1，α為集群的繁忙程度，β為集群的響應效率，γ為集群的均衡程度。由于threshold只能屬于在0～100間的值，所以當計算得到的動態threshold<0時，自動替換為默認值10，當threshold>100時，自動替換為100。

2.1.1 集群繁忙程度計算

集群的繁忙程度可以使用集群中所有節點的平均負載Lavg來表示，在進行Lavg的計算時，為了減少集群繁忙程度衡量的滯后性，采用集群中所有節點的負載預測值來對其平均負載Lavg進行計算。具體如下：

(11)

2.1.2 集群響應效率計算

集群中節點的讀寫時間直接影響系統整體的響應時間，節點的讀寫時間又與節點的存儲量和性能密切相關，節點i的平均讀寫時間可由下式計算：

(12)

式(12)中，SNi為第i個節點存儲的數據量；SRi為第i個節點中磁盤的I/O速率。

將數據節點i在集群中數據讀寫時間占整個集群中所有節點的讀寫時間比重定義為節點的響應效率：

(13)

每個節點的響應效率為βi，則集群整體的響應效率為：

(14)

2.1.3 集群均衡程度計算

采用集群中各存儲節點的均方差ε來衡量集群內部負載均衡程度，ε越大，說明集群內部狀態越不均衡，ε越小，說明集群內部狀態越均衡， 計算公式如下：

(15)

2.2 改進算法具體步驟和流程

1)系統初始化，設置采集節點信息的周期值T(10～15 s)，數據節點主動且周期性的對自身負載信息進行獲取，包括存儲空間利用率Lstoragei、網絡帶寬占用率Lneti、I/O占用率LI/Oi、已存儲的數據量SNi、磁盤的I/O速率SRi。代入式(1)中計算節點的負載值Li，并將Li、SNi、SRi等信息反饋給控制節點。

3)根據2)中得到的預測結果和1)中的反饋信息分別計算α，β，γ，最后由式(10)計算出動態threshold并做均衡判斷。當集群中所有節點的負載與平均負載的差值都小于threshold時，則認為集群處于正常范圍，不需要進行遷移調度；反之，需要對其進行數據遷移和任務調度，直至集群處于正常范圍。

具體算法流程如圖2所示。

圖2 改進的算法負載均衡流程圖Fig.2 Improved algorithm load balancing flow chart

3 實驗結果及分析

為驗證上述算法的高效性和優越性，采用VMware Workstation組建包含13個節點的Hadoop集群環境，其中7個節點分布于A硬盤上， I/O速率為480 MB/s，剩余節點分布于B硬盤上，I/O速率為510 MB/s。集群中有1個負責監控和任務調度的控制節點(NameNode)和12個執行任務的數據節點(DataNode)，其配置均為：CPU: Intel Core i5-4200M 2.50 GHz；內存：4 GB；硬盤：8 GB；操作系統：CentOS 6.7；編程語言：Java 1.7.0；Hadoop版本：2.5.2。在實驗中，采集節點信息的周期為15 s，其中本文算法中負載衡量函數和閾值計算函數中的權系數參數通過層次分析法，在算法實現過程中計算得到。

1)負載均衡效果對比。圖3顯示了啟用負載均衡器后的1 h集群均衡程度隨著時間推移的變化情況。圖4為上傳不同大小的數據文件，直至調度結束后，集群均衡程度的對比結果。圖中數據均為進行3組實驗后取得的平均值。如圖3所示，采用HDFS算法的集群均衡程度1 h內基本沒有變化，而采用本文算法在啟用負載均衡器后的18 min內就明顯的減少了負載均衡度值，最終均衡效果要優于HDFS算法。其原因是HDFS算法中采用默認靜態閾值10，也就是當集群負載均衡度小于10%時，會認為系統處于均衡狀態，不會對其進行負載遷移操作。而本文的閾值是通過實時評估系統的整體狀態動態得到的，從而可以使系統達到更好的均衡效果。圖4結果說明，采用HDFS算法時，集群的均衡程度受上傳數據大小的影響比較大，隨著文件大小增加，其均衡效果會減弱，而本文算法中的均衡程度則受影響較小，始終保持在0.01～0.02之間。其很大部分是因為本文算法引入了負載預測模型，所以隨著集群環境的改變其穩定性和適應性更好。

圖3 隨時間推移的集群均衡程度變化Fig.3 The loading balance degree changing chart over time

圖4 基于數據上傳的負載均衡度對比Fig.4 Load balancing comparison based on data upload

2)任務執行效率對比。為了更好觀察本文算法的執行效率，將本文算法、HDFS算法和文獻[8]中的算法進行實驗對比。圖5為系統對不同并發任務數的作業完成時間對比結果。如圖所示，任務完成時間與并發任務數大小成正比，隨著并發任務數增加，完成時間也相應增加。但文本算法與HDFS算法和文獻[8]中的算法相比較，所用的時間最少。當并發任務數為300時，HDFS算法用時為460 s，文獻[8]算法用時443 s，本文算法用時355 s，本文算法執行效率相比于HDFS算法和文獻[8]中的算法可分別提升26%和20%。其是由于本文算法中的節點信息獲取由數據節點進行，減少了控制節點的存儲負擔和計算開銷，且本文在進行算法設計時，盡可能地以降低算法時間復雜度為目標，因此大大減少了整體系統的作業執行時間。

圖5 任務完成時間對比Fig.5 Task completion time comparison

4 結論

本文提出了一種基于負載預測的HDFS動態負載均衡改進算法。該算法通過建立存儲節點負載值的多指標計算函數，并使用優化后的二次指數平滑預測模型對其負載值進行動態預測，最后根據預測結果和節點性能對集群的實時整體狀態進行評估，建立動態閾值計算模型，進而對集群做出均衡判斷和決策，有效彌補了HDFS中負載狀態衡量的片面性、滯后性以及閾值的靜態性等缺陷。理論分析和實驗結果表明，本文改進算法對存儲系統中的負載均衡調度具有高效性，不僅達到了更好的均衡效果，也縮短了作業的完成時間，提高了系統的整體響應效率。