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

唐瑋峰 趙振戟

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

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

DOIDOI：10.11907/rjdk.161358

中圖分類號：TP312

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

0 引言

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

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

1 MapReduce在Hadoop上的任務調度

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

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

2 常用Hadoop作業調度算法

2.1 FIFO調度算法

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

2.2 Capacity Scheduler調度算法

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

2.3 Fair Scheduler 調度算法

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

3 動態優先級負載均衡調度算法（DPLB）

3.1 算法思想

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

3.2 算法相關定義

3.2.1 節點負載能力NL與隊列承載能力QL

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

3.3 算法描述

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

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

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

Step3：遍歷隊列，根據Pri優先級進行作業排序；

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

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

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

Step7：將該節點的資源分配給該作業，轉到Step1；

Step8：將該節點的健康狀態標記為false，轉到Step4；

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

Step10：JobTask停止作業調度，算法結束。

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

4 仿真實驗結果與分析

4.1 實驗環境與數據

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

4.2 實驗結果與分析

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

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

5 結語

本文針對傳統Hadoop作業調度模式可能出現的節點負載不均衡，以及資源利用率不高等問題，提出了一種動態優先級的負載均衡調度算法DPLB，通過實驗證明了該算法在Hadoop集群作業的執行效率上要高于傳統調度算法，并且能夠有效實現集群節點的負載均衡。該算法在節點負載優化方面還有很大提升空間，后續將在此基礎上重點研究如何降低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階段負載均衡分區算法研究[J].小型微型計算機系統，2015（2）：240-243.

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

[5]王峰.Hadoop集群作業的調度算法[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的高性能優化及超大規模集群模擬器設計及實現[D].杭州：浙江大學，2012.

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

（責任編輯：孫 娟）