0 引言

近几年,云计算正在快速崛起,随着云计算规模不断扩大,其面临的资源优化管理方面的问题也越来越具有挑战性:目前主流的数据中心资源管理方式以虚拟机为中心,每个用户必须指明所需的虚拟机数量和资源要求,包括CPU、内存、存储器等,甚至可能还要包含带宽^[1],资源要求以绝对值抑或平均值和方差的方式定义^[2-3]。

由于异构需求的快速增长和用户群体的动态变化,虚拟机必须有动态适应云系统环境的能力,在满足服务条件的同时,充分地利用物理机资源。一些解决方案考虑了服务器到应用的动态分配方式以应对工作负载的变化^[4],另一些方案通过开发虚拟化技术^[5]来改善资源、降低经费开支等。

传统的云计算资源管理以虚拟机为中心,用扁平、细粒度的资源分配方式来设计资源分配模型。这种细粒度的管理模型导致要解决的计算问题规模巨大,对虚拟机固定的资源分配而言不利于资源共享。

针对以上问题,本文提出了一种包簇资源分配框架，通过改进多目标遗传算法将包部署到簇中，与传统的以虚拟机为中心的框架相比,提高了资源利用率,减少了物理机器使用个数。

1 相关工作

随着云计算规模的不断扩大,传统的云计算资源管理方式难以满足当前市场对高性能计算的需求,并出现了可扩展性、灵活性方面的问题。可扩展性问题的主要表现是虚拟机中的资源到服务器映射时需要大量的变量维护,而虚拟机间的通信流量矩阵、网络拓扑模型以及数据中心的带宽共享^[6]等因素也会影响模型的可扩展性。

灵活性问题的主要表现是用户申请虚拟机时必须指明虚拟机的资源要求^[7]以对数据中心的网络性能进行优化^[8]。然而，当用户希望以集中的方式来保证某种资源的供给时,如果允许资源共享,则对每个虚拟机而言就没有固定的资源承诺。

目前,在云计算资源分配领域中,都是以虚拟机为中心的资源分配调度。文献^[9]通过能量感知算法对应用程序进行调度,并用实时迁移的技术降低机器数量,从而降低硬件资源的能源消耗,但该资源分配算法仅支持单目标；文献^[10]通过改进优先配合降序方法来解决单点装箱问题,该方法只涉及负载峰值情况下的节点整合,却没有考虑物品和箱子不相容约束的问题；文献^[11]在长期负载性能模型的基础上,对带应用服务级目标约束虚拟机的放置进行了多目标优化,有效减少了物理机的使用数量和迁移次数,但该方法忽略了虚拟机和资源的整合；文献^[12]将虚拟机和资源进行整合,提出了一种多目标遗传算法,能有效减少物理机数量,提高资源利用率,但该算法并未考虑到虚拟机间的资源共享。

本文对传统的用于资源分配的遗传算法进行改进,提出了基于包簇框架的改进多目标遗传算法(Improved Multi-Objective genetic algorithm based on Package-Cluster,IMOPC)。该算法以节约能耗为目标,实现对需求包的部署和映射,从而最小化簇个数,最大化资源利用率。

2 包簇框架 2.1 包的构造

本文定义“包”作为虚拟机或者子包的集合,是一个递归定义,即一个包可由多个二级包组成,每个二级包亦可由多个三级包组成或由多个虚拟机组成,以此类推,包的集中实现有利于包内虚拟机间的资源共享。这种递归定义允许用户通过一种层次化结构来组织自己的资源需求。图 1展示了某中外合资企业的部门结构和虚拟机分布情况,其总部设在华盛顿,北京、上海、广州和南京分别设有分部。

然后根据用户需求,可以构造相对应的包结构,图 2中使用5个包来分别描述了5个场地的资源需求。其中总部有4个二级包,分别描述了人事部、销售部、管理部和工程部的资源需求;其他几个分部门也都拥有几个二级包,并且每个包中的资源都是可以共享的。

2.2 簇的构造

簇就是数据中心拓扑中位置相近的服务器或者更低级别的簇的集合。簇中所拥有的资源就是组成这个簇的每一部分的资源之和。图 3是以肥胖树^[13]表示以虚拟机为中心的服务器的拓扑结构。

按照簇的定义可知,每个机架上的服务器可表示成一个簇,因此图 3的拓扑结构可进一步简化成图 4。当低级别簇聚合成为高级别簇之后,又可进一步向上归并,依据不同的层次包含关系可构造出不同的簇结构。簇和包的结合降低了数据中心资源管理的复杂度。

3 基于包簇框架的资源分配

本文通过簇层次结构中任意一个簇ρ来描述资源分配问题,假设该簇拥有N个子簇或者服务器,以p作为子簇编号,1≤p≤N。假设分配给ρ的包由M个子包或虚拟机构成,标号为v(1≤v≤M)。现在要解决的问题就是如何将这M个子包最优分配给ρ中的N个子簇,而且该算法又可以递归调用来把子包的子包映射到子簇的子簇,直至最终的虚拟机到服务器的映射。此类问题可以考虑成多维装箱问题^[14],装入的物品就是资源共享的虚拟机组合成的包,包所用的共享资源总数就是物品的大小,箱子就是簇,箱子容量是簇资源的使用阈值,资源的种类数就是装箱问题的维数,目标是使得物理节点数最少,并且使资源利用率最大。

3.1 包簇框架理论 3.1.1 包簇框架模型

假设存在J种资源,每个子包对应一个描述所需资源的向量,其中每一项表示一个资源类型。相应地,每一个子簇,也对应一个可资分配的资源总量的向量。可用资源和用户需求会随时间变化,本文设定资源分配总时间为T,对于每一个子包v而言,在时间t对资源i的需求总量为R_v,i[t],其中1≤i≤J,1≤t≤T。而对每一个子簇p而言,在时间t对资源i的可用总量为A_p,i[t]。

本文将资源分配通过矩阵x来表示,即x:=(x_v,p[t]),其中,1≤v≤M,1≤p≤N,1≤t≤T。每个x_v,p[t]其实是一个0-1变量,当且仅当在时间t时包v被分配给簇p,则x_v,p[t]=1;否则x_v,p[t]=0。还要求:对于任何时间t,均有∑Np=1x_v,p[t]=1,也就是在任何时候每个包正好只分配给一个簇。由此一来,问题的目标函数可由式(1)表示:

$\left\{ \begin{matrix} \max \sum\limits_{t=1}^{T}{\sum\limits_{p=1}^{N}{\sum\limits_{i=1}^{J}{{\sum\limits_{v\in V}{{{R}_{v,i}}[t]{{x}_{v,p}}[t]}}/{{{A}_{p,i}}\left[ t \right]}\;}}} \\ \min \sum\limits_{p=1}^{N}{\sum\limits_{\text{v=1}}^{M}{{{x}_{v,p}}}} \\ \end{matrix} \right.$

(1)

$\text{s}\text{.t}\text{.}\sum\limits_{v\in V}{{{R}_{v,i}}[t]{{x}_{v,p}}[t]}\le {{A}_{p,i}}\left[ t \right]$

(2)

其中:第一个目标表示资源利用率最大化;第二个目标表示所用的物理节点簇个数最小化。在时间t,对任何资源i而言,给定分配矩阵x,每个簇p的资源使用量不能超过可用资源量。

3.1.2 可扩展性分析

对于虚拟机到服务器的映射而言,可以假设存在10个数据中心,每一个中心有10 000台服务器,共承载200 000台虚拟机,而每台虚拟机需要5种资源,资源分配时间间隔为1 h,优化时间范围为T=100 h。在以上的合理假定条件下,资源分配矩阵会有10万亿个变量,优化计算量大得难以想象，其性能在数据中心资源管理这样一个复杂的多维环境下难以进行分析。

而对于包簇框架模型,通过分层的抽象模型来降解问题的规模。顶层包映射顶层簇,对于每一个簇及它所支持的包,进一步将其下一级别的包映射到下一级别的簇,这个过程递归重复,直到虚拟机被映射到服务器。该方法可将一个高复杂度的问题简化并分解成多个小规模的子问题,这些子问题又可利用多目标遗传算法逐个解决。

这样,云资源管理优化问题就被转换成了一个多层次的、可递归的且易于解决的问题。可以使用数据中心分布式的监控/分配系统,结合资源需求和性能约束条件,来完成从高级包簇映射到低级包簇映射的迭代过程。由于数据中心的资源管理问题可被分解成多个的小规模包簇映射的子问题,这些子问题彼此又相互独立,因此可用多个资源分配处理器对其进行并行计算,以进一步提高资源分配的效率。

3.2 多目标包部署算法设计和实现

随着数据中心规模的不断扩大,传统的资源分配模型在处理组合优化问题时会产生大量的可行解,而使用包簇映射模型可有效降解问题的规模。为了提高包簇映射模型下可行解的收敛速度,本文对多目标优化遗传算法进行改进,并与包簇映射模型相结合。

3.2.1 物品编码

先对物品进行编码。其中包内资源主要有CPU、内存、I/O。然后,对时间T内的每个包i进行采样分析,并将每个包中虚拟机三类资源划分权重,从而标记当前包。本文将采用文献^[15]中的能效模型对每个包的资源需求进行采样。采样模型将作以下定义:

$\left\{ \begin{matrix} {{P}_{c,i}}(T)=\sum\limits_{t=1}^{T}{\left[ {{C}_{f,i}}(t)\times {{C}_{u,i}}(t)\times {{C}_{c,i}}\left( t \right)\times {{C}_{fn}} \right]} \\ {{P}_{d,i}}(T)=\sum\limits_{t=1}^{T}{\left[ {{D}_{r,i}}(t)+{{D}_{w,i}}(t) \right]} \\ {{P}_{m,i}}(T)=\sum\limits_{t=1}^{T}{\left[ {{M}_{r,i}}(t)+{{M}_{w,i}}(t) \right]} \\ \end{matrix} \right.$

(3)

其中:C_*,i(t)分别为包i在t时刻的CPU频率、使用率、核心数和浮点运算次数;D_*,i(t)分别为在t时刻的包i下所有虚拟机磁盘写入和写出的数据量;M_r,i(t)分别为t时刻包i下所有虚拟机内存写入和写出的数据量。

然后,将所有包中的三类资源统一作归一化处理,即包中的每一种资源占当前簇的权重。这样,每个包就可以通过这三类资源的比重来标记当前包,并且保证每类资源的使用量小于当前簇该类资源的门阈值。编码方式如图 5所示。

3.2.2 组编码

组编码的选择对结果的影响尤为重要,编码的具体实现其实就是问题的解决方案到染色体之间的映射。在这里,染色体就是资源共享的包到簇之间的解的编码。

如图 6中的第一个图所示,9个包被分成3个组,对应的染色体有3个基因,每个基因包括一组包,基因既可以表示物品也可以表示箱子。遗传算法对染色体的组部分操作,物品部分以资源编码的形式组成,因为簇节点放置的包数目的不同,同样的多种包也许放置到个数不同的簇节点上,因此遗传算法要处理不同长度的染色体。

3.2.3 适应度评估

在遗传算法中,适应度是由适应度函数计算得出的,它是用来评价个体在群体中的优劣程度的重要指标。遗传算法通过对种群中的个体的适应度进行比较,将优秀的个体选作产生下一代个体的母体,进行交叉和变异等操作,经过不断迭代直至满足收敛条件,最终产生适应度最高的个体作为最优解。

为了最大化资源利用率,需以尽可能少的簇来存放尽可能多的包,因此适应度函数将作以下定义:

$F(y)=\frac{1}{P}\sum\limits_{p=1}^{N}{\sum\limits_{i=1}^{J}{U_{p,i}^{x}}}$

(4)

其中: y为当前迭代种群的节点编号;U_p,i^y表示簇p对第i类资源的利用率;P_y为每个个体所使用的簇个数。

3.2.4 初始种群生成

初始种群的生成过程为:先随机生成一定数量的请求放置序列,然后将这些序列按适应度降序排列,最后选择前N个请求放置序列作为初始种群。

接着使用优先配合启发式算法,将各请求序列按包下标由低到高的顺序依次添加到簇中,若当前簇中的资源足够,就将其放入当前簇节点；否则就放入下一个簇节点。这样就可以将多个包分配到各个簇中,从而得到N个包放置方案,作为最终的初始种群。

3.2.5 选取

每一次迭代都会根据适应度函数来选择最优的染色体集合作为下一代的父个体,适应度越大被抽中为下一代的概率越高,即簇的资源利用率越高,簇使用个数越少,则被选中的可能性就越大。

3.2.6 交叉

交叉算子是遗传算法中最主要的操作,子代通过交叉操作从父代继承优秀的基因,从而扩大搜索域。交叉操作的具体步骤为:

第1步 从当前种群中随机挑选两个父个体,并在两个父体中随机选择需要交叉的部分;

第2步 将从第一个父个体中挑选出来的包组插入到第二个个体中的交叉点处,并删除重复的包;

第3步 将第一个父个体中取出交叉部分的剩余包组和第二步得到的包组进行第二轮交叉,此时交叉的对象是单个包,主要是最大化资源利用率;

第4步 在第二轮中的第一个父个体中随机选择一个包组,随机选择一个包作为交叉部分,第二个父个体中的随机包组的随机处选择一个交叉点;

第5步 将挑选出的单个包插入到交叉点之后删除重复包和多余物理机器,合并第一轮和第二轮交叉结果。

3.2.7 变异

变异主要就是以随机概率对群体中的个体串中的某个基因作变动，这样不仅可以增强问题解的收敛性,还可以维持群体的多样性,防止过早收敛情况发生。

在这里,染色体的变异可分为组编码的变异和物品编码的变异,这两种变异操作可以同时发生也可以单独发生。组编码的变异操作是随机地删除一个包组;物品编码的变异操作则是随机地删除一个包。

3.2.8 灵活性分析

当把最底层包映射到最底层簇时,为了保证包内资源的共享,不需要指定单个虚拟机内对单类资源的限额,而是以集中的形式来指定资源的配置。假设包v中有J种资源,虚拟机的数量为n,则该包的第j类资源的使用模式为:

$\sum\limits_{i=1}^{n}{{{\alpha }_{i,j}}}={{M}_{j}}$

(5)

其中: j是J种资源中的某一种；常量M_j是该包所拥有的j类资源的总量。

这种资源共享模式可以根据用户的需求拟定,这里只是假设其中一种情况,当指定资源共享的使用模式之后,包下虚拟机的资源调配就会更具灵活性,在某一段时间内,若其中一个虚拟机需要大量资源,而在满足其他虚拟机运行应用所需基本资源外,合理分配自己的一部分资源给当前虚拟机,这样的资源调配更具灵活性。

在这里,属于同一个包的虚拟机将在相互邻近的属于同一个簇的服务器上实现,从而有利于在簇控制器的监测管理下实现资源共享。

4 实验分析

为了验证本文算法IMOPC在基于包簇框架下的资源分配结果的合理性,在CloudSim^[16]上进行仿真实验。CloudSim是由澳大利亚墨尔本大学的网格实验室和Gridbus项目宣布推出的云计算仿真软件,该软件根据用户需求可以指定虚拟机和物理机的数量,自定义应用负载,符合本次实验要求。

对比算法选择以虚拟机为中心的多目标遗传算法(Multi Objective genetic algorithm based on Virtual machine,MOV)和基于包簇框架的首次适应算法(Best Fit Algorithm based on Package-Cluster,BFAPC)。

首次适应算法就是在部署虚拟机过程中，按照顺序查找物理机器，将虚拟机直接部署在满足虚拟机需求的物理机器上。IMOPC和MOV都是运用遗传算法,只是分配对象不同；BFAPC主要是以包为分配对象。

实验平台选取500台虚拟机部署到250台物理服务器上。在基于包簇的框架下,本文对500台虚拟机逐层划分包结构,直到底层的虚拟机;相应地,250台物理机根据包的结构划分簇。包层次结构划分如图 8所示。

本实验中共有5个二级包,50个三级包(每个三级包有10台虚拟机);相应地,有3个二级簇,25个三级簇(每个簇下面有10台服务器)。

实验主要分为两部分：首先,将IMOPC和BFAPC部署包簇,从而比较包簇框架下不同部署算法使用的簇个数;然后再验证IMOPC、BFAPC和MOV这三种算法下的资源利用率变化情况。

实验1 簇使用个数计算。

本轮实验的簇主要以三级簇为例,分别用IMOPC和BFAPC部署包簇,这两种算法除了部署方法以外,资源门阈值、物理机器属性和虚拟机任务都一致。在IMOPC部署算法中,交叉概率设置为0.7,变异概率设置为0.05,种群的个数设置为22,遗传代数分别设置为7、14、22、26。随着迭代次数的增加,目标函数值向着最优解的方向收敛,在第14代时群体总共存在22个个体,前后变化不大,基本趋于稳定。在25个簇上放置50个包,搜索空间为25⁵⁰个可行解,并且IMOPC仅仅需要22×14=308次循环执行即可得到近似最优解,它的时间复杂度为O(mN²),在保证效率的情况下,这种执行时间的算法是可以容忍的。每隔一段固定时间来观察簇个数的变化,如图 9所示。

实验结果表明,通过IMOPC部署的簇个数明显要比BFAPC部署的簇个数要少,这是因为BFAPC每次都选择剩余资源最小的簇,而IMOPC每次都在满足约束条件下搜索最小化簇个数寻求最优解。

实验2 资源利用率计算。

在基于包簇框架下的两种算法和传统的以虚拟机为中心的框架下的算法MOV进行比较,每隔一段时间记录几种算法的资源利用率情况,三种部署算法下的CPU平均利用率和内存平均利用率变化情况如图 10~11所示。

实验结果表明,包簇框架下的IMOPC和同框架下的BFAPC相比,CPU利用率提高了5%,内存利用率提高了7%;IMPOC算法和传统的以虚拟机为中心的框架下的MOV算法相比,CPU利用率提高了9%,内存利用率提高了14%。因为BFAPC尽可能少地部署簇,却忽略了资源利用率。IMOPC虽然和MOV用的是同一种部署算法,但在包簇框架下,包内的资源是共享的,在资源不超过阈值的情况下,虚拟机间可通过动态的负载均衡来减少虚拟机迁移的概率,提高了资源利用率,达到了节能的效果。

5 结语

本文在分析了传统的以虚拟机为中心框架下所存在的可扩展性和灵活性的问题后,将改进的遗传算法应用到了新的框架下,对包进行了组编码和物品编码,在一定的交叉概率和变异概率下对包和包中资源进行操作,缓解了云计算中能耗问题。由仿真结果可知,框架下的部署算法减少了物理机的使用个数,提高了资源利用率。目前,综合性挑战也是数据中心存在的一个问题,云系统的优化目标不止能耗这一方面,将多优化目标结合,也是云计算资源分配的研究方向。