一种高效的云资源—动态虚拟机实例分配机制

2021-08-12徐友洪

计算机应用与软件 2021年8期

徐友洪李杰,2

1(衢州职业技术学院信息工程学院浙江衢州 324000)2(武汉大学印刷与包装系湖北武汉 430072)

0 引言

云提供商将其资源提供给虚拟机(Virtual Machine,VM)实例，并将它们分配给特定时间段的用户。提供、分配和定价这些VM实例是一个挑战性课题，必须通过云提供商来解决。商业云提供商(如阿里云、腾讯云、百度云及天翼云计算)所采用的固定价格分配机制不能有效地分配VM实例，也不能对动态反映变化的用户需求资源进行定价。经济学理论认为，当拍卖成本较低时，拍卖比固定价格机制更有效，因为产品与估价最高的客户相匹配。特别地，基于组合拍卖的机制最适合云计算中的资源分配，这源于分配需求的特性。组合拍卖中的胜者决定是一个NP-Hard问题，因此要求解这种大量用户和资源的问题相当费时。

文献[1]设计了2种基于组合拍卖的贪婪算法即CA-贪婪算法作为VM实例分配，但假设VM实例是静态提供的，即要求VM实例已经配置好，不能更改。如果这种静态机制不能准确地预测用户需求，则会由于资源利用率不足而导致效率低下。文献[3]提出了一种VM提供的分布式在线聚类算法，并提出了基于模型的方法来生成长期的工作负荷估计，但这种算法过于依赖工作负荷的特点，需要对工作负荷特性进行预测来捕获当前的VM需求，这无疑限制了用户的扩展并增加了分配机制的复杂性。为解决虚拟机调度分配的多目标优化问题，文献[4]提出了一种适用于云环境下虚拟机调度的优化方法，这种提供机制主要支持云中科学应用的实现而限制了应用范围。文献[5]采用基于多代理的协商模型来处理网格资源所有者和网格资源使用者之间的交互，设计了市场和行为驱动的谈判代理机制。测试结果表明，该协商模型能够较好地实现协商决策和预算支出，存在的主要不足在于资源使用者和网格资源所有者必须交互协商，这种谈判机制降低了资源的实时有效利用。文献[6]针对云资源的在线分配进行了研究，建立基于拍卖的在线云资源分配机制，这种云资源定价模型存在扩展局限性。文献[7]提出的资源市场分配和定价是采用计算资源的交换市场来确定的。在交换中，服务提供商和用户表达他们的标价和出价，只有匹配正确才被准予分配，显然降低了效率。文献[8]研究了异构网络中基于势博弈和演进博弈的联合资源分配算法，主要目标是实现无线资源和云资源的协调管理，而对资源提供商的经济利益考虑较少。文献[9]提出了关于组合拍卖的基础知识，未对组合拍卖的具体实施策略和机制进行深入研究。文献[10-11]针对组合拍卖的复杂性和专一投标人的组合拍卖进行了研究，但仅考虑了胜者决定和贪婪组合拍卖，这仅对获胜用户有利，忽略了出价低的用户，从而导致资源的分配不均。文献[12-13]提出了在专一环境下真实机制设计的附加构建技术，但这种专一环境排除了大多数提供商和资源用户的复杂环境，因而不具有可扩展性。文献[14]提出了一种均衡价格拍卖机制，该机制为采购拍卖提供了近似解，但不能保证真实性。文献[15]将资源分配问题构建为一种采购拍卖，该模型中，用户向拍卖代理表达他们的需求，云提供商参与由代理运行的拍卖。这种机制假设存在几个云提供商，拍卖在它们之间进行，但这种机制仍然不是真实的。

本文提出了一种用于云中动态虚拟机实例分配机制。该机制在作出分配决策时考虑了变化的用户需求，还考虑了保留价格和确定的方法，并证明了其是真实的，即保证了一个参与用户仅有通过投标其对VM包的真实估价来最大化其效用。最后通过采用来自于并行工作负荷存档中的归一化工作负荷进行大量的仿真实验评价了本文算法的性能。实验结果表明，本文提出的算法机制不仅能为云提供商带来更高的收益，而且还提高了云资源的利用率。

1 问题建模

虚拟化技术允许云计算提供商将计算资源配置到几乎所有不同类型VM的组合中，因此，可以通过组合拍卖确定VM实例的最佳组合，然后动态地提供。这将确保基于市场需求来确定不同类型的VM实例数量，然后有效地分配给用户。本文构建的动态VM提供和分配问题如下。

将m种有差别的VM实例VM1,VM2，…,VMm计算服务提供给用户。一个VM实例类型VMi(i=1,2,…,m)的计算能力假设为wi，这里w1=1,w1

为了创建最小计算能力类型的M个VM实例，云提供商可以根据VM1,VM2,…,VMm给定的指定类型，以多种方式提供VM实例。将提供的VMi实例的数量表示为ki，则提供商可以提供由向量(k1,k2,…,km)给定的任意实例组合，只要：

(1)

(2)

考虑成本cR和cI的目的是在需求非常低或用户估价过低时减少云提供商的损失。在这两种情况下，通过拍卖将资源分配给用户将导致用户付费非常低，这将间接导致拍卖商的收入损失。正如后面将看到的，考虑这些成本有助于确定一个保留价格，以阻止出价极低的用户参与拍卖，并隐含地保证提供商在需求低时仍能获得一些利润。

这样，就可将动态VM提供和分配问题构建为：

maxΠ

(3)

(4)

xj∈{0,1}j=1,2,…,n

(5)

0≤pj≤vjj=1,2,…,n

(6)

目前的云服务提供商采用固定价格机制分配VM实例，且依赖于统计数据以静态方式提供VM。而通过动态方式选择VM实例集，反映了拍卖时的市场需求，可以提高系统的总体性能。因此，本文提出一种算法机制，通过确定云提供商需要提供的VM的分配、定价和最佳配置来求解云中动态VM提供和分配问题，以获得更高的利润和资源利用率。

2 动态虚拟机实例分配算法

2.1 算法原理及实现

本文提出的动态虚拟机实例分配算法简称为DVMIA(Dynamic Virtual Machine Instances Allocation)算法。算法决定获胜用户必须支付的价格，以及为满足获胜用户需求需要提供的VM实例集，还确保分配最大可能的资源，并且任何VM实例都不会以低于保留价格的价格分配。

DVMIA算法采用投标密度来决定分配。用户uj的投标密度定义为：

dj=vj/sj

(7)

DVMIA算法首先收集用户的投标，计算出全部投标的投标密度，并根据他们的投标密度对投标进行排序，然后计算保留价格，并丢弃投标密度低于保留价格的投标；接下来将计算资源按排序分配给用户，并提供相应的资源；最后，计算每个获胜用户的付款，即他们必须支付给云提供商的金额。付款是获胜用户为获得其所要求的资源而必须出的最低价(即临界支付)，全部失败用户的支付为零。算法1给出了DVMIA算法的实现原理。算法需要来自系统的一些信息，如计算资源总量M，表示为由云提供商可以提供的VM1类型的VM总数量，算法还需要输入可用VM类型的数量m以及它们的权值向量w，还需要知道cR即运行一个VM1类型的VM实例的成本以及即保持一个VM1类型的VM实例空闲的成本cI。

算法1DVMIA算法

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

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

1.{阶段一：收集投标}

2.forj=1,2,…,ndo

4.endfor

5.{阶段二：胜者决定和提供}

6.W←∅{胜者集合}

7.vres←cR-cI

8.添加投标B0=(1,0,0,…,0,vres)的虚拟用户

9.forj=0,1,…,ndo

11.dj←vj/sj{计算投标密度}

12.endfor

13.重排序用户u1,u2，…,un，以使d1≥d2≥…≥dn

14.令l为指标以使如果j≤l，dj≥d0，否则dj

15.丢弃用户ul+1,…,un

16.重命名用户u0为ul+1

17.n←l+1

18.M←R

19.forj=1,2，…,n-1do{删除虚拟用户}

20.ifsj≤Rthen

21.W←W∪uj

22.R←R-sj

23.endif

24.endif

25.fori=1,2,…,mdo{确定VM配置}

27.endfor

28. {阶段三：支付}

29.for全部uj∈Wdo

32.pj←dlsj

33.endfor

34.for全部uj∉Wdo

35.pj←0

36.endfor

37.return(W;pj:j=1,2,…,n;ki:i=1,2,…,m)

2.2 DVMIA算法创新特性分析

算法的一个重要创新就是激励相容性，也称为真实性，因为算法计算分配和支付是基于用户报告的信息(即投标)，这是私人信息。一个理性的用户可以通过投标虚假的估价来操纵这个机制，这样对其有利。因此，设计这种算法的挑战包括设计胜者决定和支付功能。支付功能给予用户真实的投标激励，因为参与真实分配的用户不必采用复杂的投标策略来最大化他们的效用，他们只需要对VM包给出他们的真实估价。

(8)

也就是说，如果分配了所请求的包，则用户uj将获得vj的估价，否则，估价为0。用户uj从获得请求包中得到的效用是其估价Vj与付款pj之间的差值：

(9)

一般来说，用户会基于理性来最大化他们的目标效用。一个真实的机制要确保一个用户只有通过对包出价真实估价来最大化其效用。下面定义真实机制的概念。

(10)

也就是说，参与真实机制的用户仅通过为竞价其包的真实估价来最大化其效用，而不管其他用户的出价。

即在临界支付函数下，获胜用户支付其临界值，而失败用户支付零，即该机制是一个规范化机制。

下面提出2个引理和1个定理来证明DVMIA算法是真实的。

引理1DVMIA算法实现一个单调的分配函数。

引理2DVMIA算法向获胜用户收取他们的临界支付。

证明：为了得到获胜用户uj的支付，DVMIA算法要找到一个失败用户ul，当用户uj不参与时，他会赢。这意味着用户uj需要击败用户ul，以获得他所请求的包(即dj≥dl)，这也意味着vj/sj≥dl，因此vj≥dl·sj。DVMIA算法收取用户uj的费用为pj=dl·sj，这是uj必须出价才能获得他所请求的包的最低估价。失败用户支付零费用。因此，DVMIA算法实现了临界支付。

定理1DVMIA算法是真实的。

证明：根据引理1和引理2，DVMIA算法实现了一个单调的分配函数，并向获胜用户收取他们的临界支付，因此DVMIA算法是一个真实的机制。保留价格不影响机制的真实性，因为保留价格基本上是由云提供商控制的虚拟用户提出的投标，而真实投标仍然是用户的主导策略。

3 实验

本文采用来自网格和超级计算站点的并行工作负荷存档中经过归一化的工作负荷进行仿真实验来评价本文提出的DVMIA算法，并将其与文献[1]提出的两种基于组合拍卖的CA-贪婪算法进行比较。文献[1]的原CA-贪婪算法采用静态VM提供，其改进的CA-贪婪算法考虑了每种类型VM实例的预测需求。

3.1 实验设置

实验包括从给定的工作负荷生成作业提交，然后运行算法来分配作业和提供VM。来自于网格和超级计算站点的工作负荷存档经过归一化的工作负荷的基本描述如表1所示，包含了日志文件的名称、记录日志的时间长度、提交的作业总数及系统中可用处理器总数；表2列出了全部仿真参数。

表1 工作负荷日志

表2 仿真参数

3.2 实验结果及分析

图1(a)-图1(c)所示为每个处理器每小时平均利润、平均收入和平均成本与归一化负荷的关系。由图1(a)可以看出，对于大于0.6的归一化工作负荷，DVMIA算法比CA-贪婪算法能获得更高的利润，而且两种算法的利润差越来越大；由图1(b)可以看出，DVMIA算法得到了更高的收入，而且对于大于0.6的归一化工作负荷来说，由DVMIA算法所获得的收入是迅速增加的。因此在资源需求很高的情况下，DVMIA算法能够获得更高的收入。通过图1(c)可见，DVMIA算法会使得全部工作负荷的总成本更高。由于DVMIA算法是动态决定VM的数量，因此在相同竞拍者的拍卖中，可以比CA-贪婪算法分配更多的VM实例，这就导致了更高的成本。这也验证了上文分析：一个单位VM实例在空闲时每单位时间花费cI，在运行时(即分配给用户)每单位时间cR>cI，因此通过提供和分配更多的VM实例，DVMIA算法会给云提供商带来更高的成本。

(a) 每个处理器每小时平均利润

图2(a)、图2(b)分别比较了2种算法获得的资源利用率、服务的用户百分比与归一化负荷的关系。显然，DVMIA算法对于资源利用率和服务的用户的百分比都获得了更高的值，在大多数情形下，DVMIA算法的资源利用率平均高于CA-贪婪算法约25百分点，服务的用户的百分比平均要高约33百分点。对于DVMIA算法来说，服务的用户数更多，是因为VM实例不是静态配置的。对于CA-贪婪算法，当VM1实例不可用，而VM2实例是可用的时，则对于有2个VM1实例请求的用户来说，将不会被分配，而DVMIA算法将其分配给为2个VM1实例进行投标的用户或为1个VM2实例进行投标的用户，这取决于谁报的估价更高，这就增加了DVMIA算法服务的用户数量。

(a) 资源利用率

实验评价了DVMIA算法与改进的CA-贪婪算法的平均利润和资源利用率，结果如图3所示。改进的CA-贪婪算法考虑了每种类型VM实例的预测需求。从图3(a)可见，即使采用预测需求，CA-贪婪算法也无法获得DVMIA算法所获得的利润；从图3(b)可见，带有需求预测的CA-贪婪算法也无法获得DVMIA算法所获得的资源利用率水平。主要是由于考虑的每种类型的VM实例的数量随时间变化很大，故需求预测的CA-贪婪算法对一个时间窗口的平均值无法很好地捕捉需求，也就无法提高资源的利用率。