基于改進(jìn)虛擬機(jī)整合算法的虛擬資源管理工具

趙長名，劉 健，李云繼

（1. 電子科技大學(xué)通信與信息工程學(xué)院 成都 611731；2. 北京科技大學(xué)通信與信息工程學(xué)院 北京 海淀區(qū) 100083；3. 貴州理工學(xué)院電氣工程學(xué)院 貴陽 550003）

基于改進(jìn)虛擬機(jī)整合算法的虛擬資源管理工具

趙長名1，劉 健2，李云繼3

（1. 電子科技大學(xué)通信與信息工程學(xué)院 成都 611731；2. 北京科技大學(xué)通信與信息工程學(xué)院 北京 海淀區(qū) 100083；3. 貴州理工學(xué)院電氣工程學(xué)院 貴陽 550003）

提出了一種基于分段迭代相關(guān)性整合（SICC）的虛擬機(jī)整合與放置策略，并將它作為云資源管理工具的核心結(jié)構(gòu)。SICC算法整合了時間序列分析、線性相關(guān)性分析和傳統(tǒng)的FFD算法，并基于虛擬機(jī)的最小資源利用率建立了一套新的虛擬機(jī)動態(tài)資源整合理論。數(shù)值仿真結(jié)果表明，在虛擬機(jī)整合過程中，新的基于SICC的架構(gòu)在使用不同的初始動態(tài)條件時，以虛擬機(jī)為粒度的物理資源利用率性能提升3%～20%；在以服務(wù)器為粒度的物理資源利用率性能提升超過5%。

動態(tài)資源整合； FFD算法； 線性相關(guān)性分析； 虛擬機(jī)

虛擬機(jī)整合技術(shù)（VM consolidation， VMC）通常被用于釋放和回收虛擬機(jī)中的碎片化虛擬資源。這項技術(shù)在概念上類似于虛擬機(jī)遷移，但相比之下VMC更強(qiáng)調(diào)虛擬機(jī)內(nèi)的預(yù)留資源整合。當(dāng)前的VMC算法主要分為靜態(tài)整合算法和動態(tài)整合算法兩類。其中靜態(tài)算法因為靜態(tài)參數(shù)模型而得名，一些靜態(tài)模型常常被簡化為具有低操作開銷和高全局優(yōu)化性能的bin-packing模型。但在資源利用率處于高動態(tài)變化的場景中，一旦資源參數(shù)被設(shè)定為VM的峰值資源利用率，靜態(tài)的bin-packing算法就會表現(xiàn)出極差的資源利用率。因此，當(dāng)任務(wù)還需同時要滿足高服務(wù)等級協(xié)議（service-level agreement， SLA）時，靜態(tài)算法就會導(dǎo)致VM群內(nèi)形成大量資源碎片［1-4］。

與此相反，動態(tài)算法支持計算并選定兩臺當(dāng)前資源利用率互補(bǔ)最好的VM進(jìn)行資源整合，從而獲得較好的局部資源整合效果，但其在全局資源整合效率上卻有較大的缺陷［5-7］。文獻(xiàn)［8］提出了一種精確反映VM資源利用率互補(bǔ)程度的方案。該方案采用了時間序列分析和皮爾遜相關(guān)系數(shù)公式等回歸統(tǒng)計工具，在歷史統(tǒng)計數(shù)據(jù)的基礎(chǔ)上對虛擬機(jī)未來資源利用率進(jìn)行精確的預(yù)測計算和互補(bǔ)性測試，從而能對VM未來的資源整合提供依據(jù)。但這個方案仍然有一個明顯的缺陷：任意一個VM在算法的整個流程中最多只有一次與其他虛擬機(jī)整合的機(jī)會，許多整合后的VM平均資源利用率仍然較低?；诖?，文獻(xiàn)［9］提出了一種改進(jìn)的算法—iterative correlation match algorithm （CMA）。該算法允許一次整合完成后的整合虛擬機(jī)（CVM）再次參與整合的相關(guān)性計算，而不是直接將CVM從待整合的VM序列中刪除。這樣一些具有高整合潛力的VM就擁有不止一次整合的機(jī)會。但是，該算法仍然有一個明顯的缺陷：即該算法是一種貪婪算法，總是搜尋當(dāng)前具有全局最小相關(guān)系數(shù)的兩臺VM進(jìn)行整合，卻忽略了按VM的資源利用率進(jìn)行全局優(yōu)化調(diào)度。這將會在整合流程的后半部分導(dǎo)致嚴(yán)重的線性規(guī)劃難題。這個缺陷只依靠ICMA并不能得到解決。這是因為現(xiàn)有的動態(tài)整合算法幾乎都是直接利用最小線性相關(guān)系數(shù)啟發(fā)式算法。這些算法所做的改進(jìn)只是單純地盡可能增加算法流程中虛擬機(jī)最小線性相關(guān)整合的次數(shù)，而缺乏對于虛擬機(jī)相關(guān)整合原理的本質(zhì)研究。

本文提出了一種基于SICC的新型虛擬資源整合工具。該工具融合了靜態(tài)和動態(tài)兩種完全不同的虛擬機(jī)整合算法模型，依靠SICC算法將在時域具有高動態(tài)資源特性的初始狀態(tài)虛擬機(jī)（original VMs）轉(zhuǎn)變?yōu)榫哂袦?zhǔn)靜態(tài)資源特性和較高平均資源利用率的整合虛擬機(jī)。接著使用成熟的FFD算法完成這些CVM在數(shù)據(jù)中心物理服務(wù)器中的聚合過程。SICC算法的策略在于：通過一定的算法變化，大幅減小原始VM中過大的資源利用率峰值-均值差值，從而有效地避免在虛擬機(jī)中形成難以利用的資源碎片。

1 系統(tǒng)模型

數(shù)據(jù)中心內(nèi)進(jìn)行相關(guān)VM整合的先決條件是系統(tǒng)能夠準(zhǔn)確地預(yù)測出虛擬機(jī)在未來特定時段內(nèi)的資源利用率。本文使用自回歸滑動平滑模型ARMA對虛擬機(jī)的歷史資源利用率數(shù)據(jù)進(jìn)行處理。但是，這些預(yù)測出的VM資源利用率數(shù)據(jù)并不能直接用于服務(wù)器中的VM相關(guān)性整合運算。這是由相關(guān)整合算法的固有缺陷造成的，相關(guān)細(xì)節(jié)將在后面進(jìn)行討論。

本文提出了一種兩階段策略來完成服務(wù)器中的虛擬機(jī)整合。第一階段利用SICC算法在初始狀態(tài)VM群中完成VM粒度的相關(guān)性整合，整合后的CVM具有資源平均利用率高和資源利用率峰值-均值差小的特點。在策略的第二階段引入適用于靜態(tài)整合的FFD算法將這些CVM重新聚合在服務(wù)器中。

SICC算法本身也可以看作一個兩階段的Bin-Packing過程。本文假定所有VM僅具有CPU一種維度的資源并且包含的資源量也是相等的，稱為標(biāo)準(zhǔn)容量VM，其容量為c。整體策略和SICC算法的流程描述如圖1所示，其中圖1a和圖1b描述了SICC算法的第一階段。在SICC的第一階段，初始狀態(tài)的VM按照峰值資源利用率（peak resource utilization， PRU）的大小分為小型、中型和大型3個級別，分別對應(yīng)的條件為：PRU≤25%、25%

圖1 資源管理工具系統(tǒng)模型

2 SICC算法分析

2.1 皮爾遜線性相關(guān)系數(shù)

采用1 440個數(shù)據(jù)抽樣點模擬一臺VM一天的時間序列，并在此基礎(chǔ)上構(gòu)造一個短相關(guān)模型對未來資源利用率進(jìn)行預(yù)測。一旦能獲取每個VM的未來資源利用率時間序列，就有可能找出當(dāng)前全局最佳互補(bǔ)的VM整合配對。分別代表ARMA模型計算出的兩臺VM在未來一段時間的資源利用率。皮爾遜相關(guān)系數(shù)定義為：

式中，系數(shù)r是一個衡量兩臺VM相關(guān)系數(shù)的基本指標(biāo)，在-1～1之間變動，最好的互補(bǔ)VM整合配對是對應(yīng)于具有全局最小線性相關(guān)系數(shù)的VM整合配對。

2.2 基于可測物理量的相關(guān)系數(shù)特征研究

ICMA這一類基于最小相關(guān)系數(shù)的整合算法有一個重要的缺陷：該系數(shù)只能衡量兩臺或兩臺以上VM間的資源利用率相關(guān)互補(bǔ)關(guān)系。因此，首要目標(biāo)是找出一個或一組基于單個VM的可測物理量來對相關(guān)整合算法的算法效能進(jìn)行描述。在文獻(xiàn)［10］提供的實驗數(shù)據(jù)和結(jié)論的基礎(chǔ)上，首先推導(dǎo)出一個結(jié)論：對于初始狀態(tài)的VM而言，如其中一個具有更大的資源利用率方差，則其在相關(guān)整合算法中具有更高的整合優(yōu)先級。

令Va（b）代表初始狀態(tài)虛擬機(jī)VMa（b）的資源利用率方差，若 Va＞Vb且差值較大，則可以認(rèn)為：

定理 1 當(dāng)系統(tǒng)中初始狀態(tài)的VM數(shù)量足夠多時，對于類似于ICMA的基于線性相關(guān)性的整合算法而言，VMa相對于VMb具有更高的合并優(yōu)先級。

證明：定理1等價于一臺VM的資源利用率曲線包絡(luò)的振幅越大，較振幅較小的VM就有越高的概率在初始VM群中找到合適的VM組成相關(guān)整合系數(shù)足夠小的配對組。建立一個簡化的模型演示VMa和VMb的組合情況。A，B和C代表3種不同的單位步長的特征振幅信號，分別對應(yīng)于1，0和-1。A和C定義為單位步長中明顯大于和小于VM資源利用率平均值的抽樣點，而B代表與VM資源利用率平均值差距不大的抽樣點。利用率序列中A的個數(shù)與C的個數(shù)相等，但少于B的個數(shù)。

令信號B在VMa和VMb中的概率等于 ρ0，信號A和信號C出現(xiàn)的概率相等，則有：

根據(jù)假設(shè)有：

則可以推出：

VMa和VMb的任意步長中，存在9種不同配對關(guān)系：

負(fù)相關(guān)關(guān)系：A-C，C-A，B-B

不相關(guān)關(guān)系：A-B，C-B，B-A，B-C

正相關(guān)關(guān)系：A-A，C-C則VMb任意步長中共有45種可能配對組合，記為以及14種可能的負(fù)相關(guān)組合，記為 LVb。則低14振幅VM的負(fù)相關(guān)整合條件概率為：

同理，VMa中的對應(yīng)參數(shù)為 LVa27和L11Va，則對應(yīng)的負(fù)相關(guān)整合概率為：

則有：

即具有連續(xù)兩個特征振幅的VM有更高的合并優(yōu)先級。

至此證明了資源利用率方差可以作為一個衡量初始狀態(tài)VM整合潛力的重要參數(shù)，并且整合潛力還正相關(guān)于VM的方差。與此同時還發(fā)現(xiàn)初始狀態(tài)VM可以分為兩種基本方差類型：Type I型VM和Type II型VM。其中Type I型VM的方差主要由低頻率高振幅的方差構(gòu)成。而Type II的方差構(gòu)成形式與Type I正好相反。由此，在定理1的基礎(chǔ)上可推導(dǎo)出定理2。

定理 2 在ICMA算法中，Type I類型的VM比Type II類型的VM更可能成為當(dāng)前全局最優(yōu)互補(bǔ)配對的組成部分。

證明：設(shè)：

式中，函數(shù)coeff代表G相關(guān)系數(shù)；Var（VMa）表示Vma的資源利用率方差。a代表VMa的資源利用率抽樣序列，而 S（a，b）代表VM（a，b）的資源利用率抽樣序列。則有：

根據(jù)定理1，可以證明VM（3，4）在ICMA中進(jìn)行整合配對的優(yōu)先概率比VM（1，2）低。則可知兩個Type I VM 進(jìn)行整合配對時有更大的概率成為當(dāng)前全局最優(yōu)的互補(bǔ)配對。但是，由Type II 生成的CVM比由Type I 生成的CVM擁有更大的方差，即Type II VM的持續(xù)整合潛力優(yōu)于Type I VM。這證明ICMA算法中總是選擇全局最小相關(guān)系數(shù)對應(yīng)的虛擬機(jī)對進(jìn)行整合配對并不是一個最優(yōu)的資源整合策略。

2.3 SICC算法分析

首先定義兩個概念，即相關(guān)系數(shù)序列（CCS）和峰值利用率柱狀分布（PUB）對算法效能進(jìn)行衡量。CCS包括了一個VM整合過程中所有按時間序列排列的和整合配對對應(yīng)的相關(guān)系數(shù)。PUB則被用來作為衡量每個VM名義資源利用率的基準(zhǔn)。本節(jié)的首要任務(wù)是建立CVM的峰值資源利用率（PRU）模型，并設(shè)計出一種有效的方法測量相關(guān)系數(shù)對資源利用率的影響。假設(shè)第i個VM的PRU為 Pi，并且第i個VM的資源利用率時間序列為i。則CVM的PRU可以表示為：

圖2 相關(guān)系數(shù)為-0.38的CVM的組合峰值分析

因此并不能直接斷言初始VM的低相關(guān)系數(shù)一定和CVM的低PRU相關(guān)。但另一項研究結(jié)果顯示這兩個參數(shù)是有關(guān)聯(lián)的。這個結(jié)論建立在對10萬個相關(guān)系數(shù)位為負(fù)的VM整合配對實例的數(shù)據(jù)回歸分析的基礎(chǔ)上。研究表明當(dāng)相關(guān)系數(shù)低于-0.5時，生成的CVM的PRU和資源平均利用率的差值變化可以保持在一個相對較小的線性區(qū)域。

該研究的仿真結(jié)果如圖3所示，當(dāng)一對初始狀態(tài)虛擬機(jī)的線性相關(guān)系數(shù)小于-0.5時，其峰值均值差小于8.63%標(biāo)準(zhǔn)VM。一般認(rèn)為，當(dāng)峰值均值差小于10%標(biāo)準(zhǔn)VM時就可以將對應(yīng)的CVM看作為一個靜態(tài)參數(shù)的VM。基于這些分析，可以推導(dǎo)出定理3。

定理 3 當(dāng)兩臺VM整合后的線性相關(guān)系數(shù)小于-0.5時，CVM的PRU滿足：

意味著當(dāng)一個整合配對組的相關(guān)系數(shù)（CC）不大于-0.5時，可以在整合時使用CVM的資源利用率均值代替資源利用率峰值（PRU），從而有效地避免預(yù)留資源浪費。解決了上述問題，可以在整合ICMA-0.5和FFD算法的基礎(chǔ)上設(shè)計SICC算法。

圖3 CVM峰值均值差與相關(guān)系數(shù)的關(guān)系

算法1 ICMA-0.5算法流程

1） 將現(xiàn)有的N個VM/CVM放入待配對序列；

2） 使用ARMA算法生成N×1 440原始數(shù)據(jù)矩陣，并使用式（1）生成N×N 維CC矩陣；

3） 矩陣中搜索coeffmin：

①若coeffmin≤-0.5 且 PRUCVM≤100%，令N=N-1，記錄下當(dāng)前coeffmin，使用新的CVM數(shù)據(jù)更新（N-1）×1 440原始數(shù)據(jù)矩陣和（N-1）×（N-1）CC矩陣；

②若coeffmin≤-0.5 且 PRUCVM＞100%，令coeffmin=1并跳到步驟①；

③若coeffmin＞-0.5，算法結(jié)束。

執(zhí)行上述SICC算法后，虛擬資源管理工具可以方便地再次采用FFD算法將SICC最終生成的CVM聚合到物理服務(wù)器中［11］。

3 仿真性能分析

本文的實驗在不同的方面對SICC算法進(jìn)行評估。實驗使用了195個初始PRU分布在15%～75%的實際VM數(shù)據(jù)。初始PRU的數(shù)據(jù)分布符合實測數(shù)據(jù)常用的假設(shè)，即峰值分布30%上限，標(biāo)準(zhǔn)差分布15%上限［12］。令iμ和iδ分別代表初始狀態(tài)虛擬機(jī)VMi的均值和方差。則實驗中所有初始狀態(tài)虛擬機(jī)VM的平均均值和平均方差大致滿足關(guān)系：

并且，在195個初始狀態(tài)VM中，有17個低容量初始VM、136個中等容量VM和42個高容量VM，分別對應(yīng)于PRU<25%，25%≤PRU≤50%和PRU＞50%。

算法2 SICC算法流程

1） 將初始狀態(tài)的VM分成3個部分：

① 若RU＜25%，將符合條件的VM放入第1部分，并在第1部分內(nèi)運行ICMA-0.5；

② 若25%≤RU≤50%，將符合條件的VM放入第2部分，并在第2部分內(nèi)運行ICMA-0.5；

③ 若RU＞50%，將符合條件的VM放入第3部分，并在第3部分內(nèi)運行ICMA-0.5。

2） 將步驟1）中產(chǎn)生的所有的CVM合并，并再次運行ICMA-0.5。

3） 依次計算步驟2）中各個CVM的PRUCVM。并將這些PRUCVM按順序放入存儲列表中。

4） 逆序排列PRUCVM存儲列表，并運行FFD算法進(jìn)行第2階段整合。

圖4比較了相同初始條件下ICMA算法產(chǎn)生的結(jié)果和SICC第二階段再次整合后的結(jié)果。仿真數(shù)據(jù)表明，第二階段完成后，SICC算法最后剩余的CVM數(shù)量明顯少于ICMA剩余的數(shù)量。并且，SICC產(chǎn)生的CVM在峰值均值差遠(yuǎn)小于ICMA的情況下，平均PRU高出了ICMA相同指標(biāo)13%。結(jié)果證明了SICC能有效地利用FFD帶來的高效的全局整合順序增益。

圖5對SICC的資源管理控制工具在數(shù)據(jù)中心服務(wù)器級別的效能進(jìn)行了研究。使用一種常用的初始假設(shè)條件，即初始狀態(tài)虛擬機(jī)的資源利用率平均值符合30%平均值標(biāo)準(zhǔn)VM資源，標(biāo)準(zhǔn)差為15%標(biāo)準(zhǔn)VM資源。實驗中設(shè)置了3 000臺符合上述假設(shè)的初始狀態(tài)VM，并假設(shè)每臺物理服務(wù)器的CPU資源等效于10臺標(biāo)準(zhǔn)VM的CPU資源。資源管理工具在上述假設(shè)條件下進(jìn)行了100次服務(wù)器級的VM整合及再聚合仿真實驗。圖5指出SICC整合后CVM的平均值為1 274個，只占ICMA整合后CVM數(shù)量的85%。并且1 274個CVM平均需要125個服務(wù)器進(jìn)行聚合，是同等初始條件下ICMA所需服務(wù)器數(shù)量的95%。該仿真證明，這種基于SICC的資源管理工具在提高服務(wù)器資源利用率方面是相當(dāng)有效的。

圖4 初始狀態(tài)VM總量與SICC第二階段完成后的CVM總量對比

圖5 SICC和ICMA的VM整合及服務(wù)器聚合對比實驗

4 結(jié) 論

本文介紹了一種基于SICC算法的新型虛擬資源管理工具。首先，研究了一種動態(tài)相關(guān)整合算法ICMA并指出ICMA的主要缺陷是不合理的VM整合順序。公式化了基于最小相關(guān)系數(shù)的動態(tài)VM整合模型，并分析了這種只基于相關(guān)系數(shù)參數(shù)的策略。研究指出，這種模型不可能在相關(guān)系數(shù)和資源利用率間建立有效的聯(lián)系。隨后，給出了一系列關(guān)于SICC算法優(yōu)點的理論推導(dǎo)，證明其可以通過整合中引進(jìn)對峰值均值差的抑制以及FFD算法達(dá)到改變ICMA算法中不合理整合順序的目的。最后，3個數(shù)值仿真實驗證明SICC算法在抑制CVM峰值、減少CVM數(shù)量和提高CVM資源利用率3個方面非常有效。本文證明了以SICC算法為核心的虛擬資源管理工具比基于ICMA核心的管理工具有更高的資源利用效率。

［1］ GONG W， CHEN Z， YAN J， et al. An optimal VM resource allocation for near-client-datacenter for multimedia cloud［C］//Ubiquitous and Future Network （ICUFN）. Shanghai： IEEE，2014： 249-255.

［2］ PAPAGIANNI C， LEIVADEAS A， PAPAVASSILIOUS S， et al. On the optimal allocation of virtual resources in cloud computing networks［J］. IEEE Transactions on Computers，2013， 62（6）： 1060-1071.

［3］ LIU K， PENG J， LIU W， et al. Dynamic resource reservation via broker federation in cloud service： a fine-grained heuristic-based approach［C］//IEEE Global Communications Conference （GLOBECOM）. ［S.l.］： IEEE， 2014： 2338-2343.

［4］ BELOGLAZOV A， ABAWAJY J， BUYYA R. Energy-aware resource allocation heuristics for efficient management of data centers for cloud computing［J］. Future Generation Computer Systems， 2012， 28（5）： 755-768.

［5］ BUYYA R， RANJAN R， CALHEIROS R N. Intercloud：Utility-oriented federation of cloud computing environments for scaling of application services， algorithms and architectures for parallel processing［J］. Computer Science，2010， 6081： 13-31.

［6］ MENG X， ISCI C， KEPHART J， et al. Efficient resource provisioning in compute clouds via VM multiplexing［C］// The 7th International Conference on Autonomic Computing（ICAC）. New York， USA： ACM， 2010： 11-20.

［7］ VERMA A， DASGUPTA G， NAYAK T K， et al. Server workload analysis for power minimization using consolidation［C］//USENIX Annual Technical Conference.［S.l.］： USENIX Assocoation Berkeley， 2009： 28-28.

［8］ APTE R， HU L， SCHWAN K， et al. Discovering dependencies between virtual machines using cpu utilization［C］//The 2nd Conference On Hot Topics in Cloud Computing （HotCloud）. California， USA： USENIX Assocoation Berkeley， 2010： 17-23.

［9］ WAN J， PAN F， JIANG C. Placement strategy of virtual machines based on workload characteristics［C］//IEEE 26th International Parallel and Distributed Processing Symposium Workshops and PhD Forum （IPDPSW）. ［S.l.］：IEEE， 2012： 1827.

［10］ DINDA P A. The statistical properties of host load［C］// Fourth Workshop on Languages， Compilers， and Run-Time Systems for Scalable Computers. Berlin： Springer Heidelberg， 1998： 1-23.

［11］ MARTELLO S， TOTH P. Knapsack problems： Algorithms and computer implementations［M］. New York， USA： Wiley，1990.

［12］ MISHRA A， HELLERSTEIN J L， CIRNE W. Towards characterizing cloud backend workloads： Insights from google compute clusters［J］. ACM Sigmetrics Performance Evaluation Review， 2009， 37（4）： 34-41.

編 輯 葉 芳

Virtualization Resource Management Tool Based on Improved Virtual Machine Consolidation Algorithm

ZHAO Chang-ming1， LIU Jian2， and LI Yun-ji3
（1. School of Communication and Information Engineering， University of Electronic Science and Technology of China Chengdu 611731；2. School of Communication and Information Engineering， University of Science and Technology Beijing Haidian Beijing 100083；3. Faculty of Information Engineering， GuiZhou Institute of Technology GuiYang 550003）

In the paper， we propose a virtual machine （VM） consolidation and placement strategy， named segmentation iteration correlation combination （SICC）. The SICC algorithm integrates several algorithms， such as time series analysis， linear correlation analysis and traditional first fit decreasing （FFD）. A new dynamic resource consolidation theory is then established based on the virtual machine minimum resource utilization parameter. The simulation results indicate that the novel SICC framework can improve the physical resource utilization by 3% to 20% in the VM granularity and by up 5% in the server granularity.

dynamic resource consolidation； FFD algorithm； linear correlation analysis； virtual machine

TN915.01

A

10.3969/j.issn.1001-0548.2016.02.007

2015 - 05 - 16；

2016 - 01 - 18

國家自然科學(xué)基金（61173149）

趙長名（1984 - ），男，博士生，主要從事數(shù)據(jù)中心虛擬化技術(shù)方面的研究.