邵必林，王莎莎

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

0 引言

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

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

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

1 負載預(yù)測模型

1.1 節(jié)點負載計算函數(shù)

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

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

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

(1)

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

1.2 二次指數(shù)平滑預(yù)測模型

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

(2)

其二次指數(shù)預(yù)測模型為：

(3)

1.3 二次指數(shù)平滑預(yù)測模型優(yōu)化

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

(4)

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

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

(5)

基于此，提出優(yōu)化后的動態(tài)二次指數(shù)平滑新模型為：

(6)

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

優(yōu)化后的動態(tài)二次指數(shù)預(yù)測公式為：

(7)

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

(8)

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

(9)

對上式非線性優(yōu)化模型進行求解即可得到最優(yōu)的平滑參數(shù)α，進而計算出相應(yīng)的動態(tài)平滑參數(shù)使預(yù)測結(jié)果更準確。本文采用執(zhí)行速度快，計算復(fù)雜度低的最速下降算法來求解最優(yōu)的α值。過程如下：

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

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

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

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

圖1 預(yù)測結(jié)果對比分析Fig.1 Comparative analysis of prediction results

2 動態(tài)負載均衡改進算法

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

2.1 動態(tài)閾值計算模型

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

threshold=u1α+u2β+u3γ

(10)

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

2.1.1 集群繁忙程度計算

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

(11)

2.1.2 集群響應(yīng)效率計算

集群中節(jié)點的讀寫時間直接影響系統(tǒng)整體的響應(yīng)時間，節(jié)點的讀寫時間又與節(jié)點的存儲量和性能密切相關(guān)，節(jié)點i的平均讀寫時間可由下式計算：

(12)

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

將數(shù)據(jù)節(jié)點i在集群中數(shù)據(jù)讀寫時間占整個集群中所有節(jié)點的讀寫時間比重定義為節(jié)點的響應(yīng)效率：

(13)

每個節(jié)點的響應(yīng)效率為βi，則集群整體的響應(yīng)效率為：

(14)

2.1.3 集群均衡程度計算

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

(15)

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

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

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

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

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

3 實驗結(jié)果及分析

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

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

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

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

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

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

4 結(jié)論

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