云计算资源池负载均衡调度策略研究

许成林 杨德胜 何亮

摘  要：本文研究资源池下的主机负载均衡算法，包括CPU、内存与网络负载3个方面。资源池下主机负载均衡主要包括两个阶段，包括新建资源池和更新资源池。这两个阶段有一定的共通性，即都考虑了资源池下主机多项资源的负载均衡;但是也存在显著差异。新建资源池时进行负载均衡不用考虑虚拟机迁移操作;更新资源池时却必须考虑，因虚拟机在主机之间进行迁移将根据虚拟机内存变化量的大小而短暂地暂停虚拟机，根据SLA（服务等级协议）的相关要求，虚拟机在线迁移操作是存在一定代价的，本文定义其为虚拟机迁移代价。本文在资源池状态变化时不光考虑了主机CPU、内存与网络三种资源的负载均衡，同时还为尽量减小虚拟机迁移代价做了特别优化。

关键词：云计算  负载均衡  遗传算法  策略研究

中图分类号：U416.214                        文献标识码：A                  文章编号：1674-098X（2020）07（b）-0106-07

Abstract： This paper studies the host load balancing scheduling strategy in the resource pool，including CPU， memory and network load. There are two main stages of load balancing in the resource pool， including creating resource pool and updating resource pool. There is a certain commonality between the two stages， that is， the load balancing of multiple host resources in the resource pool is considered， but there are also significant differences. Load balancing when creating a new resource pool does not consider virtual machine migration; Resource pool updates must be considered， however， as the virtual machine migrates between hosts， the virtual machine will be temporarily suspended， and the time to suspend depends on the size of change in the virtual machine memory. According to relevant requirements of SLA （service level agreement）， virtual machine online migration operation has a certain cost， which is defined as virtual machine migration cost in this paper. This paper not only considers load balancing of host CPU， memory and network when resource pool state changes， but also makes special optimization to minimize the migration cost of virtual machine.

Key Words： Cloud computing; Load balancing; Genetic algorithm; Strategy research

1  相关研究

目前国内外学者对资源池下的主机负载均衡提出了多种方法：（1）根据双向蚂蚁记录分配资源这一理念提出了一种改进的蚁群算法，但是其将多目标算法函数简单处理成了单目标算法函数，这可能导致从主机外部看其可能处于负载均衡状态，但从其内部的CPU、内存以及网络负載着却可能处于失衡状态，同时其也未考虑虚拟机迁移代价的问题;（2）提出了一种基于双向反馈的蚁群算法的负载均衡调度策略，但研究时发现为每只蚂蚁建立自己的正反向结构集合会导致占用太多的资源，并在信息素局部更新时会导致收敛的速度加快从而无法获得全局最优解;（3）提出了基于一种改进的遗传算法的资源池负载均衡策略，但是其只考虑了CPU与磁盘I/O这两个方面，对于当前需要考虑更多维度的实际情况已不再适合;（4）提出了一种基于服务器资源权重的方法将多维资源的负载函数转换成单一维度负载函数，但其过多地考虑了人为设置的因素，通常在基于FC-SAN的资源池中，作为计算节点的主机需同时考虑CPU、内存及网络负载，而并不是仅仅关注某一项;（5）采用轮询调度算法对虚拟机进行分配以实现资源池负载均衡，其使用局部调度而不能实现全局优化，同时其也未考虑虚拟机迁移成本的问题。

本文将资源池分为新建与更新两种状态。对于新建资源池，本文使用了类似遗传算法种群初始化的方法对解空间进行初始化以保证解空间的多样性，之后基于模拟退火算法循环遍历处理前面通过遗传算法得到的解，最后在满足预设的资源池负载均衡条件后终止循环，并输出当前最优解;对于更新资源池，可以通过预设的资源池负载均衡条件来动态调整资源池整体的虚拟机迁移成本，这给予实际生成环境极大的灵活性。

2  问题的形式化描述

2.1 资源池负载均衡调度的数学模型

资源池中主要包含了计算、存储与网络资源，本文不考虑存储，而计算资源包括主机的CPU与内存，网络资源则表示主机的带宽。

从资源池中包括的对象而言，主要包括作为计算节点的主机以及运行在主机上的虚拟机，同时将资源池整体抽象为一个对象。本文假定资源池中存在n个主机以及m个虚拟机。现在进行以下定义：

映射方案：包含了资源池下所有主机与虚拟的映射关系，用F表示，则F={scheme1，scheme2，scheme3，……，schemen }，其中Fs（1≤s≤n）表示第s个映射方案。

虚拟机：定义CPU核数为vmCpuNum，内存大小为vmMemSize，网络带宽使用量vmNetUseWidth，CPU使用率为vmCpuUseRatio，内存使用率为vmMemUseRatio;则CPU使用量vmCpuUseNum = vmCpuNum*vmMemUseRatio，内存使用量vmMemUseSize = vmMemSize*vmMemUseRatio。

主机：定义CPU总核数为hostCpuTotalNum，总内存大小为hostMemTotalSize，总网络带宽为hostNetBandTotalWidth;设空闲CPU资源为hostCpuFreeNum，空闲内存资源为hostMemFreeSize，空闲网络带宽为hostNetBandFreeWidth;由此可得主机CPU使用率hostCpuUseRatio = 1-hostCpuFreeNum/hostCpuTotalNum，内存使用率hostMemUseRatio = 1-hostMemFreeSize/hostMemTotalSize，网络带宽使用率hostNetUseRatio = 1-hostNetBandFreeWidth/hostNetBandTotalWidth。

主机资源倾斜度：其表示了主机的CPU、内存与网络的使用率与资源池平均CPU利用率、内存利用率、网络利用率之差，包括CPU倾斜度hostCpuSkew=100*（ hostCpuUseRatio - poolAvgCpuUseRatio） ，内存倾斜度hostMemSkew =100*（hostMemUseRatio- poolAvgMemUseRatio），网絡倾斜度hostNetSkew = 100*（hostNetUseRatio- poolAvgNetUseRatio），主机总资源倾斜度hostSkew = Math.abs（hostCpuSkew）+ Math.abs（hostMemSkew） + Math.abs（hostNetSkew），这里Math.abs（x）函数将获得数值x的绝对值。

2.2 应用场景和范围

在本文中，主要考虑资源池使用共享FC-SAN（光纤存储）作为虚拟机磁盘文件的场景，主机使用HBA卡与光纤存储交换机连接，光纤存储交换机再与FC-SAN连接。通常主机使用的HBA卡（光纤存储卡）以及与其连接的存储光纤交换机的读写带宽都比FC-SAN本身提供的读写速率高很多，所以主机磁盘I/O主要取决于FC-SAN本身的读写速率（底层磁盘阵列的读写速率），不论是一台主机还是两台主机，瓶颈不在主机而在FC-SAN上，所以本文不考虑主机磁盘I/O的负载均衡。

3  算法的调度模型

3.1 遗传算法的关键元素

个体：资源池下主机与虚拟机的一个具体的映射方案Fs（1≤s≤n）为个体。

种群：一定规模个体的集合。

种群规模：种群中个体的总数量。

基因：资源池下一个具体虚拟机的具体位置（在某台主机上）以及其对资源池CPU、内存与网络资源的具体使用量。

最佳适应度：本文定义主机的适应度函数为主机资源倾斜度的负相关函数，当主机资源总倾斜度以及主机的单项资源倾斜度越小则表示越接近负载均衡的目标。但由于主机总倾斜度与单项资源倾斜度可能存在冲突，本文将以预设条件来使主机的资源使用情况尽量达到预期效果。

变异：本文定义将虚拟机从一个主机迁移到另一个主机为变异，变异后将导致源主机与目标主机的各自的总倾斜度以及CPU、内存与网络倾斜度发生变化。在本文中变异包含两种：第一种是朝着资源池整体倾斜度减小的方向变异，这种变异将会快速地收敛解空间;第二种是朝着资源池整体倾斜度增大的方向变异，这是为了避免陷入局部最优解。

交叉：不同个体间互换基因的操作，因为在这里一个个体就是一个资源池下所有主机与虚拟机的映射方案，而适应度高的个体在交叉后有很大机率不会变得更好，为了减少计算时间将不使用这种操作。

代数：种群迭代的次数。

3.2 新建资源池过程调度算法

如图1，算法主流程的第一步是初始化种群，在这一步中，首先初始化待部署的虚拟机以及资源池中存在的主机，遍历虚拟机以及主机，在所有主机的CPU、内存与网络资源都不超载的情况下构建一个原始映射方案;然后以这个原始映射方案为基础，通过高概率随机基因变异的方式最终获取一定规模的映射方案集合即种群。

如图1，算法主流程的第二步是遍历整个种群中的所有个体，为每个个体开启一个子处理流程，从此处开始并发处理每个种群中的所有个体-映射方案。个体处理子流程的具体步骤如图2。

如图2，个体处理子流程的第一步是对个体进行有条件的变异，此处的变异操作将以减小源主机与目标主机总资源倾斜度为目标，这样即可减小资源池的总体倾斜度以达到增加主机与资源池适应度的效果。当这个映射方案的适应度不再发生变化的时候，就进行个体处理子流程中的第二步处理。

个体处理子流程第二步的处理过程如下：对当前个体，选择出主机倾斜度以及CPU、内存与网络的单项倾斜度不符合预设条件的主机集合并进行遍历，假设当前主机为Hi，获取Hi上运行的所有虚拟机，分别选择出vmCpuUseNum、vmMemUseSize、vmNetUseWidth最大的虚拟机集合，取这三者中最大的那个值对应的虚拟机Vbiggest，获取整个资源池中虚拟机数量最多那个主机Hmost，虚拟机数量多表示其上运行的单台虚拟机的CPU、内存与网络利用率更小，因此可以形成较多的组合。将Hi上的虚拟机Vbiggest与Hmost中的多台虚拟机进行交换，例如：假设此时Vbiggest是基于vmCpuUseNum的，那么就从Hmost中对虚拟机以vmCpuUseNum从小到大进行排序，循环处理排序后的虚拟机列表，对每个虚拟机的vmCpuUseNum进行累加求和，设此值为vmCpuSumUseNum，当vmCpuSumUseNum >Vbiggest.vmCpuUseNum时循环终止，然后进行虚拟机的交换操作。此虚拟机交换操作会增加资源池整体的不均衡度，但对整个资源池负载均衡方案的寻找是有好处的。其好处之一是会将某项资源消耗较大的虚拟机分散到资源池中不同的主机上;好处之二让集合H_V中的主机上运行更多的虚拟机，这样通过后续的操作则更有可能达到预期的负载均衡状态。当需要进行交换的主机完成一次遍历后，检测终止条件2，如果为否则返回到个体处理子流程的第一步开始循环整个子流程，直到满足终止条件2，此时保存当前个体，并结束当前的子流程。

如图1，在主流程中，当所有个体处理子流程都结束之后，此时种群表示为映射方案的集合Fnew = {Snew1，Snew2，Snew3，……，Snewn }，其中Fs（1=

3.3 更新资源池过程调度算法

在更新资源池状态时，本文将以尽量少的虚拟机迁移成本来达到一个符合预期的资源池负载均衡状态为目标进行算法设计。

如图3，算法主流程的第一步是初始化当前的资源池状态，通过这一步可以获取资源池下所有虚拟机与主机在当前状态的映射关系，本文设这个映射关系为Schemeold。因为后续子流程中虚拟机调度存在随机性，因此在主流程的第二步则可并发开启n个子处理流程。当所有子流程都处理完成之后，因为都时满足资源池负载均衡条件的，所以直接选取迁移成本最小的那个映射方案即可。

如图4，算法子流程的第一步，首先选择出不满足资源池负载均衡预设的主机必须达到的限制条件时的主机集合HV，遍历这些主机并进行以下处理。在这里引入MIGRATE_MULTIPLE（强制迁移倍数），此处理将会引起资源池整体倾斜度的增加，为了避免MIGRATE_MULTIPLE过大引起资源池倾斜严重，其值将从1开始，并以0.02的步长缓慢递增，在越小的MIGRATE_MULTIPLE完成对主机集合HV的处理则表示需要迁移的虚拟机越少，资源池的整体迁移成本越小。当处理完集合HV中的主机之后，将判定此时是否满足终止条件2，如果满足则保存此时的映射关系Schemebest并结束整个子流程，如果不满足则跳转到主流程中的第三步从新基于资源池当前的映射关系Schemetmp进行处理。

如图4，算法子流程的第二步将先获取映射关系Schemetmp下不满足负载均衡条件的主机集合Hnotbalance，将遍历Hnotbalance中所有主机上的所有虚拟机（此处将优先获取源主机上不在方案Schemeold中存在映射关系的虚拟机进行处理，这样可减小迁移代价），计算将源主机Hi上的虚拟机V_ij迁移到目标主机Hm上时，Hi与Hm二者的整体资源倾斜度之和是否会减小，如果会减小则进行迁移。终止条件1表示资源池整体倾斜度不再变化，如果满足终止条件1，则终止循环并进行终止条件2的判断。终止条件2将主要判定当前映射方案中所有主機的倾斜度是否都已满足预设的资源池负载均衡限条件，例如：任意主机的整体资源倾斜度不超过10，且其上CPU、内存与网络的单项资源倾斜度均不超过5，通过这两者的相互制约，可以让资源池中的主机整体处于负载均衡状态。另外，通过修改这两个值，比如两者都增大，则可以更多地避免虚拟机迁移，以此来降低更新资源池状态时的整体迁移成本。如果此时终止条件2不满足，则跳转至算法子流程的第一步并继续处理;如果终止条件2满足，则保存此时的映射关系Schemebest并结束整个子流程。

4  实验仿真与分析

4.1 实验环境及参数设置

为了评估本文所描述资源池负载均衡调度策略的有效性与可行性，自己基于Java编写了一套资资源池运行的仿真程序。程序的核心对象就是资源池、主机与虚拟机，其相关属性及属性间的关系在3.1小节已详细描述。本文设置主机的相关配置为：CPU 128核，内存256GB，虚拟机调度使用到的管理网络带宽为1000Mb/s;虚拟机配置则主要有4C8GB、8C16GB及16C32GB 3个档次，网络速率在1000Mb/s 中没有限制。

按照以上模板分别生成200、400、600、800、1000台虚拟机，对应的主机数量为15、35、50、70、85台;这些虚拟中的CPU使用率、内存使用率与网络占用速率都是在不超载的范围内保持随机性。

4.2 调度策略模型仿真与分析

新建资源池时调度策略可配置的一些参数有：种群规模populatioSize;映射方案局部变异次数countVar，其主要应用于初始化种群;资源池整体倾斜度hostSkew，单项资源可承受倾斜度：errorRange。经过反复验证：设置populatioSize=200，countVar=60， hostSkew=8，errorRange=4时，可快速获得负载均衡方案，如图5，可以看出随着虚拟机数量的增加，资源池整体倾斜度基本呈线性增长，而且其中每台主机的整体倾斜度不超过8且单项资源倾斜度均小于4，可见映射方案的负载均衡性于实用性都较好。

更新资源池时调度策略可配置的一些参数有：资源池整体倾斜度hostSkew，单项资源可承受倾斜度：errorRange。资源池更新前状态与这两个参数同时作用，对负载均衡时的资源池倾斜度以及资源池整体迁移代价密切相关。整个调度策略是在进行资源池负载均衡的过程中尽可能不迁移与初始化映射方案中在同一台主机上的虚拟机来减小资源池整体迁移代价。如图6，使用了减少迁移代价的处理方式时比没使用的基本会少60%左右的迁移成本。

5  结语

本文针对云计算资源池的负载均衡调度问题，提出了一种虚拟机的调度方案。首先将资源池的负载均衡分为新建与更新两个阶段，在处理新建资源池的负载均衡时使用了遗传算法，在处理资源池状态更新之后的负载均衡时同时考虑了相应策略以减小资源池整体迁移代价。最后通过资源池仿真程序进行实验，通过实验结果表明了本文所述调度策略的有效性与可用性都较好。

参考文献

[1] 吕燕兵，王静宇，吴金明.云计算资源负载均衡调度优化算法研究[J].内蒙古科技大学学报，2017，36（2）：181-186.

[2] 栾志坤，牛超.云数据中心中负载均衡的虚拟机调度方法[J].计算机与现代化，2017（5）：24-36.

[3] 洪越.遗传算法在随机分布控制中的应用综述[J].现代工业经济和信息化，2018（17）：69-70.

[4] 颜恩锋.基于遗传算法优化BP神经网络的基坑变形研究[J].中国水运（下半月），2019，19（4）：72-73，76.

[5] 杜吉成.云数据中心基于负载权重的负载均衡调度算法[J].研究与开发，2013（12）：7-11.

[6] 张超. 混合群智能优化算法研究及应用[D].北京：北京科技大学，2018.