適應異構集群的Mesos多資源調度DRF增強算法

柯尊旺 于炯 廖彬

摘要：云計算集群環境下多資源分配的公平性是考量資源調度子系統最重要的指標之一，DRF作為通用的多資源公平分配算法，在異構異質的集群環境下可能有失公平性。在研究Mesos框架中DRF多資源公平分配算法的基礎上，設計并實現了增加機器性能評估影響因子的meDRF分配算法。將計算節點的機器性能得分，作為DRF主導份額計算的因子，使得計算任務有均等的機會獲得優質計算資源和劣質計算資源。通過選取Kmeans、Bayes及PageRank 等多種作業進行實驗，實驗結果表明：meDRF較DRF分配算法更能體現多資源分配的公平性，且資源分配具有更好的穩定性，能有效提高系統資源的利用率。

關鍵詞：資源分配；DRF分配算法；公平性；Mesos

中圖分類號：TP311 文獻標志碼：A

Abstract：The fairness of multiresource allocation is one of the most important indicators in the resource scheduling subsystem， Dominant Resource Fairness （DRF）， as a general resource allocation algorithm for multiresources scenarios， it may be unfair in heterogeneous cluster environment. On the basis of the research on the DRF multiresource fair allocation algorithm under Mesos framework environment， meDRF allocation algorithm was designed and implemented to evaluate the influence factors of the performance of the server. The machine performance scores of computing nodes， as the dominant factor of DRF share calculation， made computing tasks have equal chance to obtain high quality computing resources and poor computing resources. Experiments were conducted by using Kmeans， Bayes and PageRank jobs under Hadoop. The experimental results show that， compared with DRF allocation algorithm， the meDRF algorithm can reflect more fairness of the allocation of resources， and the allocation of resources has better stability， which effectively improves the utilization of system resources.

Key words：resource allocation； Dominant Resource Fairness （DRF） allocation algorithm； fairness； Mesos

0 引言

隨著云計算、大數據等新技術及應用的高速發展以及智能終端爆炸式增長，以Hadoop[1]、Spark[2]、Cloudra及Strom等為代表的大數據計算框架得到了快速發展。但是，傳統數據中心的資源管理模式無法有效應對種類繁多的上層計算框架的個性化資源管理需求。在這樣的背景下，作為下一代數據中心的創新者，軟件定義數據中心（Software Defined Data Center，SDDC）[3]將服務器進行虛擬化、軟件化數據中心的一切物理資源，并適應上層應用程序不斷變化的資源需求，動態地進行資源分配。SDDC通過整合多種計算資源實現資源的統一管理和調度，在計算資源有限的情況下，為確保各計算任務節點的利益最大化，資源調度子系統應該提供一種公平的資源分配策略，使得各計算任務節點具有均等的機會獲得計算資源來完成任務。另一方面，不同的計算任務（或作業）對不同資源類型的需求也存在著不同程度的差異，如：計算密集型的MapReduce[4-10]作業更多地需要CPU資源，而I/O密集型的MapReduce作業則需要更多的磁盤及內存資源。因此，SDDC集群中資源調度子系統需要解決多類型資源分配的公平性問題。

當前，資源公平分配方面的研究工作及實踐主要集中在單資源類型的場景，以至于在多種資源類型和異質資源混合的應用場景下，仍采用首先將單資源進行抽象，然后再進行資源的分配工作，如Hadoop的slotbased[11]公平調度策略[12-13]。在單資源公平分配場景下，maxmin fairness[14-15]是最通用的單資源公平分配算法，它通過使資源分配向量最小值的最大化，確保任何資源請求不被餓死，是一種優秀的兼顧有效性和公平性的分配策略。而在多資源類型公平分配方面，DRF（Dominant Resource Fairness）[16]是一種針對多資源應用場景的maxmin fairness算法。DRF通過對“主導資源份額（Dominant Share）”進行maxmin fairness，比較合理地解決了多資源類型的分配公平性問題。經過大量的測試工作表明：DRF算法比slotbased算法更能夠滿足多資源分配的應用場景，資源分配的效率及公平性表現更佳[17]。

在DRF的實踐中，資源調度管理框架Mesos[18-19]采用了DRF作為它的多資源公平分配算法，在集群節點的計算資源同構（即集群中的節點配置不存在差異）的情況下，DRF算法表現出優秀的性能，并能很好地權衡資源調度的有效性和公平性。但在實際的應用場景中，同一集群中的不同節點之間的資源質量可能存在著不同程度的差異，而DRF算法并沒有考慮因為計算資源質量的差異性而導致的資源分配不公平性問題。為了改進DRF算法對異構集群環境的適應能力，本文通過增加節點性能評估影響因子，提出一種增強的DRF資源分配算法meDRF，使資源調度的各上層應用計算任務之間能夠有均等的機會分配到滿足需求的計算資源。

1 DRF分配算法

1.1 DRF算法簡介

DRF資源分配是一種改進的maxmin fairness算法，能在多資源類型的集群環境中進行資源的公平分配，DRF是一種基于“主導份額（Dominant Share）”的多資源公平分配策略[17]。DRF公平分配算法具有4個性質[20]：

1） 鼓勵共享（Sharing Incentive）。即集群中的上層應用之間通過共享自己的資源而不是獨占資源來達到更高的資源利用效率。如：在一個具有n個計算任務的集群節點中，每個計算任務最多只能分配1/n的資源。

2） 欺騙屏蔽（Strategyproofness）。DRF能夠防止計算任務謊報資源需求量，企圖通過欺騙的手段而獲取更多資源的行為。

3） 無嫉妒性（Envyfreeness）[21]。任何的計算任務都不能在獲得計算資源后，通過已有的資源，去獲得（或交換）另一個任務的資源。

4） 帕累托效率性（Pareto Efficiency）。集群中的所有計算任務都不能夠在不減少其他任務的資源擁有量的前提下增加自己的資源擁有量。

DRF算法的核心思想是根據每個計算任務的資源需求向量和系統資源總向量，求出各個計算任務的主導份額。該主導份額所對應的主導資源是該計算任務最重要的計算依據。通過平衡各個計算任務的主導份額，來確定每個計算任務的子任務數量，最終得到每個計算任務的資源配額向量。DRF算法描述如下：

1.2 DRF算法的不足

在實際的集群環境中，集群中的計算機可能不是同一時間采購，或者機器品牌及機器型號之間存在著差異。在實際的資源分配過程中，即使分配相同數量的資源，但是由于節點之間的性能差異，分配方案之間存在較大的差異，將會有悖公平性原則[12]。DRF算法并沒有考慮這種因計算資源性能的差異而導致的資源分配不公平性的問題，即使分配相同數量的資源，性能高的資源在任務的執行效率上比性能差的資源高。但是在DRF分配算法中，主導份額的計算只與資源數量有關，而與資源的質量無關。計算任務i的主導份額如式（2）所示：

式中：j表示資源類別，k表示資源種類數量，Rj表示資源類別j的資源總量，Wi表示計算任務的權重，Rui， j表示計算任務i已分配的j類別資源總量。

根據式（2）可知計算任務i的主導份額為該計算任務已獲得的各類型資源與系統中該類型資源總量的比值中的最大值，如果計算任務存在加權，則主導份額與權重成反比。式（2）中無法體現出集群中節點之間的性能區別。如果有一個計算任務拿到大量的優質資源，而另一個拿到大量的劣質資源，雖然它們主導份額相同，但任務實際的執行效率和運行時間卻相差甚遠，這將導致資源分配的不公平，這種情況違反了DRF算法的Envyfreeness性質。

2 meDRF分配算法

本文提出的meDRF分配算法，是在DRF算法基礎上增加了機器性能評估影響因子，使得計算任務有均等的機會獲得優質計算資源和劣質計算資源，而不是長期持有優質或劣質計算資源。本算法的核心思想是：首先給每個集群節點的計算機進行性能評估打分并按照所得分值從小到大排序，再計算出每個計算任務的主導份額并從小到大排序，然后交替使用優質資源、劣質資源為計算任務的子任務進行資源分配，盡可能地使所有計算任務的主導份額趨向于平衡。

假設集群環境中存在n個計算節點，Qk表示機器k的性能評估得分，ηk代表機器k的性能評估得分與平均得分之比，Si表示計算任務i的主導份額，Rkj表示機器k上j類型資源的總量，Ruki， j表示計算任務i在機器k上已經分配的j類型資源數量，Rck， j表示機器k上j類型資源可分配的數量，Wi表示計算任務i的權重。

在Mesos中，使用框架這一術語表示計算任務。圖1中灰色區域代表各框架的主導份額，dS1表示框架2和框架1的主導份額差，dS2表示框架3和框架2的主導份額差。為均衡不同框架間的主導份額，框架1在執行第1次分配計算時，在資源足夠的情況下分配資源給子任務使其主導份額增加dS1，此時與框架2的主導份額相等。然后框架1進行第2次分配計算時框架2將執行第1次分配計算，框架1和框架2都使它們各自的主導份額增加dS2，此時與框架3的主導份額相等。綜上所述，meDRF分配算法的流程描述如下：

1） 對每個集群節點的計算機進行性能評估打分，并按分值從小到大排序，求得ηk值；

2） 計算每個框架的主導份額Si，并按從小到大排序；

3） 計算相鄰框架之間的主導份額差dSi；

4） 主導份額最小的框架進行分配計算，如果是第奇數次分配計算則從性能評估分值高的機器分配資源，如果是第偶數次分配計算則從分值低的機器分配資源；

5） 反復執行步驟2）～4），當所有任務分配完畢或者所有資源分配完成時，分配流程結束。

3 實驗結果

本實驗的集群環境由4個計算節點組成，分別為2臺性能較差的曙光服務器和2臺性能較好的IBM服務器，共56核CPU和48GB內存，服務器硬件配置如表1所示。集群節點計算機的操作系統Linux版本為CentOS 7.0，Mesos采用最新的0.24.0版本。運行2個Hadoop框架，分別處理不同的任務。本實驗選取WordCount，TeraSort、NutchIndex、Kmeans、Bayes及PageRank[22]6種作業進行實驗，作業參數設置如表2所示。

對比實驗中，框架1的子任務對資源的需求為〈2核CPU，1GB內存〉，框架2的子任務對資源的需求為〈1核CPU，2GB內存〉。本實驗在mesos中分別采用DRF算法和修改源程序實現的meDRF算法進行測試。經過運行表2中的MapReduce任務，兩個算法分配的資源分布分別如圖2、3所示。

通過對比WordCount、TeraSort、NutchIndex、Kmeans、Bayes及PageRank 6種作業分別在DRF、meDRF、異構、同構4種條件下的任務完成時間（如表3所示）?？梢园l現：不論是DRF還是meDRF算法，同構環境下的任務執行時間都較短；meDRF與DRF算法相比，meDRF大部分情況下的執行時間與DRF算法相比，執行時間較短。這說明更加公平的資源調度策略在一定程度上能夠減小作業的執行時間。

實驗過程中，本文還對不同作業的執行過程中內存，磁盤及網絡資源使用情況進行了監控，如圖4所示。

通過圖4可以看出不同的MapReduce作業在運行過程中對內存、磁盤與網絡資源的利用存在較大的差異，并且相同作業在不同時間點的資源使用情況變化也很大。并且，在異構環境下，這些隨時變化的資源需求，已有的DRF算法并不能很好地適應公平性的要求。

算法meDRF比DRF在MapReduce中執行效率較好的原因是：當前Hadoop中采用機架感知的數據存放策略，將數據文件切分為相同大小的數據塊（Block）隨機存儲到集群DataNode節點中。在同構環境中，這種數據的切分與存儲方法配合DRF算法的資源分配，能夠滿足系統可用性與負載分流的要求。但是，在異構環境中，由于集群中各節點的計算能力存在著差異，異構節點處理相同任務（任務數據集大小相同）的完成時間不同。因為只有當一個作業的Map任務成功完成的數量超過一定的閾值時，才能開始分配該作業的Reduce任務給某TaskTracker節點執行，所以對于計算機能力強的節點，DRF算法在異構環境容易造成大量的等待時延。MapReduce任務執行過程中任務之間并不是按照完全并行的方式進行的，Map與Reduce任務之間存在不同程度的執行順序與數據調用的制約關系。當某任務處于等待其他任務的執行結果（或等待其他任務的執行完畢）才能繼續往下執行而處于“被動等待”狀態時，DRF算法的資源分配的缺點就顯現出來。而meDRF算法則是適應了異構環境的資源分配，較DRF更能提高異構環境下作業的執行效率。

另外，本文對任務運行過程中的資源使用情況進行了監控，對于系統最核心的資源CPU，DRF與meDRF算法的平均CPU負載情況比對如圖5所示。從圖5可以發現，meDRF算法較DRF算法在120min的監控周期中，meDRF算法的CPU負載更加平穩，波動幅度控制能力更好。

4 結語

本文在研究mesos框架中的DRF多資源公平分配算法的基礎上，設計并實現了增加機器性能評估影響因子的meDRF分配算法。實驗測試結果表明：meDRF分配算法更能體現多資源分配的公平性，且資源分配具有更好的穩定性，能有效提高計算資源的使用率。通過選取WordCount、TeraSort、NutchIndex、Kmeans、Bayes及PageRank 6種作業進行實驗，對比作業運行時間及資源的使用情況，證明了meDRF算法相對于DRF算法的優越性。在實際應用的場景中，不同框架運行的作業類型存在差異，有些框架側重于分析，而有些側重于計算。如何使側重計算的框架獲得更多的優質資源，而側重分析的框架獲得較多的劣質資源，進一步提高資源使用率，是下一步的工作目標。

參考文獻：

[1]SHVACHKO K， KUANG H， RADIA S， et al. The Hadoop distributed file system[C]// Proceedings of the 2010 IEEE 26th Symposium on Mass Storage Systems and Technologies. Piscataway， NJ： IEEE， 2010： 1-10.

[2]WANG L， WANG Y， XIE Y. Implementation of a parallel algorithm based on a spark cloud computing platform[J]. Algorithms， 2015， 8（3）：407-414.

[3]LEE B S， KANAGAVELU R， AUNG K M M. An efficient flow cache algorithm with improved fairness in softwaredefined data center networks[C]// Proceedings of the 2013 IEEE 2nd International Conference on Cloud Networking. Piscataway， NJ： IEEE， 2013：18-24.

[4]DEAN J， GHEMAWAT S. MapReduce： simplified data processing on large clusters[C]// Proceedings of the 6th Conference on Symposium on Opearting Systems Design & Implementation. Berkeley， CA： USENIX Association， 2004：107-113.

[5]VERNICA R， CAREY M J， LI C. Efficient parallel setsimilarity joins using MapReduce[C]// Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2010： 495-506.

[6]覃雄派，王會舉，杜小勇，等.大數據分析： RDBMS與MapReduce的競爭與共生[J].軟件學報， 2012，23（1）：32-45.（QIN X P， WANG H J， DU X Y， et al. Big data analysis： competition and symbiosis of RDBMS and MapReduce[J]. Journal of Software， 2012， 23（1）：32-45.）

[7]張雪萍，龔康莉，趙廣才. 基于MapReduce的KMedoids并行算法[J]. 計算機應用， 2013，33（4）：1023-1025. （ZHANG X P， GONG K L， ZHAO G C. Parallel KMedoids algorithm based on MapReduce[J]. Journal of Computer Applications， 2013， 33（4）： 1023-1025.）

[8]亓開元，韓燕波，趙卓峰，等.支持高并發數據流處理的MapReduce中間結果緩存[J]. 計算機研究與發展， 2013， 50（1）：111-121.（QI K Y， HAN Y B， ZHAO Z F， et al. MapReduce intermediate result cache for concurrent data stream processing[J]. Journal of Computer Research and Development， 2013， 50（1）：111-121.）

[9]顧榮，王芳芳，袁春風，等. YARM： 基于MapReduce的高效可擴展的語義推理引擎[J]. 計算機學報， 2015，38（1）：74-85. （GU R， WANG F F， YUAN C F， et al. YARM： efficient and scalable semantic reasoning engine based on MapReduce[J]. Chinese Journal of Computers， 2015，38（1）：74-85.）

[10]王習特，申德榮，于戈，等. MapReduce集群中最大收益問題的研究[J]. 計算機學報， 2015， 38（1）：109-121.（WANG X T， SHEN D R， YU G，et al. Research on maximum benefit problem in a MapReduce cluster[J]. Chinese Journal of Computers， 2015， 38（1）：109-121.）

[11]TANG S， LEE B S， HE B. DynamicMR： a dynamic slot allocation optimization framework for MapReduce clusters[J]. IEEE Transactions on Cloud Computing， 2014， 2（3）：333-347.

[12]夏祎. Hadoop平臺下的作業調度算法研究與改進[D]. 廣州： 華南理工大學， 2010： 30-40. （XIA Y. Research and improvement of Hadoop job scheduling algorithm[D]. Guangzhou： South China University of Technology， 2010： 30-40.）

[13]趙春燕.云環境下作業調度算法研究與實現[D]. 北京： 北京交通大學， 2009： 36-37. （ZHAO C Y. Research and implementation of a cloud environment job scheduling algorithm[D]. Beijing： Beijing Jiaotong University， 2009： 36-37.）

[14]最大最小公平算法[EB/OL]. [2015-10-22].https：//en.wikipedia.org /wiki/Maxmin_fairness.（Maxmin fairness[EB/OL]. [2015-10-22]. https：//en.wikipedia.org/wiki/Maxmin_fairness.）

[15]ASADPOUR A， SABERI A. An approximation algorithm for maxmin fair allocation of indivisible goods[J]. SIAM Journal on Computing， 2010， 39（7）：2970-2989.

[16]GHODSI A， ZAHARIA M， HINDMAN B， et al. Dominant resource fairness： fair allocation of multiple resource types[C]// Proceedings of the 8th USENIX Conference on Networked Systems Design and Implementation. Berkeley， CA： USENIX Association， 2011： 323-336.

[17]盧笛，馬建峰，王一川，等.云計算下保障公平性的多資源分配算法[J]. 西安電子科技大學學報（自然科學版）， 2014，41（3）：162-168. （LU D， MA J F， WANG Y C， et al. Enhanced fairnessbased multiresource allocation algorithm for cloud computing[J]. Journal of Xidian University （Natural Science）， 2014，41（3）：162-168.）

[18]Apache Mesos Documentation[EB/OL]. [2015-10-03]. http：//mesos.apache.org/documentation/latest/index.html.

[19]HINDMAN B， KONWINSKI A， ZAHARIA M， et al. Mesos： a platform for finegrained resource sharing in the data center[C]// Proceedings of the 8th USENIX Conference on Networked Systems Design and Implementation. Berkeley， CA： USENIX， 2011：429-483.

[20]霍菁，石京燕，孫功星，等.一種改進的DRF算法對BESIII集群資源管理的優化[J]. 核電子學與探測技術，2014，34（10）：1153-1158. （HUO J， SHI J Y， SUN G X， et al. The optimization of BESIII cluster resource management by using the improved DRF algorithm[J]. Nuclear Electronics & Detection Technology， 2014，34（10）：1153-1158.）

[21]BOUVERET S， LANG J. Efficiency and envyfreeness in fair division of indivisible goods： logical representation and complexity[J]. Journal of Artificial Intelligence Research， 2008，32（1）： 525-564.

[22]BOLDI P， SANTINI M， VIGNA S. PageRank： functional dependencies[J]. ACM Transactions on Information Systems， 2009， 27（4）：1139-1141.