基于遗传算法的虚拟机在线迁移优化方法

刘 畅

(国网冀北电力有限公司秦皇岛供电公司 信息通信分公司，河北 秦皇岛 066000)

基于遗传算法的虚拟机在线迁移优化方法

刘 畅

(国网冀北电力有限公司秦皇岛供电公司 信息通信分公司，河北 秦皇岛 066000)

虚拟机在线迁移是云计算研究热点。目前已有的研究工作未能考虑Web应用资源需求的变化规律，可能会存在因虚拟机循环迁移而导致的Web应用性能频繁违约现象。提出一种基于Web应用资源需求变化分析的虚拟机迁移优化方法，以虚拟机资源需求小于物理机资源供给为约束条件，将虚拟机和物理机空间布局的稳定性刻画成收益。每次执行虚拟机在线迁移操作时，都以收益最大化作为待迁移虚拟机和目标物理机的选择依据。实验结果表明，与已有方法相比，本方法能减少超过50%的性能违约次数。

虚拟机；循环迁移；在线迁移；遗传算法

Abstract: VM live migration is a hot topic, and previous work ignores the periodic change of resource requirements for a Web application. It may do VM live migration between two physical machines periodically. In this paper, we propose a benefit-sensitive approach based on analysis of periodic changes on resource requirement. Here, the benefit means the stability in spatial topological between VMs and physical machines. Experimental results based on live workload traces show that our approach can effectively reduce performance violations by as much as 50% compared with previous work.

Key words:virtual machine; cyclic migration; live migration; genetic algorithm

0 引言

虚拟机在线迁移[1-3]是指运行时变更虚拟机内存的物理位置，却不需要重启的一种资源调整技术。它强调的是虚拟机实例的位置变迁，而不是资源总量的改变。虚拟机在线迁移操作具有运行时重新绑定Web应用与物理机关系的能力，适用于Web应用负载动态变化，物理机资源供给无法满足(该物理机上虚拟机资源需求)的场景。其本质是找到虚拟机 (Web应用)和物理机的最佳部署关系，又称为“虚拟机放置”问题。

已有研究工作或忽略虚拟机在线迁移操作对Web应用性能的影响(能耗敏感方法)，或容忍一定程度的Web应用性能违约(迁移代价敏感方法)。除此之外，已有方法通常是以某一时间点的Web应用资源需求作为虚拟机在线迁移的决策依据，在长期负载模式(Time-of-day)下，存在“循环迁移”和频繁Web应用性能违约现象。所谓“循环迁移”[4-6]，即虚拟机i某一时刻从物理机j迁移到物理机k，另一时刻从物理机k迁回物理机j的现象。

针对已有方法不足，本章提出了收益(Benefit-sensitive)敏感的放置优化方法。该方法将虚拟机和物理机空间布局的稳定性刻画成收益，并以收益最大化作为虚拟机放置优化的依据。具体而言，首先将具体Web应用和物理机的空间布局抽象成遗传算法中的个体，将可能的空间布局抽象成遗传算法中的群体。然后，基于收益最大化原则构建遗传算法的适应度函数，适应度最大的个体即为满足约束条件的最优解。实验结果表明，本方法与Energy-sensitive方法和Cost-sensitive方法相比，会多消耗约50%的能耗成本，但能有效减少Web应用性能违约次数。

本文给出了循环迁移现象分析，介绍了放置优化平台的设计。其中，迁移决策是该平台的核心组件，详细描述了基于遗传算法的虚拟机放置优化算法，通过实验验证了本方法的有效性及相关工作介绍。

1 循环迁移现象

在初始条件下虚拟机和物理机的部署关系如下：

(1)三台物理机Server1、Server2和Server3，假设每台物理机配置都是1 vCPU，2 GB内存；

(2)四个TPC-W应用实例，假设实例都部署在配置为1vCPU和1 GB内存的虚拟机上。其中，TPC-W-1、TPC-W-4部署在Server1上，TPC-W-2部署在Server2上，TPC-W-3部署在Server3；

(3)除了CPU资源，假设其他资源不存在瓶颈。

表1给出了应用实例的CPU资源需求分布函数：TPC-W-1和TPC-W-2的CPU资源需求分别符合偏距为60、振幅为10的正弦和余弦分布；TPC-W-3、TPC-W-4的CPU资源需求则分别稳定在50%和40%。

表1 Web应用资源需求分布函数

常用决策算法下虚拟机在线迁移流程：

(1)从第15分钟开始，TPC-W-4应用部署到虚拟化平台中，此时Server1、Server2和Server3的CPU资源空闲率均为50%。因此会采用“随机策略”将TPC-W-4应用部署并运行在Server1上。

(2)从第33分钟开始，TPC-W-1和TPC-W-4的CPU资源需求均为50%， Server1资源供给面临瓶颈，虚拟化平台会触发虚拟机在线迁移操作。会采用“随机策略”选择待迁移虚拟机，假设是TPC-W-4。根据效用理论，已有研究会选择Server3作为目标物理机。因为在第33分钟，Server2空闲CPU资源为50%，而Server3空闲CPU资源为60%，认为物理机CPU空闲率越高，其效用越大。

(3)从第42分钟开始，TPC-W-3和TPC-W-4的资源需求大于Server3的资源供给，虚拟化平台再次触发虚拟机在线迁移操作。同样的原理TPC-W-4被选择成待迁移对象，Server1被选择成目标物理机。因为在第42分钟，Server2的CPU资源空闲率为50%，而Server1为60%。

随着时间的推移，部署TPC-W-4应用的虚拟机会周期性地在Server1和Server3之间进行切换，出现“循环迁移”现象。这是因为虚拟机资源需求小于物理机资源供给的约束条件会周期性违背。

2 遗传算法设计

遗传算法(Genetic Algorithm, GA)是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，该算法具有自组织、自适应、自学习和群体进化功能，有很强的解决问题的能力，在许多领域都得到了应用。

2.1基本流程

遗传算法的基本运算过程如下：

(2)个体适应度评估：计算群体P(t)中个体的适应性，即满足目标约束的能力。

(3)选择运算：将选择算子作用于群体，选择目的是将优良个体直接遗传到下一代。选择操作建立在群体中个体适应度评估的基础上。

(4)交叉运算：将交叉算子作用于群体。交叉是指将两个父代个体的部分结构加以替换，重组生成新个体的操作。

(5)变异运算：将变异算子作用于群体，即修改父代个体的部分结构操作。

(6)终止条件：群体P(t)经过选择、交叉和变异操作生成新一代群体P(t+1)。若t=T，则进化过程的中最大适应度个体为最优解。

2.2初始种群

对于虚拟机放置问题：

(1)个体表示虚拟机和物理机的空间布局关系，是由用户指定的。如图1所示，12台虚拟机和3台物理机至少存在两种不同的空间布局关系。

长期以来，西部地区经济社会发展滞后，金融发展水平薄弱，人力资本存量较低。尤其是当前，西部地区作为区域协调发展战略的推进方和脱贫攻坚战的主战场，如何促进西部地区的经济又好又快发展成为新时代的重要课题。因此，现阶段从人力资本视角研究西部地区金融发展与经济增长之间的相互关系，从而揭示如何实现西部地区金融发展与经济增长的良性循环，对于我国继续实施西部大开发战略、“一带一路”倡议以及实现全面建成小康社会的宏伟目标都具有重要的理论和现实意义。

图1 基于组编码的虚拟机放置

(2)基因表示个体的组成。如图1所示，该个体由3个基因组成，分别为A、B和C。

(3)种群表示个体的集合。为了便于算法理解和计算，种群的一个关键问题是如何高效描述虚拟机和物理机空间布局与个体的映射关系，即编码与译码问题。

编码目的是构建物理机与虚拟机空间布局到个体的表示，通常包括3种遗传编码方法：(1)基于箱子的表示；(2)基于物品的表示；(3)基于组的表示。考虑到搜索效果和效率要素，本文采用基于组的编码方式。比如，图1所示个体由3个基因组成，可表示为A{2，4，7，5}、B{8，10，11，12}、C{1，3，6，9}；图2所示个体由3个基因组成，可表示为A{2，4，7}、B{5，8，10，11，12，1}、C{3，6，9}。

译码的目的是将个体基因快速地转化为物理机和虚拟机空间布局表现，它是能否有效执行遗传算法的关键。译码采用文献[7]提出的空间分解方法。考虑到存在CPU、内存、网络IO和磁盘IO四种资源，采用四维空间的分割方法。如图2所示，当一个虚拟机放入一个物理节点时，该物理节点被分割成四维空间，即上空间、前空间、左空间和右空间。当执行选择、交叉和变异等算子操作，改变虚拟机在物理节点上的放置位置时，虚拟机必须满足目标物理节点的空间约束。

图2 空间分解示意图

2.3适应度函数

由于个体表示全局物理机与虚拟机的空间布局，因此，适应度最高的个体即为最优解。本小节基于两阶段收益最大化原理构建适应度函数。

假设虚拟化平台是由M台物理机PM和N台虚拟机VM构成的，对于当前物理机与虚拟机的空间布局(假设运行在物理机i上的虚拟机集合是VMSetOn(PMi))，每台物理机的收益为Benefit(PMt),1≤t

(1)

由图3所示可见，物理机收益与其上部署的虚拟机及虚拟机的资源消耗相关。具体而言，对于任何一个采样点t，可根据是否违反公式(2)约束，将收益函数细分为两种构建方法。

图3 虚拟机在线迁移示意图

(2)

(1)满足公式(2)约束

此时物理机的收益函数可由公式(3)描述，说明物理机的收益是与多维资源使用的均衡度相关，且物理机资源使用越均衡，其收益也越大。例如，CPU、内存和网络IO的使用率均为50%的场景，要比CPU使用率60%、内存使用率40%，而网络IO使用率50%的场景更为均衡，收益也越高。

(3)

其中，∂i表示收益因子，需要用户配置。

(2)不满足公式(2)约束

此时物理机的收益函数可由公式(4)描述，说明物理机的收益是与违反公式(2)约束的时间点相关，且违约的时间越晚，收益越大。比如，虚拟机A和B部署在物理机Server1上，若将虚拟机A迁移到物理机Server2，公式(3)违约的时间点发生在中午12点；而迁移虚拟机B，公式(3)违约的时间点发生在发生在下午6点，说明迁移虚拟机A是最优的，收益也最大。

(4)

其中，β表示收益因子，N表示每天资源需求采样点个数，t表示公式(4)中发生第1次违约的采样点标识。

2.4选择算子

对所有个体按照适应度进行降序排列，选择q个适应度最大的个体作为下一代个体的输入。基于选择算子的个体选择算法如下：第1～10行表示对当前种群中的个体按照适应度从大到小排序。第11行表示从当前种群中选择q个适应度最大的个体作为下一代种群的输入。

Generatingnewpopulationsfromselectionoperator

Input：PopulationSizeM;Nextgenerationfromselectionoperatorq；

Fitnessfitness(p)

Output：PopulationPop.

1.intcnt= 0;

2. Randomly generate an initial populationP(0)

3. New population new P, and new P[0]=0

4. fori in newP

5. if new P[i]

6. break;

7.endif

8.insertfitness(cnt)atnewP[i].

9. cnt++;

10.endfor

11. select first p elements ofnewP to the next generation P(1)

2.5交叉算子

交叉是指将两个父代个体的部分结构加以替换，重组生成新个体的操作。如图4所示，交换物理机A和物理机B上标识为5和12的虚拟机是一个具体的交叉实例。

图4 交叉过程

交叉算子需考虑死锁约束问题。由于CPU约束，VM1只有在VM2从物理机B迁移到物理机A之后才能从物理机A迁移到物理机B。同时，由于CPU约束，VM2只有在VM1从物理机机A迁移到物理机B之后才能从物理机B迁移到物理机A。这样就形成了迁移死锁。通过引入额外的物理机可打破迁移死锁现象。具体而言，首先将VM1迁移到引入的物理机C上，然后将VM2迁移到物理机A，最后将VM1从物理机C迁移到物理机B。

2.6变异算子

变异是指修改父代个体部分结构的操作，例如个体indv1={A{2，4 }、B{8，10}}变异成indv2={A{2，7}、B

表2 Web应用资源需求分布函数

{8，10}}。由于个体组成元素是虚拟机，虚拟机不存在凭空创建的可能，因此，变异操作可以看成是特殊的交换操作。

2.7遗传算法实现

基于收益最大化的遗传算法实现如下：

(1)首先初始化群体P(t)，然后分别将选择算子、交叉算子和变异算子作用到初始化群体P(t)，得到群体解空间newP，见算法1～18行；

(2)对群体解空间newP进行筛选，选择依据是根据收益最大化原则，见算法12～19行。

Geneticalgorithmbasedonbenefitmaximization

Input：PopulationSizeM;

Probabilityforcrossoveroperatorp1；

Probabilityformutationoperatorp2;

Output：PopulationPop.

1.intt= 0;

2. Randomly generate an initial population P(0)

3. New population new P

4.whilet

5.forindividualpinP(t)

6. Select operation to new P

7.endfor

8.ifrandom (0, 1)

9.forindividualpinP(t)

10. Crossover operation to new P

11.endfor

12.endif

13.ifrandom (0, 1)

14.forindividualpinP(t)

15. Mutation operation to new P

16.endfor

17.endif

18. t=t+1;

19.foriinnew P

20.forj in new P

21.ifbenefit(i)

22. exchange elementsi,j in newP

23.endif

24.endfor

25.endfor

26. select first p elements of new P to the next

generation P(cnt)

27.end

3 结论

表2给出了应用实例的CPU资源需求分布函数：TPC-W-1和TPC-W-2的CPU资源需求分别符合偏距为60、振幅为10的正弦和余弦分布；TPC-W-3、TPC-W-4的CPU资源需求则分别稳定在50%和40%。

从第15分钟开始，TPC-W-4应用部署到虚拟化平台中，此时Server1、Server2和Server3的CPU资源空闲率均为50%。本文采用“随机策略”将TPC-W-4应用部署并运行在Server1上。

从第33分钟开始，TPC-W-1和TPC-W-4的CPU资源需求均为50%， Server1资源供给面临瓶颈，vMigration平台会触发虚拟机在线迁移操作，根据遗传算法的适应度函数，算法会发现TPC-W-1迁移到Server3，或者TPC-W-4迁移到Server2，或者TPC-W-4迁移到Server3，都会违反虚拟机资源需求小于物理机资源供给的约束(资源供需平衡约束)。只有TPC-W-1迁移到Server2方案，才能满足资源供需平衡约束。因此，TPC-W-1迁移到Server2方案的收益是最大的，也是虚拟机放置的最优解。

由此可见，本方法考虑了全局物理机空间状态稳定性，能间接打破虚拟机“循环迁移”的触发条件。

[1] 张梁,罗宇.基于openstack的虚拟机定时任务的设计与实现[J].计算技术与自动化, 2015,34(2):127-131.

[2] 田苗苗,李俊.面向低能耗的虚拟机部署和迁移策略[J]. 微型机与应用, 2015,34(18):23-25.

[3] 王加昌，曾辉，何腾蛟，等.面向数据中的虚拟机部署及优化算法[J].计算机应用，2013，33(10)：2772-2777.

[4] 董健康，王洪波.IaaS环境下改进能源效率和网络性能的虚拟机放置方法[J].通信学报，2014，35(1)：72-81.

[5] 周舟，胡志刚.云环境下面向能耗降低的虚拟机部署算法[J].华南理工大学学报，2014，42(5)：109-114.

[6] 高林，宋相倩，王洁萍.云计算及其关键技术研究[J].微型机与应用，2011，30(10)：5-7.

[7] 李松，罗勇，张铭锐.遗传算法优化BP神经网络的混沌时间序列预测[J].计算机工程与应用，2011，47(29)：52-55.

Virtual machine live migration optimization method based on genetic algorithm

Liu Chang

(State Grid Jibei Electric Power Co., Ltd., Qinhuadao Power Supply Company, Qinhuangdao 066000, China)

TP311

A

10.19358/j.issn.1674- 7720.2017.18.007

刘畅.基于遗传算法的虚拟机在线迁移优化方法[J].微型机与应用，2017,36(18)：22-25，29.

2017-03-28)

刘畅(1974-)，通信作者，男，本科，工程师，主要研究方向：信息安全等。E-mail:101378822@qq.com。