基于螢火蟲(chóng)算法的多租戶(hù)SaaS優(yōu)化部署研究*

胡龍茂，王會(huì)穎

(安徽財(cái)貿(mào)職業(yè)學(xué)院，安徽 合肥 230601)

?

基于螢火蟲(chóng)算法的多租戶(hù)SaaS優(yōu)化部署研究*

胡龍茂，王會(huì)穎

(安徽財(cái)貿(mào)職業(yè)學(xué)院，安徽 合肥 230601)

摘要:軟件即服務(wù)(SaaS)日益成為云計(jì)算環(huán)境下的軟件交付模式，SaaS的部署費(fèi)用也成為SaaS提供商關(guān)注的問(wèn)題.該文首先針對(duì)SaaS環(huán)境下租戶(hù)的響應(yīng)時(shí)間性能需求，建立最小化SaaS提供商的虛擬機(jī)費(fèi)用模型，然后將SaaS部署問(wèn)題分解為裝箱問(wèn)題，最后采用物品編碼方式，提出利用具有良好全局尋優(yōu)能力的螢火蟲(chóng)算法求解多租戶(hù)SaaS部署的優(yōu)化方案.

關(guān)鍵詞:SaaS；多租戶(hù)；虛擬機(jī)費(fèi)用；螢火蟲(chóng)算法；優(yōu)化

軟件即服務(wù) (Software as a Service, SaaS)是云計(jì)算在應(yīng)用層提供的服務(wù)，在此模式下，客戶(hù)無(wú)需購(gòu)買(mǎi)和維護(hù)軟件，而是按需租用服務(wù)提供商的軟件服務(wù)，由服務(wù)提供商負(fù)責(zé)軟件的開(kāi)發(fā)、部署、組合、維護(hù).SaaS的典型特征是不同的租戶(hù)共享軟件的同一實(shí)例，這些實(shí)例對(duì)租戶(hù)而言是透明的，租戶(hù)無(wú)需了解服務(wù)部署的位置，也無(wú)需擔(dān)心服務(wù)的質(zhì)量，服務(wù)就像是獨(dú)占的[1].對(duì)于租戶(hù)提出的SaaS應(yīng)用請(qǐng)求，SaaS服務(wù)提供商部署一定數(shù)量的應(yīng)用實(shí)例，這些應(yīng)用實(shí)例將安裝在向云基礎(chǔ)設(shè)施提供商租用的虛擬機(jī)上面.從SaaS服務(wù)提供者的成本角度而言，其優(yōu)化目標(biāo)是在滿(mǎn)足每個(gè)租戶(hù)服務(wù)級(jí)別協(xié)議(Service Level Agreement,SLA)的條件下，使租用的虛擬機(jī)的總費(fèi)用最低.

多租戶(hù)SaaS環(huán)境下的資源分配是一個(gè)典型的組合優(yōu)化問(wèn)題，適合采用非線(xiàn)性方法進(jìn)行求解.劍橋?qū)W者Yang在2008年提出的螢火蟲(chóng)算法(Firefly Algorith,FA)[2]是一種仿生智能群算法，應(yīng)用于處理函數(shù)優(yōu)化問(wèn)題及組合優(yōu)化問(wèn)題，通過(guò)調(diào)整參數(shù)，能獲得比隨機(jī)搜索和粒子群算法更好的性能[3-4]，本文研究了螢火蟲(chóng)算法在分配虛擬機(jī)資源中的優(yōu)化部署問(wèn)題.

1多租戶(hù)SaaS模型及數(shù)學(xué)描述

云平臺(tái)中多租戶(hù)SaaS模型主要包括租戶(hù)、SaaS提供商和組成云基礎(chǔ)設(shè)施(IaaS)的虛擬機(jī)，如圖1所示.租戶(hù)是租用Web軟件的客戶(hù).SaaS提供商對(duì)外提供多種SaaS應(yīng)用，當(dāng)一個(gè)或多個(gè)租戶(hù)需要租用某種應(yīng)用時(shí)，SaaS提供商根據(jù)SLA計(jì)算出需要部署的應(yīng)用的實(shí)例數(shù)目，然后通過(guò)某種策略將這些實(shí)例部署到向云基礎(chǔ)設(shè)施提供商租來(lái)的虛擬機(jī)上.IaaS供應(yīng)的虛擬機(jī)有多種型號(hào)，其CPU性能、存儲(chǔ)容量及通道性能均不一樣，其使用費(fèi)用也不一樣，客戶(hù)可以根據(jù)自身情況租用合適的虛擬機(jī).

圖1　多租戶(hù)SaaS模型

設(shè)某SaaS提供商有m個(gè)租戶(hù)，提供n種SaaS應(yīng)用.每種應(yīng)用可以部署多個(gè)應(yīng)用實(shí)例，租戶(hù)和應(yīng)用實(shí)例之間是多對(duì)多的聯(lián)系.應(yīng)用實(shí)例部署在租來(lái)的p類(lèi)虛擬機(jī)上，每類(lèi)虛擬機(jī)包括q種資源，如處理能力、內(nèi)存及I/O性能等.每個(gè)租戶(hù)在使用應(yīng)用前要用

SaaS提供商簽訂SLA，SLA規(guī)定了應(yīng)用實(shí)例所應(yīng)達(dá)到的性能.

基于費(fèi)用優(yōu)化的多租戶(hù)SaaS部署的數(shù)學(xué)模型如下：

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

(1)

其中，在目標(biāo)函數(shù)中，countj表示第j類(lèi)虛擬機(jī)的數(shù)量，evaluej表示第j類(lèi)虛擬機(jī)的租用價(jià)格.在約束條件中，consumeijk表示虛擬機(jī)j上部署第第k個(gè)實(shí)例所消耗的i類(lèi)資源量，在達(dá)到響應(yīng)時(shí)間的性能需求下，consumeijk與并發(fā)用戶(hù)數(shù)成線(xiàn)性關(guān)系[5]；casej表示在虛擬機(jī)j上部署的實(shí)例數(shù)量；allowij表示虛擬機(jī)j上第i類(lèi)資源的最大利用率；consumeij表示虛擬機(jī)j上第i類(lèi)資源的消耗量.

多租戶(hù)SaaS部署問(wèn)題可以看作是將x個(gè)物品裝到y(tǒng)個(gè)箱子的裝箱問(wèn)題，其中，每個(gè)物品代表一個(gè)應(yīng)用實(shí)例及其所對(duì)應(yīng)的租戶(hù)，每個(gè)箱子代表一個(gè)虛擬機(jī).因此多租戶(hù)SaaS部署問(wèn)題是NP問(wèn)題，時(shí)間復(fù)雜度高，本文采用螢火蟲(chóng)算法來(lái)求解近似最優(yōu)方案.

2螢火蟲(chóng)算法

螢火蟲(chóng)算法通過(guò)模擬自然界中螢火蟲(chóng)的群體行為實(shí)現(xiàn)目標(biāo)優(yōu)化.螢火蟲(chóng)的亮度越高，其吸引力也越大，會(huì)吸引亮度較弱的螢火蟲(chóng)向其移動(dòng).隨著距離的增大，螢火蟲(chóng)的亮度和吸引力逐漸減少.螢火蟲(chóng)的亮度由其所處位置的目標(biāo)值而確定，位置越佳，亮度越高.在螢火蟲(chóng)算法中，用螢火蟲(chóng)個(gè)體表示搜索空間的點(diǎn)，用目標(biāo)函數(shù)值表示個(gè)體所處位置的好壞，螢火蟲(chóng)個(gè)體的移動(dòng)即較優(yōu)解取代劣解的過(guò)程，通過(guò)個(gè)體位置的不斷變化，最終達(dá)到優(yōu)化結(jié)果.螢火蟲(chóng)算法的定義[2]如下：

定義1螢火蟲(chóng)的相對(duì)亮度為:

I=I0e-γrij2

(2)

其中，I0為螢火蟲(chóng)的原始亮度，即自身(r=0)亮度，取決于目標(biāo)函數(shù)，目標(biāo)函數(shù)所處位置越好則原始亮度越高；γ為光吸收系數(shù)，表征了媒介對(duì)光的吸收效果；rij為螢火蟲(chóng)i和j間的距離.

定義2螢火蟲(chóng)的吸引力：

β=β0e-γr2

(3)

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

定義3螢火蟲(chóng)i向更有吸引力的螢火蟲(chóng)j移動(dòng)的位置變化：

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

(4)

其中，xi、xj為螢火蟲(chóng)的坐標(biāo)；α∈[0,1]為步長(zhǎng)因子；rand為[0,1]區(qū)間均勻分布的隨機(jī)數(shù)發(fā)生器.

3基于螢火蟲(chóng)算法的多租戶(hù)SaaS優(yōu)化部署

3.1SaaS部署的編碼方式

設(shè)有租戶(hù)集合U={U1,U2,…,Um}、應(yīng)用集合A={A1,A2,…,An}及租約關(guān)系集合UA?U×A，SaaS部署的編碼如下：

(1)將每一個(gè)租約關(guān)系(Ui,Aj)∈UA映射為一個(gè)租戶(hù)-應(yīng)用實(shí)例關(guān)系.如{(U1,A1),(U2,A1)}生成{(U1,C1),(U2,C2)}，其中C1和C2都是A2的實(shí)例.

(2)裝箱編碼方式.將步驟(1)中生成的應(yīng)用實(shí)例看成是物品，采用基于物品的編碼進(jìn)行裝箱，如編碼x={2,5,1,4,3}表示先裝2號(hào)物品，然后再裝5號(hào)物品，以此類(lèi)推，最后裝3號(hào)物品.

(3)裝箱策略.常用的裝箱策略有下次適應(yīng)算法、首次適應(yīng)算法和最佳適應(yīng)算法等.本文采用首次適應(yīng)算法.將當(dāng)前物品裝箱時(shí)，查找非空箱子，當(dāng)找到一個(gè)非空箱能裝下當(dāng)前物品時(shí)，則將其裝箱；如未找到這樣的非空箱，則開(kāi)啟新的箱子.

(4)不同編碼的距離計(jì)算.編碼xi和xj的第k個(gè)分量的距離定義如下：

(5)

那么編碼xi和xj之間的距離

(6)

在裝箱過(guò)程中，如果屬于同一個(gè)應(yīng)用的多個(gè)實(shí)例被安裝到同一臺(tái)虛擬機(jī)上，則這多個(gè)實(shí)例被合并成一個(gè)實(shí)例，與此同時(shí)，租戶(hù)-應(yīng)用實(shí)例關(guān)系也被合并.

3.2算法流程

求解多租戶(hù)SaaS優(yōu)化部署的螢火蟲(chóng)算法流程如下.

步驟1初始化基本參數(shù).包括螢火蟲(chóng)數(shù)目n，光吸收系數(shù)γ，最大吸引力β0，步長(zhǎng)因子α，最大迭代次數(shù)maxT.

步驟2初始化螢火蟲(chóng)的位置.對(duì)于SaaS部署問(wèn)題，將所有的應(yīng)用實(shí)例進(jìn)行排序編碼，一個(gè)螢火蟲(chóng)表示一種編碼方式，將螢火蟲(chóng)隨機(jī)放置在解空間中.

步驟3按照式(1)計(jì)算螢火蟲(chóng)的目標(biāo)函數(shù)值作為原始亮度，按照式(2)(3)計(jì)算螢火蟲(chóng)的相對(duì)亮度和吸引力(螢火蟲(chóng)之間的距離按式(6)進(jìn)行計(jì)算)，根據(jù)相對(duì)亮度決定螢火蟲(chóng)的移動(dòng)方向.

步驟4按照式(4)更新螢火蟲(chóng)的位置，由于物品編碼順序都是整數(shù)值，故需將更新后的位置四舍五入成整數(shù)值.

步驟5當(dāng)滿(mǎn)足結(jié)束條件時(shí)，跳轉(zhuǎn)步驟6輸出結(jié)果；否則，轉(zhuǎn)步驟3.

步驟6輸出最優(yōu)目標(biāo)值，并按照3.1節(jié)輸出最優(yōu)部署方案.

4結(jié)語(yǔ)

螢火蟲(chóng)算法利用個(gè)體趨向最亮的螢火蟲(chóng)來(lái)實(shí)現(xiàn)目標(biāo)尋優(yōu)，適用于函數(shù)優(yōu)化和組合優(yōu)化問(wèn)題.本文通過(guò)將租戶(hù)和SaaS應(yīng)用的簽訂的租約關(guān)系進(jìn)行分解，使得SaaS部署問(wèn)題成為一個(gè)裝箱問(wèn)題，采用基于物品的編碼方式，利用螢火蟲(chóng)算法求解最優(yōu)目標(biāo)值和最優(yōu)解.對(duì)于多租戶(hù)SaaS優(yōu)化部署問(wèn)題，以往多采用遺傳算法、蟻群算法[5-6]等進(jìn)行求解，本文的解決方案提供了另一條多租戶(hù)SaaS優(yōu)化部署的可行途徑.

參考文獻(xiàn)：

[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業(yè)務(wù)流程定制及驗(yàn)證機(jī)制研究[J].計(jì)算機(jī)學(xué)報(bào),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]孟凡超,周學(xué)權(quán),曹祖鳳,初佃輝,戰(zhàn)德臣.基于成本優(yōu)化的多租戶(hù)SaaS應(yīng)用優(yōu)化放置算法[J].計(jì)算機(jī)集成制造系統(tǒng),2014(06):1508-1518.

[6]王會(huì)穎,倪志偉,伍章俊，等.基于MapReduce和多目標(biāo)蟻群算法的多租戶(hù)服務(wù)定制算法[J].模式識(shí)別與人工智能,2014,(12):1105-1116.

(責(zé)任編輯:王前)

DOI:10.13877/j.cnki.cn22-1284.2016.06.003

*收稿日期：2016-01-24

基金項(xiàng)目：安徽省高校自然科學(xué)研究重點(diǎn)項(xiàng)目“基于MapReduce的螢火蟲(chóng)算法及其在多租戶(hù)SaaS優(yōu)化部署中的研究與應(yīng)用”(KJ2016A009)

作者簡(jiǎn)介：胡龍茂，男，安徽太湖人，講師.

中圖分類(lèi)號(hào)：TP301.6

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1008-7974(2016)03-0007-03