基于異構Hadoop集群的負載均衡策略研究

秦 軍，馮亮亮，孫 蒙

(1.南京郵電大學 教育科學與技術學院，江蘇 南京 210003； 2.南京郵電大學 計算機學院，江蘇 南京 210003)

基于異構Hadoop集群的負載均衡策略研究

秦 軍1，馮亮亮2，孫 蒙2

(1.南京郵電大學 教育科學與技術學院，江蘇 南京 210003； 2.南京郵電大學 計算機學院，江蘇 南京 210003)

異構Hadoop環境中，每個節點的處理能力各不相同，且集群中的節點會不斷增加和刪除，隨著作業量的增大，負載傾斜會越來越明顯。顯然，負載均衡也成為影響Hadoop集群性能的重要因素之一。針對異構Hadoop環境中MapReduce任務調度，提出了一種新的負載均衡算法。該算法充分利用節點性能和當前的計算資源，根據集群負載平衡度量值進行任務分配，將任務分配給適合的節點，使集群負載逐漸趨于平衡，以提高集群節點利用率。由于Hadoop集群中各節點通過網絡連接，以節省網絡傳輸代價，因此在負載均衡調度時，根據數據分布特點，優先考慮數據的本地性，以縮短任務執行時間。仿真實驗結果表明，所提出的負載均衡算法能明顯改善系統性能，有效縮短MapReduce作業執行時間。

Hadoop集群；MapReduce；節點性能；任務調度；負載均衡

0 引 言

Hadoop是由Apache基金開發的分布式系統基礎架構[1]。該架構充分利用集群進行高速運算和存儲。作為開源的云計算平臺，已有大量學者加入到Hadoop集群的研究中，并且有許多著名的互聯網公司，例如Facebook、Yahoo、百度、阿里巴巴等利用Hadoop集群進行海量數據的存儲和處理[2]。在大規模的并行計算中，如何充分利用集群的計算資源，提高系統性能，成為負載均衡技術研究的重點[3-4]。

作為Hadoop的核心框架，MapReduce利用分而治之的思想將主節點JobTracker的作業執行分成很多個子任務task[5]，然后交給集群中TaskTracker節點去執行。MapReduce作業執行主要分為map任務和reduce任務。在map階段，接收的輸入，產生的中間結果，將所有鍵值對中key相同的value組成value list傳遞給reduce，reduce階段接收作為輸入，對value集處理后得到,并輸出最終結果[6]。整個作業的完成時間取決于map任務和reduce任務的完成時間之和。在集群節點很多且負載較大時，任務調度會起到關鍵的作用[7]。同構環境下，集群節點之間差異小，任務調度在各節點之間的負載能夠達到較好的平衡[8]。但是實際的Hadoop集群是由大量普通廉價計算機組成[9]，節點處理能力各不相同，隨著負載的增加，集群中負載不平衡會越來越嚴重，導致集群整體吞吐量不高、資源利用率低等問題。從而導致任務處理時間的增加，進而延長了整個作業的執行時間。

因此，為了保持異構Hadoop集群處于負載平衡狀態，在對集群節點進行任務分配時，應該充分考慮節點之間的性能差異和集群當前的負載情況，將任務分配給與其計算能力相應的節點，從而不因局部節點負載過重導致集群負載失衡。仿真實驗結果表明，所提出的負載均衡算法能明顯改善系統性能，有效降低MapReduce的運行時間。

1 相關研究及改進模型

負載均衡問題一直是影響Hadoop集群性能[10]的重要因素之一。通過負載均衡可以使得集群中的節點處于相對的相等忙碌狀態。一個好的負載均衡算法能通過均衡任務來重新分配負載、優化系統的資源利用率和任務的響應時間。

文獻[11]提出了LBVP算法：利用虛擬分區Partition，將map階段處理完成后的輸出數據進行分區，保證各個reduce獲取的數據量基本一致，從而達到負載均衡的目的。該算法對于同構環境下的集群負載均衡效果較好，但對于異構環境下的集群，每個節點處理能力各不相同，即使對于輸入同樣的數據量，其處理效果也會有較大差異。文獻[12]提出了基于節點性能的LBNP負載均衡算法：異構環境下，根據節點性能，解決map階段執行完后的數據預分配問題，從而均衡reduce階段任務的執行時間。該算法考慮了異構環境下節點的性能差異，從局部reduce階段任務調度進行均衡，不能解決在全局MapReduce執行過程中的負載均衡問題。同樣地，文獻[13]結合節點計算能力和數據本地性感知的MapReduce負載均衡也只是針對reduce階段任務調度提出的。

針對上述集群負載均衡中存在的問題，提出了一種改進的任務調度負載均衡模型，如圖1所示。

圖1 任務調度負載均衡模型

圖1中的負載均衡器包括三個模塊：負載均衡度量(Load Balancing，LB)、本地化節點請求隊列和非本地化節點請求隊列。通過對異構環境中TaskTracker節點進行合理的任務調度，保持集群中節點間的負載平衡。其中LB是通過周期地收集TaskTracker節點信息得到的集群負載均衡估量值。按照數據本地性要求，將請求map或reduce任務的TaskTracker節點分為本地化和非本地化請求隊列，并根據當前集群負載均衡度量值LB優先對本地化節點請求隊列中的節點分配任務。由于在每一個心跳周期內，集群性能和請求分配任務的節點是動態變化的，所以負載均衡器所維護的兩個節點請求隊列是基于搶占式優先的。這樣負載均衡器在進行任務調度時是基于當前集群的實時信息進行的，保證了調度的可靠性。

2 算法實現過程

圖1的任務調度負載均衡模型是為了在進行任務調度時，根據當前節點性能和負載均衡度量值將任務分配給與其能力相匹配的節點上，避免超載或饑餓現象，從而使集群的資源得到充分利用。該算法所需要的計算資源和實現步驟如下所述。

2.1 節點性能計算

為了充分反映節點當前性能，應該從多個變量因素進行分析，如CPU利用率、內存利用率、磁盤I/O占用率、網絡帶寬占用率以及執行task任務的響應等。綜合這些因素來反映節點性能。對于節點i(i=1,2,…,n)，其性能計算見式(1)：

(1)

其中，pi表示節點i的性能；pcpu、pio、pmemeory、pbandwidth和presponse分別表示CPU利用率、磁盤I/O占用率、內存利用率、網絡帶寬占用率和單位時間內對task任務的響應速率；r1、r2、r3、r4和r5分別表示各變量在影響節點性能方面所占的比重，根據實際環境來確定，并且r1+r2+r3+r4+r5=1。

2.2 集群整體性能估算

JobTracker周期性地收集TaskTracker通過式(1)計算得到的節點性能，從而得到集群整體的負載狀況。假設集群中含有n個計算節點，每個節點性能為pi(i=1,2,…,n)，計算集群整體平均性能為：

(2)

2.3 節點請求隊列的維護

TaskTracker節點向JobTracker請求分配新的任務時，不僅要保證當前節點運行良好，具有較高的性能，還要保證有足夠的計算資源用于執行task任務。節點i(i=1,2,…,n)當前可以用的計算資源式表示為：

(3)

其中，qi表示當前節點剩余計算資源；qcpu、qio、qmemory、qbandwidth分別表示CPU、磁盤I/O、內存和網絡帶寬的剩余量；k1、k2、k3和k4分別表示各變量所占的比重，并且k1+k2+k3+k4=1。

當有多個節點請求分配任務時，考慮到異構環境中的節點差異，為同樣性能表現的節點，分配相等任務量時，執行任務時間會受到剩余內存和CPU等可用計算資源的限制。因此任務調度器需要綜合當前節點性能和剩余可用計算資源?？捎脙烧叩谋戎祦肀硎荆?/p>

(4)

其中，j表示請求分配任務的節點；Nodej表示作為任務調度器中節點請求隊列排序的標準；pj和qj可分別由式(1)、式(3)計算得到。

考慮到數據本地性，任務調度器會維護兩個節點請求隊列：本地化節點請求隊列和非本地化節點請求隊列，分別用LocalityQueue和nonLocalityQueue來表示。當有多個節點同時請求分配任務時，通過判斷該節點是否含有本地化數據，將其加入到相應的隊列。加入到隊列的節點按照式(4)從大到小進行排序。而且隊列LocalityQueue具有比隊列nonLocalityQueue更高的優先級，即在進行任務調度時，會優先從LocalityQueue隊列中選擇節點來分配任務。

2.4 負載均衡度量

在MapReduce集群大規模的數據計算時，集群負載應該是逐漸趨于平衡的，即大部分節點的計算資源能得到充分利用，節點性能均表現良好，出現節點負載超載或者長期空閑的概率很低。根據概率論中的大數定律和中心極限定理可知，節點性能表現值分布應該近似數學中的正態分布。用X表示集群節點性能值，則X～N(μ,σ2)。其中X即為式(1)中的pi，期望μ為式(2)計算得到的均值，σ2為方差，見式(5)：

(5)

其中，Xi表示節點i(i=1,2,…,n)的性能。

由正態分布3σ準則可知，數據的取值幾乎全部集中在(μ-3σ,μ+3σ)范圍內。對于負載均衡的集群來說，其節點性能值的分布也應遵守3σ準則。這里設定集群負載均衡的范圍為μ-2σμ+2σ的節點，表示節點當前性能很好，處于空閑狀態，可以分配新的任務。假設負載均衡度量為LB=μ-2σ，當節點性能值Xi>LB時均可以分配新的任務。

2.5 任務調度負載均衡算法的實現步驟

在異構環境下，基于集群節點性能和數據本地性的任務調度負載均衡算法的實現步驟如下：

(1)每個心跳周期內，JobTracker收集TaskTracker節點的信息。節點的性能和可用資源的計算根據式(1)、式(3)完成。

(2)當有多個TaskTracker節點發送請求分配新任務的請求時，任務調度器會將含有本地化數據的節點放入到LocalityQueue隊列中，而不含本地化數據的節點放到nonLocalityQueue隊列。并按照式(4)將隊列中的節點從大到小進行排序。

(3)當LocalityQueue隊列非空時，依次取隊列中節點，當節點性能值大于LB時，可以為該節點分配新任務，否則判斷隊列中的下一個節點。

(4)當LocalityQueue為空或者已經遍歷結束時，依次取nonLocalityQueue隊列中的節點，同樣當節點性能值大于LB時，可以為該節點分配新任務，否則判斷隊列中的下一個節點。

(5)重復步驟(1)～(4)。

需要說明的是，在心跳周期內如果有新的節點請求分配任務，則將其按照步驟(2)中的規則加入到相應隊列，可見負載均衡器所維護的節點請求隊列是實時更新并且是基于搶占式優先的。這樣保證了任務分配時，選擇性能和計算資源最好的節點，縮短任務執行時間，并且滿足負載均衡的要求。

3 仿真實驗及結果分析

通過仿真實驗評估改進后的任務調度算法和Hadoop默認的FIFO調度算法[14]的性能表現。實驗中選取10臺在CPU頻率、內存大小等各不相同的物理機器用來模擬異構的集群環境。MapReduce應用作業選擇sort，即對輸入字典中的數據進行排序。作業的大小依次選擇2 G、4 G、6 G、8 G和10 G。在相同輸入數據規模的情況下，分析原有Hadoop框架中FIFO任務調度算法和改進后的任務調度算法在作業完成時間、集群性能和系統吞吐量方面的對比，結果見圖2～4。

圖2 基于作業完成時間的比較

從圖2可以看到，改進后的任務調度執行時間通過更多的執行本地化數據，縮短了任務執行時間，從而加快了整個作業完成時間。

圖3 基于集群性能表現的比較

從圖3可以看到，作業在6 GB左右時，集群平均性能達到了最大，隨著作業規模的增加，負載加大，改進后的集群性能相對于原Hadoop仍然能保持在一個較高水平，可見負載均衡效果得到了明顯的改善。

圖4 基于集群系統吞吐量的對比

從圖4中可以看到，系統的吞吐量增大，這是由于改進后的任務調度算法充分考慮異構環境下的節點差異，通過利用集群中節點計算資源增大了系統吞吐量。

4 結束語

MapReduce中的調度相關問題是影響其執行性能的重要因素之一，負載均衡則是其在調度中需要考慮的因素。在分析節點計算性能的基礎上，提出了一種負載均衡度量新的計算方式，通過與LB的比較，將任務分配給與節點計算能力最匹配的節點，使計算資源得以充分利用，使得集群負載逐漸趨于均衡，增加了系統吞吐量。且在進行負載均衡調度的同時，通過優先調度本地化節點，以減少數據遷移代價和網絡帶寬，縮短了任務的執行時間。仿真實驗結果表明，提出算法顯著提高了系統的綜合性能。

[1] Apache Hadoop[EB/OL].2016-02-13.http://hadoop.apache.org.

[2] 應 毅,劉亞軍.MapReduce并行計算技術發展綜述[J].計算機系統應用,2014,23(4):1-6.

[3] 柳 香,李瑞臺,李俊紅,等.Hadoop性能優化研究[J].河北師范大學學報:自然科學版,2011,35(6):567-570.

[4] 周一可.云計算下MapReduce編程模型可用性的研究與優化[D].上海:上海交通大學,2011.

[5] 孫彥超,王興芬.基于Hadoop框架的MapReduce計算模式的優化設計[J].計算機科學,2014,41(11A):333-336.

[6] Dean J,Ghemawat S.MapReduce:simplified data processing on large clusters[J].Communications of the ACM,2008,51(1):107-113.

[7] 許 丞,劉 洪,譚 良.Hadoop云平臺的一種新的任務調度和監控機制[J].計算機科學,2013,40(1):112-117.

[8] Fan Y,Wu W,Cao H,et al.A heterogeneity-aware data distribution and rebalance method in Hadoop cluster[C]//ChinaGrid annual conference.[s.l.]:IEEE,2012:176-181.

[9] 顧 濤.集群MapReduce環境中任務和作業調度若干關鍵問題的研究[D].天津:南開大學,2014.

[10] 荀亞玲,張繼福,秦 嘯.MapReduce集群環境下的數據放置策略[J].軟件學報,2015,26(8):2056-2073.

[11] Fan Y,Wu W,Cao H,et al.LBVP:a load balance algorithm based on virtual partition in Hadoop cluster[C]//Asia Pacific cloud computing congress.[s.l.]:IEEE,2012:37-41.

[12] Gao Z,Liu D,Yang Y,et al.A load balance algorithm based on nodes performance in Hadoop cluster[C]//16th Asia-Pacific network operations and management symposium.[s.l.]:IEEE,2014:1-4.

[13] 李航晨,秦小麟,沈 堯.數據本地性感知的MapReduce負載均衡策略[J].計算機科學,2015,42(10):50-56.

[14] Tao Y,Zhang Q,Shi L,et al.Job scheduling optimization for multi-user MapReduce clusters[C]//2011 fourth international symposium on parallel architectures,algorithms and programming.[s.l.]:IEEE,2011:213-217.

Research on Load Balancing Strategy with Heterogeneous Hadoop Clustering

QIN Jun1,FENG Liang-liang2,SUN Meng2

(1.College of Education Science & Technology,Nanjing University of Posts and Telecommunications,Nanjing 210003,China; 2.College of Computer,Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

In the heterogeneous Hadoop environment,processing capabilities of the nodes are diverse and various,among which each node may be continuously added or removed in the clustering and its load slope may increase obviously with tasks.Apparently,load balancing is one of the most important factors that affect the performance of Hadoop clustering.Thus a new load balancing algorithm has been proposed and employed in MapReduce task scheduling of the heterogeneous environment,which makes full use of the node performance and current computation resources according to the cluster load balancing measurement value to allocate task to suitable node for balancing the cluster load gradually and promoting coefficient of utilization of cluster nodes.Since the nodes in the Hadoop clustering are connected with network to save the costs of network transmission and the data locality should be considered with priority to decrease execution time for each task according to the characteristics of data distribution during load balancing scheduling.Simulation results show that the proposed load balancing algorithm has improved performances of whole system significantly and shorten the execution time of the MapReduce task.

Hadoop clustering;MapReduce;node performance;task scheduling;load balancing

2016-07-15

2016-10-20 網絡出版時間：2017-04-28

江蘇省自然科學基金項目(BK20130882)

秦 軍(1955-)，女，教授，研究方向為計算機網絡技術、多媒體技術、數據庫技術；馮亮亮(1992-)，女，碩士研究生，研究方向為分布式計算機技術與應用。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170428.1703.070.html

TP301.6

A

1673-629X(2017)06-0110-04

10.3969/j.issn.1673-629X.2017.06.023