秦 軍，馮亮亮，孫 蒙

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

基于異構(gòu)Hadoop集群的負(fù)載均衡策略研究

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

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

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

Hadoop集群；MapReduce；節(jié)點性能；任務(wù)調(diào)度；負(fù)載均衡

0 引 言

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

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

因此，為了保持異構(gòu)Hadoop集群處于負(fù)載平衡狀態(tài)，在對集群節(jié)點進(jìn)行任務(wù)分配時，應(yīng)該充分考慮節(jié)點之間的性能差異和集群當(dāng)前的負(fù)載情況，將任務(wù)分配給與其計算能力相應(yīng)的節(jié)點，從而不因局部節(jié)點負(fù)載過重導(dǎo)致集群負(fù)載失衡。仿真實驗結(jié)果表明，所提出的負(fù)載均衡算法能明顯改善系統(tǒng)性能，有效降低MapReduce的運行時間。

1 相關(guān)研究及改進(jìn)模型

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

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

針對上述集群負(fù)載均衡中存在的問題，提出了一種改進(jìn)的任務(wù)調(diào)度負(fù)載均衡模型，如圖1所示。

圖1 任務(wù)調(diào)度負(fù)載均衡模型

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

2 算法實現(xiàn)過程

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

2.1 節(jié)點性能計算

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

(1)

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

2.2 集群整體性能估算

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

(2)

2.3 節(jié)點請求隊列的維護(hù)

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

(3)

其中，qi表示當(dāng)前節(jié)點剩余計算資源；qcpu、qio、qmemory、qbandwidth分別表示CPU、磁盤I/O、內(nèi)存和網(wǎng)絡(luò)帶寬的剩余量；k1、k2、k3和k4分別表示各變量所占的比重，并且k1+k2+k3+k4=1。

當(dāng)有多個節(jié)點請求分配任務(wù)時，考慮到異構(gòu)環(huán)境中的節(jié)點差異，為同樣性能表現(xiàn)的節(jié)點，分配相等任務(wù)量時，執(zhí)行任務(wù)時間會受到剩余內(nèi)存和CPU等可用計算資源的限制。因此任務(wù)調(diào)度器需要綜合當(dāng)前節(jié)點性能和剩余可用計算資源?？捎脙烧叩谋戎祦肀硎荆?/p>

(4)

其中，j表示請求分配任務(wù)的節(jié)點；Nodej表示作為任務(wù)調(diào)度器中節(jié)點請求隊列排序的標(biāo)準(zhǔn)；pj和qj可分別由式(1)、式(3)計算得到。

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

2.4 負(fù)載均衡度量

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

(5)

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

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

2.5 任務(wù)調(diào)度負(fù)載均衡算法的實現(xiàn)步驟

在異構(gòu)環(huán)境下，基于集群節(jié)點性能和數(shù)據(jù)本地性的任務(wù)調(diào)度負(fù)載均衡算法的實現(xiàn)步驟如下：

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

(2)當(dāng)有多個TaskTracker節(jié)點發(fā)送請求分配新任務(wù)的請求時，任務(wù)調(diào)度器會將含有本地化數(shù)據(jù)的節(jié)點放入到LocalityQueue隊列中，而不含本地化數(shù)據(jù)的節(jié)點放到nonLocalityQueue隊列。并按照式(4)將隊列中的節(jié)點從大到小進(jìn)行排序。

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

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

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

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

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

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

圖2 基于作業(yè)完成時間的比較

從圖2可以看到，改進(jìn)后的任務(wù)調(diào)度執(zhí)行時間通過更多的執(zhí)行本地化數(shù)據(jù)，縮短了任務(wù)執(zhí)行時間，從而加快了整個作業(yè)完成時間。

圖3 基于集群性能表現(xiàn)的比較

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

圖4 基于集群系統(tǒng)吞吐量的對比

從圖4中可以看到，系統(tǒng)的吞吐量增大，這是由于改進(jìn)后的任務(wù)調(diào)度算法充分考慮異構(gòu)環(huán)境下的節(jié)點差異，通過利用集群中節(jié)點計算資源增大了系統(tǒng)吞吐量。

4 結(jié)束語

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

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

[2] 應(yīng) 毅,劉亞軍.MapReduce并行計算技術(shù)發(fā)展綜述[J].計算機(jī)系統(tǒng)應(yīng)用,2014,23(4):1-6.

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

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

[5] 孫彥超,王興芬.基于Hadoop框架的MapReduce計算模式的優(yōu)化設(shè)計[J].計算機(jī)科學(xué),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云平臺的一種新的任務(wù)調(diào)度和監(jiān)控機(jī)制[J].計算機(jī)科學(xué),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環(huán)境中任務(wù)和作業(yè)調(diào)度若干關(guān)鍵問題的研究[D].天津:南開大學(xué),2014.

[10] 荀亞玲,張繼福,秦 嘯.MapReduce集群環(huán)境下的數(shù)據(jù)放置策略[J].軟件學(xué)報,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] 李航晨,秦小麟,沈 堯.數(shù)據(jù)本地性感知的MapReduce負(fù)載均衡策略[J].計算機(jī)科學(xué),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 網(wǎng)絡(luò)出版時間：2017-04-28

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

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

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