陳 平 李 攀 劉秋菊

1(濟(jì)源職業(yè)技術(shù)學(xué)院 河南 濟(jì)源 459000) 2(鄭州工程技術(shù)學(xué)院 河南 鄭州 450044)

0 引 言

云數(shù)據(jù)中心利用虛擬化技術(shù)可以在物理服務(wù)器上部署多個(gè)不同性能的虛擬機(jī)，以提高整體的資源利用率[1]。虛擬化的一個(gè)主要優(yōu)勢(shì)是在數(shù)據(jù)中心內(nèi)可以進(jìn)行動(dòng)態(tài)的虛擬機(jī)合并來降低能耗，通過將虛擬機(jī)合并到更少數(shù)量的物理主機(jī)上，并將閑置主機(jī)轉(zhuǎn)換為睡眠模式以提升能效。動(dòng)態(tài)的虛擬機(jī)合并實(shí)現(xiàn)了運(yùn)行時(shí)虛擬機(jī)在不同主機(jī)間的在線遷移[2]，尤其在主機(jī)處于較低負(fù)載或超載狀態(tài)下時(shí)，遷移將具有諸多好處。因此，通過遷移操作會(huì)使得數(shù)據(jù)中心內(nèi)的資源管理更加靈活。然而，虛擬機(jī)在線遷移對(duì)于運(yùn)行在虛擬機(jī)上的應(yīng)用任務(wù)的性能具有負(fù)面影響[3]。由于在云服務(wù)提供者與其用戶間提供相應(yīng)的服務(wù)質(zhì)量是至關(guān)重要的，所以動(dòng)態(tài)虛擬機(jī)合并應(yīng)該著重考慮優(yōu)化虛擬機(jī)遷移次數(shù)。此時(shí)的服務(wù)質(zhì)量需求通常以服務(wù)等級(jí)協(xié)議SLA來描述，根據(jù)吞吐量或服務(wù)的響應(yīng)時(shí)間上的性能表現(xiàn)來定義。

動(dòng)態(tài)虛擬機(jī)合并可以形式化為裝箱模型，是NP問題。由于裝箱問題僅能在給定物品下最小化箱子數(shù)量，直接應(yīng)用于虛擬機(jī)合并中擁有一定局限性[4]。很多算法也以裝箱思路求解過虛擬機(jī)合并問題。然而，這會(huì)產(chǎn)生過多的非必要虛擬機(jī)遷移，增加SLA違例風(fēng)險(xiǎn)。比較已有工作最小化主機(jī)利用數(shù)量，本文將設(shè)計(jì)一種啟發(fā)式算法同步最小化虛擬機(jī)遷移次數(shù)和SLA違例。本文算法進(jìn)行動(dòng)態(tài)虛擬機(jī)合并主要由兩個(gè)階段組成：1) 嘗試將負(fù)載最低主機(jī)上的所有虛擬機(jī)遷移至負(fù)載最大主機(jī)上；2) 從當(dāng)前超載或預(yù)測(cè)在近期會(huì)變?yōu)槌d的主機(jī)上遷移出部分虛擬機(jī)以防止可能的SLA違例。同時(shí)，本文算法可以根據(jù)當(dāng)前和未來的資源請(qǐng)求將遷移虛擬機(jī)分配至合適主機(jī)上。為了預(yù)測(cè)負(fù)載，本文設(shè)計(jì)使用了線性回歸LR和K最近鄰回歸KNNR模型預(yù)測(cè)方法，對(duì)未來資源利用率進(jìn)行預(yù)測(cè)。為了訓(xùn)練和測(cè)試預(yù)測(cè)模型，本文通過運(yùn)行云環(huán)境中的多種現(xiàn)實(shí)負(fù)載生成歷史數(shù)據(jù)集，并通過實(shí)驗(yàn)驗(yàn)證了本文算法的有效性。

1 相關(guān)工作

相關(guān)研究中，文獻(xiàn)[5]提出了動(dòng)態(tài)的服務(wù)遷移機(jī)制，在給定負(fù)載狀態(tài)和降低SLA違例的條件下可以降低物理能力的使用量，算法利用了裝箱啟發(fā)式方法和時(shí)序預(yù)測(cè)技術(shù)最小化主機(jī)利用量，但并沒有考慮新部署中的虛擬機(jī)遷移次數(shù)。文獻(xiàn)[6]利用蟻群系統(tǒng)尋找最優(yōu)解，同步考慮了休眠主機(jī)量和遷移次數(shù)。文獻(xiàn)[7]為了避免性能下降，設(shè)置門限值防止主機(jī)CPU達(dá)到100%占用率，將CPU占用率限定在門限值之內(nèi)。然而，靜態(tài)的門限值設(shè)置無法處理動(dòng)態(tài)的云負(fù)載環(huán)境，此時(shí)主機(jī)上運(yùn)行的負(fù)載類型是多樣的。因此，門限值應(yīng)該針對(duì)不同的負(fù)載類型作出相應(yīng)改變，并允許有效的任務(wù)合并。文獻(xiàn)[8]根據(jù)歷史數(shù)據(jù)的靜態(tài)分析設(shè)置了自適應(yīng)的上下限值，而文獻(xiàn)[9]則根據(jù)數(shù)據(jù)中心內(nèi)不同的應(yīng)用類型，以最大化資源利用率和負(fù)載均衡為目標(biāo)，提出了新的虛擬機(jī)部署算法。

虛擬機(jī)合并問題可以形式化為裝箱問題，裝箱問題即是將若干物品裝入有限數(shù)量的箱子內(nèi)，并最小化箱子數(shù)量。每臺(tái)虛擬機(jī)可視為一個(gè)物品，每臺(tái)主機(jī)即為一個(gè)箱子。由于裝箱問題的NP難屬性，有效求解方法為啟發(fā)式方法。如：首次適應(yīng)算法FF將物品放入可容納該物品的第一個(gè)箱子中；最佳適應(yīng)算法BF將物品放入空間最合適的箱子中。此外，F(xiàn)F和BF算法可進(jìn)一步改進(jìn)為降序首次適應(yīng)算法FFD和降序最佳適應(yīng)算法BFD。然而，經(jīng)典的裝箱方法并不能直接應(yīng)用于虛擬機(jī)合并問題。原因在于：1) 虛擬機(jī)和主機(jī)擁有多個(gè)維度資源，如CPU、內(nèi)存和網(wǎng)絡(luò)帶寬。若考慮CPU和內(nèi)存資源的約束，虛擬機(jī)合并問題就是典型的二維裝箱問題。2) 虛擬機(jī)合并問題可修正為可變箱子(主機(jī))大小的裝箱問題，不同于經(jīng)典的等同能力箱子的裝箱問題。3) 經(jīng)典裝箱方法僅最小化箱子數(shù)量，即單目標(biāo)優(yōu)化。而本文考慮的目標(biāo)包括虛擬機(jī)遷移次數(shù)和SLA違例問題。文獻(xiàn)[10]設(shè)計(jì)了BFD的改進(jìn)算法，可以節(jié)省部分能耗。文獻(xiàn)[11]利用FFD的改進(jìn)算法在功耗和遷移代價(jià)間取得均衡。文獻(xiàn)[12]利用改進(jìn)的FF和BF算法在未考慮性能下降的情況下最小化主機(jī)利用量。然而，以上算法多是單一目標(biāo)的優(yōu)化，沒有在能效和服務(wù)性能上作出綜合的考量。

本文提出一種融合了負(fù)載預(yù)測(cè)機(jī)制的虛擬機(jī)合并算法UP-VMC，與已有研究相比具有以下幾點(diǎn)優(yōu)勢(shì)：1) 算法可以得到能效和SLA違例間的最優(yōu)均衡解，實(shí)現(xiàn)動(dòng)態(tài)的虛擬機(jī)合并；2) 為了降低虛擬機(jī)遷移量，算法可以根據(jù)當(dāng)前和未來的資源需求分配遷移虛擬機(jī)至目標(biāo)主機(jī)；3) 為了降低SLA違例，算法選擇從當(dāng)前超載主機(jī)或最近未來會(huì)變?yōu)槌d的主機(jī)上遷移部分虛擬機(jī)，避免無用虛擬機(jī)遷移；4) 算法利用線性回歸與K最近鄰回歸方法對(duì)負(fù)載進(jìn)行預(yù)測(cè)，可以基于歷史數(shù)據(jù)預(yù)測(cè)主機(jī)和虛擬機(jī)的CPU占用率，實(shí)現(xiàn)了前瞻性的虛擬機(jī)合并。

2 系統(tǒng)模型

假設(shè)一個(gè)云數(shù)據(jù)中心由m臺(tái)異構(gòu)物理主機(jī)構(gòu)成，表示為P={p1,p2,…,pm}。每臺(tái)主機(jī)擁有D類資源，如CPU、內(nèi)存、網(wǎng)絡(luò)帶寬和存儲(chǔ)能力。多個(gè)虛擬機(jī)可以通過虛擬機(jī)監(jiān)視器部署在一臺(tái)主機(jī)上。初始情況下，虛擬機(jī)通過傳統(tǒng)裝箱方法降序最佳適應(yīng)算法進(jìn)行部署。在任意給定的時(shí)間，用戶可發(fā)送虛擬機(jī)請(qǐng)求，表示為V={v1,v2,…,vn}，需要部署至主機(jī)上。由于虛擬機(jī)和主機(jī)請(qǐng)求的資源占用隨著時(shí)間發(fā)生變化，初始部署時(shí)，需要利用周期性的虛擬機(jī)合并算法對(duì)虛擬機(jī)部署進(jìn)行優(yōu)化。本文提出的UP-VMC算法即可根據(jù)負(fù)載變化對(duì)虛擬機(jī)部署作出優(yōu)化。圖1是虛擬機(jī)合并的系統(tǒng)模型，由兩類代理構(gòu)成：1) 在主機(jī)上全分布的本地代理(Local Agents,LAs)；2) 在主節(jié)點(diǎn)上的全局代理(Global Agent,GA)。執(zhí)行過程如下：

圖1 系統(tǒng)模型

1) 每個(gè)LA周期性監(jiān)測(cè)主機(jī)上所有虛擬機(jī)的當(dāng)前資源利用率，然后利用回歸預(yù)測(cè)模型預(yù)測(cè)虛擬機(jī)的未來資源利用率。本文引入線性回歸和K最近鄰回歸進(jìn)行預(yù)測(cè)。

2) GA收集本地代理信息，獲得虛擬機(jī)的當(dāng)前和未來資源利用率情況。

3) 利用UP-VMC算法，GA生成全局最優(yōu)遷移計(jì)劃，并將其發(fā)送虛擬機(jī)監(jiān)視器執(zhí)行虛擬機(jī)遷移。該指令決定了源主機(jī)上的哪些虛擬機(jī)需要遷移至對(duì)應(yīng)目標(biāo)主機(jī)。

4) 接收GA指令后，虛擬機(jī)監(jiān)視器VMM執(zhí)行實(shí)際虛擬機(jī)遷移。

每臺(tái)主機(jī)p擁有d維資源能力向量，Cp={Cp,1,Cp,2,…,Cp,d}，Cp,d表示主機(jī)p的第d維資源能力。每個(gè)維度對(duì)應(yīng)一類物理資源，如CPU、內(nèi)存、網(wǎng)絡(luò)帶寬和磁盤存儲(chǔ)。根據(jù)現(xiàn)實(shí)負(fù)載的資源維度需求，設(shè)置|D|=2，考慮二維虛擬機(jī)合并問題，并將CPU和內(nèi)存考慮為主要資源類型。主機(jī)p已使用的能力向量表示為Up={Up,1,Up,2,…,Up,d}，其中，Up,d表示主機(jī)p的資源d的已使用能力。若三個(gè)虛擬機(jī)部署在同一臺(tái)主機(jī)上，則該主機(jī)已使用的CPU能力為三個(gè)虛擬機(jī)的CPU占用之和。虛擬機(jī)v的總能力向量表示為Cv={Cv,1,Cv,2,…,Cv,d}，其中，Cv,d表示虛擬機(jī)v在d維資源上的能力。Uv={Uv,1,Uv,2,…,Uv,d}表示虛擬機(jī)v已使用的資源能力。由于動(dòng)態(tài)負(fù)載條件下虛擬機(jī)的資源利用會(huì)隨時(shí)間發(fā)生變化，虛擬機(jī)部署需要通過UP-VMC算法進(jìn)行周期性優(yōu)化。表1給出相關(guān)符號(hào)說明。

表1 參數(shù)說明

3 算法的詳細(xì)設(shè)計(jì)

UP-VMC算法的執(zhí)行過程如算法1所示。UP-VMC算法通過兩個(gè)階段進(jìn)行虛擬機(jī)合并優(yōu)化。

算法1UP-VMC算法

1. setM1=NULL

2. forpso∈[Pover,Pover′] do

3. sortVMsonpsoandVmin ascending order ofUv,mem

4. forv∈Vmdo

5. if (pso∈Pover)‖(pso∈Pover′) then

6. forpde∈P-[Pover,Pover′] do

7. if (Upde+Uv≤T×Cpde) and (PUpde+PUv≤T×Cpde)

8.M1←M1∪{(pso,v,pde)}

9. updateUpsoandUpde

10. break

11. if (pso∈Pover)‖(pso∈Pover′) then

12. switch on the dormantPMp

13. else break

14. setM2=NULL

15. sortPactivein descending ofLoadp

16. fori=|Pactive| to 1 do

17.pso←Pactive[i]

18.Vm←sortVMsonpso,Vpin descending order ofLoadv

19. forv∈Vmdo

20.success←false

21. forpde∈Pactive-psodo

22. if (Upde+Uv≤T×Cpde) and (PUpde+PUv≤T×Cpde)

23.M2←M2∪{(pso,v,pde)

24. updateUpsoandUpde

25.success←true

26. break

27. ifsuccess=false then

28.M2←null

29. recoverUpsoandUpde

30. else switchpsoto the sleep mode

31.M←M1∪M2

32. returnM

第一階段。UP-VMC算法該階段的目標(biāo)是從超載和預(yù)測(cè)超載主機(jī)遷移虛擬機(jī)以最小化SLA違例。若至少有一類資源(CPU或內(nèi)存)超過總能力，則主機(jī)被視為超載主機(jī)集合Pover中的成員。若至少一個(gè)預(yù)測(cè)利用率高于可用資源能力，則該主機(jī)被視為超載主機(jī)集合Pover′中的成員。UP-VMC算法首先從Pover中遷移部分虛擬機(jī)，直到?jīng)]有超載主機(jī)為止。然后，從Pover′中遷移虛擬機(jī)以確保在短期內(nèi)不會(huì)出現(xiàn)SLA違例。

為了預(yù)測(cè)資源利用率，利用兩種回歸模型進(jìn)行預(yù)測(cè)：線性回歸模型LR和K最近鄰回歸模型KNNR。預(yù)測(cè)模型可以估算主機(jī)和虛擬機(jī)的CPU和內(nèi)存的資源利用。UP-VMC算法在動(dòng)態(tài)的負(fù)載條件下主要關(guān)注短期的負(fù)載預(yù)測(cè)。LR主機(jī)利用歷史資源利用率數(shù)據(jù)并將其估算為線性函數(shù)，該函數(shù)給出了當(dāng)前與未來資源利用率的關(guān)系，表示為：

PUpde=α+βUpde

(1)

式中：PUpde和Upde分別表示主機(jī)p的預(yù)測(cè)和當(dāng)前已使用能力向量；α和β表示回歸因子，分別用于描述Y軸截距和線性斜率。估算回歸因子的常用方法是最小方差法，該方法估算最優(yōu)的直線擬合為觀察輸出值與預(yù)測(cè)輸出值間的距離最小化。因此，回歸因子可通過以下公式進(jìn)行估算：

(2)

α=y′-βx′

(3)

式中：x′代表x1,x2,…,xn的均值；y′代表y1,y2,…,yn的均值。

利用類似的方法，虛擬機(jī)資源利用也可以通過線性函數(shù)預(yù)測(cè)，表示為當(dāng)前已使用的能力向量Uv和預(yù)測(cè)使用的能力向量PUv之間的線性關(guān)系式，為：

PUv=α+βUv

(4)

KNNR利用數(shù)據(jù)集的局部均值對(duì)資源利用做出預(yù)測(cè)。局部數(shù)據(jù)量定義為與新的樣本最近的k個(gè)樣本。最優(yōu)k值(鄰居數(shù)量)可以通過留一交叉驗(yàn)證法確定，取值范圍為樣本數(shù)以內(nèi)。留一交叉驗(yàn)證法通過每個(gè)可能k值的平方冗余之和估算預(yù)測(cè)準(zhǔn)確性；然后，選擇冗余最小的最優(yōu)k值作為K最近鄰回歸的k值。

UP-VMC從超載或預(yù)測(cè)超載主機(jī)遷移虛擬機(jī)時(shí)，將根據(jù)以下三種策略進(jìn)行遷移虛擬機(jī)選擇：最小遷移時(shí)間策略MMT、最大負(fù)載策略MaxL和最小負(fù)載策略MinL。

第二階段。該階段算法將盡可能消除最低載主機(jī)，降低活躍主機(jī)數(shù)量以節(jié)省能耗。算法的目標(biāo)是遷移最低載主機(jī)上所有虛擬機(jī)至最高載主機(jī)并釋放低載主機(jī)節(jié)省能耗。UP-VMC算法可確保部署遷移虛擬機(jī)后目標(biāo)主機(jī)在短期內(nèi)不會(huì)變?yōu)槌d主機(jī)。選擇目標(biāo)主機(jī)時(shí)，算法將依次負(fù)載從高到低順序選擇，直到虛擬機(jī)完成遷移。若低載主機(jī)上存在至少一個(gè)虛擬機(jī)無法遷移，則所有均不遷移。是否能夠?qū)崿F(xiàn)虛擬機(jī)遷移，需要考慮不同維度資源的約束。定義主機(jī)p的負(fù)載為每個(gè)資源維度d的資源利用率Rp,d之和，表示為：

(5)

式中：Rp,d表示資源利用Up,d與資源能力Cp,d之比。Rp,d計(jì)算為：

Rp,d=Up,d/Cp,d

(6)

為了決定低載主機(jī)上遷移的虛擬機(jī)，算法按虛擬機(jī)負(fù)載對(duì)其作降序排列，因此，第一個(gè)選擇遷移的虛擬機(jī)即為負(fù)載最高的虛擬機(jī)。虛擬機(jī)v的負(fù)載定義為：

(7)

式中：Rv,d表示虛擬機(jī)v在d維資源上的請(qǐng)求Uv,d與虛擬機(jī)的d維資源總能耗Cv,d之比。Rv,d計(jì)算如下：

Rv,d=Uv,d/Cv,d

(8)

為了尋找部署遷移虛擬機(jī)的目標(biāo)主機(jī)，引入兩種約束避免SLA違例和無用遷移。第一個(gè)約束：若主機(jī)當(dāng)前擁有足夠資源容納遷移虛擬機(jī)，則允許虛擬機(jī)v遷移至目標(biāo)主機(jī)pde。當(dāng)主機(jī)利用率接近100%時(shí)，即會(huì)產(chǎn)生SLA違例風(fēng)險(xiǎn)。因此，需要設(shè)置閾值T限制虛擬機(jī)的資源請(qǐng)求量。因此，第一個(gè)能力約束為：

Upde+Uv≤T×Cpde

(9)

式中：Cpde表示目標(biāo)主機(jī)pde的總能力向量；Upde表示pde的已使用能力向量；Uv表示虛擬機(jī)v已使用能力向量。

第二個(gè)約束確保在虛擬機(jī)遷移后目標(biāo)主機(jī)不會(huì)變?yōu)槎唐诔d主機(jī)，因此，此時(shí)UP-VMC算法同時(shí)考慮了主機(jī)pde和虛擬機(jī)v的未來資源能力需求。第二個(gè)預(yù)測(cè)能力約束為：

PUpde+PUv≤T×Cpde

(10)

式中：PUpde表示主機(jī)pde的預(yù)測(cè)使用能力向量；PUv表示虛擬機(jī)v的預(yù)測(cè)使用能力向量。

UP-VMC算法的目標(biāo)是通過實(shí)現(xiàn)前文所述兩個(gè)步驟得到一個(gè)最終的虛擬機(jī)遷移計(jì)劃。在第一階段中，即步驟2-步驟13，步驟2遍歷超載主機(jī)集合Pover和預(yù)測(cè)超載主機(jī)集合Pover′，其目標(biāo)是從這兩個(gè)集合中遷移出虛擬機(jī)以避免更多的SLA違例。為了實(shí)現(xiàn)這一目標(biāo)，算法首先選擇遷移時(shí)間最小的虛擬機(jī)進(jìn)行遷移。由于主機(jī)間的網(wǎng)絡(luò)帶寬為1 Gbit/s，根據(jù)虛擬機(jī)請(qǐng)求的內(nèi)存利用即可計(jì)算出遷移時(shí)間。因此，算法以請(qǐng)求內(nèi)存利用的降序?qū)λ刑摂M機(jī)進(jìn)行排序，然后開始虛擬機(jī)遷移，即步驟3-步驟4。若源主機(jī)仍為超載或預(yù)測(cè)超載集合中的成員，則再次利用虛擬機(jī)遷移選擇策略從該主機(jī)選擇遷移虛擬機(jī)，即步驟5，重復(fù)該過程直到該主機(jī)在當(dāng)前和未來均不是超載主機(jī)為止。然后，算法根據(jù)提出的兩個(gè)約束選擇重分配虛擬機(jī)v的目標(biāo)主機(jī)(步驟6-步驟7)。最后，新的虛擬機(jī)部署被添加為遷移計(jì)劃M1中的成員，即步驟8。遷移計(jì)劃設(shè)置為三元組(pso;v;pde)，其中：pso為源主機(jī)；v為遷移虛擬機(jī)；pde為目標(biāo)主機(jī)。若活躍主機(jī)沒有足夠資源分配虛擬機(jī)v，則開啟一臺(tái)休眠主機(jī)p，即步驟11-步驟13。

第二個(gè)階段中，即步驟14-步驟30，算法根據(jù)負(fù)載的降序?qū)钴S主機(jī)進(jìn)行排序。UP-VMC從列表Pactive中的最后一個(gè)主機(jī)開始，將負(fù)載最低的主機(jī)考慮為源主機(jī)pso，即步驟16-步驟17。然后，算法嘗試從主機(jī)pso上遷移所有虛擬機(jī)以釋放pso。為了從pso上選擇優(yōu)先遷移的虛擬機(jī)，算法對(duì)pso上的所有虛擬機(jī)按其負(fù)載進(jìn)行降序排列，即步驟18。為了找到分配遷移虛擬機(jī)的目標(biāo)主機(jī)pde，UP-VMC算法從列表Pactive中第一個(gè)主機(jī)(負(fù)載最高主機(jī))開始掃描，即步驟19。若無法部署，繼續(xù)選擇第二臺(tái)主機(jī)嘗試。算法選擇的目標(biāo)主機(jī)pde需要在當(dāng)前和短期未來均擁有容納遷移虛擬機(jī)的資源，即步驟20。最后，新的虛擬機(jī)部署添加為遷移計(jì)劃M2中的成員，即步驟23。更新源主機(jī)和目標(biāo)主機(jī)的能力以反映遷移后的改變，即步驟24。參數(shù)success用于檢測(cè)從源主機(jī)上是否所有虛擬機(jī)均被遷移，若有至少一個(gè)虛擬機(jī)未遷移，則所有虛擬機(jī)均不作遷移。因此，若success為false，則算法需要移除遷移計(jì)劃中的所有三元組并恢復(fù)源主機(jī)和目標(biāo)主機(jī)的資源能力，即步驟27-步驟29。否則，所有虛擬機(jī)遷移后，源主機(jī)被轉(zhuǎn)換為休眠模式，即步驟30。UP-VMC算法的輸出是遷移計(jì)劃M，包括兩個(gè)階段中的全部遷移三元組，即步驟31-步驟32。

4 實(shí)例分析

以一個(gè)實(shí)例說明UP-VMC算法的實(shí)現(xiàn)過程?，F(xiàn)在三臺(tái)異主機(jī)P={p1,p2,p3}，五臺(tái)虛擬機(jī)部署請(qǐng)求，V={v1,v2,v3,v4,v5}。主機(jī)的能力向量分別是為：Cp1={12,18}，Cp2={6,8}，Cp3={8,12}，表明主機(jī)p1的CPU能力和內(nèi)存分別為12 GHz和18 GB。虛擬機(jī)的能力向量分別為：Cv1={1,1}，Cv2={1,4}，Cv3={2,2}，Cv4={2,2}，Cv5={3,4}。Cv1={1,1}表明虛擬機(jī)1的CPU和內(nèi)存消耗分別為1 GHz和1 GB。假設(shè)CPU閾值設(shè)置為T=0.8。

UP-VMC算法的第一次迭代中，虛擬機(jī)請(qǐng)求的資源占用為：Uv1={0.5,0.7}，Uv2={0.5,2}，Uv3={0.5,0.5}，Uv4={0.5,0.5}，Uv5={0.5,0.5}。Uv1={0.5,0.7}表明虛擬機(jī)v1請(qǐng)求1 GHz中的0.5 GHz的CPU能力和1 GB內(nèi)存的0.7 GB。基于初始的虛擬機(jī)部署(圖2(a))，主機(jī)的已使用能力向量為：Up1={1,2.7}，Up2={0.5,0.5}，Up3={1,1}。如：{0.5,0.7}為虛擬機(jī)v1請(qǐng)求的CPU和內(nèi)存元組，{0.5,2}為虛擬機(jī)v2請(qǐng)求的能力。那么，主機(jī)p1容納這兩個(gè)虛擬機(jī)后，其占用則為{1,2.7}，即請(qǐng)求向量之和。算法首先利用式(3)計(jì)算每個(gè)主機(jī)的負(fù)載為：

(a) 第一次迭代：v3從p2遷移至p1

(b) 第二次迭代：v4從p3遷移至p1，然后v5遷移

(c) 第三次迭代：不發(fā)生遷移圖2 實(shí)例說明

類似地，p2和p3的負(fù)載分別為：Loadp2≈0.14，Loadp3≈0.20。在第一步，UP-VMC算法沒有找到任一超載和預(yù)測(cè)超載主機(jī)，由于所有主機(jī)的當(dāng)前和預(yù)測(cè)利用率均未超過主機(jī)能力。在第二步，算法根據(jù)當(dāng)前負(fù)載得到主機(jī)p2是最低負(fù)載主機(jī)，為了釋放p2，需要遷移虛擬機(jī)v3。

為了尋找部署v3的目標(biāo)主機(jī)，UP-VMC算法從負(fù)載最大主機(jī)p1開始掃描，并確定式(9)和式(10)是否成立。

Up1+Uv3≤T×Cp1={1，2.7}+{0.5,0.5}≤

0.8×{12,18}={1.5,3.2}≤{9.6,14.4}

PUp1+PUv3≤T×Cp1={1.2，2.5}+{0.8,1.3}≤

0.8×{12,18}={2,3.8}≤{9.6,14.4}

由于主機(jī)p1在所有資源維度上均擁有足夠的能力部署虛擬機(jī)v3，式(9)條件滿足。同時(shí)，如果主機(jī)p1的預(yù)測(cè)能力向量為{1.2,2.5}，虛擬機(jī)v3的預(yù)測(cè)需求能力向量為{0.8,1.3}，則式(10)條件滿足。

由于兩個(gè)條件均滿足，虛擬機(jī)v3可從主機(jī)p2遷移至p1。由于p2未部署任一虛擬機(jī)，p2可轉(zhuǎn)換為休眠狀態(tài)節(jié)省能耗 。

在第二次迭代中，算法未執(zhí)行第一步，由于活躍主機(jī)p1和p3不是超載或預(yù)測(cè)超載主機(jī)。在第二步中，假設(shè)虛擬機(jī)的當(dāng)前資源需求為：Uv1={1.4,3}，Uv2={2,2}，Uv3={3,4}，Uv4={0.5,0.5}，Uv5={0.5,0.6}。根據(jù)當(dāng)前的虛擬機(jī)部署，如圖2(b)所示，主機(jī)已使用能力向量為：Up1={6.4,9}，Up2={0,0}，Up3={1,1.1}。活躍主機(jī)的負(fù)載為：Loadp1≈1.03，Loadp3≈0.21。由于主機(jī)p3負(fù)載小于p1，若p1可容納v4和v5，則可將p3轉(zhuǎn)換為休眠。UP-VMC算法首先從p3上遷移一個(gè)擁有最大負(fù)載的虛擬機(jī)。虛擬機(jī)負(fù)載由式(7)計(jì)算。

由于v4比v5負(fù)載高，UP-VMC算法嘗試將v4遷移至p1。p1需要在當(dāng)前和未來均有足夠資源能力容納該虛擬機(jī)。在PUp1={1,2.5}和PUv4={0.5,0.6}情況下，式(9)和式(10)成立，則p1為目標(biāo)主機(jī)。

Up1+Uv4≤T×Cp1={6.4,9}+{0.5,0.5}≤

0.8×{12,18}={6.9,9.5}≤{9.6,14.4}

PUp1+PUv4≤T×Cp1={1，2.5}+{0.5,0.6}≤

0.8×{12,18}={1.5,3.1}≤{9.6,14.4}

因此，v4可遷移至p1，由于主機(jī)在當(dāng)前和未來均擁有足夠資源能力。然后，算法檢測(cè)p1是否有足夠資源容納v5，且假設(shè)PUv5={0.7,0.5}：

Up1+Uv5≤T×Cp1={6.4,9}+{0.5,0.6}≤

0.8×{12,18}={6.9,9.6}≤{9.6,14.4}

PUp1+PUv5≤T×Cp1={1，2.5}+{0.7,0.5}≤

0.8×{12,18}={1.7,3}≤{9.6,14.4}

由于v5可遷移至p1，遷移后p3可轉(zhuǎn)換為休眠。最后，主機(jī)利用量從3減至1。同時(shí)，資源需求量增加，兩個(gè)休眠主機(jī)可以再次開啟。

5 性能評(píng)估

5.1 實(shí)驗(yàn)環(huán)境搭建

為了測(cè)試算法性能，在CloudSim平臺(tái)[13]中進(jìn)行仿真實(shí)驗(yàn)，構(gòu)建由M臺(tái)異構(gòu)主機(jī)構(gòu)成的數(shù)據(jù)中心，M大小由負(fù)載類型決定，如表2所示，選取PlanetLab[14]和Google[15]兩類負(fù)載類型。每種負(fù)載類型中，一半主機(jī)為HP ProLiant ML110 G4服務(wù)器，單核1 860 MIPS，一半主機(jī)為HP ProLiant ML110 G5服務(wù)器，單核2 660 MIPS。每臺(tái)主機(jī)擁有兩個(gè)核心，4 GB內(nèi)存和1 GB/s帶寬。虛擬機(jī)實(shí)例的CPU和內(nèi)存屬性參考Amazon EC2在平臺(tái)中設(shè)置，即：High-CPU中等實(shí)例(2 500 MIPS,0.85 GB)，越大實(shí)例(2 000 MIPS,3.75 GB)，小型實(shí)例(1 000 MIPS,1.7 GB)，微型實(shí)例(500 MIPS,613 MB)。

表2 負(fù)載流特征

5.2 評(píng)估指標(biāo)

1) SLA違例SLAV指標(biāo)。SLAV是一種獨(dú)立的負(fù)載指標(biāo)，用于評(píng)估虛擬機(jī)部署中SLA的交付情況。SLAV包括主機(jī)超載導(dǎo)致的SLA違例SLAVO和由于遷移導(dǎo)致的SLA違例SLAVM。對(duì)于云環(huán)境中的虛擬機(jī)合并問題而言，兩種SLA違例具有同等的重要性，因此，綜合的SLA違例指標(biāo)可考慮為兩個(gè)參數(shù)的乘積，表示為：

SLAV=SLAVO×SLAVM

(11)

式中：SLAVO表示活躍主機(jī)經(jīng)歷CPU利用率100%所占的時(shí)間比例。

(12)

式中：M表示主機(jī)數(shù)量；Tsi表示主機(jī)i經(jīng)歷的CPU利用率100%(導(dǎo)致SLA違例)的總時(shí)間；Tai表示主機(jī)i活躍狀態(tài)的總時(shí)間。

SLAVM表示由遷移導(dǎo)致的虛擬機(jī)性能下降，度量為：

(13)

式中：N表示虛擬機(jī)數(shù)量；Cdj表示由于遷移導(dǎo)致的虛擬機(jī)j性能下降的估算；Crj表示整個(gè)周期中虛擬機(jī)j的總CPU請(qǐng)求量。

2) 能耗指標(biāo)。該指標(biāo)表示數(shù)據(jù)中心中物理主機(jī)執(zhí)行負(fù)載消耗的總體能耗。主機(jī)能耗取決于CPU、內(nèi)存、存儲(chǔ)及網(wǎng)絡(luò)帶寬的利用率。研究表明，相比其他資源類型，CPU消耗了最多能源。因此，簡(jiǎn)化能耗模型后，主機(jī)能耗可表示為其CPU利用率的關(guān)系式。實(shí)驗(yàn)中依據(jù)SPECpower試驗(yàn)床中現(xiàn)實(shí)的功耗數(shù)據(jù)。表3給出了在不同的負(fù)載條件下兩類主機(jī)HP G4和HP G5的功耗情況，可以看出，低載主機(jī)轉(zhuǎn)換為休眠后可降低能耗。

表3 不同負(fù)載條件下主機(jī)的功耗 單位：W

3) 虛擬機(jī)遷移量。在線虛擬機(jī)遷移涉及在源主機(jī)上的CPU處理、源和目標(biāo)主機(jī)間的鏈路帶寬、遷移時(shí)的服務(wù)停機(jī)、遷移時(shí)間等多重代價(jià)，因此，虛擬機(jī)合并過程中需要最小化虛擬機(jī)遷移量。

5.3 比較基準(zhǔn)

將以下啟發(fā)式算法與本文的虛擬機(jī)合并算法UP-VMC進(jìn)行對(duì)比分析：

1) 改進(jìn)降序最佳適應(yīng)算法MBFD。該算法利用一個(gè)閾值限定目標(biāo)主機(jī)的CPU利用率進(jìn)行分配虛擬機(jī)遷移。若虛擬機(jī)和主機(jī)的總的已使用能力未超過主機(jī)的總能力閾值，則算法將虛擬機(jī)v分配至負(fù)載最高的主機(jī)pde，即式(9)。

比較UP-VMC，MBFD算法未使用預(yù)測(cè)模型，僅從超載主機(jī)上遷移虛擬機(jī)以避免SLA違例。因此，該算法可以通過釋放主機(jī)節(jié)省能耗。

2) 改進(jìn)降序首次適應(yīng)算法MFFD。該算法將遷移虛擬機(jī)分配至滿足資源需求且不超過CPU能力向量約束的第一臺(tái)主機(jī)上，即式(10)。

同時(shí)，該算法通過遷移超載主機(jī)上的虛擬機(jī)最小化SLA違例，也執(zhí)行了UP-VMC的第二階段，基于當(dāng)前資源需求最小化了活躍主機(jī)量。

3) 主機(jī)利用率預(yù)測(cè)的虛擬機(jī)合并算法PUP-VMC。該算法運(yùn)行機(jī)制與本文算法UP-VMC類似，但僅考慮了目標(biāo)主機(jī)的未來資源利用率進(jìn)行虛擬機(jī)分配。因此，算法分配虛擬機(jī)v至目標(biāo)主機(jī)pde，若主機(jī)pde的預(yù)測(cè)能力和虛擬機(jī)v的請(qǐng)求能力向量不超過主機(jī)總能力向量閾值，即：

PUpde+Uv≤T×Cpde

(14)

4) 虛擬機(jī)利用率預(yù)測(cè)的虛擬機(jī)合并算法VUP-VMC。該算法運(yùn)行機(jī)制與本文算法UP-VMC類似，但僅考慮了虛擬機(jī)的未來資源利用率進(jìn)行虛擬機(jī)分配。虛擬機(jī)v可分配至目標(biāo)主機(jī)pde，若主機(jī)已使用能力向量與虛擬機(jī)的預(yù)測(cè)需求能力向量不超過主機(jī)的總的能力向量閾值，即：

Upde+PUv≤T×Cpde

(15)

5) 貪婪虛擬機(jī)合并算法G-VMC。該算法從最低載主機(jī)上嘗試遷移出所有虛擬機(jī)至最高載主機(jī)上，并釋放最低載主機(jī)。為了消除不必要的遷移，該算法只要出現(xiàn)一個(gè)虛擬機(jī)無法遷移，則所有虛擬機(jī)均不遷移。

6) 蟻群優(yōu)化虛擬機(jī)合并算法ACS-VMC。一種元啟發(fā)式裝箱算法，利用蟻群覓食過程得到虛擬機(jī)遷移計(jì)劃，降低能耗和SLA違例風(fēng)險(xiǎn)。

5.4 虛擬機(jī)遷移選擇機(jī)制

引入三種典型的虛擬機(jī)遷移選擇機(jī)制觀察UP-VMC算法的性能：

1) 最小遷移時(shí)間算法MMT。該算法選擇遷移的是具有最小遷移時(shí)間的虛擬機(jī)。遷移時(shí)間定義為虛擬機(jī)的內(nèi)存除以源/主機(jī)間的網(wǎng)絡(luò)帶寬。

2) 最大負(fù)載算法MaxL。該算法選擇遷移的虛擬機(jī)具有最大的負(fù)載Loadv。

3) 最小負(fù)載算法MinL。該算法選擇遷移的虛擬機(jī)具有最小的負(fù)載Loadv。

5.5 結(jié)果分析

實(shí)驗(yàn)1觀察虛擬機(jī)遷移選擇策略對(duì)于性能的影響，結(jié)果如圖3和圖4所示。當(dāng)利用MMT進(jìn)行虛擬機(jī)遷移選擇時(shí)，UP-VMC算法可以降低能耗、SLA違例、虛擬機(jī)遷移量。此外，利用K最近鄰回歸作為負(fù)載預(yù)測(cè)模型時(shí)，UP-VMC算法也可以更好地降低三個(gè)性能指標(biāo)值，顯然K最近鄰回歸比線性回歸可以更準(zhǔn)確地對(duì)主機(jī)和虛擬機(jī)的資源利用做出預(yù)測(cè)。

(a) SLA違例情況

(b) 能耗情況

(c) 虛擬機(jī)遷移量圖3 PlanetLab負(fù)載流的性能結(jié)果-UP-VMC采用不同的虛擬機(jī)遷移選擇機(jī)制和不同的負(fù)載預(yù)測(cè)模型

(a) SLA違例情況

(c) 虛擬機(jī)遷移量圖4 GCD負(fù)載流的性能結(jié)果-UP-VMC采用不同的虛擬機(jī)遷移選擇機(jī)制和不同的負(fù)載預(yù)測(cè)模型

實(shí)驗(yàn)2觀察與基準(zhǔn)算法的對(duì)比結(jié)果。先以PlanetLab負(fù)載流進(jìn)行測(cè)試。由于越高的CPU利用閾值將導(dǎo)致越高的性能下降和越多的遷移，而低閾值又會(huì)增加能耗，因此需要選取合適閾值大小。實(shí)驗(yàn)中在50%～100%范圍內(nèi)改變閾值取值觀察性能指標(biāo)值的影響。圖5(a)顯示了七種算法的SLA違例情況。顯然，UP-VMC算法對(duì)比其他算法可以更有效地降低SLA違例，這是由于該算法根據(jù)設(shè)計(jì)的預(yù)測(cè)模型在將虛擬機(jī)遷移至目標(biāo)主機(jī)時(shí)不會(huì)導(dǎo)致該主機(jī)變?yōu)槎唐趦?nèi)的超載主機(jī)。此外，UP-VMC算法可以從當(dāng)前超載和預(yù)測(cè)超載主機(jī)上遷移虛擬機(jī)以避免SLA違例。圖5(b)顯示，UP-VMC算法較MFFD可以節(jié)省約71%的能耗，原因在于本文算法可以將虛擬機(jī)裝箱至高負(fù)載主機(jī)，最小化了活躍主機(jī)的數(shù)量。圖5(c)顯示了虛擬機(jī)合并過程中的虛擬機(jī)遷移量。由于資源利用的預(yù)測(cè)，本文算法有效降低了虛擬機(jī)遷移量，且優(yōu)于基準(zhǔn)算法。

(a) SLA違例情況

(b) 能耗情況

(c) 虛擬機(jī)遷移量圖5 PlanetLab負(fù)載流的性能結(jié)果

以GCD負(fù)載流同樣進(jìn)行了一次仿真實(shí)驗(yàn)，仿真過程中，每個(gè)虛擬機(jī)隨機(jī)分配一個(gè)負(fù)載流。圖6(a)顯示UP-VMC算法比基準(zhǔn)算法大大降低了SLA違例，這是由于UP-VMC能夠通過主機(jī)和虛擬機(jī)的負(fù)載預(yù)測(cè)以及虛擬機(jī)遷移不會(huì)導(dǎo)致目標(biāo)主機(jī)變?yōu)槌d主機(jī)的方式有效避免了SLA違例。圖6(b)顯示，UP-VMC擁有最多的能耗節(jié)省，這是由于UP-VMC通過裝箱虛擬機(jī)至更少的主機(jī)釋放了低載主機(jī)，節(jié)省了能耗。同時(shí)，由圖6(c)，UP-VMC也得到了最少的虛擬機(jī)遷移量，這利于本文算法可以根據(jù)當(dāng)前和未來的資源占用分配遷移虛擬機(jī)，降低了無用虛擬機(jī)遷移。

(a) SLA違例情況

(b) 能耗情況

(c) 虛擬機(jī)遷移量圖6 GCD負(fù)載流的性能結(jié)果

綜合實(shí)驗(yàn)結(jié)果分析，負(fù)載的動(dòng)態(tài)變化會(huì)直接影響虛擬 機(jī)遷移過程。當(dāng)負(fù)載量急劇增加時(shí)，虛擬機(jī)遷移量也會(huì)相應(yīng)增加，由于在確定的資源能力狀態(tài)下，必須通過虛擬機(jī)遷移才能滿足更大的負(fù)載需求。在此過程中，資源利用閾值也會(huì)影響虛擬機(jī)遷移，閾值的增加也會(huì)導(dǎo)致遷移量的增加，這是因?yàn)榇藭r(shí)在相同條件下資源可容納的負(fù)載會(huì)增多，可允許的遷移也會(huì)增加。但是，在虛擬機(jī)和主機(jī)兩端進(jìn)行了資源利用預(yù)測(cè)可以明顯降低虛擬機(jī)遷移量，避免動(dòng)態(tài)負(fù)載條件下的不必要遷移。當(dāng)負(fù)載量比較平穩(wěn)或較小時(shí)，虛擬機(jī)遷移頻率也會(huì)較小，因?yàn)橐延匈Y源能力可以滿足負(fù)載需求，無須進(jìn)行虛擬機(jī)遷移。

綜合圖5和圖6可以發(fā)現(xiàn)，閾值的增加會(huì)導(dǎo)致能耗的降低，但遷移量和SLA違例會(huì)有所增加。因此，在實(shí)際環(huán)境中，應(yīng)該綜合考慮性能優(yōu)化目標(biāo)來設(shè)置合適的閾值。

6 結(jié) 語

本文提出一種預(yù)測(cè)感知的虛擬機(jī)合并算法。算法將虛擬機(jī)合并形式化為多目標(biāo)向量裝箱問題。為了將虛擬機(jī)合并至最小數(shù)量的活躍主機(jī)上，算法利用回歸模型同步考慮了主機(jī)上的當(dāng)前負(fù)載和未來負(fù)載，使得虛擬機(jī)遷移過程中在目標(biāo)主機(jī)選擇上可以避免主機(jī)在虛擬機(jī)遷移后變?yōu)槌d主機(jī)，增加SLA違例風(fēng)險(xiǎn)。通過兩類負(fù)載類型的仿真測(cè)試，證明了本文算法不僅可以降低數(shù)據(jù)中心能耗，還可以同步降低SLA違例和虛擬機(jī)遷移量。進(jìn)一步的研究可集中考慮資源維度更多的虛擬機(jī)合并和遷移問題。除了關(guān)鍵的CPU資源和內(nèi)存之外，網(wǎng)絡(luò)資源占用和鏈路擁塞也是虛擬機(jī)合并過程中可能需要考慮的問題，尤其針對(duì)通信密集型應(yīng)用負(fù)載類型而言，可能導(dǎo)致通信鏈路的擁塞，此時(shí)若僅考慮CPU和內(nèi)存資源兩個(gè)維度，可能導(dǎo)致最終的虛擬機(jī)合并與遷移出現(xiàn)超時(shí)問題。