0 引言

随着云服务市场的迅速发展，数据中心能耗问题愈发突出^[1]。2015年，我国数据中心总量已超40万个，年耗电量超过全社会用电量的1.5%^[2]。提高数据中心服务器资源利用率，降低能耗，成为了当前数据中心亟待解决的问题^[3]。解决该问题的一个常见手段是利用虚拟化技术进行服务整合：也就是把服务请求进行整合，减少活动物理机数量，从而提高资源利用率，减少能源消耗^[4]。由此产生了虚拟机放置(Virtual Machine Placement, VMP)问题：根据一定的方法和策略，把虚拟机(Virtual Machine, VM)放置在最适合的物理机(Physical Machine, PM)中。

目前对于VMP的研究，一般是在假设数据中心物理机完全同构的前提下，仅着眼于改进放置算法本身。有些研究虽然考虑了物理机异构，但是没有分析虚拟机资源需求分布特征与异构云环境之间的关联。现实生活中，数据中心往往拥有多种物理机资源配置，是一个异构的云环境，而虚拟机需求的分布特征也多种多样。虚拟机需求分布的变化，反映到异构物理机上就会使得所需异构物理机数量也发生变化。

针对异构云环境下的虚拟机放置问题，本文依据虚拟机资源需求分布特征的变化并将其与异构物理机的配置比例关系相联系，提出一种分两步进行的基于虚拟机资源需求分布特征的放置算法(Resource Demand Distribution Feature based Placement Algorithm, RDDFPA)。首先，利用异构物理机资源配置和虚拟机资源需求分布特征的比例关系对虚拟机需求集合进行划分，虚拟机需求子集合的变化使得不同配置物理机产生数量变化；其次，利用启发式算法，在对应配置物理机上，对划分后的虚拟机需求进行放置。实验结果表明，相比直接在同构物理机上执行启发式算法进行放置，应用该算法在异构云环境下进行的虚拟机放置使用的活动物理机数量更少，资源利用率更高，能耗更低。

1 现有VMP研究

VMP的难点在于它是一种NP-Hard问题，甚至是NP-完全问题，难以在多项式时间内解决^[5]。根据云环境的同构与异构来对现有研究进行分类。

在同构云环境基础下，主要以改进放置算法本身为主。常用算法有两种，即启发式算法和元启发式算法。

启发式算法的特点在于它可以在物理机和虚拟机数量较多，求最优解难度较大、耗时较长的情况下，以较小的开销找到一个相对合理的近似解^[6]。经典的算法有首次适应(First Fit)算法、最佳适应(Best Fit)算法等^[7]。改进算法如Lee等^[8]提出的两个具有节能效果的启发式服务整合算法，其目的是最大化物理机的利用率，从而减少活动物理机数量，节约能耗。

元启发式算法的特点在于该类算法能较好地找出全局最优解，但是其时间复杂度较高，导致可扩展性和实时性较差^[6]。较为常见的元启发式算法有蚁群算法：Gao等^[9]把同构环境下虚拟机的放置问题看作一个多目标优化问题，提出了一种多目标蚁群算法，以降低系统的能源消耗、提高物理机的资源利用率。还有诸如遗传算法^[10]和模拟退火算法^[11]等。

针对异构云环境，目前的研究相对较少。Beloglazov等^[12]考虑了异构性问题，提出一个能源感知的资源分配启发式算法，将虚拟机放置在一个使系统能源消耗增加最少的物理机上。但该算法只考虑CPU需求，并没有考虑所需资源的多维性。周东清等^[4]考虑了资源的多维性，提出一个启发式算法，在异构物理机上利用权重来分配虚拟机，同时保持一定的负载均衡。Shi等^[13]考虑了服务器的异构性，提出了按照物理机不同资源配比进行虚拟机分配的启发式算法。这些研究都没有考虑到虚拟机需求的分布变化，并将其与异构物理机的配置或数量相联系。

2 异构云环境下资源需求分布的具体描述 2.1 虚拟机资源需求分布的具体描述

虚拟机需求集合由一系列的虚拟机需求组成，定义为S_vm。S_vm中的每个虚拟机需求对不同类型资源需求往往具有偏向性。按照偏向性，可把集合中的虚拟机划分为两类：CPU处理能力偏重的计算密集型和内存空间偏重的数据密集型。假设第k个虚拟机包括两种资源需求：CPU处理能力CPU_vmk和内存空间MEM_vmk，CPU处理能力的单位为每秒百万条指令(Million Instructions Per Second, MIPS)，内存空间(MEMory, MEM)的单位为GB。虚拟机需求配置比例计算公式为：

$ rat{e_{v{m_k}}} = CP{U_{v{m_k}}}/ME{M_{v{m_k}}} $

(1)

根据每个虚拟机的配置比例rate_vm，从小到大对S_vm内的虚拟机需求进行排序，便得到一个排序后的虚拟机资源需求分布序列sortedList_vm={vm₁, vm₂, …, vm_n}。

2.2 异构云环境的具体描述

本文中，异构云环境由两种具有不同资源偏向性且和虚拟机资源需求分布相对契合的物理机组成。结合实际，选出两种物理机构成异构物理机组pair_pm={pm_left, pm_right}。其中pm_left为数据密集型，配置比例为：

$ rat{e_{p{m_{{\rm{left}}}}}} = CP{U_{p{m_{{\rm{left}}}}}}/ME{M_{p{m_{{\rm{left}}}}}} $

(2)

另一种物理机pm_right为计算密集型，配置比例rate_pmright大于rate_pmleft。

2.3 虚拟机资源需求分布的跨度分类

虚拟机资源需求分布的变化，体现为序列sortedList_vm分布范围的不同，在以资源配置的比例为坐标的数轴上，即表现为从rate_vm1至rate_vmn的区间长度。依据区间长度在数轴上做椭圆，来表示sortedList_vm的分布范围，本文称其为分布跨度。而根据物理机资源配置的比例也可以在该数轴上标识异构物理机组的位置。至此，数轴就可以直观地展示出sortedList_vm和pair_pm的关系。根据虚拟机需求分布可能出现的情况，并结合异构物理机组的配置比例，如图 1所示，大体可以使用四种跨度情况来囊括。

2.4 问题描述

在本文提出的算法中，通过研究异构物理机组和虚拟机资源需求分布特征之间的资源比例关系，在执行虚拟机放置算法之前对虚拟机资源需求分布进行划分处理，从而更好地放置虚拟机，达到减少活动物理机、节约能耗的效果。具体问题可以分解为以下几个部分：

1) 依据虚拟机资源需求集合特征和异构物理机组的关系，判定跨度情况；

2) 划分虚拟机资源需求集合，使其分别与两种异构物理机相匹配；

3) 在两种物理机上分别进行虚拟机放置。

3 算法描述

本文提出的RDDFPA具体可以分为两大阶段：

第一阶段依据虚拟机需求分布和物理机资源配比的关系，在排序后的sortedList_vm上取得一个划分点；

第二阶段在取得划分点后，将划分后的虚拟机需求分别在相应侧物理机上使用启发式算法进行放置。

其中第一阶段可以细分为：比例数轴的预处理；确定虚拟机资源需求分布跨度；获取虚拟机序列分界点；判断划分点。

3.1 比例数轴的预处理

如图 1所示，本文以pm_left的资源比例rate_pmleft和pm_right的资源比例rate_pmright之间的中点作为数轴的中心点，称为异构物理机组中心点center。center的作用在于：依据不同配置的pair_pm确定相应的center，由此可以界定虚拟机资源需求的偏向性，即位于center左侧的虚拟机资源需求为计算密集型，位于右侧则被认为是数据密集型。

根据rate_pmleft和rate_pmright，在数轴上标识出pair_pm的具体位置，得出比例跨度[rate_pmleft, rate_pmright]，并依据它确定数轴的异构物理机组中心点center。

center的具体取值方式为：center并非数轴上两种物理机之间的距离中点，而是比例中点，此例中center应位于1/1处。对两侧物理机的CPU处理能力之和与内存空间之和求商，便可得到正确的center比值rate_center，即使用式(3)计算:

$ rat{e_{{\rm{center}}}} = \frac{{CP{U_{p{m_{{\rm{left}}}}}} + CP{U_{p{m_{{\rm{right}}}}}}}}{{ME{M_{p{m_{{\rm{left}}}}}} + ME{M_{p{m_{{\rm{right}}}}}}}} $

(3)

3.2 确定虚拟机资源需求分布跨度

在sortedList_vm={vm₁, vm₂, …, vm_n}中，取得首尾两个虚拟机需求的比例rate_vm1以及rate_vmn，据此确定sortedList_vm在数轴上的分布跨度为[rate_vm1, rate_vmn]。将[rate_vm1, rate_vmn]和pair_pm比例跨度[rate_pmleft, rate_pmright]进行对比，即可确定虚拟机资源需求分布跨度情况。必须使得pair_pm跨度情况为图 1(c)或图 1(d)所示，即pair_pm的比例跨度[rate_pmleft, rate_pmright]需要满足以下条件：rate_vmn>rate_center或rate_center>rate_vm1。

3.3 跨度情况3下的分界点获取

在跨度情况3下，先对虚拟机序列sortedList_vm两侧分别取分界点。分界点的意义在于：从某侧虚拟机起始到分界点为止的范围内，虚拟机需求之和的比例与对应侧物理机的资源配置比例最为匹配。以左侧为例：从sortedList_vm最左侧vm₁开始向右侧遍历。每遍历到新的虚拟机需求vm_k(k∈[1, n])，就求出已遍历的所有虚拟机需求的CPU之和$\sum\limits_{v{m_1}}^{v{m_k}} {_{{\rm{left}}}} CP{U_{v{m_k}}} $，以及内存之和$\sum\limits_{v{m_1}}^{v{m_k}} {_{{\rm{left}}}} ME{M_{v{m_k}}} $，并求出相应的比例:

$ Lsumrat{e_{v{m_k}}} = \sum\limits_{v{m_1}}^{v{m_k}} {_{{\rm{left}}}} CP{U_{v{m_k}}}/\sum\limits_{v{m_1}}^{v{m_k}} {_{{\rm{left}}}} ME{M_{v{m_k}}} $

(4)

在比例Lsumrate_vmk与左侧物理机资源配置比例rate_pmleft最为接近或完全相同时，遍历停止，并记录下当前vm_k的编号k，也就是左侧虚拟机需求的分界点POINT_left。

从右侧开始对sortedList_vm进行倒序遍历，以最右侧虚拟机作为起点vm₁，计算：

$ Rsumrat{e_{v{m_k}}} = \sum\limits_{v{m_1}}^{v{m_k}} {_{{\rm{right}}}} CP{U_{v{m_k}}}/\sum\limits_{v{m_1}}^{v{m_k}} {_{{\rm{right}}}} ME{M_{v{m_k}}} $

(5)

使用与左侧类似方法得到右侧分界点POINT_right。

3.4 跨度情况3下的划分点判断

当取得两侧分界点后，又面临两种可能：分界点相交或不相交。

在相交的情况下，两侧虚拟机资源需求不可能同时达到最接近比例，需要在重叠的分布序列部分overlapList(虚拟机需求编号为POINT_right≤p≤POINT_left)中相互妥协，取一个最合适的p点，使得两侧都接近最优的位置，称之为划分点Divide。在overlapList中，从sortedList_vm左侧起始遍历，求在q∈[1, p]范围内，虚拟机需求vm_q的CPU需求之和$\sum\limits_{q = 1}^p {_{{\rm{left}}}} CP{U_{v{m_q}}} $与MEM需求之和$\sum\limits_{q = 1}^p {_{{\rm{left}}}} ME{M_{v{m_q}}} $；分别求得它们与左侧物理机的CPU_pmleft及MEM_pmleft的商，并计算两商之差的绝对值；右侧使用类似方式计算。当两绝对值之和最小时，虚拟机需求与左侧物理机资源配置最为匹配，此时p的位置记为Divide。由此得出最优值OPT为：

$ \begin{array}{l} OPT = \min \left| {\frac{{\sum\limits_{q = 1}^p {_{{\rm{left}}}CP{U_{v{m_q}}}} }}{{CP{U_{p{m_{{\rm{left}}}}}}}}-\frac{{\sum\limits_{q = 1}^p {_{{\rm{left}}}ME{M_{v{m_q}}}} }}{{ME{M_{p{m_{{\rm{left}}}}}}}}} \right| + \\ \;\;\;\;\;\;\;\;\;\;\min \left| {\frac{{\sum\limits_{q = 1}^p {_{{\rm{right}}}CP{U_{v{m_q}}}} }}{{CP{U_{p{m_{{\rm{right}}}}}}}}-\frac{{\sum\limits_{q = 1}^p {_{{\rm{right}}}ME{M_{v{m_q}}}} }}{{ME{M_{p{m_{{\rm{right}}}}}}}}} \right| \end{array} $

(6)

在不相交的情况下，两侧都能达到各自最佳匹配位置。对于不相交的序列部分overlapList={vm_a, …, vm_b}，则要判断它与center的比例rate_center的关系，如图 2所示。

① 当rate_vmb≤rate_center，即overlapList位于center左侧时，则划分点Divide应定为右侧分界点POINT_right；

② 当rate_vma≥rate_center，即位于center右侧时，划分点Divide应定为左侧分界点POINT_left；

③ 当rate_vma≤rate_center≤rate_vmb时，则应以center的位置作为划分点Divide。

3.5 跨度情况4下的分界与划分

跨度情况4下，只需判断出对应侧虚拟机序列分界点即可完成划分处理。还是以左侧为例：获得的分界点POINT_left位于center左侧时，使用center作为Divide；当分界点POINT_left位于center右侧时，以此POINT_left作为Divide。

3.6 对划分后的序列进行放置

判定划分点Divide后，sortedList_vm被分为两个子集合。两个子集合的资源需求的大小对应了pair_pm中相应配置物理机数量对比。使用同构情况下的启发式算法对Divide左侧的虚拟机需求子集合在pm_left上进行放置，Divide右侧虚拟机需求子集合在pm_right上进行放置。至此得到具体的虚拟机需求放置结果，得出具体需要的两种活动物理机数量。

4 仿真实验及分析

对本文提出的RDDFPA性能进行评估实验，并与不经划分直接在同构环境下进行放置的常规方法进行对比。统一使用First Fit算法作为双方使用的启发式算法。将每10000个虚拟机需求作为一组数据，随机取20组进行实验。假设虚拟机的CPU需求以及MEM需求都在0~8内随机取值，虚拟机资源需求分布跨度中点在CPU和MEM资源比例为1:1的位置。通过调整资源配置构成不同异构物理机组，来模拟sortedList_vm和pair_pm的不同搭配情况。假设5组异构物理机组，左侧物理机称为A，右侧物理机称为B，并逐渐增大每一组资源配置比例之间的差异。5组配置如下：

组合一：

A:CPU_left=8 MIPS, MEM_left=10 GB, rate_left=4:5

B:CPU_right=10 MIPS, MEM_right=8 GB, rate_right=5:4

组合二：

A:CPU_left=8 MIPS，MEM_left=12 GB，rate_left=2:3

B:CPU_right=12 MIPS，MEM_right=8 GB，rate_right=3:2

组合三：

A:CPU_left=8 MIPS，MEM_left=16 GB，rate_left=1:2

B:CPU_right=16 MIPS，MEM_right=8 GB，rate_right=2:1

组合四：

A:CPU_left=8 MIPS，MEM_left=32 GB，rate_left=1:4

B:CPU_right=32 MIPS，MEM_right=8 GB，rate_right=4:1

组合五：

A:CPU_left=8 MIPS，MEM_left=40 GB，rate_left=1:5

B:CPU_right=40 MIPS，MEM_right=8 GB，rate_right=5:1

其中：CPU_left、MEM_left、rate_left分别代表左侧A的CPU资源、内存资源以及配置比例。右侧B相关符号意义与A近似。

使用本文提出的RDDFPA进行放置，所需要的两种异构物理机的台数之和，与直接在某一种物理机上进行放置所需要的同构物理机台数对比如图 3所示。

根据图 3中的数据，对随机数据集中20组数据的结果取平均值，得出不同异构物理机组合与单一配置物理机A、B相比节约的物理机台数与百分比，来展示实际算法应用的效果，如表 1所示。

从组合一到组合三，异构物理机组的CPU和内存资源配比从8:10和10:8一直扩大到8:16和16:8。随着异构物理机组差距增大，优化效果也从对比仅使用A时节约大概121台，比例约为2%，以及对比仅使用B时节约大概209台，比例约为3%，逐渐提升到对比左右侧均能节约大概900台，节约比例均约为17%。但是从组合四和组合五中也可以看出，在扩大两侧物理机资源配比差异时，优化效果并非随之线性扩大，而是逐渐趋于平稳，应将配置差异限定在一定范围内。

由以上对比实验可以看出，本文提出的RDDFPA，在异构物理机的资源配置具有一定差异时，相比单一配置物理机较为显著地减少了活动物理机数量，同时节约了能耗。

5 结语

针对异构云环境下的虚拟机放置问题，本文提出一种利用变化的虚拟机资源需求分布特征与异构物理机配置的比例关系，对虚拟机需求进行划分, 使得虚拟机子集合的变化反映为对应异构物理机数量变化，再对其放置的方法。实验结果表明，所提的算法能够在异构物理机配置差异较大且虚拟机资源分布和物理机资源配比相互较为契合的前提下，有效减少活动物理机的总数量，达到较好的优化效果。未来可以进一步研究在虚拟机分布的跨度和物理机配置偏离时如何避免算法退化的问题。