王越峰+陳福洪

摘 要：Hadoop集群環(huán)境下本地性調(diào)度算法是提高數(shù)據(jù)本地性的算法。算法本質(zhì)是提高數(shù)據(jù)本地性，減少數(shù)據(jù)傳輸時間，減少集群的網(wǎng)絡(luò)I/O，提高資源利用率。由于調(diào)度算法采用FIFO方式，當(dāng)前作業(yè)數(shù)據(jù)量大時將影響其他緊急性高的作業(yè)響應(yīng)時間，降低系統(tǒng)性能。本文提出一種新的調(diào)度策略，即在保證原算法數(shù)據(jù)本地性的前提下，集成靜態(tài)優(yōu)先級的搶占調(diào)度策略。實(shí)驗結(jié)果表明，在相同的數(shù)據(jù)集上，采用集成靜態(tài)優(yōu)先級搶占的調(diào)度策略，優(yōu)先級高的作業(yè)響應(yīng)時間較優(yōu)先級低的作業(yè)響應(yīng)時間減少。

關(guān)鍵詞：數(shù)據(jù)本地性；靜態(tài)優(yōu)先級搶占；作業(yè)響應(yīng)時間

中圖分類號：TP316.4 文獻(xiàn)標(biāo)識碼：A

1 引言（Introduction）

在大數(shù)據(jù)持續(xù)發(fā)展的今天Hadoop集群環(huán)境下調(diào)度算法的研究越來越受到重視。對于作業(yè)調(diào)度算法的改進(jìn)一般都是為了減少作業(yè)的完成時間，在同樣資源的基礎(chǔ)上減少系統(tǒng)消耗。例如大多數(shù)的算法都要研究數(shù)據(jù)本地性，通過減少機(jī)架間的網(wǎng)絡(luò)傳輸減少傳輸時間，提高系統(tǒng)性能。

本文在對已有的調(diào)度策略改進(jìn)時不僅注意提高作業(yè)的完成時間，還注意了系統(tǒng)對作業(yè)需要的優(yōu)先程度，即一般作業(yè)使用FIFO默認(rèn)調(diào)度策略思路。導(dǎo)致一些優(yōu)先級高的作業(yè)沒有在需要的時間完成，造成系統(tǒng)性能降低。在其他操作系統(tǒng)中遇到類似情況，一般使用優(yōu)先級搶占策略，使優(yōu)先級高的作業(yè)可以搶占正在執(zhí)行的優(yōu)先級低的作業(yè)的資源，達(dá)到可以降低緊急作業(yè)的響應(yīng)時間。本文沿用了這一思路，提出基于靜態(tài)優(yōu)先級的搶占策略。以解決作業(yè)優(yōu)先級不同時如何降低緊急作業(yè)的響應(yīng)時間等問題。

2 Hadoop平臺（Hadoop platform）

Hadoop平臺是Apache基金組織引入[1]，受到Google開發(fā)的GPS（Google File System）的啟發(fā)，主要由Hadoop分布式文件系統(tǒng)HDFS（Hadoop Distributed Files System）[2]和分布式計算框架MapReduce[3]計算架構(gòu)組成。

Hadoop平臺在大數(shù)據(jù)的背景下發(fā)展飛速，在這種背景下大量數(shù)據(jù)出現(xiàn)了中心聚集的問題，每日的數(shù)據(jù)處理、作業(yè)處理在逐步上升。作業(yè)調(diào)度性能是衡量大型Hadoop平臺性能的首要問題，一個好的調(diào)度策略可以減少作業(yè)的平均完成時間，減少系統(tǒng)的負(fù)荷，提高作業(yè)的完成效率和準(zhǔn)確性，同時也可以有效使用平臺資源[4]。在Hadoop平臺中，作業(yè)調(diào)度策略是通過作業(yè)調(diào)度器（HadoopTask Schedule）對作業(yè)進(jìn)行調(diào)度，如圖1所示。那么設(shè)計、使用好的Task Schedule，對Hadoop集群平臺的性能提高特別主要[5]。Hadoop中MapReduce原有三種調(diào)度器[6]：默認(rèn)的調(diào)度器FIFO Scheduler（先入先出調(diào)度）、計算能力調(diào)度器（Capacity Scheduler）、公平調(diào)度器（Fair Scheduler）。

默認(rèn)調(diào)度器FIFO是HadoopMap/Reduce計算架構(gòu)中最早的，JobTracker在進(jìn)行作業(yè)調(diào)度時使用的是FIFO（First In First Out）算法。所有用戶的作業(yè)都被提交到一個隊列中，然后由JobTracker先按照作業(yè)的優(yōu)先級高低，再按照作業(yè)提交時間的先后順序選擇將被執(zhí)行的作業(yè)。優(yōu)點(diǎn)是調(diào)度算法簡單明了，JobTracker工作負(fù)擔(dān)輕。同樣缺點(diǎn)是忽略了不同作業(yè)的需求差異。例如如果類似對海量數(shù)據(jù)進(jìn)行統(tǒng)計分析的作業(yè)長期占據(jù)計算資源，那么在其后提交的交互型作業(yè)有可能遲遲得不到處理，從而影響到用戶的體驗。計算能力調(diào)度器使用時，用戶需要了解大量系統(tǒng)信息，才能設(shè)置和選擇隊列；公平調(diào)度器不考慮節(jié)點(diǎn)的實(shí)際負(fù)載狀態(tài)，導(dǎo)致節(jié)點(diǎn)負(fù)載不均勻。所以越來越多的研究者從多個方面對調(diào)度算法進(jìn)行了深入研究。

為了研究資源調(diào)度策略，研究者通過調(diào)查大量數(shù)據(jù)和不同的方向[9]從其他研究者的工作中，將調(diào)度分成五類：

（1）本地性感知調(diào)度（Data Locality Aware Schedulers）

（2）可靠性感知調(diào)度（Speculative Execution Based Schedulers）

（3）資源競爭感知調(diào)度（Resource Contention Aware Schedulers）

（4）性能管理感知調(diào)度（Performance Management Based Schedulers）

（5）能源與完成時間感知調(diào)度（Energy and Makespan Aware Schedulers）

MapReduce作業(yè)調(diào)度算法對集群的性能有著至關(guān)重要的影響。通過以下五個標(biāo)準(zhǔn)來比較Hadoop平臺性能[10]：平均完成時間（是一個作業(yè)從開始到結(jié)束的時間，同時也是衡量系統(tǒng)性能的最重要的標(biāo)準(zhǔn)）、公平性（調(diào)度策略給不同的作業(yè)分配的資源是否一致）、數(shù)據(jù)本地性（研究調(diào)度策略的另一重要指標(biāo)，是否在存儲數(shù)據(jù)節(jié)點(diǎn)上處理任務(wù)）、調(diào)度時間（調(diào)度策略的開銷）、調(diào)度策略是否達(dá)到客戶對系統(tǒng)資源的配額。然而，這些性能標(biāo)準(zhǔn)之間又存在互相沖突，即當(dāng)提高一些標(biāo)準(zhǔn)時，會同時降低其他一些標(biāo)準(zhǔn)。在通常情況下，作業(yè)的平均完成時間和數(shù)據(jù)本地性是每個調(diào)度策略都必須優(yōu)先處理的性能標(biāo)準(zhǔn)

3 本地性調(diào)度算法（Local scheduling algorithm）

數(shù)據(jù)本地性是Hadoop集群平臺下衡量作業(yè)調(diào)度器的重要的標(biāo)準(zhǔn)。大量的數(shù)據(jù)在機(jī)架之間傳輸會產(chǎn)生較大的網(wǎng)絡(luò)I/O，特別是在多個不同的機(jī)架之間傳輸時延遲更大。這會使作業(yè)的平均完成時間降低，同時還會產(chǎn)生大量的網(wǎng)絡(luò)傳輸開銷。Palanisamy等人提出Purlieus[11]算法，該算法通過將任務(wù)調(diào)度和數(shù)據(jù)放置結(jié)合起來的方式，使Reduce任務(wù)的本地性有較大幅度的提高。他指出，如果不考慮數(shù)據(jù)的放置策略，將會很難獲得良好的本地性，因為隨機(jī)的數(shù)據(jù)放置策略可能會導(dǎo)致一些節(jié)點(diǎn)變得更加擁塞。一個有效的數(shù)據(jù)放置策略需要將這些特點(diǎn)考慮進(jìn)去，盡量將長作業(yè)的數(shù)據(jù)放到負(fù)載最小的節(jié)點(diǎn)上。但是這種算法仍然沒有考慮到Reduce任務(wù)的本地性要求。

Hammoud等人提出本地化感知的Reduce任務(wù)調(diào)度算法LARTS[12]（Locality-Aware Reduce Tasl Scheduling for MapReduce）以解決Reduce任務(wù)數(shù)據(jù)本地性的問題。LARTS在Map任務(wù)完成到一定的閾值α后啟動Early Shuffle機(jī)制。這種調(diào)度策略利用Early Shuffle的優(yōu)點(diǎn)并且兼顧了Reduce任務(wù)的數(shù)據(jù)本地性。但是閥值α的設(shè)定需要根據(jù)不同類型的作業(yè)設(shè)定，而且存在一定的誤差。

4 集成靜態(tài)優(yōu)先級搶占的本地性調(diào)度算法（Local

scheduling algorithm with integrated static priority

preemption）

對于本地性調(diào)度算法來說，優(yōu)先強(qiáng)調(diào)的是數(shù)據(jù)的本地性。但是，無論是單機(jī)調(diào)度還是集群式調(diào)度都會涉及到任務(wù)的優(yōu)先性問題。尤其是在集群環(huán)境下的作業(yè)調(diào)度，當(dāng)前作業(yè)的Map任務(wù)個數(shù)多，需要系統(tǒng)利用大量時間進(jìn)行處理計算。而后面進(jìn)入的重要任務(wù)一直沒辦法分配到資源，使得任務(wù)無響應(yīng)，嚴(yán)重時會引發(fā)系統(tǒng)崩潰。這樣正常的本地性調(diào)度并不能處理這些問題，本文提出靜態(tài)優(yōu)先級搶占式本地性調(diào)度算法。

集成靜態(tài)優(yōu)先級搶占的本地性調(diào)度策略，為每一個提交的作業(yè)都設(shè)置一個靜態(tài)優(yōu)先級，而被設(shè)置的靜態(tài)優(yōu)先級意味著作業(yè)的緊急程度。按照優(yōu)先級搶占策略，緊急程度高的作業(yè)有著較高的優(yōu)先級，它可以搶占緊急程度低的且優(yōu)先級低的作業(yè)的處理資源。使得調(diào)度策略更加的有針對性，提高調(diào)度策略對高優(yōu)先級任務(wù)的關(guān)注，使計算資源優(yōu)先分配。確保緊急任務(wù)緊急處理，減少高優(yōu)先級任務(wù)的響應(yīng)時間。

一般的本地性調(diào)度算法都是使用FIFO算法的調(diào)度方式，也就是先到的作業(yè)先進(jìn)行處理，這樣的調(diào)度算法缺少對任務(wù)緊要程度的關(guān)注。所以集成靜態(tài)優(yōu)先級搶占的本地性調(diào)度策略首先要對優(yōu)先級進(jìn)行定義。每個作業(yè)在提交時設(shè)置獨(dú)立的參數(shù)staticpriority，用來表示作業(yè)的緊要程度。作業(yè)越緊要越優(yōu)先staticpriority值越高。

但是如果僅僅考慮到作業(yè)的優(yōu)先性問題，有可能導(dǎo)致作業(yè)優(yōu)先級低且數(shù)據(jù)量很小的作業(yè)一直被優(yōu)先級高數(shù)據(jù)量很大的作業(yè)搶占，導(dǎo)致優(yōu)先級低的作業(yè)一直無法執(zhí)行。所以本文在定義優(yōu)先級的時候加入新的參數(shù)作業(yè)的等待時間waittime。

waittime=nowtime-submittime （1）

在公式（1）中nowtime和submittime分別表示系統(tǒng)的現(xiàn)在時間和作業(yè)的提交時間，通過兩者做差的方式得出作業(yè)在作業(yè)池中的等待時間。

為了防止上文中提到的優(yōu)先級低的作業(yè)無法執(zhí)行的問題為作業(yè)的優(yōu)先級加入等待時間這個影響因素。但是即使加上了作業(yè)的等待時間也會出現(xiàn)等待時長過長的問題。比如優(yōu)先級較高的作業(yè)數(shù)據(jù)非常大，Map任務(wù)數(shù)量也較多。系統(tǒng)在通過原本地性調(diào)度策略后，作業(yè)的處理時間也非常大。在處理的過程中可能會有優(yōu)先級相同且數(shù)據(jù)小，Map任務(wù)個數(shù)少的作業(yè)等待時間變長。在Hadoop集群環(huán)境下不能像其他系統(tǒng)一樣直接搶占運(yùn)算資源，因為其中涉到了Map任務(wù)完成后的中間值問題，和Reduce任務(wù)的中間拷貝等問題。無法直接搶占原有作業(yè)的運(yùn)算資源。所以作業(yè)池中的優(yōu)先級定義就特別重要。在加入等待時間的基礎(chǔ)上再加入作業(yè)的估計執(zhí)行時間estimatetime如公式（2）。

priority=α×staticpriority+β×waittime+γ×estimatetime（2）

α+β+γ=1（α>0，β>0，γ>0） （3）

priority是調(diào)度算法的最終優(yōu)先級。α、β、γ表示其中各項參數(shù)所占比例，對于不同種的數(shù)據(jù)類型和作業(yè)將取不同的數(shù)值，以達(dá)到對作業(yè)優(yōu)先性能的標(biāo)準(zhǔn)。其中estimatetime的確定要根據(jù)不同的本地性調(diào)度算法出發(fā)，針對算法的本地性調(diào)度得出估計時間。

5 實(shí)驗結(jié)果及性能分析（Experimental results and

performance analysis）

本文通過虛擬機(jī)的方式搭建異構(gòu)測試環(huán)境。定義兩個機(jī)架，每個機(jī)架5臺虛擬機(jī)，每個虛擬機(jī)分配512MB內(nèi)存。測試作業(yè)為WordCount。通過給不同大小的作業(yè)設(shè)置不同的靜態(tài)優(yōu)先級實(shí)驗比較算法間作業(yè)的響應(yīng)時間。

提交五個大小為5G的WordCount作業(yè)，靜態(tài)優(yōu)先級分別設(shè)置為1、2、3、4、5，作業(yè)編號為1、2、3、4、5。提交五個大小為10GB的WordCount作業(yè)，靜態(tài)優(yōu)先級分別設(shè)置為1、2、3、4、5，作業(yè)編號為6、7、8、9、10。

通過圖2可以觀察出編號為5、10的響應(yīng)最快，其次是編號4、9，響應(yīng)時間最長的是編號1、6。這樣的結(jié)果可以證明前面的想法，作業(yè)的響應(yīng)時間和作業(yè)的靜態(tài)優(yōu)先級設(shè)置有關(guān)，通過實(shí)驗可以發(fā)現(xiàn)編號5、10的作業(yè)優(yōu)先級最高，調(diào)度策略將優(yōu)先處理這些作業(yè)，使得調(diào)度算法在實(shí)際上將資源傾斜。而兩種作業(yè)之間比較5GB的作業(yè)處理估計時間短，所以響應(yīng)時間要比10GB的作業(yè)短。這也證明了之前的想法，相同情況下執(zhí)行時間小的作業(yè)優(yōu)先處理。

6 結(jié)論（Conclusion）

本文分析了Hadoop集群下對數(shù)據(jù)本地性調(diào)度的改進(jìn)，在保證原算法的數(shù)據(jù)本地性的前提下，指出可以通過集成靜態(tài)優(yōu)先級搶占的方式提高優(yōu)先級高的作業(yè)響應(yīng)時間。通過獲得靜態(tài)優(yōu)先級，計算等待時間等參數(shù)，得到作業(yè)的優(yōu)先級。通過優(yōu)先級分配資源給各個作業(yè)，使得作業(yè)按照優(yōu)先級響應(yīng)。避免高優(yōu)先級的作業(yè)無法執(zhí)行。通過實(shí)驗可以發(fā)現(xiàn)這種調(diào)度策略，基本上達(dá)到了要求，即優(yōu)先級高的作業(yè)的響應(yīng)時間要小于優(yōu)先級低的，等待時間長的作業(yè)對應(yīng)的等待時間權(quán)值也會增加，而執(zhí)行時間小的作業(yè)在相同優(yōu)先級情況下優(yōu)先執(zhí)行。這個算法的設(shè)計使緊急程度較高的作業(yè)能優(yōu)先執(zhí)行，且盡量小的去影響其他作業(yè)。

這種集成了靜態(tài)優(yōu)先級搶占的本地性調(diào)度算法依然存在一些不足，例如添加了搶占機(jī)制后增加了系統(tǒng)開銷。實(shí)驗的作業(yè)功能和數(shù)據(jù)類型不全面，在大數(shù)據(jù)情況下的性能測試還不 是很多，實(shí)驗在普遍性上還有不足。接下來的工作重點(diǎn)

可以研究如何降低系統(tǒng)開銷，當(dāng)開銷為何值時可被接受等問題，在更大的實(shí)驗數(shù)據(jù)集上進(jìn)行改進(jìn)和驗證。

參考文獻(xiàn)（References）

[1] Thakkar，Shraddha1，Patel，Sanjay.Scheduling in Big Data Heterogeneous Distributed System Using Hadoop[C].Proceedings of International Conference on ICT for Sustainable Development，Gujaratp，2016：119-131.

[2] Khan，et al.Data Locality in HadoopCluster Systems[C].Proceedings of 11th International Conference on Fuzzy Systems and Knowledge Discovery，2014：720-724.

[3] Xiong，et al.Optimizing Data Placement in Heterogeneous Hadoop Clusters[J].Cluster Computing，2015（18）：1465-1480.

[4] Hadoop[EB/OL].http：//hadoop.apache.org.

[5] Shvachko K，et al.The hadoop distributed file system[C].Proceedings of the 26th IEEE Symposium on Mass Storage Systems and Technologies，IEEE，2010：1-10.

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

[7] 胡丹，于炯.Hadoop平臺下改進(jìn)的LATE調(diào)度算法[J].計算機(jī)工程與應(yīng)用，2014，50（4）：86-89.

[8] 何文峰.基于任務(wù)特征與公平策略的Hadoop作業(yè)調(diào)度算法研究[D].湖北：華中科技大學(xué)，2013.

[9] 燕明磊.Hadoop集群中作業(yè)調(diào)度研究[J].軟件導(dǎo)刊，2015，14

（4）：1-2.

[10] 儲雅，馬廷淮.云計算資源調(diào)度：策略與算法[J].計算機(jī)科學(xué)，2013，40（11）：8-13.

[11] 陶昌俊.Hadoop平臺的作業(yè)調(diào)度算法[D].安徽：中國科學(xué)技術(shù)大學(xué)，2015.

[12] B.Palanisamy，A.Singh，L.Liu，B.Jain."Purlieus：Locality-Aware Resource Allocation for MapReduce in a Cloud"[C].Proceedings of 2011 International Conference for High Performance Computing，Networking，Storage and Analysis，2011.

[13] Mohammad Hammoud，Majd F.Sakr.Locality-Aware Reduce

Task Scheduling for MapReduce[C].Proceedings of International

Conference on Cloud Computing Technology & Science，

Beijing，2011：570-576.

作者簡介：

王越峰（1990-），男，研究生.研究領(lǐng)域：嵌入式系統(tǒng).

陳福洪（1992-），男，研究生.研究領(lǐng)域：數(shù)據(jù)挖掘.