基于负载不确定性的虚拟机整合方法

李双俐，李志华，2*，喻新荣，闫成雨

(1.江南大学物联网工程学院，江苏无锡214122; 2.物联网应用技术教育部工程研究中心(江南大学)，江苏无锡214122)(*通信作者电子邮箱lily_lshl@163.com)

0 引言

近年来伴随着企业计算的爆炸性增长，用户对云计算的需求也不断上升。传统的资源分配方式使得数据中心常处于高负载、高成本的运营状况［1］，因此，许多云服务提供商开始采用虚拟化技术为用户分配资源。虚拟化技术使得数据中心能够快速地进行资源分配，增加了数据中心的灵活性。然而，数据中心的资源管理也因此变得更加复杂，如何制定虚拟机的调度策略变成了合理分配数据中心资源的关键问题之一。

高效的虚拟机整合策略能合理地分配资源、降低数据中心能耗、提高服务质量(Quality of Service，QoS)。已有的一些虚拟机整合方法［2－4］为了提高资源利用率和降低数据中心能耗，通过将低负载物理主机上的虚拟机整合到其他物理主机并关闭这些空闲物理主机的方式达到降低能耗的目的;但是，过度的虚拟机整合在应对数据中心负载突然增加时，需要额外消耗一定的时间开启休眠物理主机［2］，此时，并不能确保服务提供商与用户签订的服务等级协议(Service Level Agreement，SLA)，从而进一步影响数据中心的服务质量。

由于虚拟机整合是一个系统性的问题，文献［4］将虚拟机整合问题分成物理主机过载检测、虚拟机选择、虚拟机放置和物理主机收缩四个阶段。虚拟机整合时，首先通过物理主机过载检测得到过载物理主机集合;然后，针对过载物理主机进行虚拟机选择，并将这些虚拟机迁出以缓解物理主机的过载风险，迁出的虚拟机需要重新放置在合适的目标物理主机上，继续提供计算服务;最后，对数据中心中的低负载物理主机进行关闭，从而达到降低数据中心能耗的目的。

虚拟机整合问题目前已得到了广泛研究，各种算法相继被提出［4－9］。文献［4］在物理主机过载检测方面给出了中位数绝对偏差(Median Absolute Deviation，MAD)算法、四分位距(InterQuartile Range，IQR)算法、局部回归(Local Regression，LR)算法;在物理主机选择方面给出了最小迁移时间(Minimum Migration Time，MMT)算法、最大相关度(Maximum Correlation，MC)算法和随机选择(Random Selection，RS)算法。近年来，一些以降低能耗为目标的算法［5－6］被提出。文献［5］通过对 CPU 能耗模型的分析，建立了一个能耗最优的混合整数规划模型，并据此提出了一种虚拟机放置方法。文献［6］介绍了一种基于时间序列预测和启发式装箱的动态虚拟机整合算法，通过启发式装箱算法最大限度地减少所需物理主机数量，降低了数据中心能耗。然而，上述算法对服务质量及资源利用率的关注不足。文献［7］根据负载变化情况提出了一种弹性资源预测方法，利用轻量级信号处理和统计学算法实现资源请求的动态预测，但未给出具体的整合策略。文献［8］提出了一种虚拟机负载负相关的虚拟机选择算法。该算法首先将虚拟机根据负载变化负相关的原则进行配对，然后将配对的两台虚拟机放置在同一台物理主机上。该算法有利于稳定物理主机的工作负载，但缺乏对虚拟机间关联性的考虑。文献［9］在文献［8］的基础上增加了虚拟机配对迭代次数，但同样利用两台虚拟机配对，忽略了虚拟机整体间的关联。文献［7－9］的实验结果表明基于负载的虚拟机整合算法给数据中心带来了积极的影响。

针对目前虚拟机整合存在的缺乏对负载稳定性分析的问题，本文通过分析虚拟机资源请求与物理主机工作负载之间的关系，确定物理主机剩余资源对虚拟机的满足程度，拟合得到虚拟机与物理主机之间的匹配度。利用匹配度进行虚拟机整合能够稳定物理主机负载，达到提高服务质量、降低能耗的双重目的。

1 工作负载与虚拟机迁移

1.1 负载分析

通常数据中心为了降低能源消耗，在资源分配时希望能够充分利用每台物理主机的资源，从而避免低利用率造成的资源浪费。然而，虚拟机对资源的请求过程是随机的，对于处于高负载状态的物理主机，一旦虚拟机请求的资源超过了物理主机的可用资源总和就会发生过载，从而违背云服务提供者与用户签订的服务水平协议，造成服务质量下降。为了提升服务质量，我们倾向于为物理主机预留充足的资源以避免过载，但过多的预留资源又会造成资源浪费，增加能源消耗。本文利用物理主机工作负载和虚拟机资源请求的变化特征进行虚拟机整合，以期达到提高云服务质量的同时能够充分利用物理主机资源的目的。

在实际情况中物理主机负载呈多峰分布，图1(a)记录了数据中心其中一台物理主机一天内的CPU负载变化情况;为了更清楚地看到其负载变化，图1(b)选取该主机在第215～234次整合周期期间的CPU负载变化。由图1可知，物理主机的负载变化具有随机性。

对于处在活动状态的物理主机，如果运行在其上的虚拟机在某一时段资源请求较高，那么此时物理主机的负载将出现局部峰值;而如果运行在其上的虚拟机在某一时段资源请求较低，那么物理主机的负载将出现局部谷值。如图1(b)所示，为了避免主机过载情况的发生，物理主机应为波峰时段预留足够的资源，然而，这些预留资源在波谷时段的闲置又造成了资源的浪费，这显然是矛盾的。因此，稳定物理主机的负载，有效避免物理主机负载出现较大的波动，从而减少资源的预留量，这不仅能够提高物理主机资源利用率，同时也降低了由于物理主机负载不确定性造成的主机过载风险。

图1 单个物理主机CPU负载变化Fig.1 Workload changing of single physical host CPU

1.2 虚拟机迁移

根据工作负载的特性，在虚拟机迁移过程中如果能够保持物理主机工作负载的稳定，避免物理主机工作负载出现明显的波动，那么就能减小物理主机的过载风险，并且增加物理主机的资源利用率。

为了稳定物理主机负载，在虚拟机从过载物理主机上迁出时，应该选择与物理主机匹配度低的虚拟机，即被选择的虚拟机的资源请求与物理主机负载在同一时段出现峰值。根据此规则对迁移虚拟机进行选择，选择的虚拟机迁出后，能降低物理主机在负载峰值时的过载风险。在放置虚拟机到目标物理主机上时，虚拟机与物理主机的负载应该呈现高匹配度，即当物理主机负载处于高峰值时虚拟机对资源的请求量应处于低谷，避免由于虚拟机的放置使物理主机负载出现突然变化。保证放置的虚拟机在各个时刻都能充分地利用物理主机剩余预留资源，并且能够稳定物理主机负载，避免由于负载出现较大波动而导致物理主机发生新的过载。

本文所提出的算法利用虚拟机资源请求拟合物理主机工作负载，并通过拟合得到的虚拟机与物理主机的负载匹配度进行虚拟机迁移。在保证物理主机资源充分利用的同时降低其过载概率，提高服务质量。

2 基于负载不确定性的虚拟机整合方法

2.1 虚拟机与物理主机匹配度估算

为了清楚地描述拟合过程，首先对数据中心的各项资源进行抽象。vmlist代表虚拟机集合。向量corhj=［…，，…，］T代表各虚拟机与物理主机hj的负载匹配度。向量b= ［b1，b2，…，bi，…，bt］T代表物理主机hj的CPU剩余可用资源的历史记录，其中，bi代表hj在i时刻的CPU剩余可用资源。A= ［vm1，vm2，…，vmi，…，vmm］代表虚拟机请求资源的历史记录矩阵，其中列向量vmi代表虚拟机vmi对CPU资源请求的历史记录。

为了量化物理主机负载的情况，定义函数 g(vmlist，hj，corhj)，如式(1)所示:

式(1)表示，若将vmlist中的虚拟机按照匹配度向量corhj放置在物理主机hj上后，物理主机负载均衡的程度。物理主机负载越平稳则函数g的值越小。当函数g取得最小值时，可以得到虚拟机在物理主机hj上的一组最优匹配向量corhj，如式(2)所示:

s.t.0 corhj1

根据式(1)及以上分析可知，求解式(2)可得到全部虚拟机对应物理主机的匹配度corhj。将虚拟机按照匹配度降序排列的方式依次放置在物理主机hj上，直至剩余虚拟机都不能再放入hj为止。此时，可以得到使物理主机负载趋于平稳的虚拟机整合方案。

图2 sigmoid函数Fig.2 sigmoid function

sigmoid函数的图形是“S”形的，它是严格递增的函数，其中a是sigmoid函数的倾斜参数［10］。修改参数a就可以改变sigmoid函数的倾斜程度，变化趋势如图2所示。根据sigmoid函数的特性，本文中令= φ(vi)，则corhj可以表示为向量形式:corhj=［φ(v1)，φ(v2)，…，φ(vi)，…，φ(vm)］T。通过这样的变换，式(2)转化为式(4):

显然，式(4)是一个无约束优化问题。在此采用梯度下降法求解无约束优化问题，利用负梯度作为搜索方向［11］，迭代公式如式(5)所示:

其中:s－(k)代表搜索的梯度负方向;ρk代表沿梯度方向上的搜索步长。对式(4)求导数可以得到函数g在v上的梯度公式。

根据导数与梯度的关系［11］，可求得函数g在v上的梯度，代表梯度向量s－(k)的一个分量，如式(6)所示:

至此，梯度下降法可求解式(4)所示的无约束优化问题。利用梯度下降算法先求出向量v的值，然后根据式(3)计算可以得到虚拟机与物理主机负载匹配度向量corhj。利用梯度下降法求匹配度流程如图3所示。

图3 利用梯度下降法求匹配度流程Fig.3 Flow chart of gradient descent method for computing matching degree

2.2 物理主机过载检测

随着虚拟机资源请求的变化，物理主机工作负载也随之改变。对于负载较高的物理主机，若虚拟机请求资源增加，那么将有可能出现虚拟机请求资源超过物理主机可用资源的情况，此时物理主机发生过载。对于每一台物理主机，可以根据其负载情况计算该物理主机的过载概率，通过过载概率为物理主机选择合适的过载阈值用于新一轮的虚拟机整合，并通过整合来动态调整物理主机负载，提高服务质量。过载概率与过载阈值的计算如式(7)、(8)所示。

本文将物理主机CPU利用率超过65%的概率作为物理主机的过载概率，如式(7)所示。当物理主机CPU利用率超过65%时，认为主机存在过载风险。在一个检测周期内物理主机CPU利用率超过65%的次数越多则该物理主机发生过载的风险越大。式(8)通过过载概率计算过载阈值。参数s控制过载概率对过载阈值的影响，s越大则过载概率对过载阈值的影响越大;s越小则过载概率对过载阈值的影响越小。当物理主机过载概率较大时，降低其过载阈值从而降低物理主机的过载风险;当物理主机过载概率较小时，则该主机过载风险较小，将其过载阈值调高，以保证物理主机资源的充分利用。

根据以上分析，本文提出基于工作负载不确定性的过载概率估计(Workload Uncertainty-based Overload Probability Estimation，WUOPE)算法。在进行过载检测时，当物理主机的CPU利用率ui大于过载阈值Tiu时，则判断当前物理主机hi过载。WUOPE算法伪代码如下。

算法1 基于工作负载不确定性的过载概率估计(WUOPE)算法。

2.3 虚拟机选择

当虚拟机请求资源超过物理主机可用资源时，物理主机同样会出现过载风险。为了保证云数据中心的服务质量应该将一部分虚拟机迁出过载主机以缓解过载风险。

迁出虚拟机的选择应遵循以下两个原则:1)迁移后应保持物理主机负载稳定，避免由于迁移导致的物理主机负载不稳定;2)最小化迁移时间，减少由于迁移带来服务质量下降的影响。通过利用虚拟机请求资源拟合物理主机剩余可用资源可以得到虚拟机与物理主机的负载匹配度。为了稳定物理主机负载可以优先迁移负载匹配度小的虚拟机，同时为了最小化迁移时间可以优先迁移占用内存小的虚拟机［12］。综合考虑以上两点，本文定义虚拟机在物理主机上迁移的优先级priority_s，计算式如式(9)所示:

为了保持物理主机负载稳定，本文提出了一种基于负载不确定性的最小迁移时间选择 (Workload Uncertainty-based Minimum Migration Time Selection，WUMMT)算法。利用式(9)计算运行在过载物理主机上的虚拟机的迁移优先级，将虚拟机按照迁移优先级降序排列，依次将优先级高的虚拟机迁移出物理主机，直至物理主机的过载风险消除。WUMMT算法伪代码如下。

算法2 基于负载不确定性的最小迁移时间选择(WUMMT)算法。

2.4 虚拟机放置

对于因为物理主机过载和收缩而迁移的虚拟机必须为其寻找合适的目标物理主机进行放置。在虚拟机放置时首先要保证待放置物理主机有充足的资源，然后是确保放置虚拟机后目标主机的工作负载稳定性。

在选择目标物理主机时，应该优先选择具有相对较高资源使用率的物理主机作为目标主机，这样更能充分利用物理主机的资源从而提高数据中心的资源利用率。通过式(10)计算出迁移虚拟机在目标主机上的放置优先级:

结合虚拟机与物理主机负载匹配度和虚拟机资源请求情况，本文提出一种基于负载不确定性的FFD的放置(Workload Uncertainty-based FFD allocation，WUFFD)算法。首先在正常运行的主机中挑选资源使用率较高的主机作为目标物理主机;然后计算虚拟机的放置优先级，把高优先级的虚拟机放置在目标主机上，以此类推，直至迁移虚拟机放置完成或目标主机不能再放入任何虚拟机为止。WUFFD算法伪代码如下。

算法3 基于负载不确定性的优先适应下降的放置(WUFFD)算法。

2.5 虚拟机整合

虚拟机整合包括主机过载检测、虚拟机选择、虚拟机放置和物理主机收缩四个阶段。本文提出一种基于负载不确定性的虚拟机整合(Workload Uncertainty-based Virtual Machine Consolidation，WU-VMC)方法。首先，WU-VMC方法利用WUOPE方法估算物理主机的过载阈值，判断物理主机是否存在过载风险;然后，使用WUMMT方法将存在过载风险的物理主机上的一部分虚拟机迁移出物理主机，从而降低物理主机的过载风险;对于迁移出的虚拟机利用WUFFD方法选择出合适的目标主机进行放置;最后，利用物理主机收缩方法降低能耗，将处于低使用率状态的物理主机上的虚拟机全部迁出，并用WUFFD方法为其选择合适的目标主机进行放置，利用循环检测的方式每次选择资源使用率最低或为“0”的物理主机进行收缩，关闭或休眠这些物理主机。WU-VMC算法伪代码如下。

算法4 基于负载不确定性的虚拟机整合(WU-VMC)算法。

3 仿真实验与分析

3.1 实验环境

实验采用 Cloudsim［14］作为仿真平台。Cloudsim是澳大利亚墨尔本大学的云计算与分布式系统实验室推出的开源云计算仿真软件，可以支持大规模数据中心、云联邦、用户自定义资源管理策略等方面的仿真建模［15］。

本文通过Cloudsim平台模拟一个拥有800台物理主机的数据中心。这些主机根据资源配置的不同分为两类:一类是HP ProLiant ML110 G4(Intel Xeon 3040 2 Cores 1 860 MHz，4 GB);另一类是 HP ProLiant ML110 G5(Intel Xeon 3075 2 Cores 2260 MHz，4 GB)。同时，模拟四种不同类型的虚拟机:超强 CPU配置的虚拟机 High-CPU Medium Instance(2500 MIPS，0.85 GB)、超大型虚拟机 Extra Large Instance(2000 MIPS，3.75 GB)、小 型 虚 拟 机 Small Instance(1000 MIPS，1.7 GB)和微型虚拟机 Micro Instance(500 MIPS，613 MB)［16］。实验所采用的工作数据来自文献［12］，即PlantLab平台在真实环境下记录的为期10天的CPU负载数据。表1记录了10天中虚拟机请求的情况。

3.2 评价指标

为了评价方法性能，本文使用文献［12］提出的六种性能评价指标:服务等级协议违背率(Service Level Agreement Violations，SLAV)、能源消耗(Energy Consumption，EC)、虚拟机迁移次数(Virtual Machine Migrations，VMM)、服务质量和能耗综合评价指标(Energy and SLA Violation，ESV)、由于迁移导致的服务下降(Performance Degradation due to Migration，PDM)、运行时SLA违背时间(SLA violation Time per Active Host，SLATAH)。

表1 PlantLab虚拟机请求情况Tab.1 Request status of virtual machine PlantLab

SLATAH指由于活动物理主机在运行时CPU过载导致的违反服务等级协议，定义式如式(11)所示:

PDM代表由于虚拟机迁移导致的服务质量下降，定义式如式(12)所示:

SLAV是用来评价单日内数据中心服务质量的综合指标，定义式如式(13)所示:

SLAV的值受当日数据中心SLATAH和PDM的综合影响。当日数据中心的SLATAH与PDM值越低，则综合值SLAV越小，数据中心服务质量越高。

EC代表数据中心一天的能源消耗。节约能源不仅能降低数据中心的运维成本，更是建设绿色数据中心的重要途径。同时，低能耗也意味着资源的高利用率。综合数据中心对低能耗和高服务质量的要求，定义服务质量和能耗综合评价指标ESV，表达式如公式(14)所示:

ESV的值越低意味着当日数据中心的能源消耗少、服务质量高。

虚拟机在整合过程中的迁移势必影响数据中心的服务质量，因此在整合过程中，迁移总量VMM的值越低虚拟机整合方法越高效。

3.3 负载稳定性分析

为了验证WU-VMC方法的效率，本文利用Cloudsim平台和PlantLab上10 d的数据进行实验。文献［4］对虚拟机整合过程进行了深入的研究，并提出了一系列经典整合方法。根据实验结果，对比分析文献［4］提出的一系列整合方法与WU-VMC整合方法。

由于负载的稳定性对于虚拟机整合有着十分重要的影响，据此对数据中心活动物理主机的CPU负载情况进行记录。物理主机负载记录的时间间隔为5 min，24 h内数据中心共记录了288次物理主机负载的变化情况。

2011年3月3日数据中心活动物理主机平均负载变化情况如图4所示。WU-VMC方法的CPU利用率明显高于MAD-MMT、ST-MMT、IQR-RS三种方法。LR-MC方法的CPU利用率峰值虽然与WU-VMC方法相当，但LR-MC方法CPU利用率波动较大容易造成资源浪费。

图4 3月3日一天内活动物理主机平均负载变化Fig.4 Average workload change of running physical hosts in March 3rd

活动物理主机的负载标准差可以反映数据中心负载的稳定性。结合图5(a)可以看出，10 d内WU-VMC方法的活动物理主机CPU资源利用率标准差最小，即利用WU-VMC方法进行虚拟机整合使得数据中心负载更稳定;同时通过图5(b)可以看出，10 d内使用WU-VMC方法的数据中心活动物理主机CPU平均利用率最高。故而，WU-VMC方法能够稳定数据中心工作负载，提高数据中心资源利用率。MADMMT方法与其他三种方法由于在整合过程中未充分考虑物理主机与虚拟机的负载变化情况因而出现了负载波动较大、资源利用不充分等现象。

3.4 整合性能分析

利用文献［12］提出的六种评价指标对本文提出的WU-VMC方法以及文献［4］提出的 MAD-MMT、LR-MC、IQRRS、ST-MMT四种方法进行对比分析。不同方法在数据中心运行的各项评价指标如表2所示。图6对各方法的能耗和服务等级协议违背率进行对比。

根据表2可以看出，由于LR-MC方法对虚拟机的过度整合导致其PDM值与SLATAH值最高，即由于迁移导致的服务质量下降和由于过载导致的服务质量下降。结合图6(a)可知，LR-MC方法由于过度整合，数据中心开启的物理主机的数量下降，所以能耗比 MAD-MMT、ST-MMT方法低。MAD-MMT方法与 ST-MMT方法由于使用最小迁移时间(MMT)作为虚拟机选择策略，所以虚拟机迁移对数据中心的服务质量影响小，即PDM值小。IQS-RS方法的综合评价指标ESV值比其他方法高，故而，在五种方法中IQS-RS方法的整合效率最低。

图5 10 d内活动物理主机负载性能变化Fig.5 Workload change of running physical hosts within ten days

图6 不同方法性能对比Fig.6 Performance comparison of different methods

本文所提WU-VMC方法通过稳定物理主机负载提高资源利用率，降低物理主机过载概率。如表2所示，WU-VMC方法与其他四种方法相比，虚拟机迁移次数VMM值降低了63%～67%;由于迁移导致的服务质量下降指标PDM值降低了39%～62%;由于过载导致的服务质量下降指标SLATAH值降低了11%～41%。因此与其他四种方法相比，WU-VMC方法综合评价指标ESV值下降了65%～83%。

表2 不同方法性能评价结果Tab.2 Performance evaluation rusults of different methods

能耗和服务等级协议违背率是判断数据中心是否高效的关键指标。根据图6可知，在五种整合方法中，WU-VMC方法的EC值和SLAV值均低于其他四种方法。综上所述，本文所提WU-VMC方法在虚拟机整合的各个方面都有着较好结果。

4 结语

云数据中心虚拟资源调度和管理是云计算的关键和核心内容之一。高效率的资源调度策略不仅能降低数据中心的能耗，而且能提高数据中心的资源利用率。考虑到物理主机当前剩余资源对虚拟机迁移和虚拟机放置的影响，通过利用虚拟机的资源请求拟合物理主机工作负载，计算虚拟机与物理主机的匹配度的核心思想，系统研究并提出了虚拟机整合过程中的主机过载检测、虚拟机选择、虚拟机放置和物理主机收缩四个子算法，通过进一步对上述四个子算法进行融合，提出了一种基于负载不确定性的虚拟机整合(WU-VMC)方法。仿真实验验证了WU-VMC方法的有效性和高效性。然而本本文仅考虑了CPU这一单一资源的使用情况，忽略了内存、带宽等因素，没有综合考虑CPU、内存、带宽等因素对虚拟机整合的综合影响，如何利用多资源约束的多目标算法［17］进行虚拟机整合，将是我们下一步的研究工作。