基于節點性能的Hadoop作業調度算法改進

馮興杰 賀 陽

(中國民航大學計算機科學與技術學院 天津 300300)

基于節點性能的Hadoop作業調度算法改進

馮興杰 賀 陽

(中國民航大學計算機科學與技術學院 天津 300300)

由于構成數據中心的計算設備一般都存在性能上的差異，但是Hadoop調度算法沒有考慮不同節點的性能差異，導致節點間出現“忙閑不均”的現象，影響作業的執行效率。針對如上問題，在系統分析Hadoop資源管理機制(Yarn)源代碼的基礎上，提出了節點性能評價指標，綜合考慮節點的硬件配置參數和運行過程中的動態性能指標。在此基礎上對Fair Scheduler調度算法進行改進，實現了基于節點性能的任務分配，整體上提高了所有節點的利用率。在Hadoop集群上的實驗表明，所提出的節點性能評價指標和對Fair Scheduler調度算法的改進，有效解決了節點的負載均衡問題，整體上提高了作業執行效率。

大數據 Hadoop Yarn 負載均衡 Fair Scheduler算法

0 引 言

隨著互聯網技術在生產、生活中的廣泛應用，以及各種移動設備和物聯網的快速發展，產生了數以P級的海量數據，并且數據還在以每兩年翻倍的速度快速增加。如此大的數據給存儲和計算帶來了巨大問題， 在大數據技術中，越來越多的企業開始使用Hadoop。Hadoop2.0引用Yarn框架，將原來的MapReduce中資源管理部分分離出來，減輕了MapReduce的壓力。Yarn由ResourceManager和NodeManager組成。

負載均衡技術是伴隨著集群的出現而產生的，它是集群系統實現技術中的關鍵部分，影響著集群的性能。隨著大數據技術的發展，大數據所具有的靈活性和用戶數量的龐大性等也給管理帶來很大問題，因此必須要采取合理而有效的資源調度策略和負載均衡措施來保證云計算的髙性能特性。

Hadoop的資源分配成為了決定運行速度的主要因素，Hadoop主要是針對節點性能相同的集群而設計，然而在現實中，由于服務器的更新和添加，所購服務器沒有辦法做到性能完全一致。

現階段的主要研究有企業應用型研究和學術型的研究：

在企業的應用型研究中，Google的負載均衡是基于DNS(域名系統)的，選擇與用戶在地理上接近的物理集群。Amazon從用戶的角度出發，把資源分配及每小時費用分為8類，綜合的考慮集群的性能及成本。Facebook的調度算法Fire Scheduler有較強擴展性，一般情況下是均衡資源量，使所有任務達到公平，但在只有一個任務的時候，會把所有資源分配給正在運行的任務。

在學術型的研究中分為以下幾類：

(1) 提出算法的研究: Zhenhua Guo[1]等針對不均衡環境下的計算對節點的資源利用不充分問題提出了一種新的資源調度算法。該算法將任務分配給有多余資源的節點，以減輕部分節點的負擔，從而達到高資源利用率。Yuanquan Fan[2]等提出的一種LBVP算法,LBVP算法提出了一種虛擬Partition,在Map處理完成后,數據輸出使用虛擬的Partition進行編號,ReduceTask在獲取數據時也根據這個編號進行。儲雅[3]等對資源調度問題進行深入剖析，根據現有云計算資源調度中的各種策略和算法歸納出4個熱點問題。

(2) MapReduce改進的研究：Zhuo Tang[4]等引入了按等級劃分的MapReduce,將大任務分為小任務以作為新任務來運行，從而減輕大任務帶來的負擔。VenkataSwamy[5]等人提出了h-MapReduce模型，用來評估Reduce任務過多的節點，以將重負載的任務進行分割，再分配到其他節點上執行。劉黨朋[6]等提出了基于MapReduce的負載均衡算法LBNP，以節點性能評價模型為核心，對Hadoop集群中各節點的計算能力進行評估，并依據性能估值在Reduce階段對輸入數據進行合理分配，從而達到均衡。

(3) 其他方面改進的研究：Ramakrishnan[7]等提出了基于對象的集群采樣法，對 Reduce的負載均衡進行研究，通過對Reduce的任務負載的評估，在其基礎上進行調度。DongshengLi[8]等對迭代操作中的數據分布情況進行收集，以此來引導下次任務迭代時對數據進行分割，從而提高負載均衡。陳若飛[9]等對在非本地任務執行前，對非本地性任務數據進行數據塊間的預取，保證了Hadoop任務的本地性。林常航[10]等通過結合Hadoop中數據放置與任務執行的關系，按不同節點對不同的任務的執行能力進行數據分配，該可以有效地縮短作業執行時間，提高時效性。Daeho Kim[11]等根據Hadoop的CPU核數及可用內存大小區分各節點能力來給每個任務分配內存，從而達到均衡。

目前，閱讀Hadoop源碼的人不在少數，在源碼上進行修改而達到相對性能均衡的論文很少，因為在源碼上進行改動的難度較大、耗時更長，但是在源碼上的改進是最直接、最能接近效果的方法。本文從Hadoop源碼入手，對Hadoop調度算法中的Fair Scheduler調度算法進行了改進，從而有效地緩解了Hadoop系統負載不均衡的情況，因此本文的出發點很有研究意義。

1 基于節點性能的Hadoop作業調度算法改進

1.1 Fair Scheduler工作原理

資源調度器是Hadoop Yarn中最核心的組件之一，它直接決定著資源的分配，也決定著節點的負載情況，Hadoop自身所帶3種調度算法，分別是：FIFO Scheduler、Capacity Scheduler、Fair Scheduler。Hadoop2.0開始將默認的調度算法FIFO Scheduler改為Capacity Scheduler，隨著Hadoop版本的演化，Capacity Scheduler 和Fair Scheduler的功能越來越完善，Fair Scheduler調度算法幾乎包括了Capacity Scheduler的所有功能，并且Fair Scheduler支持多種調度策略[12]。因此，本文選中Fair Scheduler。

Hadoop整個系統相對龐大，通過對Hadoop任務運行過程中的代碼追蹤，得到了詳細的Hadoop架構。并且對重要的調度算法Fair Scheduler的追蹤進行詳細分析得到如圖1所示的流程圖。

圖1 Fair Scheduler流程圖

Fair Scheduler調度算法同樣遵循Hadoop調度器的三級調度原則，即當有空閑資源出現時，先從節點隊列中選擇一個節點，再從選中的節點中選擇一個優先級高的任務，然后再選中空閑資源分配給任務。而節點的性能不均衡問題顯然應當從節點排序入手，節點的排序變化直接影響了任務在哪個節點上執行，也是解決所出現的負載是否均衡問題的關鍵點，因此本文從節點的排序(圖中灰色)這一部分入手。

1.2 基于節點性能的Hadoop作業調度

算法的改進過程分為兩部分。一部分為確定評價指標，對于每個節點而言，服務器是其主要構成設備，所以確定其指標主要有兩大因素，即靜態指標和動態指標，靜態指標即服務器本身的硬件參數;動態指標即在運行過程中的各資源使用狀態。另一部分即對算法的改進，主要是對Fair Schedule算法中對節點排序部分進行改進。

1.2.1 節點性能評價指標

在性能不同的節點組成的集群中，節點性能并不能完全相同。如果作為相同性能的節點，會造成性能低的節點與性能高的節點可能接受同樣的任務，直接導致性能低節點運行時間長，性能高節點運行時間短，運行過程中會發生性能高節點等待性能低節點運行結果，從而浪費性能高節點的資源，導致運行時間變長。因此研究節點性能指標有重要意義。

對節點性能進行分析，總結出影響節點的性能指標主要有兩大因素：靜態因素和動態因素。靜態因素為可控因素，其組成不會發生變化，也起到主要作用，靜態因素中起重要作用的兩個因素為：CPU和內存。CPU和內存容量大必然會運行速度較快。因此主要從CPU和內存來考慮其靜態性能指標。

靜態性能指標相對好處理，主要考慮節點的CPU容量在集群中所占的百分比以及內存容量在集群中所占的百分比，所占百分比大的即為性能高節點。將每個節點的CPU所占百分比和內存所占百分比做歸一化處理，得到CPU和內存的綜合因素在集群中的所占比重。即得到節點的靜態性能指標。

主要考慮CPU所占集群百分比和內存所占集群百分比。單個節點CPU大小比上集群總的CPU大小，即為CPU所占集群百分比。同樣的方式求得內存所占集群百分比，再將兩項綜合。

(1)

其中，i代表某節點，s代表整個集群，i.cpu代表i節點的cpu核數，i.memory代表i節點內存的大小，h.index.i代表節點i在集群中的硬件指標量。

根據上述所求得的單個節點性能所占集群百分比，求出所有結點性能百分比的和：

(2)

其中n代表節點個數，sum求出各節點的指標量總合。

再針對單個節點求得單個節點的性能百分比在集群性能百分比中所占的百分比，即求得單個節點性能在集群總性能中的百分比：

(3)

動態因素主要由運行過程中各項性能指標的使用情況來判斷，因為運行過程中每個節點的任務量不盡相同，加上每個節點的功能也不完全相同(主節點上要運行Master任務，相對來說任務量會偏重)。還有一種情況是新節點和舊節點因為使用的時間不同，導致新節點會性能比較高。因此動態因素也是檢測性能指標的一個重要因素。

動態性能指標：首先用相同的任務對單個節點進行測試，用ganglia進行單個節點運行過程中的CPU和內存的使用數據采集，再將單個節點采集到的CPU和內存數據分別取得平均值，最后將各節點采集到的CPU和內存使用率分別相加，以求得各節點的使用率在集群數據中所占的百分比。

在動態運行過程中，用ganglia對節點運行過程中的CPU使用率進行10次采集，取平均值：

(4)

其中i.cpu為對節點i運行過程中CPU的使用百分比的一次采集。

在動態運行過程中，對單個節點運行時的內存使用率進行10次采集，取得其平均值：

(5)

其中，i.memory為對節點i運行過程中內存的使用百分比的一次采集。

將單個節點的運行時CPU平均使用率和運行時內存平均使用率進行綜合，得到其單個節點運行過程中的CPU和內存的綜合使用率，因為資源的未使用率與性能的高低是成正比的，所以在使用率的基礎上求得單個節點運行過程中資源的未使用率：

(6)

其中，pro.index.i求得的是節點i內存和CPU剩余量的指標。

最后將所有節點的未使用率綜合考慮，求得單個節點對于集群的資源未使用率：

(7)

其中n為節點個數，pro.i即為節點i在運行過程中未使用資源所占集群的百分比。

各節點綜合性能指標的計算，要將動態指標和靜態指標全部考慮進去，并且能達到希望的最佳效果，因此在動態指標和靜態指標前加參數以顯示兩項指標對整體的權重。所以綜合考慮結果計算公式：

perf.index.i=a1×hard.i+a2×pro.i

(8)

其中，hard.i與pro.i由式(3)、式(7)計算得到，perf.index.i即為節點i的綜合性能指標，各節點perf.index.i值的比值即為各節點的權重比，由a1和a2決定兩部分因素的權重。

1.2.2Hadoop作業調度算法改進

Hadoop默認的是所有節點性能相同，然而由于所構成服務器的時間不同，使用情況不同以及每個節點的功能不同都會造成節點性能的不均衡。假設兩臺服務器，一臺服務器a內存總量100，可用內存量為40，另一臺服務器b內存總量40，可用內存30。這種情況下默認的Hadoop系統會選擇a服務器來運行下一個應用程序，然而服務器a的可用內存百分比為30%，而服務器b的可用內存百分比為75%，可見服務器a比較緊張。因此會在運行過程中發生資源不能很好利用，負載不均衡等情況。

根據這種情況，在考慮集群靜態性能指標和動態性能指標的情況下，加入了在任務執行時考慮內存使用率這一因素，對每個節點任務執行時的內存使用率作對比進行排序，使得內存未使用率高的節點優先能安排到任務。并且事先對各節點進行測試，根據上一小節的動態性能指標的計算方法對各節點增加相應的權重，運行效率高的節點的權重增加，使其更容易分配到任務，從而提高效率，降低了上面這種情況發生的概率，從而達到了均衡的目的。

Compare(n1,n2)是FairScheduler算法中排序算法中的一個方法，作為排序的重要部分，Radio1和Radio2為兩個作比較的節點的未使用內存資源百分比。在比率的基礎上加上兩個節點的權重，即上一小節的節點性能指標所得出的各節點權重，再進行比較。

算法偽代碼如下：

Sort(nodeIdList){

Compare(n1,n2){

//對比兩個節點

Radio1=n1.getAvailableMemory()/n1.getTotalMemory();

//可用節點百分比

Radio2=n2.getAvailableMemory()/n2.getTotalMemory();

R1=Radio1*n1.Weight;

//加上權重

R2=Radio1*n2.Weight;

If(R1

R2排在前面;

}else {

R1排在前面;

}

}

}

1.3 算法的實現過程

1.3.1 源碼改進框架圖

Hadoop由Java實現，整個系統相對龐大，源碼改進能最直接地達到效果。入手源碼會有點難度，入門后就會有一個整體的印象。只有在對Hadoop整體都了解的情況下才能去對源碼改進，否則Hadoop不能啟動。對源碼改進需要做多次實驗驗證其有效性。本研究把對Hadoop改動的類做了粗略整理，如圖2所示。

圖2 源碼改進框架圖

主要更改的類為FairScheduler、DefaultResourceCalcultor、DominantResourceCalculator以及ResourceCalculator，其中最主要的更改在ResourceCalculator類中，這個類是根據節點未使用資源量進行排序的關鍵類。

1.3.2 重新編譯源碼的過程

編譯過程如圖3所示。

圖3 源碼編譯過程圖

Hadoop的重新編譯過程以及啟動過程不像一些成熟的系統，過程比較復雜，在hadoop-src中有BUILDING.txt文檔對各插件版本要求做了介紹。在干凈的Hadoop環境下，嚴格按照流程圖中的步驟才可能成功，對Hadoop的重新編譯過程加深了對Hadoop整個系統的理解。

2 實 驗

2.1 實驗環境

為了驗證此想法的正確性，本研究用三臺服務器搭建了Hadoop集群，Hadoop版本為2.5.2，由3臺不同性能的服務器組成，三臺服務器都作為存儲和運算節點。Name Node在Master節點上(即HDFS主節點)，ResourceManager在Slave1節點上(即Yarn主節點)，主節點分開，主要防止某一節點太過繁忙，服務器的各項參數如表1所示。

表1 節點性能參數表

由表1可以看出，集群的總CPU核數為18，內存總量為17 GB,硬盤總量為1.7 TB。為了更方便看到直觀效果，用ganglia來進行集群監控(Slave1為ganglia主節點)。ganglia主要用來監控系統性能：CPU、內存、硬盤利用率、I/O負載、網絡流量等。由曲線圖來展現各節點的當前各資源使用狀態，對本實驗進程中調整、分配各項資源，提高集群的整體性能起到了非常重要的作用。

圖4為運行過程中對每個節點的運行情況的收集，圖中縱坐標為每分鐘負載值，橫坐標為運行時間。由于Slave2配置最低，且Hadoop分配任務為平均分配，使得slave2過于繁忙，運行過程中狀態呈現紅色(即圖中Slave2為深灰色)，1 GB數據大約運行時間為9分鐘(運行時間從08:57:21到09:06:19)，而Slave2節點每分鐘負載最高達到了10。高性能的Master節點每分鐘負載最高達到了5。Slave1節點的每分鐘負載最高只達到了2。圖4能清楚地表明Master和Slave1節點資源沒有能夠有效利用。

圖4 改進前各節點運行狀態圖

2.2 節點性能指標計算

節點性能指標計算的兩部分中，硬件參數根據節點性能參數表由1.2.1節所示式(1)-式(3)計算得到。

而動態指標中用到的的數據在任務執行之前采集，先用wordcount對每個節點單獨進行測試，測試過程中對每個節點進行采集資源信息，每個節點同一時間的CPU和內存使用量為一組數據，共采集10組。利用1.2.1節中節點性能評價指標方法來進行各節點的性能評定，從而確定各節點的權重，其中所采集的運行過程中CPU及內存的使用情況數據如表2、表3所示。

表2 運行中cpu使用情況表

表3 運行中memory使用情況表

T1到T10分別表示10個時間段，最右列為名節點的名字，中間為單個時間段在單個節點上的資源使用率。利用這些數據，根據式(4)-式(7)計算得到各節點運行過程中CPU和內存的使用情況，即動態性能指標。式(8)中的a1和a2，由于硬件的性能指標占主要地位，而動態性能會因運行的時間、運行的任務不同而發生不穩定變化，因此將硬件性能指標的比率設置為0.6，而動態性能指標的比率設置為0.4，即a1=0.6，a2=0.4。根據前面計算得到的靜態性能與動態性能相結合，得到三個節點的性能比約為3∶3∶1。因此將Master和Slave1的初始權重設置為3，Slave2的初始權重設置為1。

2.3 實驗結果

根據權重計算方法算得的結果，將Master和Slave1的初始權重設為3，Slave2的初始權重設為1。對改進后的Yarn的源碼用maven進行重新編譯，重新啟動Hadoop后再次用同樣的1GB數據進行實驗，實驗結果如圖5所示。

圖5 改進后各節點運行狀態圖

由圖5可看到相對于改進前得到了很大的改善，每分鐘負載最大的節點為Slave1，負載值為6，Slave1節點為高性能節點，所以相對于改進前的負載最大的是Slave2的低性能節點這種情況，已經得到了改善。改進后，1GB數據的任務大約運行時間為5分鐘(運行時間從13:44:24到13:49:31)，相比較改進前的運行時間得到了很大的提高，同時緩解了Slave2的運行壓力，每分鐘最大的負載為2。整體來看運行時間有很大減少，大概節約了44%。Slave2節點也從之前的最大的每分鐘負載10降到了2。

從結論分析，由于改進前給不同性能的節點分配了相同的任務，導致性能最差的Slave2節點太過繁忙，且其他節點中間結果出來后要等待Slave2而拖延整體的運行時間。改進后Slave2的任務明顯減少，性能高的節點Slave1充分發揮了其性能，從而使運行時間大大減少，因此證明了結論的正確性。

3 結 語

本文對Hadoop2.0的資源調度器Yarn進行了研究，結合服務器靜態指標和動態指標確定了節點的性能評價指標，且從源碼的角度討論了負載均衡問題，給出了源碼中FairScheduler的流程，提出了對FairScheduler的改進算法，并且在搭建的集群上進行了實驗，結果證明在Hadoop系統中加入此改進算法，對負載均衡有很好的效果，同時提高了利用率。負載均衡問題是集群運行效率的一個重要問題，改進后對Hadoop集群的負載不均衡問題確實有很大的改善，然而現實情況中影響負載均衡的因素眾多，例如：數據在集群上的分布，任務提交節點以及主節點要有一部分資源的占用等問題。下一步的研究要在本研究方法的基礎上加入更多的考慮因素，結合hdfs的分布情況使集群的負載更加均衡。

[1]GuoZ,FoxG.ImprovingMapReduceperformanceinheterogeneousnetworkenvironmentsandresourceutilization[C]//Proceedingsofthe2012 12thIEEE/ACMInternationalSymposiumonCluster,CloudandGridComputing(CCGrid2012).IEEEComputerSociety,2012:714-716.

[2]FanY,WuW,CaoH,etal.LBVP:aloadbalancealgorithmbasedonvirtualpartitioninHadoopcluster[C]//2012IEEEAsiaPacificCloudComputingCongress,2012:37-41.

[3] 儲雅,馬廷淮,趙立成.云計算資源調度：策略與算法[J].計算機科學,2013,40(11):8-13.

[4]TangZ,ZhouJ,LiK,etal.AMapReducetaskschedulingalgorithmfordeadlineconstraints[J].ClusterComputing,2013,16(4):651-662.

[5]MarthaVS,ZhaoW,XuX.h-MapReduce:aframeworkforworkloadbalancinginMapReduce[C]//Proceedingsofthe2013IEEE27thInternationalConferenceonAdvancedInformationNetworkingandApplications.IEEEComputerSociety,2013:637-644.

[6] 劉黨朋.不均衡環境下面向Hadoop的負載均衡算法研究[D].北京:北京郵電大學,2015.

[7]RamakrishnanSR,SwartG,UrmanovA.BalancingreducerskewinMapReduceworkloadsusingprogressivesampling[C]//ProceedingsoftheThirdACMSymposiumonCloudComputing,2012:1-14.

[8]LiD,ChenY,HaiRH.Skew-awaretaskschedulinginclouds[C]//Proceedingsofthe2013IEEESeventhInternationalSymposiumonServiceOrientedSystemEngineering.IEEEComputerSociety,2013:341-346.

[9] 陳若飛.Hadoop作業調度本地性的研究與優化[D].北京:北京交通大學,2015.

[10] 林常航,郭文忠,陳煌寧.針對Hadoop異構集群節點性能的數據分配策略[J].小型微型計算機系統,2015,36(1):83-88.

[11]KimD,ChoiE,HongJ.Systeminformation-basedHadooploadbalancingforheterogeneousclusters[C]//Proceedingsofthe2015ConferenceonResearchinAdaptiveandConvergentSystems.ACM,2015:465-467.

[12] 董西成.Hadoop技術內幕：深入解析YARN架構設計與實現原理[M].北京:機械工業出版社,2014.

IMPROVEMENT OF SCHEDULING ALGORITHM ON HADOOP BASED ON NODE PERFORMANCE

Feng Xingjie He Yang

(SchoolofComputerScienceandTechnology,CivilAviationUniversityofChina,Tianjin300300,China)

Because the computing devices that make up the data center generally have different performance, Hadoop scheduling algorithm does not consider the performance difference of different nodes, resulting in the phenomenon of “busy and idle inhomogeneous” between nodes, affecting the efficiency of job execution. In view of the above problem, based on the analysis of the source code of Hadoop resource management mechanism (Yarn), the node performance evaluation index is proposed. Considering the hardware configuration parameters and the dynamic performance indexes, the Fair Scheduler scheduling algorithm is improved, and the task allocation based on node performance is realized, and the utilization rate of all the nodes is improved as a whole. The experiments on Hadoop cluster show that the proposed node performance evaluation index and the improvement of Fair Scheduler scheduling algorithm effectively solve the problem of node load balancing and improve the efficiency of job execution as a whole.

Big data Hadoop Yarn Load balancing Fair Scheduler algorithm

2016-04-01。國家自然科學基金委員會與中國民用航空局聯合基金項目(U1233113)；國家自然科學基金項目(61301245，61201414)。馮興杰，教授，主研領域：智能算法，智能信息處理理論與技術。賀陽，碩士生。

TP302.7

A

10.3969/j.issn.1000-386x.2017.05.039