云数据中心网络中的先应式碎片整理算法＊

郭 磊 侯维刚

（东北大学信息科学与工程学院，沈阳，110819）

引 言

近年来，Amazon EC2，Microsoft Azure，Infrastructure-asa-service（IaaS）等云数据中心平台快速发展，并实现了多个应用服务提供商对底层物理基础设施的共享［1］。由于虚拟机（Virtual machine，VM）的动态生成、重组与下线，云数据中心网络资源易产生碎片，从而导致较低的资源利用率［2，3］。图1（a）为产生上述资源碎片的现象举例，其中服务器S1和S2承载了3个VM，且各自的总容量为8个单位资源。VM1和VM3各占用2个单位资源，而VM2占用3个单位资源。因此在图1（a）所示的网络状态下，若一个占用7个单位资源的VM请求到达，则无法被此网络容纳，从而产生资源碎片。

现有云数据中心网络资源碎片整理方案可归纳为两大类：基于VM请求到达的迁移策略，以及服务器整合策略。在第一种策略中，当一个VM请求到达后，云数据中心网络首先判断自己能否容纳这个VM［4，5］。若不能，它将对已存放在服务器内的一个或多个VM进行迁移处理，使其中的一个服务器能够腾出空间来容纳到达的VM［6］。这是个可行策略，但是，当上百个VM需要在短时间内置入服务器中时，云数据中心网络将执行频繁的VM迁移，这会导致严重的服务中断和延迟。

第二种策略是服务器整合技术，它通过减少服务器的使用数量以腾出更多空闲服务器来容纳后续到达的VM［7-15］。如图1（b）所示，将VM3迁入服务器S1后可腾空S2，从而容纳即将到达的、占用7个单位资源的VM请求。可见，此技术可在一定程度上减少资源碎片，但腾空服务器会产生频繁且无效的VM迁移，系统灵活性也较差。仍以图1（a）为例，若即将到达的两个VM请求分别占用5个和3个单位资源，则无需采用服务器整合，便可直接将它们放入网络中。

因此，一个更加高效的云数据中心网络资源碎片整理方案应重点关注两个方面的问题：（1）何时执行必要的碎片整理操作；（2）在碎片整理进程中，哪些VM必须进行迁移。针对上述两个关注点，本文提出了云数据中心网络中基于预测的先应式碎片整理算法。首先，本文对上述问题进行数学定义，在给定网络中现有VM集合的条件下，对后续即将到达的VM集合进行预测，从而求出最大限度避免无效VM迁移的碎片整理方案（即最优解）。由于此问题是NP困难的，本文还设计了有效的启发式方法获取近似最优解。

图1 资源碎片与服务器整合技术示意图Fig.1 Diagram of resource fragments and server consolidation

1 问题定义

给定一个具有S个服务器的云数据中心网络。其中，对于服务器j（1≤j≤S）：Oj为总容量；Lj（Lj≤Oj）为占用资源；Fj为可用剩余资源，且Fj＝Oj-Lj。根据惯例（如 Amazon EC2），假设云数据中心网络将受理C种类型VM。每个VM请求为一个三元组〈c，ec，rc〉。其中，c为类型索引号；ec为付费；rc为资源需求。为便于讨论，假设rc为一实数，且r1＞r2＞…＞rC。资源需求越大，付费越高，因此有e1＞e2＞…＞eC。在特定时间点t，云数据中心网络内可存在先前放置的VM（即现有VM）、一些新到达或离开此网络的VM。此外，可对特定未来时间点t′（t′＞t）的VM到达与离开状态做出预测，从而在时间点t求解有效的VM迁移决策。一些重要的符号定义如下（以首个字母表排序）：

A为二维VM放置矩阵；C为类型总数；ec为容纳一个类型-c的VM所获得的收入；Fj为第j个服务器的可用剩余资源；Gs为存放迁出VM的服务器集合；Gt为具有可用剩余资源的服务器集合；i为VM 索引号；j为服务器索引号；lr为迁移成本系数（0＜lr＜1）；lu为服务器成本系数（0＜lu＜1）；Lj为第j个服务器的占用资源；mc为网络内现有类型-c的VM数；nc为在时间点t到达的、类型-c的VM数；n′为将在时间点t′到达的VM总数；n′c为将在时间点t′到达的、类型-c的VM数；Oj为第j个服务器的总容量；pc（n′c）为将在时间点t′到达的n′c个类型-c的 VM 的概率；φc为将在时间点t′到达的类型-c的 VM比例，且Φ＝｛φc｝c∈［1，C］；rc为类型-c的 VM 的资源需求；S为网络内服务器总数；t为当前时间点；t′为未来时间点；Uj为一个布尔变量，用以记录第j个服务器是否空闲。

1.1 VM迁移的最佳放置

计算总迁移和服务器成本如下

其中，∀j∈［1，S］

对现有VM的放置应遵循以下约束

新到达的VM的放置以及对现有VM的迁移应遵循以下约束

式（4，6）确保VM不被分割；式（7）表明采用迁移后，某些VM请求仍可能被阻塞；式（5，8）表明可容纳的VM数受限于服务器的总容量。则考虑VM迁移的最佳放置问题可描述为

1.2 基于预测的先应式碎片整理

由于迁移成本只与现有VM有关，仍可根据式（2）计算总迁移和服务器成本。类似地，未来到达VM的放置及对现有VM的迁移遵循以下约束

则基于预测的先应式碎片整理问题描述如下

实际上，任一时间点新到达VM请求数均是一个有限值。因此，假定可得到未来时间点t′新到达的VM 数预测值为n′。给定向量Φ＝｛φc｝c∈［1，C］（其中φc为在未来时间点t′到达的、类型-c的 VM 比例），从而有

相应地，遵循式（6，11，12）约束，将可预测的总收入化简为

则基于预测的先应式碎片整理问题可描述为

2 算法描述

在时间点t，本文所提出的基于预测的先应式碎片整理（Provident resource defragmentation，PRD）算法主流程描述如下：

输入：At-＝｛At-（c）｝c∈［1，C］，Φ＝｛φc｝c∈［1，C］，n′

输出 ：At，α，At′，β′

（1）At，α（0，0）＝At-；（At′，β′（0，0），nt）←BVF（At-，Φ，n′）

（2）If所有n′个VM均已成功放置then

（3）forc＝1，2，…，Cdo

首先，初始化n′×S空矩阵At′，β′（0，0）。随后以类型索引号的升序对 VM 进行初始放置：对于某种类型VM，遍历所有服务器以获取能够容纳此类型VM的数量。

图2 BVF子算法举例示意图Fig.2 Diagram of illustration of BVF sub-algorithm

如图3所示，执行BVF子算法后，随着后续放入服务器中某类型VM数的增加，收入将提升。但由于迁移成本的引入，整体利润不一定呈线性增长趋势。因此采用MaxPD子算法为某类型VM寻求能取得最大利润的值。

执行BVF子算法后，若后续容纳了k（0≤k≤n′c-）个类型c的 VM，采用矩阵At，α（c，k）和At′，β′（c，k）分别记录现有VM的迁移状态，以及新到达的、类型-c的VM 分配情况。根据矩阵At，α（c，k）和At′，β′（c，k）的记录，可分别计算出收入和成本κc，k

图3 PRD算法举例示意图Fig.3 Diagram of illustration of PRD algorithm

MinCM子算法：为避免迁移的乒乓效应，采用单向迁移技术保证迁移后的VM不再迁回原服务器，则有以下两个引理成立。

引理2 执行BVF子算法后，若存在未能成功放置的VM，则有∀j（1≤j≤S），Fj＜rc＊。

导出c＊后，初始化两种服务器集合：（1）存放迁出VM的服务器集合Gs；（2）具有可用剩余资源的服务器集合Gt。引入迁移控制，即仅有类型-c′（c＊＜c′≤C）的VM可被迁移，从而有

如图2（b）所示，有c＊＝1，且每个服务器的可用剩余资源均小于16。因此，Gs＝｛1，2，3，4，5，6｝，Gt＝｛2，3，6，7，8｝。

为进一步容纳一个类型-c的VM，在Gs中确定一个服务器，通过将其内VM以最小的开销迁移到Gt中其他服务器，以腾出更多空间。具体地，首先在Gs中确定具有最大空闲空间的服务器j＊，若j＊∈Gt，更新G′t＝Gt-｛j＊｝。其次判断服务器j＊能否通过VM迁移后腾出空间容纳一个类型-c的VM：（1）计算服务器j＊中类型-c′的 VM 数fc′（j＊），c＊＜c′≤C；（2）采用BVF方法计算G′t内所有服务器可用剩余资源最多可容纳的类型-c′的 VM 数fc′（G′t），c＊＜c′≤C；（3）确定从服务器j＊中最多能够迁出的、类型-c′的 VM 数fc′＝min［fc′（j＊），fc′（G′t）］，c＊＜c′≤C；（4）确定能够容纳一个类型-c的 VM 的条件为

若满足上述条件，采用首次命中（First-fit，FF）方法将服务器j＊中的VM迁出；否则使Gs＝Gs-｛j＊｝，进行while循环直到Gs为空。例如，图2（b）中可确定j＊＝6。根据上述定义可得f2（6）＝2，f3（6）＝0。由于服务器6属于Gt，则更新G′t＝｛2，3，7，8｝，因此有f2（G′t）＝2，f3（G′t）＝4。显然，f2＝2且f3＝0。由于F6＋f2·r2＝8＋8×2＝24＞r1＝16，从而将一个类型-2的VM从服务器6迁移到服务器7后，将一个类型-1的VM放入服务器6中，如图2（b）所示。采用类似方法，可确定j＊＝2，并通过将一个类型-2的VM从服务器2迁移到服务器8，同时将一个类型-3的VM从服务器2迁移到服务器3，进一步将一个类型-1的VM放入服务器2中，如图2（c）所示。

PRD算法时间复杂度主要取决于运行FF方法的次数，而每运行一次FF方法的时间复杂度为C2·S。在MinCM子算法中最多调用S次FF方法，而在主算法中最多调用n′次MinCM子算法，因此，PRD算法时间复杂度约为O（n′·C2·S2）。

3 仿真实现与性能分析

采用异构云数据中心网络，即服务器总容量可从｛40，60，80｝中随机选取。引入时间轴，该轴被等分为24个时隙。VM请求在某一时隙的起始端到达，且服务持续时间占用时隙数满足均匀整数分布［1，4］。网络内存在C＝3种类型 VM：r1＝16，r2＝8，r3＝2且ec＝rc，c＝1，2，3。给定Φ＝｛0.2，0.5，0.3｝和以下仿真场景。

场景1S＝35，lr＝0.01，预测未来到达VM请求数采用均值n，依次取为｛150，200，250，300，350｝，且n′＝（即预测精确度为100%）。

场景2S∈｛35，40，45，50，55｝，lr＝0.01，均值从150增长到300，即每5个时隙后n增长50，但n′＝230（即存在预测误差）。

总利润（Total profit，TP）：每个时隙产生的利润为相应收入与迁移成本之差，总利润为20个时隙产生利润总和；平均迁移成本（Average migration cost，AMC）为20个时隙产生的总迁移成本与执行碎片整理操作的次数之比。

表1，2分别显示在场景1和2下可为固定周期的服务器整合方法找到最佳周期T，使相应总利润最大（最大利润为表中粗体数据）。在场景2下，各方法的总利润随着服务器数量的增加而升高。同时，所提PRD算法的总利润高于未采用碎片整理的普通VM放置方法和固定周期的服务器整合方法，即使在预测精度较低情况下，PRD总利润同样接近于总利润最优值，偏差率仅为6%。

表1 场景1下的总利润比较结果Table 1 Comparative results of TP under scenario 1

表2 场景2下的总利润比较结果Table 2 Comparative results of TP under scenario 2

本文假设网络内服务器可用资源可整合成连续的、无碎片的资源池，即可得到总利润最优值。

图4（a，b）分别显示在场景1，2下PRD算法有效地降低了平均迁移成本，且PRD平均迁移成本不会随着VM请求数和服务器数量的增加而发生明显变化。采用固定周期的服务器整合方法所产生的迁移成本会随着服务器数量的增加而线性增长，这意味着PRD算法更加灵活，且适用于大规模的云数据中心网络。

4 结束语

虚拟机的动态创建和下线会使云数据中心网络内产生大量的资源碎片，本文给出了针对云数据中心网络资源碎片整理的系统阐述和分析。首先提出了在某一时段最小化无效VM迁移成本的优化问题，并对其进行数学定义。随后设计了启发式算法获取上述问题的近似最优解，并通过仿真结果验证了所提算法的优越性。本文所设计的算法只考虑了单一维度的计算资源。因此在未来的研究工作中，将重点考虑设计面向多维度计算资源的碎片整理算法。此外，多维度资源（如计算、内存、存储、带宽以及I／O等）之间的相关性也将是未来设计碎片整理算法所要考虑的重要方面。

［1］ Armbrust M，Fox A，Grifĝth R，et al.A view of cloud computing［J］.Commun ACM，2010，53（4）：50-58.

［2］ Sridharan M，Calyam P，Venkataraman A，et al.Defragmentation of resources in virtual desktop clouds for cost-aware utility optimal allocation［C］∥Proceedings of IEEE International Conference on Utility and Cloud Computing.Los Alamitos：IEEE Computer Society Press，2011：253-260.

［3］ He S，Guo L，Guo Y.Real time elastic cloud management for limited resources［C］∥Proceedings of IEEE International Conference on Cloud Computing.Los Alamitos：IEEE Computer Society Press，2011：622-629.

［4］ Mishra M，Sahoo A.On theory of VM placement：Anomalies in existing methodologies and their mitigation using a novel vector based approach［C］∥Proceedings of IEEE International Conference on Cloud Computing.Los Alamitos：IEEE Computer Society Press，2011：275-282.

［5］ He S，Guo L，Ghanem M，et al.Improving resource utilisation in the cloud environment using multivariate probabilistic models［C］∥Proceedings of IEEE International Conference on Cloud Computing.Los Alamitos：IEEE Computer Society Press，2012：574-581.

［6］ Calcavecchia N，Biran O，Hadad E，et al.VM placement strategies for cloud scenarios［C］∥Proceedings of IEEE International Conference on Cloud Computing.Los Alamitos：IEEE Computer Society Press，2012：852-859.

［7］ Khanna G，Beaty K，Kar G，et al.Application performance management in virtualized server environments［C］∥Proceedings of Network Operations and Management Symposium.Piscataway：IEEE，2006：373-381.

［8］ Bobroff N，Kochut A，Beaty K.Dynamic placement of virtual machines for managing SLA violations［C］∥Proceedings of International Symposium on Integrated Network Management.Piscataway：IEEE，2007：119-128.

［9］ Speitkamp B，Bichler M.A mathematical programming approach for server consolidation problems in virtualized data centers［J］.IEEE Transactions on Services Computing，2010，3（4）：266-278.

［10］Wang M，Meng X，Zhang L.Consolidating virtual machines with dynamic bandwidth demand in data centers［C］∥Proceedings of IEEE INFOCOM.Los Alamitos：IEEE Computer Society Press，2011：71-75.

［11］Wood T，Shenoy P，Venkataramani A，et al.Black-box and gray-box strategies for virtual machine migration［C］∥Proceedings of the 4th USENIX conference on Networked systems design implementation.Piscataway：IEEE，2007：17-17.

［12］Xu L，Chen W，Wang Z，et al.Smart-DRS：A strategy of dynamic resource scheduling in cloud data center［C］∥Proceedings of International Conference on Cluster Computing Workshops.Piscataway：IEEE，2012：120-127.

［13］Beloglazov A，Buyya R.Managing overloaded hosts for dynamic consolidation of virtual machines in cloud data centers under quality of service constraints［J］.IEEE Transactions on Parallel and Distributed Systems，2013，24（7）：1366-1379.

［14］Deng W，Liu F，Jin H，et al.Lifetime or energy：Consolidating servers with reliability control in virtualized cloud datacenters［C］∥Proceedings of International Conference on Cloud Computing Technology and Science.Los Alamitos：IEEE Computer Society Press，2012：18-25.

［15］Feller E，Morin C，Esnault A.A case for fully decentralized dynamic vm consolidation in clouds［C］∥Proceedings of International Conference on Cloud Computing Technology and Science.Los Alamitos：IEEE Computer Society Press，2012：26-33.