云计算中基于拍卖的虚拟机动态供应和分配算法

许建豪

(南宁职业技术学院 信息工程学院，广西 南宁 530008)



云计算中基于拍卖的虚拟机动态供应和分配算法

许建豪

(南宁职业技术学院 信息工程学院，广西 南宁 530008)

摘要：当前云计算供应商通过定价算法或类似拍卖的算法来分配虚拟机(virtual machine,VM)。针对这些算法大多要求虚拟机静态供应，无法准确预测用户需求，导致资源未得到充分利用的问题，提出一种基于组合拍卖的虚拟机动态供应和分配算法，在做出虚拟机供应决策时考虑用户对虚拟机的需求。该算法将可用的计算资源看成是“流体”资源，且这些资源根据用户请求可分为不同数量、不同类型的虚拟机实例。然后可根据用户的估价决定分配策略，直到所有资源分配完毕。基于并行工作负载存档(parallel workload archive，PWA)的真实工作负载数据进行了仿真实验，结果表明该方法可保证为云供应商带来更高收入，提高资源利用率。

关键词：云计算；虚拟机实例；拍卖；分配；云供应商；资源利用率

0引言

云计算系统所提供的未来计算基础设施使得用户可以为他们的计算需求分配更多的远程资源，节约了自己建立系统所需的前期成本。云供应商将他们的资源以多种类型虚拟机(virtual machine,VM)实例的方式供应。然后，使用定价策略来分配和出售VM实例[1]，使用拍卖算法来出售定价之后仍然闲置的资源。云供应商希望分配算法能够支持动态供应，以便他们根据市场需求就不同类型的VM实例数量做出决策。

多篇文献对虚拟机的动态供应和分配问题进行了研究。文献[2]设计了一种在线虚拟机动态供应和分配算法。在该算法下，每当有足够多的资源和合适的申请，就会分配VM实例。然而，该算法在运行时需要收集一段时间内所有用户请求的所有信息。文献[3]为了改善云采购平台中的顾客满足情况。提出了载有虚拟供应商资源的虚拟机分配流程，并且建立模型；然后分别采用最佳递减匹配(best fit decrease, BFD)方法和仪跟踪多群粒子群优化(finder-tracker multi-swarm particle swarm optimization，FTMPSO)算法对其求解。然而该方法还存在很多不足，例如对于需求到达的模拟过于粗糙，对虚拟机迁移的成本没有过多的考虑。文献[4]分析和研究了Xen 虚拟机管理器的Credit调度算法的不足，提出了改进的调度算法对虚拟机进行Credit比例预分配，采用动态调度时间片机制,以非工作保留模式(non-work-conserving)实现软实时任务周期调度。然而，Credit值更新会受到更新时间片长度、虚拟机数量、虚拟机权重等影响，响应性能受到限制，系统的公平性无法保证。文献[5]提出基于组合拍卖的近似策略(combinatorial auction-greedy，CA-GREEDY)，并证明了基于组合拍卖的机制是虚拟机拍卖问题的最优求解策略。虽然该策略可以提高虚拟机实例的分配效率及云供应商的收入，但是该策略要求虚拟机实例已经供应完毕且不会再变，资源未得到充分利用。

为此，本文描述了虚拟机动态供应和分配问题，提出一种基于组合拍卖的求解算法。该算法可保证为云供应商带来更高收入，提高资源利用率。文中还分析了运行本文算法时的成本和效益，并给出部署指导原则。最后基于并行工作负载存档(parallel workload archive，PWA)[6]的真实工作负载数据进行仿真实验，评估了本文方法的有效性。

1虚拟机动态供应和分配问题

假设连续2次拍卖的时间间隔为一个时间单位。设cR和cI表示一个VM1实例在一个单位时间内处于运行状态和空闲状态时的成本。很显然，有cR>cI。云供应商运行所有可用资源的成本(即所有M个VM1实例)为M·cR，而使所有可用资源处于空闲状态的成本为M·cI。本文用x=(x1,x2,…,xn)表示分配向量，其中如果用户uj请求的批量实例被分配给该用户，则xi=1，否则xi=0。已知一个具体的分配向量和支付费用，云供应商的收益为

(1)

(2)

文献[7]已经证明，相比于当前的固定价格机制，组合拍卖机制可提高虚拟机实例的分配效率和收益。然而该文献研究的组件拍卖机制要求虚拟机已经提前分配完毕。本文认为，如果在拍卖时对虚拟机实例实行仔细的动态选择，以反映当时的市场需求，则可提升系统的总体性能。

2基于组合拍卖的虚拟机实例动态供应和分配机制

本节提出求解DVMPA问题的组合拍卖算法(combinationalauctionalgorithm-dynamicvmprovisioningandallocation，CAM-DVMPA)。通过确定云供应商需要供应的虚拟机的分配策略、价格和最优配置来提高收益。该算法可以确定获胜用户需要支付的价格以及为了满足获胜用户的要求需要供应的虚拟机实例集合。该算法可同时保证被分配的资源数量最大，且虚拟机实例分配时价格不低于底价。

CAM-DVMPA的具体过程见算法1。该算法需要部分系统信息，以便云供应商在供应资源时将计算资源总量M表示为VM1虚拟机总量。该机制同时需要可用的虚拟机类型数m及其权重向量w。它还需要知道VM1虚拟机实例的运行成本cR及空闲成本cI。

算法1CAM-DVMPA算法

输入：M;m;wj:j=1,…,n;cR,cI;

输出：W;pj:j=1,…,n;ki:i=1,…,m;

1：{阶段1：收集出价}

2：forj=1,…,ndo

4：endfor

5：{阶段2：确定获胜用户和供应策略}

6：W←∅ {获胜用户集合}

7：υres←cR-cI

8：增添出价为B0=(1,0,0,…,0,υres)的虚拟用户u0

9：forj=0,…,ndo

11：dj←υj/sj{‘出价密度’}

12：endfor

13：对用户u1,…,un重新排序，于是有d1≥d2≥…≥dn

14：设l表示索引，于是当j≤l时dj≥d0，否则dj

15：排除用户ul+1,…,un

16：将用户u0重命名为ul+1

17：设置n←l+1

18：n←l+1

19：forj=1,…,n-1do{排除虚拟用户}

20：ifsj≤Rthen

21：W←W∪uj

22：R←R-sj

23：endif

24：endfor

25：fori=1,…,mdo{确定虚拟机配置}

27：endfor

28：{阶段3：支付}

29：for所有的uj∈Wdo

32：pj←dlsj

33：endfor

34：for所有uj∉Wdo

35：pj←0

36：endfor

37：返回(W,p,k)

CAM-DVMPA分为3个阶段。在第1阶段，它收集用户的出价Bj(第1至4行)。在阶段2，该机制确定云供应商需要供应的虚拟机配置及获胜出价方。具体为：它增加一个虚拟用户u0，出价内容包括1个VM1实例，出价为υres=cR-cI(第8行)。该虚拟用户只用于模拟支持底价的拍卖模型，不会被分配任何资源。然后，它将计算所有用户的批量资源规模sj及出价密度dj(第9—12行)。此后，除了虚拟用户外的所有用户按照出价密度降序排列，dj

此后，算法采用贪婪策略确定获胜用户。只要有资源可用，那么便按照出价密度降序向用户分配他们所请求的批量资源。然而，在分配时不考虑虚拟用户。确定了获胜用户后，该算法将聚集获胜用户请求的批量资源，确定需要分配给用户们的虚拟机配置(第25—27行)。

在第3阶段，算法确定所有用户的支付价格。对每个获胜用户uj，算法寻找失败用户ul(如果uj不参与，则ul将获胜)。然后，用户uj的支付费用计算为其批量资源规模sj与ul的出价密度之积。所有失败用户支付费用为0。这种支付类型通常称为临界支付。

3理论分析

本文中如果用户通过为批量虚拟机表达自己的真实估价来实现其效用最大化，则称该机制具有真实性。其中，用户uj的效用表示为用户uj对批量虚拟机的估价υj及为了使用该批虚拟机而向分配机制提交的支付费用pj之差。因为参与真实的分配机制的用户必须采用复杂的出价策略才能使其效用最大，所以上述特点非常重要。他们只需为批量虚拟机提交自己的真实估价即可。文献[8]指出，如果分配功能具有单调性，且支付过程属于临界支付，则该分配机制具有真实性。该描述有助于我们证明定理1。

定理1CAM-DVMPA是真实的

证明首先证明，CAM-DVMPA分配具有单调性。用户通过增加其出价的密度就可以增加申请成功的概率。提交的估价越大，密度越大；批量虚拟机规模越大，密度越小。于是，用户若想在CAM-DVMPA进行分配决策时用到的排序表上位置靠前，只能提高出价或降低批量虚拟机申请规模。因此，CAM-DVMPA分配具有单调性。其次，根据CAM-DVMPA的支付方式，用户需要为其申请的批量虚拟机支付一定费用，以便单位虚拟机实例的平均价格等于其临界支付费用。用户只是支付了赢取申请所需要的最小费用。单调分配和临界支付特点保证CAM-DVMPA具有真实性。底价不会影响分配机制的真实性，因为底价基本只是虚拟用户的出价，而虚拟用户受云供应商控制，所以真实出价仍然是用户的主要策略。证毕。

下面分析CAM-DVMPA的复杂性。算法1的主要计算负载来自第19-24行和29-33行循环。第1个循环的最大复杂性为O(M)，即：所有获胜用户所申请的批量实例均只包含1个单位的VM1实例。第29-33行循环的总运行时间为O(n)。这是因为它对获胜用户进行循环操作，对失败用户进行搜索操作。因为已经对用户排序，所以获胜用户uj+1的临界支付搜索实际上是从uj的“临界支付用户ul”处开始(不失一般性，我们假设此时uj和uj+1为获胜方)。因此，该循环的总体最大复杂性为O(n)，其中第13行的排序复杂度为O(nlogn)。于是，CAM-DVMPA机制的复杂性为O(M+nlogn)。

4仿真实验

本文利用真实的工作负载数据进行全面的仿真实验，来评估CAM-DVMPA机制的性能。比较CAM-DVMPA与基于虚拟机静态分配的组合拍卖策略(combinatorialauction-greedy，CA-GREEDY)[5]的性能。文献[5]的研究已经证明，CA-GREEDY与当前云供应商采用的固定价格虚拟机分配机制[9-10]的性能相比，CA-GREEDY的性能远优于固定价格机制，因此在本文实验中采用该机制作为比较对象。利用并行工作负载存档[9]中的11种工作负载日志共进行264次实验，其中每个工作负载有24种不同的参数组合。

4.1实验配置

实验内容主要从已知的工作负载中生成作业提交，然后同时运行CA-GREEDY和CAM-DVMPA来分配作业并供应虚拟机。在配置实验时还要处理工作负载选择、申请生成及建立拍卖等问题。

1)工作负载选择：利用文献[6]中的并行工作负载存档负载。该存档包括许多网格和超级计算站点收集而来的大量工作负载。表1中给出了工作负载的部分统计数据。

表1　负载日志的统计数据

2)作业和出价生成：为日志文件中的每条记录，生成一个作业，用户需要运行该作业并为该作业生成一个出价。然后，需要为作业生成2个重要参数：请求的批量虚拟机及相应出价。为了生成作业的批量虚拟机实例，根据(3)式确定其通信与计算比。

(3)

(3)式可衡量有多少运行时间花费于给定作业的进程之间的通信上。以该值为基础，可确定作业的类别，其中共有m种类别，m表示可用的虚拟机类别数量。作业的类别指定了该作业的“首选”虚拟机类型。用因子μ描述被请求的总体虚拟机中有多少属于“首选”类型的虚拟机实例。例如，请求qj个处理器的类别为i的作业将会生成一个批量的虚拟机，该批量由一定数量的VMi实例构成，以便分配μqj个处理器。通过随机选择其他虚拟机类型来请求剩余处理器。生成批量虚拟机后，将生成相应的出价。为此，定义作业的加速因子为

(4)

该加速因子与“估价因子”相乘，即可生成出价。估价因子与用户类型有关。利用用户的ID号与5的模数将用户划分为5种类别。为作业设置的最后一个参数是其截止时间，此时工作负载日志内无信息提供。假设截止时间为完成作业所需时间的4-8倍。因此，将一个作业的截止时间设置为4-8的随机数与所需时间之积。

对可以运行的作业并行且独立地运行CA-GREEDY和CAM-DVMPA机制。用户(或作业)参与拍卖，直到其作业完成或确定其作业在截止时间前无法完成。如果其作业完成，则认为用户“被服务”，否则便“未被服务”。不失一般性，假设每个用户只提交一项作业，于是在下文中“用户”与“作业”可互用。

3)拍卖设置：假设云供应商提供4种不同类型的虚拟机：VM1,VM2,VM3,VM4。这些虚拟机类型由权重向量w=(1,2,4,8)描述。对每个负载文件，提取用户总数N及可用的处理器总数M。随着拍卖的进行，动态确定参与一次拍卖的用户数量。

本文在生成一个用户提交的作业所需的批量虚拟机时，只配置了几个参数。向量(C1,C2,C3)确定了用于描述作业情况的通信比。如果(C1,C2,C3)=(0.05,0.15,0.25)即通信比低于0.05的作业属于类型1，所需要的大部分虚拟机实例μqj将请求VM1，其中，qj表示uj请求的处理器数量。假设μ取值0.5和0.75。利用其余类型的虚拟机实例来随机确定其余批量虚拟机。利用日志文件的用户ID字段来确定用户的估价范围。有5种类型的用户提交作业。用户的类型t计算方法为(用户ID)%5。日志的用户ID为实数，因此这种分类方法实际上可生成用户的分布。用户的每种类型t关联一个“估价因子”ft。确定用户属于类型t后，利用加速因子及向量f的“估价向量”ft，即可确定用户对批量虚拟机的估价。向量f有5个元素(等于用户类型数)，每个元素表示该类型的用户对“每个单位的加速因子”的平均估价。具体来说，假设有用户uj，其作业的加速因子为Sj，则如果uj属于类型t，则该用户为了能够在一个小时内使用其申请的批量虚拟机，平均愿意支付ftSj。在(0，2ft)生成一个随机数，然后与Sj相乘以生成均值为ftSj的估价。本文使用2组f向量，如表2所示。

表2　仿真参数

CAM-DVMPA机制本身就可确定云供应商需要供应的虚拟机的配置，而CA-GREEDY假设虚拟机静态供应，因此需要提前供应虚拟机配置。为了生成CA-GREEDY需要的虚拟机静态供应，使用的向量h，在仿真中假设有2个h实例。第1个为h=(0.07,0.13,0.27,0.53)，可保证已知权重向量w后，每种类型的虚拟机实例数量相等或基本相等。另一个为h=(0.25,0.25,0.25,0.25)，可保证所有的处理器均衡分布给不同类型的虚拟机。在表2中给出了所有的仿真参数。通过对数值进行全面组合，我们对每个日志文件实验24次，共计264次实验。

4.2结果分析

下面分析了不同负载条件下2种算法的性能。因为工作负载在多个维度上均是异质负载，所以首先定义一个指标来描述工作负载，以便确定它们的次序。然后，对分配机制的性能指标正规化，比较它们相对于工作负载特征的性能。观察表1中列出的负载特点可以确定，对工作负载进行比较的最优指标是正规化负载，定义为

每小时的作业数量×平均运行时间×每个作业的平均处理器数量/总处理器数量

(5)

每小时的作业数量乘以每个作业的平均处理器数量可以获得每小时期间作业需要的处理器数量。然后再与平均运行时间相乘即获得一个小时期间所有作业请求的处理器平均数量估计值。正规化负载可为我们提供负载集合的排序。

对每组仿真实验，计算生成的总营收、总成本及每次拍卖产生的总收益。但是生成工作负载时的系统时间不同，处理器数量也不同。因此，对每小时每个处理器的收益定义为

(6)

类似地，可以定义每个处理器每小时营收及每个处理器每小时成本。

我们在图1a-图1c中分别给出了不同负载日志条件下的平均营收、平均成本和平均收益。图1中的负载按照其正规化负载升序排列。大部分情况下，CAM-DVMPA算法创造的营收更高。对不小于1.44的正规化负载，CAM-DVMPA的营收稳步上升，比CA-GREEDY高出40%。于是我们得出结论，对资源的需求越高，CAM-DVMPA创造的营收越高。

从图1b可以发现，无论负载情况如何，CAM-DVMPA的总成本均比较高。因为CAM-DVMPA是动态确定虚拟机的数量，所以在拍卖时如果申请方相同，则CAM-DVMPA分配的处理器数量高于CA-GREEDY。由于处理器运行时成本较高(cR>cI)，所以分配的处理器越多，生成的总成本也越高。从图1c可以看出，当正规化负载大于1.44时，CAM-DVMPA的收益始终高于CA-GREEDY，且收益间的差异迅速增大。我们也发现，当负载因子低于1.44时，CAM-DVMPA和CA-GREEDY分别领先于对方的情况数量相等。这表明当负载较低时，分配机制的效果取决于其他参数。

在图2和图3中，我们比较了2种分配算法的资源利用率和被服务用户比例。CAM-DVMPA在这两方面的指标数值更高。从图2中可以看到，在大部分情况下，二者的资源利用率相差30%左右。这就是说，如果我们从静态分配策略转向动态供应和分配策略，则在这方面可获得显著的性能提升。因为人们已经认可组合拍卖策略在提高分配效率方面的效果，将其与动态供应结合起来即可提高云计算资源分配机制的效率。

图1　CAM-DVMPA和CA-GREEDY的性能比较Fig.1　Performance Comparison of CAM-DVMPA and CA-GREEDY

从图3中可以看到，CAM-DVMPA可使更多的用户被服务，因为虚拟机实例不是静态供应。因此，如果无VM1实例可用但是有VM2实例可用，此时若采用CA-GREEDY则申请2个VM1实例的用户将申请失败，但是若采用CAM-DVMPA则该用户将申请成功。原因在于，CAM-DVMPA将可用资源看成是2个VM1实例的等价计算资源，因此如果有用户申请2个VM1实例或者申请1个VM2实例，则CAM-DVMPA会将可用资源分配给这些用户，具体分配给哪个用户取决于哪个用户的估价更高。这种机制可使CAM-DVMPA服务更多的CA-GREEDY用户。

图2　不同正规化负载条件下CAM-DVMPA和CA-GREEDY的资源利用率Fig.2　Resourse utilization of CAM-DVMPA and CA-GREEDY under different load conditions

图3　不同正规化负载条件下CAM-DVMPA和CA-GREEDY的服务用户比Fig.3　Service user ratio of CAM-DVMPA and CA-GREEDY under different load conditions

总的来说，当供需匹配时，CA-GREEDY的营收更高。如果拍卖期间的资源不像云拍卖那样可配置， CA-GREEDY拍卖的效率也较高。但是如果资源像云拍卖那样可配置，则难以提前准确预测需求。此时，更应采用CAM-DVMPA机制，随着当今技术的发展，该机制可部署为一种无需大量人工干预的独立配置和分配工具。CAM-DVMPA算法还有另一种用途。可以将CAM-DVMPA和CA-GREEDY结合起来，周期性地运行CAM-DVMPA以确定当前的市场需求，确定与需求最匹配的静态分配策略，然后运行CA-GREEDY。如果资源利用率低于某一阈值，则调用CAM-DVMPA以便再次确定高性能资源配置。这可避免确定CA-GREEDY的高效率静态配置时进行详细的统计分析。

5结论

本文研究了云环境下虚拟机实例的动态供应问题，以便在确定基于组件拍卖的虚拟机分配策略时提高收益。我们提出CAM-DVMPA机制以解决这一问题。利用真实的工作负载数据进行了全面的仿真实验，评估了本文方法的性能。结果表明，CAM-DVMPA可有效确定市场需求，并针对需求供应计算资源，尤其是在需求较高时可提高云供应商的营收。我们认为本文算法是云环境下VM实例分配和供应技术的良好选择。在下一步工作中，我们打算建立一个私有云并在上面部署上述系统。

参考文献：

[1]刘正伟, 文中领,张海涛. 云计算和云数据管理技术 [J]. 计算机研究与发展, 2012, 49(1): 26-31.

LIU Zhengwei, WEN Zhongling, ZHANG Haitao. Research and development of cloud computing and cloud data management technology, 2012, 49 (1): 26-31.

[2]张丽敏. 云计算中一种高效的虚拟机在线动态分配算法[J]. 电信科学, 2015, 31(4): 14-19.

ZHANG Limin. Cloud computing in an efficient online virtual machine dynamic allocation algorithm[J]. Telecom Science, 2015, 31(4): 14-19.

[3]黄莉，丁一，姚锦元，等. 云采购平台虚拟供应商资源动态分配[J]. 计算机应用，2014, 34(2): 377-381.

HUANG Li, DING Yi, YAO Jinyuan, et al. Dynamic allocation of resources for the virtual supplier of cloud platform[J].computer applications,34,2014(2):377-381.

[4]丁晓波，马中，戴新发，等. 一种基于资源预分配的虚拟机软实时调度方法[J]. 计算机工程与科学，2015,37(5)：865-872.

DING Xiaobo, MA Zhong, DAI ,Xinfa， et al. A software real-time scheduling method for virtual machines based on resource pre allocation [J]. computer engineering and science, 2015,37 (5):865-872.

[5]ZAMAN S, GROSU D. Combinatorial auction-based allocation of virtual machine instances in clouds [J]. Journal of Parallel and Distributed Computing, 2013, 73(4): 495-508

[6]KRAKOV D, FEITELSON D G. High-resolution analysis of parallel job workloads[C]∥Job Scheduling Strategies for Parallel Processing. Berlin Heidelberg: Springer, 2013, 178-195

[7]师雪霖, 徐恪. 云虚拟机资源分配的效用最大化模型[J]. 计算机学报, 2013, 36(2): 252-262.

SHI, Xuelin， XUKe，The utility maximization model [J]. Chinese Journal of computers, cloud virtual machine resource allocation 2013, 36 (2): 252-262.

[8]ROUGHGARDEN T. Algorithmic game theory [J]. Commun-ications of the ACM, 2010, 53(7): 78-86.

[9]贲飞,汪芸.云计算下基于容错QoS的虚拟机资源分配策略[J].微电子学与计算机,2013,12(3):33-35.

BEN Fei, WANG Yun. Cloud computing based on fault-tolerant QoS of the virtual machine resource allocation strategy [J]. Electronics and computer, 2013, 12 (3): 33-35.

[10] 谢文静, 唐卓, 杨柳, 等. 基于随机规划的云计算中虚拟机分配优化研究[J]. 计算机工程与科学, 2012, 34(5): 95-100.

XIE Wenjing，TANG Zhuo, YANG Liu， et al. Based on stochastic programming of cloud computing in virtual machine allocation optimization [J]. Computer engineering and science, 2012, 34 (5): 95-100.

DOI：10.3979/j.issn.1673-825X.2016.04.021

收稿日期：2015-05-28

修订日期：2016-06-08通讯作者：许建豪jhaos@163.com

基金项目：国家自然科学基金(61373010，F020501)；广西高校科研项目(YB2014495)

Foundation Items：The National Natural Science Foundation of Chine(61373070,F020501); The Guangxi University Scientific Research Project(YB2014495)

中图分类号：TP391

文献标志码：A

文章编号：1673-825X(2016)04-0585-08

作者简介：

许建豪(1977-)，男，壮族，广西天等人，副教授。主要研究方向为云计算、信息处理。

(编辑：张诚)

Virtual machine dynamic supply and allocation algorithm based on auction in cloud computing

XU Jianhao

(School of Information Engineering, Nanning College for Vocational Technology, Nanjing 530008, P.R.China)

Abstract:Current cloud computing providers allocate their virtual machine (VM) instances via fixed price-based or auction-like mechanisms. However, most of these algorithms require static supply virtual machine, and unable to accurately predict the user demand so as lead to underutilization of resources. Thus, an auction-based algorithm for dynamic VM provisioning and allocation is proposed that takes into account the user demand for VMs when making VM provisioning decisions in this paper. Which treats the set of available computing resource as ‘liquid’ resources that can be configured into different numbers and types of VM instances depending on the requests of the users, and the proposed algorithm determines the allocation strategy based on the users’ valuations until all resources are allocated. Our mechanism is evaluated by performing simulation experiments using traces of real workload from Parallel Workload Archive, the results show that the proposed method can guarantee brings the higher income for cloud providers, and improves the resource utilization rate.

Keywords：cloud computing; virtual machine instances; auction; allocation; cloud providers; resource utilization rate