Hadoop集群環境下本地性調度算法改進

王越峰+陳福洪

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

關鍵詞：數據本地性；靜態優先級搶占；作業響應時間

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

1 引言（Introduction）

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

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

2 Hadoop平臺（Hadoop platform）

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

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

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

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

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

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

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

4 集成靜態優先級搶占的本地性調度算法（Local

scheduling algorithm with integrated static priority

preemption）

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

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

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

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

waittime=nowtime-submittime （1）

在公式（1）中nowtime和submittime分別表示系統的現在時間和作業的提交時間，通過兩者做差的方式得出作業在作業池中的等待時間。

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

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

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

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

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

performance analysis）

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

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

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

6 結論（Conclusion）

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

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

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

參考文獻（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架構設計與實現原理[M].北京：機械工業出版社，2013.

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

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

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

（4）：1-2.

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

[11] 陶昌俊.Hadoop平臺的作業調度算法[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-），男，研究生.研究領域：嵌入式系統.

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