能耗与性能均衡的云计算虚拟机部署优化算法

许利军， 王付强

(1.新乡学院 计算机与信息工程学院，河南 新乡 453003；2.武汉理工大学 计算机学院，武汉 430063)

0 引 言

云计算已经成为学术界和产业界的热点问题，它带来了递增式广域式应用和规模式经济的计算模型[1-2]。由于云计算的快递发展，云服务提供商越来越多的建立大规模数据中心以满足用户对多类型资源的需求[3]。云数据中心的加速建立带来了急剧增长的能耗问题，正成为云服务提供者面临的巨大难题。能耗的增加除了增加云服务的运营成本和总体投入，还会加重碳排放[4]。除了任务执行过程中造成的数据中心能源消耗，空闲服务器仍然消耗满载时能源的30%[5]，因此，服务器的低载问题同样需要进行优化。虚拟化的服务器合并技术是提高数据中心能效的有效手段之一，它可以降低活动服务器的使用数量，消除闲置能耗。

相关工作中，文献[6]中在大规模虚拟化系统中提出了一种新的功耗管理算法，实现了硬件扩展和虚拟机合并。文献[7]中虚拟机的动态迁移被定义为优化问题，优化目标是最小化云物理主机的能耗。以上工作并未从用户的角度考虑性能方面的SLA违例问题。文献[8]中提出一种高效的合并算法，同步实现能耗和SLA违例的降低。算法引入一种SLA感知资源分配机制，考虑了能耗与性能间的均衡以及主机占用与虚拟机在映射主机的相关性因素。文献[9]中研究了虚拟化数据中心中功耗与性能有效的资源管理问题，以通过同步最小化功耗和SLA违例的方式最大化提供者收益为目标，设计了一种资源分配算法。文献[10]中引入一种改进装箱算法优化虚拟机迁移，优化资源分配。同时引入一个阈值定义虚拟机的迁移时机，以合并的手段降低主机利用数量。但该方法未考虑频繁切换和虚拟机迁移的开销问题。

显然地，目前云环境中的虚拟机部署问题主要涉及单目标和双目标优化[6-12]，即在主机使用数量、SLA违例和应用服务质量(Quality of Service,QoS)性能保障、或数据中心能耗和虚拟机(Virtual Machine,VM)迁移等因素上进行选择优化。以上目标通常相互冲突。降低主机使用量，VM需要频繁迁移；降低SLA违例，VM需要频繁合并与迁移，势必会开启更多主机[13-14]；能耗与主机利用率相关，主机使用数量最少，并不一定能耗最小等。本文将考虑主机能耗、SLA违例及VM迁移量的相互关联，实现一种性能与能耗均衡的虚拟机部署算法。

1 虚拟机部署与功耗模型

图1所示为本文中云数据中心的能效虚拟机部署框架图。具体包括两个主要模块：

(1) 虚拟机VMs分析模块。该模块决定每个VM请求的每秒百万指令数(Million Instructors Per Second,MI/s)和内存，以及基于前端服务器计算的来自用户的VM请求数量得到的每个时间间隔内系统运行的VMs。

图1 能效虚拟机部署模型

(2) 虚拟机部署策略模块。该模块处理两个参数：①由VMs分析模块计算的资源需求；②数据中心设备的当前状态(开/关)以及每个开启服务器的可用资源。模块(2)试图寻找最小的服务器数量以完成VMs的资源需求。

云数据中心中计算节点的功耗主要由CPU、内存、磁盘存储及网络带宽构成。比较其他系统资源，CPU消耗了大部分能源。因此，本文将关注于CPU功耗及其管理。CPU利用率通常正比于全局系统负载，为了简化模型，本文应用一种负载与功耗成线性关系的功耗模型。研究表明，空闲服务器的能耗仍约占CPU满载能耗的70%，这表明将空闲服务器切换至睡眠模式可以降低总体功耗。应用以下功耗模型：

P(u)=kPmax+(1-k)·Pmaxu

(1)

式中：Pmax为服务器满负载时的最大功耗;k为空闲服务器的功耗比例，一般为70%；u为CPU利用率。

一般地，由于负载的不断变化，CPU的利用率会随着时间而发生改变，因此，u是时间的函数，表示为u(t)，物理主机的总能耗E可定义为某段时间间隔内功耗函数的积分形式：

(2)

2 SLA违例指标

QoS需求通常以服务等级协议SLAs进行形式化描述，通常以最小吞吐量或最大响应时间进行衡量。由于不同的QoS特征对于不同的的应用类型是不尽相同的，有必要定义一种通用的与负载类型无关的度量标准，以评估基础设施中部署虚拟机所交付的SLA等级。本文使用SLA违例SLAV指标度量算法性能，该指标由每个活动主机的SLA违例时间(SLA Time of Active Host,SLATAH)和由于VM迁移带来的性能下降(Performance Degration Model,PDM)构成，具体定义为：

SLAV=SLATAH×PDM

(3)

(4)

(5)

式中：Tsi为主机i经过的100%利用率的总持续时间；Tai为主机i为活动状态的总时间；N为服务器数量；Cdj为表示迁移导致的虚拟机j的性能降低的估算；Crj为生命周期内虚拟机j请求的总的CPU能力。

3 虚拟机部署策略

云环境中的虚拟机合并技术可以减少主机使用数量，从而降低主机的闲置能耗。先前的工作多利用每个VM的最大CPU负载作为标准对VMs进行排序与合并。然而，由于处理器功耗的改变，该方法可能导致云数据中心的高能耗。以下利用一个算例阐述该问题的影响。

假设一个云数据中心的资源提供者拥有3个物理服务器，标识为S1、S2和S3，每个服务器拥有一个CPU，性能为1 000 MI/s。现需要配置5台虚拟机VMs，标识为VM1、 VM2、VM3、VM4和VM5，其最大性能需求分别为250、500、1 000、750、500 MI/s。假设所有物理服务器初始是空闲的，且第1个到达的用户在每个VM上的需求为100、200、600、300、200 MI/s。如果利用基于静态VM最大CPU负载方法进行VM合并，则分配结果如图2所示。可以得出，3个物理服务器的实际利用率分别为40%、40%和60%。

图2 基于CPU负载的VM部署

本文设计一种基于需求的方法，基于每个VM的实际MI/s进行VM合并。该方法的最终分配结果如图3所示。可以得出，该方法仅部署了两台物理服务器，每台的实际利用率为70%。

图3 基于需求的VM部署

为了降低云数据中心的能耗，本文设计了一种基于能效的VM部署启发式算法(Virtual Machine Power Aware,VMPA)解决VM部署问题。在VMPA中，首先根据动态请求的MIPS对VMs进行降序排列。排序后，为每个VM寻找提供最少功耗增加的最优服务器。算法充分利用节点的异构性，优先选择功效最高的节点利用。该步骤中，首先，在所有充分利用和非空闲服务器中选择最佳服务器，如果没有找到分配VM的服务器，算法尝试在所有非充分利用的服务器寻找最优服务器。最后，如果所有服务器均无法找到目标，算法从空闲服务器上开启新的服务器进行VM部署。VMPA算法的伪代码如算法1所示。VMPA算法的时间复杂度为O(n×m)，其中，n为部署的VM数量，m为物理服务器的数量。

算法1VMPA-Virtual Machine Placement Algorithm

1. Input: ServerListH={h1,h2,…,hn}, VMListV={v1,v2,…,vm}

2. Output: Solution of VMs placement

3. Initialize EmptyServerListE, Underutilized Server ListU

4. SortVMsInDecreasing MIPS

5. ForviinV

6. InitializePmin←MAX

7. Initialize HV←NULL

8. ForhjinH

9. Ifhjhas no placed VMs

10. EmptyServerListE←hj

11. Else ifhjis an underutilized server

12. UnderutilizedServerListU←hj

13. Else ifhjhas enough resources

14.P(u)=k×Pmax+(1-k)×Pmax×u

15. IfP

16. HV←hj

17.Pmin←P

18. If HV=NULL

19. ForuiinE

20. Return 13-17

21. If HV=NULL

22. ForejinE

23. Return 13-17

24. If HV≠NULL

25. HV←HV(vi)

26. Else

27. Return infeasible placement

28. Return VMs placement solution

4 虚拟机迁移选择

对于VM迁移，考虑引进一种基于CPU上下限的双门限值，使得CPU利用率保持在双门限值之间。如果CPU利用率低于下限值，则该服务器视为低载主机，所有VMs需要从该主机上迁移出去，然后将该主机切换至睡眠模式以降低空闲功耗。如果CPU利用率超过上限值，则该服务器视为过载主机，需要迁移部分VMs以降低CPU利用率。双门限值方法如图4和图5所示。

为了从过载主机上选择最佳VMs进行迁移，本文设计了一种VM迁移算法(Virtual Machine Migration Selection Algorithm, VMMSA)，可以使得迁移VMs的数量最少。VMMSA算法中，需要考虑两个条件：①该虚拟机的CPU占用大于主机上所有虚拟机的CPU占用与门限值之差；②若该虚拟机从主机迁移，门限值与新的CPU占用之差是所有虚拟机迁移情况中值最小的。算法运行至主机CPU利用率低于上门限值为止，可以实现迁移的VMs数量达到最少以降低迁移开销。

图4 过载服务器的上门限值

图5 低载服务器的下门限值

令Vj表示当前分配到主机j上的虚拟机集合，Q(Vj)表示Vj的幂集，包括空集和全集的所有子集。VMMSA算法寻找的迁移虚拟机集合表法为R。

Minimize |R|

式中：uj为主机j当前的CPU占用；uj(v)为分配给虚拟机v的CPU占用率。VMMSA算法的伪代码如算法2所示。

算法2VMMSA-Virtual Machine Migration Selection Algorithm

1. Input: ServerListH={h1,h2,…,hn}

2. Output: MigratedVMListM

3. ForhjinH

4. Receive VMList deployed onhj

5. VMListSortDecreasingCpuUtilization

6. Receive R_CPU inhj

7. Initialize Ratio←MAX

8. While R_CPU >Upper

9. Forvmin VMList

10. If VM.Cpu>R_CPU-Upper

11. r←VM.Cpu-(R_Cpu-Upper)

12. ifr

13. Ratio←r

14. BestVM←vm

15. Else if Ratio==MAX

16. BestVM←vm

17. Break

18. Update R_CPU = R_CPU-BestVM.Cpu

19. M←vm

20. Delete BestVM from VMList

21. If R_Cpu

22.M←all VMs onhj

23. ReturnM

5 算法流程与时间复杂度分析

算法首先处理过载服务器上的VMs和新到达的VMs，将以上VMs部署到目标服务器上后，对低载服务器上VMs进行重新分配，并关闭低载服务器。然后，从过载服务器上选择合适的VMs与新到达的VMs进行合并作为VM部署算法的输入。图6所示为所提算法的流程图。

图6 算法流程

假设N为物理服务器的数量，M为待部署于服务器上的VMs数量，H为新到达的VMs数量，L为过载服务器数量，K为低载服务器数量，VMPA算法的时间复杂度为O(N×M)，VMMSA算法的时间复杂度为N。因此，算法时间复杂度为

2N+H+N(M+H)+NM+

K+NM=O(3NM+N)

6 仿真实验

为了评估算法性能，本节在CloudSim平台[15]中实现了所提的虚拟机部署算法。云环境包括一个数据中心，由N个异构物理节点组成。根据CPU的不同处理能力，物理节点划分为两种类型，表示为(1 800 MI/s, 2 600 MI/s)。两种类型物理节点均包括两个CPU内核、4GB RAM和1GB/s网络带宽。每个VM请求一个CPU内核，性能需求分别为2 500、 2 000、1 500、500 MI/s, RAM为0.8、1.7、1.5、0.6GB，带宽为100 MB。每个VM运行一个Web应用或其他类型可变负载的应用任务，可建模形成为均匀随机分布的CPU利用率。应用任务的计算量为150 000 MI，等同于250 MI/s的CPU在100%利用的状态下运行10 min。初始状态下，所有VMs根据资源请求特征按100%利用率进行分配。实验中模拟实现了以下4种VM部署策略进行性能分析：

STA(Single Threshold Algorithm)，单门限值算法。

DVFS(Dynamic Voltage and Frequency

Scaling)[12]，动态电压/频率调整算法。

MPA(Maximum Power Algorithm)，最大功耗算法。

VMPA-VMMSA，本文提出的能效算法。

实验结果的评价指标包括：

TEC(Total Energy Consumption)，总能耗。

SLAV(SLA Violations)，SLA违例。

VMMN(VM Migration Number)，VM迁移数量

ANAS(Average Number of Active Servers)，平均活动服务器数量

实验1观察算法在以上4项性能指标上的情况，结果如图7～10所示。图7是算法得到的总能耗情况，可以看出，MPA消耗了最多的能耗，由于该算法在所有物理服务器上均保持100%的CPU利用率，并未考虑VMs的部署问题。DVFS可以根据CPU利用率动态调整其电压和频率状态，从而降低节点功耗。STA通过设置服务器利用的上门限值，并以此为限制进行VMs部署，保持服务器的总利用率在该门限值以下。然而，STA可能导致低载服务器。不同于STA，VMPA-VMMSA算法通过上下门限的双门限值方法可以实现VMs合并。当服务器利用率低于下门限时，该服务器上的所有VMs需要迁移至其它服务器，并关闭该服务器，进而降低总体能耗。图8中，DVFS和MPA拥有更小的SLA违例，由于这两种算法中请求的资源量等同于分配的资源量。VMPA-VMMSA拥有比STA更小的SLA违例，由于双门限值方法更加有效，它可以激动更少的物理主机。但在图9中，VMPA-VMMSA拥有更高的VMs迁移量。基于类似的理由，本文所提的算法利用了更少的活动物理服务器，如图10所示。

图7 总体能耗图8 SLA违例

实验2观察双门限值对性能的影响，结果如图11、12所示。当上门限值增加时，总能耗将减少，由于此时更少的服务器被激活使用。同时，这将导致更多的VMs合并和更多的SLA违例，如图12所示。下门限值对性能的影响幅度相对较小，但其趋势与上门限值的改变是类似的。

图9 VM迁移量图10 平均活动物理服务器数量

图3观察单门限与双门限方法的性能，结果如图13所示。由于单门限值仅设置上门限以确保服务器不出现过载情况，这将导致可能出现低载服务器和更多的额外能耗。双门限值方法可以通过设置下门限值和VM迁移的方法合并VMs减少活动服务器数量，进而降低能耗。同时，双门限值可能拥有比单门限值方法更高的SLA违例。

实验4观察双门限值方法中上下门值的间隔大小对算法性能的影响，结果如图14所示。

可以看出，下门限值的增加将导致SLA违例的增加。同时，对于相同的下门限值，上门限值越高，能耗越小，SLA违例越高，这是因为上下门限值间的间隔越大，将导致要通过VM迁移进行更多的VM合并，以得到更少的活动服务器。

7 结 语

利用动态迁移和切换节点至睡眠萨尔动态虚拟机合并技术可以使云资源提供者优化资源利用和降低数据中心能耗。然而，向用户提供高可靠QoS，实现能耗与性能的平衡也是必不可少的，由于激进的合并策略可能导致应用执行性能的下降。为了解决这一问题，提出了一种自适应的虚拟机部署算法。新算法能够实现动态的虚拟机合并与迁移以降低能耗，同时确保高等级的SLA，并降低虚拟机优化部署过程中的迁移量。仿真实验结果表明该算法是有效可行的。