Hadoop集群環(huán)境下本地性調度算法改進

王越峰+陳福洪

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

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

中圖分類號：TP316.4 文獻標識碼：A

1 引言（Introduction）

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

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

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]計算架構組成。

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

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

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

（1）本地性感知調度（Data Locality Aware Schedulers）

（2）可靠性感知調度（Speculative Execution Based Schedulers）

（3）資源競爭感知調度（Resource Contention Aware Schedulers）

（4）性能管理感知調度（Performance Management Based Schedulers）

（5）能源與完成時間感知調度（Energy and Makespan Aware Schedulers）

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

3 本地性調度算法（Local scheduling algorithm）

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

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

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

scheduling algorithm with integrated static priority

preemption）

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

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

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

但是如果僅僅考慮到作業(yè)的優(yōu)先性問題，有可能導致作業(yè)優(yōu)先級低且數(shù)據(jù)量很小的作業(yè)一直被優(yōu)先級高數(shù)據(jù)量很大的作業(yè)搶占，導致優(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任務數(shù)量也較多。系統(tǒng)在通過原本地性調度策略后，作業(yè)的處理時間也非常大。在處理的過程中可能會有優(yōu)先級相同且數(shù)據(jù)小，Map任務個數(shù)少的作業(yè)等待時間變長。在Hadoop集群環(huán)境下不能像其他系統(tǒng)一樣直接搶占運算資源，因為其中涉到了Map任務完成后的中間值問題，和Reduce任務的中間拷貝等問題。無法直接搶占原有作業(yè)的運算資源。所以作業(yè)池中的優(yōu)先級定義就特別重要。在加入等待時間的基礎上再加入作業(yè)的估計執(zhí)行時間estimatetime如公式（2）。

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

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

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

5 實驗結果及性能分析（Experimental results and

performance analysis）

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

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

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

6 結論（Conclusion）

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

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

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

參考文獻（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技術內幕：深入解析MapReduce架構設計與實現(xiàn)原理[M].北京：機械工業(yè)出版社，2013.

[7] 胡丹，于炯.Hadoop平臺下改進的LATE調度算法[J].計算機工程與應用，2014，50（4）：86-89.

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

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

（4）：1-2.

[10] 儲雅，馬廷淮.云計算資源調度：策略與算法[J].計算機科學，2013，40（11）：8-13.

[11] 陶昌俊.Hadoop平臺的作業(yè)調度算法[D].安徽：中國科學技術大學，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-），男，研究生.研究領域：嵌入式系統(tǒng).

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