胡龍茂,王會(huì)穎
(安徽財(cái)貿(mào)職業(yè)學(xué)院,安徽 合肥 230601)
?
基于螢火蟲(chóng)算法的多租戶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)境下租戶的響應(yīng)時(shí)間性能需求,建立最小化SaaS提供商的虛擬機(jī)費(fèi)用模型,然后將SaaS部署問(wèn)題分解為裝箱問(wèn)題,最后采用物品編碼方式,提出利用具有良好全局尋優(yōu)能力的螢火蟲(chóng)算法求解多租戶SaaS部署的優(yōu)化方案.
關(guān)鍵詞:SaaS;多租戶;虛擬機(jī)費(fèi)用;螢火蟲(chóng)算法;優(yōu)化
軟件即服務(wù) (Software as a Service, SaaS)是云計(jì)算在應(yīng)用層提供的服務(wù),在此模式下,客戶無(wú)需購(gòu)買和維護(hù)軟件,而是按需租用服務(wù)提供商的軟件服務(wù),由服務(wù)提供商負(fù)責(zé)軟件的開(kāi)發(fā)、部署、組合、維護(hù).SaaS的典型特征是不同的租戶共享軟件的同一實(shí)例,這些實(shí)例對(duì)租戶而言是透明的,租戶無(wú)需了解服務(wù)部署的位置,也無(wú)需擔(dān)心服務(wù)的質(zhì)量,服務(wù)就像是獨(dú)占的[1].對(duì)于租戶提出的SaaS應(yīng)用請(qǐng)求,SaaS服務(wù)提供商部署一定數(shù)量的應(yīng)用實(shí)例,這些應(yīng)用實(shí)例將安裝在向云基礎(chǔ)設(shè)施提供商租用的虛擬機(jī)上面.從SaaS服務(wù)提供者的成本角度而言,其優(yōu)化目標(biāo)是在滿足每個(gè)租戶服務(wù)級(jí)別協(xié)議(Service Level Agreement,SLA)的條件下,使租用的虛擬機(jī)的總費(fèi)用最低.
多租戶SaaS環(huán)境下的資源分配是一個(gè)典型的組合優(yōu)化問(wè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多租戶SaaS模型及數(shù)學(xué)描述
云平臺(tái)中多租戶SaaS模型主要包括租戶、SaaS提供商和組成云基礎(chǔ)設(shè)施(IaaS)的虛擬機(jī),如圖1所示.租戶是租用Web軟件的客戶.SaaS提供商對(duì)外提供多種SaaS應(yīng)用,當(dāng)一個(gè)或多個(gè)租戶需要租用某種應(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)用也不一樣,客戶可以根據(jù)自身情況租用合適的虛擬機(jī).
圖1 多租戶SaaS模型
設(shè)某SaaS提供商有m個(gè)租戶,提供n種SaaS應(yīng)用.每種應(yīng)用可以部署多個(gè)應(yīng)用實(shí)例,租戶和應(yīng)用實(shí)例之間是多對(duì)多的聯(lián)系.應(yīng)用實(shí)例部署在租來(lái)的p類虛擬機(jī)上,每類虛擬機(jī)包括q種資源,如處理能力、內(nèi)存及I/O性能等.每個(gè)租戶在使用應(yīng)用前要用
SaaS提供商簽訂SLA,SLA規(guī)定了應(yīng)用實(shí)例所應(yīng)達(dá)到的性能.
基于費(fèi)用優(yōu)化的多租戶SaaS部署的數(shù)學(xué)模型如下:
i=1,2,…,q;j=1,2,…,p
(1)
其中,在目標(biāo)函數(shù)中,countj表示第j類虛擬機(jī)的數(shù)量,evaluej表示第j類虛擬機(jī)的租用價(jià)格.在約束條件中,consumeijk表示虛擬機(jī)j上部署第第k個(gè)實(shí)例所消耗的i類資源量,在達(dá)到響應(yīng)時(shí)間的性能需求下,consumeijk與并發(fā)用戶數(shù)成線性關(guān)系[5];casej表示在虛擬機(jī)j上部署的實(shí)例數(shù)量;allowij表示虛擬機(jī)j上第i類資源的最大利用率;consumeij表示虛擬機(jī)j上第i類資源的消耗量.
多租戶SaaS部署問(wèn)題可以看作是將x個(gè)物品裝到y(tǒng)個(gè)箱子的裝箱問(wèn)題,其中,每個(gè)物品代表一個(gè)應(yīng)用實(shí)例及其所對(duì)應(yīng)的租戶,每個(gè)箱子代表一個(gè)虛擬機(jī).因此多租戶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)算法的多租戶SaaS優(yōu)化部署
3.1SaaS部署的編碼方式
設(shè)有租戶集合U={U1,U2,…,Um}、應(yīng)用集合A={A1,A2,…,An}及租約關(guān)系集合UA?U×A,SaaS部署的編碼如下:
(1)將每一個(gè)租約關(guān)系(Ui,Aj)∈UA映射為一個(gè)租戶-應(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)物品,以此類推,最后裝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í),租戶-應(yīng)用實(shí)例關(guān)系也被合并.
3.2算法流程
求解多租戶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)滿足結(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ò)將租戶和SaaS應(yīng)用的簽訂的租約關(guān)系進(jìn)行分解,使得SaaS部署問(wèn)題成為一個(gè)裝箱問(wèn)題,采用基于物品的編碼方式,利用螢火蟲(chóng)算法求解最優(yōu)目標(biāo)值和最優(yōu)解.對(duì)于多租戶SaaS優(yōu)化部署問(wèn)題,以往多采用遺傳算法、蟻群算法[5-6]等進(jìn)行求解,本文的解決方案提供了另一條多租戶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)化的多租戶SaaS應(yīng)用優(yōu)化放置算法[J].計(jì)算機(jī)集成制造系統(tǒng),2014(06):1508-1518.
[6]王會(huì)穎,倪志偉,伍章俊,等.基于MapReduce和多目標(biāo)蟻群算法的多租戶服務(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)算法及其在多租戶SaaS優(yōu)化部署中的研究與應(yīng)用”(KJ2016A009)
作者簡(jiǎn)介:胡龍茂,男,安徽太湖人,講師.
中圖分類號(hào):TP301.6
文獻(xiàn)標(biāo)志碼:A
文章編號(hào):1008-7974(2016)03-0007-03
通化師范學(xué)院學(xué)報(bào)2016年6期