基于萤火虫算法的多租户SaaS优化部署研究*

胡龙茂，王会颖

(安徽财贸职业学院，安徽 合肥 230601)



基于萤火虫算法的多租户SaaS优化部署研究*

胡龙茂，王会颖

(安徽财贸职业学院，安徽 合肥 230601)

摘要:软件即服务(SaaS)日益成为云计算环境下的软件交付模式，SaaS的部署费用也成为SaaS提供商关注的问题.该文首先针对SaaS环境下租户的响应时间性能需求，建立最小化SaaS提供商的虚拟机费用模型，然后将SaaS部署问题分解为装箱问题，最后采用物品编码方式，提出利用具有良好全局寻优能力的萤火虫算法求解多租户SaaS部署的优化方案.

关键词:SaaS；多租户；虚拟机费用；萤火虫算法；优化

软件即服务 (Software as a Service, SaaS)是云计算在应用层提供的服务，在此模式下，客户无需购买和维护软件，而是按需租用服务提供商的软件服务，由服务提供商负责软件的开发、部署、组合、维护.SaaS的典型特征是不同的租户共享软件的同一实例，这些实例对租户而言是透明的，租户无需了解服务部署的位置，也无需担心服务的质量，服务就像是独占的[1].对于租户提出的SaaS应用请求，SaaS服务提供商部署一定数量的应用实例，这些应用实例将安装在向云基础设施提供商租用的虚拟机上面.从SaaS服务提供者的成本角度而言，其优化目标是在满足每个租户服务级别协议(Service Level Agreement,SLA)的条件下，使租用的虚拟机的总费用最低.

多租户SaaS环境下的资源分配是一个典型的组合优化问题，适合采用非线性方法进行求解.剑桥学者Yang在2008年提出的萤火虫算法(Firefly Algorith,FA)[2]是一种仿生智能群算法，应用于处理函数优化问题及组合优化问题，通过调整参数，能获得比随机搜索和粒子群算法更好的性能[3-4]，本文研究了萤火虫算法在分配虚拟机资源中的优化部署问题.

1多租户SaaS模型及数学描述

云平台中多租户SaaS模型主要包括租户、SaaS提供商和组成云基础设施(IaaS)的虚拟机，如图1所示.租户是租用Web软件的客户.SaaS提供商对外提供多种SaaS应用，当一个或多个租户需要租用某种应用时，SaaS提供商根据SLA计算出需要部署的应用的实例数目，然后通过某种策略将这些实例部署到向云基础设施提供商租来的虚拟机上.IaaS供应的虚拟机有多种型号，其CPU性能、存储容量及通道性能均不一样，其使用费用也不一样，客户可以根据自身情况租用合适的虚拟机.

图1　多租户SaaS模型

设某SaaS提供商有m个租户，提供n种SaaS应用.每种应用可以部署多个应用实例，租户和应用实例之间是多对多的联系.应用实例部署在租来的p类虚拟机上，每类虚拟机包括q种资源，如处理能力、内存及I/O性能等.每个租户在使用应用前要用

SaaS提供商签订SLA，SLA规定了应用实例所应达到的性能.

基于费用优化的多租户SaaS部署的数学模型如下：

i=1,2,…,q;j=1,2,…,p

(1)

其中，在目标函数中，countj表示第j类虚拟机的数量，evaluej表示第j类虚拟机的租用价格.在约束条件中，consumeijk表示虚拟机j上部署第第k个实例所消耗的i类资源量，在达到响应时间的性能需求下，consumeijk与并发用户数成线性关系[5]；casej表示在虚拟机j上部署的实例数量；allowij表示虚拟机j上第i类资源的最大利用率；consumeij表示虚拟机j上第i类资源的消耗量.

多租户SaaS部署问题可以看作是将x个物品装到y个箱子的装箱问题，其中，每个物品代表一个应用实例及其所对应的租户，每个箱子代表一个虚拟机.因此多租户SaaS部署问题是NP问题，时间复杂度高，本文采用萤火虫算法来求解近似最优方案.

2萤火虫算法

萤火虫算法通过模拟自然界中萤火虫的群体行为实现目标优化.萤火虫的亮度越高，其吸引力也越大，会吸引亮度较弱的萤火虫向其移动.随着距离的增大，萤火虫的亮度和吸引力逐渐减少.萤火虫的亮度由其所处位置的目标值而确定，位置越佳，亮度越高.在萤火虫算法中，用萤火虫个体表示搜索空间的点，用目标函数值表示个体所处位置的好坏，萤火虫个体的移动即较优解取代劣解的过程，通过个体位置的不断变化，最终达到优化结果.萤火虫算法的定义[2]如下：

定义1萤火虫的相对亮度为:

I=I0e-γrij2

(2)

其中，I0为萤火虫的原始亮度，即自身(r=0)亮度，取决于目标函数，目标函数所处位置越好则原始亮度越高；γ为光吸收系数，表征了媒介对光的吸收效果；rij为萤火虫i和j间的距离.

定义2萤火虫的吸引力：

β=β0e-γr2

(3)

其中，β0是在r=0处的吸引力.

定义3萤火虫i向更有吸引力的萤火虫j移动的位置变化：

xi=xi+β(xj-xi)+α(rand-1/2)

(4)

其中，xi、xj为萤火虫的坐标；α∈[0,1]为步长因子；rand为[0,1]区间均匀分布的随机数发生器.

3基于萤火虫算法的多租户SaaS优化部署

3.1SaaS部署的编码方式

设有租户集合U={U1,U2,…,Um}、应用集合A={A1,A2,…,An}及租约关系集合UA⊆U×A，SaaS部署的编码如下：

(1)将每一个租约关系(Ui,Aj)∈UA映射为一个租户-应用实例关系.如{(U1,A1),(U2,A1)}生成{(U1,C1),(U2,C2)}，其中C1和C2都是A2的实例.

(2)装箱编码方式.将步骤(1)中生成的应用实例看成是物品，采用基于物品的编码进行装箱，如编码x={2,5,1,4,3}表示先装2号物品，然后再装5号物品，以此类推，最后装3号物品.

(3)装箱策略.常用的装箱策略有下次适应算法、首次适应算法和最佳适应算法等.本文采用首次适应算法.将当前物品装箱时，查找非空箱子，当找到一个非空箱能装下当前物品时，则将其装箱；如未找到这样的非空箱，则开启新的箱子.

(4)不同编码的距离计算.编码xi和xj的第k个分量的距离定义如下：

(5)

那么编码xi和xj之间的距离

(6)

在装箱过程中，如果属于同一个应用的多个实例被安装到同一台虚拟机上，则这多个实例被合并成一个实例，与此同时，租户-应用实例关系也被合并.

3.2算法流程

求解多租户SaaS优化部署的萤火虫算法流程如下.

步骤1初始化基本参数.包括萤火虫数目n，光吸收系数γ，最大吸引力β0，步长因子α，最大迭代次数maxT.

步骤2初始化萤火虫的位置.对于SaaS部署问题，将所有的应用实例进行排序编码，一个萤火虫表示一种编码方式，将萤火虫随机放置在解空间中.

步骤3按照式(1)计算萤火虫的目标函数值作为原始亮度，按照式(2)(3)计算萤火虫的相对亮度和吸引力(萤火虫之间的距离按式(6)进行计算)，根据相对亮度决定萤火虫的移动方向.

步骤4按照式(4)更新萤火虫的位置，由于物品编码顺序都是整数值，故需将更新后的位置四舍五入成整数值.

步骤5当满足结束条件时，跳转步骤6输出结果；否则，转步骤3.

步骤6输出最优目标值，并按照3.1节输出最优部署方案.

4结语

萤火虫算法利用个体趋向最亮的萤火虫来实现目标寻优，适用于函数优化和组合优化问题.本文通过将租户和SaaS应用的签订的租约关系进行分解，使得SaaS部署问题成为一个装箱问题，采用基于物品的编码方式，利用萤火虫算法求解最优目标值和最优解.对于多租户SaaS优化部署问题，以往多采用遗传算法、蚁群算法[5-6]等进行求解，本文的解决方案提供了另一条多租户SaaS优化部署的可行途径.

参考文献：

[1]Shi Y L,Luan S,Li Q Z,et al.TLA Based Customization and Verification Mechanism of Business Process for SaaS[J].Chinese Journal of Computers,2010,33(11):2055-2067(in Chinese)(史玉良,栾帅,李庆忠,等.基于TLA的SaaS业务流程定制及验证机制研究[J].计算机学报,2010,33(11):2055-2067.

[2]Yang X S.Nature-inspired metaheuristic algorithm [M].[S.l]：Luniver Press,2008：83-96．

[3]Yang X S.Firefly algorithms for multimodal optimization[C].Lectrue Notes in Computer Science,2009,5792:169-178.

[4]Yang X S,DEB S.Eagle strategy using levy walk and firefly algorithms for stochastic optimization[J]．Studies in Computational Intelligence，2010，284：101-111．

[5]孟凡超,周学权,曹祖凤,初佃辉,战德臣.基于成本优化的多租户SaaS应用优化放置算法[J].计算机集成制造系统,2014(06):1508-1518.

[6]王会颖,倪志伟,伍章俊，等.基于MapReduce和多目标蚁群算法的多租户服务定制算法[J].模式识别与人工智能,2014,(12):1105-1116.

(责任编辑:王前)

DOI:10.13877/j.cnki.cn22-1284.2016.06.003

*收稿日期：2016-01-24

基金项目：安徽省高校自然科学研究重点项目“基于MapReduce的萤火虫算法及其在多租户SaaS优化部署中的研究与应用”(KJ2016A009)

作者简介：胡龙茂，男，安徽太湖人，讲师.

中图分类号：TP301.6

文献标志码：A

文章编号：1008-7974(2016)03-0007-03