基于多目标优化的虚拟机部署策略

刘 军, 代福成, 辛 宁

(1. 东北大学 计算机科学与工程学院, 辽宁 沈阳 110169; 2. 中国空间技术研究院 通导部, 北京 100000)

如何高效进行虚拟机部署与管理是云数据中心性能保障的主要问题之一[1].虚拟机部署(virtual machine placement,VMP)是指将虚拟机(virtual machine, VM)分配至物理服务器(physical server, PS)的过程.其可以理解为在云数据中心利用虚拟化技术把PS的资源抽象为对应的虚拟资源,再被分配到相互独立的VM上的过程.不同的部署策略会导致VM请求最终映射到不同的PS上,从而直接影响VM性能、系统的资源利用率和负载均衡值等多个指标.通常,VM部署后可以通过是否满足相应的服务等级协议(service-level agreement, SLA)来衡量部署结果,本文将其表述为VM性能.此外过高的资源占用会导致SLA违例和PS负载不均衡,而资源利用率过低又会导致大量的资源浪费和能源消耗.因此,本文针对VMP过程提出改进的深度强化学习算法与聚类算法来优化这些指标,在智能化完成VMP过程时,将优化目标及目标占比,以及资源状态同时输入预测器,从而输出最优的部署决策,并加入多维信息的反馈,每一维信息代表一个优化的目标,从而可以兼顾多个优化目标,另外为了更快地完成部署,对资源池中的PS利用改进后的均值聚类算法进行处理,减少不必要的搜索时间.

1 相关工作分析

针对VMP问题,当前学者提出了不同的算法来优化不同的目标.Gharehpasha等提出了一种将正余弦算法与蚁群算法相结合的VMP策略,其目标是通过平衡活跃服务器的数量来最小化云中的功耗和减少资源浪费[2];Azizi等提出了一种贪婪随机虚拟机部署算法,通过将VMP部署在更节能的PS上同时优化系统能耗和资源利用率[3]; Fang等提出了一种改进蚁群优化算法,同时平衡物理机之间的负载和物理机内部的负载[4].Han等基于马尔科夫模型动态部署虚拟机来减少能源消耗[5].另外,启发式算法也可以作为VMP问题的求解方法,例如以最小化能耗为单目标的VMP可以利用群智能算法:蚁群算法[6-7]、粒子群算法[8]、模拟退火算法[9]、遗传算法[10-11]等求解.为了解决多目标的VMP问题,Gaggero等通过模型预测控制来设计虚拟机和物理机之间的最优映射,实现云资源的服务级别、能源占用、硬件或软件中断以及安全策略多个目标之间的权衡[12].Zhao等提出在满足虚拟机可靠性的前提下尽可能地降低能源消耗的VMP算法[13].Liu等针对基于度量和仿真的调度算法代价大、耗时长的特点,提出了一种自适应的调度算法评价方法,该方法只对不同调度算法的奖励函数进行了修改,不需要重构过程,可以量化调度算法对服务质量和运行成本的影响[14].Alresheedi等将鱼群算法和正余弦算法相结合实现多目标优化,目的是尽可能地加长PS的开机时间,同时降低功耗,并最大限度地减少违反服务协议的情况[15].然而,一方面目前大多数VMP算法的研究都是基于某约束下的单目标优化,未考虑复杂环境中部署策略的设计需要同时考虑多个目标；另一方面目前的多目标部署算法通常是将多目标按权重进行线性组合作为目标函数,一旦环境变化,不能短时间内快速优化某个特定的目标,不适用于动态变化的环境.

因此,为了解决动态变化环境中VMP的多目标优化问题,本文提出一种基于强化学习算法(deep Q network,DQN)和均值聚类的VMP(K-means and DQN-based virtual machine placement, KDQNVMP)策略,首先提出改进K-means算法对资源池中的PS按照资源属性进行聚类,然后提出一种基于强化学习的VMP多目标优化算法(DQN-based virtual machine placement, DQNVMP),该算法将强化学习算法的奖励由单一信号改为多维目标组成的向量形式,同时设定目标占比向量决定每个优化目标的权重,其中占比由资源池状态反馈决定;本文将优化目标设定为VM性能、资源利用率和负载均衡值,利用改变目标占比来达到动态优化多目标的目的,从而解决动态环境下VMP多目标优化问题,与现有算法不同的是本算法可以针对性地改变多目标占比来适应环境的变化.

2 VMP数学模型

本文主要解决VMP过程中的多目标优化问题,为了更好地描述所提出的DQNVMP算法,下面进行数学上的描述.

本文假设数据中心(data center,DC)由N个PS组成:

DC={PS1,PS2,…,PSN} .

(1)

每一个PS表示为计算资源R1、内存资源R2、存储资源R3的集合:

PSt={R1,R2,R3} .

(2)

虚拟机VMs请求序列由M个VM生成请求组成:

VMs={VM1,…,VMM} .

(3)

每个VM请求表示为对计算资源E1、内存资源E2、存储资源E3的需求集合:

VMj={E1,E2,E3} .

(4)

VM性能vmp可以用来衡量生成VM是否符合要求,定义为需求值与实际提供值之间的欧氏距离:

(5)

资源池的资源利用率r_utiltotal是指VMP完成后实际使用的资源和总资源的比值.每一种资源定义见式(6),总资源定义见式(7):

(6)

(7)

其中:r_utilRp表示资源Rp的资源利用率;usedRp表示当前资源Rp使用量;totalRp表示资源Rp的总量.

资源池的负载均衡度r_blb是指VMP完成后系统中的每一个PS的资源利用率与均值的偏差程度,每一种资源定义见式(8),总体定义见式(9):

(8)

(9)

基于上述的数学模型,本文所提出的KDQNVMP算法主要解决在M个VM请求映射到N个PS的过程中,随着资源的动态变化,同时优化vmp,r_utiltotal,r_blb等多个目标的问题.

3 VMP策略设计

本文所提出的VMP策略KDQNVMP主要包括两部分:优化K-means算法和DQNVMP算法,如图1所示.首先利用优化均值算法对PS资源在逻辑上进行聚类,形成包括:计算资源、内存资源、计算内存资源、计算存储资源、存储资源等集群,然后利用提出的DQNVMP算法对VMP请求进行分配资源,完成VMP请求到PS的映射.

图1 KDQNVMP部署策略结构图

3.1 服务器资源预处理

VMP过程可以理解为每个VM根据自身的资源需求寻找目标PS的过程.由于不同PS之间资源属性的差异,对于特定的VM资源请求,并不是所有的PS都可以满足;而聚类的过程可以按照相似度将同一类PS聚合在一起,产生一系列资源簇.此外,本文引入了强化学习算法,空间的范围会直接影响算法训练的时间以及完成部署的时间,因此,在资源池中按照PS的资源类型进行聚类会极大地优化本文的DQNVMP算法.

在聚类算法选取方面,本文使用K-means聚类算法将资源类型划分为若干资源簇.在原始K-means算法中,聚类中心是根据样本点之间的距离进行确定的,这样随机确定的第一个样本点就会对结果造成不稳定的影响,此外由于噪声点的存在也会导致最终的聚类结果不准确.因此,本文提出了改进思路:首先根据样本的相似性距离定义每个样本的密度属性,然后选取密度值最大的样本点作为聚类中心,最后根据密度和距离选取其他聚类中心.在聚类中心更新时,根据密度属性确定孤立点,将孤立点的权重降低,避免孤立点对集群聚类中心的更新影响,然后进行聚类,最后得到满足一定误差条件的聚类结果.具体改进方式如下.

1) 初始聚类中心优化.在传统K-means算法中,不同的聚类中心选取策略会得到不同的结果,通常情况下,基于距离因素,会选择相聚较远的两个点作为聚类中心,但是这样会受噪声点的影响,导致选取的初始聚类中心变化很大.因此,本文将每个点周围分布的数据点数量作为该点的密度属性,然后在高密度值的区域内按照距离因素进行聚类中心的选取:密度最大的点作为第一个聚类中心,接着在区域内依次选取与已有聚类中心最小距离最大的点作为接下来的聚类中心.聚类中心的数量由下文的适应度函数确定.这样根据样本的密度属性和距离属性的聚类就可以保证聚类结果有着较好的稳定性.其中密度属性定义为公式(10), 距离属性定义如式(11)所示:

D(PSx)={PSp∈DC|dis(PSp,PSx)≤r} ,

(10)

(11)

其中:dis(PSp,PSx)表示PSp和PSx之间的距离;r为阈值半径,其取值为每对数据样本距离的平均值;DC代表数据中心的所有样本集.

2)基于最大适应度函数的k值选择.理想的聚类结果应该是保证类别之间数据相似度最小,类别内部的相似度最大.因此,本文通过定义适应度函数来确定最优的k值,从而获得最优的聚类结果,本文将适应度函数 Fitness 设定为

(12)

(13)

(14)

式中:Dis_out代表类间距;Dis_in代表类内距;a,b为常系数,取值受到样本数量和维数的影响;PSi是第i类的聚类中心元素;dis(PSi,PSj)表示PSi和PSj之间的距离;ni是第i类中的样本数;Si,j是属于第i类的第j个样本.

通过对式(12)分析,可以发现Fitness的取值受k值影响,通过对式(13)和式(14)分析,可以看出随着k值的增加Dis_out和Dis_in的值都在变小,不同的是Dis_out的下降速度要比Dis_in快一些,如果只是用Dis_out与Dis_in的比值表示适应度函数,则结果就是关于k的单调递增函数,无法获得最优解;因此,本文对Dis_in作了线性变换,通过微积分原理可以知道适应度函数就是关于k的单峰值函数,就可以通过实验找出最理想的k值;通过对初始聚类结果的不断调整,最后按照资源属性划分为k个PS集群.对迭代停止条件的确定可以通过簇中变化率小于一定阈值或者一定的迭代次数作为终止,在本文中,考虑到PS的宕机问题对聚类结果的影响,设置一定的迭代次数作为算法的结束条件.

改进后的K-means算法流程图如图2所示.首先,输入资源池中所有PS数据集合,根据式(10)计算所有样本点的密度属性,选择具有最高密度的样本点作为第一个聚类中心,根据式(12)确定满足最优适应度函数的类别数目k,然后依次找出与已有聚类中心距离最远的点,直到确定k个初始聚类中心;然后根据式(11)计算其余样本点与每个资源簇中心的距离,并在每次划归样本点后根据每个聚类簇中所有样本的均值进行样本中心的更新,当算法迭代的次数达到本文设定的阈值时,按照资源属性输出k个不同的PS集群.

图2 聚类算法流程图

3.2 DQNVMP部署算法设计

考虑到VMP过程中,每个VMP是离散的,而且没有固定的部署策略可以参考,需要利用VMP之后的结果来评估VMP策略的优劣,因此,选用强化学习算法中基于值的Q学习算法完成VMP过程,且根据环境数据尺度大的特点,引入了融合神经网络的Q学习算法,即DQN算法,并进一步提出了具有多目标优化特性的DQNVMP算法来更好地完成VMP.三种算法的模型结构对比见图3,DQN算法通过利用神经网络解决了Q学习算法中数据维度和规模过大导致的时空复杂的问题,而DQNVMP算法通过改变网络的输入与输出解决了DQN算法中优化目标单一的问题.与DQN不同的是,在DQNVMP算法中的神经网络的作用不是建立状态和奖励值的关系,而在网络的输入端加入优化目标和优化目标占比,然后训练网络去估计每个动作的优化目标值,从而选择出满足环境变化的最优动作,达到优化多个目标的目的.

图3 Q-learning,DQN和DQNVMP的模型结构对比

DQNVMP算法框架是在强化学习(reinforcement learning,RL)中引入了深度学习(deep learning,DL),其可能带来如下问题:首先是DL需要大量带标签的数据进行神经网络的训练,RL只有单个奖励返回值;其次DL样本独立,RL状态的改变与前一时刻的状态有关;最后DL目标是相对固定的,而RL的代理随着环境的变化而改变动作.因此,如图4所示,DQNVMP算法对此作出如下改进:通过Q-Learning算法使用奖励来构造标签;使用一个全连接神经网络作为当前预测器输出当前F值,使用另外一个相同结构的神经网络作为目标预测器输出目标F值.然后每隔一定时间间隔更新目标预测器的参数,而当前预测器的参数每回合都进行更新.这样就可以有效地利用神经网络解决RL算法在处理大数据量时的空间和时间消耗问题.

图4 DQNVMP算法框架图

在实现算法时,本文使用一个参数化的函数预测器来选择动作,表示为

(15)

at=argmaxa∈AgTF(st,mt,a,g;θ) .

(16)

本文所提的函数预测器F的网络结构如图5所示.输入包括状态s、优化目标m、目标占比g,然后通过神经网络模型预测每个动作的价值,即每个动作带来测量目标值的改变.此外,在选择最优动作时,引入竞争网络结构[16],将预测结果输出分成两路:上路代表动作期望流E(s,m,g),指的是所有动作的价值的平均值;下路代表动作优势流A(s,m,g),用于显示每个动作之间的价值差别.最后,式(17)将动作期望流和动作优势流的和作为每个动作的价值进行输出,根据价值选择最优动作.

P={Pa1,…,PaN}={A1(s,m,g)+
E(s,m,g),…,AN(s,m,g)+E(s,m,g)} .

(17)

其中:Ap(s,m,g)+E(s,m,g)表示动作ap的价值；N为动作空间的维数.

图5 函数预测器F的网络结构

函数预测器F是根据代理收集的经验进行训练的.代理与环境采用ε-greedy策略进行交互,交互过程随着固定的时间步数或者终止事件的发生而结束.过程中代理将收集到的大量经验存放在经验池D中,然后每一次从经验池中随机取出部分样本进行训练,经验池D的定义:

D={si,mi,gi,ai;fi},i=1,…,N.

(18)

其中:si代表状态输入;mi代表优化目标输入;gi代表目标占比输入;ai代表采取的动作;fi是该动作对应的预测值的输出.最后使用回归损失函数进行预测器的训练:

(19)

训练过程就是对预测器输出结果的优化,优化的目标则是目标函数值逐渐达到最小值,这里采用Adam 算法作为优化算法[17].通过训练,神经网络的参数不断更新.当代理搜集到新的经验时,代理使用的训练集和预测集都会发生变化,为了预测结果的稳定性,本文保留M个最近的经验记忆;对于目标占比的设计,在训练时可以采取两种方式:固定目标占比或者随机目标占比;而实际环境中,反馈网络的引入会根据资源池的状态进行调整目标占比.

此外,代理遵循ε-greedy策略,以概率1-Pε贪婪地选取最优动作,以概率Pε随机地选取动作,随机性保证了可以获得比经验更优的动作.故本文将Pε的初始值设置为1,这样代理可以在训练开始阶段寻找更多的动作选择,随着迭代过程的进行,Pε以α的比例下降,在最优的探索与利用平衡点获得Pε的最优值.使得在模型训练的初始阶段,可以有更多的动作空间进行选择,从而不会错过任何最优选择,而在训练一段时间之后,可以根据之前的最优结果减少搜索空间,加快训练.迭代公式:

(20)

DQNVMP算法的伪代码如表1所示:

表1 DQNVMP算法

在预测器F完成训练之后,就可以根据资源池的状态改变奖励目标,部署过程只需将当前资源状态输入预测器,预测器会输出每个VM对应的PS,或者当前VM无法部署.具体流程图见图6,假设数据中心DC中包含N台物理服务器PS,对于M个虚拟机请求的序列VMs,通过本文的部署策略得出所有VM的放置结果:

VMs-PS={w1,w2,…,wM} .

(21)

其中,wi代表虚拟机VMi所部署在PS的编号,对于放置失败的虚拟机,其对应的wi的值为0.

4 仿真实验

本文实验环境为Windows系统,具有8核的CPU和16GB内存的PC机,采用Python语言,基于离散事件仿真框架SimPy搭建数据中心调度仿真框架CloudsimPy,并与深度学习框架TensorFlow相结合进行改进算法的实验结果验证.并与粒子群算法PSO、遗传算法GA以及DQN算法进行比较.参数信息见表2;对于DQN和DQNVMP,神经网络的隐藏层的维度设为400,代理累计奖励值的学习率γ=0.9.设置Pε=1,α=0.95.经过一定次数的迭代后收敛到最优值,从经验池中选取的训练样本规模为150.拷贝周期T=10，经过8 000次迭代后进行测试.假设资源池中含有200台异构PS,并按照HP DL388 Gen10,Lenovo 1288H V5和ThinkSystem SR50 3种类型随机分布,具体配置参数如表3所示.同时为了保证实验结果的真实性,部署请求选取来自阿里巴巴数据集群的2017年的服务请求日志数据.为了使测试结果具有可对比性,这里的智能优化算法和强化学习算法均使用相同的测试数据进行测试.

图6 虚拟机部署流程图

表2 对比算法参数设置

表3 物理服务器配置

为了验证本文优化后的K-means算法的有效性,本文将优化的聚类部署算法与原算法进行比较,结果对比如图7所示.可以看出,KDQNVMP算法的平均完成时间比DQNVMP算法的平均完成时间减少了34.07%,极大地优化了强化学习算法完成虚拟机部署的时间.

图7 虚拟机部署请求的部署时间优化

对于待优化的目标:虚拟机可靠性表示为VM请求资源与获得资源的参数化距离,其值越小表示VM性能越好;资源池资源利用率代表对物理资源的使用情况,其值表示资源是否被充分利用;负载均衡值是指每个活跃PS的资源利用率与均值的差值,其值越小表示越接近均衡.为了便于观察,对所有目标值进行归一化处理见式(22),使最后指标值处于[0,1]之间.

(22)

图8为DQNVMP算法优化目标随着迭代次数的变化情况,在开始迭代的时候将待优化目标占比设置为g=[虚拟机性能,资源利用率,负载均衡值]=[1,0,0];随着迭代过程的进行,资源池的状态在不断改变,优化目标也在不断变化;从图中可以看出,由于开始时设定的唯一优化目标是VM性能,因此虚拟机可靠性的值在不断缩小,说明虚拟机性能在不断提升,部署的虚拟机多数为成功的;但是,由于未将利用率和负载均衡看作优化目标,二者的值都没有得到很好的优化.当迭代3 000次以后,资源利用率的值降低到了一定的程度,此时通过反馈,会将优化目标占比调整为g=[0.5,1,0],从图中可以看到资源利用率的值在不断地优化,直到4 000次迭代时,由于系统的负载均衡值过高,说明虚拟机分配不合理,此时通过反馈调节将优化目标占比设定为g=[0.3,0.5,1],可以发现4 000次以后,系统的负载均衡值在不断地缩小,说明PS之间的差异在减少,有很好的负载均衡;在以后的迭代过程中,会根据要求进行目标占比调整,在5 000次迭代之后,可以看出,系统中的3个指标都相对趋于稳定,说明此时在执行VMP时已经可以同时优化多个目标.在实际环境中,如果没有明确的要求,系统会动态地调整目标占比的值,达到动态平衡及优化多目标的目的.如果需要优化某种特定目标,只需要改变目标占比向量即可.

图8 优化目标值随迭代次数的变化情况

图9为KDQNVMP算法与其他算法在服务器数量一致时,部署成功率随虚拟机请求数量变化的对比图,其中部署成功率是指成功部署的虚拟机请求数与已提交虚拟机请求总数的比值.从图中可以看出,KDQNVMP算法成功部署的虚拟机数量较其他算法多,这是由于在KDQNVMP算法中,虚拟机的可靠性和资源利用率作为动态优化目标,代理会根据资源池的变化动态调整优化目标,进而使得更多发送请求的虚拟机被成功部署.

图10表示在相同的任务序列的前提下,同样的服务器数量不同部署算法的最大可完成任务数量对比图.图中记录连续任务失败的阈值为最大可部署虚拟机数量,这样就可以避免单个任务失败导致的数据错误.从图中可以看出KDQNVMP算法较其他算法可以部署更多的虚拟机请求,这是由于导致部署失败的原因是资源不足以满足虚拟机的请求值,而KDQNVMP算法中,将资源池资源利用率和各个服务器的负载均衡作为优化目标,极大地减少了资源碎片带来的资源浪费问题,从而部署了更多的虚拟机.

图9 虚拟机部署成功率随虚拟机部署请求数量的变化

图10 最大虚拟机部署数量随服务器数量的变化

图11为不同虚拟机请求数量下各个算法的部署完成时间的对比图.从图中可以看出,随着虚拟机请求数量的增加,KDQNVMP算法的部署速度较其他算法更快,这是因为随着数量的增加,学习代理可以掌握更完善的模型,从而在保证优化目标时,保证部署速度的执行,此外,聚类之后对搜索空间进行了减小,也极大优化了训练速度.综上,可以发现通过不断地改变不同目标的占比可以很好完成多目标的动态优化.在KDQNVMP算法中,通过反馈资源池的状态,计算出此时的多个优化目标值,并调整目标占比,可以达到同时优化多目标的目的.对于有特定需求的任务请求,也可以根据任务的要求进行目标占比设定,从而达到部署结果的最优化.

图11 虚拟机部署时延随虚拟机部署请求数量的变化

5 结 语

基于聚类算法和强化学习算法提出了适合VMP的KDQNVMP策略,重点解决了VMP过程中保证部署速度的同时对VM可靠性、资源池利用率和负载均衡值等多个目标的优化问题.与其他算法进行对比,该算法在完成多目标优化时能够同时优化VM性能、资源利用率和负载均衡值,从而在VMP完成时间、VM请求部署成功率和最大可部署VM数量方面较其他算法都有所提高.由于该智能算法可以由代理进行自主决策,根据资源池环境的变化动态地改变优化目标.所以,在应用该算法时,只需要给定环境奖励,智能体就可以自主地寻找最优策略.此外,对于强化学习算法而言,环境的复杂度越高,优化的目标越多,代理就可以更好地完成动作的训练,从而获得最优的结果.故本文所提出的基于动态目标优化的强化学习策略在解决其他复杂目标优化问题时具有可以针对多目标中的单目标快速优化的优势.