適應(yīng)異構(gòu)集群的Mesos多資源調(diào)度DRF增強算法

柯尊旺 于炯 廖彬

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

關(guān)鍵詞：資源分配；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 引言

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

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

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

1 DRF分配算法

1.1 DRF算法簡介

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

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

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

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

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

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

1.2 DRF算法的不足

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

式中：j表示資源類別，k表示資源種類數(shù)量，Rj表示資源類別j的資源總量，Wi表示計算任務(wù)的權(quán)重，Rui， j表示計算任務(wù)i已分配的j類別資源總量。

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

2 meDRF分配算法

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

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

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

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

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

3） 計算相鄰框架之間的主導(dǎo)份額差dSi；

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

5） 反復(fù)執(zhí)行步驟2）～4），當(dāng)所有任務(wù)分配完畢或者所有資源分配完成時，分配流程結(jié)束。

3 實驗結(jié)果

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

對比實驗中，框架1的子任務(wù)對資源的需求為〈2核CPU，1GB內(nèi)存〉，框架2的子任務(wù)對資源的需求為〈1核CPU，2GB內(nèi)存〉。本實驗在mesos中分別采用DRF算法和修改源程序?qū)崿F(xiàn)的meDRF算法進行測試。經(jīng)過運行表2中的MapReduce任務(wù)，兩個算法分配的資源分布分別如圖2、3所示。

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

實驗過程中，本文還對不同作業(yè)的執(zhí)行過程中內(nèi)存，磁盤及網(wǎng)絡(luò)資源使用情況進行了監(jiān)控，如圖4所示。

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

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

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

4 結(jié)語

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

參考文獻：

[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]覃雄派，王會舉，杜小勇，等.大數(shù)據(jù)分析： RDBMS與MapReduce的競爭與共生[J].軟件學(xué)報， 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]. 計算機應(yīng)用， 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]亓開元，韓燕波，趙卓峰，等.支持高并發(fā)數(shù)據(jù)流處理的MapReduce中間結(jié)果緩存[J]. 計算機研究與發(fā)展， 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]顧榮，王芳芳，袁春風(fēng)，等. YARM： 基于MapReduce的高效可擴展的語義推理引擎[J]. 計算機學(xué)報， 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]王習(xí)特，申德榮，于戈，等. MapReduce集群中最大收益問題的研究[J]. 計算機學(xué)報， 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平臺下的作業(yè)調(diào)度算法研究與改進[D]. 廣州： 華南理工大學(xué)， 2010： 30-40. （XIA Y. Research and improvement of Hadoop job scheduling algorithm[D]. Guangzhou： South China University of Technology， 2010： 30-40.）

[13]趙春燕.云環(huán)境下作業(yè)調(diào)度算法研究與實現(xiàn)[D]. 北京： 北京交通大學(xué)， 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]. 西安電子科技大學(xué)學(xué)報（自然科學(xué)版）， 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集群資源管理的優(yōu)化[J]. 核電子學(xué)與探測技術(shù)，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.