基于多資源協(xié)同優(yōu)化的虛擬機(jī)整合方法

趙雪陽,岳延奇,王海晨

(長安大學(xué) 信息工程學(xué)院,陜西 西安 710064)

0 引 言

隨著數(shù)據(jù)中心應(yīng)用業(yè)務(wù)日漸增長和規(guī)模不斷擴(kuò)大,能耗顯著增加;同時(shí),云服務(wù)提供商需要保證可靠的服務(wù)質(zhì)量(Quality of Service,QoS),否則將受到懲罰[1]。因此,節(jié)能和保證服務(wù)質(zhì)量是數(shù)據(jù)中心亟待解決的問題。

虛擬機(jī)整合是解決上述問題的重要方法。該方法利用動(dòng)態(tài)虛擬機(jī)遷移來定期合并虛擬機(jī),避免主機(jī)過載引起的性能下降、減少低載主機(jī)數(shù)量從而降低能耗。虛擬機(jī)整合的相關(guān)研究大多[2-7]將虛擬機(jī)整合分解為:過載主機(jī)檢測、欠載主機(jī)檢測、虛擬機(jī)選擇、虛擬機(jī)放置。

在數(shù)據(jù)中心,主機(jī)資源的低利用率會浪費(fèi)資源,而高利用率引起過載,進(jìn)而影響性能[8]。Beloglazov等[9]提出雙靜態(tài)閾值算法,該算法設(shè)置了主機(jī)CPU利用率的過載閾值、欠載閾值,根據(jù)閾值將主機(jī)分為3類。但是,由于云數(shù)據(jù)中心的主機(jī)負(fù)載變化的動(dòng)態(tài)特性,基于靜態(tài)閾值的方法不能很好地適應(yīng)這種動(dòng)態(tài)的變化。為解決該問題,Buyya等[10]提出了兩種穩(wěn)健的統(tǒng)計(jì)估計(jì)來調(diào)整閾值,即中位數(shù)絕對偏差法和四分位距法。Farahnakian等[11]分別使用線性回歸和K近鄰(K-Nearest Neighbor,KNN)回歸算法,根據(jù)從虛擬機(jī)生命周期中收集的數(shù)據(jù)來近似函數(shù),從而預(yù)測過載、低載物理主機(jī)以減少SLA違規(guī)和能源的消耗。在虛擬機(jī)選擇問題上,Jiang等[12]給出了一種包含GPU利用率和CPU利用率兩個(gè)影響因素的能效評價(jià)模型。他們使用基于人工蜂群算法的虛擬機(jī)選擇算法,選定可以使得能耗降低最多的虛擬機(jī)。徐勝超等[13]提出了一種基于皮爾遜系數(shù)的虛擬機(jī)選擇策略,該策略引入了皮爾遜系數(shù),將CPU利用率最高的虛擬機(jī)放入到待遷移虛擬機(jī)列表。在虛擬機(jī)放置階段,能耗感知最適降序(Power-Aware Best Fit Decreasing,PABFD[9])算法在放置虛擬機(jī)時(shí)將虛擬機(jī)遷移到資源利用率高的主機(jī)上,容易導(dǎo)致過度的虛擬機(jī)整合,從而影響服務(wù)質(zhì)量。Murtazaev等[14]提出了Sercon算法,該算法繼承了首次適應(yīng)(First Fit,FF)算法和最佳適應(yīng)(Best Fit,BF)算法的一些屬性,以最小化主機(jī)數(shù)量和遷移次數(shù)。

虛擬機(jī)整合會受到多種資源的約束,其中多種類型的資源相互關(guān)聯(lián)、約束[15],使得同時(shí)保持所有資源類型的高利用率變得困難,可能導(dǎo)致不同資源利用失衡和過載風(fēng)險(xiǎn)。針對該問題,該文提出了基于多資源協(xié)同優(yōu)化的虛擬機(jī)整合(Multi-Resource Collaborative Optimization-based Virtual Machine Consolidation,MRCO-VMC)方法。使用基于正態(tài)分布的多資源過載檢測算法篩選出數(shù)據(jù)中心的過載主機(jī);利用基于正態(tài)分布的最小遷移時(shí)間虛擬機(jī)選擇算法選出過載主機(jī)中待遷移的虛擬機(jī);采用基于正態(tài)分布的能耗感知最適降序算法將虛擬機(jī)從源主機(jī)遷移到目的主機(jī);最后,采用貪心策略將運(yùn)行物理主機(jī)數(shù)量進(jìn)行收縮。經(jīng)仿真實(shí)驗(yàn)驗(yàn)證,在虛擬機(jī)整合中,該方法有效地減少了遷移次數(shù)、減少了能耗并提高了服務(wù)質(zhì)量,取得了較好的結(jié)果。

1 虛擬機(jī)整合問題描述

1.1 虛擬機(jī)放置問題描述

(1)

(2)

此時(shí),虛擬機(jī)放置滿足公式(3)所示的約束條件,即主機(jī)上的全部虛擬機(jī)的各類資源需求總量不能超過該主機(jī)的相應(yīng)的各類資源的總量,并且每臺虛擬機(jī)只能放置到一個(gè)物理主機(jī)上。

(3)

1.2 基于正態(tài)分布的主機(jī)負(fù)載模型

虛擬機(jī)所需資源來源于用戶向云數(shù)據(jù)中心提交的任務(wù)請求,這些請求是隨機(jī)的,這導(dǎo)致虛擬機(jī)的資源需求是動(dòng)態(tài)變化的;物理主機(jī)的負(fù)載是其上虛擬機(jī)的所有資源的總和,隨著虛擬機(jī)需求資源的變化,主機(jī)負(fù)載也隨之變化。由于云數(shù)據(jù)中心負(fù)載的動(dòng)態(tài)特性,很難準(zhǔn)確地對物理主機(jī)負(fù)載進(jìn)行預(yù)測。但有研究表明,虛擬機(jī)的資源利用率服從正態(tài)分布[16]。因此,該文采用正態(tài)分布模型估計(jì)虛擬機(jī)的資源利用率,計(jì)算虛擬機(jī)處于資源利用平衡狀態(tài)的概率。

(4)

(5)

(6)

(7)

(8)

(9)

在虛擬機(jī)放置過程中,如何快速高效地識別虛擬機(jī)遷移所涉及的源主機(jī)和目標(biāo)主機(jī)是首先要解決的關(guān)鍵問題。根據(jù)虛擬機(jī)資源利用率的歷史記錄,并且通過公式(7)～公式(9)計(jì)算f(hj)的值,如果從一個(gè)物理主機(jī)遷出虛擬機(jī)或向其部署虛擬機(jī)后的下一個(gè)虛擬機(jī)整合周期中f(hj)的值較高,則優(yōu)先選擇該物理主機(jī)作為源主機(jī)或目標(biāo)主機(jī),因此f(hj)可以作為一個(gè)量化指標(biāo)來指導(dǎo)待遷移虛擬機(jī)的選擇和放置。

2 基于多資源協(xié)同優(yōu)化的虛擬機(jī)整合

2.1 過載主機(jī)檢測算法

物理主機(jī)過載是導(dǎo)致云數(shù)據(jù)中心服務(wù)質(zhì)量下降的主要原因之一,在虛擬機(jī)整合中預(yù)測主機(jī)的負(fù)載,從而減少避免主機(jī)過載的情況,將有利于服務(wù)質(zhì)量的提升。該文提出了一種基于正態(tài)分布的多資源過載檢測(Normal Distribution-based multi-resource Overload Host Detection,NDOHD)算法來檢測過載主機(jī)。NDOHD算法時(shí)間復(fù)雜度為O(|H|),|H|為需要過載檢測的主機(jī)數(shù)量。

NDOHD算法步驟如下:

(1)給定過載主機(jī)hi;

(2)根據(jù)物理主機(jī)中多維資源負(fù)載的歷史數(shù)據(jù),使用式(4)、式(5)為每個(gè)虛擬機(jī)建立正態(tài)分布模型;

2.2 虛擬機(jī)選擇算法

該文將云數(shù)據(jù)中心虛擬機(jī)資源利用率服從正態(tài)分布的特點(diǎn)與MMT算法結(jié)合,提出基于正態(tài)分布模型的最小遷移時(shí)間虛擬機(jī)選擇(Normal Distribution Model-based Minimum Migration Time,NDMMMT)策略。在選擇待遷移虛擬機(jī)時(shí),必須充分考慮虛擬機(jī)內(nèi)存的大小,因?yàn)樘摂M機(jī)遷移會導(dǎo)致虛擬機(jī)宕機(jī),虛擬機(jī)內(nèi)存越大,對云數(shù)據(jù)中心的QoS產(chǎn)生的負(fù)面影響越大,所以盡量選擇內(nèi)存較小的虛擬機(jī)遷移。

具體計(jì)算公式如下:

vmi∈VMhj∣?a∈VMhj

(10)

NDMMMT算法步驟如下:

(1)輸入過載主機(jī)hover;

(2)對hover中每個(gè)虛擬機(jī)vmi執(zhí)行以下步驟;

(3)計(jì)算選擇虛擬機(jī)vmi的優(yōu)先級priority,如式(11)所示,如果該值大于前一虛擬機(jī)的值,則更新待遷移虛擬機(jī)vmMig;

(11)

(4)循環(huán)結(jié)束后,得到待遷移的虛擬機(jī)vmMig。

2.3 虛擬機(jī)放置算法

虛擬機(jī)放置算法也被稱為虛擬機(jī)映射或分配策略。在選擇完要遷移的虛擬機(jī)之后,整合的最后一個(gè)階段是為當(dāng)前選定的待遷移虛擬機(jī)集合找到最佳的目標(biāo)主機(jī)。為了確保遷移后不影響目標(biāo)主機(jī)的穩(wěn)定性,需要根據(jù)物理主機(jī)中未分配的資源數(shù)量和每臺主機(jī)處于資源均衡利用的概率選擇目標(biāo)主機(jī)。

在PABFD算法的基礎(chǔ)上,結(jié)合NDOHD檢測算法,該文提出了ND-PABFD算法。該算法在PABFD算法的基礎(chǔ)上結(jié)合了多資源協(xié)同優(yōu)化。首先,將所有待遷移虛擬機(jī)按照CPU資源請求量進(jìn)行降序排列。其次,為虛擬機(jī)匹配物理主機(jī),并根據(jù)公式(12)計(jì)算虛擬機(jī)需要選擇的物理主機(jī)的優(yōu)先級;最后,選擇優(yōu)先級最高的物理主機(jī)放置虛擬機(jī)。重復(fù)以上步驟,直到所有的虛擬機(jī)都被放置到合適的目標(biāo)物理主機(jī)上。ND-PABFD的算法復(fù)雜度為O(|Ha|·|VMa|)。

ND-PABFD算法步驟如下:

(1)非過載主機(jī)集合Ha、待遷移虛擬機(jī)VMa作為輸入;

(2)遷移虛擬機(jī)按照CPU資源請求量進(jìn)行降序排列;

(3)while vmi∈vmList,執(zhí)行步驟(4)～(5);

(4)遍歷所有主機(jī)hi,根據(jù)式(12)計(jì)算主機(jī)對應(yīng)的PRI(vmi,hj),選擇PRI(vmi,hj)最大值相應(yīng)主機(jī)allocationHost作為vmi放置的主機(jī):

(12)

(5)將(vmi,allocationHost)放入虛擬機(jī)映射集合allocation;

(6)輸出虛擬機(jī)映射集合allocation。

2.4 活動(dòng)主機(jī)規(guī)模收縮

由于云數(shù)據(jù)中心負(fù)載的不確定性,虛擬機(jī)放置完成后,云計(jì)算中心的部分主機(jī)上可能會出現(xiàn)負(fù)載不足的情況,必須將低負(fù)載物理主機(jī)上的所有虛擬機(jī)遷移出去并休眠該主機(jī)。

首先,選擇出與其他主機(jī)相比利用率最低的主機(jī),并嘗試將此物理主機(jī)上的虛擬機(jī)放置在其他物理主機(jī)上,同時(shí)避免目標(biāo)主機(jī)過載。如果可以完成此操作,則將虛擬機(jī)設(shè)置為遷移到確定的目標(biāo)主機(jī),并在所有遷移完成后將源主機(jī)切換到休眠模式。如果源主機(jī)上的所有虛擬機(jī)都無法放置到其他物理主機(jī)上,則將該物理主機(jī)保持活動(dòng)狀態(tài)。未被視為過載的主機(jī)則會重復(fù)此過程。

2.5 基于多資源協(xié)同優(yōu)化的虛擬機(jī)整合策略

結(jié)合前文提出的NDOHD、NDMMMT、ND-PABFD算法以及活動(dòng)主機(jī)規(guī)模收縮過程,提出了MRCO-VMC方法。MRCO-VMC策略的工作步驟如下:首先,該策略采用NDOHD算法計(jì)算運(yùn)行中物理主機(jī)過載的概率,形成過載主機(jī)集合;其次,使用NDMMMT算法從過載的物理主機(jī)中選擇向外遷移虛擬機(jī),直到該主機(jī)上的負(fù)載降低到過載閾值以下,并將待遷移的虛擬機(jī)添加到向外遷移虛擬機(jī)集合中;第三,利用ND-PABFD算法為向外遷移的虛擬機(jī)找到合適的目標(biāo)主機(jī),即滿足向外遷移虛擬機(jī)的資源需求和虛擬機(jī)放置后虛擬機(jī)的低過載風(fēng)險(xiǎn)需求的目標(biāo)主機(jī);最后,選擇負(fù)載最低的物理主機(jī),將其所有的虛擬機(jī)移動(dòng)到合適的目標(biāo)主機(jī)上,并休眠該物理主機(jī),直到所有低載物理主機(jī)都被關(guān)閉為止,其偽代碼見算法1。

算法1:MRCO-VMC算法。

1 Input:hostList

2 Output:Map〈host,vm〉

3 //過載檢測

4 for eachhjin hostList

5 if NDOHD(hj) is true then

6 將hj加入過載主機(jī)集overHostList

7 end if

8 end for

9 //虛擬機(jī)選擇

10 for eachhjin overHostList

11 While NDOHD(hj) is true do

12 NDMMMT(hj)

13 vmMigrateList←vm

14 end while

15 end for

16 //虛擬機(jī)放置

17 ND-PABFD算法輸入:過載主機(jī),待遷移虛擬機(jī)

18 使用貪心策略,關(guān)閉低載主機(jī)

19 return 虛擬機(jī)與主機(jī)映射關(guān)系Xm*n

3 仿真實(shí)驗(yàn)

3.1 實(shí)驗(yàn)環(huán)境配置

該文使用虛擬機(jī)整合的主要仿真平臺CloudSim模擬云計(jì)算環(huán)境進(jìn)行仿真。實(shí)驗(yàn)中使用的數(shù)據(jù)集來源于CoMon項(xiàng)目中PlabetLab平臺,其擁有超1 000臺虛擬機(jī)在10天運(yùn)行的負(fù)載記錄。模擬的數(shù)據(jù)中心有800臺物理主機(jī),為CloudSim提供的HP ProLiant ML110 G4和HP ProLiant ML110 G5;虛擬機(jī)參考Amazon Ec2,共四類:High-CPU medium、Extra large、Small、Micro[9-10]。

3.2 評估指標(biāo)

采用文獻(xiàn)[10]中的指標(biāo)作為算法的評估標(biāo)準(zhǔn),包括能源消耗(EC)、服務(wù)等級協(xié)議違背率(SLAV)以及二者組成的指標(biāo)ESV,遷移引發(fā)的服務(wù)質(zhì)量下降(PDM)、活動(dòng)物理主機(jī)的平均等級協(xié)議違背率(SLATAH)。

3.3 MRCO-VMC策略性能分析

為了驗(yàn)證提出虛擬機(jī)整合策略的效果,選擇了Beloglazov和Buyya教授放置在CloudSim中的三種基準(zhǔn)算法[10]。三種算法所采用的過載主機(jī)檢測方法分別是:四分位距(Inter Quartile Range,IQR)、局部回歸(Local Regression,LR)以及絕對中位差(Median Absolute Difference,MAD)。文獻(xiàn)[10]還介紹了三種虛擬機(jī)選擇算法,分別為最少遷移時(shí)間算法(MMT)、隨機(jī)選擇算法(RS)、最大相關(guān)性系數(shù)算法(MC)。此外,CloudSim中又新增了最小利用率(MU)方法,該方法的思想是遷移對象為CPU利用率最小的虛擬機(jī)。通過對上文介紹的算法進(jìn)行組合,選擇了IQR-MMT、LR-RS、MAD-MU(對比算法)三種算法。根據(jù)“控制變量法”思想,將MRCO-VMC策略與對比算法在各個(gè)指標(biāo)上進(jìn)行比較。

能耗指標(biāo)反映的是云數(shù)據(jù)中心電能消耗的情況,其值越小代表虛擬機(jī)整合算法產(chǎn)生的能耗越少。由圖1可知,MRCO-VMC算法具有最低的能耗值,LR-RS算法次之,MAD-MU消耗的電能最多,而MRCO-VMC算法比對比算法中平均能耗最低的LR-RS算法還要低36.66%。由此看出,MRCO-VMC算法在降低能耗方面效果顯著。

圖1 EC指標(biāo)平均值對比

SLAV指標(biāo)代表服務(wù)水平協(xié)議違背率,它既表示由于過度利用物理主機(jī)而產(chǎn)生的SLA違規(guī),也表示由于遷移虛擬機(jī)而產(chǎn)生的SLA違規(guī),其值越低表示云計(jì)算中心服務(wù)質(zhì)量越好。由圖2可知,MRCO-VMC算法的平均服務(wù)等級協(xié)議違背率處于較低的水平,低于其他對比算法,IQR-MMT算法次之,LR_RS算法的SLAV指標(biāo)最高,且MRCO-VMC算法的SLAV指標(biāo)與IQR-MMT算法相比平均下降了64.1%。由此可知,MRCO-VMC算法的SLAV性能最好,服務(wù)質(zhì)量提升最高。

圖2 SLAV指標(biāo)平均值對比

由于SLAV指標(biāo)是將PDM和SLATAH這兩項(xiàng)指標(biāo)綜合評定之后云數(shù)據(jù)中心的整體服務(wù)質(zhì)量,所以有必要對PDM和SLATAH這兩項(xiàng)指標(biāo)做出更深入的剖析。SLATAH指標(biāo)是指由于活動(dòng)物理主機(jī)運(yùn)行時(shí)過載給服務(wù)質(zhì)量帶來的下降率。虛擬機(jī)整合過程中物理主機(jī)越少則SLATAH指標(biāo)越小。由圖3可知,MRCO-VMC算法的SLATAH指標(biāo)最低,IQR-MMT算法和LR-RS算法次之,MAD-MU算法的指標(biāo)值最高,這主要是因?yàn)镮QR-MMT算法、LR-RS算法和MAD-MU算法在虛擬機(jī)整合時(shí)無法預(yù)測工作負(fù)載趨勢,更容易導(dǎo)致物理主機(jī)過載,服務(wù)質(zhì)量下降。由此可知,MRCO-VMC算法降低了活動(dòng)物理主機(jī)過載的概率,保障了服務(wù)質(zhì)量。PDM指標(biāo)是指虛擬機(jī)整合過程中受到的虛擬機(jī)遷移次數(shù)和持續(xù)時(shí)間的影響,通常情況下,虛擬機(jī)遷移次數(shù)越少、遷移時(shí)間越短,PDM越低,即虛擬機(jī)遷移對云數(shù)據(jù)中心的服務(wù)質(zhì)量的負(fù)面影響越小。當(dāng)選擇遷移虛擬機(jī)時(shí),MRCO-VMC算法綜合考慮了使遷移時(shí)間最小化的因素,它的最終目標(biāo)是最大化物理主機(jī)處于資源均衡利用狀態(tài)的概率,防止物理主機(jī)超載,虛擬機(jī)遷移更少,圖5也驗(yàn)證了該算法遷移次數(shù)相比較少。因此,MRCO-VMC算法的PDM指標(biāo)值要低于其他三種對比算法,如圖4所示。

圖3 SLATAH指標(biāo)平均值對比

圖4 PDM指標(biāo)平均值對比

虛擬機(jī)在遷移時(shí)會被迫停止服務(wù),因此需要盡量減少虛擬機(jī)的遷移次數(shù)。VMMs表示虛擬機(jī)整合過程中的遷移總次數(shù),它的值越小說明相應(yīng)的虛擬機(jī)整合策略對服務(wù)質(zhì)量的影響越小。由圖5可知,MRCO-VMC算法的虛擬機(jī)遷移次數(shù)遠(yuǎn)遠(yuǎn)低于其他三種對比算法,其次是LR-RS算法和IQR-MMT算法,MAD-MU算法的虛擬機(jī)遷移次數(shù)最多。這是由于MRCO-VMC算法利用正態(tài)分布模型估計(jì)云數(shù)據(jù)中心處于多資源均衡利用狀態(tài)的概率,平衡了各種資源的工作負(fù)載,有效避免了物理主機(jī)頻繁過載的風(fēng)險(xiǎn),同時(shí),避免了不必要的虛擬機(jī)遷移。

圖5 虛擬機(jī)遷移次數(shù)平均值對比

ESV指標(biāo)是在服務(wù)質(zhì)量和能量消耗之間平衡的組合度量,ESV的值越低說明對應(yīng)的算法綜合性能越好。與其他三種方法相比,MRCO-VMC算法引起的SLAV和消耗的電能較少,從而降低了ESV。如圖6所示,MRCO-VMC策略的ESV的值最低,且該策略的值要遠(yuǎn)低于對比算法,說明該策略在保證服務(wù)質(zhì)量、降低能耗方面表現(xiàn)較好,其次是IQR-MMT算法和LR-RS算法,ESV值最高的是MAD-MU算法。

圖6 ESV平均值對比

4 結(jié)束語

為解決主機(jī)多資源利用不平衡引起的數(shù)據(jù)中心能耗增加、服務(wù)質(zhì)量下降,該文提出了一種基于多資源協(xié)同優(yōu)化的虛擬機(jī)整合策略(MRCO-VMC)。該策略根據(jù)虛擬機(jī)的資源利用率呈現(xiàn)正態(tài)分布的特點(diǎn),采用正態(tài)分布模型估計(jì)虛擬機(jī)的資源利用率,計(jì)算物理主機(jī)處于資源利用平衡狀態(tài)的概率;使用基于正態(tài)分布的多資源過載檢測算法預(yù)測物理主機(jī)過載的概率,篩選出數(shù)據(jù)中心的過載主機(jī);基于正態(tài)分布的最小遷移時(shí)間虛擬機(jī)選擇算法通過結(jié)合云數(shù)據(jù)中心虛擬機(jī)資源利用呈正態(tài)分布的特點(diǎn)和MMT算法,選取待遷移的虛擬機(jī);基于正態(tài)分布的能耗感知最適降序算法將PABFD算法與正態(tài)分布模型相結(jié)合,將虛擬機(jī)從源主機(jī)遷移到目的主機(jī);最后,采用貪心策略將運(yùn)行物理主機(jī)數(shù)量進(jìn)行收縮。

基于真實(shí)虛擬機(jī)負(fù)載數(shù)據(jù)進(jìn)行仿真實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果表明MRCO-VMC能夠有效地減少虛擬機(jī)遷移次數(shù)、提升系統(tǒng)服務(wù)質(zhì)量。由于實(shí)驗(yàn)環(huán)境的局限性,該文僅在CloudSim仿真平臺上進(jìn)行了對比實(shí)驗(yàn),無法保證其在真實(shí)實(shí)驗(yàn)環(huán)境中的效率,在未來工作中將進(jìn)行更多仿真實(shí)驗(yàn),評估提出的方法在實(shí)際負(fù)載中的性能表現(xiàn)。