(紹興職業(yè)技術(shù)學(xué)院, 浙江 紹興 312000)

0 引言

近年來隨著網(wǎng)絡(luò)帶寬的提高及通信流量成本的降低，各類大型IT企業(yè)都已經(jīng)逐步建立了自己的基于云的大數(shù)據(jù)中心，其消耗的電力能源也與日俱增，政府與企業(yè)都在開始研究云數(shù)據(jù)中心的低能耗問題，倡導(dǎo)低碳環(huán)保生活與綠色云計算[1-3]。云數(shù)據(jù)中心的虛擬機遷移策略是目前提高云端資源利用效率和降低能量消耗的主要技術(shù)，它能夠?qū)?yīng)用服務(wù)封裝在虛擬機之中，在服務(wù)請求減少的情況下，將云端的多個虛擬機遷移到一個物理服務(wù)器，關(guān)閉空閑服務(wù)器或者使空閑服務(wù)器進(jìn)入睡眠模式[4-7]；當(dāng)服務(wù)請求增加時，重新喚醒空閑服務(wù)器[8]。

目前學(xué)術(shù)界利用云端的虛擬機遷移策略來節(jié)省云端的能源消耗,進(jìn)行了大量的研究。虛擬機遷移早期的技術(shù)有預(yù)復(fù)制Pre-copy,后復(fù)制post-copy,混合復(fù)制等, 這些主要是應(yīng)用在單虛擬機遷移領(lǐng)域(single virtual machine migration)或者非云端的虛擬機遷移。隨著云端服務(wù)規(guī)模的擴大，目前大多都是多虛擬機遷移模式[9-11]。Luo等人[12]從CPU維度對虛擬機的動態(tài)配置問題進(jìn)行建模，并利用改進(jìn)的蛙跳算法進(jìn)行求解。Xu[13]等人提出了PS-ABC算法，該方法能夠在長期服務(wù)項目的局部時間段內(nèi)實現(xiàn)較好節(jié)能效果，但是在服務(wù)項目全局的能耗優(yōu)化問題上，效果并不理想。Zhao等人[14]在此基礎(chǔ)上提出了PS-ES啟發(fā)式算法，不僅實現(xiàn)了當(dāng)前場景的能源優(yōu)化，而且也有效降低了長期服務(wù)項目總體的能源消耗，但其考慮的維度較單一。Cao等人[15]在Beloglazov研究的基礎(chǔ)上提出SLA違規(guī)算法，引入最小能源最大利用率策略，進(jìn)一步優(yōu)化虛擬機配置方法; 上述這些方法的主要目的是應(yīng)用虛擬機動態(tài)遷移技術(shù)實現(xiàn)云端服務(wù)的負(fù)載均衡，容錯,優(yōu)化服務(wù)器的電力能量管理等,最終是為了改善云端的服務(wù)質(zhì)量QoS,減少SLA違規(guī), 但是考慮的物理資源使用情況的維度比較少，例如只考慮CPU或者內(nèi)存情況，沒有考慮網(wǎng)絡(luò)帶寬及虛擬機本身的資源需求等情形。

總體來說云計算環(huán)境下的虛擬機的遷移優(yōu)化問題可以被描述為類似多維裝箱的問題，即將物理服務(wù)器抽象為箱子，箱子的容量是服務(wù)器資源的大小，包括CPU、內(nèi)存、硬盤和網(wǎng)絡(luò)帶寬；虛擬機抽象為裝入的物品，其所用的資源就是物品的大?。毁Y源的種類被抽象為裝箱問題的維度[21]。此類問題是一個基于多約束的整數(shù)規(guī)劃問題，同時也是一個NP-hard問題，唯一和裝箱問題不同的是，該裝箱問題是處于動態(tài)變化之中，即當(dāng)前的物品裝箱狀態(tài)是基于前一次的狀態(tài)，因此，還需要優(yōu)化物品的移動成本。根據(jù)以上分析，本文的研究點就轉(zhuǎn)化為基于多約束的多目標(biāo)優(yōu)化問題，并求其近似最優(yōu)解,為此本文提出一種云計算環(huán)境下的虛擬機動態(tài)遷移策略DMS-VM(Dynamic Migration Strategy for Virtual Machine)。

1 問題描述與建模

在云計算環(huán)境下，由于用戶的彈性需求，導(dǎo)致虛擬機中的工作負(fù)載也同樣處于動態(tài)變化之中，為了提高資源利用率，需要利用虛擬機遷移技術(shù)來整合各工作負(fù)載。一般情況下，動態(tài)虛擬機遷移的目標(biāo)主機可能由多個，而且選擇不同的目標(biāo)主機會產(chǎn)生不同的能源消耗，DMS-VM被設(shè)計一種高效節(jié)能的虛擬機遷移策略，使得虛擬機在遷移時能夠被部署在合適的物理服務(wù)器上。如圖1所示，可以將云計算環(huán)境下虛擬機遷移問題描述為：

圖1 虛擬機放置示意圖

考慮云數(shù)據(jù)中心包含m臺同構(gòu)的主機PM={PM1,PM2,……PMm}和n臺虛擬機VM={VM1,VM2,……VMn}，VM有w種類型，同時滿足w

為了實現(xiàn)應(yīng)用的隔離性和虛擬機的有效性，假定每個虛擬機中只運行一種應(yīng)用程序，即將應(yīng)用程序封裝在虛擬機之中，實現(xiàn)虛擬機與應(yīng)用程序一對一的綁定，因此應(yīng)用程序與虛擬機個數(shù)相同，應(yīng)用程序可表示為A={A1,A2,……An}，其中Ai只處理Qesi類型的應(yīng)用請求，根據(jù)Qesi請求量Qi的動態(tài)變化產(chǎn)生不同的負(fù)載占用虛擬機資源的比例表示為ri={ricpu,rimem,ristore,ribw}，因此ri隨著時間的推移也在動態(tài)變化。主機上運行的虛擬機狀態(tài)可表示為(Xij)nxm，Xij值域為{0,1}，當(dāng)Xij=1時，表示在主機PMj上已啟動虛擬機VMi，相反，當(dāng)Xij=0時，表示虛擬機VMi不在主機PMj上。

根據(jù)以上的場景假定和變量的定義，云計算環(huán)境下的虛擬機遷移策略可以抽象為類似多維裝箱的問題，不同點在于每一次的物品裝箱，都要在物品前一次的狀態(tài)基礎(chǔ)上進(jìn)行。因此，建立如下所示的虛擬機遷移模型：

目標(biāo)函數(shù)：

(1)

(2)

式(1)表示執(zhí)行第k次遷移策略之后，啟動的物理主機數(shù)目最少；式(2)表示執(zhí)行第k次遷移策略所移動的虛擬機次數(shù)最少。

約束條件：

(3)

Yj(k) ∈{0,1}表示執(zhí)行第k次遷移策略之后，主機PMj中是否存在運行的虛擬機。如果Yj(k)=0，表示主機PMj中沒有運行的虛擬機，即處于關(guān)機或者待機，相反Yj(k)=1，表示主機PMj中有虛擬機運行，即處于激活狀態(tài)。定義遷移變量如下:

(4)

為了降低遷移的復(fù)雜度，假定每次執(zhí)行遷移操作時，每個虛擬機最多只能遷移一次，即Mi(k)∈{0,1}，Mi(k)=1表示執(zhí)行第k次遷移策略之后，VMi已經(jīng)遷移，相反，Mi(k)=0表示VMi沒有遷移。

(5)

式(5)表示第k次遷移完成之后，PMj沒有超負(fù)荷運行。假定遷移過程中，任何一臺主機不能既遷入虛擬機同時又遷出虛擬機。

2 DMS-VM算法設(shè)計與實現(xiàn)

根據(jù)前面的分析, DMS-VM算法轉(zhuǎn)化為多目標(biāo)優(yōu)化問題. 它一般不存在單一最優(yōu)解，需要從一組非劣解中選擇一個滿意解，因此對于解的滿意選擇就存在一種偏好問題。一種簡單的方法就是引入一個權(quán)重變量將多個目標(biāo)求解轉(zhuǎn)化為單目標(biāo)求解。而遺傳算法是一種模擬自然選擇機制和自然遺傳進(jìn)化過程的計算模型，不僅可以高效地搜索最優(yōu)解，并且其具有的并行性能夠適應(yīng)大規(guī)模組合優(yōu)化問題。因此本節(jié)引入多目標(biāo)遺傳算法求解虛擬機遷移問題。DMS-VM中利用遺傳算法求解的具體步驟如下：

(1)染色體編碼。

染色體編碼的選擇是影響遺傳算法搜索效率和效果的重要因素，其實現(xiàn)的是從問題的解到染色體的映射。根據(jù)模型所示，虛擬機和主機是多對一的關(guān)系，因此，本文運用分組編碼的方式對染色體進(jìn)行編碼，即染色體基因位上數(shù)字表示分組的主機號，每個分組中包含一串子基因，該子基因號表示主機中的虛擬機編號。

(2)種群初始化。

種群初始化是遺傳算法最基本的步驟，本文DMS-VM中遺傳算法求解的是虛擬機動態(tài)遷移問題，種群的初始化需要基于虛擬機和主機遷移前的狀態(tài)，因此，根據(jù)虛擬機編號，隨機產(chǎn)生一組虛擬機序列，按照當(dāng)前染色體編碼、本文約束條件和多維優(yōu)先適應(yīng)的原則，將虛擬機分配到運行的主機中，若運行的主機不滿足約束條件，則將虛擬機分配到編號最小的待機狀態(tài)主機，使主機處于運行狀態(tài)。

(3)適應(yīng)度函數(shù)。

適應(yīng)度函數(shù)Fitness是由目標(biāo)函數(shù)轉(zhuǎn)換而成的，根據(jù)權(quán)重值W，將多目標(biāo)轉(zhuǎn)變單目標(biāo),如公式(6)。

(6)

(4)選擇操作。

本文DMS-VM遺傳算法中的選擇操作為輪盤賭法，即基于適應(yīng)度比例的選擇策略，以此來選擇出合適的個體進(jìn)行后續(xù)的交叉和變異操作，為了防止當(dāng)前群體的最優(yōu)個體在下一代發(fā)生丟失，導(dǎo)致算法不能收斂到全局最優(yōu)解，在選擇操作前，需要保留g個最優(yōu)個體。選擇操作中每個個體xi的選擇概率為Pi：

式中，F(xiàn)i為個體xi的適應(yīng)度值，由于選擇的適應(yīng)度是模型目標(biāo)函數(shù)最小值，因此其值越小越好，所以在個體選擇前對適應(yīng)度值求倒數(shù)，k為系數(shù)，size為種群個體數(shù)目。

(5)交叉操作。

在種群中隨機選擇兩個染色體chromosomei和chromosomej，設(shè)置交叉概率Pc，并對兩個父個體隨機產(chǎn)生交叉位置，將第一個父個體的交叉位基因插入第二個父個體的染色體最前端，刪除第二個父個體中重復(fù)出現(xiàn)的虛擬機及其所在的主機，根據(jù)多維優(yōu)先適應(yīng)的原則，從新分配無主虛擬機，并且在滿足約束條件的前提下，根據(jù)虛擬機遷移數(shù)最小原則，將染色體最前端新插入的基因替換刪除的主機基因，若不滿足約束，則將新基因替換最小編號的空閑主機基因。交叉操作的實例如圖2所示。

圖2 DMS-VM中利用遺傳算法的交叉操作

(6)變異操作。

首先，以較小的概率Pm獲得需要變異的染色體chromosomei，隨機產(chǎn)生一個存在于chromosomei中的整數(shù)M∈ [0,m)，即運行的主機號，將主機中的所有虛擬機按照多維優(yōu)先適應(yīng)的原則進(jìn)行從新分配。

(7)精英保留。

根據(jù)適應(yīng)度函數(shù)，重新計算新種群中個個體適應(yīng)度F={F1,F2,……Fd}，令精英個體適應(yīng)度G={G1,G2,……Gg}，將F和G進(jìn)行混合排序，選取其中最優(yōu)的d個個體作為新一代種群。

3 仿真與結(jié)果分析

3.1 仿真環(huán)境與配置

為了對本文提出的云計算環(huán)境下的虛擬機動態(tài)遷移策略DMS-VM進(jìn)行實驗分析，需要應(yīng)用到大規(guī)模的數(shù)據(jù)中心基礎(chǔ)架構(gòu)， 利用某個企業(yè)的一個大規(guī)模云數(shù)據(jù)中心作為測試環(huán)境，它包括300個空閑的HP ProLiant ML110 G4物理服務(wù)器，這些物理服務(wù)器在執(zhí)行云計算應(yīng)用程序的時候,劃分為虛擬機后的參數(shù)配置如表1所示: 我們把本文的虛擬機遷移策略與已經(jīng)有的MADLVF[16], Buyya[17], Melliti[18]等常見的遷移策略進(jìn)行了比較。比較的性能參數(shù)包括四個: 低負(fù)載服務(wù)器數(shù)量變化情況，虛擬機遷移個數(shù)分析，云數(shù)據(jù)中心能耗分析和SLA的平均違規(guī)分析。

表1 實驗中的虛擬機參數(shù)配置情況

3.2 低負(fù)載的服務(wù)器數(shù)量分析

在測試過程中，當(dāng)整個應(yīng)用的虛擬機的請求數(shù)量增加的時候，4種遷移策略情況下, 那些負(fù)載比較輕的服務(wù)器數(shù)量都隨著增加，這也表明四個虛擬機遷移策略都可以降低負(fù)載比較重的服務(wù)器的工作壓力，把這些負(fù)載遷移到低負(fù)載的服務(wù)器上，而且被增加的這些服務(wù)器的數(shù)量也是緩慢的增加。與其他幾種云計算環(huán)境的虛擬機遷移策略比較起來，本文的DMS-VM遷移策略低負(fù)載的服務(wù)器數(shù)目增加是最緩慢的,整個測試結(jié)果如圖3所顯示。

圖3 4種虛擬機遷移策略的負(fù)載均衡性能比較

3.3 虛擬機遷移次數(shù)分析

圖4顯示了隨著云計算應(yīng)用的虛擬機請求數(shù)量的變化,4種策略比較起來虛擬機遷移后的遷移個數(shù)比較情況。結(jié)果顯示本文的DMS-VM遷移策略隨著虛擬機請求個數(shù)從100到1 000的變化,它的遷移個數(shù)從370到2 000左右,大約只有5.0倍的增加。而其他的三個遷移策略的個數(shù)都是8.0倍以上的增加。

從這個結(jié)果表明, DMS-VM與其它三中策略比較起來，本文的遷移策略能夠有效的減少動態(tài)虛擬機的遷移個數(shù)，這樣它間接就減少了云數(shù)據(jù)中心的能源消耗情況。

圖4 4種虛擬機遷移策略的遷移次數(shù)比較

3.4 云數(shù)據(jù)中心的能耗分析

圖5顯示了隨著云計算應(yīng)用的虛擬機請求數(shù)量的變化, 4種策略比較起來云數(shù)據(jù)中心的電力消耗情況，本文的策略在4種策略中是最節(jié)省能源的,在虛擬機個數(shù)為100的時候，大約只有4千瓦特小時(KWH)的能源消耗。 但是盡管如此, 云數(shù)據(jù)中心的能源消耗還是增加比較快， 這個是因為DMS-VM遷移策略了主要目的是為了使服務(wù)器的負(fù)載虛擬機負(fù)載最小和負(fù)載均衡，在這個過程中就存在一定的虛擬機遷移動作，這樣云數(shù)據(jù)中心的電力的消耗情況也受到了影響。

圖5 4種虛擬機遷移策略的能量消耗比較

3.5 SLA平均違規(guī)分析

云計算中，服務(wù)質(zhì)量QoS必須保證,QoS的衡量標(biāo)準(zhǔn)主要通過服務(wù)等級協(xié)議的SLA Violations(SLA違規(guī))來體現(xiàn)，SLA違規(guī)通過最小的吞吐量或者最大響應(yīng)時間來表示。但是在云計算中針對不同的應(yīng)用，表示方法也不完全一致,為了研究的需要，我們通過公式(7)來表示SLA違規(guī)。

SLAViolations=

(7)

SLA違規(guī)值的百分比將表明在客戶有服務(wù)請求的時候，CPU并沒有分配資源的比例，因此,為了云客戶端增加QoS,我們的首要目標(biāo)是減少SLA違規(guī)的值。圖6顯示了隨著云計算應(yīng)用的虛擬機請求數(shù)量的變化4種策略比較起來云數(shù)據(jù)中心的服務(wù)等級協(xié)議SLA的平均違規(guī)比較情況，結(jié)果表明隨著虛擬機請求數(shù)目的增加，4種策略下的SLA的平均違規(guī)都是隨機的變化，本文的遷移策略處于性能中的中等水平,盡管如此,它的SLA違規(guī)都是比較平穩(wěn)的變化， 這個也表明它可以穩(wěn)定的保證云平臺的QoS。

圖6 4種虛擬機遷移策略的SLA平均誤差率比較

從上面的四個實驗可以看出，DMS-VM虛擬機遷移策略既可以減少能量消耗,也可以使虛擬機均勻的分布到所有的服務(wù)器中，使的云數(shù)據(jù)中心的各個服務(wù)器的負(fù)載均衡,預(yù)防計算資源過于集中和聚集, 和常見的其他策略比較起來，性能處于優(yōu)勢, 這個是因為DMS-VM采用遺傳算法的多目標(biāo)優(yōu)化問題，引入一個權(quán)重變量將多個目標(biāo)求解轉(zhuǎn)化為單目標(biāo)求解,最終求出最滿意的資源放置策略, 從而達(dá)到節(jié)省云數(shù)據(jù)中心的電力消耗與成本。

4 結(jié)論

針對云端的多種應(yīng)用服務(wù)請求處于動態(tài)變化情形下，本文提出了一種云端的虛擬機動態(tài)遷移策略DMS-VM，采用遺傳算法的目標(biāo)優(yōu)化作為虛擬機的主要遷移策略，并運用實驗將本文算法與常見優(yōu)化算法進(jìn)行對比分析。實驗表明DMS-VM能夠有效減少物理主機的使用數(shù)量和虛擬機的遷移次數(shù)，保證QoS質(zhì)量,減少SLA的違規(guī), 降低數(shù)據(jù)中心能耗。未來的工作在虛擬機遷移策略中將考慮物理主機的內(nèi)存大小，網(wǎng)絡(luò)帶寬和空余磁盤空間情況。