基于成本優(yōu)化的多租戶SaaS應(yīng)用優(yōu)化放置算法

孟凡超，周學(xué)權(quán)，曹祖鳳，初佃輝，戰(zhàn)德臣

（哈爾濱工業(yè)大學(xué)（威海）企業(yè)與服務(wù)智能計(jì)算研究中心，山東 威海 264209）

0 引言

隨著云計(jì)算的出現(xiàn)，IT領(lǐng)域正在進(jìn)行著一場(chǎng)深刻的變革。云計(jì)算是一種新型的計(jì)算模型，它將IT資源、數(shù)據(jù)和應(yīng)用作為服務(wù)，通過(guò)互聯(lián)網(wǎng)提供給用戶［1］。云計(jì)算根據(jù)其服務(wù)類型可分為基礎(chǔ)設(shè)施即服務(wù)（Infrastructure as a Service，IaaS）、平臺(tái)即服務(wù)（Platform as a Service，PaaS）和軟件即服務(wù)（Software as a Service，SaaS）。在SaaS模式下，客戶不需要購(gòu)買完整的軟件系統(tǒng)，也不需要配備相應(yīng)的硬件系統(tǒng)和維護(hù)人員，只需通過(guò)互聯(lián)網(wǎng)按需租用應(yīng)用軟件即可，這對(duì)成本預(yù)算有限、技術(shù)條件不足的中小企業(yè)來(lái)說(shuō)，具有很強(qiáng)的吸引力［2］。

在云計(jì)算環(huán)境下，SaaS主要涉及客戶（也稱為租戶）、SaaS提供商和云基礎(chǔ)設(shè)施提供商［3］三類角色。租戶租用SaaS提供商所提供的SaaS應(yīng)用來(lái)滿足自己的業(yè)務(wù)需求，每個(gè)租戶可以租用一個(gè)或多個(gè)SaaS應(yīng)用。SaaS提供商通過(guò)向租戶提供SaaS應(yīng)用服務(wù)來(lái)獲取利潤(rùn)，每個(gè)SaaS應(yīng)用可以部署多個(gè)實(shí)例，這些實(shí)例被部署在云基礎(chǔ)設(shè)施提供商所提供的虛擬機(jī)上，例如，Amazon的彈性計(jì)算云EC2，或者部署在自己的服務(wù)器或虛擬機(jī)上，本文主要研究前者，即租用云基礎(chǔ)設(shè)施提供商的虛擬機(jī)，此時(shí)SaaS提供商需要向云基礎(chǔ)設(shè)施提供商支付相應(yīng)的租金［4］。云基礎(chǔ)設(shè)施提供商對(duì)外提供一組虛擬機(jī)模板，由同一模板所生成的虛擬機(jī)具有相同的資源配置和價(jià)格，例如，亞馬遜提供的虛擬機(jī)模板有m1．small，m1．large和 m1．large等［5］。

基于成本優(yōu)化的SaaS應(yīng)用放置是指在SaaS應(yīng)用部署的初始階段，SaaS提供商根據(jù)已有租戶的數(shù)量以及對(duì)每類租戶市場(chǎng)規(guī)模的預(yù)測(cè)，確定應(yīng)部署的SaaS應(yīng)用實(shí)例的數(shù)量和租用每一類虛擬機(jī)的數(shù)量，并建立租戶與SaaS應(yīng)用實(shí)例，以及SaaS應(yīng)用實(shí)例與虛擬機(jī)之間的放置關(guān)系，其優(yōu)化目標(biāo)是在滿足每個(gè)租戶服務(wù)級(jí)別協(xié)議（Service Level Agreement，SLA）的條件下，使租用的虛擬機(jī)的總成本最低。

1 相關(guān)工作

針對(duì)多租戶SaaS應(yīng)用優(yōu)化放置問(wèn)題，國(guó)內(nèi)外學(xué)者已經(jīng)展開了許多研究。Kwok等提出一種多租戶SaaS應(yīng)用實(shí)例資源消耗度量模型，該模型描述了SaaS應(yīng)用實(shí)例的資源消耗與租戶數(shù)量和用戶數(shù)量之間的關(guān)系，基于該模型，又提出了一種租戶放置算法并開發(fā)了相應(yīng)的支撐工具［6］。Zhang等擴(kuò)展了Kwok等所提出的資源消耗度量模型，加入了服務(wù)響應(yīng)時(shí)間的約束，并提出一種啟發(fā)式在線租戶放置算法［7］。Wu 等 站 在 SaaS 提 供 商 的 角 度［3－4］，提 出了基于SLA的SaaS應(yīng)用資源分配算法以降低租用虛擬機(jī)的成本，并通過(guò)仿真實(shí)驗(yàn)來(lái)模擬在線租戶放置過(guò)程。Yu等提出了面向租戶服務(wù)質(zhì)量（Quality of Service，QoS）的資源優(yōu)化分配模型，同時(shí)給出啟發(fā)式算法和遺傳算法，并對(duì)這兩種算法的性能進(jìn)行了比較［8］。汪德帥等面向租約用戶的非功能需求，提出一種支持多租約SaaS應(yīng)用按需服務(wù)的負(fù)載均衡策略［9］。Izzah等研究了構(gòu)件化的SaaS應(yīng)用優(yōu)化部署問(wèn)題，提出一種基于懲罰的遺傳算法來(lái)求解最優(yōu)SaaS放置方案［10］。Yang等針對(duì)基于服務(wù)的SaaS應(yīng)用，提出一個(gè)基于案例推理（Case－Based Reasoning，CBR）的混合租戶放置方法［11］。

多租戶SaaS應(yīng)用放置可分為租戶放置和SaaS應(yīng)用實(shí)例放置兩方面，租戶放置是指確定租戶與SaaS應(yīng)用實(shí)例之間的服務(wù)關(guān)系；SaaS應(yīng)用實(shí)例放置是指建立SaaS應(yīng)用實(shí)例與服務(wù)器或虛擬機(jī)之間的部署關(guān)系。然而，現(xiàn)有研究大多針對(duì)租戶放置［3－4，6－9，11］，對(duì) SaaS 應(yīng) 用 實(shí) 例 放 置 的 研 究 比 較 少。有些研究雖然也考慮了資源的預(yù)分配［8－9］和SaaS應(yīng)用實(shí)例的放置策略［10］，但都是在給定服務(wù)器/虛擬機(jī)的數(shù)量，即限定資源數(shù)量的基礎(chǔ)上進(jìn)行的優(yōu)化，然而現(xiàn)實(shí)情況是服務(wù)器/虛擬機(jī)的數(shù)量和SaaS應(yīng)用實(shí)例的數(shù)量是不確定的，例如，SaaS提供商在初次租用虛擬機(jī)/服務(wù)器時(shí)，只知道虛擬機(jī)的類型，如EC2的小、中、大型虛擬機(jī)，但要租用的各類虛擬機(jī)的個(gè)數(shù)未知，而且要部署的SaaS實(shí)例的個(gè)數(shù)也需要根據(jù)租戶需求確定。

因此，對(duì)于給定的租戶需求，如何確定需要部署的SaaS應(yīng)用實(shí)例的數(shù)量和租用的虛擬機(jī)數(shù)量，同時(shí)建立租戶與SaaS應(yīng)用實(shí)例，以及SaaS應(yīng)用實(shí)例與虛擬機(jī)之間的放置關(guān)系，是本文所要解決的問(wèn)題。針對(duì)該問(wèn)題，本文通過(guò)分析多租戶SaaS應(yīng)用服務(wù)模式，提出了面向租戶響應(yīng)時(shí)間的資源消耗度量模型，采用基于虛擬機(jī)序列的遺傳算法來(lái)求解多租戶SaaS應(yīng)用優(yōu)化放置問(wèn)題，并通過(guò)實(shí)驗(yàn)分析了算法的可行性和有效性，最后通過(guò)一個(gè)應(yīng)用案例來(lái)描述放置方案的確定過(guò)程。

2 多租戶SaaS應(yīng)用放置模型

設(shè)某SaaS提供商有m個(gè)租戶，對(duì)外提供n種SaaS應(yīng)用（簡(jiǎn)稱應(yīng)用），每種應(yīng)用可以部署多個(gè)SaaS應(yīng)用實(shí)例（簡(jiǎn)稱應(yīng)用實(shí)例），每個(gè)應(yīng)用實(shí)例可以放置多個(gè)租戶，這些應(yīng)用實(shí)例需要部署在云基礎(chǔ)設(shè)施提供商所提供的虛擬機(jī)上。設(shè)云基礎(chǔ)設(shè)施提供商對(duì)外提供q種虛擬機(jī)，應(yīng)用實(shí)例的運(yùn)行需要消耗其所在虛擬機(jī)的資源，例如，CPU、內(nèi)存、網(wǎng)絡(luò)帶寬等，設(shè)p為資源種類的數(shù)量。每個(gè)租戶在使用應(yīng)用前需要與SaaS提供商簽訂SLA，SLA規(guī)定了應(yīng)用實(shí)例所要滿足的性能需求。應(yīng)用實(shí)例所消耗的資源一般與該應(yīng)用的類型、租戶數(shù)量、并發(fā)用戶數(shù)量以及租戶的性能需求等因素有關(guān)，對(duì)于性能需求，本文主要考慮服務(wù)響應(yīng)時(shí)間。

基于成本優(yōu)化的多租戶SaaS應(yīng)用放置問(wèn)題可描述為：對(duì)于給定的租戶集合TS＝｛T1，T2，…，Tm｝、應(yīng)用集合 AS＝｛A1，A2，…，An｝、租戶與應(yīng)用之間的租約關(guān)系集合TA?TS×AS、虛擬機(jī)類型集合VMTS＝｛VMT1，VMT2，…，VMTq｝，確定多租戶SaaS應(yīng)用放置方案，即確定SaaS提供商所要租用云基礎(chǔ)設(shè)施提供商的虛擬機(jī)數(shù)量xj、部署應(yīng)用實(shí)例的數(shù)量應(yīng)用實(shí)例與虛擬機(jī)之間的放置關(guān)系集合PRAV?AIS×VMS、租戶與應(yīng)用實(shí)例之間的放置關(guān)系集合PRTA?TS×AIS，其優(yōu)化目標(biāo)是租用虛擬機(jī)的成本最低，并且部署的應(yīng)用實(shí)例數(shù)量y盡可能少。

其中：xj表示虛擬機(jī)類型VMTj的實(shí)例數(shù)量；yj表示應(yīng)用Aj的實(shí)例數(shù)量；AIS表示部署的應(yīng)用實(shí)例集合；VMS表示租用的虛擬機(jī)集合，它們的數(shù)量分別為y和x；cj表示虛擬機(jī)類型VMTj的成本。

多租戶SaaS應(yīng)用放置的一個(gè)關(guān)鍵問(wèn)題是建立應(yīng)用的資源消耗模型。本文借鑒文獻(xiàn)［6－7］的思想，提出一個(gè)面向租戶服務(wù)響應(yīng)時(shí)間的資源消耗模型。

設(shè)Sk∈AIS表示被部署的第k（k＝1，2，…，y）個(gè)應(yīng)用實(shí)例，VMj∈VMS 表示被租用的第j（j＝1，2，…，x）個(gè)虛擬機(jī)，當(dāng)把Sk放置到VMj上時(shí)，Sk在VMj上消耗的第i（i＝1，2，…，p）種資源的數(shù)量其中：表示在沒有租戶和用戶時(shí)的資源消耗；表示隔離租戶的資源消耗，隔離租戶指當(dāng)多個(gè)租戶共享同一應(yīng)用實(shí)例時(shí)，為使不同租戶的業(yè)務(wù)和數(shù)據(jù)互不干擾所采取的技術(shù)手段表示處理用戶服務(wù)請(qǐng)求的資源消耗，ut表示租戶t∈Tk所包含的并發(fā)用戶數(shù)量，Tk表示放置在Sk上的租戶集合，rt表示租戶t∈Tk對(duì)Sk服務(wù)響應(yīng)時(shí)間的需求，fik（r，u）＝（w/r）·fik（w，u），fik（w，u）表示基準(zhǔn)響應(yīng)時(shí)間為w、并發(fā)用戶數(shù)為u時(shí)Sk對(duì)第i類資源的消耗，該函數(shù)可以根據(jù)測(cè)試和實(shí)際運(yùn)行數(shù)據(jù)來(lái)確定［6－7］。一般來(lái)說(shuō)，隔離租戶的資源消耗遠(yuǎn)小于處理用戶服務(wù)請(qǐng)求的資源消耗［6］。

設(shè)rij表示虛擬機(jī)VMj上的第i（i＝1，2，…，p）種資源的最大可用量，則有

式中：zj表示在VMj上放置的應(yīng)用實(shí)例的數(shù)量，αij表示VMj上第i種資源的最大利用率。

綜上所述，基于成本優(yōu)化的多租戶SaaS應(yīng)用優(yōu)化部署問(wèn)題可以表示為：

例如，某SaaS提供商有5個(gè)租戶，對(duì)外提供3種應(yīng)用，云基礎(chǔ)設(shè)施提供商為其提供3種虛擬機(jī)模板，圖1描述了租戶與應(yīng)用之間的租約關(guān)系。針對(duì)圖1所示的租約關(guān)系，圖2給出一種多租戶SaaS應(yīng)用放置方案：租用類型為VMT1的兩個(gè)虛擬機(jī)VM1和VM2，租用類型為VMT3的1個(gè)虛擬機(jī)VM3，即租用虛擬機(jī)的數(shù)量x＝3（x1＝2，x2＝0，x3＝1）；部署2個(gè)A1實(shí)例S1和S2，部署2個(gè)A2實(shí)例S3和S4，部署1個(gè)A3實(shí)例S5，即部署應(yīng)用實(shí)例的數(shù)量為y＝5（y1＝2，y2＝2，y3＝1）；應(yīng)用實(shí)例S1和S3放置在虛擬機(jī)VM1上，應(yīng)用實(shí)例S2和S4放置在虛擬機(jī)VM2上，應(yīng)用實(shí)例S5放置在虛擬機(jī)VM3上；應(yīng)用實(shí)例S1上放置1個(gè)租戶T1，應(yīng)用實(shí)例S2上放置1個(gè)租戶T2，應(yīng)用實(shí)例S3上放置2個(gè)租戶T2和T3，應(yīng)用實(shí)例S4上放置1個(gè)租戶T4，應(yīng)用實(shí)例S5上放置3個(gè)租戶T2、T4和T5，即應(yīng)用實(shí)例放置關(guān)系集PRAV＝｛（S1，VM1），（S3，VM1），（S2，VM2），（S4，VM2），（S5，VM3）｝，租戶放置關(guān)系集PRTA＝｛（T1，S1），（T2，S2），（T2，S3），（T2，S3），（T2，S5），（T3，S3），（T4，S4），（T4，S5），（T5，S5）｝。

基于成本優(yōu)化的多租戶SaaS應(yīng)用放置問(wèn)題可以劃分為2個(gè)子問(wèn)題：①確定應(yīng)用實(shí)例數(shù)量y（y≤｜TA｜）和虛擬機(jī)的數(shù)量x（x≥q）；②確定租戶放置關(guān)系PRTA和應(yīng)用實(shí)例放置關(guān)系PRAV。其中問(wèn)題②可以看作是將y個(gè)物體放到x個(gè)箱子的裝箱問(wèn)題，其中，每個(gè)物體代表一個(gè)應(yīng)用實(shí)例及其所包含的租戶，每個(gè)箱子代表一個(gè)虛擬機(jī)，該問(wèn)題的時(shí)間復(fù)雜度為xy，因此，多租戶SaaS應(yīng)用放置問(wèn)題屬于NP問(wèn)題。為提高問(wèn)題的求解效率和質(zhì)量，本文提出一個(gè)基于虛擬機(jī)序列的遺傳算法來(lái)求解近似最優(yōu)放置方案。

3 多租戶SaaS應(yīng)用優(yōu)化放置遺傳算法

3．1 初始應(yīng)用實(shí)例和虛擬機(jī)的確定

為了采用遺傳算法進(jìn)行問(wèn)題求解，首先需要確定放置方案的染色體編碼方式。因?yàn)樵诔跏疾渴痣A段，應(yīng)用實(shí)例的個(gè)數(shù)和虛擬機(jī)個(gè)數(shù)都未知，所以染色體的長(zhǎng)度和基因的取值都是不確定的，不能直接運(yùn)用遺傳算法進(jìn)行求解。為此，首先根據(jù)租約關(guān)系來(lái)確定初始的應(yīng)用實(shí)例數(shù)量和虛擬機(jī)的數(shù)量，具體計(jì)算方法如下：

（1）將每一個(gè)租約關(guān)系（Ti，Aj）∈TA 映射為一個(gè)租戶放置關(guān)系（Ti，Sk）∈PRTA，其中，Sk為Aj的一個(gè)實(shí)例，并且對(duì)于每個(gè)應(yīng)用的每個(gè)租戶都分配一個(gè)不同的實(shí)例，這樣可以確定初始的應(yīng)用實(shí)例集AIS，其數(shù)量為租約關(guān)系的數(shù)量y＝｜TA｜，且每個(gè)應(yīng)用實(shí)例只放置一個(gè)租戶。

（2）對(duì)每一種虛擬機(jī)VMTi（i＝1，2，…，q），計(jì)算所有應(yīng)用實(shí)例都放置到該類虛擬機(jī)時(shí)，需要的虛擬機(jī)實(shí)例個(gè)數(shù)的下限xi，則初始的虛擬機(jī)需求數(shù)量可以定義為這樣可以保證有足夠的虛擬機(jī)供選擇，本文的目標(biāo)就是從這些虛擬機(jī)中選擇能夠放置所有應(yīng)用實(shí)例及其所包含的租戶、并且滿足成本最低的一組虛擬機(jī)。

確定每一類虛擬機(jī)VMTi（i＝1，2，…，q）需求數(shù)量的算法如下：

算法1 確定每類虛擬機(jī)需求數(shù)量。

輸入：初始應(yīng)用實(shí)例集AIS、虛擬機(jī)類型VMTi；

輸出：VMTi的需求數(shù)量xi。

步驟1 令VMSi＝?為已部署的VMTi實(shí)例集（VMSi為有序集）。

步驟2 生成VMTi的一個(gè)實(shí)例加入VMSi中。

步驟3 從AIS中取出一個(gè)應(yīng)用實(shí)例Sk。

步驟4 依次檢查VMSi中的每個(gè)實(shí)例VMj，計(jì)算將Sk放置到VMj后，VMj的每一類資源需求量是否滿足其資源可用量約束。

（1）如果滿足，則將Sk從AIS中取出，并將其加入VMj所放置的應(yīng)用實(shí)例集AIS（VMj）中，轉(zhuǎn)步驟3；

（2）如果不滿足，則生成VMTi的一個(gè)實(shí)例，加入VMSi的第一個(gè)位置，轉(zhuǎn)步驟4；

（3）如果AIS中的所有應(yīng)用實(shí)例都已放置，即AIS＝?，則轉(zhuǎn)步驟5。

步驟5 輸出VMTi的需求數(shù)量xi＝｜VMSi｜。

算法1的最壞時(shí)間復(fù)雜度是O（｜AIS｜2）＝O（y2），即AIS中的每個(gè)應(yīng)用實(shí)例都放置在不同的虛擬機(jī)中，則確定所有類型的虛擬機(jī)數(shù)量的時(shí)間復(fù)雜度為O（q·y2）。

例如，針對(duì)圖1所示的租約關(guān)系，可以確定如圖3左側(cè)所示的8個(gè)初始租戶放置關(guān)系：（T1，S1），（T2，S2），（T2，S3），（T2，S6），（T3，S4），（T4，S5），（T4，S7），（T5，S8）。其中：A1包含S1和S2兩個(gè)實(shí)例，A2包含S3，S4和S5三個(gè)實(shí)例，A3包含S6，S7和S8三個(gè)實(shí)例，即y＝8（y1＝2，y2＝3，y3＝3）。根據(jù)算法1，可以確定初始虛擬機(jī)數(shù)量，為了簡(jiǎn)化問(wèn)題的復(fù)雜度，這里省略了計(jì)算過(guò)程，只給出計(jì)算結(jié)果，三類虛擬機(jī)的初始數(shù)量分別為4，3和4，即x＝11（x1＝4，x2＝3，x3＝4），它們的編號(hào)如圖3右側(cè)所示。

3．2 染色體編碼設(shè)計(jì)

確定了初始應(yīng)用實(shí)例數(shù)量和虛擬機(jī)需求數(shù)量后，就可以對(duì)放置方案進(jìn)行編碼。針對(duì)該類問(wèn)題，目前的編碼方式主要有基于應(yīng)用實(shí)例（看作物體）的編碼和基于虛擬機(jī)（看作箱子）的編碼［12］?；趹?yīng)用實(shí)例的編碼方式是每個(gè)基因代表一個(gè)初始應(yīng)用實(shí)例，基因的取值為初始虛擬機(jī)的編號(hào)，表示該應(yīng)用實(shí)例所放置的虛擬機(jī)［10］。基于虛擬機(jī)的編碼方式是每個(gè)基因表示一個(gè)初始虛擬機(jī)，基因的取值為一組應(yīng)用實(shí)例的集合，表示放置在該虛擬機(jī)上的所有應(yīng)用實(shí)例［13］。

通過(guò)實(shí)驗(yàn)發(fā)現(xiàn)，采用這兩種編碼方式的遺傳算法在求解多租戶SaaS應(yīng)用放置問(wèn)題時(shí)的優(yōu)化結(jié)果都不是很理想。目前，基于應(yīng)用實(shí)例編碼的染色體主要采用隨機(jī)生成的方法，即對(duì)每個(gè)基因隨機(jī)生成一個(gè)虛擬機(jī)編號(hào)［10］。對(duì)于多租戶應(yīng)用放置問(wèn)題來(lái)說(shuō)，如果初始的虛擬機(jī)數(shù)量非常大，則采用隨機(jī)生成方式會(huì)導(dǎo)致被選擇的虛擬機(jī)的數(shù)量非常多，算法的收斂速度會(huì)很慢，而且解的質(zhì)量也很低。另外，隨機(jī)生成還會(huì)產(chǎn)生許多不可行的染色體，對(duì)這些染色體進(jìn)行修復(fù)還會(huì)消耗一定的時(shí)間。雖然基于虛擬機(jī)的編碼在解的質(zhì)量上有所提高，但是由于編碼方式的復(fù)雜性，算法的時(shí)間復(fù)雜度相對(duì)較高［13］。

針對(duì)上述兩種編碼方式存在的問(wèn)題，本文提出一種基于虛擬機(jī)序列的編碼方式，在該編碼方式中，每條染色體是一個(gè)初始虛擬機(jī)的序列，表示一個(gè)初始應(yīng)用實(shí)例序列所放的順序。例如，針對(duì)圖3右側(cè)所示的初始虛擬機(jī)集合，可隨機(jī)生成一個(gè)初始虛擬機(jī)序列：1 2 5 9 3 4 6 7 8，表示初始應(yīng)用實(shí)例序列S1S2S3S4S5S6S7S8的放置順序，即按照該順序?qū)⑦@些應(yīng)用實(shí)例先放置到虛擬機(jī)VM1中，如果VM1放滿（表示該虛擬機(jī)當(dāng)前狀態(tài)下的可用資源不能再滿足應(yīng)用實(shí)例序列中沒有被放置的任何應(yīng)用實(shí)例的資源需求）則再往VM2中放置，如果VM2放滿則再往VM5中放置，直到所有應(yīng)用實(shí)例都被放完為止，此時(shí)可能還存在閑置的虛擬機(jī)，表示它們沒有被選擇。在此例中選擇了VM1，VM2，VM5和VM94個(gè)虛擬機(jī)，其中：S1和S2放置在VM1中，S3和S4放置在VM2中，S5，S6和S7放置在VM5中，S8放置在VM9中，其他虛擬機(jī)則沒有被選擇。對(duì)基于虛擬序列的編碼方式來(lái)說(shuō)，由于不同的虛擬機(jī)序列會(huì)產(chǎn)生不同的放置方案，虛擬機(jī)的序列是影響求解質(zhì)量的關(guān)鍵因素。

在應(yīng)用實(shí)例放置過(guò)程中，如果同一應(yīng)用的多個(gè)實(shí)例被放置到一個(gè)虛擬機(jī)上，則將這些應(yīng)用實(shí)例合并為一個(gè)應(yīng)用實(shí)例（同一應(yīng)用在一個(gè)虛擬機(jī)上只能部署一個(gè)實(shí)例），合并后的應(yīng)用實(shí)例的租戶為這些應(yīng)用實(shí)例租戶的并集，因此在計(jì)算應(yīng)用實(shí)例的資源消耗時(shí)，不是單獨(dú)計(jì)算每個(gè)應(yīng)用實(shí)例的資源消耗再求它們的和，而是先按照類別合并同類應(yīng)用實(shí)例，再計(jì)算合并后每類應(yīng)用實(shí)例的資源消耗，最后求所有應(yīng)用類別的資源消耗之和。因此，對(duì)基于虛擬序列的編碼方式來(lái)說(shuō)，應(yīng)用實(shí)例的放置順序也會(huì)影響放置方案的質(zhì)量，為了盡量將同類應(yīng)用實(shí)例放置到一個(gè)虛擬機(jī)上，以減少應(yīng)用實(shí)例的數(shù)量和資源消耗，可以按照同類應(yīng)用實(shí)例放在一起的規(guī)則來(lái)進(jìn)行放置。

例如，在圖3的示例中，首先放置A1的實(shí)例，然后放置A2的實(shí)例，最后放置A3的實(shí)例。由于S1和S2是同屬A1的兩個(gè)實(shí)例，當(dāng)它們被放置在同一個(gè)虛擬機(jī)VM5上時(shí)，應(yīng)把它們作為一個(gè)實(shí)例來(lái)處里，該實(shí)例上放置兩個(gè)租戶T1和T2。圖4描述了圖3所示的應(yīng)用實(shí)例序列和虛擬機(jī)序列（染色體編碼）所對(duì)應(yīng)的放置方案。

初始染色體的生成以及建立染色體與放置方案之間映射關(guān)系的算法如下：

算法2 染色體生成及放置方案映射算法。

輸入：初始應(yīng)用實(shí)例集AIS、初始虛擬機(jī)集合VMS；

輸出：染色體P、P所對(duì)應(yīng)的租戶放置關(guān)系PRTA和應(yīng)用實(shí)例放置關(guān)系PRAV。

步驟1 按照同類應(yīng)用實(shí)例放在一起的規(guī)則，生成AIS中應(yīng)用實(shí)例的一個(gè)序列Q＝i1，i2，…，iy（應(yīng)用實(shí)例放置順序），Q 為集合｛1，2，…，y｝的一個(gè)排列，y＝｜AIS｜。

步驟2 隨機(jī)生成VMS中虛擬機(jī)的一個(gè)序列P＝j(luò)1，j2，…，jx，P 為集合｛1，2，…，x｝的一個(gè)排列（代表一條染色體，對(duì)應(yīng)于虛擬機(jī)放置順序），x＝｜VMS｜。

步驟3 按順序取出Q中的每個(gè)應(yīng)用實(shí)例，首先檢查將該應(yīng)用實(shí)例放置到P中的第一個(gè)虛擬機(jī)上是否可行，如果不可行則再放置到P中的下一個(gè)虛擬機(jī)上，直至找到一個(gè)可以放置的虛擬機(jī)為止；然后建立該應(yīng)用實(shí)例與所放置的虛擬機(jī)之間的放置關(guān)系，以及其上租戶與應(yīng)用實(shí)例之間的放置關(guān)系，分別加入PRAV和PRTA中。

步驟4 重復(fù)步驟3，直到Q中所有的應(yīng)用實(shí)例都被放置為止。

算法2的時(shí)間復(fù)雜度為O（x（y），其中x和y分別為初始虛擬機(jī)數(shù)量和應(yīng)用實(shí)例數(shù)量。

3．3 遺傳操作與染色體修復(fù)

遺傳操作包括交叉操作和變異操作。針對(duì)基于虛擬機(jī)序列的編碼方式，采用循環(huán)交叉操作和移位變異操作。

循環(huán)交叉的核心思想是子串位置上的值必須與父母相同位置上的值相等［14］，其主要步驟如下：

步驟1 選擇父染色體P1的第一個(gè)基因作為子染色體C1的第一位，選擇父染色體P2的第一個(gè)基因作為子染色體C2的第一位。

步驟2 在P1中找出P2的第一個(gè)基因賦給C1的相對(duì)位置，并把P2中該位置的基因賦給C2的相對(duì)位置，重復(fù)此過(guò)程，直至P2上得到P1的第一個(gè)基因?yàn)橹?，稱為一個(gè)循環(huán)。

步驟3 對(duì)最前面的基因按P1、P2基因輪替原則重復(fù)以上步驟。

步驟4 重復(fù)以上步驟，直至所有的位都完成。

循環(huán)交叉操作的時(shí)間復(fù)雜度是O（x2），如圖5所示為循環(huán)交叉過(guò)程的示意圖。

移位變異是任意選擇一位基因，將其移動(dòng)到最前面，該操作的時(shí)間復(fù)雜度是O（x），圖6描述了移位變異過(guò)程的示意圖。

3．4 適應(yīng)函數(shù)

本文的優(yōu)化目標(biāo)是降低租用虛擬機(jī)的成本，如果兩個(gè)放置方案的成本相同，則部署應(yīng)用實(shí)例數(shù)量少的方案優(yōu)于應(yīng)用實(shí)例數(shù)量多的方案，這是因?yàn)檩^多的應(yīng)用實(shí)例將會(huì)帶來(lái)較高的維護(hù)成本。

設(shè)P為一個(gè)染色體（對(duì)應(yīng)放置方案），c和y分別為P的虛擬機(jī)成本和應(yīng)用實(shí)例的數(shù)量，將適應(yīng)函數(shù)定義為一個(gè)二元組F（P）＝（c，y），并定義適應(yīng)函數(shù)之間的等價(jià)關(guān)系“?”和超優(yōu)關(guān)系“?”。

設(shè)P1和P2為兩個(gè)染色體，c1和c2分別為P1和P2的虛擬機(jī)成本，y1和y2分別為P1和P2的應(yīng)用實(shí)例數(shù)量，即F（P1）＝（c1，y1），F(xiàn)（P2）＝（c2，y2）。如果c1＜c2，則F（P2）?F（P1）；如果c1＝c2且y1＜y2，則F（P2）?F（P1）；如果c1＝c2且y1＝y(tǒng)2，則F（P2）≡F（P1）。如果F（P2）?F（P1），則說(shuō)明P1的適應(yīng)度大于P2的適應(yīng)度，如果F（P2）≡F（P1），則說(shuō)明P1的適應(yīng)度等于P2的適應(yīng)度。本文的優(yōu)化目標(biāo)就是選擇適應(yīng)度大的放置方案。

3．5 遺傳算法

基于前述分析，給出多租戶SaaS應(yīng)用優(yōu)化放置遺傳算法。

算法3 多租戶SaaS應(yīng)用優(yōu)化放置遺傳算法。

輸入：初始應(yīng)用實(shí)例集AIS、初始租戶放置關(guān)系PRTA、虛擬機(jī)集合VMS、資源消耗度量模型、適應(yīng)函數(shù)、種群大小pop＿size、遺傳操作進(jìn)化代數(shù)gen、交叉操作概率pc，變異操作概率pm；

輸出：最優(yōu)放置方案P。

步驟1 設(shè)定種群大小pop＿size，遺傳操作進(jìn)化代數(shù)gen、交叉操作概率pc、變異操作概率pm等參數(shù)的取值。

步驟2 產(chǎn)生初始種群old＿pop，令g＝0表示當(dāng)前代數(shù)。

步驟3 將當(dāng)前種群old＿pop中個(gè)體適應(yīng)度最大的染色體放入新種群new＿pop。

步驟4 從種群old＿pop中采用輪盤賭算法任選兩條染色體進(jìn)行交叉、變異等遺傳操作，計(jì)算新染色體的個(gè)體適應(yīng)度并放入new＿pop中，令g＝g＋1。

步驟5 若g＜gen，則old＿pop＝new＿pop，轉(zhuǎn)步驟3；否則轉(zhuǎn)步驟6。

步驟6 從new＿pop中選擇適應(yīng)度值最高的染色體best＿chrom，根據(jù)該染色體計(jì)算得出最終的放置方案P。

在算法3中，步驟1的時(shí)間復(fù)雜度是O（1），可以忽略不計(jì)；步驟2初始化種群的時(shí)間復(fù)雜度是O（pop＿size·x·y）；步驟3和步驟6的時(shí)間復(fù)雜度都是O（gen）；步驟4～步驟5的時(shí)間復(fù)雜度是O（gen（x2）。因此，算法3的時(shí)間復(fù)雜度是O（pop＿size·x·y＋2（gen＋gen（x2）＝O（pop＿size·x·y＋gen（x2），加上確定初始虛擬機(jī)數(shù)量的時(shí)間復(fù)雜度O（q·y2），整個(gè)問(wèn)題求解的時(shí)間復(fù)雜度為O（q·y2＋pop＿size·x·y＋gen·x2）。

4 實(shí)驗(yàn)分析

本文所提算法已經(jīng)利用Java進(jìn)行了模擬仿真，實(shí)驗(yàn)環(huán)境為：CPU為雙核AMD Athlon 2．7GHz，內(nèi)存2GB，操作系統(tǒng)為Windows 7。

4．1 實(shí)驗(yàn)參數(shù)設(shè)定

實(shí)驗(yàn)參數(shù)設(shè)定主要是對(duì)模擬仿真實(shí)驗(yàn)中所涉及的各類參數(shù)進(jìn)行，包括虛擬機(jī)模擬參數(shù)、SaaS應(yīng)用模擬參數(shù)、租約模擬參數(shù)和算法實(shí)驗(yàn)參數(shù)。

（1）虛擬機(jī)參數(shù) 虛擬機(jī)類型參考亞馬遜EC2的虛擬機(jī)模板類型進(jìn)行參數(shù)設(shè)置，主要考慮CPU、內(nèi)存和存儲(chǔ)三種資源，不同虛擬機(jī)類型的資源數(shù)量不同，成本價(jià)格也不同，如表1所示。其中，CPU的單位為CU（compute unit），內(nèi)存的單位是 GiB（230字節(jié)），存儲(chǔ)的單位是G。小型的虛擬機(jī)CPU大小為1CU，內(nèi)存為1．7GiB，存儲(chǔ)為160G，價(jià)格為0．115＄/h?？梢愿鶕?jù)實(shí)驗(yàn)的需要?jiǎng)討B(tài)增加虛擬機(jī)類型及其模擬參數(shù)。設(shè)虛擬機(jī)的資源利用率αij＝0．95。

表1 EC2虛擬機(jī)資源約束及價(jià)格表

（2）應(yīng)用參數(shù) 應(yīng)用的模擬數(shù)據(jù)按如下方法設(shè)置：

1）應(yīng)用對(duì)資源的初始消耗r＊ik取值范圍為［1，5］×10－2，忽略了隔離租戶的資源消耗。

2）假設(shè)資源消耗函數(shù)fik（w，u）與用戶數(shù)u呈線性關(guān)系，fik（w，u）的斜率取值范圍為（0，10］，基準(zhǔn)響應(yīng)時(shí)間設(shè)置為w＝0．1s。

仿真實(shí)驗(yàn)中，模擬了12個(gè)應(yīng)用Ak（k＝1，2，…，12），每個(gè)應(yīng)用的主要模擬參數(shù)為資源消耗函數(shù)的斜率，其詳細(xì)參數(shù)設(shè)置如表2所示?？梢愿鶕?jù)實(shí)驗(yàn)的需要?jiǎng)討B(tài)增加應(yīng)用及其模擬參數(shù)。

表2 基準(zhǔn)響應(yīng)時(shí)間資源消耗函數(shù)斜率表

續(xù)表2

（3）租戶租約參數(shù) 一個(gè)租戶租約包含了租用的應(yīng)用類型、用戶數(shù)量、響應(yīng)時(shí)間、起止日期和價(jià)格等信息，本文主要關(guān)注應(yīng)用類型、用戶數(shù)量和響應(yīng)時(shí)間，響應(yīng)時(shí)間集合定義為R＝｛0．1，0．3，0．5｝s。

（4）算法實(shí)驗(yàn)參數(shù) 算法實(shí)驗(yàn)參數(shù)包括種群大小、進(jìn)化代數(shù)、交叉概率、變異概率、租約個(gè)數(shù)和用戶數(shù)，詳細(xì)設(shè)置如表3所示。

表3 算法實(shí)驗(yàn)參數(shù)設(shè)置

4．2 實(shí)驗(yàn)結(jié)果分析

通過(guò)實(shí)驗(yàn)仿真，分別實(shí)現(xiàn)了用基于應(yīng)用實(shí)例編碼的遺傳算法（Genetic Algorithm based on Application Instances Coding，AI－GA）［10］、基于虛擬機(jī)編碼的遺傳算法（Genetic Algorithm based on Virtual Machines Coding，VM－GA）［13］和基于虛擬機(jī)序列編碼的遺傳算法（Genetic Algorithm based on Virtual Machines Order Coding，VMO－GA）等算法求解多租SaaS應(yīng)用放置問(wèn)題，并從運(yùn)行時(shí)間、運(yùn)行結(jié)果、收斂速度等方面進(jìn)行了分析和對(duì)比。

（1）VMO－GA運(yùn)行結(jié)果分析

首先分析VMO－GA的平均收斂速度。圖7顯示了租約個(gè)數(shù)為200時(shí)算法運(yùn)行100次的平均收斂速度，在每次運(yùn)行中，進(jìn)化到400代左右算法開始收斂到一個(gè)相對(duì)最優(yōu)的結(jié)果。

接下來(lái)分析VMO－GA的進(jìn)化代數(shù)為400、租約個(gè)數(shù)仍然為200時(shí)，交叉概率和變異概率對(duì)算法結(jié)果的影響。圖8顯示了交叉概率與運(yùn)行結(jié)果之間的關(guān)系，從圖中可以看出，在交叉概率為0．8時(shí)運(yùn)行結(jié)果最好，最好時(shí)虛擬機(jī)成本為4．921 6，交叉概率小于或大于0．8時(shí)運(yùn)行得出的虛擬機(jī)成本都會(huì)變大。

圖9顯示了在交叉概率為0．8時(shí)變異概率與運(yùn)行結(jié)果之間的關(guān)系。當(dāng)變異率為0．05時(shí)運(yùn)行結(jié)果最好，虛擬機(jī)成本為4．916 4＄，變異率大于或小于0．05時(shí)運(yùn)行得出的虛擬機(jī)成本都會(huì)增大。

種群的大小對(duì)算法的運(yùn)行結(jié)果也有很大的影響，一般種群規(guī)模越大、運(yùn)行結(jié)果越好，但是所消耗的時(shí)間也越長(zhǎng)，因此通常采用一個(gè)折中的大小。圖10顯示了租約個(gè)數(shù)為200、進(jìn)化代數(shù)為400、交叉概率和變異概率分別為0．8和0．05時(shí)，VMO－GA的運(yùn)行結(jié)果與種群大小之間的關(guān)系。

（2）三種算法運(yùn)行結(jié)果比較

首先對(duì)三種算法的運(yùn)行時(shí)間進(jìn)行比較。以租約個(gè)數(shù)為500，進(jìn)化代數(shù)分別為50，100，150，200，250，300，350，400時(shí)的運(yùn)行時(shí)間為例，隨著進(jìn)化代數(shù)的增加，三種算法的運(yùn)行時(shí)間都呈線性增長(zhǎng)，在相同進(jìn)化代數(shù)下，VM－GA的運(yùn)行時(shí)間最長(zhǎng)，VMO－GA的

運(yùn)行時(shí)間居中，而AI－GA的運(yùn)行時(shí)間最少，如圖11所示。

進(jìn)一步比較三種算法的求解質(zhì)量。從運(yùn)行結(jié)果來(lái)看，VMO－GA和VM－GA在求解多租戶SaaS應(yīng)用放置問(wèn)題時(shí)的結(jié)果遠(yuǎn)遠(yuǎn)優(yōu)于AI－GA，如圖12所示。在進(jìn)化代數(shù)為500時(shí)，隨著進(jìn)化代數(shù)的逐漸增加，虛擬機(jī)成本逐漸收斂到一個(gè)最小的值，AI－GA，VMO－GA和 VM－GA 得 到 的 最 好 結(jié) 果 分 別 為64．148 5＄，10．887 5＄和10．929 1＄。通過(guò)實(shí)驗(yàn)結(jié)果可以看出，VMO－GA和VM－GA的收斂速度比AI－GA快，而在虛擬機(jī)成本上，VMO－GA得到的結(jié)果最好，VM－GA的結(jié)果次之，AI－GA的結(jié)果最差。

4．3 應(yīng)用案例

為了說(shuō)明多租戶SaaS應(yīng)用放置方案的確定過(guò)程，以圖3所描述的租戶放置關(guān)系為例，分析最終放置方案的選擇策略。在本例中，包含5個(gè)租戶、8個(gè)租約和3個(gè)應(yīng)用，根據(jù)初始應(yīng)用實(shí)例的計(jì)算規(guī)則（見第3．1節(jié)），每個(gè)租約映射為一個(gè)應(yīng)用實(shí)例，租約的參數(shù)設(shè)置如表4所示。

表4 租戶SLA需求設(shè)置

當(dāng)租戶確定了租約的響應(yīng)時(shí)間和用戶數(shù)后，就可以根據(jù)本文提出的資源消耗模型（見第2章），對(duì)各租約的資源消耗進(jìn)行計(jì)算。這里忽略了隔離租戶的資源消耗，應(yīng)用A1，A2和A3的基準(zhǔn)響應(yīng)時(shí)間資源消耗函數(shù)斜率如表2所示，虛擬機(jī)的資源利用率設(shè)置為0．95。表5給出每個(gè)租約所對(duì)應(yīng)的初始應(yīng)用實(shí)例放置在虛擬機(jī)上的資源需求，包括應(yīng)用實(shí)例在沒有租戶放置情況下的初始資源需求，以及在實(shí)際響應(yīng)時(shí)間下根據(jù)用戶數(shù)增長(zhǎng)的資源需求，這兩部分的和就是租約部署在虛擬機(jī)上資源需求。

表5 租約的資源需求

為簡(jiǎn)化問(wèn)題的復(fù)雜度，這里只考慮小、中、大三種虛擬機(jī)類型，其資源約束和價(jià)格如表1所示。首先根據(jù)算法1，可以確定三類虛擬機(jī)的初始數(shù)量，如圖3右側(cè)所示；然后根據(jù)算法2和算法3，選出一條最優(yōu)的染色體作為最終的放置策略，租戶、應(yīng)用實(shí)例和虛擬機(jī)之間的映射關(guān)系如圖 所示。根據(jù)放置策4略，確定需要中型虛擬機(jī)1個(gè)、大型虛擬機(jī)2個(gè)，因此，租用虛擬機(jī)的成本為1．15＄/h。對(duì)租戶和應(yīng)用實(shí)例進(jìn)行放置后，每個(gè)虛擬機(jī)的負(fù)載情況如表6所示。

表6 虛擬機(jī)負(fù)載情況

5 結(jié)束語(yǔ)

本文提出了基于成本優(yōu)化的多租戶 應(yīng)用SaaS放置模型和算法。研究了在多租戶SaaS應(yīng)用部署的初始階段，如何根據(jù)租戶的需求來(lái)確定應(yīng)用部署的SaaS應(yīng)用實(shí)例的數(shù)量以及租用的虛擬機(jī)數(shù)量，并建立租戶與SaaS應(yīng)用實(shí)例、SaaS應(yīng)用實(shí)例與虛擬機(jī)之間的放置關(guān)系，使租用的虛擬機(jī)成本最低，對(duì)于SaaS提供商減少初期資金投入具有重要意義。本文提出了面向租戶服務(wù)響應(yīng)時(shí)間的資源消耗度量模型，給出了基于成本優(yōu)化的多租戶SaaS應(yīng)用放置問(wèn)題的形式化描述；依據(jù)租約關(guān)系給出了計(jì)算初始的應(yīng)用實(shí)例數(shù)量和虛擬機(jī)數(shù)量的方法，并采用基于虛擬機(jī)序列編碼的遺傳算法來(lái)求解多租戶SaaS應(yīng)用放置問(wèn)題；通過(guò)實(shí)驗(yàn)分析了算法的可行性與有效性，并與基于應(yīng)用實(shí)例編碼的遺傳算法和基于虛擬機(jī)的遺傳算法進(jìn)行了比較，證明了該方法具有較高的求解質(zhì)量；最后通過(guò)一個(gè)實(shí)例說(shuō)明了多租戶SaaS應(yīng)用放置方案的確定過(guò)程。

由于目前還缺乏實(shí)際的實(shí)驗(yàn)環(huán)境，本文主要采用模擬實(shí)驗(yàn)的方法對(duì)所提算法進(jìn)行驗(yàn)證。下一步工作主要集中在兩方面：①基于已有的項(xiàng)目基礎(chǔ)，搭建實(shí)際的應(yīng)用環(huán)境，從而進(jìn)一步驗(yàn)證本文所提出方法的可行性；②研究將多租戶SaaS應(yīng)用部署到云環(huán)境后，如何進(jìn)行在線租戶優(yōu)化放置，以提高資源的利用率。

［1］ BOSS G，MALLADI P，QUAN D，et al．Cloud computing［EB/OL］．［2013－01－10］．http：//download．boulder．ibm．com/ibmdl/pub/software/dw/wes/hipods/Cloud＿computing＿wp＿final＿8Oct．

［2］ KANG S，KANG S，HUR S．A design of the conceptual architecture for a multitenant SaaS application platform［C］//Proceedings of the 2011 1st ACIS/JNU International Conference on Computers，Networks，Systems，and Industrial Engineering．Washington，D．C．，USA：IEEE Computer Society，2011：462－467．

［3］ WU L L，KUMAR S，BUYYA R．SLA－based rsource allocation for software as a service provider（SaaS）in cloud computing environments［C］//Proceedings of the IEEE/ACM International Symposium on Cluster，Cloud and Grid Computing．Washington，D．C．，USA：IEEE Computer Society，2011：195－204．

［4］ WU L L，GARG S K，BUYYA R．SLA－based admission control for a Software－as－a－service provider in cloud computing environments［J］．Journal of Computer and System Science，2012，78（5）：1280－1299．

［5］ Wikipedia．Amazon．com［EB/OL］．［2013－01－10］．http：//en．wikipedia．org/wiki/Amazon．com．

［6］ KWOK T，MOHINDRA A．Resource calculations with constraints，and placement of tenants and instances for multi－tenant SaaS applications［C］//Proceedings of International Conference on Service－Oriented Computing．Berlin，Germany：Springer－Verlag，2008：633－648．

［7］ ZHANG Y，WANG Z H，GAO B．An effective heuristic for on－line tenant placement problem in SaaS［C］//Proceedings of IEEE International Conference on Web Services．Washington，D．C．，USA：IEEE Computer Society，2010：425－432．

［8］ YU H Y，WANG D S．System resource allocation algorithm for multi－tenant SaaS application［C］//Proceedings of International Conference on Cloud and Service Computing．Washington，D．C．，USA：IEEE Computer Society，2011：207－211．

［9］ WANG Deshuai，ZHANG Yichuan，ZHANG Bin，et al．Load balancing strategy for multi－tenancy SaaS applications supporting service on demand［J］．Journal of Northeastern University：Natural Science，2011，32（3）：353－355（in Chinese）．［汪德帥，張一川，張 斌，等．支持多租約SaaS應(yīng)用按需服務(wù)的負(fù)載均衡策略 ［J］．東北大學(xué)學(xué)報(bào)：自然科學(xué)版，2011，32（3）：353－355．］

［10］ IZZAH Z，YUSOH M，TANG M．A penalty－based genetic algorithm for the composite SaaS placement problem in the cloud［C］//Proceedings of the IEEE Congress on Evolutionary Computation．Washington，D．C．，USA：IEEE Computer Society，2010：1－8．

［11］ YANG E F，ZHANG Y，WU L，et al．A hybrid approach to placement of tenants for service－based multi－tenant SaaS application［C］//Proceeding of IEEE Asia－Pacific Services Com－puting Conference．Washington，D．C．，USA：IEEE Computer Society，2011：124－130．

［12］ ZHANG Dabin，LIU Guiqin，WANG Jing，et al．Genetic algorithm based on group coding for bin－packing problem［J］．Computer Engineering and Design，2008，29（12）：3154－3156（in Chinese）．［張大斌，劉桂琴，王 婧，等．基于群體編碼方式的遺傳算法求解裝箱問(wèn)題［J］．計(jì)算機(jī)工程與設(shè)計(jì)，2008，29（12）：3154－3156．］

［13］ FALKENAUER E，DELCHAMBRE A．A genetic algorithm for bin packing and line balancing［C］//Proceedings of the IEEE International Conference on Robotics and Automation．Washington，D．C．，USA：IEEE Computer Society，1992：1186－1192．

［14］ WANG Dingwei，WANG Junwei，WANG Hongfeng，et al．Intelligent optimization methods［M］．Beijing：Higher Education Press，2007（in Chinese）．［汪定偉，王俊偉，王洪峰，等．智能優(yōu)化方法［M］．北京：高等教育出版社，2007．］