基于負(fù)載預(yù)測的HDFS動(dòng)態(tài)負(fù)載均衡改進(jìn)算法

邵必林，王莎莎

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

0 引言

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

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

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

1 負(fù)載預(yù)測模型

1.1 節(jié)點(diǎn)負(fù)載計(jì)算函數(shù)

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

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

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

(1)

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

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

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

(2)

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

(3)

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

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

(4)

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

將式(4)中兩個(gè)公式各項(xiàng)系數(shù)之和進(jìn)行歸一化處理，得到：

(5)

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

(6)

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

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

(7)

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

(8)

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

(9)

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

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

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

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

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

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

2 動(dòng)態(tài)負(fù)載均衡改進(jìn)算法

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

2.1 動(dòng)態(tài)閾值計(jì)算模型

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

threshold=u1α+u2β+u3γ

(10)

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

2.1.1 集群繁忙程度計(jì)算

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

(11)

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

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

(12)

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

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

(13)

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

(14)

2.1.3 集群均衡程度計(jì)算

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

(15)

2.2 改進(jìn)算法具體步驟和流程

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

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

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

圖2 改進(jìn)的算法負(fù)載均衡流程圖Fig.2 Improved algorithm load balancing flow chart

3 實(shí)驗(yàn)結(jié)果及分析

為驗(yàn)證上述算法的高效性和優(yōu)越性，采用VMware Workstation組建包含13個(gè)節(jié)點(diǎn)的Hadoop集群環(huán)境，其中7個(gè)節(jié)點(diǎn)分布于A硬盤上， I/O速率為480 MB/s，剩余節(jié)點(diǎn)分布于B硬盤上，I/O速率為510 MB/s。集群中有1個(gè)負(fù)責(zé)監(jiān)控和任務(wù)調(diào)度的控制節(jié)點(diǎn)(NameNode)和12個(gè)執(zhí)行任務(wù)的數(shù)據(jù)節(jié)點(diǎn)(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。在實(shí)驗(yàn)中，采集節(jié)點(diǎn)信息的周期為15 s，其中本文算法中負(fù)載衡量函數(shù)和閾值計(jì)算函數(shù)中的權(quán)系數(shù)參數(shù)通過層次分析法，在算法實(shí)現(xiàn)過程中計(jì)算得到。

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

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

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

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

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

4 結(jié)論

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