冯 伟，陈静怡，吴 杰

（复旦大学 计算机科学技术学院，上海200433）

0 引 言

目前，数据中心通过虚拟化技术使虚拟机共享物理机资源池的方式，以物理机服务单元承载虚拟机，同时以虚拟机服务单元来承载应用服务。对于数据中心中物理资源（如服务器，网络，存储等）和虚拟资源的大量聚集，如何通过虚拟资源的调度管理改变传统IT的资源提供与管理模式，实现IT资源的集约共享，提高资源整体利用率，降低服务成本，并保证服务质量是当前迫切需要解决及改善的重要问题。目前亟需解决的问题突出表现在：

（1）传统的虚拟机资源分配与调度通常未能做到面向应用的动态自适应［1］。典型的Internet应用的访问通常是负载随时间动态变化的，如何根据应用模式及负载，结合虚拟资源特征，在进行虚拟机资源的多目标优化，目前尚未很好的解决；

（2）为实现应用负载自适应的需求，将导致虚拟机放置问题［2］的复杂化。目前学术界和工业界主要关注虚拟机与物理机之间的容量映射［3］（NP难问题），却未考虑虚拟机承载的应用资源消耗类型、用户对应用的访问模式以及虚拟机应用负载匹配关系等因素；

（3）虚拟机迁移策略［4］：目前学术界关于虚拟机迁移的研究主要考虑独占性资源如CPU、内存等的利用率，以及能耗，却没有综合考虑共享性资源I/O状况以及未考虑虚拟机具有本地动态伸缩能力。因此，在新的情况下，综合考虑各方面因素，需要确定虚拟机需要迁移的时机和策略，以确保迁移能具有较长时间的稳定。

上述问题的解决将会对数据中心的虚拟资源调度管理［5］重要意义。而以上3个问题产生的根本原因是由于虚拟机的资源消耗特征与物理机资源配置不匹配造成的。为解决该问题，本篇论文论述了一种新的虚拟机放置算法：基于资源消耗特征匹配的虚拟机放置算法。算法综合考虑虚拟机资源消耗特征、应用访问模式以及虚拟机资源配置与负载匹配关系等因素，能够有效地对虚拟机进行优化放置，同时大幅提高了物理机资源整体利用率。

1 相关研究

传统数据中心提供以物理机为基本单位的服务器租赁服务，由于资源分配的粗粒度，造成数据中心资源利用率低，能耗较高，同时服务能力无法动态扩展。

由于虚拟化技术的广泛应用，虚拟机正逐步取代物理机成为数据中心的基本服务单元。根据虚拟机具备的迁移以及本地动态伸缩的不同特性，可以提供不同形式的服务以提高资源使用率，降低能耗并保证服务质量。

以亚马逊EC2为代表的传统弹性云服务提供服务能力固定、不可迁移的虚拟机服务，采用以虚拟机为单位、按需增减开启运行的虚拟机数量，进行负载自适应。与传统数据中心以物理机作为租赁服务单位相比，能够提供较小粒度的资源分配，将有限的物理资源分配给更多的虚拟机以容纳更多用户请求；同时，数据中心资源整体利用率有所提高。文献 ［6］，研究了虚拟化数据中心的网络特征以及虚拟机的网络性能。文献 ［7］通过研究虚拟机放置和迁移策略，使用流量感知的虚拟机放置算法，将具有通信关联的虚拟机迁移到同一或网络位置相近的物理机上，降低数据中心内部通信量，提高网络可扩展性。

文献 ［8－10］等研究了粒度较为精细的动态虚拟机资源伸缩模型，通过本地资源的动态伸缩来适应负载变化，以达到提高可扩展性和保证服务质量的目的。另外文献［11］提出了一种应用无关的负载均衡机制，通过实时监控物理机及虚拟机的各项资源使用情况，结合应用的当前负载并预测其变化趋势，及时调整物理资源到虚拟资源的重新分配。文献 ［12］研究的资源控制系统能够自动的适应应用负载动态变化，并获取应用程序性能和资源分配值之间的复杂关系，按需调整分配资源量，在保证服务质量的同时提高数据中心的可扩展性。

未来数据中心的虚拟机服务单元将具备动态迁移和伸缩能力［13］，需要对虚拟资源进行自适应调度和管理以适应应用负载的动态变化。究其核心问题依然是虚拟机的优化放置问题，本文将从虚拟机的负载—资源—服务性能模型出发，研究虚拟机资源特征表达和虚拟机特征匹配算法。

2 基于资源特征匹配的虚拟机放置算法

本文首先建立应用负载—资源消耗—服务性能的关系模型，并根据三者的内在联系，采用统计和回归方法建立基于虚拟机应用性能表现和访问模式的资源特征表达。进而，虚拟机放置算法在资源特征表达的基础上，根据物理机的资源配置，选择关联与特征匹配的虚拟机集合，提高资源的整体利用率。

2.1 虚拟机性能特征模型

应用负载的变化将会影响数据中心中服务单元的内部网络带宽消耗、能耗、CPU和内存利用率的变化，而服务单元消耗的内部网络带宽、CPU和内存利用率的变化又将影响最终的服务性能。本节首先在数据中心的虚拟机服务单元层面对应用负载、服务单元资源与服务性能建立关系模型，如图1所示。

图1 应用负载—资源消耗—服务性能的关系模型

负载—资源—服务性能的关系模型的关键问题是如何根据虚拟机的CPU利用率、内存使用量和占用的内部网络带宽标识虚拟机应用的性能特征 （为简化模型，本文暂未考虑能耗的影响）。由于CPU和内存是虚拟机独占性资源，内部网络带宽是一台物理机上所有虚拟机的共享性资源，而且3个影响因素的量纲均不不同。为统一表征对虚拟机应用性能的影响，本节通过采用各影响因素的变化率来表征虚拟机应用响应性能的变化率进行归一化处理。本节采用统计和线性回归的方法建立虚拟机性能敏感因素的特征表达，描述如下

式中：Rate（VM）——应用请求数量每变化△ （Request）时虚拟机响应时间的变化率；C——常数；ki——影响系数，用以表征敏感程度；Rate（CPU）、Rate（MEM）、Rate（TRA）——应用请求数量每变化△ （Request）时，虚拟机CPU使用量与内存使用量以及内部网络带宽的变化率，且Rate（TRA）指虚拟机所在物理机的带宽消耗变化率 （包括虚拟机响应请求所消耗内部网络带宽的变化率和同一物理机上其它虚拟机消耗内部网络带宽的变化率）。

同时，本节采用标准差分析方法表达虚拟机资源消耗特征与物理机资源配置的匹配程度，匹配度公式定义如下

式中：▽i——虚拟机m性能敏感因素要求的标准系数，根据虚拟机实际运行数据得知；Sm——影响系数标准差，用以表示各类虚拟资源消耗与物理机资源配置的匹配程度；Ω（m，n）——虚拟机n对虚拟机m消耗各类虚拟资源的优化程度。

负载—资源—服务性能的关系模型能够根据负载、资源和服务性能之间的影响关系，定量确定各因素的影响程度，为虚拟机资源特征匹配算法的有效性提供评判依据。

2.2 基于访问模式的虚拟机资源特征表达

在虚拟机具有动态伸缩能力和迁移特性情况下，虚拟机已经不再是固定的资源配置，而是动态适应应用负载变化、与时间序列相关的资源配置序列集合。因此，本节将根据虚拟机的资源配置序列来关联组合特征匹配的虚拟机，建立基于访问模式的虚拟机资源特征表达模型。为简化模型，本模型暂不考虑能耗因素，把CPU、内存资源和实时流量作为关键指标，描述如下：VM （APPi）＝＜（WLD1，CPU1，MEM1，TRA1），...， （WLDT，CPUT，MEMT，TRAT）＞；其中VM （APPi）即 （WLDi，CPUi，MEMi，TRAi）表示在ti时间点，应用APPi的负载请求为APPi时，消耗的计算资源、内存资源量以及内部网络带宽；T （APPi）＝ ＜t1，t2，…，tn＞表示应用APPi的时间序列。确定每个虚拟机基于访问模式的资源特征表达具体过程如下：

（1）对VMi的负载请求、资源使用和能耗情况进行监测，确定负载的访问周期T和变化关系 WLDi＝fi（t＋T），以及资源消耗变化关系RESOURCE （CPUi，MEMi，TRAi）＝hi（t＋T），并将每个访问周期T内的资源需求＜（WLD1，CPU1， MEM1，TRA1）， …，（WLDT，CPUT，MEMT，TRAT）＞作为一组样本；

（2）对每个虚拟机维护一定数量的资源需求样本信息，若样本信息超过样本容量时则根据各样本的预测误差大小对样本更新维护；

（3）处理样本数据，确定虚拟机基于访问模式的资源特征表达TimeResourFeature（VMi）。

2.3 虚拟机资源特征匹配算法

虚拟机资源特征匹配算法建立在虚拟机资源特征表达的基础之上，选择同时满足性能特征和应用访问特征资源匹配条件虚拟机集合进行关联，进而有效匹配物理机的资源配置。

算法将所有数据中心的物理机PMSET逻辑划分为n个物理机集合，其中物理机集合PMSETi中包含的物理机数量为pi；根据物理机的划分，将数据中心的所有虚拟机VMSET划分为相应的虚拟机集合，虚拟机集合VMSETi中包含的虚拟机数量为vi。物理机集合关系表述如下

式中：PMSET（i，j）——物理机集合 PMSETi中的第j台物理机。虚拟机集合关系表述如下

式中：VMSETi——PMSETi中所有的虚拟机集合，VMSET（i，k）——虚拟机集合 VMSETi中的第k个虚拟机。具体算法流程如下：

Match （PMSETi，VMSETi）//特征匹配算法

while（PMSET）｛//遍历物理机集合

foreach （PMSET（i，j）） ｛//随机选择某一虚拟机对物理机初始化

VMSET（i，j，k）＝ RandomSelect （VMSET）；

//将物理机的可使用资源去除虚拟机需要的资源得到空闲资源IdleResource （PMSET（i，j）） ＝InitResource （PMSET（i，j））－Resource （VMSET（i，j，k））；

while （IdleResource （PMSET（i，j）） ＞ MinResource（VMSETi））｛

//寻找同时满足两个特征匹配条件的虚拟机组合

if（KeyFactorMatch （VMSET（i，j，k），VMSETi－ VMSET（i，j，k）））

selectVMs＝ TimeFeatureMatch （VMSET（i，j，k），VMSETi－ VMSET（i，j，k））

//调整物理机空闲资源

IdleResource （PMSET（i，j）） ＝ IdleResource （PMSET（i，j））－Resource （selectVMs）；

｝//end while

｝//end foreach

｝//end while

其中，TimeFeatureMatch（）表示基于访问模式的资源特征匹配条件，KeyFactorMatch（）表示性能敏感因素的特征匹配条件。特征匹配算法 Match（PMSETi，VMSETi）的平均时间复杂度为O（·pi），将VMSETi经过排序优化后可达到O（K·vi·pi）其中K为常数；算法可对多个物理机集合同时进行匹配，进而可提高匹配效率。

3 实验设计及结果分析

实验目的是根据监控资源实际运行情况，利用本文描述的资源消耗特征模型对应用所使用的资源建模，并验证基于资源消耗特征匹配的虚拟机放置算法有效性。

实验环境采用CentOS系统，并且部署Xen虚拟化环境，在Xen的Domain0上发布虚拟机作为虚拟化资源；同时采用SNMP协议获得CPU利用率、内存使用量以及占用的内部网络带宽等资源实时运行数据，使用Jmeter获得不同请求数量下的虚拟机响应时间RTT。实验环境包括3台物理机，其中一台作为SNMP监控服务器，其余两台部署虚拟机。

3.1 虚拟化环境下内部网络带宽分配机制

由于内部网络作为多个虚拟机的共享资源，需要首先研究虚拟化环境下的网络带宽分配机制。在试验环境的某一台物理机上部署3台同样配置的虚拟机VM1、VM2和VM3。在0s时，VM1向VM2，VM2向VM3同时进行文件传输；40s时VM3向VM1进行文件传输；100s时停止VM1向VM2的文件传输，实验结果如图2所示。

图2 Xen虚拟化环境下的内部网络带宽使用情况

根据实验结果分析得知Xen虚拟化环境下的内部上行网络总带宽可达到11MB/s，网络带宽分配采用可抢占式的平均共享机制。因此在虚拟化环境下，同一物理机上不同用户的虚拟机将会相互影响，这种内部网络带宽分配机制在将来的理论研究和实践中需要进行改进。

3.2 虚拟机性能影响因素特征表达

在两台虚拟机VM1和VM2上分别部署两种应用：SNS1和SNS2，其中SNS1主要处理HTTP请求，SNS2主要处理检索请求；同时为简化处理数据，本文设置二者的应用访问周期相同，包含请求量递增到最大请求量的全部过程。根据监控得到的实际运行数据，本文在实验环境中以虚拟机性能敏感因素的影响系数均值作为物理机资源的配置要求标准。VM1性能特征表达的回归分析结果见表1。

表1 VM1性能特征表达的回归分析

得到SNS1应用的虚拟机性能影响因素特征表达为：Rate（VM1）＝2.11－0.31·Rate （CPU）－0.04·Rate（MEM）－0.12·Rate（TRA）；虚拟机 VM2性能特征表达的回归分析结果见表2。

表2 VM2性能特征表达的回归分析

得到SNS2应用的虚拟机性能影响因素特征表达为：Rate（VM2）＝2.29－0.33·Rate （CPU）－0.55·Rate（MEM）－0.30·Rate（TRA）；根据公式计算得到，影响系数标准差S1＝0.337672，S2＝0.094403，即 VM2的资源消耗均衡程度优于VM1。

3.3 算法性能分析

模拟虚拟机应用的请求变化，根据两种应用访问模式的虚拟机资源特征表达关系进行特征匹配，匹配后两虚拟机的综合性能特征表达见表3。

表3 VM1和VM2综合性能特征表达的回归分析

得到SNS1和SNS2两种应用的综合虚拟机性能影响因素特征表达为：Rate（VM12）＝2.44－0.32·Rate（CPU）－0.25·Rate（MEM）－0.29·Rate（TRA）；根据公式计算得到，影响系数标准差 S12＝0.029427。优化度为Ω（s12，s1）＝11.48，Ω（s12，s2）＝3.21，即将虚拟机 VM1和 VM2关联在同一物理机上时，与将两虚拟机分别放置在不同的物理机上时相比，其消耗资源的优化程度将显著提高。

在本实验环境中，一台物理机最多可承载4台VM1或VM2类型的虚拟机。首先在一台物理机上承载4台VM1虚拟机，当应用请求使虚拟机的CPU利用率达到90%以上，即CPU资源已经充分利用时，其内存使用率仅为37%。一个访问周期内，虚拟机VM1的资源特征如图3所示。

图3 虚拟机VM1的资源利用率

根据实验的设计，可以VM1实验结果等效为物理机的资源使用情况，即物理机的CPU资源充分利用时，其内存资源处于低效利用状态，造成很大浪费。

经过算法关联后，一台物理机承载2台VM1和2台VM2虚拟机，当应用请求使虚拟机的CPU利用率达到90%以上，即CPU资源已经充分利用时，其内存使用率为76%，其中VM1和VM2资源综合利用率为二者的加权平均值。一个访问周期内，虚拟机VM1和VM2的资源综合特征如图4所示。

图4 虚拟机VM1和VM2资源综合利用率

同样地，将VM1和VM2的综合实验结果等效为物理机的资源使用情况，即当物理机的CPU资源充分利用时（90%以上），其内存利用率由37%提高到76%，资源利用率得到显著提高，进而验证了算法的有效性。

4 结束语

本文在进行虚拟机的优化放置时，不再将虚拟机与物理机的映射这个NP难问题作为核心来解决，而是基于监控和统计对虚拟机资源消耗特征进行参数化表达，并将特征匹配的虚拟机进行关联，使得每个物理服务单元的资源得到充分有效的利用。同时算法是在监控和统计分析的基础上进行的，因此可以对，避免了虚拟机不必要的迁移。经过实验验证，虚拟机放置算法VMP－RUFM通过调整物理机上各虚拟机性能影响因素的影响系数以适应物理机的资源配置，达到了提高物理资源整体利用率的目的。

［1］Gupta R.A two stage heuristic algorithm for solving the server consolidation problem with item－item and bin－item incompatibility constraints［C］.IEEE International Conference on Services Computing，2008：39－46.

［2］Chris Hyser，Bret Mckee，Rob Gardner，et al.Autonomic virtual machine placement in the data center ［R］.HP Labs Technical Report，2007.

［3］Swarna Mylavarapu，Vijay Sukthankar，Pradipta Banerjee.An optimized capacity planning approach for virtual infrastructure exhibiting stochastic workload ［C］.Proceedings of the ACM Symposium on Applied Computing.New York，NY，USA：ACM，2010.

［4］Park J，Kim J，Choi H，et al.Virtual machine migration in selfmanaging virtualized server environments［C］.Proc Int Conf on Advanced Communication Technology，2009：2077－2083.

［5］Nie L，Xu Z.An adaptive scheduling mechanism for elastic grid computing ［C］.Proceedings of the Fifth International Conference on Semantics，Knowledge and Grid.Washington，DC，USA：IEEE Computer Society，2009：184－191.

［6］Wang Guohui，Eugene Ng T S.The impact of virtualization on network performance of Amazon EC2data center ［C］.San Diego，California，USA：Proceedings of the 29th conference on Information communications，2010：1163－1171.

［7］Vasileios Pappas，Li Zhang.Improving the scalability of data center networks with traffic－aware virtual machine ［C］.San Diego，CA：Proceedings of IEEE INFOCOM，2010：1－9.

［8］Timothy Wood，Prashant Shenoy，Arun Venkataramani，et al.Black－box and gray－box resource management for virtual machines ［J］.Computer Networks：The International Journal of Computer and Telecommunications Networking，2009：2923－2938.

［9］SONG Ying，LI Yaqiong.A service－oriented priority－based resource scheduling scheme for virtualized utility computing ［C］.High Performance Computing Conference，2008：186－193.

［10］SONG Ying，WANG Hui，LI Yaqiong，et al.Multi－tiered on－demand resource scheduling for VM－based data center，international symposium on cluster［C］.Cloud and Grid Computing，2009：148－155.

［11］ZHOU Wenyu，YANG Shoubao，FANG Jun，et al.A load balancing scheme for virtual machine cluster based on dynamic resource allocation ［C］.Barcelona，Spain：9th International Conference on Grid and Cooperative Computing，2010：87－98.

［12］PradeepPadala，Hou Kai－Yuan，Kang G Shin，et al.Automated control of multiple virtualized resources ［C］.Proceedings of the 4th ACM European Conference on Computer Systems，2009：13－26.

［13］Xu Jing，José A B Fortes.Multi－objective virtual machine placement in virtualized data center environments［J］.IEEE/ACM International Conference on Green Computing and Communications ＆ IEEE/ACM International Conference on Cyber，Physical and Social Computing，2010：179－188.