Hadoop異構集群中數據負載均衡的研究

張　松　杜慶偉　孫　靜　孫　振

1(南京航空航天大學計算機科學與技術學院　江蘇 南京 210016)2(中國人民解放軍94860部隊　江蘇 南京 210016)

?

Hadoop異構集群中數據負載均衡的研究

張松1杜慶偉1孫靜2孫振2

1(南京航空航天大學計算機科學與技術學院江蘇 南京 210016)2(中國人民解放軍94860部隊江蘇 南京 210016)

摘要Hadoop平臺下，數據的負載均衡對平臺性能的發揮有著深遠的影響。首先分析默認數據負載均衡的局限性，針對現有默認HDFS(Hadoop Distributed File System)數據負載均衡算法只考慮存儲空間利用率，而未考慮節點間異構性的問題，提出一種量化異構集群數據負載均衡的數學模型。該模型根據節點的存儲空間及節點性能計算得到各個節點的理論空間利用率，并根據當前集群存儲空間利用率動態調整節點最大負載。實驗結果表明，提出的數據負載均衡策略能夠讓異構集群達到更合理的均衡狀態，提高集群的效率，并有效減少作業的執行時間。

關鍵詞HadoopHDFS數據負載均衡異構集群

0引言

隨著計算機技術和信息技術的飛速發展，在科研和商業領域產生了越來越規模巨大的數據，這些數據的規模甚至達到了若干PB。單臺節點顯然已經無法處理如此規模巨大的數據，云計算在此背景下應運而生。Hadoop是一個由Apache基金會所開發的開源分布式處理系統[1]。該系統由若干節點組成，數據分布在各個節點上。用戶提交作業后，Hadoop將作業拆分成若干task,然后分布到各個節點上運行，最后將結果匯總返回給用戶。

在Hadoop等數據密集型的超級計算中，移動數據的代價要遠遠高于移動計算的代價。因此將計算移動到數據節點上，將大大節省網絡帶寬，提升作業的執行效率。數據負載均衡的集群，能夠降低非本地化任務的次數，進而減少集群中數據傳輸量，提高系統效率[2]。

然而隨著新的數據節點的加入以及用戶對集群中文件的動態刪除和添加，使得各個節點擁有的數據量變得不均衡。當集群中節點間的數據負載變得不均衡后，會引發許多問題。比如，MapReduce程序無法很好地利用本地計算的優勢，計算任務被分配到非本地化執行的概率增大，于是節點不得不從其他節點復制數據，增加網絡負載。節點之間無法達到更好的網絡帶寬使用率，各節點磁盤無法達到更好的利用率，這將間接導致集群的效率降低，作業的執行時間變長。可見，保證Hadoop集群的數據平衡是非常重要是事情，數據的負載均衡已經成為分布式計算的一個重要的研究領域[3-5]。

文獻[6]對異構集群負載均衡以及文件響應時間進行了初步研究，但忽略了異構集群中節點容量的異構性。文獻[7]提出了按比例存放數據的策略，該策略考慮到了節點的異構性，然而卻忽略了節點存儲空間的異構性對數據存放的影響。文獻[8]在Hadoop數據負載均衡效率方面，提出了超負載機架的優先處理，能夠在較短時間內使各個機架的數據負載達到平衡，但并沒有考慮節點的異構性。文獻[9]改進了副本管理技術，通過動態副本來解決數據熱點的問題。

本文首先分析了默認負載均衡的原理及其局限性，然后提出了適用于異構集群的負載均衡的量化模型。最后通過大量實驗證明了在特定環境下該模型能夠更合理的降低集群的不均衡性，提高集群的效率，并有效減少作業的執行時間。

1默認負載均衡原理及其局限性

默認的負載均衡策略是基于所有節點都是同構節點這樣一個假設下的。同構集群下，由于節點的硬件配置，包括CPU、內存、磁盤容量等都是一樣的，唯一不一樣的參數為各個節點的存儲空間利用率。負載均衡的目的就是將各個節點的存儲空間利用率盡量達到一致。當集群中的部分datanode承載了過多的數據時，集群管理員便應該通過start-balancer.sh啟動均衡器，來重新布局數據塊。Balancer負載均衡程序根據用戶提交的閾值(threshold)(默認為10%)，將DataNode按照存儲空間的利用率分為四組：分別為overUtilizedDatanodes(過載的節點信息)、aboveAvgUtilizedDatanodes(大于閾值的節點信息)、belowAvgUtilizedDatanodes(小于閾值的節點信息)、underUtilizedDatanodes(空載的節點信息)。負載均衡的主要過程是將過載節點和大于閾值的節點數據往空載節點和小于閾值的節點移動，最終使得各個節點的存儲空間的利用率偏離集群平均存儲空間利用率在閾值以內。

在同構集群中，該負載均衡策略簡單并可獲得較好的效果。但是在異構集群中，由于節點的硬件配置有可能相差很大，性能高的節點顯然可以處理更多的數據。各個節點分配給HDFS的可用空間也有可能相差幾倍，將異構集群中各個節點的存儲空間利用率均衡到盡量一致并不能達到負載均衡的效果。分析這樣一種情況，假設集群中的節點Na的性能是節點Nb的一半(Pa=1/2 Pb)，節點Na的存儲空間Da為節點Nb的存儲空間Db兩倍(Da=2Db),節點Na的存儲空間使用率是節點Nb的兩倍。即性能低的節點Na的存儲空間是性能高的節點的兩倍，調用默認負載均衡程序，最終得到的期望結果會是節點Na的存儲空間利用率等于節點Nb的存儲空間利用率。表面上看兩異構節點的存儲空間的利用率達到了一個均衡狀態，實際上，該操作使得集群變得更加不均衡，性能較低的節點Na獲得了更多的數據。這使得低性能節點承擔了更多的數據負載,使得該節點在作業執行過程中成為高負載節點,同時增加了非本地化任務的概率,增加了網絡流量負載。此時，集群默認的負載均衡策略失效。所以異構集群中通過將各個節點的存儲空間利用率均衡到一個一致的期望值來使得集群負載均衡的方法是不可取的。基于對默認負載均衡原理及其局限性的分析，我們提出了一種適用于異構集群中量化數據負載均衡的數學模型。該模型基于各個節點的性能及存儲空間計算得出各個節點的理論空間利用率。

2異構集群負載均衡量化模型

2.1問題描述

異構集群的異構性不僅體現在高性能節點處理相同的工作消耗更少的時間，還體現在各節點分配給Hadoop使用的存儲空間之間的差異性。本文提出的均衡模型基于各節點的性能按比例分配存儲容量，而各節點存儲空間的異構性可能導致異構集群中節點無法承載理想的存儲容量。為此我們提出了一種基于集群異構性的量化負載均衡的數學模型。該模型基于各個節點的性能及存儲空間，分別計算得到各個節點的理論磁盤利用率。再將用戶輸入的threshold參數泛化為各個節點的閾值。最終將異構集群的負載均衡轉化為類同構集群的負載均衡，簡化異構集群負載均衡問題的復雜性。

2.2相關參數及定義

存儲空間(Cconf(i))：某節點分配給HDFS使用的容量，而非節點磁盤容量，Cconf(i)表示第i個節點的配置容量。

已用容量(Cused(i))：某個節點的存儲空間中HDFS使用的容量，Cused(i)表示第i個節點的已用容量。

節點的CPU性能(Pcpu(i))：由于多核的性能是無法達到1+1=2的效果。查閱相關資料得知，比較理想的情況下，雙核的每個核的性能為單核的0.8～0.9。所以我們取多核CPU轉換參數ρ=0.8。得到節點的CPU性能為：

Pcpu(i)=ρ×(Ncore(i)-1)×F(i)+F(i)

(1)

其中Ncore(i)為節點的CPU核數，F(i)為節點的CPU頻率(單位GHZ)，ρ為多核CPU轉換參數。

節點的內存性能(Pmem(i))：對于節點內存的衡量，采用Pmem(i)=Nmem(i)，其中Nmem(i)為節點i的內存的大小(單位為MB)。

定義1節點相對性能：

(2)

式中α和β為CPU性能和內存性能的權重因子，且α+β=1。min(Pcpu),min(Pmen)分別為集群中節點CPU性能和內存性能的最小值。將集群中的所有節點性能統一為最小值為1的量化值,方便后面的計算。并由此計算出節點的性能總和：

(3)

定義2集群的存儲空間利用率：

(4)

定義3各節點基于性能的理論存儲空間占用容量及各節點基于性能的理論存儲空間利用率：

(5)

(6)

定義4節點的動態存儲空間最大負載：

M=(0.8 + 0.2×RAvg2)×100%

(7)

由于磁盤空間的異構性，節點的存儲空間有時并不能滿足理論占用容量的需求，這時，我們需要將該節點理論上多余的數據轉移到其他節點。為了確保節點的存儲空間占用率不超過某一特定百分比這里我們需要定義一個節點最大負載。該值應該隨著集群存儲空間利用率的提高而提高。當集群負載較輕的時候，節點的最大負載應該維持在一個低水平上。這里我們采用自定義式(7)來描述節點動態最大負載,M取值范圍[80%,100%)，并隨著集群存儲空間利用率Ravg的增大而增大。若Ravg=50%，我們可以得到集群中的單個節點的最大負載為M=85%，若Ravg=50%，則M=96.2%。該公式較好地定義了節點最大負載，解決了節點可能出現的負載過重的問題，避免了用戶靜態配置導致的參數不適用的問題。

根據節點最大負載和各個節點基于性能的理論利用率，找出那些節點理論利用率大于節點最大負載的節點，并計算出盈余容量，集群盈余容量的計算公式如下：

(8)

式中i=1,2,…,n并且Rideal(i)>M 。然后再將這部分容量分配給其他節點。迭代運行，直到集群中沒有節點的理論容量大于節點最大負載值。

在將盈余容量分配給其他節點的過程中，以減少機架間數據傳輸為目的，我們采用了同機架優先的策略。該策略如下：當前機架內的某節點基于性能的理論利用率高于節點最大負載的時候，優先將該節點的容量分配到該機架的其他節點上。為此，我們定義了一個同一機架和非同一機架的配置比γ=2。該參數的意義在于優先將當前機架盈余出來的容量存放在同一機架的其他節點上，以減少機架與機架之間理論存儲空間利用率的差別。最終我們得到一組各個節點基于性能的理論存儲空間利用率。

定義5各節點參數化的閾值：

(9)

用戶輸入的threshold參數值t是集群達到平衡狀態的各節點存儲空間使用率與集群存儲空間使用率的偏差值的最大值。如果偏差值小于該值，那么我們認為該節點是均衡的。由于異構集群中，各個節點的存儲空間的異構性，該閾值所對應的存儲空間及節點性能差別較大，于是我們需要將該閾值根據式(9)參數化為各個節點的閾值。

2.3算法

下面介紹算法的詳細步驟。

1) 計算各個節點的相對性能值P(i)，節點的性能總和P以及集群的存儲空間利用率Ravg。

2) 求出各個節點基于性能的理論占用容量Cidel(i)及基于性能的理論利用率Ridel(i)。

3) 計算集群節點最大負載值M。

4) 根據節點最大負載和各個節點基于性能的理論利用率，找出那些節點理論利用率大于節點最大負載的節點，并計算出盈余容量C_supr。如果沒有找到該類節點，轉6)。

5) 基于機架的策略，優先將盈余容量分配到同一機架上。然后重新計算各個節點基于性能的理論利用率并轉到4)。

6) 將用戶輸入的threshold 通過式(8)參數化為各個節點的閾值。

7) 根據最終計算得到的各節點基于性能的理論利用率和各節點參數化后的閾值，將集群中的節點分為如表1所示四組。

表1　節點分組

8) 計算各節點需要移動的數據量并移動數據。

9) 算法結束。

3實驗與結果分析

由于實驗環境有限，測試環境由三個機架共9個節點組成。其中機架A中有兩個節點，機架B中有四個節點，機架C中有三個節點，Namenode節點位于機架B中編號為3的節點，同時該節點也作為Datanode節點。所有節點都安裝為Ubuntu 12.04操作系統。實驗環境的網絡拓撲如圖1所示。

圖1　網絡拓撲

實驗中我們的負載均衡器運行在節點編號為3的節點，即Namenode節點。其中各個節點的硬件配置如表2所示。

表2　節點硬件配置

為了比較異構集群中HDFS默認的負載均衡器和本文改進的負載均衡器之間的效果差異，我們將數據塊的副本數設定為2，并將其中幾個節點作為客戶端上傳文本數據，再刪除其中的部分數據使集群處于不均衡的狀態。然后分別運行默認負載均衡器和本文改進的負載均衡器，觀察均衡效果。同時，我們分別在運行默認負載均衡器后和運行本文改進的負載均衡器后執行Hadoop的WordCount程序，觀察程序在各個負載均衡后的執行時間。執行指令start-balancer.sh-threshold 5 ，即將閾值(threshold)設定為百分之5并執行負載均衡器，集群的狀態如表3所示。

表3　集群負載狀態

續表3

由表3的數據我們可以看出，改進后的數據負載均衡器能夠較好地依據節點的性能調整數據的分布。為了驗證本文改進的負載均衡器能夠具有較好的數據均衡效果。運行WordCount程序以觀察該程序在各狀態下的執行時間。WordCount是Hadoop官方的MapReduce的demo程序。WordCount例程讀取集群中文本文件，并統計文件中單詞出現的頻數。不同于蒙特卡羅方法計算π的demo例程，蒙特卡洛發計算π值，對節點的CPU性能要求較高，屬于CPU密集型作業，而WordCount程序屬于I/O密集型作業，對數據的分布更加敏感。本實驗采用節點5作為客戶端提交用戶WordCount作業20次，觀察作業的執行時間，并且作業執行前數據已經分布在集群中。

數據分布均衡的集群，可以有效減少作業調度帶來的計算資源和數據資源在不同的物理節點而產生的數據遷移問題，并有效減少網絡I/O，降低所謂的“非本地化任務”，縮短作業的執行時間[10, 11]。圖2顯示了在不同數據負載均衡算法下作業的執行時間，橫坐標表示的是我們執行作業的序列號，縱坐標表示的是作業的執行時間。從圖中我們可以清楚的看出，相較于默認數據負載均衡算法下作業的執行時間，改進后的數據負載均衡算法可以有效地減少作業的執行時間，提高集群效率。

圖2　不同均衡算法下作業的執行時間

4結語

本文分析了集群默認數據負載均衡的局限性，并針對該問題提出了異構集群數據負載均衡的量化模型。該模型通過綜合考慮節點性能的異構性和存儲空間的異構性求得各個節點存儲空間的理論均衡利用率，并將用戶輸入的閾值量化為各個節點的負載參數。然后移動各個節點的數據，使得各個節點的存儲空間利用率與理論均衡利用率的偏差值不大于各個節點的理論閾值。通過實驗分析，證明了該模型能夠讓集群達到更均衡的狀態，一定程度上減少了作業的執行時間，提高了集群的整體性能。

后續的研究將繼續關注Hadoop異構集群中數據的負載均衡，特別關注集群中作業的執行與數據副本之間的關系。

參考文獻

[1] White T.Hadoop:The definitive guide[M].O’Reilly Media,Inc,2012.

[2] 王意潔,孫偉東,周松,等.云計算環境下的分布存儲關鍵技術[J].Journal of Software,2012,23(4):962-986.

[3] Sun H,Chen J,Liu C,et al.Improving MapReduce Performance via Heterogeneity-Load-Aware Partition Function[C]//Cluster Computing(CLUSTER),2011 IEEE International Conference on.IEEE,2011:557-560.

[4] 楊昊溟.云存儲系統的數據副本放置算法研究[D].電子科技大學,2013.

[5] 王寧,楊揚,孟坤,等.云計算環境下基于用戶體驗的成本最優存儲策略研究[J].電子學報,2014,42(1):20-27.

[6] 劉琨,鈕文良.一種改進的Hadoop數據負載均衡算法[J].河南理工大學學報:自然科學版,2013,32(3):332-336.

[7] Xie J,Yin S,Ruan X,et al.Improving mapreduce performance through data placement in heterogeneous hadoop clusters[C]//Parallel & Distributed Processing,Workshops and Phd Forum (IPDPSW),2010 IEEE International Symposium on.IEEE,2010:1-9.

[8] 劉琨,肖琳,趙海燕.Hadoop中云數據負載均衡算法的研究及優化[J].微電子學與計算機,2012,29(9):18-22.

[9] 陶永才,張寧寧,石磊,等.異構環境下云計算數據副本動態管理研究[J].小型微型計算機系統,2013,34(7):1487-1492.

[10] Ananthanarayanan G,Agarwal S,Kandula S,et al.Scarlett:coping with skewed content popularity in mapreduce clusters[C]//Proceedings of the sixth conference on Computer systems.ACM,2011:287-300.

[11] Wei Q,Veeravalli B,Gong B,et al.CDRM:A cost-effective dynamic replication management scheme for cloud storage cluster[C]//Cluster Computing (CLUSTER),2010 IEEE International Conference on.IEEE,2010:188-196.

RESEARCH ON DATA LOAD BALANCING IN HETEROGENEOUS HADOOP CLUSTER

Zhang Song1Du Qingwei1Sun Jing2Sun Zhen2

1(SchoolofComputerScienceandTechnology,NanjingUniversityofAeronauticsandAstronautics,Nanjing210016,Jiangsu,China)2(Unit94860ofPLA,Nanjing210016,Jiangsu,China)

AbstractIn Hadoop, the data load balancing has profound effect on the exertion of platform performance. First we analysed the limitation of default data load balancing, aiming at the problem of current default HDFS (Hadoop distributed file system) that the data load balancing algorithm only focuses on the storage space utilisation but not considers the heterogeneity between nodes, we presented a mathematic model which quantifies the data load balancing of heterogeneous clusters. The model calculates the theoretical space utilisation of each node based on their allocated storage space and processing capacity, and dynamically adjusts the maximum load of each node according to current average utilisation of cluster storage space. Experimental result showed that the proposed data balancing strategy could enable the heterogeneous clusters to reach more reasonable balancing state so as to improve clusters efficiency, and to decrease the execution time of job effectively as well.

KeywordsHadoopHDFSData load balancingHeterogeneous cluster

收稿日期：2014-11-14。國家自然科學基金項目(61202350)。張松，碩士生，主研領域：計算機網絡與分布式計算。杜慶偉，副教授。孫靜，助理工程師。孫振，助理工程師。

中圖分類號TP391

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.05.009