基于權(quán)值的Hadoop調(diào)度算法改進(jìn)與實(shí)現(xiàn)

朱健軍，張　彤，吳哲夫

(浙江工業(yè)大學(xué)信息學(xué)院，浙江 杭州 310023)

摘要：針對(duì)當(dāng)前Hadoop集群自帶的任務(wù)級(jí)調(diào)度分配方法在實(shí)際處理作業(yè)時(shí)存在資源分配不均的問(wèn)題，提出了一種基于權(quán)值的任務(wù)調(diào)度分配算法。該算法結(jié)合節(jié)點(diǎn)當(dāng)前的負(fù)載狀態(tài)、節(jié)點(diǎn)物理性能和任務(wù)優(yōu)先級(jí)等作為依據(jù)，通過(guò)權(quán)值排序當(dāng)前的作業(yè)隊(duì)列并將空閑資源優(yōu)先分配給權(quán)值高的任務(wù)，從而實(shí)現(xiàn)運(yùn)行過(guò)程中作業(yè)任務(wù)的自適應(yīng)動(dòng)態(tài)調(diào)度。實(shí)驗(yàn)結(jié)果表明，改進(jìn)算法相比原來(lái)的FIFO算法有30%的性能提升。

關(guān)鍵詞：云計(jì)算；任務(wù)調(diào)度；權(quán)值

DOI: 10.13954/j.cnki.hdu.2015.01.005

基于權(quán)值的Hadoop調(diào)度算法改進(jìn)與實(shí)現(xiàn)

朱健軍，張彤，吳哲夫

(浙江工業(yè)大學(xué)信息學(xué)院，浙江 杭州 310023)

摘要：針對(duì)當(dāng)前Hadoop集群自帶的任務(wù)級(jí)調(diào)度分配方法在實(shí)際處理作業(yè)時(shí)存在資源分配不均的問(wèn)題，提出了一種基于權(quán)值的任務(wù)調(diào)度分配算法。該算法結(jié)合節(jié)點(diǎn)當(dāng)前的負(fù)載狀態(tài)、節(jié)點(diǎn)物理性能和任務(wù)優(yōu)先級(jí)等作為依據(jù)，通過(guò)權(quán)值排序當(dāng)前的作業(yè)隊(duì)列并將空閑資源優(yōu)先分配給權(quán)值高的任務(wù)，從而實(shí)現(xiàn)運(yùn)行過(guò)程中作業(yè)任務(wù)的自適應(yīng)動(dòng)態(tài)調(diào)度。實(shí)驗(yàn)結(jié)果表明，改進(jìn)算法相比原來(lái)的FIFO算法有30%的性能提升。

關(guān)鍵詞：云計(jì)算；任務(wù)調(diào)度；權(quán)值

DOI:10.13954/j.cnki.hdu.2015.01.005

收稿日期：2014-11-06

基金項(xiàng)目：浙江省自然科學(xué)基金資助項(xiàng)目(LY13F010011)

作者簡(jiǎn)介：朱健軍(1974-)，男，浙江杭州人，講師，云計(jì)算網(wǎng)絡(luò).

中圖分類號(hào)：TP301.5

文獻(xiàn)標(biāo)識(shí)碼：：A

文章編號(hào)：：1001-9146(2015)01-0027-04

Abstract:To address the problem of unfair resource assignment in task scheduling method on Hadoop platform， this paper proposed an improved scheduling algorithm based on weight. The algorithm considered the current node state， node physical properties as well as job priority to queue the job， and then sorted the free resource to the first job task based on the weight to implement adaptive dynamic task scheduling during system operation. The experimental results show that it gives about 30% performance better than FIFO algorithm.

0引言

Hadoop作為云計(jì)算系統(tǒng)的MapReduce開(kāi)源實(shí)現(xiàn)，在大規(guī)模的數(shù)據(jù)處理方面得到了廣泛應(yīng)用。在Hadoop平臺(tái)上[1]用戶可以不考慮任務(wù)的底層實(shí)現(xiàn)，只需開(kāi)發(fā)云計(jì)算的應(yīng)用程序，然后將任務(wù)提交給Hadoop云平臺(tái)。Hadoop具有很強(qiáng)的容錯(cuò)性，并可方便地增加集群節(jié)點(diǎn)個(gè)數(shù)、線性擴(kuò)展集群規(guī)模，使集群能適應(yīng)處理更大規(guī)模的數(shù)據(jù)集。Hadoop已經(jīng)成為了許多互聯(lián)網(wǎng)公司基礎(chǔ)計(jì)算平臺(tái)的核心。但Hadoop也有自身的一些不足，特別是在實(shí)際使用過(guò)程中暴露出來(lái)的MapReduce調(diào)度器[2]的低效性和對(duì)異構(gòu)系統(tǒng)適應(yīng)能力差的問(wèn)題。目前常見(jiàn)的調(diào)度算法主要有默認(rèn)調(diào)度算法FIFO，該方法采用單一的先進(jìn)先出隊(duì)列，不考慮作業(yè)的大小或優(yōu)先級(jí)，效率較低；延遲調(diào)度算法[3]則采用了時(shí)間推移來(lái)改善數(shù)據(jù)公平性與本地性的沖突；LATE算法[4]根據(jù)異構(gòu)集群中任務(wù)執(zhí)行速率變化的特性，將后進(jìn)任務(wù)調(diào)度到執(zhí)行速度較快的空閑節(jié)點(diǎn)執(zhí)行。本文從資源利用率角度出發(fā)，在計(jì)算能力調(diào)度算法[5]的基礎(chǔ)上，根據(jù)作業(yè)優(yōu)先級(jí)、資源需求、節(jié)點(diǎn)距離[6]等因素來(lái)計(jì)算作業(yè)的權(quán)重值，同時(shí)實(shí)時(shí)觀察和反饋執(zhí)行狀態(tài)，進(jìn)一步自適應(yīng)地調(diào)節(jié)節(jié)點(diǎn)工作負(fù)載，實(shí)現(xiàn)任務(wù)調(diào)度過(guò)程中的負(fù)載均衡，從而提高集群的任務(wù)執(zhí)行效率。

1Hadoop任務(wù)調(diào)度

1.1　資源調(diào)度模型

集群資源的組織和分配管理是Hadoop系統(tǒng)中最基本的功能模塊之一，如圖1所示，其資源分配過(guò)程可以概括為以下7個(gè)步驟。

1)節(jié)點(diǎn)管理器通過(guò)周期性心跳匯報(bào)節(jié)點(diǎn)信息；

2)資源管理器和節(jié)點(diǎn)管理器返回心跳應(yīng)答，釋放Container列表信息；

3)資源管理器收到節(jié)點(diǎn)管理器信息后觸發(fā)節(jié)點(diǎn)更新事件；

4)資源調(diào)度器在收到節(jié)點(diǎn)更新事件后，按照一定策略將該策略節(jié)點(diǎn)上的資源分配給各應(yīng)用程序；

5)應(yīng)用程序向資源管理器發(fā)送周期心跳，以領(lǐng)取最新分配的Container；

6)資源管理器收到應(yīng)用程序心跳信息后分配的Container以心跳應(yīng)答的形式返回；

7)應(yīng)用程序收到新分配Container列表，將其進(jìn)一步分配給內(nèi)部的各個(gè)任務(wù)。

圖1　資源調(diào)度器資源分配流程

1.2　加權(quán)計(jì)算能力調(diào)度算法

從以上調(diào)度模型可知，Hadoop采用了3級(jí)資源分配策略，當(dāng)某個(gè)節(jié)點(diǎn)上有空閑資源時(shí)依次選擇隊(duì)列、應(yīng)用程序和Container請(qǐng)求，其調(diào)度過(guò)程如下：1)選擇隊(duì)列。Hadoop采用基于優(yōu)先級(jí)的深度優(yōu)先遍歷算法；2)選擇應(yīng)用程序。選定葉子隊(duì)列后，容量調(diào)度器按照提交時(shí)間對(duì)葉子隊(duì)列中的應(yīng)用程序進(jìn)行排序并依次遍歷，以找到一個(gè)或多個(gè)最合適的Container；3)選擇Container。對(duì)于同一個(gè)應(yīng)用程序，所請(qǐng)求Container可能是多樣化，涉及不同的優(yōu)先級(jí)、節(jié)點(diǎn)、資源量和數(shù)量。當(dāng)選中一個(gè)應(yīng)用程序后，容量調(diào)度器將嘗試優(yōu)先滿足優(yōu)先級(jí)高的Container，對(duì)于同一類優(yōu)先級(jí)則優(yōu)先滿足本地性因子高的Container。

在原算法中作業(yè)隊(duì)列是先按照作業(yè)提交時(shí)間和作業(yè)優(yōu)先級(jí)進(jìn)行排序，然后選擇隊(duì)列頭部的作業(yè)。本文改進(jìn)算法首先根據(jù)作業(yè)權(quán)重對(duì)每個(gè)隊(duì)列的作業(yè)進(jìn)行排序，然后將空閑時(shí)隙分配給選中隊(duì)列的第一個(gè)作業(yè)的Container。因此，改進(jìn)算法中作業(yè)權(quán)重的選擇是作業(yè)排序的重要參考依據(jù)。

為使調(diào)度任務(wù)避免長(zhǎng)期等待，改進(jìn)算法優(yōu)化了分配步驟中Container的排列順序，即根據(jù)實(shí)際情況來(lái)動(dòng)態(tài)調(diào)整Container的權(quán)值。在分析權(quán)重排序時(shí)，令avgResource表示請(qǐng)求的平均資源大小，Resource表示某個(gè)Container的資源請(qǐng)求量，containerNum表示Container的數(shù)量，則有：

(1)

為保證優(yōu)先級(jí)，如果container[i]的權(quán)重為weight[i]，將優(yōu)先級(jí)體現(xiàn)在權(quán)重中，設(shè)立如下公式：

(2)

式中，V表示一個(gè)輪轉(zhuǎn)周期內(nèi)處理的任務(wù)數(shù)總量，一般情況下V為一個(gè)常數(shù)。于是可以得到：

(3)

同時(shí)，考慮到Container請(qǐng)求中的期望資源所在節(jié)點(diǎn)、Container數(shù)目和Container提交時(shí)間等參數(shù)對(duì)Container選擇的影響，由此可得：

(4)

式中，ctime，stime分別表示當(dāng)前時(shí)間和任務(wù)提交時(shí)間，resouceDist表示資源與計(jì)算節(jié)點(diǎn)的距離。

算法中的偽代碼設(shè)計(jì)如下：

Input: JobInfo

Output: null

update parameter of job

factor=cTime/sTime+container/sum(container)

if container numbers of job>0

Then

job weight=(priority/sum(priority))*factor*resourceDist

else

job weight=0

end if

改進(jìn)算法增加的參數(shù)、優(yōu)先權(quán)值和資源節(jié)點(diǎn)距離對(duì)應(yīng)的取值如表1、表2所示。

表1　優(yōu)先級(jí)對(duì)應(yīng)具體值

表2　資源本地性對(duì)應(yīng)具體值

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

表3　節(jié)點(diǎn)配置參數(shù)

本實(shí)驗(yàn)環(huán)境采用3臺(tái)機(jī)器構(gòu)成的Hadoop異構(gòu)集群，其操作系統(tǒng)為Ubuntu12.04，Java版本為jdk1.7.0_45，Hadoop版本為2.2.0。3個(gè)節(jié)點(diǎn)配置參數(shù)如表3所示。

實(shí)驗(yàn)采用了Hadoop自帶WordCount實(shí)例，通過(guò)計(jì)算處理任務(wù)時(shí)的花費(fèi)時(shí)間來(lái)比較自帶算法和改進(jìn)調(diào)度算法的性能。將10個(gè)作業(yè)提交到集群上運(yùn)行，作業(yè)的大小不同，而且其各自的任務(wù)優(yōu)先級(jí)、資源節(jié)點(diǎn)距離也各不相同，其詳細(xì)信息如表4。集群任務(wù)分別采用FIFO、計(jì)算能力調(diào)度算法和本文改進(jìn)算法來(lái)執(zhí)行，所完成時(shí)間對(duì)比如圖2所示。

表4　任務(wù)作業(yè)的參數(shù)

圖2　作業(yè)在不同調(diào)度算法下的完成時(shí)間

從圖2可以看出改進(jìn)算法在任務(wù)數(shù)較少時(shí)并沒(méi)有太大優(yōu)勢(shì)，但隨著作業(yè)數(shù)量增多，改進(jìn)算法相比計(jì)算能力調(diào)度算法而言已有一定的改善，相比FIFO算法的優(yōu)勢(shì)則更為明顯。這是因?yàn)楦倪M(jìn)算法進(jìn)一步優(yōu)化了原來(lái)的計(jì)算能力調(diào)度算法，特別針對(duì)系統(tǒng)任務(wù)數(shù)較多時(shí)，優(yōu)化分配了Container的排列順序，并通過(guò)動(dòng)態(tài)性的調(diào)整Container權(quán)值，使其在調(diào)度過(guò)程中能夠自適應(yīng)調(diào)整作業(yè)的權(quán)值，減少了系統(tǒng)任務(wù)調(diào)度和作業(yè)執(zhí)行過(guò)程中的等待時(shí)間。實(shí)驗(yàn)數(shù)據(jù)結(jié)果表明，在任務(wù)數(shù)較多的情況下，改進(jìn)算法性能相較于系統(tǒng)默認(rèn)的FIFO算法提高了將近30%，而對(duì)于計(jì)算能力調(diào)度算法也提高了7%左右。實(shí)驗(yàn)結(jié)果表明，本改進(jìn)算法確實(shí)進(jìn)一步提高了Hadoop中原先的計(jì)算能力調(diào)度算法性能。

3結(jié)束語(yǔ)

作業(yè)調(diào)度系統(tǒng)是Hadoop平臺(tái)的核心，在很大程度上影響了平臺(tái)的性能和系統(tǒng)運(yùn)行效率。本文提出的改進(jìn)算法在計(jì)算能力調(diào)度算法的基礎(chǔ)上，根據(jù)作業(yè)優(yōu)先級(jí)、資源需求量和資源本地性等因素計(jì)算作業(yè)的權(quán)值，當(dāng)系統(tǒng)出現(xiàn)空閑時(shí)優(yōu)先調(diào)度權(quán)值高的作業(yè)。改進(jìn)算法動(dòng)態(tài)地調(diào)整了作業(yè)的執(zhí)行順序，降低了作業(yè)在爭(zhēng)奪資源過(guò)程中產(chǎn)生的等待時(shí)間，從而提高了系統(tǒng)的運(yùn)行效率。

參考文獻(xiàn)

[1]董成西.Hadoop技術(shù)內(nèi)幕：深入解析YARN架構(gòu)設(shè)計(jì)與實(shí)現(xiàn)原理[M].北京:機(jī)械工業(yè)出版社，2014:30-52.

[2]Dean J， Ghemawat S. MapReduce: simplified data processing on large clusters[J]. Communications of the ACM，2008，51(1):107-113.

[3]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 the 5th European conference on Computer systems. ACM，2010:265-278.

[4]胡丹，于炯，英昌甜，等.Hadoop平臺(tái)下改進(jìn)的LATE調(diào)度算法[J].計(jì)算機(jī)工程與應(yīng)用，2014，50(4):86-89.

[5]Hadoop. CapacityScheduler[EB/OL]. [2014-09-22]. http://hadoop.apache.org/docs/current/had-oop-yarn/hadoop-yarn-site/CapacityScheduler.html.

[6]Jayalath C，Stephen J，Eugster P.From the Cloud to the Atmosphere: Running MapReduce across Data Centers[J].IEEE Transactions on Computers，2014，63(1):74-87.

Improvement of Scheduling Algorithm in Hadoop Based on Weight

Zhu Jianjun， Zhang Tong， Wu Zhefu

(CollegeofInformationEngineering，ZhejiangUniversityofTechnology，HangzhouZhejiang310023，China)

Key words: cloud computing; task scheduling; weight