Hadoop的負(fù)載均衡調(diào)度算法研究

唐瑋峰 趙振戟

摘要：不斷增大的數(shù)據(jù)規(guī)模給Hadoop集群處理能力帶來了挑戰(zhàn)，而合理的作業(yè)調(diào)度方式與策略能夠提高集群的運(yùn)行效率。通過對(duì)Hadoop MapReduce的任務(wù)調(diào)度機(jī)制進(jìn)行研究，設(shè)計(jì)了節(jié)點(diǎn)負(fù)載能力與動(dòng)態(tài)優(yōu)先級(jí)的計(jì)算方式，提出了一種動(dòng)態(tài)優(yōu)先級(jí)的負(fù)載均衡調(diào)度算法，并搭建小型Hadoop平臺(tái)進(jìn)行了實(shí)驗(yàn)分析。結(jié)果表明，該算法在集群負(fù)載均衡方面的效果要優(yōu)于傳統(tǒng)調(diào)度算法。

關(guān)鍵詞：Hadoop；負(fù)載均衡；MapReduce；調(diào)度算法

DOIDOI：10.11907/rjdk.161358

中圖分類號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2016）005-0047-03

0 引言

Hadoop[1]執(zhí)行MapReduce的過程主要分為Map和Reduce兩個(gè)階段[2]，前者對(duì)數(shù)據(jù)進(jìn)行劃分和鍵值對(duì)處理，后者對(duì)劃分后的數(shù)據(jù)片進(jìn)行規(guī)約計(jì)算。然而Reducer所處理的數(shù)據(jù)是根據(jù)數(shù)據(jù)片的Key值分配的，由于數(shù)據(jù)本身特點(diǎn)的不確定性，Key值的分布通常不均衡，從而導(dǎo)致Reducer分配到的數(shù)據(jù)量與資源也容易出現(xiàn)不均衡狀況，在數(shù)據(jù)量較大的情況下會(huì)嚴(yán)重影響MapReduce的任務(wù)處理效率[3]。

針對(duì)該問題，本文通過研究Hadoop的任務(wù)調(diào)度原理，結(jié)合相關(guān)負(fù)載均衡調(diào)度算法，提出了一種新的動(dòng)態(tài)優(yōu)先級(jí)負(fù)載均衡算法（DPLB），實(shí)現(xiàn)集群作業(yè)的動(dòng)態(tài)負(fù)載，提高了Hadoop集群的資源利用率和系統(tǒng)響應(yīng)速度。

1 MapReduce在Hadoop上的任務(wù)調(diào)度

Hadoop MapReduce的任務(wù)調(diào)度主要由JobTracker和TaskTracker兩個(gè)進(jìn)程來完成。JobTracker的作用是作業(yè)控制、狀態(tài)監(jiān)控以及資源管理，TaskTracker的作用是執(zhí)行JobTracker下達(dá)的命令，并且周期性地將節(jié)點(diǎn)資源使用情況以及任務(wù)運(yùn)行狀態(tài)等信息通過心跳機(jī)制[4]匯報(bào)給JobTracker。Hadoop MapReduce的任務(wù)執(zhí)行過程如圖1所示。

在作業(yè)調(diào)度過程中，當(dāng)一個(gè)Maptask完成之后并不會(huì)主動(dòng)將輸出的數(shù)據(jù)發(fā)送給Reducer，而是由Reducetask通過向JobTracker詢問自身的節(jié)點(diǎn)狀態(tài)是否能接受工作任務(wù)，得到JobTracker允許后會(huì)通過http協(xié)議從完成的Maptask獲取屬于自己的數(shù)據(jù)塊，并根據(jù)Key值進(jìn)行排序，最后調(diào)用用戶定義的Reduce函數(shù)進(jìn)行處理并輸出結(jié)果。合理的調(diào)度算法能夠更充分地利用集群中的TaskTracker，提高集群的并行處理效率。

2 常用Hadoop作業(yè)調(diào)度算法

2.1 FIFO調(diào)度算法

FIFO調(diào)度算法[5]通過單隊(duì)列結(jié)構(gòu)來存放提交的作業(yè)，新到達(dá)的作業(yè)排在隊(duì)列尾，隊(duì)列頭部的作業(yè)擁有最高的執(zhí)行優(yōu)先級(jí)。該算法的缺點(diǎn)是不利于多作業(yè)的并行執(zhí)行，另外時(shí)間先后優(yōu)先級(jí)的方式?jīng)]有考慮作業(yè)之間的差異性，容易導(dǎo)致小作業(yè)的長時(shí)間等待，無法充分利用系統(tǒng)資源。

2.2 Capacity Scheduler調(diào)度算法

基于容量的調(diào)度[6]算法采用多隊(duì)列結(jié)構(gòu)，每個(gè)隊(duì)列配置一定比例的資源，當(dāng)JobTracker接到一個(gè)作業(yè)時(shí)，會(huì)對(duì)各隊(duì)列當(dāng)前可用資源比重進(jìn)行比較，將作業(yè)分配給可用資源最多的隊(duì)列。Capacity Scheduler算法靈活性較好，但在隊(duì)列的資源配置上依賴經(jīng)驗(yàn)設(shè)置，管理難度較大。

2.3 Fair Scheduler 調(diào)度算法

公平調(diào)度算法[7]也采用多隊(duì)列結(jié)構(gòu)，不同的是該算法為每個(gè)用戶配置了一個(gè)資源池，不管提交的作業(yè)有多少都能夠保證每個(gè)用戶分得均等的資源，并且允許每個(gè)資源池選擇自己的調(diào)度方式。但該算法在分配資源池之前需要針對(duì)不同用戶的數(shù)據(jù)特性做出不同的參數(shù)配置策略，因而在異構(gòu)集群情況下的管理會(huì)變得十分復(fù)雜。

3 動(dòng)態(tài)優(yōu)先級(jí)負(fù)載均衡調(diào)度算法（DPLB）

3.1 算法思想

針對(duì)傳統(tǒng)Hadoop集群調(diào)度算法的不足，提出DPLB（Dynamic Priority Load Balance，動(dòng)態(tài)優(yōu)先級(jí)負(fù)載均衡）算法。該算法利用TaskTracker周期性反饋的心跳信息計(jì)算節(jié)點(diǎn)負(fù)載情況與隊(duì)列的任務(wù)承擔(dān)能力，結(jié)合作業(yè)在隊(duì)列中的等待時(shí)間與作業(yè)規(guī)模設(shè)計(jì)一種動(dòng)態(tài)優(yōu)先級(jí)，使小作業(yè)的等待時(shí)間減少，提高調(diào)度效率。

3.2 算法相關(guān)定義

3.2.1 節(jié)點(diǎn)負(fù)載能力NL與隊(duì)列承載能力QL

其中，Twait表示作業(yè)在隊(duì)列中的等待時(shí)間，Tres表示作業(yè)需要的資源量，由式（3）可以看出，作業(yè)的優(yōu)先級(jí)會(huì)隨著在隊(duì)列中等待時(shí)間的增加而提高，同時(shí)考慮到了小作業(yè)優(yōu)先執(zhí)行的情況，作業(yè)需求的資源比越小，則優(yōu)先級(jí)越高。

3.3 算法描述

基于心跳反饋的Hadoop動(dòng)態(tài)負(fù)載均衡調(diào)度算法描述如下：

Step1：計(jì)算隊(duì)列承載能力QL與當(dāng)前并行的作業(yè)數(shù)TaskNum，若TaskNum達(dá)到最大并行作業(yè)數(shù)maxTask則轉(zhuǎn)到Step10，否則轉(zhuǎn)到Step2；

Step2：JobTracker將作業(yè)放入QL值最大的隊(duì)列中；

Step3：遍歷隊(duì)列，根據(jù)Pri優(yōu)先級(jí)進(jìn)行作業(yè)排序；

Step4：計(jì)算各健康節(jié)點(diǎn)的負(fù)載能力NL，選出NL最高的健康節(jié)點(diǎn)；

Step5：判斷該節(jié)點(diǎn)是否滿足隊(duì)列中一個(gè)作業(yè)的執(zhí)行資源需求，滿足則轉(zhuǎn)Step6，否則轉(zhuǎn)到Step9；

Step6：檢查該節(jié)點(diǎn)的TaskTracker啟動(dòng)記錄與任務(wù)失敗記錄，判斷該節(jié)點(diǎn)是否健康，狀態(tài)為true則轉(zhuǎn)Step7，為false則轉(zhuǎn)Step8；

Step7：將該節(jié)點(diǎn)的資源分配給該作業(yè)，轉(zhuǎn)到Step1；

Step8：將該節(jié)點(diǎn)的健康狀態(tài)標(biāo)記為false，轉(zhuǎn)到Step4；

Step9：將該作業(yè)轉(zhuǎn)移至其它隊(duì)列，轉(zhuǎn)到Step3；

Step10：JobTask停止作業(yè)調(diào)度，算法結(jié)束。

過多的并行作業(yè)數(shù)量會(huì)對(duì)JobTracker造成很大負(fù)擔(dān)，因此當(dāng)并行的作業(yè)數(shù)量達(dá)到maxNum時(shí)會(huì)終止調(diào)度算法。另外，節(jié)點(diǎn)的健康與否主要由該節(jié)點(diǎn)執(zhí)行上一個(gè)作業(yè)的失敗次數(shù)來判斷，若JobTracker檢測(cè)到該節(jié)點(diǎn)在執(zhí)行同一個(gè)任務(wù)時(shí)失敗多次，則會(huì)將其標(biāo)記為非健康節(jié)點(diǎn)，暫時(shí)脫離集群工作，直到管理員對(duì)該節(jié)點(diǎn)進(jìn)行修復(fù)后將其重新分配給隊(duì)列。

4 仿真實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)環(huán)境與數(shù)據(jù)

根據(jù)實(shí)驗(yàn)室條件與設(shè)備情況，采用虛擬機(jī)搭建了4個(gè)節(jié)點(diǎn)的Hadoop集群，其中一個(gè)節(jié)點(diǎn)作為Master，其余3個(gè)節(jié)點(diǎn)作為Slave。為了體現(xiàn)異構(gòu)環(huán)境，其中兩臺(tái)Slave虛擬主機(jī)配置為AMD單核CPU，主頻2.9Gz，內(nèi)存512M，硬盤大小為64G，另一臺(tái)Slave與Master配置均為AMD雙核CPU，主頻2.9Gz，內(nèi)存1G，系統(tǒng)采用Linux Redhat9.0，Hadoop版本為Hadoop1.2，代碼編譯采用Java jdk1.6.0_24。實(shí)驗(yàn)數(shù)據(jù)使用路透社的14 578條新聞集數(shù)據(jù)，在集群上運(yùn)行K-均值聚類算法，聚類中心數(shù)設(shè)為200[8]。

4.2 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)使用DPLB算法與常用的3種Hadoop調(diào)度算法分別進(jìn)行不同數(shù)據(jù)規(guī)模下的聚類分析，通過記錄不同調(diào)度方式下的運(yùn)行時(shí)間與節(jié)點(diǎn)負(fù)載情況來分析算法對(duì)Hadoop集群負(fù)載均衡的效果，結(jié)果如圖2、圖3所示。

從圖2可以看出，DPLB算法在Hadoop作業(yè)執(zhí)行的效率上與公平調(diào)度算法相當(dāng)，但要優(yōu)于FIFO算法與基于容量的調(diào)度算法。而在集群節(jié)點(diǎn)的負(fù)載均衡方面，DPLB算法取得了很好的效果。圖3結(jié)果顯示，DPLB算法在作業(yè)執(zhí)行過程中對(duì)資源的占有量較高，究其原因在于實(shí)驗(yàn)中采用的數(shù)據(jù)集是條目較多的小文件，在DPLB的小作業(yè)相對(duì)優(yōu)先的調(diào)度模式中使得并行的作業(yè)數(shù)增多，增加了節(jié)點(diǎn)壓力，但在作業(yè)執(zhí)行的整體效率上有明顯提升。

5 結(jié)語

本文針對(duì)傳統(tǒng)Hadoop作業(yè)調(diào)度模式可能出現(xiàn)的節(jié)點(diǎn)負(fù)載不均衡，以及資源利用率不高等問題，提出了一種動(dòng)態(tài)優(yōu)先級(jí)的負(fù)載均衡調(diào)度算法DPLB，通過實(shí)驗(yàn)證明了該算法在Hadoop集群作業(yè)的執(zhí)行效率上要高于傳統(tǒng)調(diào)度算法，并且能夠有效實(shí)現(xiàn)集群節(jié)點(diǎn)的負(fù)載均衡。該算法在節(jié)點(diǎn)負(fù)載優(yōu)化方面還有很大提升空間，后續(xù)將在此基礎(chǔ)上重點(diǎn)研究如何降低TaskTracker的通信開銷。

參考文獻(xiàn)：

[1]WHITE T.Hadoop：the definitive guide[M].O'Reilly，2012.

[2]DEAN B J.Mapreduce：simplified data processing on large clusters[J].Osdi，2010， 51（1）：107-113.

[3]萬聰，王翠榮，王聰，等.MapReduce模型中reduce階段負(fù)載均衡分區(qū)算法研究[J].小型微型計(jì)算機(jī)系統(tǒng)，2015（2）：240-243.

[4]關(guān)國棟，滕飛，楊燕.基于心跳超時(shí)機(jī)制的Hadoop實(shí)時(shí)容錯(cuò)技術(shù)[J].計(jì)算機(jī)應(yīng)用，2015，35（10）：2784-2788.

[5]王峰.Hadoop集群作業(yè)的調(diào)度算法[J].程序員，2009（12）：119-121.

[6]CHEN H，CUI D.SLa-based hadoop capacity scheduler algorithm[C].2015 International Conference on Electronic Science and Automation Control，2015.

[7]潘旭明.Map Reduce Fair Scheduler的高性能優(yōu)化及超大規(guī)模集群模擬器設(shè)計(jì)及實(shí)現(xiàn)[D].杭州：浙江大學(xué)，2012.

[8]趙衛(wèi)中，馬慧芳，傅燕翔，等.基于云計(jì)算平臺(tái)Hadoop的并行K-means聚類算法設(shè)計(jì)研究[J].計(jì)算機(jī)科學(xué)，2011，38（10）：166-168.

（責(zé)任編輯：孫 娟）