IaaS云融合Q学习的自适应虚拟机部署

宋建松，连 玮，陕粉丽，闫慧鹏

(1.长治学院 计算机系，山西 长治 046011；2.中国电信集团有限公司 长治分公司，山西 长治 046011)

0 引 言

虚拟化是云数据中心的主要技术，利用虚拟化可以在物理服务器上部署不同性能的虚拟机，提高资源利用率[1]。虚拟化的主要优势是在数据中心内可以进行动态虚拟机合并来降低能耗，通过将虚拟机部署到更少物理主机上，将闲置主机转换为睡眠以提升能效。动态虚拟机合并实现了运行时虚拟机在不同主机间的在线迁移[2]，尤其在主机处于低负载或超载状态时，迁移将具有诸多好处。因此，通过迁移会使得数据中心的资源管理更加灵活。然而，虚拟机在线迁移对于运行在虚拟机上的任务具有负面影响[3]。由于在云服务提供者与其用户间提供相应服务质量至关重要，所以动态虚拟机合并应该着重考虑优化虚拟机迁移量。

很多算法通过装箱算法求解虚拟机部署问题，但会产生过多非必要迁移，增加SLA违例。比较已有工作最小化活跃主机量，本文设计一种基于Q学习的虚拟机部署算法，同步最小化虚拟机迁移量和SLA违例。所提算法由两个阶段组成，第一个阶段目标是从超载主机上迁移虚拟机，避免SLA违例；第二个阶段目标是合并非超载主机的虚拟机。为了预测负载，设计了一种Q学习机制的预测方法，对未来资源利用率进行有效预测。实验部分通过运行云环境中的两种现实负载流对算法进行评估，验证了该算法在优化能效、提升性能和降低虚拟机迁移量上的优势。

1 相关工作分析

目前，很多方法已被提出用于求解多目标优化的资源管理问题，在IaaS云提供方与其用户间维持需要的QoS等级是当前云资源管理的最主要目标之一。基于这一考虑，多数已有算法利用静态利用率阈值预防服务性能的下降。文献[4]利用一个上限值避免主机CPU的利用率达到100%，从而导致性能降低。文献[5]设计的虚拟机部署算法将主机CPU利用率维持在静态上限与下限值之间。文献[6]利用静态CPU阈值发现数据中心内的低载和超载主机。静态阈值设置虽然具有简单性，但在动态的云负载环境中，不同类型的应用负载运行在一台主机上，静态阈值不切实际。因此，利用率阈值应用根据负载类型的不同做出相应调整，并以此执行有效的虚拟机优化部署。文献[7] 根据历史数据的统计分析设计多种CPU阈值的预测方法，在当前的主机CPU利用率超过上限值的基础上，通过虚拟机部署算法实现虚拟机迁移。然而，该算法仅考虑了当前的资源请求，忽略了未来的资源请求，此时得到的阈值会无法反映当前的负载状况。因此，该过程会产生过多非必须的虚拟机迁移，进而增加数据中心内SLA违例的风险。

本文设计了IaaS中的一种自适应的多层次资源管理系统SARMS，在此系统的基础上，主要做了以下工作：

(1)利用Q学习机制设计了一种自适应利用率阈值AUT机制动态调整资源利用率阈值。不同于现有工作仅仅考虑CPU利用率，AUT同步考虑了CPU资源和内存资源利用率。结合两类资源阈值，SARMS系统可以更好识别SLA违例并对其进行预防。

(2)在SARMS系统内设计了一种虚拟机部署优化算法可维持主机利用率在自适应阈值以内，以避免SLA违例；同时，算法可以将虚拟机合并至最小数量的活跃主机上，以降低数据中心内的整体能耗。

(3)利用Google负载和PlanetLab负载两种现实数据流在模拟云环境中对算法性能进行评测，评估了Q学习机制下对利用率阈值自适应调整的有效性，并与其它阈值算法在整体能耗、SLA违例比例以及虚拟机完成的迁移量进行了系统比较，体现了本文算法的性能优势。

2 系统模型

考虑数据中心由m台异构物理主机构成，表示为PM={PM1,PM2,…,PMm}。 每台物理主机拥有D类资源属性，包括CPU、内存、网络I/O和存储能力。多台虚拟机VM可以通过虚拟机监视器VMM部署在一台主机上。初始时，虚拟机根据降序最佳适应启发式方法BFD部署在虚拟机上。在任意给定的时间，用户发送n台虚拟机的请求，表示为VM={VM1,VM2,…VMn}， 部署在物理主机上。由于虚拟机和主机的请求资源利用率会随着时间发生改变，云资源管理系统需要根据资源请求控制物理和虚拟资源分配。基于此，本文设计了一种基于分层的自适应资源管理系统，如图1所示，将系统命名为SARMS。系统由3层拓扑结构组成，最低下的访问层由物理主机构成，主机由机架顶层ToR交换机连接。中间层为聚合层，主机集群通过聚合交换机AS连接在不同的模块中。最高层为核心层，通过AS和核心交换机的安全连接至互联网。

图1 系统模型

SARMS体系将云资源管理问题划分为跨层的多代理模型，每个代理求解一个子问题。因此，可将其视为多代理的分布式资源管理系统。系统一共由4类代理构成。在核心层，全局代理GAs接收用户的虚拟机请求，并将其派发至聚合层中的不同模块代理MAs。每个MA根据来自于CAs的接收信息(包括集群中已经利用和总体资源能力)将虚拟机VM请求分派至集群代理CAs。每个CA接收来自于MA的请求并分配请求至集群的本地代理LAs。同时，数据中心内为了降低SLA违例和降低能耗，需要周期性运行虚拟机部署优化算法。每个LA监测一台主机，根据自适应利用率阈值AUT机制发现该主机的超载或非超载状态，并将其报告至集群代理CAs。LAs、CAs和MAs的数量则分别对应于主机、ToRs和CSs的数量。

3 自适应虚拟机部署算法设计

3.1 假设条件

数据中心内，每台主机PMi拥有一个d维总能力矢量，表示为CPMi={C1,PMi,C2,PMi,…,Cd,PMi}， 其中，Cd,PMi表示PMi的d维资源总能力。每一维度对应一种物理资源，如：CPU能力、内存、网络I/O和磁盘存储。PMi利用的能力矢量表示为UPMi={U1,PMi,U2,PMi,…,Ud,PMi}， 其中，Ud,PMi表示PMi的d维资源已利用能力矢量。如：若3台虚拟机VM部署在一台主机上，则主机PM已利用的CPU能力为3台虚拟机的CPU利用率之和。PMi的负载为每个个体资源d∈D的资源利用率Rd,PMi之和，表示为

LoadPMi=RCPU,PMi+Rmem,PMi

(1)

其中，Rd,PMi表示主机PMi已利用资源Ud,PMi与其总资源能力Cd,PMi之比，表示为

Rd,PMi=Ud,PMi/Cd,PMi

(2)

需要说明的是：云数据中心内，相比网络资源和磁盘存储资源，CPU资源和内存资源是相对更为受限的资源，因此本文仅考虑了这两类资源的限制。但以现有模型将其扩展至另外两种资源上，也是比较容易的，不会对虚拟机部署决策的性能表现产生反转式影响。

虚拟机VMi的负载定义为

LoadVMi=RCPU,VMi+Rmem,VMi

(3)

式(3)表明，虚拟机上的负载为其请求的CPU和内存负载之和。相应地

Rd,VMi=Ud,VMi/Cd,VMi,d=CPU,mem

(4)

式中：Rd,VMi表示VMi请求的d维资源利用与VMi的d维资源消耗的比率，d指CPU或内存mem资源。式(4)表明，某一维度资源上的资源请求应为虚拟机上资源消耗与资源能力之比。

3.2 主机超载状态发现

本地代理LAi利用资源利用率自适应阈值AUT机制发现每台物理主机PM的状态。若CPU或内存利用率超过自适应阈值，则将PMi考虑为超载集合Pover中的成员；否则，可将其视为非超载集合Pnonover中的一个成员。由于负载的动态变化，自适应阈值Td,PMi需要根据当前负载状况在每个资源维度上进行调整。为了解决该问题，AUT利用Q学习方法在线从当前环境中学习经验，并利用该经验知识寻找每个阈值的自适应值。Q学习机制在对环境无先验知识的前提下提供了一种自适应机制。在Q学习机制中，LAi首先观测环境的当前状态s，然后在当前时槽t中执行一个行为a。定义AUT机制中的状态s为 (RCPU,PMi,Rmem,PMi)，RCPU,PMi和Rmem,PMi分别表示主机PMi的CPU利用率和内存利用率。

根据观测状态s，LAi选择一个利用率阈值Td,PMi={0.5,0.6,0.7,0.8,0.9} 作为每个d维度资源上的行为a。由于在PM的利用率接近于100%时，可能导致SLA违例的风险，本文将资源利用率限制在90%以内。在Q学习过程的初始阶段，LA执行一个确定的搜索行为，此时随机选择一个行为。然后，LAi根据其经验(搜索)选择一个行为。

在下一个时槽t+1的开始阶段，环境行为转换为一个新的状态s’，LAi根据加强信号改进其知识。该信号可以反映行为发生后系统的成功或失效。本文将信号考虑为本地惩罚值、集群和模块惩罚值之和。由于LAi执行行为a时需要支付惩罚值，LAi在学习期间需要最小化其平均长期惩罚值。每个惩罚值即为所设计系统每一层次中的目标函数，该目标函数决定了代理行为对于性能和功耗的综合影响。

本地惩罚值LPi表示本地代理i决策行为对于主机PMi的功耗和性能影响。由于该惩罚值由LA计算，因此将其称为本地惩罚值。由于将PM转换为节能模式会降低其性能等级，故AUT需要在功耗和性能间做出均衡考虑。因此，引入一个多目标函数LPi(SLAV,POW)， 将功耗和性能均考虑在内，并利用该函数给出在RL上的惩罚值。性能需求可形式化为服务等级协议SLA，而主机PMi的SLA违例SLAVt+1,PMi即为时槽t+1时所有虚拟机的请求资源与实际分配的资源之差。时槽t+1时的本地惩罚值可定义为SLA违例SLAV与主机PMi的总功耗POW的线性函数

LPi(SLAV,POW)=SLAVt+1,PMi+β×POWt+1,PMi

(5)

其中，β为权重因子，代表功耗目标与性能目标间的关系。

集群惩罚值CPj,i从集群代理j发送至本地代理i。该惩罚值代表本地代理i的行为决策对于同一集群中其它主机PM的影响。因此，集群惩罚值是除了LPi之外的集群j的本地惩罚的均值。此外，本地代理i可以得到集群中总体的性能与功耗

(6)

其中，Y表示集群j中本地代理的数量。

CAj接收来自模块代理z的模块惩罚值MPz,j， 该惩罚值表示除了其集群惩罚值之外的模块内的其它集群的惩罚值，定义为

(7)

其中，X表示模块z中的集群代理的数量。

最后，LAi更新一个Q值Qt+1(s,a)， 该值通过总体惩罚值Pt+1,i与相应的行为-状态对相联系，即总体惩罚值为本地惩罚值LP、集群惩罚值CP和模块惩罚值MP之和

Pt+1,i=LPi+CPj,i+MPz,j

(8)

(9)

其中，α表示学习率，取值空间为0至1之间，若取值为0，表明算法没有发生学习行为，若取值为1，则表明仅仅利用了最近的信息来学习。折扣因子γ取值0至1之间，给出近期未来和远期未来的惩罚权重。Qt+1(s,a) 表示状态s时行为a导致的期望功耗。因此，本地代理在再次观测到状态s时将选择使得Q值达到最小的行为。

3.3 虚拟机部署最优化算法过程

为了降低SLA违例和物理主机能耗，每个集群代理均需要周期性运行算法1如示的虚拟机部署最优化算法，该算法通过两个阶段创建虚拟机迁移计划M。

在第一个阶段中，即步骤(1)～步骤(22)，算法目标是从超载主机上迁移部分虚拟机以避免可能的SLA违例。迁移虚拟机时选择的是拥有最小迁移时间的虚拟机优先迁移，迁移时间计算为分配至虚拟机的内存除以源主机与目标主机间的可用网络带宽。算法首先对源主机pso上的虚拟机按其利用的内存能力进行降序排列(所有网络带宽均设置为1 GBps)，即步骤(3)，然后，开始按序迁移虚拟机直到源主机PM仍被考虑为超载集合Pover中的一个成员，即步骤(4)～步骤(5)。为了寻找重新分配迁移虚拟机v的合适目标主机pde，算法优先考虑的是集群中非超载主机集合Pnonover，即步骤(7)～步骤(12)。若虚拟机和主机的整体资源利用率低于自适应阈值，则该PM被选择为目标主机pde，即步骤(8)。若算法在同一集群内无法找到目标主机pde，则将该请求发送至模块代理，在其它集群内寻找，即步骤(13)～步骤(15)。若活跃状态的主机没有足够的资源部署迁移虚拟机v，则算法重新开启一台休眠主机进行部署。最后，新的虚拟机部署被添加至迁移计划M1中，即步骤(16)。迁移计划是一个三元组集合，表示为 (pso;v;pde)，pso表示源主机，v表示迁移的虚拟机，pde表示目标主机。步骤(17)对源主机和目标主机的资源利用率进行更新。

在第二个阶段中，即步骤(23)～步骤(45)，算法目标是合并非超载主机上的虚拟机。首先基于当前负载按降序排列非超载主机集合Pnonover内的主机，即步骤(24)。然后，从列表中的最低载主机开始遍历，将其考虑为一个源主机pso，即步骤(25)～步骤(26)。算法尝试迁移其上的所有虚拟机，以便释放源主机pso。为了选择从pso上优先需要迁移的虚拟机，算法根据其负载按降序对pso上的虚拟机进行排列，即步骤(27)。算法从集合Pnonover中的第一个主机(负载最重主机)开始遍历寻找目标主机pde，即步骤(30)。若第一个主机不满足，则选择第二个主机，依此类推。算法选择的目标主机pde需要在考虑阈值的情况下拥有足够的虚拟机请求的资源能力，即步骤(31)。最后，新的虚拟机部署被添加至迁移计划M2中，即步骤(32)。步骤(33)对源主机和目标主机的已利用资源能力进行更新，以反映出新的虚拟机部署结果。变量success定义为检测是否来自于源主机pso上的所有虚拟机能够完成迁移。若有一个虚拟机无法完成迁移，则全部不迁移。此时，success=false，算法将移除迁移计划中的所有三元组，并恢复源主机和目标主机的资源能力，即步骤(39)～步骤(41)。否则，在其上的所有虚拟机迁移后，空闲源主机pso将转换为休眠状态，即步骤(42)～步骤(44)。算法的输出为迁移计划M，包括了在第一阶段和第二阶段中生成的所有迁移三元组，即步骤(46)～步骤(47)。最后，集群代理根据迁移计划M将迁移指令发送至集群的本地代理，执行具体的虚拟机迁移。

算法1： 虚拟机部署最优化算法

(1)M1=null

(2)forpso∈Poverdo

(3)Vm←sort VMs onPMpsoin ascending order ofUmem,v

(4) forv∈Vmdo

(5) ifpso∈Poverthen

(6)pde=null

(7) forp∈Pnonoverdo

(8) if (RCPU,p+RCPU,v≤TCPU,p)&(Rmem,p+Rmem,v≤Tmem,p)

(9)pde=p

(10) break

(11) end if

(12) end for

(13) ifpde=null then

(14) send a request to the module agent to findpde

(15) end if

(16)M1=M1∪{(pso,v,pde)}

(17) updateRpsoandRpde

(18) else

(19) break

(20) end if

(21) end for

(22)end for

(23)M2=null

(24)sortPnonoverin descending order ofLoadp

(25)fori=|Pnonover| to 1 do

(26)pso=Pnonover[i]

(27)Vm←sort VMs onPMpsoin descending order ofLoadv

(28) forv∈Vmdo

(29)success=false

(30) forpde∈Pnonover-psodo

(31) if(RCPU,pde+RCPU,v≤TCPU,pde)&(Rmem,pde+Rmem,v≤Tmem,pde)

(32)M2=M2∪{(pso,v,pde)}

(33) updateRpsoandRpde

(34)success=true

(35) break

(36) end if

(37) end for

(38) end for

(39) ifsuccess=falsethen

(40)M2=null

(41) recoverRpsoandRpde

(42) else

(43) switchpsoto the sleep mode

(44) end if

(45)end for

(46)M=M1∪M2

(47)returnM

3.4 虚拟机分配

虚拟机分配需在SAMRS中的3层结构中得以求解，最低下的访问层由物理主机构成，主机由机架顶层ToR交换机连接；中间层为聚合层，主机集群通过聚合交换机AS连接在不同的模块中；最高层为核心层，通过AS和核心交换机的安全连接至互联网在核心层和聚合层。具体分配流程是：首先，全局代理和模块代理通过运行BFD算法先将虚拟机分配至模块，然后分配虚拟机至集群。BFD算法根据当前的虚拟机负载状况的降序对虚拟机进行排列，其目标是：如果模块或集群拥有足够资源能力分配至虚拟机，则将负载最轻的虚拟机分配至负载最重的模块或集群中。最后，在访问层，如果某主机拥有足够的CPU和内存能力在当前自适应阈值的前提下部署虚拟机，同集群代理会将每个虚拟机分配至该主机上，即算法1中的步骤(8)。因此，这样可以限制虚拟机请求的资源量在自适应度阈值以内，进而最小化可能的性能下降。

4 仿真实验

4.1 测试负载说明

利用两种现实负载流测试虚拟机部署优化算法，包括：Google集群数据GCD[8]和PlanetLab数据[9]。GCD提供的是集群系统中某一个月内的负载流数据。该负载流涉及12 000 台异构主机上的650 k个任务。每个任务代表一个Linux程序，其中包含了在CPU(内核占用秒数)、内存、磁盘存储空间等资源上的请求。每类资源的利用以5 min作为时间间隔进行收集。利用任务ID对任务进行标识，CPU和内存属性分别考虑为CPU速率和内存量的利用。PlanetLab数据为CoMon工程的一部分，该工程中，CPU和内存利用数据从数以千计的虚拟机中每5 min收集一次。该负载流是一种典型的IaaS云环境负载流，如典型的Amazon EC2。GCD和PlanetLab中虚拟机的负载所对应的CPU和内存占用属性见表1。

表1 测试负载流属性

4.2 仿真环境搭建

为了测试算法效率，在云仿真平台CloudSim[10]中进行仿真实验。表2给出了针对两种测试负载流的相关参数配置。模拟云数据中心由若干台异构物理主机构成，一半主机配置为HP ProLiant ML110 G4服务器，每个内核1860 MIPS，另一个主机配置为HP ProLiant ML110 G5服务器，每个内核2660 MIPS。每个主机配置两个内核，4 GB 内存和1 GBps的网络带宽。虚拟机实例的CPU和内存属性参考Amazon EC2在平台中设置，即：High-CPU中等实例(2500 MIPS,0.85 GB)，越大实例(2000 MIPS,3.75 GB)，小型实例(1000 MIPS,1.7 GB)，微型实例(500 MIPS,613 MB)。α和γ(Q学习因子)分别设置为0.5和0.8。

表2 仿真环境参数配置

4.3 评估指标

(1)SLA违例SLAV指标。SLAV是一种独立的负载指标，用于评估虚拟机部署中SLA的交付情况。SLAV包括主机超载导致的SLA违例SLAVO和由于迁移导致的SLA违例SLAVM。对于云环境中的虚拟机合并问题而言，两种SLA违例具有同等的重要性，因此，综合的SLA违例指标可考虑为两个参数的乘积，表示为

SLAV=SLAVO×SLAVM

(10)

其中，SLAVO表示活跃主机经历CPU利用率100%所占的时间比例，表示为

(11)

其中，M表示主机数量，Tsi表示主机i经历的CPU利用率100%(导致SLA违例)的总时间，Tai表示主机i活跃状态的总时间。

SLAVM表示由迁移导致的虚拟机性能下降，度量为

(12)

其中，N表示虚拟机数量，Cdj表示由于迁移导致的虚拟机j性能下降的估算。仿真实验中，该估算值一般设为虚拟机j在所有迁移过程中以MIPS计算的CPU占用的10%，Crj表示整个周期中虚拟机j的总CPU请求量。

(2)能耗指标。该指标表示数据中心中物理主机执行负载消耗的总体能耗。主机能耗取决于CPU、内存、存储及网络带宽的利用率。研究表明，相比其它资源类型，CPU消耗了最多能源。因此，简化能耗模型后，主机能耗可表示为其CPU利用率的关系式。实验中根据SPECpower实验床中现实的功耗数据。表3给出了在不同的负载条件下两类主机HP G4和HP G5的功耗情况，从表中可以看出，低载主机转换为休眠后可降低能耗。

表3 不同负载条件下主机的功耗/W

(3)虚拟机迁移量。在线虚拟机迁移涉及在源主机上的CPU处理、源和目标主机间的链路带宽以及迁移时的服务停机、迁移时间等多重代价，因此，虚拟机合并过程中需要最小化虚拟机迁移量。

4.4 对比算法

(1)HiVM算法[11]：该算法利用了基于虚拟机管理方法的利用率预测方法，根据当前和未来的虚拟机资源利用优化了虚拟机部署方案。

(2)MADC算法[12]：基于多代理的动态虚拟机合并算法，该算法是一种双层结构的多代理模型。

(3)3种自适应利用率阈值算法[5]：该类算法首先根据统计学方法动态调整CPU利用率上限阈值，相关统计学方法包括：绝对中位差法MAD、四分位差法IQR和局部回归法LR。通过以上统计学方法确定上限阈值后，若主机的CPU利用率超过此上限值，则虚拟机部署优化根据负载均衡的原则重新进行虚拟机分配。通过与该算法的比较，可以显示本文设计的AUT所使用的Q学习自适应机制与经典统计学方法的性能优势。

(4)静态阈值算法THR[7]：该算法设置CPU阈值为固定值，如80%，当主机当前利用率超过总能力的80%时，则需要从主机上迁移虚拟机。通过与算法的比较，可以显示出自适应阈值设置的优势。

4.5 结果分析

图2给出了利用GCD数据流测试时7种算法在SLAV、能耗以及虚拟机迁移量的性能表现。可以看到，比较另外6种算法，本文可以有效降低SLA违例，这是因为本文设计的虚拟机部署优化算法可以通过AUT机制将主机利用率维持在自适应阈值以内。此外，比较HiVM、MADC、LR、MAD、IQR和THR这6种算法，本文算法可以分别降低13.7%、25.6%、43.3%、59.1%、66.3%和69.4%的能耗，这是由于本文算法可以最小化非超载主机的数量。同时，图2(c)显示出本文算法可以最小化虚拟机迁移量。

图2 GCD负载流的测试结果

图3(a)显示了利用PlanetLab负载流时算法得到的SLAV指标情况，结果表明，本文得到了比基准算法更小的SLA违例，这是由于该算法在CPU或内存利用率超过自适应阈值时会从主机上迁移部分虚拟机预防SLA违例。图3(b)显示本文算法比其它算法也节省了更多的能耗，这是由于算法可以通过运行算法的第二阶段将虚拟机合并至最小数量的非超载主机上。同时，本文算法也可以有效降低虚拟机迁移量，避免了过多非必要的虚拟机迁移。

图3 PlanetLab负载流的测试结果

5 结束语

提出一种基于Q学习机制的自适应虚拟机部署算法。算法利用Q学习机制在无需先验知识的前提下，可以自适应生成资源利用率阈值，根据动态自适应阈值动态地对主机超载状态作出决策，以此判断是否进行虚拟机迁移。通过两种现实负载流数据对算法进行了实验分析。结果表明，与另外6种典型虚拟机部署算法相比，该算法不仅可以降低主机能耗，还可以同步减小虚拟机迁移量和SLA违例率。