一种融合虚拟机选择的虚拟机放置方法

袁静珍，刘亚同

(1.韩山师范学院 物理与电子工程学院,广东 潮州 521041; 2.河南广播电视大学 信息工程学院， 郑州 450008)

0 引 言

近年来，大规模节能云数据中心的构造与使用成为政府和各大IT企业越来越重视的问题[1-3]。一个云数据中心(data center,DC)通常配置有大量的物理主机(physical machines,PMs)，虚拟化是云数据中心的关键技术，虚拟化通过虚拟机(virtual machines,VM)的形式将应用程序的任务与数据封装起来，通过虚拟机分配策略将虚拟机调度到具体的物理节点之上执行。为了节省云数据中心的能量消耗成本，云服务提供商还采用虚拟机迁移(VM migration,VMM)策略来完成虚拟机在各个物理服务器上的选择与放置，最终目标是节省云数据中心能量消耗，提高服务质量(quality of service,QoS)，节省物理空间和提高可靠性等。

目前，以Anton Beloglazov博士团队开发的Cloudsim项目在云数据中心的节能研究方面处于世界领先地位[4-5],Cloudsim项目中把虚拟机迁移过程划分为物理主机状态检测,虚拟机选择和虚拟机放置3个步骤,最终完成整个虚拟机迁移。物理主机状态检测可以通过观察它的资源使用状态来判断，如果CPU的使用效率超过90%或者低于10%都可以认为是超负载或者低负载。在这个时候，该物理节点的虚拟机将被选择出来，同时放置到另外一个物理节点之上。虚拟机选择的含义是通过判断物理主机的运行状态(超负载over-utilized或低负载under-utilized)，然后从中选择出合适的候选迁移虚拟机。虚拟机放置的含义是将虚拟机选择算法中选择出来的虚拟机按照一定的算法重新放置到云数据中心其他最合适的物理节点。

从这个过程可以看出，虚拟机选择和虚拟机放置应该属于2个不同的步骤，这2个过程都可以通过算法进行优化。前者可以通过虚拟机尺寸、资源利用效率等来进行优化；后者属于一类经典装箱问题(classical packing problem,CPP)，即把大量的候选虚拟机VM放置到大量的物理节点之中,还有些文献把它称为稳定匹配或者医院病床分配问题[6]。

目前研究虚拟机迁移策略的文献不足之处往往都在研究虚拟机选择算法本身和虚拟机放置算法本身等方面,很少研究两者之间的密切关系。事实上，虚拟机选择可以影响到虚拟机放置，至少在私有云中虚拟机选择和虚拟机放置都可以由一个机构去控制。本文的研究重点在虚拟机放置阶段，提出了融合虚拟机选择和放置的虚拟机迁移策略(interrelation virtual machine migration,Inter_VMM)。在物理主机状态检测和虚拟机选择阶段,Inter_VMM采用了Cloudsim项目中的基本思路与方法，在虚拟机放置阶段提出了自己的融合虚拟机选择与放置2个过程之间的密切联系的策略，与医院病床分配类似,Inter_VMM根据匹配双方每个个体的优先级来确定,虚拟机和物理主机都是稳定可靠匹配的，该机制可以保证活动主机的物理资源有比较满意的利用效率。

采用真实的工作负载数据，Inter_VMM虚拟机迁移策略通过Cloudsim来实现和仿真,仿真结果表明，Inter_VMM策略比Cloudsim中普通的虚拟机迁移策略可以更好地节省云数据中心的能量消耗,减少了服务等级协议(service level agreement,SLA )违规率,保证了服务质量。

1 相关工作

1.1 虚拟机选择相关工作

针对云数据中心的虚拟机选择问题，国内外已经有相当多的研究，大部分研究焦点关注在物理主机的计算能力[7-9]，其他的研究也有关注硬件资源，比如内存大小[10-11]等，它们的研究目标是在性能与虚拟机代价之间追求平衡。

也有文献把虚拟机选择算法放在虚拟机最小代价计算方面。大部分文献认为虚拟机代价与虚拟机使用时间成比例[12-15]，还有研究认为该代价应该由消费资源的使用情况或者是长期处于租赁状态下的物理资源使用来计算[16]。

在Cloudsim项目中采用的是最小迁移时间(minimum migrationtime，MMT)虚拟机选择策略,即选择一个在最短时间内能够完成迁移的虚拟机作为候选迁移对象,文献[4]表明该策略要明显优于其他的虚拟机选择策略。本文的Inter_VMM虚拟机迁移策略在这个阶段借鉴了MMT方法。

1.2 虚拟机放置相关工作

在虚拟机放置方面，目前也有很多研究。一些研究关注于物理主机的计算能力和虚拟机的计算负载方面[17-19]，另外的一些研究把放置因素聚焦在物理资源的内存大小、磁盘空间大小、网络带宽大小、I/O通讯能力等方面[20-23]。

虚拟机放置研究中一个最重要的因素是活动物理主机的数量(number of turn-on PMs)，因为它可以最大程度地决定能量消耗的大小[17]；还有一些研究考虑到了物理主机的动态能量消耗的负载相关性(number of PMs overloads)[24]。

在虚拟机放置中，如果资源比较单一，只把目标放到物理主机的数量降低上，该类问题可以划归为经典的装箱问题，它没有最优解，只有近似最优，包括Cloudsim项目等都使用经典装箱问题来完成虚拟机的放置问题。

1.3 虚拟机选择与虚拟机放置的结合

也有部分文献没有把虚拟机选择和虚拟机放置划分开来，而是发掘它们之间的相关联系，例如文献[25]根据任务的特点，选择最优的虚拟机尺寸来分配虚拟机，它的目的是通过最小资源的使用来降低能量消耗,不考虑它的负载，每个虚拟机都有一个固定的尺寸，虚拟机尺寸之间的差异及它的负载的总体尺寸都有规定。

文献[26]把软件即服务云平台中应用程序的组件映射给虚拟机，它关注的也是虚拟机尺寸，虚拟机的共享能力，该策略也提出了虚拟机放置算法的建议，哪些虚拟机放置可以静态处理，哪些虚拟机放置需要动态处理，但是实际上这些虚拟机到物理主机的放置并未完成，而是通过一个外部算法来操作。与文献[26]比较起来，本文主要把重点放在虚拟机选择过程和虚拟机放置过程的稳定匹配方面，通过设计稳定匹配算法完成虚拟机和物理主机的高效率资源利用。

2 虚拟机迁移策略的工作背景

2.1 虚拟机迁移的工作背景

Inter_VMM把虚拟机的迁移过程分为物理主机负载检测过程、虚拟机选择过程与虚拟机放置过程，最终完成整个虚拟机迁移过程,具体包括下面4个步骤。

步骤1周期性检测云数据中心物理主机的超负载或者低负载状态(over-utilized或under-utilized)；

步骤2判断其是否进行虚拟机迁移操作；

步骤3基于可靠匹配完成虚拟机的选择;

步骤4将候选虚拟机进行虚拟机放置操作。

Cloudsim项目中已经有的物理主机状态检测方法,根据物理资源利用效率的使用阈值情况，常见的包括下面5种。

1)局部归约检测方法(local regression，LR)；

2)鲁棒局部归约检测方法(local regression robust， LRR)；

3)绝对中位差检测方法(median absolute deviation，MAD)；

4)静态的资源使用效率阈值检测法(static threshold ，THR)；

5)4分位数区间检测方法(inter quartile range，IQR)。

步骤3中，CloudSim项目中已经有的虚拟机选择算法包括下面几种。

1)最大关联选择方法(maximum correlation，MC):即选择同一个物理主机上与CPU使用效率有最高关联度的虚拟机作为对象；

2)最小迁移时间选择方法(minimum migration time，MMT):即迁移一个在最短时间内能够完成的虚拟机作为选择对象；

3)最小资源使用效率选择办法(minimum utilization，MU):即对一个具有最小使用效率的虚拟机进行迁移；

4)随机选择策略(random selection，RS):即在物理主机上随机选择一个虚拟机进行迁移。

本文的Inter_VMM虚拟机迁移策略与Cloudsim项目中不同的是，在后续的虚拟机放置过程中，融合虚拟机选择和虚拟机放置的相结合方法,着重考虑虚拟机和物理主机匹配双方每个个体的优先级而不是经典装箱方法。

2.2 虚拟机迁移的相关术语

2.2.1 物理主机使用效率

物理主机的使用效率体现了云数据中心资源使用状态，所有物理主机的平均使用效率可以表示为

(1)

(1)式中：ui是当前的物理主机i的CPU使用效率；m是物理主机的数目。

2.2.2 能源消耗模型

为了计算云数据中心的能源消耗，假设服务器是空闲的，它的能源消耗的百分比是k,pfull表示服务器在完全满负载工作时的能源消耗，ui是当前的物理主机i的CPU使用效率,物理主要数目为m,则整个云服务器端的能源消耗表示为

(2)

3 融合虚拟机选择的虚拟机放置算法描述

Inter_VMM虚拟机迁移策略主要工作在平台即服务(infrastructure as a service,IaaS)的条件下，假设一个云数据中心有N个异构的物理服务器节点，在一个给定的时间内，有多个客户端提交应用程序到该平台，该应用程序被虚拟化技术封装成M个虚拟机到该平台,接下来该M个虚拟机将被分配到具体的物理服务器上执行。按照前面思路，应该包括物理主机状态检测,虚拟机选择,虚拟机放置等过程。

Inter_VMM的策略在前2个阶段分别采用了鲁棒局部归约放检测方法LRR完成物理主机状态检测,采用了最小迁移时间选择方法MMT来完成虚拟机选择,之所有选择这2个方法是因为相关文献表明它们在构造节能的云数据中心方面具有良好、优异的性能。在第3阶段,即虚拟机放置阶段，Inter_VMM采用了一种兼顾虚拟机和物理主机双方资源优先级冲突的方法,表1描述了相关的术语,算法步骤具体描述如下。

表1 Inter_VMM虚拟机迁移策略的相关符号描述

步骤1给每个候选迁移列表中虚拟机确定最高优先级的物理主机。

a)假设有α≤M个虚拟机要放置到β≤N个物理主机之上,定义虚拟机的集合为V,V={V1,V2,…,Vα},定义可用的物理主机的集合为P,P={P1,P2,…,Pβ}。

b)对于集合V中的每一个虚拟机Vi,计算物理主机集合P中的Uij,公式为

(3)

c)计算理想目标利用效率Uth和评测利用效率Uij之间的差值,如果Uth≥Uij,该差异值计算表达式为

ΔUij=Uth-Uij

(4)

否则，表明这个物理主机不适合作为被放置的物理节点。

d)物理主机Pk(i)是一个容易被虚拟机Vi最优先放置的物理节点，则有

k(i)=argminΔUij,1≤j≤β

(5)

根据它们的优先级,多个虚拟机也可以选择相同的物理主机,这里定义Vlist_j为根据它们的优先级完成排序的最容易放置到物理主机Pj的候选放置列表。

步骤2匹配虚拟机到物理主机.

a)对于每个P集合中的物理主机，匹配Pj到Vlist_j,这样都可以获得一个最小的ΔUij。

b)在每次匹配过程完成之后，丢弃Vlist_j列表,并且将Vi从V集合中删除。

步骤3如果V不等于空集,反复执行步骤1和步骤2,否则终止整个放置步骤的运行。

融合虚拟机选择的虚拟机放置算法的步骤如下。

算法1:融合虚拟机选择过程的虚拟机放置算法

输入:物理主机列表hostList,虚拟机选择阶段产生的候选虚拟机列表VMsToMigrateList

输出:已经完成好的虚拟机放置列表Placement of VMs

1 for vm in VmsToMigrateList do

2 minInterrelationDiff1:=MAX //

3 preferredhostList :=NULL // 优先级物理主机列表为空

4 for each host in hostList do

5 if host has enough resources for vm then

6 InterrelationDiff1 :=estimated InterrelationDiff1 (host,vm)

7 if (InterrelationDiff1 < minInterrelationDiff1) then//如果ΔUij最小.

8 preferredHost := host//空闲物理主机加入列表

9 minInterrelationDiff1 :=InterrelationDiff1

10 end if

11 end if

12 end for

13 if preferredHostList !=NULL then

14 preferredHostList.add(vm,preferredHost) //生成最优先级的物理主机列表

15 end if

16 end for

17 for preferredHost in preferredHostList do

18 minInterrelationDiff2:=MAX

19 finalSelectedVM:=NULL

20 for VM inVMsSelectpreferredHost do

21 InterrelationDiff2:=estimateInterrelationDiff2(host,vm)//计算物理主机集合P中的Uij,从而使ΔUij最小

22 If InterrelationDiff2

23 minInterrelatinDiff2:=InterrelationDiff2

24 finalSelectdVM:=VM//虚拟机匹配到最优先级的物理主机列表preferredHostList

25 end if

26 end for

27 end for

28 if finalSelectedVM !=NULL then

29 placement.add(finalSelectedVM,preferredHost)

30 end if

31 return Placement

上述代码中1—16行的功能是从候选迁移物理主机列表VmsToMigrateList中产生最优先级的物理主机列表preferredHostList,在这个步骤中，每次都获得一个最小的minInterrelationDiff1.estimatedInterrelationDiff1函数，功能是计算物理主机集合P中的Uij,从而使ΔUij最小。代码17—31行的功能是将虚拟机匹配到最优先级的物理主机列表preferredHostList,该过程每次也可以获得一个最小的ΔUij。

该算法表明物理资源的利用效率与理想利用效率的差值最小，物理主机的利用效率比较高。在每次完成匹配之后，被匹配的虚拟机将从候选虚拟机列表中删除，该算法一直执行直到候选虚拟机列表中的所有虚拟机都完成匹配为止,最后返回一个虚拟机迁移地图。

4 仿真实验与性能分析

4.1 仿真环境

为了对本文提出的融合虚拟机选择的虚拟机放置Inter_VMM模型进行实验分析，采用了Cloudsim模拟器。Cloudsim的最新版本中提供了很多已有的虚拟机迁移策略的能量消耗模型的实验数据，方便科研工作者对云数据中心的能量相关的虚拟机迁移算法的比较与研究[5]。

根据虚拟机迁移3个阶段的步骤，Cloudsim中比较好的办法是用LRR策略为物理主机状态检测,结合MMT策略完成虚拟机选择,再结合经典装箱方法(classical packing problem,CPP)完成虚拟机放置,本文称之为LRR_MMT_CPP策略,它的实现结果见文献[4-5]。

LRR_MMT_CPP策略为与本文Inter_VMM策略作为比较的对象。被模拟的云数据中心主要由2类物理服务器组成，物理服务器总数为800个，物理服务器配置如表2。

表2 云数据中心物理服务器配置

模拟云客户端的应用程序访问，使用10 000个具有正确CPU与内存请求的任务数据, 运行的可以是一个Web应用程序或者其他一个具有不同类型工作负载的应用程序,一共产生大约4类虚拟机,如表3。

表3 云数据中心4类虚拟机需求情况

能量模型如2.2节所描述的能量消耗模型,这也是Cloudsim中常用的能量消耗模型。虚拟机迁移周期设置为5 min，这种设置就意味着虚拟机的负载探测和虚拟机的迁移5 min运行一次，一共运行24 h,每次统计一天内的能量消耗,在一周内重复运行5次。

4.2 评测标准

按照Cloudsim项目研究思路，虚拟机迁移策略评价的主要指标有4个:①云数据中心的总体能量消耗;②虚拟机迁移次数;③平均的SLA违规分析;④能量与SLA违规的联合指标。这4个指标可以体现与能量消耗相关的虚拟机迁移策略的性能好坏。前面2个指标比较好理解，现在主要描述下指标③和指标④。

4.2.1 SLA违规比率

在云数据中心中，SLA违规值表明在客户有服务请求的时候，CPU并没有分配资源的情况。本文参考了文献[4]中的方法，采用了2个方法来评价SLA违规。单活动主机SLA违规时间(SLA violation time per active host ,SLATAH), 虚拟机迁移后降低的性能(performance degradation due to migrations , PDM)。 所以，最终SLA违规的具体值可以表示为

SLAV=SLATAH*PDM

(6)

(6)式中：SLATAH是活动主机的CPU具有100%的使用效率所占的比例；PDM是整个系统因为虚拟机迁移后降低的性能。

4.2.2 SLA违规与能量消耗联合指标

能量消耗和SLA违规这2个指标往往是互相冲突的，如果SLA违规比率过高,表明云数据中心提供服务出现异常，这样企业将会失去商业利润。如果使用过多的IT物理资源来保证QoS,这样能量消耗就会增加,间接提高了企业的成本,所以本文主要是保证能量消耗和QoS之间的平衡。参考Cloudsim中的ESV(energy and SLA violations)方法来评价整个云数据中心的性能, ESV的计算公式为

ESV=E*SLAV

(7)

(7)式中：E是云数据中心的整体能量消耗，SLAV是(6)式中的SLA违规情况,ESV体现了能量与SLA违规的联合指标.

4.3 仿真结果与性能分析

本文在Cloudsim上执行融合虚拟机选择和虚拟机放置的虚拟机迁移策略Inter_VMM的仿真。

资源的使用效率阈值调整为0.8,与LRR_MMT_CPP策略进行比较。

本文的方法与LRR_MMT_CPP策略方法不同的地方是最后在虚拟机放置阶段采用了新的虚拟机与物理主机匹配算法。在Inter_VMM的方法中，融合了虚拟机选择的结果，体现了虚拟机选择与虚拟机放置的结合，使虚拟机与物理主机能够达到稳定匹配。

本文的实验结果在总体能量消耗，虚拟机迁移次数，SLA违规比率,ESV等指标了进行了计算,结果如图1—图4,包括从周一到周五每天的实验数据,体现了普遍性。

从图1可以看出，Inter_VMM策略的总体能量消耗低于LRR_MMT_CPP策略,周一到周五平均至少节省30%的总能量消耗,分析原因是Inter_VMM以提高物理主机资源利用效率为最终目标,如果提高了利用效率,将直接降低资源能量消耗，而不是像LRR_MMT_CPP策略中采用经典装箱方法和递减经典装箱方法中以降低活动物理主机数量为目标。

图1 云数据中心总体能量消耗性能比较Fig.1 Total energy consumption performance results of cloud data center

图2显示云数据中心的SLA违规比率情况。Inter_VMM策略比LRR_MMT_CPP策略的SLA违规比率要低,SLA违规比率都在0.002%～0.007%，意味着10000次的云客户端访问,只有大约0.2～0.7次物理资源无法分配，Inter_VMM和LRR_MMT_CPP都比较优秀,但是Inter_VMM虚拟机迁移过程的服务质量QoS比LRR_MMT_CPP要好,分析原因是2个策略都采用了MMT方法完成候选物理主机列表,迁移时间短,这样可靠性比较好。

图2 云数据中心SLA违规比率性能比较Fig.2 SLA violation rate performance results of cloud data center

由于每次虚拟机迁移都会影响到系统能量消耗和SLA违规的比率,所以虚拟机迁移的次数也非常重要。图3显示了融合虚拟机选择和虚拟机放置的Inter_VMM策略的实验结果,Inter_VMM策略虚拟机迁移次数明显要少,正是因为迁移次数少，才会直接导致云数据中心的可靠性与节能性能进一步提高。

在SLA违规和能量消耗联合性能指标之上，ESV的值越小，云数据中心的总体性能就越优秀。从图4可以看出，Inter_VMM策略比LRR_MMT_CPP策略要低,这是因为在采用融合虚拟机选择和虚拟机放置的虚拟机迁移策略后，所有物理服务器的CPU使用效率可以控制在很接近一个理想的使用效率范围，这样就增加了虚拟机资源的利用效率,Inter_VMM策略可以将那些空闲的物理服务器关闭,最终节省了云数据中心能量消耗。

图3 云数据中心虚拟机迁移次数比较Fig.3 Virtual machine migration numbers results of cloud data center

图4 云数据中心综合ESV性能比较Fig.4 Total ESV performance results of cloud data center

5 结 论

本文提出了云数据中心融合虚拟机选择的虚拟机放置的策略Inter_VMM。该策略主要工作在虚拟机放置阶段，将虚拟机和物理主机双方的稳定匹配作为目标,将云数据中心的物理资源的利用效率控制在一个理想的阈值范围。实验表明，本文方法比Cloudsim中已经有的虚拟机迁移策略在总体能量消耗,虚拟机迁移次数，SLA违规比率，ESV等指标上有更加优秀的性能,本文方法对其他企业构造大规模节能的云数据中心具有重要参考价值。