基于K最近鄰回歸預(yù)測(cè)的高能效虛擬機(jī)合并

王 諾，李 艷

(河北傳媒學(xué)院 信息管理中心，河北 石家莊 051430)

0 引 言

云數(shù)據(jù)中心中，動(dòng)態(tài)的虛擬機(jī)合并實(shí)現(xiàn)了運(yùn)行時(shí)虛擬機(jī)在不同主機(jī)間的在線遷移[1,2]，尤其在主機(jī)處于較低負(fù)載或超載狀態(tài)下時(shí)，遷移將具有諸多好處。因此，通過(guò)遷移操作會(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來(lái)描述，根據(jù)吞吐量或服務(wù)的響應(yīng)時(shí)間上的性能表現(xiàn)來(lái)定義[4]。

比較已有工作最小化主機(jī)利用數(shù)量，本文將設(shè)計(jì)一種啟發(fā)式算法同步最小化虛擬機(jī)遷移次數(shù)和SLA違例。所提算法進(jìn)行動(dòng)態(tài)虛擬機(jī)合并主要由兩個(gè)階段組成：①嘗試將負(fù)載最低主機(jī)上的所有虛擬機(jī)遷移至負(fù)載最大主機(jī)上；②從當(dāng)前超載或預(yù)測(cè)在近期會(huì)變?yōu)槌d的主機(jī)上遷移出部分虛擬機(jī)以防止可能的SLA違例。同時(shí)，提出的算法可以根據(jù)當(dāng)前和未來(lái)的資源請(qǐng)求將遷移虛擬機(jī)分配至合適主機(jī)上。為了預(yù)測(cè)負(fù)載，本文設(shè)計(jì)了一種基于K最近鄰回歸KNNR模型的預(yù)測(cè)方法，對(duì)未來(lái)資源利用率進(jìn)行預(yù)測(cè)，該預(yù)測(cè)方法優(yōu)于線性回歸方法。為了訓(xùn)練和測(cè)試預(yù)測(cè)模型，本文通過(guò)運(yùn)行IaaS云環(huán)境中的多種現(xiàn)實(shí)負(fù)載生成歷史數(shù)據(jù)集，并通過(guò)實(shí)驗(yàn)驗(yàn)證了所提動(dòng)態(tài)虛擬機(jī)合并算法的有效性。

1 相關(guān)工作

動(dòng)態(tài)虛擬機(jī)合并可以增加資源利用率和提高數(shù)據(jù)中心能效，已有很多相關(guān)研究。文獻(xiàn)[5]提出一種動(dòng)態(tài)服務(wù)器遷移和合并算法，在給定負(fù)載狀態(tài)和支持SLA違例的條件下可以降低物理能力的使用量，算法利用了裝箱啟發(fā)式方法和時(shí)序預(yù)測(cè)技術(shù)最小化主機(jī)利用量。然而，算法并沒(méi)有考慮新部署中虛擬機(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è)置無(wú)法處理動(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ī)合并問(wèn)題可以形式化為裝箱問(wèn)題，裝箱問(wèn)題即是將若干物品裝入有限數(shù)量的箱子內(nèi)，并最小化箱子數(shù)量。每臺(tái)虛擬機(jī)可視為一個(gè)物品，每臺(tái)主機(jī)即為一個(gè)箱子。由于裝箱問(wèn)題的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ī)合并問(wèn)題。原因在于：①虛擬機(jī)和主機(jī)擁有多個(gè)維度資源，如CPU、內(nèi)存和網(wǎng)絡(luò)帶寬。若考慮CPU和內(nèi)存資源的約束，虛擬機(jī)合并問(wèn)題就是典型的二維裝箱問(wèn)題；②虛擬機(jī)合并問(wèn)題可修正為可變箱子(主機(jī))大小的裝箱問(wèn)題，不同于經(jīng)典的等同能力箱子的裝箱問(wèn)題；③經(jīng)典裝箱方法僅最小化箱子數(shù)量，即單目標(biāo)優(yōu)化。而本文考慮的目標(biāo)包括虛擬機(jī)遷移次數(shù)和SLA違例問(wèn)題。文獻(xiàn)[10]設(shè)計(jì)了BFD的改進(jìn)算法，可以節(jié)省部分能耗。文獻(xiàn)[11]利用FFD的改進(jìn)算法在功耗和遷移代價(jià)間取得均衡。文獻(xiàn)[12]利用改進(jìn)的FF和BF算法在未考慮性能下降的情況下最小化主機(jī)利用量。然而，以上算法多是考慮優(yōu)化比較單一的目標(biāo)，沒(méi)有在能效和服務(wù)性能上作出綜合的考量。

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

2 問(wèn)題的提出

虛擬機(jī)合并可以優(yōu)化虛擬機(jī)部署，減少活躍主機(jī)利用量，這其中需要考慮兩個(gè)因素：SLA違例率和虛擬機(jī)遷移量。基于未來(lái)負(fù)載預(yù)測(cè)可以強(qiáng)化兩個(gè)優(yōu)化目標(biāo)。以兩個(gè)實(shí)例描述未作負(fù)載預(yù)測(cè)下傳統(tǒng)虛擬機(jī)合并方法的局限性。如圖1和圖2所示，現(xiàn)有2臺(tái)主機(jī)和3臺(tái)虛擬機(jī)的部署需求。如圖1(a)所示，Host1和Host2的CPU利用率分別為0.35和0.6。由于Host1擁有足夠資源部署虛擬機(jī)VM3，傳統(tǒng)虛擬機(jī)合并將VM3遷移至Host1以減少主機(jī)利用量，并將Host2轉(zhuǎn)換為休眠。在時(shí)間t+1，VM3的CPU請(qǐng)求從0.6增加至0.75，如圖1(b)所示。由于Host1沒(méi)有VM3請(qǐng)求的空閑能力，Host1出現(xiàn)超載，發(fā)生SLA違例。因此VM3遷移至Host2以避免SLA違例，如圖1(c)所示，此次即為無(wú)用遷移。因此，如果遷移前可以預(yù)測(cè)資源請(qǐng)求，虛擬機(jī)合并就可以避免非必要虛擬機(jī)遷移并降低SLA違例。

圖1 示例1：未作資源利用率預(yù)測(cè)

如圖2所示，在當(dāng)前時(shí)間t，VM3遷移至Host1，由于Host1擁有足夠空閑資源部署VM3，如圖2(a)所示。如圖2(b)所示，Host2轉(zhuǎn)換為休眠，僅Host1為活躍主機(jī)。由于VM2的請(qǐng)求CPU利用率增加，此時(shí)出現(xiàn)熱點(diǎn)主機(jī)。VM3遷移至之前的目標(biāo)主機(jī)以避免SLA違例，如圖2(c)所示。因此，若虛擬機(jī)合并算法可以根據(jù)主機(jī)的未來(lái)資源占用率情況對(duì)虛擬機(jī)進(jìn)行遷移分配，將極大減少遷移次數(shù)和SLA違例。

圖2 示例2：作資源利用率預(yù)測(cè)

3 系統(tǒng)模型

動(dòng)態(tài)虛擬機(jī)合并可以形式化為裝箱模型，是NP問(wèn)題。由于裝箱問(wèn)題僅能在給定物品下最小化箱子數(shù)量，直接應(yīng)用于虛擬機(jī)合并中擁有一定局限性。很多算法也以裝箱思路求解過(guò)虛擬機(jī)合并問(wèn)題。然而，這會(huì)產(chǎn)生過(guò)多的非必要虛擬機(jī)遷移，增加SLA違例風(fēng)險(xiǎn)。虛擬化是云計(jì)算數(shù)據(jù)中心的主要技術(shù)，利用虛擬化技術(shù)可以在物理服務(wù)器上部署多個(gè)不同性能的虛擬機(jī)，以提高整體的資源利用率。虛擬化的一個(gè)主要優(yōu)勢(shì)是在數(shù)據(jù)中心內(nèi)可以進(jìn)行動(dòng)態(tài)的虛擬機(jī)合并來(lái)降低能耗，通過(guò)將虛擬機(jī)合并到更少數(shù)量的物理主機(jī)上，并將閑置主機(jī)轉(zhuǎn)換為睡眠模式以提升能效。圖3是虛擬機(jī)合并與遷移系統(tǒng)模型。云數(shù)據(jù)中心由M臺(tái)異構(gòu)主機(jī)構(gòu)成，可通過(guò)虛擬機(jī)監(jiān)視器VMM部署N臺(tái)虛擬機(jī)。每臺(tái)主機(jī)擁有不同的資源屬性，包括CPU、內(nèi)存和網(wǎng)絡(luò)帶寬。在給定的時(shí)間，數(shù)據(jù)中心可服務(wù)于多個(gè)同步的用戶需求。用戶通過(guò)虛擬機(jī)請(qǐng)求方式發(fā)送需求，每個(gè)需求的長(zhǎng)度以百萬(wàn)指令數(shù)MI描述，CPU性能以每秒百萬(wàn)指令數(shù)MIPS描述。模型包括兩個(gè)代理Agent：一個(gè)是主節(jié)點(diǎn)上的全局代理GA(global agent)，一個(gè)是主機(jī)上分布的本地代理LA(local agent)。所提出的動(dòng)態(tài)虛擬機(jī)合并算法每次迭代中的任務(wù)處理次序如下：

圖3 系統(tǒng)模型

(1)每個(gè)LA監(jiān)測(cè)主機(jī)的資源利用率，并利用K最近鄰回歸預(yù)測(cè)主機(jī)短期的CPU利用率；

(2)GA收集LA的利用率數(shù)據(jù)，利用UP-BFD算法建立遷移計(jì)劃(算法詳細(xì)設(shè)計(jì)中描述)；

(3)GA發(fā)送遷移指令至VMM，執(zhí)行虛擬機(jī)合并任務(wù)。該指令指定了虛擬機(jī)的遷移目標(biāo)主機(jī)；

(4)在接收GA的遷移指令后，VMM執(zhí)行實(shí)際的虛擬機(jī)遷移。

4 UP-BFD算法的詳細(xì)設(shè)計(jì)

4.1 符號(hào)說(shuō)明

初始時(shí)，虛擬機(jī)通過(guò)傳統(tǒng)的BFD算法將虛擬機(jī)分配至主機(jī)上。BFD算法首先根據(jù)資源利用率請(qǐng)求的降序序列將所有虛擬機(jī)進(jìn)行排序，然后選擇每個(gè)虛擬機(jī)分配至一個(gè)主機(jī)上，使得主機(jī)擁有最少的剩余空閑能力。由于虛擬機(jī)的資源利用率會(huì)隨著時(shí)間發(fā)生變化，即動(dòng)態(tài)負(fù)載，初始的虛擬機(jī)部署需要周期性地通過(guò)虛擬機(jī)合并算法進(jìn)行不斷修正。為了實(shí)現(xiàn)該目的，本文設(shè)計(jì)了利用率預(yù)測(cè)感知的降序最佳適應(yīng)算法UP-BFD，可以根據(jù)當(dāng)前和未來(lái)的資源請(qǐng)求，優(yōu)化虛擬機(jī)部署。為了方便算法設(shè)計(jì)的描述，表1給出相關(guān)參數(shù)說(shuō)明。

表1 參數(shù)說(shuō)明

4.2 負(fù)載計(jì)算與約束說(shuō)明

為了降低數(shù)據(jù)中心能耗，UP-BFD算法通過(guò)釋放冷點(diǎn)的方式將最低負(fù)載主機(jī)(冷點(diǎn))上的虛擬機(jī)遷移至負(fù)載最高主機(jī)(熱點(diǎn))上。如果最冷點(diǎn)主機(jī)上的所有虛擬機(jī)無(wú)法遷移至其它主機(jī)上，則全部都不遷移。因此，未釋放冷點(diǎn)上的虛擬機(jī)遷移并不會(huì)實(shí)施，這樣可以消除不必要的虛擬機(jī)遷移。由于將一臺(tái)虛擬機(jī)分配至主機(jī)需要確定的主機(jī)資源量，有效的虛擬機(jī)合并算法必須感知資源維度，這意味著資源利用比例(CPU和內(nèi)存資源)在決定虛擬機(jī)部署過(guò)程中就需要在每臺(tái)主機(jī)上予以確定。由于主機(jī)的CPU和內(nèi)存能力是表示負(fù)載等級(jí)的主要因素，本文的算法也主要考慮CPU和內(nèi)存利用率兩個(gè)資源維度。將主機(jī)負(fù)載定義為每個(gè)資源維度的總利用率，即

Lh=RCPU(h)+RMEM(h)

(1)

(2)

(3)

其中，RCPU(h) 定義為主機(jī)h上已經(jīng)分配的CPU能力 (UCPU(h)) 除以主機(jī)的總體CPU能力 (CCPU(h))，RMEM(h)

定義為主機(jī)h上已經(jīng)分配的內(nèi)存能力 (UMEM(h)) 除以主機(jī)的總體內(nèi)存能力 (CMEM(h))。

UP-BFD算法能夠決定主機(jī)上的哪些虛擬機(jī)需要遷移至其它主機(jī)上，算法會(huì)選擇主機(jī)上所有虛擬機(jī)中最高負(fù)載的虛擬機(jī)作為遷移目標(biāo)，由于負(fù)載越大的虛擬機(jī)越難以插入至其它主機(jī)上。虛擬機(jī)v的負(fù)載Lv定義為

Lv=RCPU(v)+RMEM(v)

(4)

(5)

(6)

其中，RCPU(v) 和RMEM(v) 分別表示虛擬機(jī)v的CPU和內(nèi)存利用率，UCPU(v) 和UMEM(v) 分別表示虛擬機(jī)v請(qǐng)求的CPU和內(nèi)存利用率，CCPU(u) 和CMEM(v) 分別表示虛擬機(jī)的總體CPU和內(nèi)存能力。

為了尋找遷移虛擬機(jī)的目標(biāo)主機(jī)，UP-BFD算法使用兩種約束避免SLA違例和非必要的遷移。第一個(gè)約束是：若主機(jī)hd擁有足夠的資源部署虛擬機(jī)，則可允許虛擬機(jī)v遷移至主機(jī)hd。由于某些資源利用率可能達(dá)到100%而引起SLA違例的風(fēng)險(xiǎn)，算法引入門限值T限制主機(jī)上虛擬機(jī)的CPU資源請(qǐng)求量。因此，第一個(gè)約束條件可表示為

UCPU(hd)+UCPU(v)≤T×CCPU(hd)

(7)

第二個(gè)約束確保目標(biāo)主機(jī)hd在虛擬機(jī)v遷移過(guò)來(lái)后不會(huì)變?yōu)槎唐诳赡艿某d主機(jī)。考慮該原因，UP-BFD算法考慮了主機(jī)和虛擬機(jī)的未來(lái)CPU請(qǐng)求。UP-BFD算法利用K最近鄰回歸方法對(duì)CPU利用率進(jìn)行預(yù)測(cè)，詳細(xì)過(guò)程見(jiàn)4.3節(jié)說(shuō)明。由于負(fù)載的動(dòng)態(tài)變化，UP-BFD算法將側(cè)重于短期的負(fù)載預(yù)測(cè)，以下資源能力約束用于將虛擬機(jī)v分配至主機(jī)h上

PUCPU(hd)+PUCPU(v)≤T×CCPU(hd)

(8)

其中，PUCPU(hd) 表示主機(jī)hd的預(yù)測(cè)CPU利用率，PUCPU(v) 表示虛擬機(jī)v的預(yù)測(cè)CPU利用率。主機(jī)和虛擬機(jī)的預(yù)測(cè)CPU利用率限制在總體能力的門限值以內(nèi)。如果T=0.5，則表示主機(jī)hd和虛擬機(jī)的總體預(yù)測(cè)利用率不能超過(guò)總體能力的50%。因此，基于以上兩個(gè)約束條件，算法在選擇目標(biāo)主機(jī)時(shí)，需要該主機(jī)在當(dāng)前時(shí)刻以及未來(lái)均擁有足夠的可用資源。

此外，UP-BFD算法還需要從超載和可預(yù)測(cè)超載主機(jī)上遷移部分虛擬機(jī)以降低SLA違例。如果當(dāng)前CPU利用率超過(guò)主機(jī)能力，則該主機(jī)可視為超載主機(jī)集合Hover中的成員。因此，部分虛擬機(jī)需要從該超載主機(jī)上遷移至其它主機(jī)以降低SLA違例可能。此外，UP-BFD算法可以根據(jù)主機(jī)的預(yù)測(cè)CPU利用率預(yù)測(cè)到主機(jī)何時(shí)會(huì)成為超載主機(jī)。若預(yù)測(cè)利用率大于可用CPU能力，則該主機(jī)可視為預(yù)測(cè)超載主機(jī)集合Hover’中的成員。因此，部分虛擬機(jī)也需要從預(yù)測(cè)超載主機(jī)上遷移出去以降低SLA違例。

4.3 基于K最近鄰回歸的負(fù)載預(yù)測(cè)

負(fù)載預(yù)測(cè)過(guò)程分為兩個(gè)步驟:第一步是確定近鄰樣本的最優(yōu)k值;第二步是基于最優(yōu)k值和樣本數(shù)據(jù)對(duì)CPU利用率進(jìn)行預(yù)測(cè)。算法1給出最優(yōu)k值的求解過(guò)程。算法輸入m個(gè)樣本的歷史利用率數(shù)據(jù)集X，對(duì)于每一個(gè)可能的k值(步驟(3))，先將該k值的預(yù)測(cè)損失值初始化為0，即步驟(4)。然后，遍歷m個(gè)樣本數(shù)據(jù)(步驟(5))，數(shù)據(jù)集中所選樣本作為測(cè)試樣本，剩余樣本用于訓(xùn)練數(shù)據(jù)集，即步驟(6)～步驟(7)。然后，調(diào)用算法2，基于當(dāng)前的k值、測(cè)試樣本和訓(xùn)練數(shù)據(jù)集，預(yù)測(cè)在當(dāng)前測(cè)試樣本下的利用率，即步驟(8)。預(yù)測(cè)準(zhǔn)確度通過(guò)每個(gè)k值的損失值的總和進(jìn)行評(píng)估，即步驟(9)。遍歷所有可能k值和所有樣本，擁有最小損失值的k值被選擇為k最近鄰回歸模型的最優(yōu)k值，如步驟(12)。最后，可以在步驟(13)～步驟(14)根據(jù)所選最優(yōu)k個(gè)最近鄰樣本預(yù)測(cè)最終的資源利用率。

算法1： KNN-UP算法

(1)Input:datasetXwithmsamples

(2)Output:predictedUtil

(3)fork=1 tomdo

(4)loss[k]←0

(5)fori=1 tomdo

(6)TestSample←xi//選取測(cè)試樣本

(7)TrainingDataset←X-{xi}//選取訓(xùn)練樣本

(8)yi’←KNN(TestSample,TrainingDataset,k)

(9)loss[k]←loss[k]+power((yi’-yi),2)

(10)endfor

(11)endfor

(12)kbest←argminkloss[k]//得到最優(yōu)k值

(13)predictedUtil←KNN(currentUtil(host),kbest)

(14)returnpredictedUtil

算法2的目標(biāo)是根據(jù)當(dāng)前已有的訓(xùn)練數(shù)據(jù)集、當(dāng)前k個(gè)最近鄰數(shù)據(jù)和樣本序列預(yù)測(cè)下一個(gè)CPU利用率，算法總共分3步進(jìn)行。第一步計(jì)算樣本xq與訓(xùn)練集中其它所有樣本間的歐氏距離，即步驟(3)～步驟(8)，第二步選擇樣本xq的k個(gè)最近鄰數(shù)據(jù)，即步驟(10)～步驟(12)，最后第三步通過(guò)計(jì)算其k個(gè)最近鄰的均值估算CPU資源利用率，即步驟(13)～步驟(17)。

算法2： KNN算法

(1)Input:query-samplexq, training dataset, number of nearest neighborsk

(2)Output:the label of samplexq(y’)

(3)forj=1 tomdo//步驟(1)

(4)distance[j] ←0

(5)fori=1 tondo

(6)distance[j]←distance[j]+(xqi-xji)2

(7)endfor

(8)distance[j]←sqrt(distance[j])

(9)//sort distance array

(10)fori=1 tokdo//步驟(2)

(11)nearestSet[i]=distance[i]

(12)endfor

(13)sum←0//步驟(3)

(14)forallz∈nearestSetdo

(15)sum←sum+yz

(16)y’ ←sum/k

(17)returny’

4.4 UP-BFD算法過(guò)程

算法3給出了UP-BFD算法實(shí)現(xiàn)的詳細(xì)過(guò)程，由兩個(gè)階段組成：①嘗試從最低負(fù)載主機(jī)上遷移所有虛擬機(jī)，并關(guān)閉該主機(jī)以節(jié)省能耗；②從超載和預(yù)測(cè)超載主機(jī)上遷移部分虛擬機(jī)以降低SLA違例。在第一個(gè)階段中，即步驟(2) ～步驟(21)，步驟(2)根據(jù)負(fù)載等級(jí)的降序?qū)χ鳈C(jī)進(jìn)行排序，并將排序后的主機(jī)存入列表H中。UP-BFD算法將H中最后一個(gè)主機(jī)(最低負(fù)載主機(jī))考慮為源主機(jī)hs(步驟(3))，遷移其上所有虛擬機(jī)并釋放hs。為了選擇從主機(jī)hs上需要遷移的第一個(gè)虛擬機(jī)，算法將主機(jī)hs上的所有虛擬機(jī)根據(jù)負(fù)載降序進(jìn)行排列，并將排列后的虛擬機(jī)存入列表Vm中(步驟(4))。為了尋找遷移虛擬機(jī)的合適目標(biāo)主機(jī)，UP-BFD算法從H中除了源主機(jī)hs以外的第一個(gè)主機(jī)(擁有最高的負(fù)載)依次掃描，直到找到第一個(gè)能滿足遷移需求的主機(jī)為止，即步驟(5)～步驟(7)。UP-BFD算法選擇目標(biāo)主機(jī)hd需要滿足在當(dāng)前和短期未來(lái)遷移虛擬機(jī)的資源請(qǐng)求，即步驟(8)。最后，新的虛擬機(jī)部署被添加至遷移決策M(jìn)，即步驟(9)。遷移計(jì)劃為一個(gè)三元組 (hs;v;hd)，hs為源主機(jī)，v為遷移虛擬機(jī)，hd為目標(biāo)主機(jī)。步驟(10)對(duì)源和目標(biāo)主機(jī)的已經(jīng)利用CPU利用率進(jìn)行更新，以反映出遷移后的結(jié)果。變量success用于檢測(cè)是否源主機(jī)上的所有虛擬機(jī)已被遷移。僅在所有虛擬機(jī)能夠遷移的情況下才作出遷移決策，否則不作遷移。因此，如果success為失效，算法將移出遷移計(jì)劃中的所有元組元素并恢復(fù)源主機(jī)和目標(biāo)主機(jī)的CPU能力，即步驟(16)～步驟(18)所示；否則，源主機(jī)上的所有虛擬機(jī)遷移后，該主機(jī)將轉(zhuǎn)換為休眠，不再部署任何虛擬機(jī)，即步驟(20)。

在第二個(gè)階段，步驟(22)～步驟(40)中，算法首先遍歷超載和預(yù)測(cè)超載主機(jī)列表，步驟(23)～步驟(24)根據(jù)負(fù)載等級(jí)的降序?qū)χ鳈C(jī)上的虛擬機(jī)進(jìn)行排列，并開(kāi)始遷移請(qǐng)求最大能力的虛擬機(jī)。當(dāng)前CPU利用率或預(yù)測(cè)CPU利用率超過(guò)主機(jī)總體能力時(shí)，虛擬機(jī)v需要遷移至其它主機(jī)，即步驟(25)。然后，算法基于兩個(gè)約束條件尋找遷移虛擬機(jī)v的目標(biāo)主機(jī)，即步驟(27)。最后，新的虛擬機(jī)部署被添加至遷移計(jì)劃M中，即步驟(28)。如果算法在所有活躍主機(jī)中無(wú)法找到部署遷移虛擬機(jī)的目標(biāo)主機(jī)，則重新開(kāi)啟一臺(tái)休眠主機(jī)，即步驟(33)～步驟(35)。UP-BFD算法的輸出為遷移計(jì)劃M，GA將發(fā)送遷移計(jì)劃指令至虛擬機(jī)監(jiān)視器VMM執(zhí)行具體虛擬機(jī)遷移。

算法3： UP-BFD算法

(1)M=NULL

(2)H←sort all hosts in descending loadLh

(3)hs←last host inH

(4)Vm←sort VMs on hosthsin descending loadLv

(5)forv∈Vmdo

(6)success=false

(7)forhd∈H-hsdo

(8)if(UCPU(hd)+UCPU(v)≤T×CCPU(hd)) and (PUCPU(hd)+PUCPU(v)≤T×CCPU(hd))then

(9)M=M∪{(hs,v,hd)}

(10) updateUCPU(hs) andUCPU(hd)

(11)success=true

(12)break

(13)endif

(14)endfor

(15)endfor

(16)ifsuccess=falsethen

(17)M=NULL

(18) recoverUCPU(hs) andUCPU(hd)

(19)else

(20) switchhsto the sleep mode

(21)endif

(22)forhs∈[Hover,Hover’]do

(23)Vm←sort VMs on hosthsin descending loadLv

(24)forv∈Vmdo

(25)if((UCPU(hs)≥CCPU(hs))‖(PUCPU(hs)≥CCPU(hs))then

(26)forhd∈H-[Hover,Hover’]do

(27)if(UCPU(hd)+UCPU(v)≤T×CCPU(hd)) and (PUCPU(hd)+PUCPU(v)≤T×CCPU(hd))then

(28)M=M∪{(hs,v,hd)}

(29) updateUCPU(hs) andUCPU(hd)

(30)break

(31)endif

(32)endfor

(33)if((UCPU(h)≥CCPU(h))‖(PUCPU(h)≥CCPU(h))then

(34) switch on a dormant host

(35)endif

(36)else

(37)break

(38)endif

(39)endfor

(40)endfor

5 性能評(píng)估

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

為了評(píng)估動(dòng)態(tài)虛擬機(jī)合并算法UP-BFD的性能，利用仿真平臺(tái)CloudSim[13]實(shí)現(xiàn)了高能效的虛擬機(jī)合并算法。仿真環(huán)境中，構(gòu)建由800臺(tái)異構(gòu)主機(jī)組成的云數(shù)據(jù)中心，選擇平臺(tái)支持的具有代表性的兩種主機(jī)配置：HP ProLiant ML110 G4(Intel Xeon 3040,2cores×1860 MHz,4 GB)和HP ProLiant ML110 G5(Intel Xeon 3075,2cores×2660 MHz,4 GB)。每臺(tái)服務(wù)器主機(jī)的網(wǎng)絡(luò)帶寬設(shè)置為1 GB/s。虛擬機(jī)數(shù)量由負(fù)載類型決定，實(shí)驗(yàn)中測(cè)試了兩種類型負(fù)載：隨機(jī)型負(fù)載和現(xiàn)實(shí)負(fù)載。隨機(jī)型負(fù)載中，用戶發(fā)送800個(gè)異構(gòu)虛擬機(jī)請(qǐng)求，每臺(tái)虛擬機(jī)運(yùn)行一種應(yīng)用負(fù)載，應(yīng)用負(fù)載對(duì)于CPU的占用服從均勻分布。現(xiàn)實(shí)負(fù)載中，選擇CoMon工程項(xiàng)目中一個(gè)時(shí)間段內(nèi)的負(fù)載數(shù)據(jù)，見(jiàn)表2，該數(shù)據(jù)由PlanetLab平臺(tái)[14]監(jiān)測(cè)得到。監(jiān)測(cè)數(shù)據(jù)中，CPU利用率數(shù)據(jù)是從多于一千臺(tái)虛擬機(jī)上每隔5 min監(jiān)測(cè)得到的結(jié)果。虛擬機(jī)部署于全球超過(guò)500個(gè)地理位置，這也是較為典型的Amazon EC2式的基礎(chǔ)設(shè)施云服務(wù)環(huán)境下的負(fù)載類型。

表2 現(xiàn)實(shí)負(fù)載的虛擬機(jī)請(qǐng)求量

5.2 評(píng)估指標(biāo)及時(shí)間復(fù)雜度分析

(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ī)合并問(wèn)題而言，兩種SLA違例具有同等的重要性，因此，綜合的SLA違例指標(biāo)可考慮為兩個(gè)參數(shù)的乘積，表示為

SLAV=SLAVO×SLAVM

(9)

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

(10)

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

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

(11)

其中，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)床[15]中現(xiàn)實(shí)的功耗數(shù)據(jù)。表3給出了在不同的負(fù)載條件下兩類主機(jī)HP G4和HP G5的功耗情況。

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

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

算法時(shí)間復(fù)雜度分析。UP-BFD算法的實(shí)現(xiàn)由兩個(gè)階段構(gòu)成，第一階段嘗試從最低負(fù)載主機(jī)上遷移所有虛擬機(jī)，第二階段從超載和預(yù)測(cè)超載主機(jī)上遷移部分虛擬機(jī)。假設(shè)M為主機(jī)數(shù)量，N為虛擬機(jī)數(shù)量。第一階段最差情況下需要遍歷所有主機(jī)上的所有虛擬機(jī)，故其時(shí)間復(fù)雜度為O(M×N)。 第二階段同樣需要遍歷超載和預(yù)測(cè)超載主機(jī)上的虛擬機(jī)，預(yù)測(cè)超載過(guò)程利用K最近鄰回歸預(yù)測(cè)方法KNN，而此時(shí)KNN的最差時(shí)間復(fù)雜度為O(M×N)。 綜上，UP-BFD算法的時(shí)間復(fù)雜度為O(M×N+M×N)=O(M×N)。

5.3 比較基準(zhǔn)

完成以下啟發(fā)式算法與本文的虛擬機(jī)動(dòng)態(tài)合并算法UP-BFD進(jìn)行對(duì)比分析：

(1)改進(jìn)降序最佳適應(yīng)算法MBFD。該算法利用一個(gè)門限值限定目標(biāo)主機(jī)的CPU利用率，在虛擬機(jī)和主機(jī)所利用的總CPU能力不超過(guò)總體CPU能力的情況下，部署遷移虛擬機(jī)至擁有最小剩余能力的主機(jī)上，即

UCPU(hd)+UCPU(v)≤T×CCPU(hd)

(12)

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

UCPU(hd)+UCPU(v)≤T×CCPU(hd)

(13)

(3)主機(jī)資源利用率預(yù)測(cè)的降序最佳適應(yīng)算法HUP-BFD。該算法通過(guò)K最近鄰回歸預(yù)測(cè)了主機(jī)的資源請(qǐng)求。算法利用預(yù)測(cè)模型和門限值T限定主機(jī)利用率。若預(yù)測(cè)主機(jī)利用率與虛擬機(jī)請(qǐng)求的CPU利用率不超過(guò)總的CPU利用率，則將虛擬機(jī)v遷移至目標(biāo)主機(jī)hd，即

PUCPU(hd)+UCPU(v)≤T×CCPU(hd)

(14)

(4)虛擬機(jī)資源利用率預(yù)測(cè)的降序最佳適應(yīng)算法VMUP-BFD。該算法通過(guò)K最近鄰回歸預(yù)測(cè)虛擬機(jī)的資源請(qǐng)求。若主機(jī)CPU利用率與預(yù)測(cè)虛擬機(jī)請(qǐng)求CPU利用率不超過(guò)總CPU利用率，則將虛擬機(jī)v遷移至主機(jī)hd，即

UCPU(hd)+PUCPU(v)≤T×CCPU(hd)

(15)

5.4 結(jié)果分析

第一個(gè)實(shí)驗(yàn)中，通過(guò)均勻分布的隨機(jī)負(fù)載進(jìn)行實(shí)驗(yàn)。較高的CPU利用率門限值會(huì)導(dǎo)致較高的性能下降和虛擬機(jī)遷移量，而較低的門限值會(huì)導(dǎo)致更高的能耗。因此，為了考慮多個(gè)指標(biāo)系數(shù)間的均衡優(yōu)化，需要尋找一個(gè)合適的門限值。實(shí)驗(yàn)中設(shè)置門限值在50%-100%之間以觀察資源利用門限值對(duì)于性能指標(biāo)的影響。圖4是在不同的門限值下，5種算法的SLA違例情況。UP-BFD算法比其它算法可以有效降低SLA違例比率，這是由于算法會(huì)將遷移虛擬機(jī)重新部署至短期未來(lái)不會(huì)變?yōu)槌d的主機(jī)上，而不是僅考慮主機(jī)當(dāng)前時(shí)刻不是超載，這說(shuō)明K最近鄰回歸預(yù)測(cè)是有效可行的。此外，UP-BFD算法可以從當(dāng)前超載和預(yù)測(cè)超載主機(jī)上進(jìn)行虛擬機(jī)遷移，前瞻性地避免了SLA違例機(jī)會(huì)。圖5顯示本文提出的UP-BFD算法能夠比其它算法總體降低約28%的能耗，這是由于該算法可以通過(guò)將虛擬機(jī)裝箱至高負(fù)載主機(jī)上的方式最小化活躍主機(jī)數(shù)量，進(jìn)而優(yōu)化了能耗。圖6顯示了隨機(jī)負(fù)載條件下虛擬機(jī)合并過(guò)程中出現(xiàn)的虛擬機(jī)遷移量。UP-BFD算法由于更好的資源利用預(yù)測(cè)，比對(duì)比算法更好減少了虛擬機(jī)遷移量。

圖4 隨機(jī)負(fù)載下的SLA違例

圖5 隨機(jī)負(fù)載下的能耗

圖6 隨機(jī)負(fù)載下的虛擬機(jī)遷移量

第二個(gè)實(shí)驗(yàn)運(yùn)行現(xiàn)實(shí)負(fù)載對(duì)算法性能進(jìn)行評(píng)估。實(shí)驗(yàn)中每臺(tái)虛擬機(jī)上隨機(jī)分配一個(gè)負(fù)載流。圖7顯示UP-BFD算法比4種對(duì)比算法具有更低的SLA違例，這是由于UP-BFD算法通過(guò)主機(jī)和虛擬機(jī)的資源利用預(yù)測(cè)可以防止SLA的違例，確保了遷移的目標(biāo)主機(jī)在虛擬機(jī)遷移后不會(huì)再次變?yōu)槌d主機(jī)。圖8顯示UP-BFD算法在現(xiàn)實(shí)負(fù)載下比其它算法也節(jié)省了更多的能耗，這是由于該算法通過(guò)裝箱虛擬機(jī)至更少量主機(jī)上，并釋放了最低載主機(jī)，降低了能耗。同樣地，在圖9中，本文的UP-BFD算法也擁有最少的虛擬機(jī)遷移量，這是由于算法可以根據(jù)未來(lái)的資源利用率將遷移虛擬機(jī)進(jìn)行重新部署，而大大降低了目標(biāo)主機(jī)最次出現(xiàn)超載的概率，帶來(lái)不必要遷移的可能。

圖7 現(xiàn)實(shí)負(fù)載下的SLA違例

圖8 現(xiàn)實(shí)負(fù)載下的能耗

圖9 現(xiàn)實(shí)負(fù)載下的虛擬機(jī)遷移量

綜合兩個(gè)實(shí)驗(yàn)結(jié)果來(lái)看，本文算法在實(shí)現(xiàn)虛擬機(jī)合并過(guò)程中較好實(shí)現(xiàn)了能耗與SLA違例間的均衡。同時(shí)，若門限值取值較大，虛擬機(jī)遷移量和SLA違例會(huì)有所提高，但UP-BFD算法在門限值接近于100%時(shí)仍然完成了更好的能耗節(jié)省。

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

云數(shù)據(jù)中心中，動(dòng)態(tài)的虛擬機(jī)合并和遷移雖然可以有效降低能耗和提高資源利用率。然而，若僅考慮當(dāng)前資源利用率會(huì)帶來(lái)許多非必要的虛擬機(jī)遷移，增加SLA違例風(fēng)險(xiǎn)。提出了一種動(dòng)態(tài)的虛擬機(jī)合并算法，算法可以通過(guò)K最近鄰回歸方法預(yù)測(cè)主機(jī)和虛擬機(jī)的資源利用率，從而減少非必要的虛擬機(jī)遷移，并降低SLA違例風(fēng)險(xiǎn)。在虛擬機(jī)遷移選擇上，算法可以通過(guò)預(yù)測(cè)模型從當(dāng)前的超載和預(yù)測(cè)超載主機(jī)上進(jìn)行虛擬機(jī)遷移。通過(guò)大規(guī)模的仿真實(shí)驗(yàn)對(duì)比，驗(yàn)證所提算法不僅可以降低主機(jī)能耗，還可以同步最小化SLA違例和虛擬機(jī)遷移量。