多维度资源环境下基于矢量代数模型的虚拟机部署

张 扬 刘 进

1(广西工业职业技术学院 广西 南宁 530001)2(广西大学计算机与电子信息学院 广西 南宁 530004)

0 引 言

为了满足用户对于计算能力的快速增长的需求，诸如Amazon和Google等云供应商可以在全世界范围内部署数以百万计的大规模数据中心提供相应计算能力，以此实现云计算能力[1]。作为一种新兴的计算模式，云计算可以以虚拟化形式提供无限的计算、存储和通信资源能力，而处于互联网上的用户可按其需求以即付即用的商业模式使用这些资源。研究表明，由于整个云系统中服务器与数据设备的能耗已经占据数据中心能耗的55%以上[2]，能耗问题已经成为管理云数据中心的总体拥有成本TCO的关键问题。大规模数据中心的高能耗会导致更大的碳排放，对大气产生不利影响。资源利用不充分是导致高能耗的另一个重要问题，由于传统的数据中心中，服务器的满负载运行仅占总运行时间的10%～15%，这会导致资源过量提供的浪费。由于云系统可通过弹性方式提供虚拟的未受限且安全可用的服务资源，因此，云数据中心中资源提供的过量成为一种普遍现象。

虚拟化技术可使数据中心在单个服务器上部署多个虚拟机VM实现资源利用与能效的提升，在维持应用性能需求的同时，通过转换物理服务器至低功耗状态实现能耗的降低[3]。基于此考虑，本文提出一种基于蚁群优化的虚拟机VM合并算法ACO-VMPC，求解不同资源类型情况下的资源利用均衡问题。算法利用基于矢量代数的方法建立了多维资源利用获取模型，进而实现资源利用的提升与能耗降低的同步优化目标。

1 相关研究

虚拟机部署与合并是虚拟云数据中心中降低能量成本和提高资源利用率的常用手段。大多数研究应用贪婪启发式方法将VM合并建模为装箱问题，并设计了相关装箱贪婪算法进行问题求解，如：首次适应递减算法FFD[4]、最佳适应算法BF[5]、最佳适应递减算法BFD[6-7]等。然而，VM合并作为NP-hard问题，贪婪方法无法确保产生近似最优解。而且，大多数方法在进行资源利用平均值的估计时，均无法获取服务器资源的多维利用率。

约束规划CP模型是求解VM合并的另一种常用方法。文献[8]提出一种VM提供与部署方法，可以实现云数据中心中较高的VM装配效率。文献[9]设计了一种服务器合并管理方法，可以在集群中实现最小化的活动服务器数量和VM迁移开销。然而，CP模型的应用会限制数据中心中服务器与VM总数量的域，从而限制搜索空间。

目前，蚁群优化算法ACO已经证明可成功求解一维装箱与虚拟机合并问题。文献[10]结合局部搜索算法提出一种基于ACO的装箱问题求解方法。文献[11]则设计一种性能优于遗传算法的改进ACO装箱求解方法。文献[12]提出了一种性能优于FFD的改进ACO进行VM合并求解。然而，算法仅仅评估了在维持其他资源需求不变时，VM所需求的处理器数量发生改变时的情形，这实质上已简化为一维资源模型。文献[13]设计一种多目标ACO算法降低云数据中心的资源浪费和功耗，文中考虑了两种资源(CPU和内存)，并证明了算法性能优于遗传算法和传统ACO算法。

综合分析，当前工作拥有以下几点不足：1) 缺乏对多维度资源利用率的建模与分析，而云数据中心是可提供多种类型的资源；2) 在进行虚拟机部署时未考虑数据中心能耗与资源利用率均衡优化。结合以上两点，本文设计一种基于蚁群优化的虚拟机部署与合并算法，引入多维度资源利用模型，并基于矢量代数获取多维度资源的利用信息，最后利用蚁群优化的手段，同步优化多维度资源环境下云数据中心的资源利用率与能耗，获得最优的虚拟机部署解。

2 虚拟机合并模型

云供应商可以提供对于每种资源特定需求的不同VM，该VM实例在其个体资源能力上各不相同。云VM实例可寄宿不同种类的应用，适应实时的动态资源需求，以获得并适应负载的动态预测与评估。由于VM实例与动态负载具有这些特征，云数据中心中在不同资源维度间进行资源需求的互补是常见的。进一步，由于云的提供方式为按需和即付即用，用户可以根据其需求随机创建和终止若干VM服务。由此，云数据中心中的VM创建与终止是实时动态的，这将导致服务器资源的分割，从而降低服务器资源利用率。VM合并是虚拟数据中心中解决以上难题的常用手段，它可以在考虑多维度资源需求的情况下在最小数量的物理服务器上进行VM的装箱，以实现节省能耗和最大化服务器资源利用率的目的。

2.1 多维矢量装箱下的虚拟机部署模型

(1)

式中：x为VM与PM间的部署矩阵。

(2)

令y为PM分配矢量，当Pi上至少部署一个VM时，元素yi=1，否则yi=0，表示为：

(3)

ACO-VMPC算法的目标即为在可用物理主机PM上部署VM，并实现：1) 在所有维度上活动PM的资源利用率最大化；2) 活动PM的功耗最小化。由于数据中心中服务器的功耗主要集中于CPU的运行，那么，活动PM的数量越少，所有维度上的资源利用越高，能耗也越少。因此，将目标函数f形式化为y上的单目标最小化函数，表示为：

(4)

PM的资源能力约束(即：对于每一资源类型，所部署的VM的需求Dk不能超过主机PM的资源能力Ck)可表达为：

(5)

同时，需要确保每个VM至多分配至一个PM上，即：

(6)

2.2 基于矢量代数的多维资源利用模型

在PM上部署VM时，对于任意部署与合并算法而言，最重要的是度量多资源类型下的全局利用率，由于可能出现单一资源类型过载而无法改进其利用率，而其他类型的资源未充分利用，出现低载情况。为了取得资源利用的均衡和全局资源利用率的提高，本文在部署算法中设计一种基于矢量代数的资源互补性利用获取机制。模型在VM合并过程中考虑CPU、内存和网络I/O三种服务器资源，PM的标准资源能力表示为单元立方(Resource Cube)，三个维度分别代表三种资源类型。RCV和RUV分别表示PM的总资源能力和当前资源占用。为了度量PM当前资源占用的不平衡度，引入资源不平衡矢量RIV计算RUV与RCV间的矢量差。给定一个PM在部署一个VM后的RUV=Ci′+Mj′+Ik′，C、M和I分别为CPU、内存和网络I/O的当前资源占用情况，RIV=(C-H)i′+(M-H)j′+(I-H)k′，H=(C+M+I)/3。当选择VM至PM上进行部署时，拥有最小RIV的VM即为所有不同维度下PM资源占用最平衡的目标VM。RIV的计算方法为：

(7)

2.3 资源占用与浪费模型

(8)

式中：R={CPU,MEM,I/O}。类似地，资源浪费可定义为每个单个资源的剩余标准化资源的总和：

(9)

2.4 功耗模型

(10)

式中：Efull和Eidle分别为当PM完全利用(即CPU100%繁忙时)和空闲时的平均能耗。由于服务器的功耗利用是非正比例的，在VM部署后可关闭或挂起空闲服务器。因此，VM部署决策x下的总能耗可表示为：

(11)

3 ACO-VMPC算法设计

3.1 基于ACO的VM合并

ACO是受蚂蚁种群行为启发形成的一种智能计算方法，其智能蚂蚁的数量即代表所优化问题的解，该解是通过不断选择可行解的成分并以信息素度量解的质量的形式获取的。ACO-VMPC算法中，将VM与PM间的分配方式定义为解的成分，与所有VM-to-PM分配所关联的信息素等级则代表一个VM至一个PM的分配意愿，然后动态地计算每个VM-to-PM对的启发值，该启发值即代表PM上全局资源利用与平衡资源利用两个目标上分配VM时所考虑的偏好。

3.2 算法步骤

ACO-VMPC算法的伪代码如算法1所示，其详细解释如下：算法输入包括主机PM集合P、主机的总资源能力RCV、虚拟机集合V、VM的资源需求矢量RDV、蚂蚁集合及相关蚂蚁算法参数，输出为蚂蚁寻优后得到的全局最优部署解GBS。步骤3对蚂蚁算法的相关参数进行初始化设置，并为每一个VM-PM对设置信息素，且全局最优解置为空。信息素等级利用n×m的矩阵τ表示。每只蚂蚁由一个空解、一个PM集合和一个随机VM集合开始执行(步骤6-步骤12)。在while循环体内，蚂蚁被随机选择，并利用概率决策规则在所有可行VM中选择一个VM分配至当前PM(步骤11-步骤22)。如果当前PM被充分占用或有不可行VM分配至PM上，则启用一个新的空闲PM进行部署VM(步骤14-步骤16)。

当所有蚂蚁建立了相应解后，比较当前循环中的所有解，寻找依据目标函数f(式(4))得到的全局最优解GBS，拥有最小目标f值的解则选择为当前的GBS(步骤23-步骤28)。计算信息素增加量，对每个VM-PM对的信息素等级进行更新，以模拟蚂蚁信息素的挥发和沉积(步骤29-步骤34)。算法仅增加属于GBS中的VM-PM对的信息素。然后，重复搜索新解的过程，直到解的质量无法进一步改进为止，即步骤35。

算法1 ACO-VMPC算法

1. Input:set of PMsPand their RCVCi, set of VMsVand their RDVDj, set ofantsantSet, set of parameters{nAnts,nCycleTerm,β,ω,δ,q0}

2. Output:GBS

3. initialize parameters,set pheromone value for each VM-PM pair(τv,p) toτ0,GBS=∅,nCycle=0

4. repeat

5. for allant∈antSetdo

6.ant.solution=∅,ant.pmList=P

7.ant.p=1,ant.vmList=V

8. Shuffleant.vmList

9. end for

10.antList=antSet,nCycle=nCycle+1

11. whileantList≠∅ do

12. pick anantat random fromantList

13. ifant.vmList≠∅ then

14. ifFVant(ant.p)=∅ then

15.ant.p=ant.p+1

16. end if

17. choose a VMvfromFVant(ant.p) accord.to Eq.16

18.ant.solution.xp,v=1,ant.vmList.remove(v)

19. else

20.ant.solution.f=p,antList.remove(ant)

21. end if

22. end while

23. for allant∈antSetdo

24. ifant.solution.f

25.GBS=ant.solution

26.nCycle=0

27. end if

28. end for

29. compute △τ

30. for allp∈Pdo

31. for allv∈Vdo

32.τv,p=(1-δ)×τv,p+δ×△τv,p

33. end for

34. end for

35. untilnCycle=nCycleTerm

以下描述算法过程中的详细步骤：

1) 信息素与初始信息素总量的定义。ACO算法的开始，蚁群开始行动时，每个VM-PM解的成分均拥有固定量的初始信息素。参考FFDL1Norm算法[11]产生的解计算初始信息素的量：

τ0=PEFFDL1Norm

(12)

式中：PEFFDL1Norm为FFDL1Norm算法得到的解的装箱效率PE。算法产生的任意解sol的PE为：

(13)

2) 启发信息的定义。搜索解的过程中，启发值ηv,p代表选择解成分v-p的收益度量。由于ACO-VMPC算法的目标是以均衡方式对VM进行装箱从而降低活动PM的数量，本文将启发值定义为同时偏好均衡所有维度的资源利用和更高的全局资源利用率，即：

ηv,p=ω×|lgmagRIVp(v)|+(1-ω)×Utilizationp(v)

(14)

式中：magRIVp(v)为分配VMv后PMp的RIV值。magRIVp(v)的对数用于为导致更小RIV的v-p对赋予更高的启发值。参数ω为均衡资源均衡利用与全局资源利用的相对因子。Utilizationp(v)为当分配VMv时PMp的全局资源利用：

(15)

3) 伪随机正比例规则。构造分配解时，一个蚂蚁k根据以下的伪随机正比例规则选择VMs分配至PMp：

(16)

式中：q为[0,1]间的随机数，q0为区间[0,1]间的参数，τv,p为当VM-PM对v-p时的当前信息素值，β为非负参数，表示在决策规则中信息素量与启发值间的相对因子。FVk(p)定义为蚂蚁k分配至PMp的可行VM集合：

(17)

若q≤q0，得到更高τv,p×[ηv,p]β值的v-p对被选择为解的成分；否则，依据以下随机正比例规则得到的概率Pk(v,p)选择VMv：

(18)

4) 全局信息素更新。为了使算法在子迭代中得到全局最优解GBS，信息素的全局更新规则将应用于每个v-p对的信息素值上，具体规则为：

τv,p=(1-δ)×τv,p+δ×Δτv,p

(19)

式中：δ为全局信息素延迟参数，且0<δ<1；Δτv,p为应用于每个v-p对上的信息素加强值。

(20)

4 实验分析

由于缺乏大规模测试床和可重复实验的现实云环境设施，本节采用仿真评估的方法分析所提算法的性能，仿真环境为CloudSim，编程环境为Java。CloudSim平台具有开源性，且使用最广泛，其内核提供了虚拟引擎，可以在单个数据中心节点上创建并管理多个独立、协同的虚拟机，并基于GridSim和离散事件驱动，可以模拟创建多种云计算环境中的实体，包括可以创建数据中心、物理服务器、虚拟机以及组件间可进行的消息传输，及消息的时钟管理等。仿真环境中构建的云数据中心由异构主机PM集群组成，对于每种资源类型的VM资源需求可表示为PM总资源能力的百分占比。同时，利用参考VM资源需求Ref=z%的形式表示每种随机产生在区间[0,2z]中的VM资源需求Dr，r∈{CPU,MEM,I/O}。实验中分别设置参考值为Ref=10%,15%,20%，25%，对应的期望平均PE=10,6.7,5和4。在仿真平台下，为了实验结果的一般性，利用相同的参数配置，构建10次独立的仿真实验，且每个实验运行20次，结果取其平均值。与ACO-VMPC相关的蚁群优化参数设置如表1所示。

表1 蚁群相关参数设置

选择以下几种算法进行性能比较：1) 文献[12]提出的基于自适应最大最小蚁群优化的VM合并算法MMVMC；2) 文献[10]提出的矢量贪婪算法VectorGreedy，在多维资源的评估方面同样使用了矢量代数机制进行VM合并；3) 文献[6]提出的基于列的平均评估算法FFDVolume；4) 文献[11]提出的基于L1标准平均评估的FFDL1Norm算法。

图1-图4给出了1 000个VM需求时算法的各项性能指标，包括活动PM的数量、VM装箱效率、总体功耗及能效改善效率。实验中设置Eidle=162 W，Efull=215 W。由图可知，ACO-VMPC在各项指标上均优于其他算法。同时，ACO-VMPC算法获得了接近于期望平均值的PE。以上结果表明，ACO-VMPC算法中的信息素更新机制和伪随机正比例规则下的蚂蚁寻优是有效可行的，它可以找到虚拟机与主机间的能效最优映射解。相比而言，MMVMC算法得到的活动PM数量仅次于本文算法结果，原因在于该算法采用了自适应最大最小蚁群优化机制，但其信息素的更新机制是基于传统蚁群搜索算法的。另外三种算法中，矢量贪婪算法VectorGreedy综合性能是最优的，它与另外两种算法的最大区别在于有效地进行了虚拟机的合并，这使得最终的活动的主机数量有所降低，资源利用率也更高。

图1 活动PM数量对比图

图2 PE值对比图

图3 能耗对比图

图4 ACO-VMPC相比基准算法得到的能效改善比例

图5给出了算法得到的活动PM的总资源浪费情况，以标准化百分比表示，部署VM数量为1 000。结果表明，ACO-VMPC算法较其他算法极大降低了资源浪费，这是由于ACO-VMPC在每个服务器上以互补性的资源需求进行了VM合并，改善了全局资源利用，从而实现了在不同资源维度上降低资源浪费的目的。其他四种算法中，MMVMC算法采用了自适应最大最小蚁群优化机制，相对而言比另外三种算法得到资源利用率更高，浪费率更低，但其传统的信息素更新机制在进行蚂蚁寻优时的效率仍然低于本文算法ACO-VMPC，故其资源浪费率高于ACO-VMPC。矢量贪婪算法VectorGreedy同样利用了虚拟机合并机制，在多数的VM需求比例下的资源浪费率要低于FFDL1Norm和FFDVolume算法，说明动态的虚拟机合并对于提高资源利用率的重要性。

图5 资源浪费比例

为了观察ACO-VMPC算法的时间复杂性，图6给出算法获得最优解GBS时的计算时间。实验仿真环境配置为Core i5-2400 3.10 GHz CPU(4 cores)和内存4 GB的工作站主机，编程语言为Java环境。可以看出，算法的计算时间会随着VM数量的增加基本呈现非线性递增，且递增幅度较小，平均花费时间约为25 s。由此可见，在虚拟机规模增大使得算法搜索最优解空间的增加的情况下，本文算法的运行时间并未出现过快的增加，这得益于寻优过程中信息素更新机制和伪随机正比例规则下的蚂蚁寻优是有效可行的，算法具有很好的适应性。

图6 ACO-VMPC算法的计算时间

5 结 语

为了优化云数据中心的能耗与资源利用率，本文提出一种基于蚁群算法的虚拟机部署与合并算法。算法首先将虚拟机合并问题形式化为多维度装箱问题，然后，设计了基于矢量代数的多维资源利用模型，从而获取资源的利用与浪费模型，最后通过改进的蚁群优化算法求解虚拟机合并问题。仿真实验验证了算法的性能。