异构云系统中基于智能优化算法的多维资源公平分配

刘曦　张潇璐　张学杰

摘要：资源分配策略的研究一直是云计算领域研究的热点和难点，针对异构云计算环境下多维资源的公平分配问题，结合基因算法（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/.