張連義 杜中軍 李震

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

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

中圖分類號：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 引言

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

1 Hadoop MapReduce框架

1.1 Hadoop MapReduce概述

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

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

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

Hadoop中的作業(yè)調(diào)度指Job Tracker指派任務（Tasks）到Task Tracker上執(zhí)行的過程?，F(xiàn)有的調(diào)度算法主要有先進先出調(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的負擔，但未考慮作業(yè)的緊迫程度，忽略了不同作業(yè)的需求差異。

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

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

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

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

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

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

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

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

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

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

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

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

⑴

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

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

⑵

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

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

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

2.3 改進算法描述

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

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

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

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

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

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

3 實驗

3.1 實驗環(huán)境

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

3.2 響應時間實驗

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

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

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

3.3 失敗任務測試

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

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

Fail（λ）= ?⑶

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

4 結(jié)束語

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

參考文獻：

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

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

程與科學，2009.31（z1）：5

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

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

半月），2009.2.

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

應用技術(shù)，2012.8.