戴小平，張宜力

DAI Xiaoping,ZHANG Yili

安徽工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，安徽 馬鞍山243002

Computer Science School,Anhui University of Technology,Ma’anshan,Anhui 243002,China E-mail：jszhangyili@163.com

1 引言

云計(jì)算是一種新的計(jì)算模型，是隨著并行計(jì)算、分布式計(jì)算和網(wǎng)格計(jì)算技術(shù)的發(fā)展而來的，在學(xué)術(shù)界和工業(yè)界產(chǎn)生了巨大的影響，Google、Amazon、Microsoft 等大公司是云計(jì)算的先行者[1]在眾多的云計(jì)算解決方案中，Google提出的基于分布式文件系統(tǒng)GFS 建立的廉價集群實(shí)現(xiàn)MapReduce 編程思想[2-3]的方案因其應(yīng)用簡單、高效的特點(diǎn)得到了廣泛支持，解決了許多大規(guī)模數(shù)據(jù)的計(jì)算問題。而Hadoop 作為Google 相關(guān)思想開源實(shí)現(xiàn)的一個分布式系統(tǒng)，除了成本少，有較高的效率和伸縮性外，安全性也得到了很好的保障[4-5]。

Hadoop 平臺中作業(yè)調(diào)度器對平臺性能至關(guān)重要，作業(yè)調(diào)度技術(shù)作為Hadoop 平臺的核心技術(shù)之一，不僅對Hadoop 平臺的整體性能有影響，還對系統(tǒng)資源是否有效利用起到了至關(guān)重要的作用。但是目前的幾種作業(yè)調(diào)度算法都存著資源浪費(fèi)，作業(yè)響應(yīng)時間過長，沒有考慮作業(yè)配置及不能夠滿足作業(yè)多樣性的服務(wù)要求等缺點(diǎn)[6]。

本文基于計(jì)算能力調(diào)度算法實(shí)現(xiàn)了一種基于優(yōu)先級的計(jì)算能力加權(quán)調(diào)度算法，能夠有效地解決目前Hadoop的作業(yè)調(diào)度算法中存在的一些問題，并在Hadoop平臺的實(shí)驗(yàn)中表現(xiàn)良好。

2 MapReduce編程思想

MapReduce是Google公司的核心計(jì)算模型，它將復(fù)雜的運(yùn)行于大規(guī)模集群上的并行計(jì)算過程高度地抽象到了兩個函數(shù)：Map（映射）和Reduce（歸約）。簡單的MapReduce 的過程如圖1 所示，MapReduce 首先將用 戶輸入的數(shù)據(jù)通過Split 方法將其分成若干Block（每個Block的默認(rèn)大小為64 MB，每一個Block由一個Mapper管理，在整個MapReduce 中Reducer 是通過配置來得到的，而Mapper 的數(shù)量則是由Block 的數(shù)量來決定）每一個Mapper 將運(yùn)行在該Block 所在的本機(jī)中，所有的臨時數(shù)據(jù)和中間數(shù)據(jù)也都會存儲在本機(jī)中，當(dāng)所有的Mapper運(yùn)行完成后，Reducer 便會開始運(yùn)行，將所有Mapper 的輸出作為它的輸入，最后將結(jié)果輸出到GFS 中[7]。

圖1 給出了MapReduce 執(zhí)行過程，分為Map 階段以及Reduce 階段，這兩個階段都使用了集群中的所有節(jié)點(diǎn)。在這兩個階段之間還有一個中間的分類階段，即將中間結(jié)果包含相同Key 交給同一個Reduce 函數(shù)去執(zhí)行。MapReduce操作相關(guān)的類型如下：

map(keyin,valuein)→list(keyout,valueintermediate)

reduce(keyout,list(valueintermediate))→list(valueout)

圖1 Google MapReduce執(zhí)行過程

3 Hadoop 的作業(yè)調(diào)度算法

Hadoop的調(diào)度器旨在調(diào)度各種提交到Hadoop的作業(yè)，使作業(yè)有個合理的執(zhí)行順序。它不僅要對作業(yè)進(jìn)行調(diào)度，提高系統(tǒng)的吞吐量，使系統(tǒng)處理盡可能多的作業(yè)，提高執(zhí)行效率，而且還要考慮系統(tǒng)的利用率，不使系統(tǒng)空閑下來，另外還得兼顧用戶的感受提高作業(yè)響應(yīng)時間。

早期Hadoop 的作業(yè)調(diào)度算法按照作業(yè)提交順序來運(yùn)行，使用的就是FIFO 調(diào)度算法。后來FaceBook 和Yahoo分別提設(shè)計(jì)了公平調(diào)度算法，計(jì)算能力調(diào)度算法。

公平調(diào)度算法目的是能夠滿足多用戶多類型作業(yè)的并行運(yùn)行[8]。該算法的設(shè)計(jì)思想是讓所有的作業(yè)隨著時間的推移，都能平均獲取等同的共享資源。算法以池的形式管理作業(yè)，默認(rèn)情況下每個用戶都有一個獨(dú)立的作業(yè)池，用戶能獲得相等份額的資源而不管用戶提交了多少作業(yè)。在公平調(diào)度算法的具體實(shí)現(xiàn)中，為了選擇合適的作業(yè)執(zhí)行，公平調(diào)度算法還定義了作業(yè)赤字作為選擇依據(jù)，即一個作業(yè)在理想情況下應(yīng)該獲得的計(jì)算資源量與它實(shí)際獲得的計(jì)算資源了之間的差距。公平調(diào)度算法會周期性地觀察各個作業(yè)中有多少任務(wù)已經(jīng)在上一時間段內(nèi)執(zhí)行，并將該結(jié)果與它應(yīng)得的資源份額作對比更新該作業(yè)的赤字值。一旦有空閑的TaskTracker 出現(xiàn)，它會被首先分配給當(dāng)前具有最高赤字的作業(yè)使用。

計(jì)算能力調(diào)度算法[9]中可以定義多個隊(duì)列，當(dāng)用戶提交了一個作業(yè)，該作業(yè)會被放到一個隊(duì)列中。各個隊(duì)列根據(jù)配置文件分配到相應(yīng)數(shù)量的TaskTracker 資源用于處理Map 操作和Reduce 操作。當(dāng)系統(tǒng)中出現(xiàn)了空閑的TaskTracker，算法會首先選擇一個具有最多空閑空間的隊(duì)列。當(dāng)一個隊(duì)列被選中時，調(diào)度器就會根據(jù)該隊(duì)列中作業(yè)的優(yōu)先級和提交時間進(jìn)行選擇合適的作業(yè)。計(jì)算能力調(diào)度算法雖然吸取了公平算法的不足，根據(jù)作業(yè)的性能分配資源，但這種分配策略過于簡單，容易陷入局部最優(yōu)，同時該算法配置起來也是比較繁瑣的，而且對服務(wù)水平協(xié)議也不能很好的支持。

在Hadoop 中作業(yè)調(diào)度器是一個可以插拔的模塊，因此針對Hadoop 現(xiàn)存調(diào)度器存在的問題，以及根據(jù)自己的實(shí)際應(yīng)用要求修改或者重新設(shè)計(jì)調(diào)度器。國內(nèi)外有很多專家學(xué)者對Hadoop 的作業(yè)調(diào)度算法進(jìn)行了深入的研究。Torabzadeh 等提出了在兩階段裝配式流水作業(yè)調(diào)度中基于云理論的模擬退火算法，其中給出相關(guān)函數(shù)，加入相應(yīng)指標(biāo)，并證明了該算法使總運(yùn)行時間和平均運(yùn)行時間減少[10]。Hadoop 的公平調(diào)度算法中存在著調(diào)度公平性與數(shù)據(jù)本地化的沖突。Zaharia 和Borthakur等人在公平調(diào)度算法的基礎(chǔ)上提出了Delay Scheduler策略，延遲調(diào)度的設(shè)計(jì)目標(biāo)是盡可能小地減少公平性，并提高作業(yè)的數(shù)據(jù)本地化，最終提高系統(tǒng)的吞吐量[11-12]。延遲調(diào)度的思想主要是針對小作業(yè)提出的，能很大程度提高小作業(yè)的吞吐量，從而提高整個系統(tǒng)的吞吐量。彭艦等提出了一種能夠找到總完成時間和平均完成時間最短的算法[13]。鄧自立針對Hadoop 的FIFO 調(diào)度算法的不足給出了一個基于優(yōu)先級的加權(quán)輪轉(zhuǎn)調(diào)度算法（PBWRR），這種算法避免了作業(yè)的長期等待，又考慮到了作業(yè)的優(yōu)先級[14]。

4 基于優(yōu)先級的計(jì)算能力加權(quán)調(diào)度算法

4.1 算法的思想與設(shè)計(jì)

在原算法中當(dāng)某個Tasktracker 上出現(xiàn)空閑slot 時，調(diào)度器依次選擇一個queue、（選中queue 中的）job、（選中job 中的）task，并將該slot 分配給該task[15]。下面介紹選擇queue、job 和task 所采用的策略。

（1）選擇queue：將所有queue 按照資源使用率由小到大排序，依次進(jìn)行處理，直到找到一個合適的job。

（2）選擇job：在當(dāng)前queue 中，所有作業(yè)按照作業(yè)提交時間和作業(yè)優(yōu)先級進(jìn)行排序，調(diào)度依次考慮每個作業(yè)，選擇符合兩個條件的job：①作業(yè)所在的用戶未達(dá)到資源使用上限；②該TaskTracker 所在的節(jié)點(diǎn)剩余的內(nèi)存足夠該job 的task 使用。

（3）選擇task，考慮task 的locality 和資源使用情況。

計(jì)算能力調(diào)度算法應(yīng)用于較多小作業(yè)時性能較差，容易陷入局部最優(yōu)，本文的算法主要是在計(jì)算能力調(diào)度的基礎(chǔ)上優(yōu)化步驟（2）中的作業(yè)選擇策略，優(yōu)化后的策略更加公平，避免選擇策略陷入局部最優(yōu)，從而提高了整個系統(tǒng)的效率和用戶滿意度。

在原算法中作業(yè)隊(duì)列是按照作業(yè)提交時間和作業(yè)優(yōu)先級進(jìn)行排序，然后選擇隊(duì)列頭部的作業(yè)。在本算法中首先根據(jù)作業(yè)權(quán)重對每個隊(duì)列的作業(yè)進(jìn)行排序，然后將這個空閑的slot 分配給選中隊(duì)列的第一個作業(yè)的task（該作業(yè)必須滿足步驟（2）中的兩個條件）?？梢钥闯觯鳂I(yè)的權(quán)重是選擇的重要參考依據(jù)。

考慮到TaskTracker主動請求task的模式以及Hadoop任務(wù)調(diào)度體系非搶占模式的特點(diǎn)，為了使調(diào)度的任務(wù)避免長期的等待，同時各個任務(wù)調(diào)度權(quán)重又能根據(jù)實(shí)際情況進(jìn)行調(diào)整，可以通過下面一系列推導(dǎo)得到權(quán)重的公式。

假設(shè)用V表示一個輪轉(zhuǎn)周期內(nèi)處理數(shù)據(jù)的總量，一般情況下Map任務(wù)的數(shù)量遠(yuǎn)遠(yuǎn)超過Reduce任務(wù)的數(shù)量。因此，用系統(tǒng)能夠同時運(yùn)行的Map 任務(wù)數(shù)量的能力來表示系統(tǒng)的所能處理任務(wù)數(shù)量的能力，記為taskcapacity。而且每個Map 任務(wù)所處理的數(shù)據(jù)量為輸入數(shù)據(jù)的分塊，大小即為HDFS中數(shù)據(jù)塊的大小，記為blockSize（一般設(shè)為64 MB），所以每一個輪轉(zhuǎn)周期系統(tǒng)所處理的數(shù)據(jù)量為：

用avgtasksize表示某job劃分的任務(wù)平均大小，jobsize表示某job的大小，tasknumber表示job的任務(wù)數(shù)，則有：

如果job[i]的權(quán)重為weight[i] 為了保證優(yōu)先級的作用和有效性，某個job 的優(yōu)先級與所有job 優(yōu)先級之和的比值應(yīng)該基本等于這個job 執(zhí)行的數(shù)據(jù)量與隊(duì)列一個輪轉(zhuǎn)周期的數(shù)據(jù)量的比值，即有：

于是就可以得到：

根據(jù)實(shí)際情況對權(quán)重進(jìn)行動態(tài)的調(diào)整避免算法陷入局部最優(yōu)，這里的實(shí)際情況就是隊(duì)列中作業(yè)的等待時間以及作業(yè)完成度（未完成task/全部的task）。因此計(jì)算作業(yè)權(quán)重要將作業(yè)的等待時間以及作業(yè)的完成度考慮進(jìn)去，由此可得：

其中，ctime表示當(dāng)前時間，stime表示作業(yè)提交時間，utask表示未完成任務(wù)數(shù)，atask代表任務(wù)的總數(shù)。

權(quán)重是同一隊(duì)列中作業(yè)排列的依據(jù)，在公式（5）中taskcapacity、blockSize和avgtasksize對同一隊(duì)列的作業(yè)來說都是定值所以可以簡化權(quán)重公式為：

4.2 算法的實(shí)現(xiàn)

（1）數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

jobQueue 的調(diào)度隊(duì)列中每個元素jobInfo 的數(shù)據(jù)結(jié)構(gòu)為：

class JobSchedulingInfo {

JobId jobId；

JobPriority priority；

long startTime；

int taskNum=0；

int finshedTaskNum=0；

double weight=0；

}

本文算法在JobSchedulingInfo 中增加了幾個參數(shù)，解析如下：

taskNum：作業(yè)的任務(wù)數(shù)量；

finshedTaskNum：作業(yè)已完成的任務(wù)數(shù)；

weight：作業(yè)的權(quán)重。

（2）權(quán)重的計(jì)算方法

權(quán)重的計(jì)算要基于作業(yè)的優(yōu)先級、作業(yè)的提交時間以及作業(yè)的完成量，其中優(yōu)先級對應(yīng)的值如表1 所示。

表1 優(yōu)先級對應(yīng)的具體值

算法的偽代碼如下：

（3）算法的其他內(nèi)容描述

本算法中要將JobQueue 中作業(yè)根據(jù)作業(yè)的權(quán)重進(jìn)行排序，實(shí)現(xiàn)的關(guān)鍵部分就是增加一個新的比較器，通過比較器來對隊(duì)列排序。比較器偽代碼描述如下：

5 實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)采用三臺虛擬機(jī)，操作系統(tǒng)為Linux Ubuntu 10.04.2，Java Version為1.6.0_10-rc2，Hadoop版本為0.20.2。將其中一臺作為主機(jī)Master，其余的兩臺分別作為Slave。使用最常用的WordCount（從文本數(shù)據(jù)統(tǒng)計(jì)單詞次數(shù)）作業(yè)來測試調(diào)度的改進(jìn)。算法部分參數(shù)配置如表2 所示。

表2 算法參數(shù)配置

實(shí)驗(yàn)1將八個作業(yè)傳到集群上運(yùn)行，作業(yè)的詳細(xì)信息如表3。

FIFO 調(diào)度器中得到的運(yùn)行時間如圖2 所示。

將Hadoop0.20.2 計(jì)算能力調(diào)度器插入到集群中。同樣將上面的八個作業(yè)傳到集群上運(yùn)行得到的運(yùn)行時間如圖3 所示。

將本文的調(diào)度算法插入到集群中，得到的運(yùn)行時間如圖4 所示。

表3 作業(yè)詳細(xì)信息

圖2 FIFO 調(diào)度器運(yùn)行結(jié)果圖

圖3 計(jì)算能力調(diào)度器運(yùn)行結(jié)果圖

圖4 本文算法運(yùn)行結(jié)果圖

對比實(shí)驗(yàn)結(jié)果可以看出三個調(diào)度算法的執(zhí)行順序均不相同，時長不一。FIFO 算法是按照作業(yè)的優(yōu)先級和進(jìn)入隊(duì)列先后時間順序執(zhí)行的，沒有考慮作業(yè)的長短以及不同作業(yè)的需求，執(zhí)行總時間最長，計(jì)算能力調(diào)度算法和本文算法執(zhí)行順序不同是因?yàn)樗惴ǖ倪x擇作業(yè)策略不同。對比圖3 和圖4，可以看出圖4 中的部分小作業(yè)執(zhí)行時間提前，執(zhí)行順序并沒有嚴(yán)格按照作業(yè)的優(yōu)先級進(jìn)行執(zhí)行；還可以看出雖然部分作業(yè)的執(zhí)行時間延長了但是等待作業(yè)執(zhí)行時間提前了。這是因?yàn)樵谧鳂I(yè)執(zhí)行的尾段，作業(yè)的完成度較高而等待作業(yè)的完成度較低，調(diào)度器動態(tài)調(diào)整了作業(yè)的權(quán)重，等待作業(yè)的權(quán)重這時候有可能大于運(yùn)行的作業(yè)，這樣就減少了等待作業(yè)的響應(yīng)時間。同時可以看出，優(yōu)化后的作業(yè)選擇策略使得總時間比計(jì)算能力調(diào)度算法減少了兩分多鐘。

實(shí)驗(yàn)2測試更一般的情況，提交八個作業(yè)到集群上運(yùn)行。作業(yè)的優(yōu)先級和大小是不盡同的，集群分別使用FIFO、本文算法和計(jì)算能力調(diào)度算法，完成時間對比如圖5 所示。

圖5 作業(yè)在不同調(diào)度算法下的完成時間對比

從圖5可以看出雖然本文算法在完成前幾個作業(yè)和原算法的用時上并沒有太大的優(yōu)勢，但是隨著作業(yè)數(shù)的增加本文算法逐漸顯現(xiàn)出優(yōu)勢。因此可以預(yù)測，在大的多用戶多任務(wù)的集群上本文算法的效率肯定將超過原算法。

實(shí)驗(yàn)3將三個不盡相同的作業(yè)組上傳到集群上，并用本文算法和計(jì)算能力調(diào)度算法進(jìn)行測試。每組八個作業(yè)，作業(yè)的優(yōu)先級隨機(jī)分配，J-a 是小作業(yè)占多數(shù)的作業(yè)組，J-b 是大作業(yè)和小作業(yè)的數(shù)量相當(dāng)?shù)淖鳂I(yè)組，J-c 是大作業(yè)占多數(shù)的作業(yè)組，得到結(jié)果如圖6 所示。

圖6 三組作業(yè)在兩種調(diào)度算法下的時間比較

從圖6可以看出來不同類型的作業(yè)組在本文算法下運(yùn)行的時間均比計(jì)算能力調(diào)度算法要少。在作業(yè)組中有較多小作業(yè)的時候本文算法可以減少總運(yùn)行時間，當(dāng)作業(yè)組中大作業(yè)占據(jù)絕大多數(shù)時，本文算法就退化為與計(jì)算能力調(diào)度算法類似。結(jié)合實(shí)驗(yàn)對比圖可以得出本文算法減少了部分作業(yè)等待時間，優(yōu)化了作業(yè)選擇策略，使得作業(yè)組的總運(yùn)行時間減少，提高了用戶的滿意度。

6 結(jié)束語

作業(yè)調(diào)度器關(guān)系到Hadoop 平臺整體的性能和系統(tǒng)的資源使用效率，以及云計(jì)算服務(wù)的能力。本文提出了一種基于優(yōu)先級的計(jì)算能力加權(quán)調(diào)度算法，當(dāng)系統(tǒng)出現(xiàn)空閑的slot 時，作業(yè)的選擇策略不僅僅考慮作業(yè)的優(yōu)先級而是同時將作業(yè)的等待時間和作業(yè)完成度動態(tài)的考慮進(jìn)去。這種策略避免了作業(yè)調(diào)度器陷入局部最優(yōu)，同時能夠減少某些相對較高優(yōu)先級小作業(yè)的等待時間，在一定程度上優(yōu)化了作業(yè)選擇策略，減少了總運(yùn)行時間，提高了系統(tǒng)的使用效率。

[1] 劉鵬.云計(jì)算[M].2 版.北京：電子工業(yè)出版社，2011.

[2] Dean J，Ghemawat S.MapReduce：Simplified data processing on large clusters[J].Communications of the ACM，2008，51（1）：107-113.

[3] Ralf L.Google’s MapReduce programming model-revisited[J].Science of Computer Programming，2008，70（1）：1-30.

[4] Wbite T.Hadoop 權(quán)威指南[M].曾大聃，周傲英，譯.北京：清華大學(xué)出版社，2010.

[5] Apache Hadoop[EB/OL].[2013-09-01].http：//hadoop.apache.org/.

[6] 趙春燕.云環(huán)境下作業(yè)調(diào)度算法研究與實(shí)現(xiàn)[D].北京：北京交通大學(xué)，2009：20-58.

[7] 羅軍舟，金嘉暉，送愛波，等.云計(jì)算體系架構(gòu)與關(guān)鍵技術(shù)[J].通信學(xué)報，2011，32（7）：3-21.

[8] Fair Scheduler[EB/OL].[2013-09-01].http：//hadoop.apache.org/common/docs/r0.20.2/fair_scheduler.html.

[9] CapacityScheduler[EB/OL].[2013-09-01].http：//hadoop.Apache.org/common/docs/r0.20.2/capacity_scheduler.html.

[10] Torabzadeh E，Zandieh M.Cloud theory-based simulated annealing approach for scheduling in the two-stage assembly flowshop[J].Advances in Engineering Software，2010，41（10）：1243-1298.

[11] Zaharia M，Borthakur D，Sen Sarma J，et al.Delay scheduling：A simple technique for achieving locality and fairness in cluster scheduling[C]//Proceedings of EuroSys’10.New York，NY，USA：ACM，2010：265-278.

[12] Matei Z，Dhruba B，Joydeep S，et al.Delay scheduling：A simple technique for achieving locality and fairness in cluster scheduling[C]//Proc of the 5th European Conference on Computer Systems，2010：265-278.

[13] 李建鋒，彭艦.云計(jì)算環(huán)境下基于改進(jìn)遺傳算法的任務(wù)調(diào)度算法[J].計(jì)算機(jī)應(yīng)用，2011，31（1）：184-186.

[14] 鄧自立.云計(jì)算中的網(wǎng)絡(luò)拓?fù)湓O(shè)計(jì)和Hadoop平臺研究[D].合肥：中國科學(xué)技術(shù)大學(xué)，2009.

[15] 陳艷金.MapReduce 模型在Hadoop 平臺下實(shí)現(xiàn)作業(yè)調(diào)度算法的研究和改進(jìn)[D].廣州：華南理工大學(xué)，2011.