面向负载-时间窗口的基于PSO-GA的云软件服务自适应资源分配方法
2021-05-10杨立坚黄引豪
杨立坚，陈 星，黄引豪
(福州大学 数学与计算机科学学院，福州 350108)
(福建省网络计算与智能信息处理重点实验室，福州 350108)
1 引 言
云计算是将某一个或某几个数据中心的计算资源虚拟化之后，向用户提供以租用计算资源的服务，其为海量数据和计算资源提供基础性的接入，并且这些资源可以按需进行动态接入和释放.在云计算环境中，云软件服务面临着动态变化的工作负载，然而，这种动态和不可预测的工作负载可能导致软件服务质量的下降，特别是当对资源的需求增加时.为了在不断变化的工作负载下提供资源的可伸缩性和弹性，云提供商通常需要在共享基础设施中提供软件和硬件资源的按需配置.如今，基于云的软件服务的大量使用证明了云软件工程正在获得发展势头[1].如何为这些云软件服务合理分配资源是一项具有挑战性的任务.近年来，随着云软件资源自适应技术[2-5]的不断发展，云应用分配资源的有效性有所提高，用户追求的高软件服务质量与云厂商追求的低云资源开销之间的矛盾关系也有所平衡.与此同时，如何更好地提高资源分配的有效性成为了自适应技术发展新的挑战.
现有的自适应技术中，大都是针对云环境中当前负载的状况做出响应，并进行资源自适应分配.AlQayedi等人[6]提出一种基于排队理论的方案，根据当前的工作负载来估计满足响应时间所需的VM实例的数量，该方案还采用响应式资源调配技术，以CPU利用率为阈值，定期(每1或2分钟)检查工作负载状况，重新计算所需的VM实例，以调整(添加或删除)所分配的VM数量，但当未来工作负载波动比较严重时，该方案未能得出较好的虚拟机资源分配方案.Maurer等人[2]设计了一种新的自适应和资源高效的决策方法，并根据工作负载的波动性，提出了基于规则的自适应知识管理方法来实现虚拟机的自主重构，但其未考虑资源成本最小化目标.Xie等人[7]提出了一种基于粒子群算法的资源配置和价格调整策略，根据工作负载的特点，设计了一个效用函数来评价服务质量.根据所有工作负载对资源的需求，由相应的资源代理动态调整资源价格，以获得每个工作负载的最大利润，但粒子群算法存在局部收敛问题，在计算资源配置与价格调整时，得到的方案无法代表整体最优解.Dhrub等人[8]了一种考虑QoS指标的动态调整资源分配的自伸缩模型，它在虚拟机级别执行资源更正，同时考虑使用不足和使用过度的情况，虽然该方法能够根据不断改变的负载对分配给应用程序的资源进行按需调整，但未综合考虑QoS与虚拟机租赁成本之间的关系，且未将未来复杂波动的负载变化情况考虑到方法中.Chen等人[9]提出了一种适用于云计算环境下软件服务的自适应资源管理框架，该框架由3部分构成，首先通过历史数据训练QoS预测模型，其次采用基于PSO的运行时决策算法结合QoS预测值来确定未来的资源分配操作，再通过引入反馈控制使资源分配达到预期效果，但其在计算QoS预测值时，未考虑未来负载的影响.
对基于云资源的系统应用来说，应用的负载情况是影响资源分配的主要因素之一.在云环境中，预测工作负载对于更有效地分配资源是可行的.仅通过当前负载来进行资源分配，其有效性受到未来负载波动的影响，而通过预测工作负载[10-12]来提高资源分配有效性则受到工作负载预测模型精度的影响.针对以上问题，受Wang等人[13]的启发，本文提出一种面向负载时间窗口的云软件服务资源自适应分配策略，并在此基础上建立优化虚拟机资源分配方案计算模型，在进行资源分配时，将当前的负载以及窗口内未来的负载加入模型计算过程中，使用基于PSO-GA的运行时决策算法搜索合适的资源分配方案.该模型旨在提高云软件服务的自适应资源分配的有效性.由于工作负载的变化是给定的，因此本文的模型是正交于工作负载预测的，可以与现有的负载预测模型相关联.
本文的主要贡献如下：
•对面向负载时间窗口的资源分配进行形式化定义.
•使用基于PSO-GA的运行时决策算法，结合QoS预测模型，根据面向负载的时间窗口，搜索目标资源分配方案，并对当前分配方案作出调整.
•我们在RUBiS基准上评估我们的方法.实验结果表明，该方法能够提高资源分配的有效性.
本文剩余的部分由以下内容构成，第2部分进行问题的形式化定义.第3部分整体概述了方法的实现框架，并详细介绍PSO-GA算法，其中包括算法中变量的定义以及具体实现，然后介绍如何根据算法结果调整资源分配方案.第4部分实例研究，报告了我们的方法与其他方法在RUBiS基准上不同指标进行对比的实验结果.第5部分对本文进行总结.
2 问题定义
在这部分，我们对问题进行形式化定义.
当运行的环境变化的时候，云中软件服务就会有不同的服务质量(Quality of Service，QoS).而运行环境变化在本文中主要分为外部环境变化与内部环境变化.外部环境变化是由外部因素造成的，内部环境变化主要是受管理系统影响.在本节的问题定义中，有两个主要的因素，如表1所示.
表1 问题定义中的主要元素
外部因素主要指系统工作负载.假设负载是一个分段函数，每个时间段的负载不变，如式(1)所示：
(1)
我们假设每段负载持续的时间是相等的，并由二元组表示：wi=
内在因素指的是由不同类型与数量的虚拟机组成的分配方案.由于虚拟机在租赁的时候是按小时来收费，所以我们假设虚拟机每次租赁一小时，且一小时后自动关闭.则我们在调整虚拟机分配方案时刻，只需考虑增加的虚拟机方案.对应于每个时段的负载，虚拟机增加方案可以表示为：
(2)
假设每个调整方案中有m种可增加的虚拟机类型Type=<1，2，3，…，m>，则ti时刻增加虚拟机配置方案addi可以表示为：
(3)
对应于增加虚拟机分配方案的是每个时刻调整后的虚拟机分配方案：
(4)
其中q=1h/Δt，表示最大的未过期增加虚拟机分配方案的数量.Δt=ti+1-ti，表示每种负载持续的时间段.由公式(4)可知，每个时段的虚拟机分配方案是由对应时段未到期的所有增加虚拟机方案相加得到.
当为云系统应用分配资源时，云工程师或者自适应系统的目标是需要权衡分配方案对应的服务质量QoS与资源耗费Cost之间的关系.我们通过目标函数来表示它们之间的关系.
目标函数的其中一个参数为QoSi，它表示ti时刻的QoS值，通常使用服务等级协议(Service-Level Agreement，SLA)来指定，包括响应时间(Response Time，RT)，数据吞吐量(Data Throughput，DT)等等.响应时间表示用户请求服务的时候，等待服务响应所需时间.而数据吞吐量表示在一个给定时间系统能够处理的信息量.但是这些指标无法用来预测系统的QoS值，因为只有分配完虚拟机资源后，这些指标才能被监控到.于是就需要一个QoS预测模型[13，14]，如公式(5)所示，该模型的输入包括请求数量与类型(w)，虚拟机数量与类型(vm)，输出为QoS预测值.
QoSpredicted=QoS(w，vm)
(5)
通过该QoS预测模型，给定一个负载w与资源配置方案vm，模型就能够预测出对应的QoS值.
函数的另一个参数为Costi它表示ti时刻负载区间对应的增加虚拟机addi的成本.假设每种类型虚拟机租赁消费P=
(6)
那么目标函数可以通过QoSi与Costi表示为：
(7)
公式中r1与r2代表权重，是由工程师根据经验进行选定.
然而，在实际环境中，仅通过当前的负载计算出的对应资源分配方案有效性无法得到保障，于是，我们需要使用面向负载的时间窗口，根据窗口内的负载给出对应的增加虚拟机分配方案，进而求出对应时刻的虚拟机分配方案.
面向负载时间窗口，在进行资源分配的时刻，时间窗口能够观察相对于当前时刻之后的一段负载，进而对资源进行相应调整.
假设窗口i能够预测到长度为l(包含的区间数量)的工作负载区域，结合公式(1)，该区域内的负载Wi可表示为：
(8)
与负载窗口Wi对应的是窗口内增加虚拟机分配方案ADDi，它表示为：
(9)
那么根据公式(9)，窗口内虚拟机分配方案VMi可表示为：
(10)
于是，问题就转化为搜索窗口内一个最优的增加虚拟机资源分配方案.由于该问题是一个经典的组合优化问题，在理论上属于np难题，所以，我们可以使用启发式算法基于适应度函数来搜索一个合适的资源分配方案.
3 方 法
本节介绍方法的实现，整体架构如图1所示.
图1 方法概览图
3.1 方法概览
本文介绍了面向负载的时间窗口，并通过负载窗口计算虚拟机资源分配方案，如图1所示，可以分为以下几个部分：
首先，初始化时间窗口参数，其中包括时间窗口对应的负载、负载对应的增加虚拟机分配方案以及虚拟机分配方案.其次，我们使用PSO-GA算法，在QoS预测模型的支持下，搜索窗口内的目标资源分配方案.最后，根据目标资源分配方案，对当前的虚拟机分配方案作出相应调整.
3.2 PSO-GA搜索目标资源分配方案
3.2.1 粒子群优化算法(PSO)
PSO算法[15，16]属于进化算法的一种，通过模拟自然界鸟群迁徙的活动，让粒子不断地迭 代从而寻找最优解.粒子在PSO算法中是非常重要的概念，每一个粒子代表优化问题的一个候选解，粒子通过自身历史最优值与族群历史最优值不断在解空间中迭代更新.式(11)是粒子的速度公式，式(12)是粒子的位置公式.
(11)
(12)
3.2.2 遗传算法(GA)
GA算法[16]是通过模拟生物界中生物进化过程的计算模型.遗传算法同样从随机解出发，按照自然界优胜劣汰的原则，通过上一代优秀个体的组合交叉和变异过程，逐代演化生成越来越好的下一代个体，从而找到更优的近似解.
3.2.3 基于PSO-GA的目标虚拟机资源分配方案搜索策略
本章提出一种改进的粒子群算法PSO-GA，PSO-GA算法通过引入PSO算法对粒子个体的优化过程，使GA算法中的粒子个体得到优化，从而解决了GA算法搜索后期效率低下的问题.PSO-GA算法先通过粒子的适应度评价函数对粒子进行排序，保留其中优秀的个体用于下一次PSO算法迭代，而淘汰表现较差的个体.通过对优秀个体的交叉与变异操作得到剩下的粒子，进入下一代.在本章中，一个粒子只是代表一个时间窗口内的解，每经过一个固定的时间间隔，通过PSO-GA求出一个最佳的粒子当做该时刻的目标虚拟机资源分配方案.下面对改进粒子群算法中的粒子编码、适应度函数、以及更新策略进行设计.
3.2.4 粒子编码
对于云软件服务资源分配问题的编码，本章采用离散编码方式对PSO的粒子进行编码[17].对于时间窗口k，窗口内的增加虚拟机资源分配方案可以表示为：
(13)
其中l为时间窗口k的长度，它表示窗口内增加虚拟机资源分配方案的数量.
将窗口k内增加虚拟机分配方案ADDk作为粒子X，一个粒子代表窗口k对应的增加虚拟机资源分配方案.假设窗口中虚拟机类型有m种，窗口长度为l，则第i个粒子的第t次迭代可表示为：
(14)
图2展示了长度为3，虚拟机种类为3的时间窗口内的一个粒子编码.它表示窗口中第1个增加虚拟机分配方案为[011]，第2个增加虚拟机分配方案为[014]，第3个增加虚拟机分配方案为[001].
图2 增加虚拟机资源分配方案粒子编码
3.2.5 适应度函数建立
在引入时间窗口之后，适应度函数需要通过窗口内的负载以及虚拟机资源分配方案来计算.假设时间窗口的长度为l，则窗口i内的负载Wi可表示为：
(15)
由公式可以看出，窗口i内的负载是分段函数.
时间窗口i内的虚拟机资源分配方案VMi需要通过窗口i内增加的虚拟机资源分配方案ADDi计算得到，ADDi如公式(16)所示：
(16)
则VMi可表示为：
(17)
由于我们已经对窗口i内增加的虚拟机资源分配方案ADDi进行粒子编码，所以VMi可以通过粒子编码计算得到.
窗口内增加虚拟机资源分配方案通过fitness函数进行评估.fitness函数在QoS值与资源成本Cost之间进行权衡，能够指导粒子群优化算法搜寻求解的方向.由于引入了时间窗口，则由上述公式，fitness函数可表示为：
(18)
fitness函数中的QoS值为窗口i内总的QoS值，如公式(18)前半部分所示，其中wk∈Wi，表示窗口i内l个时段中某个时段的负载.而vmk∈VMi，表示窗口i内l个时段中某个时段的虚拟机资源分配方案
于是，根据时间窗口i内的负载Wi以及虚拟机分配方案VMi中每个时段对应的wk与vmk，通过QoS预测模型(式(5))，分别计算出QoS，然后再对这l个QoS求和，就能得到窗口i内总的QoS值.
另外，它们的权重r1与r2是专家通过对不同系统的需求而定的.且从公式中可以明显看出，窗口内越好的增加虚拟机资源分配方案，所对应的评估值也越小.因此，在给定窗口i内的负载Wi以及ADDi对应的粒子编码后，我们就可以通过fitness函数计算出对应的评估值.
3.2.6 粒子更新策略
我们通过遗传算法的交叉变异过程来更新整个粒子群的状态.
变异操作随机选取粒子中的一个基因段，不规律改变其基因值，且新值必须都在对应的阈值内[18].图3为对图2粒子编码的变异操作，随机选择粒子的一个基因段mg1，mg1位置上的值由(0，1，4)变异为(0，2，3)，该变异符合虚拟机分配准则.
图3 粒子编码惯性部分变异
图4为局部(或全局)最优粒子部分的交叉操作[19]，随机产生两个交叉的基因段位置cg1与cg2，将这两个基因段内的值替换为pBest(或gBest)对应基因段的值.在更新过程对于局部(或全局)最优粒子的交叉概率都为50%.
图4 粒子编码局部(或全局)最优粒子部分的交叉操作
3.2.7 算法流程
如PSO-GA算法所示，搜索目标虚拟机配置方案的流程如下：
Step 1.随机初始化粒子种群，其中包括种群规模大小N、最大迭代次数以及种群本染色体addi，并初始化每个种群的局部最优解pBesti以及全局最优解gBest，如算法2-6行.
Step 2.在满足算法执行条件下，通过粒子的交叉变异操作对粒子群进行更新操作，通过公式(13)计算每个种群染色体addi的评估值，并更新全局最优与局部最优染色体，如算法7-16行所示.
Step 3.输出最终的全局最优解gBest.
算法.PSO-GA
输入：种群规模N
输出：满足执行条件下的一个全局最优解gBest
1.procedure PSO-GA
2.foreach particlei
3. Initialize velocityaddifor particlei
4. Evaluate particleiand setpBesti=addi
5.endfor
6.gBest=min{pBesti}
7.whilenot stop
8.fori=1toN
9. update particleibymutateandcrossover
10. Evaluate particlei
11.ifFitnessi(addi) 12.pBesti=addi 13.ifFitnessi(pBesti) 14.gBest=pBesti 15.endfor 16.endwhile 17.printgBest 18.end procedure 于是，在每个资源调整的时刻，通过PSO-GA算法在窗口内搜索目标增加虚拟机资源方案，该方案是在满足算法执行条件下搜索到的适应度函数值最小的方案，可以表示为： (19) 我们在RUBiS[20]基准上评估我们的方法.评估的目标是：基于面向负载的时间窗口，通过比较PSO-GA算法与其他两种方法计算出来的目标虚拟机分配方案的各项指标，评估PSO-GA算法的性能. RUBiS是一个模仿eBay.com的拍卖网站原型，通常用于评估应用服务器的性能可伸缩性[20].它提供了一个客户端，可以为各种工作负载模式模拟用户行为.我们假设工作负载量在[2000，7000]范围内，并且工作负载中有两种类型的任务(读与写).实验中使用到的虚拟机分为小中大3种类型，每种配置方案都是由虚拟机数量与类型构成的，具体的虚拟机信息如表2所示. 表2 虚拟机类型及价格 在实验中，我们通过一个Sigmoid函数将响应时间(RT)的值映射到[0，1]的时间间隔，其值实际上是QoS值，根据经验数据，映射的QoS值(代表客户对服务质量的满意度)与响应时间的函数如图5所示. 图5 QoS映射图 本实验在已知一段时间内连续的负载前提下进行的.这里，我们定义Wi={wi，wi+1，wi+2}，时间窗口长度为90分钟(窗口内包含3段负载)，每30分钟预测一次.并设置了实验场景验证方法的性能. 图6是负载情况图，我们一共预测了540分钟的时间，为了使预测趋于稳定，假设540分钟后的负载是无法观测到的.对于每个时间段的负载，在其下方都有对应的读写比率. 图6 工作负载情况图 如公式(18)所示，适应度函数表示云工程师给出的资源分配目标.较好的资源配置方案应获得较小的适应度函数值.云工程师预先定义的权重(r1和r2)反映了他们对服务质量和资源成本的不同偏好.在实际应用中，最常见的适应度函数是平衡服务质量和资源成本，由于云服务的服务质量和资源之间的复杂关系，这一点也很难实现.因此，在实验中，我们根据我们的经验设置r1=900和r2=1/6，以平衡QoS和资源成本，如公式(20)所示： (20) 我们在面向负载时间窗口计算目标虚拟机资源分配方案的过程中，使用3种方法进行实验： a)贪心算法.贪心法不考虑时间窗口中负载的变化，在每次计算虚拟机资源分配方案的时候，都是以上一时刻的最优配置计算当前时刻的负载对应的最优虚拟机配置. b)单点最优局部随机法.分成两个阶段来进行.首先，一个时间窗口内的负载区间Wi中包含3个负载，对于每个负载，我们依据Fitness函数，遍历所有虚拟机配置方案，找到对应的一个评估值最小的方案，我们称之为单点最优配置方案.其次，根据单点最优配置方案，在其附近随机增减2台虚拟机来进行实验.在设定的运行时间内，得到窗口i内最优的一个虚拟机资源分配方案. c)PSO-GA算法.初始化时间窗口对应的增加虚拟机ADDi的染色体，设定种群规模为50，迭代次数为100，每次迭代通过公式(18)计算每个粒子染色体的评估值，并选出全局最优粒子与局部最优粒子，再通过概率都为50%的变异交叉对粒子的染色体进行更新操作.在满足算法执行条件的前提下，继续进行更新后的粒子评估值计算，以及迭代更新. 我们设置单点最优局部随机法与PSO-GA算法执行的时间都为2分钟，进而比较上述3种实验方法的性能. 我们分别对单点最优局部随机法、贪心法以及PSO-GA在给定的负载场景下进行实验.对应的虚拟机分配结果如图7至图9所示，其中位于图上方的表格表示每个时刻对应的增加虚拟机分配方案，条形图表示每个负载根据增加虚拟机分配方案调整过后对应的虚拟机分配方案，它们由小中大三种虚拟机组成. 图7 贪心算法实验虚拟机资源分配结果 图8 单点最优局部随机法实验虚拟机资源分配结果 图9 PSO-GA实验虚拟机资源分配结果 为了更好的评估我们的方法的性能，我们将QoS值、成本以及公式(20)所获取到的评估值一起作为资源分配有效性的评估指标，这可以证明我们的方法总体上提供了最合理的资源分配计划. 图10表示系统的总体Fitness值，它是由0-360分钟内各个时段的评估值相加而来.从这个图中可以看出，我们的方法比贪心算法跟单点最优局部随机法的性能分别高出5.74%和4.15%.这些性能增益主要是由于PSO-GA算法既注重了种群每一代之间的进化过程，又注重了优秀个体的保留与再成熟，提高了种群多样性，计算出来的虚拟机资源配置更接近最优资源分配方案.而单点最优局部随机法，虽然是基于单点最优进行随机实验，但搜索没有目的，具有随机性，无法更好地向最优的资源配置方案靠近，贪心算法由于每次只考虑当前负载的最优资源分配方案，所以，其计算出来的方案会随负载的波动而波动. 图10 总体Fitness值比较 另外，从图11可以看出，就QoS而言，PSO-GA计算出来的配置方案的平均QoS值为0.96，比其他两种方法的平均QoS值好，且在0～360分钟内，QoS值维持在0.91～0.99之间，特别是在60～150分钟负载快速上升阶段，我们可以看到基于PSO-GA算法的虚拟机资源分配方案能够将QoS值维持在一个合理的水平，且比较稳定.再观察贪心算法的QoS曲线，可以看出，它的QoS值波动比较严重，(在240分钟的时候达到0.95，而到120分钟时，降到0.77)而单点最优局部随机法的QoS值在0.80～0.94之间，平均QoS值介于两者之间，为0.89.其次，我们比较了PSO-GA算法与其他两种对比方法的资源成本，如图4～图7中的条形图所示，贪心算法在0～360分钟内的每个时段的平均成本为89.24 RMB，单点最优局部随机法为91.94 RMB，而我们的PSO-GA的平均成本最高，为102.65 RMB.可以发现，在保证服务质量的前提下，PSO-GA算法的资源成本是我们能够接受的. 图11 QoS与Cost比较 最后，我们比较3种实验方法的执行时间，可以明显地看出，在同样执行2分钟时间的前提下，PSO-GA算法在计算虚拟机资源分配方案的性能上比单点最优局部随机法要好.虽然贪心算法计算虚拟机资源分配方案的速度是3种方法中最快的，但是，其虚拟机资源分配方案的各项指标比较差. 在进行资源分配的时候，通过每个时刻负载来计算资源分配方案无法满足负载波动较大的云环境，且有效性无法得到保证.而使用面向负载的时间窗口，将当前的负载以及窗口内未来的负载加入计算，可以提高自适应资源分配的有效性.在本文中，我们提出面向负载时间窗口的云软件服务自适应资源分配策略，并使用PSO-GA运行时决策算法来搜索合适的虚拟机资源分配方案.然后，通过将PSO-GA算法与另外两种方法进行比较，验证算法的性能.实验结果表明，PSO-GA算法所表现出来的性能比其他两种方法更好. 尽管本文的方法计算出的资源分配方案有效性有所提高，但是文中使用的负载是通过离散分段函数来定义的，在实际环境中，负载更多时候是连续的，此时，通过时间窗口观察到的负载数量就比分段函数多，如何将窗口内的连续负载加入计算成为新的挑战.未来的研究方向主要有两点：一是结合实验中3种算法的优缺点，继续研究和改进算法，提高算法性能.二是引入连续负载函数，研究如何在连续负载环境中进行自适应资源分配.3.3 调整虚拟机资源分配方案
4 实例研究
4.1 实验环境
4.2 实验总体介绍
4.3 实验结果比较与分析
5 总 结
