云计算中的服务可用性保障机制

沈时军，刘欣然,2，张鸿，朱春鸽,2

（1. 国家计算机网络应急技术处理协调中心，北京 100029；2. 北京邮电大学 信息安全中心，北京 100876）

1 引言

云计算通过虚拟化技术动态整合 IT基础设施与平台资源，利用互联网络为企业与个人用户提供按需的、廉价的计算、存储、软件、平台等服务。近年来，随着国外Amazon EC2、Google App Engine、Microsoft Azure及国内阿里云等一系列云计算产品的成功以及OpenStack、CloudStack、Eucalyptus、Open Nebula等许多开源云平台的推广，云计算已被认为是继大型计算机、个人计算机、互联网之后的又一次IT产业革命。

安全问题一直是云计算面临的最重要挑战之一，如数据泄密、服务可用性、拒绝服务攻击等[1,2]。虽然云计算因其良好的可扩展性被称为弹性计算，但当大量服务请求在同一时间到达时仍可能耗尽云计算平台中的所有资源。此时若有新的请求，特别是重要用户的请求到达时，将无法得到满足。考虑到投资回报，绝大多数云计算平台都不会长期维持大量的空闲资源，因此这种服务可用性的威胁无论在商业云还是私有云中都是常见的[3,4]。

为了应对这种服务可用性威胁，价格调控与资源预留是2种主要的手段。价格调控存在于绝大多数商业云中。服务商根据当前的资源紧张程度动态调整服务价格，使供需保持相对的平衡，减少资源耗尽的危险。例如在Amazon EC2中，服务商推出了按需支付(on-demand instance)服务、预约支付(reserved instance)服务、竞价支付(spot instance)服务3种不同的收费服务模式[5]。资源预留策略存在于各种云平台中。在一些私有云中，由于服务是免费的，价格调控无法进行，资源预留成为保障重要用户服务可用性的主要手段[6]。由于用户需求的不可知性，预留的资源过多可能造成浪费，预留的资源过少又可能无法满足用户需求。在文献[7]中，用户提前向云计算服务商预订可能用到的资源，服务商收集这些用户的需求后，通过资源新增、任务调度等手段，保证特定时间的资源可用性。由于用户通常很难回答“什么时间、需要多少资源”，这种策略可能有一定的局限性。

文献[6]指出，“在没有价格调控的情况下，如何既保证重要用户的请求得到满足，又不因资源过度预留而造成浪费，是云计算中的重要挑战之一”。本文提出了一种云计算中的服务可用性保障机制——基于滑动窗口的资源预留(SWRR,sliding window based resource reservation)算法。它将云平台用户提交的任务分为普通任务与重要任务(VIP任务)。SWRR的基本思想是：在云计算平台中为VIP任务预留一定数量的优秀资源，并将这部分优秀资源在整个资源池中所占的比例称为窗口。窗口的“滑动”包含 2层含义：1）窗口大小动态变化，即在VIP任务增加时扩大窗口以保证优先调度，在VIP任务减少时缩小窗口以减少资源浪费；2）窗口内容动态刷新，即每隔一段时间会评估窗口中的预留资源，淘汰差的资源，引入新的优秀资源。

SWRR已被应用于一个大型的云计算应用平台iVCE中，如图1所示。目前，该平台包含分布于全国各地的300多台物理机，可支持每天百万级的任务吞吐量。平台中用户每天提交的任务数随时间的波动很大且很难预测，在高峰时段大量的用户请求可能相互抢占资源，平台的服务可用性变差。为了体现差分服务的特点，iVCE授予某些用户提交VIP任务的权限，并采用SWRR优先调度。实际运行结果表明，SWRR可以保证VIP任务的服务等待时间（一般小于5 s）远小于普通任务（平均约60 s），保障重要用户的服务可用性。

图1 SWRR算法示意

由于在实际环境中直接调试 SWRR参数可能影响平台稳定性，本文实现了一个SWRR仿真器，并通过多方面的分析比较，论证 SWRR在资源预留、保障重要用户服务可用性方面的优势。

2 基于滑动窗口的资源预留算法

2.1 资源的定义

云计算平台中可用的资源集合记为Φ={ri| i=1,2,…,n}，该集合动态变化。对每一个资源ri，定义资源评价函数V(ri)为ri在过去一段时间内的任务执行成功率，V(ri)越大表示ri越优秀。

SWRR算法将Φ划分为普通资源池Φbase与预留资源池Φresv，分别存放普通资源与预留资源。初始时，Φbase=Φ，Φresv为空。

2.2 任务的定义

云计算平台中需调度的任务集合记为Ψ={tj| j=1,2,…,m}，该集合动态变化。对每一个任务tj，令I(tj)表示任务tj的重要程度，若I(tj)=true，表示tj为VIP任务；否则，为普通任务。

任务分为z个优先级，记为Z={1,2,…,z}。对每一个任务 tj，令 P(tj)表示任务 tj的优先级，则优先级为k的任务集合记为Ψk={tj|P(tj)=k,k∈Z}。任务集合 Ψk中的任务按先入先出（FIFO）算法组成队列，任务从队首开始调度。

2.3 SWRR算法

根据任务优先级的不同，用户提交的任务被保存在相应的任务队列Ψk中，并按照FIFO的顺序进行调度。SWRR算法包括任务调度与窗口滑动2个阶段，如算法1所示。

在算法的任务调度阶段，采用“轮盘赌”选择需要调度的任务队列Ψk，并且优先级k越大的队列被选中的概率越大。如果任务tj为VIP任务，优先在预留资源池 Φresv中查找资源，在Φresv查找失败后继续在Φbase中查找；如果任务tj为普通任务，则仅在Φbase中查找资源。标志位 fbase、fresv反映当前的资源池状态。当Φbase资源不足时，fbase=false；当Φresv资源不足时，fresv=false。

在算法的窗口滑动阶段，根据标志位fbase、fresv调整滑动窗口大小ω。如果预留资源池Φresv资源不足，则扩大滑动窗口；如果预留资源池Φresv资源充足并且普通资源池Φbase资源不足，则缩小滑动窗口；否则窗口大小不变。系统预设滑动窗口的最大值 ωmax、最小值 ωmin，ω∈[ωmin,ωmax]。在每一个调度周期结束后，根据V(ri)重新评估所有资源，并将 Φresv中最差的部分资源与 Φbase中最优秀的部分资源互换，以保证Φresv始终维持最优秀的资源。

算法1 SWRR算法

给定资源集合Φ，任务集合Ψ，滑动窗口大小ω。给定常数：滑动窗口的最大值ωmax、最小值ωmin，窗口调整步长ω'∈(0,1)，资源交换率λ∈(0,1)。初始时，令 ω=ωmin。

在每一个任务调度周期，进行如下步骤。

1)初始化标志位fbase=true，fresv=true。

2)采用“轮盘赌”算法选取一个需要调度的任务队列 Ψk（k∈Z）。

3)从Ψk中取出第一个需要调度的任务tj。

① 若tj为VIP任务，即I(tj)=true，则从Φresv中选取若干符合 tj条件的资源组成备选资源池Φ(tj)。

若Φ(tj)非空，从Φ(tj)中随机选取资源ri，将tj下发到资源ri上执行，然后转步骤4)。

若Φ(tj)为空，设置fresv=false，并将tj当成普通任务继续步骤3)中的②。

② 从Φbase中选取若干符合tj条件的资源组成备选资源池Φ(tj)。

若Φ(tj)非空，从Φ(tj)中随机选取资源ri，将tj下发到资源ri上执行，然后转步骤4)。

若Φ(tj)为空，设置fbase=false，增加tj的调度失败次数，将tj放回Ψk，然后转步骤4)。

4)循环进行步骤2)、步骤3)，直到本次调度时间结束，或者所有任务队列都没有需调度的任务。

5)确定新的滑动窗口大小ω。

① 若 fresv=false，则设置 ω=min(ωmax,ω+ω')。

② 若fresv=true并且fbase=false，则设置ω=max(ωmin,ω-ω')。

③ 否则ω不变。

6)令 a=|Φbase|表示普通资源数，b=|Φresv|表示预留资源数。从Φresv中选择V(ri)评价最差的λb个资源，从 Φbase中选择 V(ri)评价最优的 max{(a+b)ω−(b−λb),0}个资源，对以上两部分资源互换。

在算法1中，如果找不到合适的资源，任务tj调度失败后将重新被放回队列Ψk中。为了避免同一个任务不断地被选中调度，当任务tj调度失败后，它将等待一定时间才能被再次调度，并且等待时间随着调度失败次数的增长而指数递增。

SWRR算法具有如下特点。

1)自适应地资源预留。通过滑动窗口大小调整与资源交换，始终维持合适的预留资源，保证VIP任务的调度。

2)兼顾所有任务调度。通过限制滑动窗口大小ω∈[ωmin,ωmax]，保证普通任务的调度；通过“轮盘赌”算法，低优先级的任务也有被调度的概率。

3)对 VIP任务突发性激增的适应性。算法中滑动窗口调整到合适的位置需要一定的时间，为保证服务质量，若VIP任务暂时在Φresv中找不到资源时，将继续在Φbase中寻找。

3 仿真实验

本文实现了一个SWRR仿真器，并通过多方面的分析比较，论证SWRR在资源预留、保障重要用户服务可用性方面的优势。实验中，SWRR参数采用与云计算平台iVCE中相同的设置，即滑动窗口最小值ωmin=0.2、最大值ωmax=0.6，窗口调整步长ω'=0.02，资源交换率λ=0.2。在本节最后，会进一步讨论这些值的选择依据。

仿真中最大资源数|Φ|=1000，每个资源的性能在资源初始化时随机生成，该指标将影响任务的执行时间与执行成功率。实验通过一个任务生成器，每秒生成一定数目的 VIP任务与普通任务，以模拟用户提交任务的行为。每个任务在生成时会附带一个截止时间的属性，如果任务在截止时间到达时仍没有执行完成，将标识为失败，并以此统计任务执行成功率。任务在截止之前，如果没有找到合适的资源，它将处于等待状态，并以此统计任务等待时间。

仿真器运行于Linux平台。实验在运行稳定后，截取其中的60 min，并分析其结果。

3.1 SWRR算法性能

图2（a）给出了实验中每分钟的任务提交情况。参考云计算平台iVCE的任务提交行为，实验分别模拟了普通任务突发性激增（第10～11 min）、VIP任务突发性激增（第20～21 min）、普通任务与VIP任务持续高负载（第30～45 min）的情况。

实验可以分为5个阶段。

第0～10 min为第1阶段。此时系统资源足够，可处理所有的普通任务与VIP任务，系统处于平稳运行状态，滑动窗口ω约为0.24，如图2(b)所示。

图2 VIP任务与普通任务的运行比较

第10～20 min为第2阶段。在第11 min，普通任务出现激增，如图 2(a)所示，普通资源池 Φbase出现资源不足，滑动窗口ω降为最小值0.2，如图2(b)所示，以尽可能减少预留资源占用。但Φbase仍不能满足需要，大量普通任务的等待时间增加，如图 2(c)所示，执行成功率下降，如图 2(e)所示。在这个阶段，VIP任务的执行未受影响。在接近20 min时，系统再次趋于平稳状态。

第20～30 min为第3阶段。在第21 min，VIP任务出现激增，如图2(a)所示，预留资源池Φresv出现资源不足，滑动窗口 ω迅速升为最大值 0.6，如图2(b)所示。大量的VIP任务导致了任务等待时间的少量增加，如图2(c)所示，但VIP任务的执行成功率基本没有变化。在这个阶段，虽然普通任务在数量上没有变化，但滑动窗口调整导致普通资源池 Φbase变小，因此仍然对普通任务的等待时间、执行成功率造成影响，分别如图2(c)、图2(e)所示。

第30～45 min为第4阶段。在这个阶段，普通任务与VIP任务先后出现了增长，并持续了较长时间，如图2(a)所示，导致系统中的资源严重不足。为了优先满足VIP任务的调度，滑动窗口最终稳定在0.4左右，如图 2(b)所示。在这个过程中，VIP任务的执行基本没有受到影响，但普通任务的等待时间、执行成功率均受到了严重影响，分别如图2(c)、图2(e)所示。

第45～60 min为第5阶段。随着提交的任务数量回到正常水平，系统又回到平稳状态。

在图2展示的整个实验过程中，用户提交的任务数随时间波动很大，SWRR算法与资源池大小固定的算法相比的优势在于，它通过动态窗口滑动，合理资源预留，始终保证VIP任务一个较稳定的任务等待时间与执行成功率。

从图2(d)进一步看出，VIP任务的执行时间明显小于普通任务。这是因为SWRR算法通过资源交换，在预留资源池中维持了最优秀的资源。作为证明，图3给出了第5 min、第21 min时的滑动窗口快照。资源评分通过函数资源评价函数V(ri)得到，它反映了资源在过去一段时间内的任务执行成功率。从图3可以看出，SWRR算法总是将系统中评分最高的那些资源作为预留资源。

3.2 资源负载率

通过预留足够多的资源，一些静态的资源预留算法也能保证VIP任务的调度。文献[6]指出一个优秀的资源预留算法不仅要保证 VIP任务的及时调度，而且要减少资源浪费。图4给出了在上述实验过程中，普通资源池与VIP资源池的资源负载情况。

图3 滑动窗口快照

图4 资源负载率

对比图2(e)和图4可以看出，在资源不足而导致任务执行成功率下降的第12～15 min、第22～25 min、第35～45 min，仅在第12～15 min预留资源池的负载率未接近 100%，即存在一定的资源空闲。造成此现象的原因是在第12 min时，滑动窗口已达到最小值，如图2（b）所示，无法进一步缩小以将资源用于普通任务的调度，因此这不是SWRR算法本身的缺陷。

在实际部署时，滑动窗口最小值、最大值的设置都需要考虑具体的应用场景。窗口最小值设置过大可能造成资源浪费，设置过小可能瞬间不能适应VIP任务的激增；窗口最大值设置过小可能不能为VIP任务预留足够的资源，设置过大可能瞬间不能适应普通任务的激增。由于 SWRR算法可以自适应调整窗口大小（但需要一定的时间），在应用场景不能确定时，可以设置一个较小的最小值、较大的最大值。另外，窗口调整步长、资源交换率实际反映了算法的响应速度与调整粒度，一般来说，对于任务波动较大的场景，可以选择较大的窗口调整步长、资源交换率。

4 结束语

本文提出了一种云计算中的服务可用性保障机制——基于滑动窗口的资源预留算法。通过动态窗口滑动、合理资源预留，SWRR算法在兼顾所有任务调度的基础上，重点提升VIP任务的调度效率与执行成功率，保障重要用户的服务可用性。

SWRR算法已被应用于一个大型的云计算平台iVCE中。接下来的工作主要包括算法执行效率的优化，并对算法在实际系统中的性能进行更深入分析。

[1]SUBASHINI S,KAVITHA V. A survey on security issues in service delivery models of cloud computing[J]. Journal of Network and Computer Applications,2011,34(1): 1-11.

[2]CARLIN S,CURRAN K. Cloud computing security[J]. International Journal of Ambient Computing and Intelligence (IJACI),2011,3(1):14-19.

[3]PAWAR C S,WAGH R B. A review of resource allocation policies in cloud computing[J]. World Journal of Science and Technology,2012,2(3):165-167.

[4]ENDO P T,DE ALMEIDA PALHARES A V,PEREIRA N N,et al.Resource allocation for distributed cloud: concepts and research challenges[J]. Network,IEEE,2011,25(4): 42-46.

[5]Amazon elastic compute cloud(EC2)[EB/OL]. http://aws.amazon.com/ec2/.

[6]SEMPOLINSKI P,THAIN D. A comparison and critique of eucalyptus,opennebula and nimbus[A]. IEEE 2nd Int Conf on Cloud Computing Technology and Science[C]. Indianapolis,2010.417-426.

[7]FUNKE D,BROSIG F,FABER M. Towards truthful resource reservation in cloud computing[A]. IEEE Int Conf on Performance Evaluation Methodologies and Tools[C]. Cargese,2012.253-262.