Hadoop平臺公平調度算法研究與優化

張連義 杜中軍 李震

摘 ?要： Hadoop MapReduce框架的公平調度算法以統一的固定配置文件管理計算節點上計算槽的數量，這不能保障集群負載均衡，亦不能滿足不同用戶的資源需求。針對公平調度算法配置方式的不足，提出一種動態反饋的調度算法。該算法結合公平調度算法預先分配的特性，能夠對計算節點上的計算槽進行動態調整。實驗結果表明，基于動態反饋的改進算法有效地提高了集群的執行效率。

關鍵詞： Hadoop; MapReduce; 公平調度算法; 動態反饋

中圖分類號：TP311 ? ? ? ? ?文獻標志碼：A ? ? 文章編號：1006-8228（2014）12-45-03

Research and improve of fair scheduling algorithms based on Hadoop platform

Zhang Lianyi， Du Zhongjun， Li Zhen

（Sichuan university， college of computer science， Chengdu， Sichuan 610065， China）

Abstract： Unified fixed configuration file is utilized in fair scheduling algorithm of the Hadoop MapReduce framework to calculate the number of slots in computing nodes. It cant guarantee the load balancing cluster especially in heterogeneous environment and satisfy the different requirement on the resource of different users. Aiming at the shortcomings of the existing configuration ways in fair scheduling algorithm， a dynamic feedback scheduling algorithm is proposed. Combined with the characteristics of pre-allocated algorithm， the computing nodes on the slots can be adjusted dynamically. The experimental results shows that the improved algorithm based on dynamic feedback can efficiently improve the execution efficiency of the cluster.

Key words： Hadoop; MapReduce; fair scheduling; dynamic feedback

0 引言

作業調度算法是一個集群的核心[1]，其主要功能是分配集群資源和對任務執行順序進行有效控制，多以插件的形式集成到Hadoop中[2-3]。當前較常用的公平調度算法（Fair Scheduling）因未考慮計算節點負載與任務失敗率之間的關系，在多用戶多任務環境下易導致資源負載不均衡，任務失敗率高。為此提出一種動態反饋的改進算法，通過不斷觀察學習任務執行過程中計算資源的占有情況，對計算節點上的計算槽進行動態調整，以提高MapReduce計算框架的整體性能和集群資源利用率。

1 Hadoop MapReduce框架

1.1 Hadoop MapReduce概述

Hadoop MapReduce是一種處理海量數據的并行編程模型，用戶選擇自定義的Map函數和Reduce函數即可并行處理海量數據。

Hadoop MapReduce將分布式計算形象的描述為key/value鍵值對，以鍵值對的形式在集群中進行操作。MapReduce運算包括Map和Reduce兩個過程。Map階段計算節點從輸入數據塊中提取key/value鍵值對，傳遞給自定義的Map函數，由Map函數來產生中間key/value鍵值對。通過哈希函數將鍵值對分成R份并寫入本地磁盤。Reduce階段對Map函數產生的中間鍵值對進行規約，Reduce函數從遠端復制對應的key/value，并依據key進行value排序、結果合并、數據塊輸出。

1.2 Hadoop MapReduce中的調度算法

Hadoop中的作業調度指Job Tracker指派任務（Tasks）到Task Tracker上執行的過程。現有的調度算法主要有先進先出調度算法[4]（FIFO）、計算能力調度算法（Capacity） 和公平調度算法（Fair）。

1.2.1 FIFO調度算法

FIFO調度算法（First In First Out）是最早出現在Hadoop MapReduce計算框架中的調度算法。所有用戶的作業都提交到一個隊列中，由Job Tracker依此按照作業的優先級和提交時間控制作業的執行順序。FIFO調度算法簡單方便，易于實現，減輕了JobTracker的負擔，但未考慮作業的緊迫程度，忽略了不同作業的需求差異。

1.2.2 計算能力調度算法

計算能力調度算法（Capacity Scheduler）的核心思想是為每一個作業隊列定義一個指標——隊列中正在運行的作業數與其應該分得的計算資源之間的比值。當系統出現空閑的Task Tracker，算法優先選擇比值最低的作業執行。計算能力調度算法必須對用戶數量進行限制，否則將出現多個用戶嚴重不公平的情況。新作業運行前，首先考慮作業所屬用戶是否超出資源限制。

1.2.3 公平調度算法

公平調度算法是Facebook提出的一種調度算法。公平調度的目的是讓所有作業能獲取等同的共享資源。一個作業單獨運行將使用整個集群，其他作業提交時，系統將任務空閑時間片（Slot）賦給新的作業，以使每一個作業獲取到等量的CPU時間。公平調度器按資源池（Pool）來組織作業，并把資源公平的分到資源池里。默認每一個用戶擁有一個獨立的資源池，以保障無論用戶提交多少作業都能獲得等同的集群資源。

2 基于動態反饋策略的改進算法

公平調度算法通過設置最小資源共享量和公平份額進行任務分配，較適合小作業的執行，但算法未考慮計算節點負載與任務失敗率的關聯，以致在多用戶多任務環境下，資源負載不平衡，任務失敗率高，不利于縮短任務的執行時間和提高系統吞吐量。

2.1 公平調度算法分析

公平調度算法通過預先配置的方式將任務分配至計算節點。

首先，集群管理員需配置計算節點最大slot，若slot配置過高，將導致資源間競爭激烈，備份任務和失敗任務增多;若slot配置的過低，將導致資源利用率過低，集群性能無法充分發揮。對集群尤其是存在大量異構計算節點的集群，配置合理的slot數難于把握。

其次，分配到計算節點上的task所消耗的計算資源各不相同，有些CPU占用率高，有些內存消耗大，有些I/O繁忙，而大部分task混合使用資源。如何在多用戶多任務情況下合理分配資源，既要滿足不同用戶資源需求，又能保障集群特別是異構環境下的集群負載均衡？本文提出一種動態反饋的調度算法，算法結合公平調度算法預先分配的特性，通過不斷觀察學習任務執行過程中計算資源的占有情況決定TaskTracker向JobTracker請求任務的時間。

2.2 改進算法參數定義及評價函數

在異構集群環境中，R={r1…rj… rn}表示計算節點（rj表示第j個計算節點，集群中共有n個計算節點）。L={l1…lj…ln}表示節點的負載值（lj表示計算節點rj的負載值）。節點rj上CPU使用率、內存利用率、I/O吞吐量分別為C%、M%、I%，則計算節點rj的動態負載值lj可以表示為：

⑴

其中λn表示各參數的重要性，j=1，2，…，m，m值為3時，。

延遲調度實驗表明，任務的平均失敗率與節點的負載成正比。文獻[5]通過大量實驗對節點的動態負載情況進行曲線擬合得到的函數表達式為：

⑵

Ej表示計算節點j的平均失敗率，表示節點的負載情況。

以LloadRate表示負載輕度值， HloadRate表示負載重度值。計算節點周期性收集CPU，MEM，I/O等信息，根據公式2計算負載值LoadRate，通過LoadRate與HloadRate和LloadRate值的比較決定是否向JobTracker發送task申請。

當LoadRate=LloadRate并且LoadRate<=HloadRate時，只有存在空閑slot，計算節點才向JobTracker請求task;當LoadRate>HloadRate時，節點負載過重，如果TaskTracker繼續向JobTracker請求task，將造成計算節點上存在慢任務，甚至出現錯誤任務。此時若出現空閑slot，延遲T1時間TaskTracker向JobTracker請求task。

2.3 改進算法描述

以下是改進的公平調度算法描述。

⑴ 收集計算節點資源信息負載情況，包括CPU使用率、空閑物理內存I/O讀寫頻率、網絡傳輸速率、磁盤剩余空間等。

⑵ 根據計算節點的實時負載值LoadRate判斷：若LoadRate小于LloadRate轉向步驟⑶，大于LloadRate并且小于HloadRate轉向步驟⑷，大于HloadRate轉向步驟⑸。

⑶ 計算節點部分資源處于空閑狀態，無論計算節點是否出現空閑slot， TaskTracker都以心跳的形式向JobTracker請求一個task 。

⑷ 計算節點處于正常負載，任務執行和資源利用處于最佳狀態。僅當計算節點中出現空閑slot時，TaskTracker才向JobTracker請求task。

⑸ 計算節點處于負載過重狀態，TaskTracker延遲T1的時間再次計算該節點的負載值。若經過T1時間計算節點中出現空閑slot，計算節點重新計算該節點的負載值后決定是否向JobTracker請求task。

3 實驗

3.1 實驗環境

四臺計算機通過一臺普通路由器連接，操作系統為redhat-server-6.0-i386，java jdk版本1.6.0_17，hadoop版本hadoop-1.0.4，開發工具：MyEclipse8.5。

3.2 響應時間實驗

對先進先出調度算法（FIFO）、公平調度算法（FS）、基于動態反饋的公平調度算法（DFFS）進行測試。測試程序采用hadoop提供的基準測試程序，選擇GrepCount、TeraSort和WordCount作為測試用例。在三種算法中分別進行GrepCount、TeraSort和WordCount應用運行程序10次，實驗統計完成時間如圖1所示。

從實驗結果可知，基于動態反饋的公平調度算法平均任務完成時間最少，當集群中計算節點出現過載的情況時，備份任務或出錯任務都會被重新執行，增加了集群資源的利用進而減少了作業完成時間。

圖1 ?三種不同算法響應時間對比

3.3 失敗任務測試

圖2 ?三種不同算法在不同負載情況下的任務失敗率

定義失敗任務為fail，超時任務數量為TimeoutNum，失敗任務數量為ErrorNum，集群中任務總數為SumNum，超時任務影響因子為λ1，失敗任務的影響因子為λ2，這里λ1、λ2的取值分別為0.5、1.0。則任務失敗率Fail（λ）可以表示為公式⑶。

Fail（λ）= ?⑶

失敗任務測試結果如圖2所示，實驗結果表明，節點負載率小于30%時，三種算法任務失敗率接近。當節點負載超過30%時，基于動態反饋的公平調度算法在高負載的情況下自動調節計算節點上計算槽的數目，保障了計算槽上的任務有資源可用，任務失敗率明顯低于其他兩種算法。

4 結束語

針對公平調度算法的不足，提出了一種動態反饋的改進調度算法。但基于動態反饋策略的評價函數是不固定的，不同用戶的不同任務有不同的評價標準。不恰當的評價函數可能導致集群資源利用不充分，對于如何根據任務及集群資源選擇恰當的評價函數是后續需要解決的問題。

參考文獻：

[1] 張青.網格環境下任務調度算法的應用研究[D].大連海事大學，2009.

[2] 陳全，鄧倩妮.異構環境下自適應的Map-Reduce調度[J].計算機工

程與科學，2009.31（z1）：5

[3] 王凱，吳泉源，楊樹強.一種多用戶MapReduce集群的作業調度算法

的設計與實現[J].計算機與現代化，2010.10.

[4] Bryant R E. Data-Intensive Supercomputing： the Case forDISC[R].

CMU Technical Report CMU-CS-07-128，Depart-ment of Computer Science， Carnegie Mellon University，2007.

[5] CHERKASOVA L. Performance modeling in mapreduce environ-

ments [C]// Proceeding of the second joint WOSP/SIPEW international conference on Performance engineering： March 14-16， 2011. Karlsruhe， Germany. NY， USA： ACM press，2011：5-6

[6] 周鋒，李旭偉.一種改進的MapReduce并行編程模型[J].科協論壇（下

半月），2009.2.

[7] 李鑫，張鵬.Hadoop集群公平調度算法的改進與實現[J].計算機工程

應用技術，2012.8.