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

1、計劃類別 項目編號 項目技術報告課題名稱 項目主持人 承擔單位 題目：Hadoop集群環(huán)境下本地性調度算法改進Hadoop集群環(huán)境下本地性調度算法是提高數據本地性的算法。算法本質是提高數據本地性，減少數據傳輸時間，減少集群的網絡I/O，提高資源利用率。由于調度算法采用FIFO方式，當前作業(yè)數據量大時將影響其他緊急性高的作業(yè)響應時間，降低系統(tǒng)性能。本文提出一種新的調度策略，即在保證原算法數據本地性的前提下，集成靜態(tài)優(yōu)先級的搶占調度策略。實驗結果表明，在相同的數據集上，采用集成靜態(tài)優(yōu)先級搶占的調度策略，優(yōu)先級高的作業(yè)響應時間較優(yōu)先級低的作業(yè)響應時間減少。關鍵詞：數據本地性；靜態(tài)優(yōu)先級搶占；作業(yè)響應

2、時間1 引言（Introduction）在大數據持續(xù)發(fā)展的今天Hadoop集群環(huán)境下調度算法的研究越來越受到重視。對于作業(yè)調度算法的改進一般都是為了減少作業(yè)的完成時間，在同樣資源的基礎上減少系統(tǒ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è)的資源，達到可以降

3、低緊急作業(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和分布式計算框架MapReduce3計算架構組成。Hadoop平臺在大數據的背景下發(fā)展飛速，在這種背景下大量數據出現了中心聚集的問題，每日的數據處理、作業(yè)處理在逐步上升。作業(yè)調度性能是衡量

4、大型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是Hado

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

6、致節(jié)點負載不均勻。所以越來越多的研究者從多個方面對調度算法進行了深入研究。為了研究資源調度策略，研究者通過調查大量數據和不同的方向9從其他研究者的工作中，將調度分成五類：（1）本地性感知調度（Data Locality Aware Schedulers）（2）可靠性感知調度（Speculative Execution Based Schedulers）（3）資源競爭感知調度（Resource Contention Aware Schedulers）（4）性能管理感知調度（Performance Management Based Schedulers）（5）能源與完成時間感知調度（Energy

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

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

9、將長作業(yè)的數據放到負載最小的節(jié)點上。但是這種算法仍然沒有考慮到Reduce任務的本地性要求。 Hammoud等人提出本地化感知的Reduce任務調度算法LARTS12（Locality-Aware Reduce Tasl Scheduling for MapReduce）以解決Reduce任務數據本地性的問題。LARTS在Map任務完成到一定的閾值后啟動Early Shuffle機制。這種調度策略利用Early Shuffle的優(yōu)點并且兼顧了Reduce任務的數據本地性。但是閥值的設定需要根據不同類型的作業(yè)設定，而且存在一定的誤差。4 集成靜態(tài)優(yōu)先級搶占的本地性調度算法（Localschedu

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

11、優(yōu)先級搶占策略，緊急程度高的作業(yè)有著較高的優(yōu)先級，它可以搶占緊急程度低的且優(yōu)先級低的作業(yè)的處理資源。使得調度策略更加的有針對性，提高調度策略對高優(yōu)先級任務的關注，使計算資源優(yōu)先分配。確保緊急任務緊急處理，減少高優(yōu)先級任務的響應時間。一般的本地性調度算法都是使用FIFO算法的調度方式，也就是先到的作業(yè)先進行處理，這樣的調度算法缺少對任務緊要程度的關注。所以集成靜態(tài)優(yōu)先級搶占的本地性調度策略首先要對優(yōu)先級進行定義。每個作業(yè)在提交時設置獨立的參數staticpriority，用來表示作業(yè)的緊要程度。作業(yè)越緊要越優(yōu)先staticpriority值越高。但是如果僅僅考慮到作業(yè)的優(yōu)先性問題，有可能導致作業(yè)

12、優(yōu)先級低且數據量很小的作業(yè)一直被優(yōu)先級高數據量很大的作業(yè)搶占，導致優(yōu)先級低的作業(yè)一直無法執(zhí)行。所以本文在定義優(yōu)先級的時候加入新的參數作業(yè)的等待時間waittime。waittime=nowtime-submittime （1）在公式（1）中nowtime和submittime分別表示系統(tǒng)的現在時間和作業(yè)的提交時間，通過兩者做差的方式得出作業(yè)在作業(yè)池中的等待時間。為了防止上文中提到的優(yōu)先級低的作業(yè)無法執(zhí)行的問題為作業(yè)的優(yōu)先級加入等待時間這個影響因素。但是即使加上了作業(yè)的等待時間也會出現等待時長過長的問題。比如優(yōu)先級較高的作業(yè)數據非常大，Map任務數量也較多。系統(tǒng)在通過原本地性調度策略后，作業(yè)的處

13、理時間也非常大。在處理的過程中可能會有優(yōu)先級相同且數據小，Map任務個數少的作業(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)先級。、表示其中各項參數所占比例，對于不同種的數據類型和

14、作業(yè)將取不同的數值，以達到對作業(yè)優(yōu)先性能的標準。其中estimatetime的確定要根據不同的本地性調度算法出發(fā)，針對算法的本地性調度得出估計時間。5 實驗結果及性能分析（Experimental results andperformance 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

15、的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ā)現編號5、10的作業(yè)優(yōu)先級最高，調度策略將優(yōu)先處理這些作業(yè)，使得調度算法在實際上將資源傾斜。而兩種作業(yè)之間比較5GB的作業(yè)處理估計時間短，所以響應時間要比10GB的作業(yè)短。這也證明了之前的想法，相同情況下執(zhí)行時間小的作業(yè)優(yōu)先處理。6 結論（Conclusion）本文分析了Hadoop集群下對數據本地性調度的改進，在保證原算法

16、的數據本地性的前提下，指出可以通過集成靜態(tài)優(yōu)先級搶占的方式提高優(yōu)先級高的作業(yè)響應時間。通過獲得靜態(tài)優(yōu)先級，計算等待時間等參數，得到作業(yè)的優(yōu)先級。通過優(yōu)先級分配資源給各個作業(yè)，使得作業(yè)按照優(yōu)先級響應。避免高優(yōu)先級的作業(yè)無法執(zhí)行。通過實驗可以發(fā)現這種調度策略，基本上達到了要求，即優(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è)功能和數據類型

17、不全面，在大數據情況下的性能測試還不 是很多，實驗在普遍性上還有不足。接下來的工作重點可以研究如何降低系統(tǒng)開銷，當開銷為何值時可被接受等問題，在更大的實驗數據集上進行改進和驗證。參考文獻（References）1 Thakkar，Shraddha1，Patel，Sanjay.Scheduling in Big Data Heterogeneous Distributed System Using HadoopC.Proceedings of International Conference on ICT for Sustainable Development，Gujaratp，2016：119

18、-131.2 Khan，et al.Data Locality in HadoopCluster SystemsC.Proceedings of 11th International Conference on Fuzzy Systems and Knowledge Discovery，2014：720-724.3 Xiong，et al.Optimizing Data Placement in Heterogeneous Hadoop ClustersJ.Cluster Computing，2015（18）：1465-1480.4 HadoopEB/OL.http：/.5 Shvachko K，et al.The hadoop distributed file systemC.Proceedings of the 26th IEEE Symposium on Mass Storage Systems and Technologies，IEEE，2010：1-10.6 董西成.Hadoop技術內幕：深入解析MapReduce架構設計與實現原理M.北京：機械工業(yè)出版社，2013.7 胡丹，于炯.Hadoop平臺下改