張連義 杜中軍 李震

摘 ?要： Hadoop MapReduce框架的公平調(diào)度算法以統(tǒng)一的固定配置文件管理計算節(jié)點上計算槽的數(shù)量，這不能保障集群負(fù)載均衡，亦不能滿足不同用戶的資源需求。針對公平調(diào)度算法配置方式的不足，提出一種動態(tài)反饋的調(diào)度算法。該算法結(jié)合公平調(diào)度算法預(yù)先分配的特性，能夠?qū)τ嬎愎?jié)點上的計算槽進(jìn)行動態(tài)調(diào)整。實驗結(jié)果表明，基于動態(tài)反饋的改進(jìn)算法有效地提高了集群的執(zhí)行效率。

關(guān)鍵詞： Hadoop; MapReduce; 公平調(diào)度算法; 動態(tài)反饋

中圖分類號：TP311 ? ? ? ? ?文獻(xiàn)標(biāo)志碼：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 引言

作業(yè)調(diào)度算法是一個集群的核心[1]，其主要功能是分配集群資源和對任務(wù)執(zhí)行順序進(jìn)行有效控制，多以插件的形式集成到Hadoop中[2-3]。當(dāng)前較常用的公平調(diào)度算法（Fair Scheduling）因未考慮計算節(jié)點負(fù)載與任務(wù)失敗率之間的關(guān)系，在多用戶多任務(wù)環(huán)境下易導(dǎo)致資源負(fù)載不均衡，任務(wù)失敗率高。為此提出一種動態(tài)反饋的改進(jìn)算法，通過不斷觀察學(xué)習(xí)任務(wù)執(zhí)行過程中計算資源的占有情況，對計算節(jié)點上的計算槽進(jìn)行動態(tài)調(diào)整，以提高M(jìn)apReduce計算框架的整體性能和集群資源利用率。

1 Hadoop MapReduce框架

1.1 Hadoop MapReduce概述

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

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

1.2 Hadoop MapReduce中的調(diào)度算法

Hadoop中的作業(yè)調(diào)度指Job Tracker指派任務(wù)（Tasks）到Task Tracker上執(zhí)行的過程?，F(xiàn)有的調(diào)度算法主要有先進(jìn)先出調(diào)度算法[4]（FIFO）、計算能力調(diào)度算法（Capacity） 和公平調(diào)度算法（Fair）。

1.2.1 FIFO調(diào)度算法

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

1.2.2 計算能力調(diào)度算法

計算能力調(diào)度算法（Capacity Scheduler）的核心思想是為每一個作業(yè)隊列定義一個指標(biāo)——隊列中正在運行的作業(yè)數(shù)與其應(yīng)該分得的計算資源之間的比值。當(dāng)系統(tǒng)出現(xiàn)空閑的Task Tracker，算法優(yōu)先選擇比值最低的作業(yè)執(zhí)行。計算能力調(diào)度算法必須對用戶數(shù)量進(jìn)行限制，否則將出現(xiàn)多個用戶嚴(yán)重不公平的情況。新作業(yè)運行前，首先考慮作業(yè)所屬用戶是否超出資源限制。

1.2.3 公平調(diào)度算法

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

2 基于動態(tài)反饋策略的改進(jìn)算法

公平調(diào)度算法通過設(shè)置最小資源共享量和公平份額進(jìn)行任務(wù)分配，較適合小作業(yè)的執(zhí)行，但算法未考慮計算節(jié)點負(fù)載與任務(wù)失敗率的關(guān)聯(lián)，以致在多用戶多任務(wù)環(huán)境下，資源負(fù)載不平衡，任務(wù)失敗率高，不利于縮短任務(wù)的執(zhí)行時間和提高系統(tǒng)吞吐量。

2.1 公平調(diào)度算法分析

公平調(diào)度算法通過預(yù)先配置的方式將任務(wù)分配至計算節(jié)點。

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

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

2.2 改進(jìn)算法參數(shù)定義及評價函數(shù)

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

⑴

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

延遲調(diào)度實驗表明，任務(wù)的平均失敗率與節(jié)點的負(fù)載成正比。文獻(xiàn)[5]通過大量實驗對節(jié)點的動態(tài)負(fù)載情況進(jìn)行曲線擬合得到的函數(shù)表達(dá)式為：

⑵

Ej表示計算節(jié)點j的平均失敗率，表示節(jié)點的負(fù)載情況。

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

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

2.3 改進(jìn)算法描述

以下是改進(jìn)的公平調(diào)度算法描述。

⑴ 收集計算節(jié)點資源信息負(fù)載情況，包括CPU使用率、空閑物理內(nèi)存I/O讀寫頻率、網(wǎng)絡(luò)傳輸速率、磁盤剩余空間等。

⑵ 根據(jù)計算節(jié)點的實時負(fù)載值LoadRate判斷：若LoadRate小于LloadRate轉(zhuǎn)向步驟⑶，大于LloadRate并且小于HloadRate轉(zhuǎn)向步驟⑷，大于HloadRate轉(zhuǎn)向步驟⑸。

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

⑷ 計算節(jié)點處于正常負(fù)載，任務(wù)執(zhí)行和資源利用處于最佳狀態(tài)。僅當(dāng)計算節(jié)點中出現(xiàn)空閑slot時，TaskTracker才向JobTracker請求task。

⑸ 計算節(jié)點處于負(fù)載過重狀態(tài)，TaskTracker延遲T1的時間再次計算該節(jié)點的負(fù)載值。若經(jīng)過T1時間計算節(jié)點中出現(xiàn)空閑slot，計算節(jié)點重新計算該節(jié)點的負(fù)載值后決定是否向JobTracker請求task。

3 實驗

3.1 實驗環(huán)境

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

3.2 響應(yīng)時間實驗

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

從實驗結(jié)果可知，基于動態(tài)反饋的公平調(diào)度算法平均任務(wù)完成時間最少，當(dāng)集群中計算節(jié)點出現(xiàn)過載的情況時，備份任務(wù)或出錯任務(wù)都會被重新執(zhí)行，增加了集群資源的利用進(jìn)而減少了作業(yè)完成時間。

圖1 ?三種不同算法響應(yīng)時間對比

3.3 失敗任務(wù)測試

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

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

Fail（λ）= ?⑶

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

4 結(jié)束語

針對公平調(diào)度算法的不足，提出了一種動態(tài)反饋的改進(jìn)調(diào)度算法。但基于動態(tài)反饋策略的評價函數(shù)是不固定的，不同用戶的不同任務(wù)有不同的評價標(biāo)準(zhǔn)。不恰當(dāng)?shù)脑u價函數(shù)可能導(dǎo)致集群資源利用不充分，對于如何根據(jù)任務(wù)及集群資源選擇恰當(dāng)?shù)脑u價函數(shù)是后續(xù)需要解決的問題。

參考文獻(xiàn)：

[1] 張青.網(wǎng)格環(huán)境下任務(wù)調(diào)度算法的應(yīng)用研究[D].大連海事大學(xué)，2009.

[2] 陳全，鄧倩妮.異構(gòu)環(huán)境下自適應(yīng)的Map-Reduce調(diào)度[J].計算機(jī)工

程與科學(xué)，2009.31（z1）：5

[3] 王凱，吳泉源，楊樹強(qiáng).一種多用戶MapReduce集群的作業(yè)調(diào)度算法

的設(shè)計與實現(xiàn)[J].計算機(jī)與現(xiàn)代化，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] 周鋒，李旭偉.一種改進(jìn)的MapReduce并行編程模型[J].科協(xié)論壇（下

半月），2009.2.

[7] 李鑫，張鵬.Hadoop集群公平調(diào)度算法的改進(jìn)與實現(xiàn)[J].計算機(jī)工程

應(yīng)用技術(shù)，2012.8.