单步启发式策略的备份虚拟机复用策略

陈鹏飞,李昕怡,齐勇,张小辉

(西安交通大学电子与信息工程学院,710049,西安)



单步启发式策略的备份虚拟机复用策略

陈鹏飞,李昕怡,齐勇,张小辉

(西安交通大学电子与信息工程学院,710049,西安)

针对云环境中的备份虚拟机(VM)利用率过低的问题,提出了基于不停歇多臂赌博机(RMAB)方法的备份VM分时复用策略,并给出了获得最优解的条件。该策略将每个备份VM形式化为具有“空闲”(1)和“占用”(0)两种状态的Markov过程,将多个备份VM的调度问题形式化为具有多个Markov过程的Markov决策问题(MDP),最终目标是期望在有限的备份VM数量下,最大化备份VM的利用率同时保证系统整体的可用性不会明显降低。然而,利用传统的动态规划方法求解该问题时会出现维度爆炸的现象,从而导致问题不可解,故将该Markov决策问题转化为RMAB问题,然后利用简单易操作的单步启发式算法进行求解,并通过计算单步最优获得长期最优解,在特定条件下该策略可以保证得到的解为最优解。模拟实验结果表明:所提方法将备份VM与服务VM之间的备份比例从1∶1扩展成1∶M(M≫1),同时保证失效VM的恢复比率不低于96%,相应地备份VM的利用率显著提高;在VM失效率较低的条件下,备份VM利用率比1∶1备份时提高了89%;利用该备份VM调度策略,有助于减少整个云计算平台的建设和运维费用。

云计算;可用性;虚拟机迁移;不停歇多臂赌博机

云基础设施可以通过虚拟化技术弹性地管理计算资源,进行灵活地硬件资源共享,以节省硬件成本和能耗成本。但是,复杂的云计算软件栈中的bug、瞬息多变的运行时环境以及随机出现的硬件失效等导致云系统的可用性保障难度骤增。为了保障云应用的高可用性,云基础设施往往采用冗余备份的方式,为相关虚拟机(VM)实例提供一个或者多个备份实例。然而,过度的冗余备份会造成计算资源的浪费,增加云基础平台的运维成本。

长久以来学术界和工业界一直聚焦于寻求一种高效的VM预留或者整合策略,以提高用于生产即直接提供服务的虚拟资源或者硬件资源的利用率,如文献[1-2]等通过设计新的任务调度器或者虚拟机调度器,达到提高资源利用率的目的。为了达到VM的k-resilient[3]即允许k个物理机同时失效,每个VM至少需要提供k个备份。假定在最弱的容错条件下即1-resilient,有n个VM提供服务,云基础平台共需要分配2n个虚拟机,如果采用热备份,计算资源和能耗是没有容错情况的两倍。然而,对于单个VM来说失效是稀疏事件,备份VM大部分时间处于空闲状态,如果利用空闲的备份VM对其他需要备份的VM进行备份,即对备份VM进行分时复用,可以减少备份VM的数量,同时减少能耗。解决该问题的难点包括:①大规模的云环境中包含成百上千的备份VM,每个备份VM都有各自特定的变化规律,如果把每个VM形式化为一个变量,问题最终形式化为超高维资源优化分配问题,而对此问题的精确求解几乎是不可能的,因此如何设计算法通过降维或者问题分解的方法解决超高维优化问题是主要难点;②在云环境中,任意时刻都会出现多个VM失效,如何保证尽可能多的失效VM得到备份,也是问题的难点之一;③由于VM失效是动态变化的,因此要求调度策略可以实时在线决策,在每个时间槽内能快速输出调度结果;④调度策略在保证备份VM得到充分利用的同时,不能明显影响到系统的整体可用性,在有限的备份VM条件下计算出能够进行备份容错的VM上限也是难点之一。

针对以上问题及难点,本文将备份VM复用问题形式化为包含‘0’、‘1’两状态的不停歇多臂赌博(RMAB)问题[4],通过将m维的优化问题分解为m个一维优化问题,给出了VM失效模型已知情况下的优化算法,并给出了算法最优解条件。模拟实验结果表明了本文提出的方法的有效性。

1 虚拟机备份

软件系统运行过程中,由于受到软件自身Bug、硬件损坏、断电以及其他外界环境变化的影响,会出现性能下降和失效现象。软件失效的特征规律在软件可靠性领域一直是个开放性话题,目前广泛采用的失效模型(两次失效之间的间隔时间分布)有Weibull分布[5]和Poisson分布[6]。软件出现失效后,系统管理员会采取一定的措施,例如重启等恢复系统,恢复时间通常服从Lognormal分布[5]。从软件的长期运行过程看,软件系统一直处于“失效-恢复”的循环过程中。本文主要讨论失效时间符合Weibull分布和Poisson分布、恢复时间符合Lognormal分布时的情况。

为了保障云平台的可用性,大量VM用于冗余备份。冗余备份的方式主要分为热备份和冷备份,热备份是指主服务VM实例与备份VM同时运行在多台物理机上,两者之间的运行状态时刻保持同步,例如Remus[7]等;冷备份不需要主服务VM与备份VM同时运行以保持运行状态的一致性,而是当主服务VM需要备份时,备份VM再启动,运行状态或者负载从主服务VM拷贝到备份VM。本文只讨论该种备份方式,利用虚拟机在线迁移技术(live migration),将即将失效的VM迁移到备份服务器上,等VM恢复后备份VM关闭,原VM提供服务,采用这种方式既能保证软件运行时状态的一致性又能减少软件的悬停时间。

针对备份资源的有效利用问题,文献[8]设计了Yank系统,可以利用一个备份服务器对多个Transient服务器进行备份,但是当VM转移到Stable服务器上后,仍然是1∶1的备份,与本文强调的对备份系统的分时复用策略不同。文献[9]讨论如何通过减少备份供电基础设施,例如UPS等,达到降低数据中心建设成本的目的,与本文的核心思想一致。本文第一次利用RMAB模型,对备份虚拟资源进行有效利用。

2 单步启发式策略

2.1 问题形式化

本文提出的策略适用于以下场景:一部分VM拥有专属的备份VM,称之为高优先级VM,当高优先级VM需要备份时,可以立即迁移到相应的备份VM上;一部分VM没有专属的备份VM,称之为次优先级VM,当次优先级VM需要备份时,依据本文提出的调度方案选择合适的备份VM进行迁移,如果出现高优先级VM与次优先级VM争用备份VM情况,高优先级VM优先调度。

开始阶段,云系统为特定的N个高优先级VM按照1∶1的比例分配了N个备份VM,以保证这些VM的高可用性,备份VM是这组高优先级VM状态的直接反映即高优先级VM正常,备份VM空闲;高优先级VM异常,备份VM忙碌,因此在后续部分,本文不再关注这N个高优先级VM的状态,而只关注N个备份VM的状态。每个备份VM的状态按照独立同分布的Markov过程演化,令sj(t)和Sj分别表示备份VMj(j=1,2,…,N)在t时刻的状态和状态空间,令Pj表示备份VMj的状态转移矩阵,S(t)={sj(t),j∈{1,2,…,N}}表示N个备份VM在t时刻的状态。用状态‘1’表示备份VM空闲,‘0’表示备份VM被占用,则备份VM的状态演化过程可以表述为包含‘0’、‘1’两状态的Markov过程。其中,sj(t)∈{0,1},S(t)∈{0,1}N,Sj={0,1},状态转移矩阵为

在t时刻感知这N个备份VM状态,选择当前状态为‘1’的备份VM,利用这些备份VM可以为其他失效VM提供备份。

(1)

π:Ω(t)→A(t), |A(t)|=K,t=1,2,…,T

本文目的在于寻找最优策略π*,最大化有限时间区段或者无限时间区段的折现回报值为

(2)

式中:β为折现因子,0≤β≤1,表示当前的决策产生的后续回报比即时回报的价值小;Rπ(Ω(t))表示信念状态为Ω(t)时,采取策略π产生的回报;Ω(1)为初始信念状态,当T为有限值时,为有限时段的决策,当T→∞时,为无限时段的决策,本文只讨论有限时段的决策。

为了评价算法的优劣,本文提出了失效VM的恢复率、备份VM的利用率增量和丢失的回报值3个度量指标。假设在t时刻失效的次优先级VM的个数为ft,在T个决策时间槽内策略π产生的失效VM的恢复率定义为

备份VM经过分时复用后的利用率比只为高优先级VM提供备份时增加了,在决策时间长度T内,策略π产生的备份VM的利用率增量定义为

ind

丢失的回报值定义为

式中:μj(t)为t时刻将所有备份VM的回报值按序排列后的第j大回报值,不失一般性地令

μ1(t)≥μ2(t)≥μ3(t)≥…≥μN(t)

2.2 问题求解

本文将备份VM的调度问题转化为不停歇的多臂赌博问题,解决不停歇的多臂赌博问题的核心思想是将一个M维的超高维优化问题分解为M个一维优化问题,计算复杂度大大降低,本文利用该思想进行求解,提出了单步启发式算法,并对解的最优条件进行了分析。

针对VM失效模型已知的情况,本文提出了“单步启发式复用策略”。求解式(2)的最优解,可以采用动态规划的方法迭代求解,有限时段T内的值函数为

式中:Vt(Ω(t))表示从t(1≤t≤T)时刻到T时刻期望的最大回报值;ε表示决策A(t)中备份VM状态为‘1’的集合,A(t)ε表示决策A(t)中备份状态为‘0’的集合,信念状态Ω(t+1)按照式(1)更新。由于云系统中备份VM的数量巨大,信念状态Ω(t)的状态空间过于庞大,导致很难给出值函数的最优解,因此本文采用单步启发式复用策略,最大化当前决策产生的即时回报值,而不考虑决策对系统未来状态产生的影响,计算复杂度大大降低,但是解的最优性难以保证,因此本文讨论了单步启发式复用策略的最优性条件。

单步启发式复用策略的求解目标不再是式(2),而是退化为

(3)

只需计算在t时刻使得即时回报R(Ω(t))最大化的策略π,即将所有备份VM在t时刻的即时回报R(ωj(t))(1≤j≤N)按照降序排列,选择前K个最大回报值对应的备份VM,该算法实现了从N维优化到一维的降维目标。在利用单步启发式复用策略求解之前,需要根据VM失效模型计算出备份VM的状态转移矩阵以及初始信念状态Ω(1)。

通过Markov稳态方程计算出稳态情况下,备份VMj处于‘0’、‘1’的概率为

单步启发式VM复用过程如下。

输出:从t到t+T之间选择出备份VM序列。

(1)计算每个备份VM的转移矩阵P以及初始信念状态Ω(1);

(2)在t时刻对所有备份VM的信念状态进行排序;

(3)选择前K个信念状态最大的备份VM;

(4)感知由步骤(3)选出的K个备份VM的状态,将失效VM调度到状态为‘1’的备份VM上;

(5)根据式(1)更新信念状态,计算t+1时刻的调度决策;

(6)重复步骤(2)～(5)直至t+T时刻。

2.3 最优解条件

文献[10]采用相同的方法求解机会频谱访问问题(OSA),证明了当p11>p01时,利用启发式算法求解OSA问题具有最优解。

定理1 对于具有两状态‘0’和‘1’的N个通信信道,且每个信道遵从独立同分布的Markov过程的OSA问题,无论从N个信道中选择一个还是K(1p01时,解是最优的。

证毕。

2.4 复杂度分析

由单步启发式算法的描述可以看出,算法主要包括对备份VM信念状态的排序过程和对备份VM状态的更新过程。给定N个备份VM,决策时间长度为T,采用快速排序方法,在一个时间槽内排序过程的时间复杂度为O(NlogN),状态更新过程的时间复杂度为O(N),总的时间复杂度为O(NlogN),因此在T个时间槽内的时间复杂度为O(T*NlogN)。与POMDP等方法的指数复杂度相比,单步启发式算法的时间复杂度大大降低了。

3 实验结果

首先,根据高优先级VM的失效、恢复规律,产生了备份VM的初始利用规律。为了模拟VM失效模型及恢复模型,利用Matlab按照“正常—失效”循环产生符合特定分布的随机数。“正常”随机数表示高优先级VM的失效间隔时间,也是备份VM的空闲时间;“失效”随机数表示高优先级VM的修复时间,也是备份VM的忙碌时间。然后,将随机数按照单位时间离散成‘0’、‘1’二值序列,表示特定时刻某个VM所处的状态,例如利用失效模型产生随机数4,二值化为“1111”,表示在4个连续时间槽内备份VM是空闲的。本文共模拟了N(N=50,100,150,200,500)个备份VM,每个备份VM的失效及恢复模型都是独立同分布的,且包含1 000个“0,1”值。在每个时间槽内(模拟时间单位为min),利用单步启发式复用算法选择K个备份VM,按照感知能力的不同,分析K取不同值时的算法性能,另外本文针对不同的次优先级VM失效率f,讨论了有限备份次优先级VM的数量上限。模拟实验程序采用Matlab实现,通过实验分析,回答了以下3个问题。

问题一 单步启发式算法产生的调度方案效果。

在此实验中,备份VM数量N为500,初始阶段每个备份VM空闲时间分别服从参数α=17、β=1的Weibull分布,忙碌时间服从参数μ=1、δ=0.5的Lognormal分布,每个VM的平均效率为0.05,模块可感知的备份VM数量为400,决策时间长度为1 000个时间槽。利用单步启发式复用策略得出的regret的对数如图1所示。由图中观察得到,regret的对数值随着决策时间增加呈现收敛趋势,说明单步启发式复用策略具有对数最优。这是因为随着决策次数增加,单步启发式策略不断感知新的备份VM的状态,单步更新的“信念状态”越来越能精确反映每个备份VM的“权重”,选择策略也渐进趋向最优策略。

图1 regret的对数随决策时间的变化曲线

图2展示了采用单步启发式策略对空闲的备份VM进行调度后,每个备份VM的利用率增量。从图中看出,单步启发式复用策略在上述场景下将备份VM的利用率平均提高了86.5%,使备份VM的空闲时段得到了充分利用,节省了资源。

图2 每个备份VM的利用率增量

问题二 当系统参量变化时,单步启发式算法产生的效果变化。

在云系统中,软件运行时的内外环境频繁变动,本文主要探讨了高优先级VM的失效率变化、失效模型类型变化、可感知的备份VM的数量变化对单步启发式复用策略的影响。

(1)失效率变化。本文通过调整失效模型或者恢复模型的参数达到调整失效率的目的。设定失效模型为Weibull分布,恢复模型为Lognormal分布,K=400,备份VM的数量为500。讨论表1中4种情况下单步启发式复用策略的效果。

表1 失效率及相应的模型参数

图3比较了不同失效率情况下,500个备份VM经过复用后的平均利用率增量。随着失效率的增加,备份VM的利用率增量逐渐降低。这是因为失效率增加后,每次经过单步启发式策略选择出的400个备份VM集合中状态为‘0’的备份VM增加,即与高优先级VM出现资源争用的情况增多,但即使在高失效率0.2的情况下,单步启发式复用策略仍然获得了71.7%的利用率增量。与利用率增量变化情况相似,regret也随着失效率增加而增加,如图4所示。

图3 不同失效率场景下的平均利用率增量

图4 不同失效率场景下的regret的对数的变化情况

(2)失效模型类型变化。固定失效率为0.05,K=400,备份VM的数量为500,讨论两种分布:失效模型采用参数λ为17的Poisson分布(d-1);失效模型采用参数α=17、β=1的Weibull分布,恢复模型均为参数μ=1、δ=0.5的Lognormal分布(d-2)。图5展示了d-1、d-2两种情况下备份VM的利用率增量,从图中可以看出,利用率增量相差并不大,平均增量都是0.84,说明单步启发式策略产生的效果在失效率相同的情况下与失效模型关系不大。这是因为失效和恢复模型都是单步启发式策略的已知条件,并据此进行单步状态更新。图6展示了d-1、d-2两种情况下备份VM在1 000个时间槽内的regret变化曲线,两条曲线几乎重叠,验证了上述结论。

图5 d-1、d-2两种情况下备份VM的利用率增量

图6 d-1、d-2两种情况下备份VM的regret的对数的变化曲线

(3)K值变化。固定失效模型和恢复模型,备份VM的数量为500,调整K值,观察单步启发式策略的效果。图7展示了失效模型参数α=17、β=1的Weibull分布,恢复模型参数μ=1、δ=0.5的Lognormal分布时备份VM的平均利用率随K值的变化情况,从图中可以直观看出,利用率增量随着K值增加而增加。这是因为K值决定了可感知的备份数量以及备份VM被调度的数量,被调度的备份VM数量越多,利用率增量也就越大,而且K与利用率增量之间遵循线性关系。regret的对数与K值之间却没有单调的线性关系,图8展示了VM失效率较低时的regret变化情况,regret的对数值随着K值增加而增加。但是,当VM失效率较高时,K=100、400时的regret对数曲线几乎重叠在一起,与K值之间不存在单调线性关系,如图9所示。

通过上述分析发现,单步启发式复用策略的决策效果受VM失效率以及可感知的备份VM数量K的影响较大,但是在失效率固定时不受失效模型类型的影响。上述3种因素与决策效果之间存在复杂的线性以及非线性关系,本文只给出了定性分析,定量关系将在后续工作中进行讨论。

图7 利用率增量随K值变化的情况

图8 VM失效率为0.05时regret的对数与K之间的关系

图9 VM失效率为0.2时regret的对数与K之间的关系

问题三 在满足可用性要求的前提下,备份VM能备份的次优先级VM数量的上限。

本实验设定备份VM的数量N=500,可感知的备份VM的数量K=400,失效模型采用参数α=17、β=1的Weibull分布,恢复模型采用参数μ=1、δ=0.5的Lognormal分布,讨论当次优先级VM在失效率为0.01、0.05、0.1、0.2时,备份VM可备份的次优先级VM的数量上限。图10展示了失效VM的覆盖率随次优先级VM数量变化的曲线。以失效VM覆盖率96%为基准,从图10中可以看出,当失效率为0.01、0.05、0.1、0.2时,500个备份VM可以备份的VM上限分别为9 000,8 000,6 000和2 000,备份比例为1∶18,1∶16,1∶12和1∶4,即使在次优先级VM频繁失效的情况下,备份比例仍可以达到1∶4。在保证失效VM被100%覆盖的情况下,单步启发式策略仍可以在次优先级失效率较高时获得1∶3的备份比。

图10 失效VM的覆盖率随次优先级VM数量变化曲线

本实验讨论单步启发式算法的运行时间与可感知的备份VM的数量K和备份VM的数量N之间的关系,算法的执行单步决策即T=1时的运行时间如表2所示。从表2可以看出,算法的执行时间处在ms级水平,完全可以做到实时决策,而且运行时间随着N值增加而增加,两者存在单调变化关系,但与K值之间不存在单调变化关系,说明单步启发式算法的执行时间与N相关但是与K无关。

表2单步启发式算法执行单步决策的运行时间ms

4 结 论

为了充分利用过度冗余的备份虚拟资源,本文提出了基于RMAB问题的单步启发式复用策略。该策略将单个备份VM描述为独立同分布的Markov随机过程,按照特定的概率转移矩阵进行单步状态更新,通过最大化单步回报达到备份VM利用率最大化的目的。此外,本文给出了在特定失效、恢复模型下的最优解条件,从理论上证明了单步启发式复用策略的最优性。模拟实验结果表明,单步启发式复用策略可以将传统的1∶1备份扩展成1∶M(M≫1),同时保证失效VM的恢复率不低于96%,相应备份虚拟资源的利用率显著提高。在VM失效率较低的条件下,备份虚拟资源利用率比1∶1备份时提高了89%,从而可以有效减少云计算平台的建设和运维费用。

[1] JAYASINGHE D, PU C. Improving performance and availability of services hosted on IaaS clouds with structural constraint-aware virtual machine placement [C]∥Proceedings of the 8th IEEE International Conference on Services Computing. Piscataway, NJ, USA: IEEE, 2011: 72-79.

[2] VERMA A, DASGUPTA G, TAPAN K, et al. Server workload analysis for power minimization using consolidation [C]∥Proceedings of the 2009 Conference on USENIX Annual Technical Conference. Berkeley, CA, USA: USENIX, 2009: 28.

[3] BIN E, BIRAN O. Guaranteeing high availability goals for virtual machine placement [C]∥Proceedings of the 31st International Conference on Distributed Computing Systems. Piscataway, NJ, USA: IEEE, 2011: 700-709.

[4] WHITTLE P. Restless bandits: activity allocation in a changing world [J]. Journal of Applied Probability, 1988, 25(2): 287-298.

[5] SCHROEDER B, GIBSON G A. A large-scale study of failures in high-performance computing systems [J]. IEEE Transactions on Dependable and Secure Computing, 2010, 7(4): 337-350.

[6] OKAMURA H, TADASHI D, SHUNJI O. Software reliability growth models with normal failure time distributions [J]. Reliability Engineering & System Safety, 2013, 11(6): 135-141.

[7] CULLY B, LEFEBVRE G. Remus: high availability via asynchronous virtual machine replication [C]∥Proceedings of the 5th USENIX Symposium on Networked Systems Design and Implementation. Berkeley, CA, USA: USENIX, 2008: 161-174.

[8] SINGH R, IRWIN D, SHENOY P, et al. Yank: enabling green data centers to pull the plug [C]∥Proceedings of the 10th USENIX Symposium on Networked Systems Design and Implementation. Berkeley, CA, USA: USENIX, 2013: 143-155.

[9] WANG D, GOVINDAN S, ANAND S, et al. Under provisioning backup power infrastructure for datacenters [C]∥Proceedings of the 19th International Conference on Architectural Support for Programming Languages and Operating Systems. New York, USA: ACM, 2013: 177-192.

[10]AHMAD S, HAJI A, LIU M. Multi-channel opportunistic access: a case of restless bandits with multiple plays [C]∥Proceedings of the 47th Annual Allerton Conference on Communication, Control and Computing. Piscataway, NJ, USA: IEEE, 2009: 1361-1368.

(编辑 赵炜)

Multiplexing of Backup Virtual Machine Based on Single-Step Heuristic Policy

CHEN Pengfei,LI Xinyi,QI Yong,ZHANG Xiaohui

(School of Electronics and Information Engineering, Xi’an Jiaotong University, Xi’an 710049, China)

Based on the restless multi-arm bandit (RMAB) approach, a multiplexing strategy of backup virtual machines (VMs) is proposed to resolve the problem of low utilization of backup VMs in the cloud environment, and the optimal condition is given. This strategy regards an individual backup VM as a Markov process with two states, namely “idle” (1) and “backup” (0), and models the scheduling of multiple backup VMs as a Markov decision problem (MDP) consisting of multiple Markov processes. The goal of this strategy is to maximize the utilization of backup VMs without obvious reduction in the system availability under the constraint of limited backup VMs. However, this problem is computationally intractable with traditional dynamic programming methods due to the curse of dimensionality. Therefore, this paper transforms the original MDP problem to a RMAB problem and adopts a simple single-step heuristic policy to resolve it. By calculating the single-step optimal solution, the long-term optimal solution can be obtained. Under specific conditions, the optimal solution of this strategy is guaranteed. The results of simulation experiments show that the proposed policy can achieve the goal of extending the backup ratio between backup VMs to service VMs from 1∶1 to 1∶M (M≫ 1) while the failed VM assurance rate is no lower than 96%. Correspondingly, the utilization of backup resources is significantly enhanced. When the failure rate of service VM is low, the utilization of backup resources can be raised 89% compared with the 1∶1 backup. The building and operation costs of a cloud platform can be reduced with the help of this backup VM scheduling strategy.

cloud computing; availability; VM migration; restless multi-armed bandit

2015-05-10。 作者简介:陈鹏飞(1987—),男,博士生;齐勇(通信作者),男,教授,博士生导师。 基金项目:国家自然科学基金资助项目(60933003)。

时间:2015-11-04

网络出版地址:http:∥www.cnki.net/kcms/detail/61.1069.T.20151104.2222.002.html

10.7652/xjtuxb201601016

TP301

A

0253-987X(2016)01-0100-08