包簇框架云资源分配规划

朱兵伟 陈世平，2

(上海理工大学光电信息与计算机工程学院 上海 200093) (上海理工大学信息化办公室 上海 200093)

0 引 言

随着虚拟化技术[1]和云计算的快速发展，大量高科技公司涌入云服务市场，如谷歌App Engine、亚马逊EC2、微软Azure以及苹果ICloud等。云计算市场规模越来越大，为服务于快速增长的异构需求和动态变化的用户群体，大量的数据中心建立起来。为保证数据中心的正常运转，与其配套的服务器设备、电力资源、冷却设备的数量急剧增长，同时也产生巨大的云设备运营支出和能源消耗[2]。因此，迫切需要新技术来降低高能耗以及提高资源利用率[3]。

每一个数据中心都有大量的服务器，每一台服务器需要多个CPU、本地缓存、内存、硬盘及其他资源，数据中心的管理在于：如何合理地将所有虚拟机映射到服务器，将对云资源的使用及能源管理有着重要意义。一方面，在复杂云系统资源限制的条件下，云服务商要满足所有用户需求就要启动更多的服务器，并且按照服务级别协议(SLAS)保证服务质量。另一方面，还要对其性能、开支、资源消耗，以及利润等目标进行优化。生活中资源需求会随时间变化，比如，一家公司白天需要许多虚拟机，但晚上需求量特别少，这时我们可将闲置服务器切换进入待机状态，尽量避免过多服务器处于“饥饿”状态。

与已有的研究不同，本文主要研究针对包簇框架下云资源预留分配规划问题，我们将用户需求定义为对虚拟机总需求量。通过在CloudSim仿真平台上的大规模云仿真实验[4]，验证了本文提出的方法。

1 相关工作

在云虚拟机调度算法中，轮回调度算法(Round robin)[5]思路清晰易于操作，准确评估了数据迁移算法的有效性及有效消除负载倾斜,但庞大的数据迁移造成很大开销。贪心调度算法(Greedy algorithm)[6]适用于周期性的负载模式或者负载相对稳定模式，因此，要考虑服务器负载的稳定周期，来减少迁移引起的不必要开销。除了这些经典算法外，国内外研究人员就云资源合理分配这一问题，提出了很多的分配方案。

文献[7]提出面向业务特征的自适应虚拟机迁移带宽分配算法，解决负载均衡中数据迁移问题，在控制负载倾斜的环境下，对迁移开销进行优化。但是服务质量(SLA)方面存在不足之处，一般而言，个人用户或企业会根据SLA协议要求云服务商保障服务质量，所以，SLA协议是云服务商优化资源配置的前提条件。文献[8]针对虚拟机调度均衡问题，提出基于遗传算法的负载均衡调度策略。该方法实现了最佳的负载均衡，减少或避免了动态迁移，从而解决了传统调度算法造成的负载均衡和高迁移成本问题。但是在实际的云计算环境中，虚拟机可能会有动态变化，而且随着虚拟机数量的增加，虚拟机的计算成本也可能会增加，并且会有一些无法预测的负载损耗。因此，需要一种监测和分析机制来更好地解决负载平衡的问题。文献[9]提出了基于时间序列工作负载预测的迁移策略，并且指出影响迁移时间成本的主要因素有内存大小、网络带宽、内存占用率等参数，有效地降低虚拟机迁移引起的额外能耗。但迁移过程中，当物理带宽使用量比较大时可能会导致大量缓存拥塞排队，并且还会有发送内存与业务运行抢占带宽的可能，增加了SLA的违反次数。文献[10]采用基于最佳适配递降算法进行分配虚拟机，VM按照当前利用率进行降序排列,再依次分配到最小能耗的服务器上。该方法主要利用VM实时迁移和关闭空闲节点，稳定了资源利用率，VM的重新分配节约了大量的能耗。其缺点是引起不必要的虚拟机迁移和增加服务器开关机次数，产生不必要的能耗。文献[11]通过提高资源利用率来控制云环境能耗，关闭闲置服务器和采用时间序列预测的方法来预测资源需求。该方法以资源利用率最大化为目标，但同时虚拟机迁移也会产生很高的额外费用，而且没有考虑关闭闲置的服务器来节约成本。

2 包簇系统架构

2.1 包与簇

“包”为虚拟机或其他包的集合(这是个递归定义，一个大包可以是许多小包的集合，而这些小包可能是虚拟机的集合，也可能是更小包的集合)[12]。包所需的内存大小，要体现对虚拟机有灵活性的要求，比如，对每台虚拟机的要求,分配VM的方式。该递归定义允许用户以一种层次结构形式组织自己的资源要求。

“簇”为数据中心拓扑中服务器位置相近或者级别更低的簇的集合。簇所拥有的资源是其组成部分的资源之和。用簇代表每个机架上的服务器，而且低级别簇聚合成高级别簇。要注意的是，每一个低级别簇实际上包含了大量的服务器，而每一个更高级别簇又包含了相当数量的低级别簇[12]。

包内部可能有很多VM，如何体现每一台VM上的资源有多大，比如内存多大。云资源只是分配给了包，如何体现在包内每一台VM获得的资源大小。单位是包，包可以分配给包，也可以分配给包内的VM，具体的VM如何拿到它需要的内存。

2.2 包簇框架

从图1可知,用户的需求可看作所需不同类型资源包(虚拟机)的数量，虚拟机与不同类型资源包相互对应的关系,用户的需求能被资源包内的虚拟机(VM)满足。同时，不同类型资源的包可根据自身资源需求在不同的簇(服务器)上部署和运行。

图1 框架结构图

每个用户可指定其包结构，或者仅指定最低级别的包，云服务商以一种树形结构把它们进一步组织成一个多层次的包结构。对于每一个已分配了包的簇，按包层次展开下一层的子包，按簇层次展开下一层的子簇，再把子包分配到相应子簇上。继续此操作，直至最底层虚拟机分配到最底层服务器。

用户需求是指所需资源包的个数，只要簇能给包提供足够的计算资源，比如：CPU、内存、缓存、带宽等，该包就能实现到该簇的映射。每个包都有一个最大和最小资源需求，簇按照它们最小资源要求进行分配，同一组包内虚拟机可以在分配的簇之间进行迁移和资源共享。

除了允许面向云服务系统和提高用户灵活性的优势外，包簇层次结构另一个主要优势是将一个大型复杂的资源管理问题分解为一系列的小问题，迅速解决并且可以并行解决。

2.3 包簇分配

任意一个簇ρ，该簇拥有N个子簇{H1,H2,…,Hn}，n为该簇中服务器的总数，任意一个包P，该包含有M个子包{V1,V2,…,Vm}。每个子包Vj表示对应所需资源总量的向量，每个子簇Hi表示对应可分配资源总量的向量。

对可用簇Hi资源(如：CPU,内存)的需求：capacitycpu(Hi)和capacitymemory(Hi)，其中i∈{1,2,…,n}，分别代表簇Hi中可进行分配CPU数量和该簇中可用内存大小。

对于∀包Vj，其中j∈{1,2,…,m}，

式中：cij表示某一包所需CPU数量。

式中：mij表示某一包所需内存大小。

需要满足式(1)、式(2)，每个簇Hi使用的资源总量绝对不能超过其资源拥有量，分配过程中，最好不引起迁移，否则增加不必要的费用，能保证距离近效率高的优点。

(1)

(2)

3 分配规划方法

3.1 服务器预留

存在一个数据中心，有m台服务器，承载n台虚拟机，要维持其正常运营需要庞大的能源和资金，用户群体的异样性和时间差异性，我们可以将一定时间内处于闲置的服务器转为待机状态，达到节能效果。这里须满足四个基本条件：

(1) 服务器的剩余资源要大于虚拟机请求的资源，且分配后服务器不能负载。

(2) 正常运行服务器数量有99%的把握来第一时间满足用户需求，99%从概率论角度提出，保证数据的科学性。

(3) 包优先放在同一个机架或者邻近的服务器，尽量启动少的设备，并且相邻的机架越近越好。

(4) 实现包内资源共享，最好在同一个服务器上或者相邻机架上。

这样可以节能，也可以保证时间，我们采用实时测量手段来监测每台服务器，将监测结果及时反馈给调度中心，首先对服务器性能进行监测，通过二次指数平滑法预测出CPU和内存资源的利用率，来检测服务器是否负载过重；然后通过中心极限定理预测出服务器正常运行的数量。

式中：at，bt为参数。

最后，得到主机i的使用情况：

其中，n1、n2分别表示CPU和内存利用率的权重。

由此可以知道主机是否负载，满足条件一。

再计算条件二：

将所有虚拟机编号，令：

令X表示这n万台虚拟机中在t时间(1≤t≤T)被申请的数量，则：

定理(中心极限定理) 设随机变量Xn～B(n,p),n=1,2,…,其中常数p∈(0,1),q=1-q。

定理表明，若X～B(n，p)，则当n充分大事有近似计算公式：

(3)

根据上述的近似计算式(3)可得:

(4)

中心极限定理又称大数定理，主要用于大量数据的计算，体现数据的科学性、准确性。根据式(4)可知，只需知道虚拟机数量n，就能计算出主机的数量k，满足条件二，然后再利用0-1背包算法对虚拟机分配，同时根据能耗公式进行比较。

3.2 包簇0-1背包算法

云资源的分配实质就是实现包到簇的映射，最低成本条件下获得最大的效益是我们的优化目标，本文研究的云资源整数规划可以看成多重0-1背包问题[13]。我们将每一个簇看成一个包，每一个包看成一个物品。首先，将最上层大型包映射给最上层的大型簇，每个簇应有足够的资源来支持映射的包的总需求。然后，针对每个簇及该簇所支持的资源包，将其下一级别的包映射到下一级别的簇，递归重复该过程，直到所有虚拟机被映射到服务器[14]。设定m个簇,n个包,m、n都为正整数，包j在簇i上运营的能耗为Cij,每个包所需总资源为aij,簇i所拥有的总资源为bi，设Xij∈{0,1}，表示簇i分配给包j的决策变量，则云资源整数规划问题为

(5)

(6)

(7)

xij∈{0,1}i=1,2,…,m,j=1,2,…,n

(8)

我们根据式(6)-式(8)对式(5)进行拉格朗日松弛，设乘子向量u∈Rn,则松驰问题为：

(9)

xij∈{0,1}i=1,2,…,m,j=1,2,…,n

xij∈{0,1}i=1,2,…,m,j=1,2,…,n

其中zi(u)是如下的最优值：

xij∈{0,1}j=1,2,…,n

4 仿真实验

云计算环境下CloudSim是一个具有现代化科学化的框架模拟仿真平台，它不仅支持应用管理建模，而且支持按需定义主机、虚拟机数量，还支持能耗建模为核心的框架，将任务分配到指定的虚拟机上工作，完成对不同算法的模拟测试。

4.1 环境搭建

利用扩展仿真模块来支持包簇系统构架，包簇递归的特定0-1背包算法在服务器之间合理分配虚拟机。实验运行硬件环境：一台PC机，Linux系统，CPU 主频2.4 GHz，内存8 GB。对本文提出的方法进行仿真实验，前提设定主机和虚拟机的硬件配置。

4.1.1 主机配置

根据市场的主机配置，模拟8台服务器，配置如表1所示，其中CPU单位是MIPS，即衡量CPU速度的一个重要指标。

表1 主机配置

4.1.2 虚拟机配置

由于用户群体的需求不同，产生多样性的虚拟机，虚拟机规格如表2所示。

表2 虚拟机配置

4.2 实验分析

4.2.1 能耗计算

本文提出的方法即服务器预留算法RA(Reserved algorithm)，要求云服务提供者任意时间段都保留固定数目的服务器正常工作，来应对用请求包数量的非线性变化，同时当服务器闲置时自动切换待机状态，再根据0-1背包算法求出最佳分配值，我们和下面两个算法进行比较。

最佳适配递降算法BADA(Best adaptive descending algorithm)，即VM按照当前利用率进行降序排列，将利用率低的虚拟机，依次分配到最小能源消耗的服务器上。该方法优势主要利用VM实时迁移和关闭空闲节点，稳定了资源利用率，VM的重新分配节约了大量的能耗。

无预留算法UA(Unreserved algorithm)，即当任意需求包到来时，立即寻找合适的服务器，来满足该用户的需求；当某一台服务器处于闲置时，立刻将其关闭，频繁关闭启动服务器的同时消耗大量的能源，还会延长用户等待时间。

将包按照不同的参数进行部署，这些参数包括相同资源、距离、内存、CPU等，簇资源根据当前需要进行分配，记录三种算法的能耗，CPU平均利用率，内存平均利用率，根据本文提出的能耗模型来对能耗进行分析，实验结果如图2所示。

图2 能耗比较(周期为1小时)

实验表明，在相同条件下，随着运行时间的延长，三种算法的能耗有明显变化，但UA算法的能耗始终高于RA算法，说明服务器预留的可行性，确实降低了能耗。从曲线统计结果可知，UA算法在实验中需要消耗26.82 kW的能源，而RA只消耗了16.22 kW的能源，节省能源10.6 kW。BADA算法在试验中消耗了19.99 kW的能源，RA算法比BADA算法节省能源3.77 kW。

4.2.2 CPU和内存平均利用率

我们在模拟数据中心CloudSim实验平台上选定50、100到500台虚拟机进行资源分配，这些虚拟机在相同的环境分配相同的任务，规定的时间内，将运行产生的CPU利用率和内存利用率数据记录，在云实验平台达到平衡时对不同算法进行评估。如图3、图4所示。

图3 CPU利用率

图4 内存利用率

从图3、图4看出，随着包数量的递增三种算法资源使用率没有明显的关联，但是，RA算法的CPU利用率和内存利用率较高且稳定，RA算法与BADA算法相比，CPU利用率提高了17.6%，内存提高了13.9%，RA算法比UA算法优越性更为明显。虽然BADA算法资源使用量比UA算法有明显优势，但是不稳定，而UA算法整体资源利用率更偏低。纵向比较，在相同包数量的条件下，RA算法的资源使用率不一定比BADA算法高，但是比UA算法高，说明RA算法确实是提高了虚拟机资源利用率，起到了节约能源的作用。

5 结 语

对任何数据中心而言，不仅要提供购买、安置设备的场地和费用，还要控制运营、维护费用，降低服务器的能耗可有效控制成本费用。本文在分析了服务器高能耗问题后，提出了一种包簇框架下云资源预留的方法来节约能源，并使用0-1背包算法来调整包簇分配方案。在较为准确的服务器预留和较为合理的包簇映射的基础上，有效减少了服务器关机的次数，也有效降低了能源消耗，对云计算有一定的现实意义。

能耗仅仅是云计算资源优化目标之一，还包括各种性能目标、成本目标及利润目标等。同时在后续研究中还可以考虑硬盘容量、网络带宽等更多类型的资源限制条件，使研究更接近复杂的实际环境。