利用遗传算法完成虚拟机放置策略的优化

2020-12-31徐胜超

计算机与现代化 2020年12期

徐胜超

(广东财经大学华商学院数据科学学院,广东广州 511300)

0 引言

节能大数据中心的构造是近年来政府与云服务提供商越来关注的问题[1-3]，虚拟机迁移技术可以使大数据中心的所有物理资源高效利用、负载均衡并降低能量消耗[4-7]。在迁移过程中虚拟机放置是一个十分关键的步骤[8-10]。

对于虚拟机放置，有些文献把它称为多目标优化或者医院病床分配问题[11]，它的功能是把候选迁移的虚拟机按照一定的规则重新分配到云数据中心的物理主机上执行。该过程有很多智能算法进行优化，例如粒子群优化算法[12]、萤火虫群优化算法[13]、贪心算法[14]、稳定匹配算法[15]、蛙跳算法[16]、遗传算法[17]等。

在节能大数据中心研究领域,Anton Beloglazov博士团队提出的Cloudsim项目及其后续研究一直处于世界领先地位,它将虚拟机迁移过程划分为物理主机状态检测、虚拟机选择、虚拟机放置等3个步骤,前一个步骤的输出参数,正好是下一个步骤的输入参数,每个步骤都可以通过算法予以优化。

在Cloudsim项目中提到的性能较好的办法是用LRR (Local Regression Robust)算法为物理主机进行状态检测,结合MMT(Minimum Migration Time)算法完成虚拟机选择,再结合递减装箱算法(Best-Fit-Decreasing CPP， BFD)完成虚拟机放置,可将这种方式称之为LRR-MMT-BFD虚拟机迁移策略,它的实现结果见Beloglazov博士的相关文献[5,7]。

LRR方法是一种自适应的主机CPU利用效率阈值检测办法,它通过检测一个物理主机的最近的j个处理器的使用效率值作为评价方法,这样来判断该物理主机是否处于异常状态,形成候选迁移物理主机列表MigratedHostList。MMT选择一个在最短时间内能够完成迁移的虚拟机作为侯选迁移对象,形成侯选迁移虚拟机列表VmsToMigrateList; BFD是递减装箱方法，它按照虚拟机的处理器的使用效率按照递减的方式排序，针对VmsToMigrateList参数,依次完成虚拟机重新放置。由于本文的研究焦点在虚拟机放置过程,所以虚拟机迁移的前面2个步骤主要参考Cloudsim的思路与代码。

目前其他的虚拟机放置方法大多采用资源使用率阈值边界来确定虚拟机迁移的因素，其资源考虑的维度因素也比较单一；另外由于虚拟机放置属NP-Hard问题,该问题没有最优解，已提出的智能计算方法只能在各个性能指标上进行平衡。

本文也提出了基于遗传算法的虚拟机放置方法GA-VMP，它考虑的物理主机的硬件维度从处理器扩展到内存大小、磁盘大小和网络带宽等；GA-VMP参考了Cloudsim中的物理主机能量消耗模型和性能测试指标。GA-VMP虚拟机放置策略配合前面的物理主机状态检测阶段LRR和虚拟机选择阶段的MMT优化方法，构成了一个完整的新型虚拟机迁移模型,最后本文完成了GA-VMP策略的仿真和性能分析。

1 虚拟机放置的相关工作

目前学术界通过虚拟机放置策略来提高绿色云数据中心的性能,并对此进行了大量的研究。近年来不同文献的研究主要涉及2个方面的研究进展：能量消耗模型的变化和智能算法的改进。

在能量消耗模型研究方面，由早期的单一CPU资源利用率提高到现在的CPU、内存、网络带宽、硬盘空间等利用率提高都予以考虑。在智能算法的改进方面，近年来提出了大量的新型智能算法进行虚拟机放置阶段的优化,例如贪心算法、蚁群算法[18]、遗传算法[19]、增强学习优化算法[20]、花授粉算法[21]等。

贪心算法在优化方面常见的有首次递减适用算法、最佳适用算法、最佳递减适用算法等，但是由于虚拟机放置是NP-Hard问题，贪心算法也不可能得到最优解；遗传算法在优化方面常见的有普通遗传算法、家族遗传算法、混合遗传算法、改进的遗传算法等，但是由于它们采用约束编程的方式，限制了搜索空间。虽然在单维物理资源的高效利用方面，近年来蚁群算法优化的虚拟机放置取得了一定成功，它们的实验结果表明其性能优于首次递减适用的贪心算法，它们的不足是不能充分利用多个维度的物理资源。文献[22]采用蚁群算法优化，用处理器和内存大小等多个维度的信息来考虑云数据中心的虚拟机迁移，结果表明它的性能优于遗传算法。

GA-VMP虚拟机放置策略克服了早熟问题和收敛速度慢的问题,与其他的普通遗传算法相比，大部分算法是以提高云数据中心的资源利用效率为目标函数，还有少量策略是以降低SLA(Service Level Agreement)违规率为目标函数，GA-VMP以降低云数据中心能量消耗为目标函数,它们与GA-VMP区别在于目标函数不同。

2 工作背景与相关术语

2.1 GA-VMP的工作场景

图1显示了GA-VMP虚拟机放置策略的工作场景，这是一个典型的云客户端对云数据中心的服务请求场景。GA-VMP依托了Cloudsim各个运行模块：全局代理(Global Broker)、本地代理(Local Broker)、虚拟机管理器(Virtual Machine Manager)。

图1 GA-VMP虚拟机放置策略的工作场景

在Cloudsim中，每个物理主机上都运行有一个本地代理，GA-VMP优化策略的实现主要在此模块中完成。这个工作场景在文献[4-5]中都有描述。

2.2 GA-VMP的工作流程

由于GA-VMP属于Cloudsim项目的后续研究工作，所以在工作流程上与Cloudsim比较接近。

工作流程具体包括下面4个步骤:

Step1基于鲁棒局部回归LRR方法完成物理主机状态检测，形成侯选迁移物理主机列表。

Step2基于最小迁移时间选择MMT算法完成虚拟机选择，形成侯选迁移虚拟机列表。

Step3基于GA-VMP方法完成虚拟机重新放置。

Step4重复Step1～Step3，设置一个周期(通常是一周),达到该时间段就结束。

图2显示了GA-VMP虚拟机放置策略在整个虚拟机迁移过程中的工作流程。

图2 GA-VMP在虚拟机迁移中的地位

2.3 GA-VMP的相关术语

1)云数据中心能量消耗模型(Energy Consumption)。

云数据中心主要由大量的物理主机组成，所以其能量消耗主要由物理主机的所有部件的能量消耗组成。文献[23]认为一个物理服务器(双核CPU、4条内存、一个磁盘、2个PCI插槽，一个主板等)所消耗的能量大约为：CPU占41%，内存占18%，磁盘占7%，PCI插槽占22%，主板占12%。根据这个思路，本文设计单个物理服务器的能量消耗为：

E(Ucpu)=Eidle+(Emax-Eidle)Ucpu

(1)

(2)

E(Umem)=Eidle+(Emax-Eidle)Umem

(3)

E(Udisk)=Eidle+(Emax-Eidle)Udisk

(4)

E(Ubw)=Eidle+(Emax-Eidle)Ubw

(5)

Etotal=E(Ucpu)+E(Umem)+E(Udisk)+E(Ubw)

(6)

其中，rj(t)表示分配到物理主机Mj的虚拟机的索引集合,Ucpu(t)、Umem(t)、Udisk(t)、Ubw(t)表示物理主机在t时刻的CPU使用率、内存使用率、磁盘使用率、网络带宽使用率，0%Ucpu(t),Umem(t),Udisk(t),Ubw(t)100%。

Eidle表示物理主机CPU、内存、磁盘空间、网络带宽在空闲时的能量消耗，即当Ucpu(t)=0%、Umem(t)=0%、Udisk(t)=0%、Ubw(t)=0%的时候。

Emax表示物理主机在满负载时的能量消耗，即当Ucpu(t)=100%、Umem(t)=100、Udisk(t)=100%、Ubw(t)=100%的时候。

mipsi,c是第i个虚拟机VMi的第c个处理元素的mips请求情况。

MIPSj,c是第j个物理主机Mj的第c个处理元素的整体的MIPS计算能力。

一个虚拟机请求的MIPS数量是随着应用程序变化而变化的，所以物理主机的资源使用率也应该是随着应用程序的变化而变化，因此统计物理服务器的能量消耗必须在一定的时间段内，这样根据公式(1)可以演化为公式(7)：

Etotal(t)=E(Ucpu(t))+E(Umem(t))+E(Udisk(t))+E(Ubw(t))

(7)

这样第j个物理主机在[t0,t1]时间段的总体能量消耗Etotal可以按照公式(8)来计算：

(8)

整个云数据中心的能量消耗为公式(9),M是物理主机个数。

(9)

2)SLA违规在线时间(SLA violation Time per Active Host， SLATAH)。

当一个云客户端提交作业到云计算平台的时候，资源缺少就会出现SLA违规，在虚拟机分配过程中，一个重要的性能指标是每个物理主机的SLA在线时间(SLA time per host)，它体现了物理主机具有高服务质量的在线时间情况。

(10)

云数据中心的主机数量和虚拟机数量分别用M和N表示，其中Tsi是物理主机CPU利用率达到100%的时间，Tai是物理主机处于在线活跃状态的时间。

3)虚拟机迁移后的性能降低(Performance Degradation due to Migrations， PDM)。

(11)

其中Cdi是由于虚拟机VMi迁移导致的性能下降的估计值，Cri是请求虚拟机VMi的整个时间段内总的CPU MIPS计算能力。

4)能量与SLA违规的联合指标(ESV)。

SLA的违规率的计算如公式(12)：

SLAViolation=SLATAH·PDM

(12)

总体能量消耗平衡的指标为：

ESV=E·SLAViolation

(13)

本文在GA-VMP基于遗传算法的虚拟机放置算法中用到的符号见表1。

表1 基于遗传算法的虚拟机放置方法相关符号

3 GA-VMP的虚拟机放置过程描述

3.1 GA-VMP虚拟机放置具体过程

假设有N个虚拟机的集合{VMi(pei,mipsi,tsi,di)|i=1,…,N}在虚拟机放置阶段要重新分配到云数据中心的M个物理主机{Mj(PEj,MIPSj)|j=1,…,M}上运行，每个虚拟机都请求pei个处理元素，请求包括mipsi个计算需求，VMi的开始执行时间为tsi，完成时间为tsi+di，在di个时间段内没有被打断也没有进行迁移操作，本文并不把迁移因素只放在物理主机的CPU使用率这个单一维度上，而是扩展物理资源的维度，包括内存大小、磁盘空间大小、网络带宽大小等。假设每个物理主机Mj可以容纳任何类型的虚拟机，物理主机的能量消耗模型Etotal(t)与各类物理资源的使用率成线性关系，那么该虚拟机放置的目标就是最小化云数据中心的能量消耗，并且尽可能地完成更多个虚拟机的执行，因此目标函数为：

前面提到虚拟机放置是完成虚拟机到物理主机的映射，是一种多目标优化问题，因此GA-VMP引入多目标遗传算法求解虚拟机放置问题，关于遗传算法的具体含义由于篇幅关系就不详细叙述，GA-VMP求解的具体步骤如下：

染色体编码为s个染色体创建一个初始的种群，s为种群的大小,其实现的是从虚拟机编号到染色体的映射。

适应度的计算适应度函数Fitness是由目标函数转换而成的，在给定的种群的条件下，计算每个染色体的进化值。

新家族种群计算通过执行下面的步骤来完成新的家族种群的创建，完成更新。

选择阶段基于染色体的进化值，从当前的种群中选择出带有2个双亲的个体。

交叉阶段利用交叉概率，通过修改双亲的染色体来创建一个新的后代。

变异阶段通过变异概率，将在染色体的某个位置完成变异。

接受阶段在当前情况下，一个新孩子将从下一代的部分中产生。

取代阶段通过分配当前的这一代个体到下一代，完成取代操作，如果终止条件达到，则算法将停止执行，返回一个具有最高的进化值的个体，否则，算法返回到适应度的计算阶段继续循环执行。

图3显示了GA-VMP的思路。

图3 GA-VMP算法的具体工作流程

下面是GA-VMP遗传算法的虚拟机放置过程的伪代码，该代码通过少量修改即可用Java语言来实现，见Algorithm1。

Algorithm1Outline of the Gene algorithm

Input:Lists of hosts and VMs

Output:VM placement decision (true/false)

1.Initialize the list of hosts and Vms.

2.Initialize the values of parameters of GA.

3.Initialize the number of families to be constructed.

4.Randomly initialize the population.

5.Compute the fitness values of each chromosome in the population.

6.Perform crossover and mutation.

7.Select the family heads as the best individuals from the current population.

8.for all Family ∈ Population do

9.repeat

10.Perform mutation on the family head and insert mutated chromosome into family.

11.Compute the fitness value of the chromosome obtained after mutation.

12.if fitness of the mutated chromosome is greater then

13.add the mutated chromosome to the population.

14.Set flag as true

15.end if

16.until family size k

17.repeat Perform crossover and mutation on the current family to get the next generation of the current family.

18.until ‘k’ times

19.if flag=true else ‘w’ times

20.if flag=false

21.Select the fittest individual from the population to get the best solution.

22.end for

23.Return flag

每个家族信息进行k次处理，如果一直没有遇到更加优质的个体，则破坏家族信息，换成下一个家族,见Algorithm1中的16～22行代码。在当前的家族信息处理过程中，如果至少产生了一个比较好的个体信息，家族算法将继续处理该家族信息，完成w次迭代处理，这里的参数k和参数w在系统测试过程中都可以进行设置。

3.2 GA-VMP的实现

GA-VMP是一种遗传算法，主要用来解决虚拟机放置这种多目标优化问题。GA-VMP的目标函数即是云数据中心的能量消耗最小。

本文使用一个层次结构来体现各个个体之间的染色体的关系。该层次结构具有3个层次，图4显示了这个层次结构。

图4 GA-VMP中虚拟机到物理主机的映射情况

层次1由初始化的个体组成。

层次2由一系列节点组成，代表了云数据中心的一组虚拟机。

层次3由一系列节点组成，代表了物理主机上运行的一组物理主机。

通过这个层次结构，体现了虚拟机到物理主机的放置情况，适应度函数完成每个染色体的进化值的计算，该过程针对虚拟机放置都是并行进行，可以降低虚拟机迁移的计算时间。针对适应度函数的伪代码见算法Algorithm2。

Algorithm2Calculation of the fitness value of each chromosome

Input:Chromosome

Output:Fitness of the chromosome

1.powerOfDatacenter=0

2.For each host∈collection of hosts do

3.utilizationMips=host.getUtilizationOfCpu( )

4.utilizationMem=host.getUtilizationOfMem( )

5.utilizationDisk=host.getUtilizationOfDisk( )

6.utilizationBw=host.getUtilizationOfBw( )

7.powerOfMips=getPower(host, utilizationMips)

8.powerOfMem=getPower(host, utilizationMem)

9.powerOfDisk=getPower(host, utilizationDisk)

10.powerOfBw=getPower(host, utilizationBw)

11.powerOfHost=powerOfMips+powerOfMem+powerOfDisk+powerOfBw

12.powerOfDatacenter=powerOf Datacenter+powerOfHost

13.End For

14.Evaluation value (chromosome)=1.0/powerOfDatacenter

本文的GA-VMP虚拟机放置方法结合Cloudsim中已有的基于鲁棒局部回归LRR物理主机状态检测方法和最小迁移时间MMT虚拟机选择策略，即形成了一个新型的虚拟机迁移模型，称为LRR-MMT-GA。

4 仿真实验与性能分析

4.1 仿真环境的设置

本文参考了Cloudsim3.0工具包，同时依据图1中的运行场景，在Cloudsim中实现基于Java语言的全局代理、局部代理和虚拟机管理器。物理主机的能量消耗模型采用CoMon project,它是一种最常使用的能量消耗模型,是由planet实验室开发的，被Cloudsim模拟器所利用的能量消耗模型[24]。

物理主机配置见表2,虚拟机个数配置见表3,虚拟机类型配置见表4。

表2 云数据中心物理服务器配置

表3 虚拟机个数与运行时间情况

表4 不同粒度的虚拟机情况

4.2 评测标准与比较对象

Cloudsim中比较好的办法为LRR-MMT-BFD策略,它的实现结果在Anton Beloglazov博士的相关文献都有发表,它应该作为首要比较对象。

本文与萤火虫群优化[13]、稳定匹配[15]、考虑关联性虚拟机放置[25]、粒子群优化的虚拟机放置[12]等策略进行了比较，分析了这些智能计算优化方法对云数据中心的性能改变情况,如表5所示。

表5 GA-VMP虚拟机放置方法的性能比较对象

4.3 仿真结果与性能分析

4.3.1 云数据中心总体能量消耗

利用GA-VMP虚拟机放置算法之后，各个虚拟机迁移模型一周之内的总体能量消耗如表6所示。LRR-MMT-GA迁移模型比其他各个迁移策略在总体能量消耗上要节约15%～30%。分析原因是通过GA-VMP最小能量消耗目标函数的优化，所有物理服务器的总体能量消耗自然减少。

表6 各类虚拟机迁移策略的总能量消耗比较

4.3.2 虚拟机迁移次数

表7显示了在一周的5天之内LRR-MMT-GA的虚拟机迁移次数最小。原因是LRR-MMT-BFD很容易增加超负载或低负载的物理主机的数量，而LRR-MMT-GA策略则与LRR-MMT-BFD正好相反，它不会增加虚拟机迁移次数。另外GSO-VMM策略、Stable-Matching策略和PSO-VMM策略的优化主要在虚拟机放置阶段，必须像Correlation-Based策略一样在虚拟机选择阶段、物理主机状态检测阶段完成优化才能更好地降低迁移次数。

表7 各类虚拟机迁移策略的虚拟机迁移次数

4.3.3 SLA违规率分析

从表8可以看出，周一到周五，LRR-MMT-GA都比较少出现SLA违规，原因是LRR-MMT-GA比递减装箱办法的优化能力要强，而且从本文设计的能量消耗模型来看，LRR-MMT-GA考虑的迁移因素的维度，范围不仅仅限制在CPU方面，还考虑了内存大小、磁盘空间及网络带宽。

表8 各类虚拟机迁移策略的SLA违规率比较

GSO-VMM、Stable-Matching、Correlation-Based和PSO-VMM在某些时候还优于LRR-MMT-GA策略，LRR-MMT-GA以降低能量消耗为最终目标函数，所以也会导致增加SLA违规率。

4.3.4 能量与SLA违规的联合指标ESV

从表9中的结果可以看到，LRR-MMT-GA的ESV指标不是最好的,Stable-Matching和Correlation-Based策略针对原始的Cloudsim各个阶段都有优化，自然比LRR-MMT-BFD迁移策略性能好，PSO-VMM迁移策略的ESV最低，它比单一目标函数的LRR-MMT-GA迁移策略在ESV方面要低。