Hadoop的負載均衡調度算法研究

唐瑋峰 趙振戟

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

關鍵詞：Hadoop；負載均衡；MapReduce；調度算法

DOIDOI：10.11907/rjdk.161358

中圖分類號：TP312

文獻標識碼：A 文章編號：1672-7800（2016）005-0047-03

0 引言

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

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

1 MapReduce在Hadoop上的任務調度

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

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

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

2.1 FIFO調度算法

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

2.2 Capacity Scheduler調度算法

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

2.3 Fair Scheduler 調度算法

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

3 動態(tài)優(yōu)先級負載均衡調度算法（DPLB）

3.1 算法思想

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

3.2 算法相關定義

3.2.1 節(jié)點負載能力NL與隊列承載能力QL

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

3.3 算法描述

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

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

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

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

Step4：計算各健康節(jié)點的負載能力NL，選出NL最高的健康節(jié)點；

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

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

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

Step8：將該節(jié)點的健康狀態(tài)標記為false，轉到Step4；

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

Step10：JobTask停止作業(yè)調度，算法結束。

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

4 仿真實驗結果與分析

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

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

4.2 實驗結果與分析

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

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

5 結語

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

參考文獻：

[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階段負載均衡分區(qū)算法研究[J].小型微型計算機系統(tǒng)，2015（2）：240-243.

[4]關國棟，滕飛，楊燕.基于心跳超時機制的Hadoop實時容錯技術[J].計算機應用，2015，35（10）：2784-2788.

[5]王峰.Hadoop集群作業(yè)的調度算法[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ī)模集群模擬器設計及實現(xiàn)[D].杭州：浙江大學，2012.

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

（責任編輯：孫 娟）