異構云系統中基于智能優化算法的多維資源公平分配

劉曦　張瀟璐　張學杰

摘要：資源分配策略的研究一直是云計算領域研究的熱點和難點，針對異構云計算環境下多維資源的公平分配問題，結合基因算法（GA）和差分進化算法（DE），分別給出了兩種兼顧分配公平性和效率的資源分配策略，改進了解矩陣表達式使異構云系統中的主資源公平分配（DRFH）模型轉化成為整數線性規劃（ILP）模型，并提出了基于最大任務數匹配值（MTM）的初始解產生機制和使不可行解轉化為可行解的修正操作，以此提高算法的收斂速度，使其能夠快速有效地得到最優分配方案。實驗結果表明，基于GA和DE算法的多維資源公平分配策略可以得到近似最優解，在最大化最小主資源份額目標值和資源利用率方面明顯優于Best-Fit DRFH和Distributed-DRFH，而且針對不同任務類型的資源需求，具有較強的自適應能力。

關鍵詞：主資源公平； 基因算法； 差分進化算法； 異構云

中圖分類號：TP393

文獻標志碼：A

0引言

在云計算環境中，如何有效地對資源進行分配調度，保證資源分配的公平性，最大可能地滿足服務的資源需求，同時，確保資源能夠最大限度被利用，是云計算平臺分配系統需要解決的重要問題。而目前面臨的是云計算環境由大量異構服務器組成，每個服務器的配置不同，而且由于資源供給的多樣性，更增加了資源公平分配的難度。因此，設計針對異構云計算環境下兼顧多維資源的分配公平性和效率，并使其分配到的資源盡可能達到最大值的公平分配方法是目前云計算平臺急需解決的一個關鍵問題。

2011年，美國加州大學伯克分校的Ghodsi等[1]首次提出了占優資源公平分配（Dominant Resource Fairness， DRF）。該機制是在最大最小公平模型的基礎上，擴展使其能夠對多種類型的資源進行分配并能保證分配的公平性。基本思想是最大化所有用戶中的占優資源份額的最小值，從而將多資源分配問題轉化為單資源分配問題。DRF與傳統的基于單資源的分配機制相比，其資源利用率有了明顯的提升。雖然DRF分配機制考慮到了多維資源的情形，但卻將所有待分配的資源全部集中在一個資源池中進行考慮。

針對上述問題，文獻[2]提出了在異構服務器組成的云計算環境下的主資源公平分配機制（Dominant Resource Fairness allocation in Heterogeneous system， DRFH），其分配機制是實現最大化用戶的最小主資源份額。DRFH分配機制很好地解決了異構服務器之間的資源差異化問題和用戶任務不可分割問題。但DRFH求解是一個NP難問題，目前很難找到一個快速有效的方法來求最優解。文獻[2]中設計了一個啟發式算法（Best-Fit DRFH）來求解DRFH。該算法優先給最小主資源份額的用戶分配資源，在最佳適應值的服務器上進行資源分配，以提高資源利用率。文獻[3]將DRFH分配機制擴展到了分布式環境中，提出 Distributed-DRFH算法。雖然Best-Fit DRFH和Distributed-DRFH算法與傳統的方法相比，在目標函數值和資源利用率方面都有所提升，但我們認為還有提升的空間。首先，Best-Fit DRFH和Distributed-DRFH算法采用簡單的啟發式算法，能達到快速求解目的，但求出來的解與最優解有明顯差距；其次，在異構云計算環境下，需要考慮異構服務器資源類型和用戶資源需求的多樣性帶來的資源分配公平和效率問題。由以上分析可以看出，采用簡單的啟發式算法來解決DRFH問題無法得到以資源公平分配最大化為目標的最優分配方案。

在云計算環境中，多維資源公平分配是一個NP難問題，其主要目的是最大化最小主資源分配份額。目前求解NP難問題的主要智能優化算法有基因算法（Genetic Algorithm， GA）[4]、差分進化（Different Evolution， DE）算法[5]、模擬退火（Simulated Annealing， SA）算法、神經網絡等，每種算法都有自己的求解方式與優點，并且已有很多研究人員針對不同的應用場景對它們進行了相應的優化或者有效的結合，但這些算法較少涉及到異構環境下資源分配調度問題。將這些算法合理地引用到異構云計算環境下多維資源的公平分配問題的研究上，可以快速得到最優解分配方案，保證資源的公平性分配，提高整個系統的資源利用率。在智能優化算法中， GA 和DE算法都是基于種群的啟發式全局搜索算法，能夠掌握并動態跟蹤目前的全局搜索情況，并根據當前的搜索情況自適應調整其搜索策略，因此能很好適用于異構云計算環境下復雜的資源分配情況，并且它們擁有較強的魯棒性和全局收斂能力，算法能在很短的時間內找到近似最優解，提高分配的效率。因此，本文提出在異構云計算環境下基于GA和DE算法來求解DRFH最優分配方案的策略，并針對傳統GA和DE算法在求解最優解過程中易早熟收斂等缺點，改進解矩陣表達式，使其更適用于離散解空間域內搜索全局最優解，并且使DRFH模型轉化成為整數線性規劃（Integer Linear Programming， ILP）模型；解的初始值生成采用采用基于最大任務數匹配值（Max Task Match，MTM）的啟發式算法，以加快解空間的探測；設計修正操作算法，使不可行解在每次迭代過程中保留優秀特征的情況下變為可行解。模擬實驗對比了基于GA和DE算法的多維資源公平分配策略與Best-Fit DRFH和Distributed-DRFH在真實實例和不同資源請求類型實例下的性能表現，其目標函數值和資源利用率均顯著地優于Best-Fit DRFH和Distributed-DRFH，且近似最優解。實驗結果表明基于GA和DE算法的分配策略能很好地適應用戶資源請求類型的變化，有效地利用服務器資源，提高了服務質量。

1相關工作

在資源分配公平性方面的研究中，文獻[6]提出了基于單資源的最大最小公平（Max-min Fairness）模型，其基本思想是使得資源分配的最小分配量盡可能最大化；文獻[1]提出了針對多維資源的DRF機制；文獻[7]將DRF機制推廣到零需求和任務不可分等情形，并討論了DRF機制的局限性；文獻[8]考慮用戶任務總數有限的情況， 提出了Lexicographically Max-Min Dominant Share （LMMDS）機制，推廣了DRF機制，并分析了DRF機制的近似比。針對用戶動態加入系統的情形，文獻[9]提出了一種動態情形下多資源公平分配機制DDRF；筆者之前的研究工作也將動態DDRF機制推廣到任務數受限的情形[10]。

以上成果是基于將資源全部集中在一個資源池中且用戶任務可以分割的情況下研究的，與云計算真實環境下的資源分配情況不相符。由于服務器的異構性，如分給用戶i在服務器1上能完成1/2任務的資源，在服務器2能完成1/2任務的資源，但用戶任務不可分割執行，使得服務器1和2上的資源閑置，造成了資源的浪費。針對上述問題，文獻[11]提出了多個異構系統下多維資源公平分配算法；文獻[12]對異構系統中任務不可分割情形下的公平分配機制進行了深入的理論分析；文獻[13]在異構云計算體系結構下提出了基于占優資源的多資源聯合公平分配機制，該機制定義了占優資源熵及占優資源權重，提高了系統的自適應能力；文獻[2]提出了異構系統中資源公平分配機制DRFH，其分配機制是實現最大化用戶的最小主資源份額；文獻[3]在DRFH[2]的基礎上，針對分布式環境中有多個資源管理者的情況，提出了Distributed-DRFH算法。Distributed-DRFH算法是將用戶資源請求分到與其最適應的資源管理者的服務器上，并提出了本地資源管理算法。實驗表明在多個資源管理者的情況下，Distributed-DRFH能有效提高資源利用率。但是求解DRFH問題是一個NP難問題，若采用傳統搜索方法，可能無法在合理的時間內找到問題的最優解，因此需要尋求一種能夠快速求出最優解或者近似最優解的方法。

近年來已有研究者將GA、蟻群算法（Ant Colony Optimization， ACO）、粒子群優化（Particle Swarm optimization， PSO）算法、人工神經網絡等引入到云計算任務調度問題中，取得了不錯的應用效果。文獻[14]為提高云計算任務調度的服務質量，提出基于GA和ACO算法的多群智能算法。首先利用GA在全局搜索較優解，然后利用ACO算法來尋找全局最優解。實驗結果表明，智能優化算法提高了云計算任務調度的效率，縮短了任務完成時間。文獻[15]針對云計算MapReduce框架下軟件即服務（Software-as-a-Service， SaaS）多租戶情況，提出了一種基于ACO的多租戶服務定制算法；文獻[16]針對云計算基礎設施即服務（Infrastructure as a Service， IaaS）中虛擬機部署問題，提出了一種基于PSO算法的負載平衡虛擬機部署策略。但以上研究均未考慮異構云計算環境下資源的多樣性和用戶需求的差異性；而且，多維資源公平分配是一個復雜問題，傳統GA、DE算法、ACO算法等均存在不足，因此考慮到異構云計算環境下多維資源分配的公平性和效率問題，需要對其算法進行改進，從而找到問題的最優解。

2.3修正操作

智能優化算法在每一次迭代完成后，都會產生不可行解，如超過資源總量限制等，這時需要一種操作去檢測解是否可行，若不可行則修正成可行解。本文采用貪心策略來修正不可行解，具體包含兩個階段：第一個階段是遍歷所有服務器，檢查其資源分配情況。如果分給用戶的資源超過服務器資源總量，則選擇最大主資源份額的用戶，減少它的任務數。第二個階段是選擇MTMkl最大的用戶，在不超過資源總量的前提下，增加它的任務數，提高最小主資源份額值。算法描述為算法2。

4基于DE算法的多維資源公平分配策略

DE算法是一種在連續空間中進行隨機搜索的全局優化算法[5]，其基本思想是：從種群中隨機選擇幾個不相同的個體（解），以其中一個個體作為基礎，剩余的個體為參照作一個隨機的擾動，將擾動得到的新個體（新解）與目標個體進行交叉操作后產生實驗個體（新解），將實驗個體與目標個體進行自然選擇，優勝劣汰，從而實現在全局空間內搜索最優個體（最優解，記為OPT）[19]。DE算法相比于其他進化算法，其在較強的種群全局搜索策略的基礎上，通過變異操作中采用的特殊且容易實現的差分策略，降低了進化操作的復雜度。DE算法與GA相似，也分為三個步驟：變異操作、交叉操作和選擇操作。

4.1變異操作

DE算法通過差分策略實現個體的變異，有效利用群體的分布特性，提高算法的搜索能力。算法首先通過差分策略對種群中的每一個個體Xk進行變異操作，得到變異個體V。本文隨機使用表1中列舉的5種差分策略。其中：x表示種群中的隨機個體、最優個體或當前個體，y表示進行差分的個體個數，z表示差分的模式。如算法中的Rand1bin操作是隨機在種群中選擇兩個不同的個體相減生成差分個體，將差分個體賦予權值之后加到第三個隨機選擇的不同個體上，生成變異個體。數學表達式為：

5實驗評估

基于Google數據集來評估基于GA和DE算法的多維資源公平分配策略的性能（以下簡稱為GA和DE算法），同時與Best-Fit DRFH、Distributed-DRFH和最優解OPT進行比較。Distribute-DRF資源分配方式設置1個資源提供者（p=1）。服務器資源配置和用戶的任務需求均是從Google的集群數據集[20]中隨機選擇。該數據集是Google 7個小時的真實數據，其中包含了服務器的配置情況，如CPU、內存和硬盤，以及用戶的資源需求等。表2為Google的異構服務器集群資源配置及數量情況，CPU和內存都是基于最大處理能力的服務器容量正則化處理后的值。GA和DE算法的種群大小設置為SN=30，迭代次數不超過2000。由于智能優化算法具有隨機性，因此針對每個實例，運行50次后取平均值進行性能評估。

參照文獻[3]中的設置，從Google數據集中隨機選取20個用戶，且每個用戶不少于20個任務需求，然后在一個由100個服務器節點組成的異構云計算系統上進行資源分配，服務器的CPU和內存配置從表2中的Google數據集中隨機選擇。由于該實驗利用Lingo程序在24h內未找到整數最優解，因此沒有進行與最優解的比較。表3比較了GA、DE算法、Best-Fit DRFH和Distributed-DRFH的主資源份額，可以看出，GA和DE算法相比Best-Fit和Distributed-DRFH的主資源份額有明顯的提高，其中GA和DE算法的結果非常接近。這主要是因為GA和DE算法是在全局空間域內搜索最優解，并通過多次迭代，不斷地改善當前最優解。從表3中還能夠看出，Best-Fit DRFH的CPU和內存利用率均高于Distributed-DRFH，但GA和DE算法的CPU和內存使用率均顯著地高于Best-Fit DRFH和Distributed-DRFH，說明基于GA和DE算法的多資源公平分配策略能夠有效提高服務器的資源利用率，避免服務器資源的閑置浪費。

在實際異構云計算資源分配情況下，用戶任務的資源請求類型呈現多樣化，如在資源類型為CPU和內存的情況下，可能會出現計算資源密集型任務或內存資源密集型任務。針對這兩種情況，設計了兩個實例來評估GA和DE算法的性能表現。對于計算資源密集型任務，從表2中隨機選取5臺服務器和3個用戶，滿足用戶任務資源需求類型為計算資源密集型（Di1>Di2）；對于內存資源密集型任務，從表2中隨機選取5臺服務器和3個用戶，滿足用戶任務資源需求類型為內存資源密集型（Di1

1）當資源需求是內存資源密集型時，Distributed-DRFH的主資源份額優于Best-Fit DRFH，而當資源需求是計算資源密集型時，Best-Fit DRFH卻優于Distributed-DRFH；但GA和DE算法均明顯地優于Best-Fit DRFH和Distributed-DRFH，且主資源份額接近最優解。該實驗結果表明GA和DE算法均能很好地適應用戶任務需求類型的變化并能得到近似最優解。

2）雖然啟發式算法和兩種智能優化算法的解均低于最優解，但GA和DE算法均顯著地高于Best-Fit DRFH和Distributed-DRFH算法。實驗結果也表明在啟發式算法下的CPU利用率較低，運用智能優化算法可以提高資源利用率，有效地避免CPU資源的浪費。GA和DE算法最多迭代2000次，如果增加迭代次數，得到的主資源份額和資源利用率會更加接近最優解。

3）當資源需求是內存資源密集型時，DE算法的CPU和內存的利用率均優于GA；當資源需求是計算資源密集型時，GA的CPU利用率優于DE算法，而DE算法的內存利用率優于GA，可以看出GA和DE算法均顯著地高于Best-Fit DRFH和Distributed-DRFH的內存利用率，且接近最優解。值得注意的是，Best-Fit DRFH和Distributed-DRFH啟發式算法在兩種資源請求類型下，出現了明顯的波動（內存資源密集型時Distributed-DRFH較優，計算資源密集型時Best-Fit DRFH較優），而GA和DE算法并沒有出現較大的波動，均接近最優解。這表明GA和DE算法能很好地適應用戶任務資源請求類型的變化，可以有效地利用服務器資源，有較強的環境適應能力。

6結語

本文針對異構服務器組成的云計算系統下多樣化的用戶資源類型請求和用戶任務不可分割等需求，運用GA和DE算法求解DRFH最優資源分配問題，改進適合于兩種智能優化算法的解矩陣表達式使求解DRFH模型轉化成為求解整數線性規劃模型，設計基于MTM啟發式算法的初始解產生機制和使不可行解轉化為可行解的修正操作。實驗結果表明，基于GA和DE算法的多維資源公平分配策略分配到的主資源份額和資源利用率方面均優于Best-Fit DRFH和Distributed-DRFH算法，且近似最優解，有效提升了資源利用率，使供給和需求更加匹配，而且兩種算法能夠很好地適應于用戶資源請求類型的變化。接下來的研究工作將會在大規模的集群中對算法性能進行驗證，并優化算法參數使其更適用于異構云計算環境下的多維資源分配情況。

參考文獻：

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

[2]WANG W， LIANG B， LI B. Multi-resource fair allocation in heterogeneous cloud computing systems [J]. IEEE Transactions on Parallel & Distributed Systems， 2015， 26（10）： 2822-2835.

[3]ZHU Q， OH J C. An approach to dominant resource fairness in distributed environment [M]// IEA/AIE 2015： Proceedings of the 28th International Conference on Industrial， Engineering and Other Applications of Applied Intelligent Systems， LNCS 9101. Berlin： Springer-Verlag， 2015： 141-150.

[4]HOLLAND J H. Adaptation in Natural and Artificial Systems [M]. Cambridge， MA： MIT Press， 1992： 89-121.

[5]STORN R， PRICE K. Differential evolution — a simple and efficient heuristic for global optimization over continuous spaces [J]. Journal of Global Optimization， 1997， 11（4）：341-359.

[6]Wikipedia. Max-min fairness[EB/OL]. [2015-06-10]. http：//en.wikipedia.org/wiki/Max-min_fairness.

[7]PARKES D C， PROCACCIA A D， SHAH N. Beyond dominant resource fairness： extensions， limitations， and indivisibilities [J]. ACM Transactions on Economics and Computation， 2015， 3（1）： 1-22.

[8]LI W， LIU X， ZHANG X， et al. Multi-resource fair allocation with bounded number of tasks in cloud computing systems [J/OL]. arXiv preprint arXiv： 1410.1255v2. （2015-02-03） [2015-12-01]. http：//arxiv.org/abs/1410.1255.[2015-02-03]. http：//xueshu.baidu.com/s？wd=paperuri%3A%28fb34151b4905f286d5f3c4d576091855 %29&filter=sc_long_sign&tn=SE_xueshusource_2kduw 22v&sc_vurl=http%3A%2F%2Farxiv.org%2Fabs%2F1410.1255&ie=utf-8&sc_us=15855640868426366128.

[9]KASH I， PROCACCIA A D， SHAH N. No Agent left behind： dynamic fair division of multiple resources [J]. AAMAS 13： Proceedings of the 2013 International Conference on Autonomous Agents and Multi-Agent Systems. Richland， SC： International Foundation for Autonomous Agents and Multiagent Systems， 2013： 351-358.

[10]LIU X， ZHANG X， ZHANG X. Dynamic fair division of multiple resources with satiable Agents in cloud computing systems [C]// BDCLOUD 15： Proceedings of the 2015 IEEE Fifth International Conference on Big Data and Cloud Computing. Washington， DC： IEEE Computer Society， 2015： 131-136.

[11]PSOMAS C-A， SCHWARTZ J. Beyond beyond dominant resource fairness： indivisible resource allocation in clusters [EB/OL]. [2015-12-03]. http：//people.eecs.berkeley.edu/～kubitron/courses/cs262a-F12/projects/reports/project13_report_ver2.pdf.

[12]FRIEDMAN E， GHODSI A， PSOMAS C-A. Strategyproof allocation of discrete jobs on multiple machines [C]// EC14： Proceedings of the fifteenth ACM Conference on Economics and Computation. New York： ACM， 2014： 529-546.

[13]王金海，黃傳河，王晶，等.異構云計算體系結構及其多資源聯合公平分配策略[J].計算機研究與發展，2015，52（6）：1288-1302. （WANG J H， HUANG C H， WANG J， et al. A heterogeneous cloud computing architecture and multi-resource-joint fairness allocation strategy [J]. Journal of Computer Research and Development， 2015， 52（6）： 1288-1302.）

[14]陳海燕.基于多群智能算法的云計算任務調度策略[J]. 計算機科學，2014，41（S1）：83-86. （CHEN H Y. Task scheduling in cloud computing based on swarm intelligence algorithm[J]. Computer Science， 2014， 41（S1）： 83-86）

[15]王會穎， 倪志偉， 伍章俊. 基于MapReduce和多目標蟻群算法的多租戶服務定制算法[J]. 模式識別與人工智能，2014，27（12）：1105-1116. （WANG H Y， NI Z W， WU Z J. Multi-tenant service customization algorithm based on MapReduce and multi-objective ant colony optimization[J]. Pattern Recognition and Artificial Intelligence， 2014， 27（12）： 1105-1116.）

[16]楊靖， 張宏軍，趙水寧，等.基于粒子群優化算法的虛擬機部署策略[J]. 計算機應用，2016，36（1）：117-121. （YANG J， ZHANG H J， ZHAO S N， et al. Virtual machine deployment strategy based on particle swarm optimization algorithm [J]. Journal of Computer Applications， 2016， 36（1）： 117-121.）

[17]XIONG A， XU C. Energy efficient multiresource allocation of virtual machine based on PSO in cloud data center [J]. Mathematical Problems in Engineering， 2014（6）：1-8.

[18]STADNYK I. Schema recombination in pattern recognition problems [C]// Proceedings of the Second International Conference on Genetic Algorithms on Genetic Algorithms and Their Application. Hillsdale， NJ： L. Erlbaum Associates Inc.， 1987： 27-35.

[19]LAMPINEN J， ZELINKA I. On stagnation of the differential evolution algorithm [C]// MENDEL 2000： Proceedings of the 6th International Conference on Soft Computing. Brno， Czech Republic： PC-DIR， 2000： 76-85.

https：//www.researchgate.net/publication/2645446_On_Stagnation_Of_The_Differential_Evolution_Algorithm

[20]WILKES J， REISSEISS C. Google cluster data 2011_2 [EB/OL]. [2015-06-15]. https：//code.google.com/p/googleclusterdata/.