随着云计算产业的发展,云计算逐步从概念走向实际应用,越来越多的传统软件提供商正在将其应用向云服务模式迁移.这些应用被部署在IaaS(infrastructure as a service)提供商或者自己的云基础设施上,通过互联网,以按需、易扩展的方式向客户提供服务.被部署在云中的应用是以SaaS(software as a service)模式对外提供服务.在SaaS服务模式下,使用SaaS应用的客户不需要购买完整的软件产品,也不需要配备相应的硬件系统和维护人员,只需通过互联网,按需租用即可,这对于成本预算有限、技术条件不足的中小企业来说,具有很强的吸引力.与传统的软件模式相比,SaaS具有部署时间短、成本低、使用方便等优势,因此,其市场应用前景非常广阔,被认为是未来应用软件的发展趋势^[1].

当传统软件提供商在向SaaS服务模式迁移时,所面临的一个重要问题是:如何根据需要部署的SaaS应用中每个构件的资源需求来确定最优的SaaS构件放置方案,即:选择哪些类型的虚拟机?每种虚拟机的数量是多少?每个被选择的虚拟机上放置哪些构件?如何放置才能够在满足每个构件资源需求的条件下,使得总的云资源使用成本最低?制定优化的SaaS构件放置方案是提高云资源利用率、降低运营成本的一项重要手段,具有十分重要的应用价值.尽管目前已经提出了许多SaaS构件优化放置方法,但是这些方法都假定虚拟机的类型和数量是确定的,即,在限定的云资源上进行优化放置,因此在实际应用中还存在许多问题.例如,SaaS提供者在将其SaaS应用部署到IaaS提供者的云环境时,其只知道IaaS提供商所发布的虚拟机种类和价格,例如,亚马逊EC2的m1.small,m1.large,m2.x large等,但是所需要的每种类型的虚拟机的数量是未知的,它需要根据构件的资源需求来确定.尽管目前许多IaaS提供商也提供了相应的虚拟机选择方案,但是这些方法大都是简单的资源匹配,很难满足大型复杂企业级SaaS应用的部署需求.SaaS构件优化放置问题是一个NP问题^[2],针对该问题,本文提出一种基于混合遗传模拟退火算法的SaaS构件优化放置方法,其目标是提高云资源利用率、降低云资源使用成本.该方法既可以应用于SaaS应用的初始部署,也可应用于SaaS运行阶段的动态部署.

1 相关工作

针对SaaS优化放置问题,国内外学者已经展开了许多研究工作.根据放置的粒度,可分为租户放置、构件放置和应用放置这3个层次.

租户放置是指建立租户与SaaS应用或构件实例之间的服务关系,即,哪些租户的服务请求被分配到哪些SaaS应用或构件实例上执行.租户优化放置的一个主要目标是:在满足每个租户服务质量需求的条件下,使得现有的云资源数量能够支持更多的租户和并发用户请求.针对租户放置问题,目前已提出了多种优化策略和算法,例如启发式算法^[2]、遗传算法^[3]、准入控制策略^[4]、分等级策略^[5]等.

应用放置是指,建立SaaS应用与IaaS层的虚拟机之间的部署关系^[6],应用放置主要适合于粒度比较小的SaaS应用,而对于大型复杂企业级SaaS应用来说,由于单个虚拟机的资源能力难以满足整个SaaS应用的资源需求,因此需要将SaaS应用分解为一组可独立部署的构件,这些构件被放置在多个虚拟机上运行.此时,SaaS应用放置问题可转化为SaaS构件放置问题.SaaS构件放置是指建立SaaS应用中的构件与IaaS层的虚拟机之间的部署关系^[7],即,哪些构件被部署在哪个虚拟机上执行.由于同一个SaaS应用被分布式地部署在多个虚拟机上执行,因此,如何提高整个应用的性能是一个需要考虑的重要问题^[8].构件优化放置的主要目标是,在保证每个租户的服务质量需求的前提下提高云资源利用率、降低云资源使用成本.

本文主要研究构件优化放置问题,针对该类问题,目前已经提出了许多相应的方法.Yusoh提出了一种组合SaaS应用放置方法(SPP),SPP分为初始放置和资源优化两个过程:初始放置的目标是确定如何将服务/数据构件放置到相应的计算/存储服务器上,使得整个SaaS应用的执行时间最少;资源优化的目标则是通过调整运行阶段构件的放置方案来提高资源的利用率、减少运营成本^[7].Moens采用特征模型来描述SaaS应用的构件及其关系,并采用整数线性规划和启发式方法对问题进行求解^[9].Zhu针对云数据中心的应用构件放置问题,提出了一个基于MIP的求解算法^[10].Jin针对跨多个云数据中心的应用构件放置问题提出了一种分布式方法,并给出了相应的模拟分析方法^[11].Sailer提出了一个基于图的云服务放置方法,该方法采用图来描述业务支持的服务(BSS)、操作支持的服务(OSS)以及它们之间的映射,并提出了一种基于服务需求和数据中心资源类型的云资源分配算法^[12].

尽管目前已经存在许多求解构件优化放置的算法,但是这些算法都是将虚拟机的类型和数量看作是固定的常量,该类问题可以抽象为多背包问题(multiple knapsack problem,简称MKP),MKP是一个NP问题^[13].目前,求解MKP的方法主要有精确算法^[13]、启发式算法^[14]、遗传算法^[15]和蚁群克隆算法^[16]等.MKP的目标是使装入多个背包中的物品的总价值最大或者物体放置得更佳均衡,由于背包的数量是有限的,因此有些物体不能被装入任何包中.本文所提出的SaaS构件优化放置问题也可以看作是一个特殊的背包问题,我们称其为多维多类背包问题(multidimensional multiple-class knapsack problem,简称MMCKP),其中,构件可以看作是物品,而虚拟机模板则看作是背包的类型,不是具体的背包.另外,物品和背包的属性都是多维的.与传统的MKP问题不同的是,MMCKP要求所有的物品都必须被放入到一个具体的背包中,其目标是使用背包的成本最低.另外,由于SaaS构件优化放置问题不仅要考虑虚拟机的使用成本,而且还要考虑不同虚拟机之间的网络通信成本,因此,其问题的复杂度要比MKP更高,目前并未见到相关文献解决此类问题.

SaaS构件放置问题是一个NP问题,当问题的规模较大时,采用枚举等精确算法的运行时间代价比较高,很难满足实际应用的需求.因此,需要采用相应的近似算法对其进行求解.目前,求解SaaS构件优化放置问题的主要近似方法有启发式算法^[2,9]和遗传算法(genetic algorithm,简称GA)^[7]等进化算法.由于GA在生成初始解时已经采用了相应的启发式规则,因此在解决构件放置问题时,其求解质量比单纯采用启发式算法的效果要好. GA是解决离散优化问题的一种常用的方法,它通过选择、交叉、变异等进化操作来实现群体的协同进化.GA具有较强的全局搜索能力,但其局部搜索能力较差,容易产生“早熟”收敛问题^[17].由于本文所提出的构件放置问题中虚拟机的数量是不确定的,因此染色体中每个基因的取值范围较大,采用交叉操作会使虚拟机的范围变大,其求解质量较低.另外,由于本文所提出的构件优化问题不仅考虑新放置的构件和新创建的虚拟机,同时还需要考虑已创建的虚拟机和已放置的构件,因此在产生新解时,许多虚拟机已经放置了构件,尽管这些虚拟机的可用资源量已经不具备放置资源需求量较高的大粒度构件的条件,但仍有可能放置一些资源需求量较小构件的条件.因此在解的搜索过程中,如果只采用遗传算法的随机交叉、变异等操作来产生新解,其错误率较高,进而影响算法的效率和求解质量.

为了克服遗传算法在求解SaaS构件优化放置问题方面的不足,本文将遗传算法与模拟退火算法(simulated annealing algorithm,简称SA)相结合,取长补短,提出了一种求解SaaS构件优化放置问题的混合遗传模拟退火算法(hybrid genetic and simulated annealing algorithm,简称HGSA).SA是对热力学中退火过程的模拟,它是一种在某一给定的初始温度下,通过缓慢下降温度参数,并根据相应的概率接受准则在解空间中随机寻找目标函数全局最优解的优化方法.SA具有较强的局部搜索能力,但其全局把握能力较弱^[18].HGSA是将GA与SA相结合而构成的一种优化算法,它克服了GA收敛速度慢和SA容易陷入局部最优的缺点,从而提高了问题的求解质量^[19].混合遗传模拟退火算法目前已在许多领域得到应用,并取得了较好的效果^{[20, 21, 22]}.例如:Ren采用混合遗传模拟退火算法以解决电子商务供应链环境下具有返程的本地库存车辆路线优化问题^[20];Deb利用混合遗传模拟退火算法解决计算机辅助计划中零件装配序列规划问题^[21];McCall提出了一种并行混合遗传模拟退火算法来求解计算网格中的Q3AP问题^[22].由于问题领域的不同,因此针对不同问题的混合遗传模拟退火算法的结构和流程也不完全相同.本文针对云计算领域中SaaS构件放置问题的特点,提出了一种基于二元组的染色体编码方法来表示虚拟机类型和虚拟机,并设计了4种邻域搜索规则来改善种群中每个个体的质量,避免了交叉操作所导致解的质量下降问题.与单独使用遗传算法和模拟退火算法相比,实验结果表明,HGSA具有较高的求解质量.

2 SaaS构件优化放置问题描述

SaaS构件优化放置是指在SaaS应用的初始部署或者运行阶段,SaaS提供者根据部署的每个构件的资源需求以及现有云环境中构件的放置情况,确定一个当前的最优放置方案.图 1描述了SaaS构件优化问题的框架.从软件部署角度来看,一个SaaS应用可以抽象为一个图结构,称为构件关系图,其中,图的顶点代表构件,边代表构件之间的连接关系.同时,SaaS构件放置方案也可表示为一个图结构,称为虚拟机网络图,其中,图的顶点代表包含一组构件的虚拟机,边则代表虚拟机之间的通信链路,因此,构件放置可以看作是对构件关系图的划分,每个被划分的子图被映射为一个由相应的虚拟机模板所创建的虚拟机,构件之间的连接关系被映射为虚拟机之间的通信链路.虚拟机是由相应的虚拟机模板创建的,不同的虚拟模板具有不同的资源配置和价格.由同一虚拟机模板所创建的虚拟机具有相同的资源配置和价格.如果被放置在两个不同虚拟机上的构件之间存在连接关系,则这两个虚拟机之间存在通信链路.为了降低网络通信成本,我们尽量将具有紧密耦合关系的构件放置到一个虚拟机中.但是虚拟机的资源需求会受到其所属的虚拟机资源能力的约束,因此,SaaS构件优化放置的关键就是确定一个最优的构件关系图划分,该划分使得虚拟机网络的资源使用成本最低.该问题是一个NP问题.

下面我们给出SaaS构件优化放置问题中所涉及到的一些基本概念的定义.

定义1(构件关系图). 构件关系图可以定义为G=(C,E),其中,

• C=C_A∪C_B为构件的集合,C_A为已放置的构件集合,C_B为新放置的构件集合;

• E={(c,c')|c,c'∈C}为构件之间的连接关系集,对于∀(c,c')∈E,表示从c到c'存在连接关系,对于∀c∈C,r_c(c)为c的计算资源消耗量,r_m(c)为c的内存资源消耗量,r_d(c)为c的存储资源消耗量;对于∀(c,c')∈E,r_t(c,c')表示从c到c'的网络通信带宽消耗量.

构件放置的一个难点在于,事先并不知道每种虚拟机的数量,因此,我们首先需要确定每种虚拟机模板所要创建的虚拟机的数量.假设有n种虚拟机模板,令VC={vc₁,vc₂,…,vc_n}表示虚拟模板的集合,其中,vc_i表示第i (i=1,2,…,n)种虚拟机模板,令r_c(vc_i)表示vc_i的计算资源提供量,r_m(vc_i)表示vc_i的内存资源提供量,r_d(vc_i)表示vc_i的存储资源提供量,p(vc_i)为vc_i的资源使用成本.

我们通过n个非负整型决策变量S={s₁,s₂,…,s_n}来表示由虚拟机模板所创建的虚拟机数量,如果s_i=0,表示没有选择vc_i创建虚拟机.令VM=VM_A∪VM_B=VM₁∪VM₂∪…∪VM_n表示放置构件的虚拟机集合,其中,VM_A表示已创建的虚拟机集合,VM_B表示需要新创建的虚拟机集合,VM_i表示由vc_i所创建的虚拟机集合,如果s_i=0,则有VM_i=∅,即,不存在类型为vc_i的虚拟机;否则,VM_i={vm_i1,vm_i2,…,$v{m_{i{n_i}}}$},其中,vm_ij(j=1,2,…,n_i)表示由vc_i所创建的第j个虚拟机.对于∀vm_ij∈VM_i,令r_c(vm_ij),r_m(vm_ij)和r_d(vm_ij)分别表示vm_ij的计算、内存和存储资源提供量.由同一虚拟机模板所创建的虚拟机具有相同的资源配置和价格,即:

${r_c}\left( {v{m_{ij}}} \right) = {r_c}\left( {v{c_i}} \right),{r_m}\left( {v{m_{ij}}} \right) = {r_m}\left( {v{c_i}} \right),{r_d}\left( {v{m_{ij}}} \right) = {r_d}\left( {v{c_i}} \right),p\left( {v{m_{ij}}} \right) = p\left( {v{c_i}} \right).$

集合VM_i(i=1,2,…,n)可划分为两个子集:已创建的虚拟机集合VM_Ai和新创建的虚拟机集合VM_Bi,即VM_i= VM_Ai∪VM_Bi.令n_Ai=|VM_Ai|表示VM_i中已创建的虚拟机数量,n_Bi=|VM_Bi|表示VM_i中新创建的虚拟机数量,因此,n_i=n_Ai+n_Bi.为了处理方便,我们规定VM_i中的前n_Ai个虚拟机为已创建的,后n_Bi个虚拟机为新创建的,n_Bi的数量在新构件放置开始时是不确定的,其需要根据放置结果来确定,因此,

$V{M_A} = V{M_A}_1 \cup V{M_A}_2 \cup \ldots \cup V{M_{An}},V{M_B} = V{M_B}_1 \cup V{M_B}_2 \cup \ldots \cup V{M_{Bn}}.$

例如,在图 1所示的放置场景中:C_A={c₁,c₂,c₃,c₄}为已放置的构件集合,其中,c₁,c₂和c₃被放置在由虚拟机模板vc₂所创建的虚拟机vm₂₁中,c₄被放置在由vc₁所创建的虚拟机vm₁₁中;C_B={c₅,c₆,c₇,c₈,c₉,c₁₀}为新放置的构件集合,通过制定新的放置方案,c₅将被放置在vm₁₁上,c₆,c₇,c₈将被放置在由虚拟机模板vc₂所创建的虚拟机vm₂₂中,c₉和c₁₀将被放置在由虚拟机模板vc₃所创建的虚拟机vm₃₁中.

为了提高云资源的利用率,我们尽量将C_B中的构件放置在VM_A,这样可以减少新创建虚拟机的数量,进而可以降低云资源的使用成本.

定义2(SaaS构件放置方案). SaaS构件放置方案可以定义从构件集合C到虚拟机集合VM的映射函数ρ:C→VM.对于∀c∈C,ρ(c)∈VM表示c所放置的虚拟机;对于∀vm_ij∈VM,C(vm_ij)={c∈C|ρ(c)=vm_ij}表示放置在虚拟机vm_ij上的构件集合.

例如,在图 1所示的放置场景中,

$\begin{array}{l} VM = \left\{ {v{m_{11}},v{m_{21}},v{m_{22}},v{m_{31}}} \right\},C\left( {v{m_{11}}} \right) = \left\{ {{c_4},{c_5}} \right\},C\left( {v{m_{21}}} \right) = \left\{ {{c_1},{c_2},{c_3}} \right\},\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;C\left( {v{m_{22}}} \right) = \left\{ {{c_6},{c_7},{c_8}} \right\},C\left( {v{m_{31}}} \right) = \left\{ {v{m_9},v{m_{10}}} \right\}. \end{array}$

在构件关系图中,如果两个构件之间存在连接关系,并且这两个构件被放置在不同的虚拟机上,则这两个虚拟机之间存在网络通信.根据放置在两个不同虚拟机之间的构件连接关系,我们可以定义虚拟机网络图.

定义3(虚拟机网络图). 虚拟机网络图可以定义为VN=(VM,L_VM),其中,VM为放置C中的构件所需要的虚拟机集合;L_VM={(vm_ij,vm_st)|∃c∈C(vm_ij),c'∈C(vm_st):(c,c')∈E∧vm_ij≠vm_st}表示VM中虚拟机之间的通信链路的集合,对于∀(vm_ij,vm_st)∈L_VM,表示vm_ij和vm_st之间存在通信链路.

对于∀(vm_ij,vm_st)∈L_VM,E(vm_ij,vm_st)={(c,c')|c∈C(vm_ij),c'∈C(vm_st),(c,c')∈E}为从vm_ij到vm_st的构件连接关系集,则从vm_ij到vm_st的通信流量可以定义为

${r_t}(v{m_{ij}},v{m_{st}}) = \sum\limits_{(c,c') \in E(v{m_{ij}},v{m_{st}})} {{r_t}(c,c')} .$

因此,虚拟机网络的通信流量可定义为r_t(L_VM)=${r_t}({L_{VM}}) = \sum\limits_{(v{m_{ij}},v{m_{st}}) \in {L_{VM}}} {{r_t}(v{m_{ij}},v{m_{st}})} .$

基于上述分析,虚拟机网络的成本可以定义为c(VN)=c(VM)+c(L_VM),其中,$c(VM) = \sum\limits_{i = 1}^n {\sum\limits_{j = 1}^{{s_i}} {p(v{m_{ij}})} } $为虚拟机的使用成本,c(L_VM)=p_t(r_t(L_VM))为虚拟机网络的通信成本.在这里,p_t(T)表示虚拟机网络通信计费价格函数,如何确定p_t(T),需要根据具体的网络通信计费模式来确定.本文的目标就是确定一种使得c(VN)最小的SaaS构件放置方案,因此,SaaS构件优化放置问题可以描述为

${\bf{Min}}c\left( {VN} \right) = c\left( {VM} \right) + c\left( {{L_{VM}}} \right)$

(1)

Subject to:

$S = \left\{ {{s_1},{s_2},...,{s_n}} \right\},{s_i} \in N\left( {i = 1,2,\ldots ,n} \right)$

(2)

$\begin{array}{*{20}{l}} {VM = V{M_1} \cup V{M_2} \cup ... \cup V{M_n}}\\ {V{M_i} = \left\{ {\begin{array}{*{20}{l}} {\emptyset ,{\rm{ }}{s_i} = 0}\\ {\{ v{m_{i1}},v{m_{i2}},...,v{m_{i{s_i}}}\} ,{\rm{ }}{s_i} > 0} \end{array}} \right.} \end{array}$

(3)

$\rho \left( c \right) \in VM,\forall c \in C$

(4)

$C\left( {v{m_{ij}}} \right) \ne \emptyset \wedge C\left( {v{m_{ij}}} \right) \subseteq C,\forall v{m_{ij}} \in V{U_B}$

(5)

$E\left( l \right) \ne \emptyset \wedge E\left( l \right) \subseteq E,\forall l \in {L_{VM}}$

(6)

$\sum\limits_{c \in C(v{m_{ij}})} {{r_c}(c)} \le {r_c}(v{m_{ij}}) - r_c^0(v{m_{ij}}),\forall v{m_{ij}} \in VM$

(7)

$\sum\limits_{o \in C(v{m_{ij}})} {{r_m}(c)} \le {r_m}(v{m_{ij}}) - r_m^0(v{m_{ij}}),\forall v{m_{ij}} \in VM$

(8)

$\sum\limits_{c \in C(v{m_{ij}})} {{r_d}(c)} \le {r_d}(v{m_{ij}}) - r_d^0(v{m_{ij}}),\forall v{m_{ij}} \in VM$

(9)

在上面的形式化描述中:公式(1)为问题的优化目标,表示SaaS构件放置方案,即,虚拟机网络图VN的成本最低;公式(2)给出了一组非负整型决策变量S={s₁,s₂,...,s_n},其中,s_i∈N表示由第i类虚拟机模板vc_i所创建的虚拟机数量,N为非负整数集合;公式(3)是基于公式(2)的决策变量所构造的虚拟机集合VM=VM₁∪VM₂∪…∪VM_n,其中,VM_i表示由第i类虚拟机模板vc_i所构造的虚拟机集合,vm_ij(j=1,2,…,s_i)表示VM_i中第j个虚拟机,VM_i和vm_ij是需要根据决策变量S来动态创建的;公式(4)表示对于C中的任何构件,都被放置到VM中的一个虚拟机上;公式(5)表示VM中的任何虚拟机所包含的构件都不能为空,并且都是C中的构件;公式(6)表示L_VM中的任何通信链路所包含的构件连接都不能为空,并且都是E中的构件连接;公式(7)到公式(9)是对虚拟机资源需求的约束,分别表示虚拟机所包含的构件的计算、内存和存储资源不能超过该虚拟机资源的提供能力,其中,$r_c^0(v{m_{ij}}),r_m^0(v{m_{ij}})$和$r_d^0(v{m_{ij}})$分别表示vm_ij的计算、内存和存储资源预留量.虚拟机的资源利用率不能超过一定的阈值,因此需要预留一部分资源作为缓冲以保证应用运行的质量,虚拟机的资源预留量与虚拟机的类型有关.

3 基于HGSA的SaaS构件优化放置算法

针对SaaS构件优化放置问题,本文采用混合遗传模拟退火算法(HGSA)对其进行求解.与遗传算法类似,HGSA也是从一组随机产生的初始解开始进行全局最优解搜索,它首先通过遗传算法(GA)中的选择和交叉操作来产生一组新个体,然后,针对每个新产生的个体采用模拟退火算法(SA)进行邻域搜索,并以其结果作为下一代种群中的个体.HGSA将GA与SA的优点充分结合起来,从而提高了SaaS构件优化放置问题的求解质量.

3.1 解的编码

HGSA采用基于构件的编码方式,染色体中每一个基因代表一个构件,染色体的长度为构件的数量|C|,基因的取值代表构件所放置的虚拟机,每个虚拟机采用一个二元组(i,j)来表示,其中,i表示虚拟机类型编号,j表示虚拟机编号.每一类虚拟机都是从1开始编号,并且要保持编号的连续性.令P表示一条染色体,P可分为两个部分:已放置构件的基因片段P_A和新放置构件的基因片段P_B,其中,P_A中的每个基因代表C_A中的一个构件,P_B中的每一个基因代表C_B中的一个构件.例如,针对图 1所示的SaaS构件放置方案,其所对应的编码如图 2所示.

3.2 解初始化

解的初始化是指生成种群中的每一条初始染色体,本文采用基于贪心策略的启发式方法来生成初始染色体,具体步骤如下:

Step 1. 按照构件的编号顺序生成一条初始染色体P,其中,P_A中每个构件的基因取值为该构件所在的虚拟机编码,P_B中的每个构件的基因取值为空.

Setp 2. 随机产生一个VM_A中虚拟机序列S_VM和C_B中构件序列S_C.

Step 3. 按照顺序取出S_C中的每一个构件c,依次检查S_VM中的每一个虚拟机是否能够放置c:如果满足放置条件,则将构件c放置到一个匹配的虚拟机上(即,c的基因取值为该虚拟机编号);如果S_VM中的每一个虚拟机都不能放置构件c,则随机创建一个新的虚拟机,并将该虚拟机编号加入到序列S_VM的末尾,然后将构件c放置到新创建的虚拟机上(即,构件c的基因取值为新创建的虚拟机编号).重复上述过程,直到S_C中的每一个构件都被放置完成.

按照上述步骤,可以生成初始种群中的每一条染色体.解初始化的时间复杂度为O(s·|C_B|·|VM|),其中,s为种群的数量,|C_B|为新放置构件数量,|VM|为虚拟机的数量上限.

3.3 新解产生规则

HGSA采用SA中的邻域搜索策略来实现解的局部搜索能力.在SA中,新解产生是旧解向邻域搜索的结果,其搜索规则决定了邻域的范围.新解产生规则的设计与实际问题密切相关,而不是简单的随机搜索.针对本文所提出的SaaS构件优化放置问题,由已知解向邻域搜索的操作对象主要有构件和虚拟机,因此,我们设计了如下4种新解产生规则,其中,规则(1)和规则(2)属于构件粒度层次的邻域搜索,规则(3)和规则(4)属于虚拟机粒度层次的邻域搜索.

(1) 改变构件放置位置

随机选择一个基因k,设其取值为(i,j),为k重新赋予一个新值(i',j'),其对应的放置操作为:将构件c_k从虚拟机vm_ij迁移到vm_i'j'上,这要求vm_i'_j'的可用资源能够满足放置c_k的资源需求.如果虚拟机vm_ij中只包含c_k一个构件,则可以将vm_ij从虚拟机网络图VN中删除.图 3(a)描述了改变构件放置位置产生新解过程的示意图,它表示将构件c₆从虚拟机vm₂₂迁移到虚拟机vm₁₂上.

(2) 交换构件放置位置

随机选择两个取值不同的基因k和l,交换k和l的值,其所对应的放置操作为:将构件c_k迁移到构件c_l所在的虚拟机上,同时将构件c_l迁移到构件c_k所在的虚拟机上,即,互换c_k和c_l的放置位置.迁移后的虚拟机应满足构件放置的资源约束条件.图 3(b)描述了交换构件放置位置产生新解过程的示意图,它表示将构件c₅从虚拟机vm₁₁取出放置到虚拟机vm₂₂中,同时将构件c₈从虚拟机vm₂₂取出放置到虚拟机vm₁₁中.

(3) 从高价虚拟机向低价虚拟机迁移

设vm_ij为虚拟机网络图VN中的一个虚拟机,若存在比vm_ij价格低且能够放置其上所有构件的虚拟机模板vc_i',则创建vc_i'的一个实例vm_i'j',将vm_ij上的所有构件都迁移到vm_i'j'上,并将所有取值为(i,j)的基因值都替换为(i',j'),然后,再将vm_ij从虚拟机网络图VN中删除.由于vm_i'j'的成本要比vm_ij低,因此通过该操作虚拟机网络VN的成本降低了p(vm_ij)-p(vm_i'_j').图 3(c)描述了从高价虚拟机向低价虚拟机迁移过程示意图,它表示存在比虚拟机vm₃₁价格低且能够放置其上所有构件的虚拟机模板vc₁,因此可以创建vc₁的一个实例vm₁₂(由于已存在编号为1的虚拟机vm₁₁,为了保持编号的连续性,新创建的虚拟机编号应为2),然后将vm₃₁中的构件c₉和c₁₀迁移到新创建的虚拟机vm₁₂中,最后,将vm₃₁从虚拟机网络图中删除.

(4) 从小型虚拟机向大型虚拟机迁移

设vm_ij为虚拟机网络图VN中的一个虚拟机,若存在能够放置vm_ij上所有构件的虚拟机vm_i'j',则将vm_ij上的所有构件都迁移到vm_i'j'上,并将这些构件的基因值都替换为(i',j'),然后,将vm_ij从虚拟机网络图VN中删除.由于减少了一个虚拟机vm_ij,而且vm_ij与vm_i'j'之间的通信由虚拟机之间转变为虚拟机内部(本文假定虚拟机内部的通信不产生成本),因此,通过该操作虚拟机网络图VN的成本低了p(vm_ij)+p_t(r_t(vm_ij,vm_i'j')).图 3(d)描述了从小型虚拟机向大型虚拟机迁移过程的示意图,它表示存在一个能够放置虚拟机vm₂₁上所有构件的虚拟机vm₃₁,因此,可以将vm₂₁上的所有构件都迁移到vm₃₁上,并将vm₂₁从虚拟机网络图中删除.迁移后,vm₃₁上包含5个构件c₉,c₁₀,c₁,c₂和c₃,其中,c₉和c₁₀为迁移之前vm₃₁中已存在的构件,c₁,c₂和c₃是从vm₂₁迁移过来的构件.

3.4 选择与交叉操作

HGSA采用遗传算法中的选择和交叉操作来提高解的全局搜索能力,其中,选择操作采用比例选择策略,交叉操作采用双切交叉法.

(1) 选择操作

选择操作采用比例选择策略和旋轮法来实现,其目的是使适应度高的个体具有更高的生存概率.

设P_i(i=1,2,…,s)为种群中的一个染色体,s为种群规模,f(P_i)为P_i的适应度,适应度采用虚拟机网络图成本来表示.令VN_i为P_i所对应的虚拟机网络图,则f(P_i)=c(VN_i),c(VN_i)为VN_i的成本.为了便于选择操作,我们采用正规化技术将适应值映射到(0,1)区间.设F(P_i)为映射后的正规化适应度,则有:

$F({P_i}) = \frac{{{f_{\{ \max \} }} - f({P_i}) + r}}{{{f_{\{ \max \} }} - {f_{\{ \min \} }} + r}},$

其中,f_{min}和f_{max}分别为种群中的最小和最大适应度;r∈(0,1)是一个常数,它可以根据实际情况进行设定,我们设定r=0.8.根据比例选择策略,P_i被选择的概率为$F({P_i})/\sum\limits_{i = 1}^s {F({P_i})} .$得到每个染色体的选择概率后,采用旋轮法来实现选择操作,共旋转s次,每次转轮时,随机产生ξ_k∈(0,1),如果$\sum\limits_{j = 1}^{i - 1} {F({P_i})} /\sum\limits_{i = 1}^s {F({P_i})} \le {\xi _k} < \sum\limits_{j = 1}^i {F({P_i})} /\sum\limits_{i = 1}^s {F({P_i})} $则选择染色体P_i.

(2) 交叉操作

交叉操作采用双切交叉法,对于两个选定的染色体P₁和P₂,随机选取两个切点k₁和k₂,交换k₁和k₂之间的基因编码,生成两个新的染色体P₁和P₂.图 4描述了交叉操作过程的示意图.

如果新生成的染色体不满足虚拟机资源约束条件,则需要对其进行修复,染色体修复过程如下:

Step 1. 针对每个不满足资源约束的虚拟机,生成该虚拟机所放置构件的一个序列,然后,按照该序列依次取出每个构件,直到虚拟机满足资源约束为止.

Step 2. 对于从所有不满足资源约束条件的虚拟机取出的所有构件,随机生成一个构件序列S_C.同时,对于所有已经使用的虚拟机,随机生成一个虚拟机序列S_VM.

Step 3. 按照顺序取出S_C中的每一个构件c,依次检查S_VM中的每一个虚拟机是否能够放置c:如果满足放置条件,则将构件c放置到第1个匹配的虚拟机上(即,c的基因取值为该虚拟机编号);如果S_VM中的每一个虚拟机都不能放置构件c,则随机创建一个新的虚拟机,并将该虚拟机编号加入到序列S_VM的末尾,然后将构件c放置到新创建的虚拟机上(即,构件c的基因取值为新创建的虚拟机编号).重复上述过程,直到S_C中的每一个构件都被放置完成.

3.5 算法流程

基于HGSA的SaaS构件优化放置算法流程如图 5所示,其具体步骤如下:

Step 1. 设置算法参数,包括种群规模s、初始温度T_high、退火系数α、终止温度T_low、交叉概率p_c、内循环次数l、最优染色体P_best.

Step 2. 设置当前温度t=T_high.

Step 3. 根据第3.1节所提出的种群初始化操作,产生初始种群Pop={P₁,P₂,…,P_s},并将Pop中的最优解保存在P_best中.

Step 4. 设置当前内循环次数n=0.

Step 5. 根据第3.2节所提出的比例选择策略,从当前种群Pop中选择s个染色体,并用其替换原染色体.

Step 6. 按照交叉概率p_c,从当前种群Pop中选择$\left\lfloor {s/2} \right\rfloor $对染色体进行交叉操作,产生$\left\lfloor {s/2} \right\rfloor $对新染色体,令$Pop' = \{ {P'_1},{P'_2},...,{P'_s}\} $为新染色体的集合,其中,P_i'为P_i的子染色体.对于Pop'中每个不满足资源约束条件的染色体,按照第3.4节所提出的策略对其进行修复.

Step 7. 对于新种群Pop'中的每个染色体${P'_i}$(i=1,2,…,s),令VN_i为${P'_i}$所对应的虚拟机网络图,VM_i为VN_i中所包含的虚拟机集合,依次检索VM_i中的每个虚拟机,然后按照第3.3节所提出的规则(3)和规则(4)对其进行迁移操作,产生新的染色体${P''_i}$,如果$f({P''_i}{\rm{ }}) < f({P'_i}{\rm{ }}),$则用${P''_i}$替换${P'_i}$;如果$f({P'_i}) < $f(P_best),则用${P'_i}$替换P_best.

Step 8. 对于新种群Pop'中的每个染色体${P'_i}$(i=1,2,…,s),利用Metropolis准则判断其是否替换当前种群Pop中其所对应的父染色体P_i,令$\Delta f = f({P'_i}) - f({P_i})$:

如果Δf<0,则用${P'_i}$替换P_i;

否则,产生一个随机数ξ#8712;(0,1):如果exp(-Δf/(α·t))>ξ,则用${P'_i}$替换P_i;如果f(P_i)<f(P_best),则用P_i替换P_best.

Step 9. 对于当前种群Pop中的每个染色体P_i(i=1,2,…,s),按照第3.3节所提出的规则(1)和规则(2)对其进行构件的迁移和交换操作,产生新的染色体${P'_i}$,利用Metropolis准则判断是否接受该新染色体${P'_i}$.令$\Delta f = f({P'_i}) - f({P_i})$:

如果Δf<0,则用${P'_i}$替换P_i;

否则,产生一个随机数ξ#8712;(0,1):如果exp(-Δf/(α·t))>ξ,则用${P'_i}$替换P_i;如果f(P_i)<f(P_best),则用P_i替换P_best.

Step 10. 令n=n+1,如果n<l,转到Step 5;否则,执行Step 11.

Step 11. 令t=α·t,如果t>T_low,转到Step 4;否则,执行Step 12.

Step 12. 输出最优解P_best.

上述算法的时间复杂度为$O\left( {s \cdot l \cdot {{\log }_\alpha }\left( {\frac{{{T_{low}}}}{{{T_{high}}}}} \right) \cdot |C| \cdot |VM{|^2}} \right),$其中,|C|为构件的数量,|VM|为所使用的虚拟机数量.由于算法每次执行所产生的虚拟机数量是不确定的,因此,|VM|不是固定的常量,$|MV| < \sum\limits_{i = 1}^n {{n_{\max }}(v{c_i})} ,$其中,

n_max(vc_i)表示只选择虚拟模板vc_i所使用的最大虚拟机数量.对于给定的构件模型和虚拟机模板的集合,该值可以通过实验来确定.

4 实验分析 4.1 算法输入

基于HGSA的SaaS构件优化算法的输入为IaaS提供商所发布的虚拟机模板和SaaS提供商所要部署的构件模型.在本实验中,虚拟机模板参考亚马逊EC2的虚拟机模板类型进行设置,我们主要考虑CPU、内存和存储这3种资源.在EC2中,不同虚拟机模板的资源数量和价格是不同的,我们选择了13种虚拟机模板作为实验对象,其配置见表 1.其中,CPU的单位为CU(compute unit),内存的单位是GiB(2³⁰字节),存储的单位是GB,虚拟机价格的单位为$\$ $/h,网络通信的价格为0.01 $\$ $/GB.虚拟机模板的数量可以根据实际需要动态地进行调整.

由于不同的SaaS应用其构件模型是不同的,为了验证本文所提出的算法在解决大规模SaaS应用优化放置方面的处理能力,我们采用仿真的方式动态生成构件模型.在本实验中,构件数量的模拟范围为[10,100],对于每个构件,其CPU需求数量的模拟范围为[0.2,2],内存需求数量的模拟范围为[0.5,3],存储需求数量的范围为[50,200],构件之间的连接关系按照概率[0,0.4]随机生成,其通信量模拟范围为^[1,5].EC2的计费方式主要分为预留和按需两种方式,这里,我们主要考虑按需计费方式,并设定租期为1天(24h).

4.2 算法参数设置

HGSA中的参数包括种群规模s、初始温度T_high、终止温度T_low、退火系数α、内循环次数l和交叉概率p_c.不同的参数对算法的性能和质量具有不同的影响,所以首先要对各种参数进行分析,确定每种参数的变化趋势和最佳的取值范围.

(1) 种群规模s

一般来说,种群规模越大越好,因为如果种群太小容易使算法发生早熟,但是种群规模的扩大也将导致运算时间的延长,从而降低了算法的性能.在本实验中,我们设定种群规模为100.

(2) 初始温度T_high

一般来说,初始温度要足够大,以此来保证算法在开始时处于平衡状态.但是如果初始温度过高,则接受不可行解的概率就会增大,从而导致算法的运行时间过长.本文采用多次随机搜索所得到的适应函数的平均增量方法来确定初始温度.通过逆推Metropolis准则接受概率公式可得${T_{high}} = \frac{{ - \overline {\Delta f} }}{{\ln ({p_0})}}$,其中,p₀为初始接受概率,$\overline {\Delta f} $为初始搜索所得到的适应度平均增量.我们设定p₀=0.8,通过反复实验分析,最终确定T_high=250.

(3) 退火系数α

退火系数α控制温度下降的方式,对于退火系数,通常在0.5~0.95之间取值.通过实验分析发现:在本问题中,退火系数对于解的影响远小于其他参数.因此,根据经验值可设置α=0.9.

(4) 内循环次数l

内循环是指在一个给定的温度下,通过Metropolis准则进行随机搜索,最终达到一种平衡状态的过程.为了保证在每一个温度下算法都能够达到平衡状态,内循环的次数l一般要足够大,但是如果l过大,则会导致邻域搜索时间过长,从而影响算法的性能.为了确定一个较为合适的内循环次数,我们在一系列终止温度条件下,通过不断地增加l取值来观测当前种群全局最优解的变化趋势(执行算法100次,取所有次数的平均值).通过实验分析发现:当构件数量较少时(≤40),内循环次数l对解的质量影响较小.这是因为,当构件数量较少时,虚拟机的使用成本占总成本的比例较高,而HGSA可以快速地搜索到成本最低的虚拟机.图 6给出在构件数量n分别为50,60,70,80,90和100、种群规模s=100、初始温度T_high=250、退火系数α=0.9、交叉概率p_c=0.9、终止温度T_low分别为200,100,10,1,0.1和0.01时的种群全局最优适应度(成本)变化趋势曲线图.从这些曲线可以看出:当l增加至6以后,每种终止温度下种群最优适应度(成本)的下降趋势不大,因此可以设置l≥6.l的具体取值可以根据实际问题的规模来设定.

(5) 终止温度T_low

当初始温度T_high和退火系数α确定以后,可以通过终止温度T_low来控制外循环的执行次数,终止温度可以设定为一个很小的正数.一般来说,终止温度要足够小,以保证算法有足够的时间来获取全局最优/好解.然而,如果终止温度过小则会增加中间温度的数量,进而导致过多的邻域搜索,增加了算法的执行时间.为了确定一个较为合理的终止温度,我们通过不断降低T_low的取值来观测当前种群全局最优解的变化趋势(执行算法100次,取所有次数的平均值).图 7给出了在构件数量n分别为50,60,70,80,90和100、种群规模s=100、初始温度T_high=250、退火系数α=0.9、内循环次数l=6、交叉概率p_c=0.9时的种群全局最优适应度(成本)随终止温度变化趋势曲线图.从这些曲线图可以看出:当T_low降低至0.01以后,种群最优适应度(成本)的下降趋势不大,因此可以设置T_low≤0.01,T_low的具体取值可以根据实际问题的规模来设定.

(6) 交叉概率p_c

交叉概率P_c为各代中交叉产生的后代数与种群中的个体数的比值.一般来说,较高的交叉概率将会达到更大的解空间,从而减少停止在非最优解上的机会.但是,如果交叉概率太高,则会因过多地搜索不必要的解空间而耗费大量的计算时间,从而降低了算法的性能.在HGSA中,交叉概率的设置与终止温度T_high密切相关:如果T_high的值较高,则p_c的值应该设置得低一些,这样可以加快收敛的速度;反之,p_c的值可以设置得高一些,因为这样有更多的机会进行解空间的搜索.图 8给出了在构件数量为100、种群规模s=100、初始温度T_high=250、退火系数α=0.9、内循环次数l=6、终止温度T_high=0.01时的种群全局最优适应度(成本)变化趋势曲线图.

根据该曲线可以看出:当交叉概率较小和较大时,解的质量较好;当交叉概率大于0.8以后,种群最优适应度的下降趋势不大.因此,可以设定p_c≥0.8.

4.3 对比实验

为了验证本文所提出的混合遗传模拟退火算法(HGSA)在求解SaaS构件优化放置问题方面的有效性,我们又单独采用了遗传算法(GA)和模拟退火算法(SA)对该问题进行了求解.

在GA中,由于虚拟机的数量是不确定的,因此,通过交叉操作所产生的新染色体的质量不但没有改进反而在不断地下降.这是因为,交叉操作会增加虚拟机的数量,导致构件的放置更加稀疏,从而增加了放置方案的成本.为了提高GA的求解质量,我们采用本文所提出的新解产生规则(3)和规则(4)对交叉操作后所产生的新解进行了优化,通过实验分析发现其求解质量已显著提高.

传统的SA是从一个初始解开始不断进行邻域搜索来产生新解,因此,初始解的质量对算法的影响比较大.为了提高SA的求解质量,我们从初始种群中选择一个最优解作为SA的初始解.在传统的SA中,邻域搜索是通过改变染色体中某个基因的取值来实现的,该操作相当于本文所提出的邻域搜索规则(1),即,改变构件的放置位置.这一操作的收敛速度比较慢,而且很容易陷入局部最优/好解.为此,我们又将其他3个邻域搜索规则都加入到SA中,从而极大地提高了SA的求解质量.

另外,本文所提出的解初始化方法采用的是一种基于贪心策略的启发式算法(HA),即,每次放置构件都是尽量选择已经存在的虚拟机,这样可以减少虚拟机的使用数量.单独采用HA进行问题求解的运行效率比较高,但是解的质量较差.为了提高HA的求解质量,我们首先采用HA来生成一组解(种群),然后,从中选择一个最优解(相当于SA的初始解)作为HA的最终解.

本文通过实验对上述4种算法(HGSA,GA,SA和HA)的求解质量进行了比较.我们采用模拟的方式随机生成了10个构件模型,其构件数量分别是10,20,…,100,每个构件的资源需求数量以及构件之间通信量按照第4.1节所给出的范围进行随机均匀生成.针对每一构件模型,我们分别采用上述4种算法对其进行求解30次取平均值.为了体现实验的公平性,每次求解它们都是从同一初始种群开始,其中,SA的初始解是该种群中的最优解,HGSA和GA的进化代数和交叉概率是一致的(s=100,p_c=0.9),GA的变异概率设置为0.1.图 9给出了4种算法所计算的总成本(虚拟机使用成本+网络通信成本)的对比分析图.

通过实验分析发现:对于任意给定的初始种群,HGSA求解质量最好,其次是SA,再次是GA,最后是HA.由于SA是在HA的基础上继续进行邻域搜索,因此从理论上来说,SA的求解质量至少不会比HA差.由于HGSA是采用多个解在其邻域内并行搜索的方式,并且利用交叉操作来提高全局搜索能力,因此其求解质量要高于SA.与HGSA和SA相比,GA对该问题的求解能力较弱,这主要是由于虚拟机数量的不确定性而导致搜索范围扩大,尽管我们希望通过相应的邻域搜索规则来改善新解的质量,但其效果仍不理想.

表 2和表 3分别给出了在每一构件数量下,4种算法所计算的虚拟机使用成本和网络通信成本的具体数值.从实验结果可以看出:在每一个构件数量下,HGSA所计算的虚拟机使用成本和网络通信成本都要低于其他3种算法;而且随着构件数量的增加,其求解质量显著提高.这说明HGSA在求解SaaS构件优化放置问题方面具有较好的效果.

4.4 实例分析

本节通过图 1所示的实例来说明HGSA在求解SaaS构件优化放置方面的能力.在该实例中,包含10个构件,每个构件的资源需求以及构件之间的通信如图 10上半部分所示,虚拟机模板采用亚马逊的EC2(具体配置见表 1).利用本文所提出的HGSA算法(算法参数设置为s=100,α=0.9,T_high=250,T_low=0.01,l=6,p_c=0.9),一次即可求得最优SaaS构件放置方案,如图 10下半部分所示.在该方案中,我们选择了2台虚拟机,它们分别是C3.xlarge和I2.2xlarge,其中,I2.2xlarge上放置构件c5,C3.xlarge上放置其他所有构件,假设租期为72h,网络通信价格为0.01$/GB,则最终成本为67.602$.其中,虚拟机使用成本为67.536$,网络通信成本为0.066$.这说明,本文所提出的算法在虚拟机数量不确定的情况下具有较好的效果.

5 结束语

针对传统软件提供商在向SaaS服务模式迁移时所遇到的SaaS构件放置问题,本文提出了一种基于混合遗传模拟退火算法的SaaS构件优化放置方法,其优化目标是提高云资源利用率、降低云资源使用成本.尽管目前存在许多SaaS优化放置方法,但是这些方法都假定云环境中虚拟机的类型和数量是确定的,即,在限定的资源上进行优化放置;然而实际情况是:虚拟机的类型和数量一般都是不确定的,需要根据被部署的构件资源需求来确定.而本文所提出的SaaS构件优化放置模型弥补了这些方法的不足.本文采用混合遗传模拟退火算法HGSA对SaaS构件优化放置问题进行求解,HGSA算法结合了遗传算法和模拟退火算法的优点,克服了GA收敛速度慢和SA容易陷入局部最优的缺点,与单独使用遗传算法和模拟退火算法相比,HGSA算法具有更高的求解质量.从云架构角度来看,本文所提出的放置方法不仅适用于公有云基础设施的放置,同时也适用于私有云基础设施的放置.从软件生命周期阶段来看,本文所提出的放置方法不仅适用于SaaS的初始部署,而且也适用于SaaS运行阶段的动态部署.