云數據中心考慮虛擬機關聯性的虛擬機放置策略

王 輝 張洪瑜 呂書林

(河南廣播電視大學信息技術中心 河南 鄭州 450008)

0 引 言

近年來大規模節能的云數據中心的構造與使用成為政府和各大IT企業越來越重視的問題[1-3]。一個云數據中心通常配置有大量的物理主機(Physical Machines ,PMs)，虛擬化是云數據中心中的關鍵技術。為了節省能量消耗的成本，云服務提供商還采用虛擬機遷移 (VM Migration) 策略來使虛擬機在各個物理服務器上選擇與放置，最終目標是節省云數據中心能量消耗、高服務質量(Quality of Service,QoS)、節省物理空間和高可靠性等。

盡管在虛擬機遷移的過程中可以提高資源使用率，但那些具有高關聯度的虛擬機之間更容易觸發超負載事件。因此,如何防止那些高關聯性的虛擬機在重新分配的過程中被分配到同一個物理節點上是一個關鍵問題。目前已有很多文獻都分析了虛擬機在重新分配中的關聯性相互影響的問題。例如：文獻[4]提出了一個基于干擾模式的最優虛擬機合并模型;文獻[5]提出了基于QoS的控制框架來管理虛擬機在重新分配到物理服務器過程中的相關關系及性能影響,并沒有涉及到虛擬機遷移;文獻[6]提出了關聯性感知的動態能量管理方法，它認為虛擬機之間的關聯度應該是獨立的，而不是采用多個關聯度因素;文獻[7]提出了穩定匹配的虛擬機遷移策略，它將虛擬機選擇和虛擬機放置過程結合起來,可以充分提高物理資源的利用效率,具有一定的優勢。

目前以Anton Beloglazov博士等[9-11]為團隊開發的Cloudsim項目在云數據中心的節能研究方面處于世界領先地位,而且有大量關于Cloudsim項目的后續研究工作，例如基于溫度感知[12]、安全檢測[13]、遺傳算法[14]、貪心算法[15-16]、任務映射[17]、數據依賴[18]、穩定匹配[7]等的虛擬機遷移策略。上述文獻往往把虛擬機遷移過程劃分為物理主機狀態檢測(超負載over-utilized 或 低負載under-utilized)、虛擬機選擇(VM Selection)和虛擬機放置(VM placement)三個步驟。物理主機狀態檢測可以通過監控物理資源使用狀態來判斷，如果CPU的使用率超過90%或者低于10%都可以認為是超負載或者低負載狀態, 在這個時候，該物理主機上運行的虛擬機將被選擇出來，在接下來的步驟中將被放置到另外一個正常狀態的物理節點之上。虛擬機選擇的含義是通過判斷物理主機的運行狀態，然后從中選擇出合適的候選遷移虛擬機列表。虛擬機放置的含義是將虛擬機選擇算法中選擇出來的候選虛擬機列表按照一定的算法盡量均勻地放置到云數據中心其他正常的物理節點上。從這里可以看出Anton Beloglazov博士團隊指出的遷移過程與本文探討的虛擬機放置比較類似,分析虛擬機選擇和虛擬機放置之間的虛擬機關聯性,最終完成新的放置。

本文重點關注虛擬機放置階段，提出了考慮虛擬機關聯性的虛擬機放置策略。該策略可以減少高關聯性的虛擬機在放置過程中被分配到同一個物理節點上的機會,盡量避免物理主機超負載問題。

本文仍然采用Cloudsim項目的性能測試指標與仿真環境，利用真實的工作負載數據，仿真結果表明本文的放置策略相比Cloudsim中普通的虛擬機放置策略，可以更好地節省云數據中心的能量消耗,降低虛擬機遷移次數，減少了SLA違規率,保證了服務質量。

1 工作背景與相關術語

1.1 虛擬機遷移的工作背景

本文涉及的虛擬機遷移過程,具體包括下面三個步驟:

步驟1基于Cloudsim已有的策略周期性地檢測云數據中心的物理主機的超負載或者低負載狀態；

步驟2基于Cloudsim已有的策略完成虛擬機的選擇,形成候選遷移虛擬機列表VmsToMigrationList;

步驟3基于本文提出的考慮虛擬機關聯性辦法完成虛擬機放置操作(虛擬機重新分配)。

由于本文屬于Cloudsim項目的后續研究，所以先指出在Cloudsim項目中已經有的物理主機狀態檢測方法, 常見的包括下面五種,即根據物理資源使用率的使用閾值情況來決定[8]：

1) Local Regression (LR)：局部回歸檢測方法；

2) Local Regression Robust (LRR)：魯棒局部回歸檢測方法；

3) Median Absolute Deviation (MAD)：絕對中位差檢測方法；

4) Static Threshold (THR)：靜態的資源使用效率閾值檢測法；

5)Inter Quartile Range(IQR): 四分位數區間檢測方法。

在步驟2中指出了在CloudSim項目中已經有的虛擬機選擇算法包括下面幾種[8]：

1) Maximum Correlation (MC):最大關聯選擇方法,即選擇同一個物理主機上的,與CPU使用效率有最高關聯度的虛擬機作為對象;

2) Minimum Migration Time (MMT): 最小遷移時間選擇方法，即遷移一個在最短時間內能夠完成的虛擬機作為選擇對象;

3) Minimum Utilization (MU):最小資源使用效率選擇辦法,即對一個具有最小使用效率的虛擬機進行遷移。

4) Random Selection (RS):隨機選擇策略，即在物理主機上隨機選擇一個虛擬機進行遷移。

1.2 虛擬機關聯性的相關術語

采用多重相關系數來評價虛擬機之間的關聯性[19]。假設一個物理主機上面有n個運行的虛擬機Vi,這些虛擬機組成了一個向量V={V1,V2,…，Vn}。

第i個虛擬機針對于其他的n-1個虛擬機的關聯性強度通過最近的q個虛擬機的CPU的使用率的觀察值來測量。假設yi為表示第i個虛擬機的最近的q個CPU的使用率的觀察值的向量,類似地,令X定義為包含物理主機上剩下的n-1個虛擬機的最近的CPU的使用率的q個觀察值構成的增加矩陣。yi和X的表示如下:

(1)

(2)

(3)

1.3 虛擬機遷移的相關術語

1) 物理主機使用效率(host utilization)。物理主機的使用效率體現了云數據中心資源使用狀態，在該情況下,所有的物理主機的平均使用效率計算為：

(4)

式中：ui是當前的物理主機i的CPU使用效率；m是物理主機的數目。

夏、商兩朝都宣揚君主“受命于天”“代天行罰”，濫用刑罰鎮壓臣民的反抗，最后都走上眾叛親離、土崩瓦解的道路。西周初年，以周公為代表的統治者總結前代教訓，深刻認識到“皇天無親”“唯德是輔”，天命與民心息息相關，只有愛護百姓、施行德政，才能獲得上天的垂青。他告誡分封在列國的王室子弟，一定要“明德慎罰”：審判囚犯要多加考慮，反復思量數日乃至十數日再做出判決；對怙惡不悛的累犯必須嚴懲，對悔過自新的初犯可以赦免；殺罰大權要集中，不可隨意委托他人。[1]“明德慎罰”的統治方式在當時取得了良好的效果，史稱“故成康之際，天下安寧，刑錯四十余年不用”。[2]

2) 能源消耗模型(Energy Consumption)。為了計算云數據中心的能源消耗，假設物理主機是空閑的，它的能源消耗的百分比是k,Pfull表示物理主機在完全滿負載工作時的能源消耗，ui是當前的物理主機i的CPU使用率,這樣物理主機的能源消耗公式為:

Ei=k×pfull+(1-k)pfull×ui

(5)

整個云數據中心的能量消耗為：

(6)

3) SLA違規比率(SLA violation)。在云數據中心中，服務質量QoS必須保證,QoS的衡量標準主要通過SLA來體現，本文參考了文獻[9]方法，采用了兩個方法來評價SLA違規：

(1) SLA violation Time per Active Host (SLATAH),單活動主機SLA違規時間;

(2) Performance Degradation due to Migrations(PDM),虛擬機遷移后的性能降低情況。

所以最終SLA違規的具體值計算為:

SLAV=SLATAH×PDM

(7)

式中：SLATAH是活動主機的CPU具有100%的使用率所占的比例；PDM是整個系統因為虛擬機遷移后的性能降低情況。

4) SLA違規與能量消耗聯合指標ESV。能量消耗和SLA違規這兩個指標往往是互相沖突的，如果SLA違規比率過高,表明云數據中心提供服務出現異常，這樣企業將會失去商業利潤。如果使用過多的IT物理資源來保證QoS,能量消耗就會增加,間接地提高了企業的成本,所以本文主要保證能量消耗和QoS之間的平衡。參考Cloudsim中的ESV(Energy and SLA Violations)方法來評價整個云數據中心的性能,ESV的計算公式如下:

ESV=Etotal×SLAV

(8)

2 算法描述

本節重點描述考慮虛擬機關聯性的虛擬機放置算法。前面提到虛擬機遷移過程包括物理主機狀態檢測、虛擬機選擇及虛擬機放置。 本文的遷移模式在主機狀態第一個階段采用了魯棒局部歸約檢測方法來發現處于超負載或者低負載狀態下的物理主機,因為相關的研究實驗結果表明LRR檢測方法性能優于其他LR、MAD、THR、IQR等的檢測方法[9]。LRR方法是一種自適應的主機使用率閾值檢測辦法,它通過檢測一個物理主機的最近J個處理器的使用率值作為評價方法,來判斷該物理主機是否處于超負載或者低負載狀態。本文設J為10。

第二階段,采用最小遷移時間選擇方法來完成虛擬機選擇[9]。在MMT策略下，選取一個在最短時間內能夠完成遷移的虛擬機作為候選遷移對象,形成候選遷移虛擬機列表VmsToMigrationList。文獻[9]指出MMT選擇策略要比Cloudsim項目中提到的其他的MC、MU、RS等策略要優秀。

虛擬機放置階段，本文提出考慮虛擬機關聯性的分配方法。這里提出三類不同的值得參考的關聯性的標準,這些辦法都可以使在第二階段形成的候選的虛擬機列表VmsToMigrationList重新分配到最合適的物理主機上，同時盡量避免物理主機超負載問題。而與Cloudsim項目中的策略比較起來，它們采用的是BPP方法,即最好適應算法(Best-Fit-Algorithm，BFA)、首次適應算法(First-Fit-Algorithm，FFA)、下次適應算法(Next-Fit-Algorithm，NFA)、最壞適應算法(Worst-Fit-Algorithm，WFA)和隨機算法(Random Allocation-Algorithm，RAA)等，來將大量的虛擬機放置到各個數據中心的物理節點完成云計算。為了改進性能，Cloudsim還采用了最好適應遞減裝箱辦法(Best-Fit-Decreasing，BFD),而BFD方法的計算復雜度比較低。下面提出三類虛擬機放置辦法：

1) 考慮遷移虛擬機的關聯性Approach1。在這種方法中，一個候選的虛擬機將被重新分配到新的物理主機上,該新的物理主機上已經存在的虛擬機之間的關聯性是最小的。該關聯性的計算通過式(9)來完成。

(9)

2) 考慮目的主機的平均關聯性級別Approach2。該方法中，一個候選的虛擬機將被重新分配到新的物理主機上,該新的物理主機上的虛擬機將具有最小的平均關聯性級別。一個物理主機的平均關聯性級別計算如下：

(10)

式中：n表示第二階段產生的候選的虛擬機上的數目加上該物理主機上原來已經有的虛擬機數。與考慮遷移虛擬機的關聯性Approach1辦法比較起來，目的主機的平均關聯性級別辦法考慮到了重新分配成功的虛擬機的遷移的影響,而且允許物理主機上有相對大數量的虛擬機存在。它既考慮了物理主機上已經存在的虛擬機的關聯性比較小,也考慮到了將要被遷移上來的虛擬機的關聯性也比較小。

3) 考慮目的主機的關聯性級別變化Approach3。一般來講一個物理主機上的虛擬機之間的關聯度越高，那么該物理主機出現超負載的可能性就越大[20],基于這種考慮，Approach3試圖合并虛擬機,以便每個活動物理主機在所有的候選虛擬機列表中能夠獲得一個比較低的關聯性值，這樣也減少了超負載的風險。直觀來講，那些具有強關聯性的虛擬機應該被放置到不同的物理主機之上才比較合適,一個將要被遷移的虛擬機最好不能被分配到帶有與自己關聯度很大虛擬機的物理主機上,這樣也可以避免目標主機的性能降低。

因此必須針對每個目的主機的總體的關聯性變化情況，以便判斷目的主機虛擬機遷移之后的性能改變情況，該變化的計算方法如下:

(11)

式中：V′表示目的物理主機在沒有接受虛擬機遷移之前其上面存在的虛擬機的向量,在Approach3中，采用具有最小的Approach3的值的物理主機作為再分配物理主機。

Approach1、Approach2、Approach3三個辦法都可以與BFD相結合，最終完成第三階段的虛擬機放置,圖1描述了Approach3考慮虛擬機關聯性的虛擬機放置方法的具體過程與工作機制,Approach1、Approach2都可以按照這個思路進行虛擬機放置。其中：allocatedHost表示一個數組變量，用來存放候選遷移的每一個虛擬機；estimated Approach()表示根據式(11)來計算Approach。

圖1 考慮虛擬機關聯性的虛擬機放置策略

首先,從物理主機狀態檢測過程中初始化可用的物理主機列表,從虛擬機選擇過程中獲得候選遷移虛擬機列表VmsToMigrationList。然后將候選遷移虛擬機列表中的虛擬機按照其CPU使用率的具體情況完成降序排序。對隊列中的每個虛擬機，那些具有最小Approach3值的物理主機將被作為目標主機完成虛擬機的放置;在每次的虛擬機放置過程中，那些完成分配的虛擬機將從VmsToMigrationList列表中刪除。

如果云數據中心沒有物理主機可用，將啟動開機程序開啟新的物理主機來完成大量虛擬機的放置;反之,處理低負載狀態的物理主機將被關閉,節省電力能量。該算法將反復執行，直到VmsToMigrationList列表中的所有虛擬機全部完成虛擬機放置。

可以看出，該虛擬機放置策略可以放置那些具有低關聯性的虛擬機到同一個物理主機,從而降低高關聯性的虛擬機在分配時帶來的負面影響。按照這個辦法，可以盡量避免物理主機的超負載情況的發生，從而間接地降低了虛擬機遷移的次數，最終提高云數據中心的資源利用效率。

3 仿真實驗

3.1 仿真環境

為了對本文提出的考慮虛擬機關聯性的虛擬機放置策略進行實驗分析，采用了Cloudsim模擬器。Cloudsim 3.0版本中還提供了很多已經有的虛擬機選擇及虛擬機放置策略的能量管理模型的實驗數據，方便科研工作者對云數據中心的能量相關的虛擬機遷移算法的比較與研究[8]。

根據虛擬機遷移過程的三個階段的步驟，Cloudsim中比較好的辦法是LRR策略完成物理主機狀態檢測。結合MMT策略完成虛擬機選擇,再結合BFD辦法完成虛擬機重新分配,我們稱之為LRR-MMT-BFD策略,將該策略與Approach1、Approach2、Approach3三個辦法進行性能比較。被模擬的云數據中心主要由兩類物理服務器組成，物理服務器總數為800個，物理服務器配置如表1所示。

表1 云數據中心物理服務器配置

模擬云客戶端的應用程序訪問，使用具有正確CPU與內存請求的任務數據, 構成1 052個虛擬機的請求，運行的可以是一個Web應用程序或者其他具有不同類型工作負載的應用程序,一共產生大約四類虛擬機,如表2所示。

表2 云數據中心四類虛擬機需求情況

采用1.3節所描述的能量消耗模型,這也是Cloudsim中常用的能量消耗模型[21]。物理主機狀態檢測過程周期設置為5分鐘一次，相當于虛擬機遷移周期也為5分鐘一次，針對虛擬機的CPU資源使用率最近的q個歷史數據,q設置為30,一共運行24小時。

3.2 評測標準

按照Cloudsim項目研究思路，虛擬機遷移策略評價的主要指標有四個: (1) 云數據中心的總體能量消耗;(2) 虛擬機遷移次數;(3) SLA違規比率分析;(4) 能量與SLA違規的聯合指標ESV。它們四個可以體現與能量消耗相關的虛擬機遷移策略的性能好壞。

本文另外增加了兩個性能指標: SLATAH指標和超負載的物理主機累積數量指標。物理主機超負載的情況是本文一個重要參考指標，每隔5分鐘就要進行一次物理主機狀態檢測,該指標是統計一天內累積的超負載物理主機數量。

最后如果SLA違規的情況發生了，云數據中心會提供一個懲罰機制,云服務提供商會產生另外的開銷。

3.3 仿真結果與性能分析

把考慮虛擬機關聯性的虛擬機放置三個方法分別與LRR-MMT-BFD策略進行性能比較,值得再次指出的是，Approach1、Approach2、Approach3三個策略在虛擬機選擇和虛擬機放置階段都分別采用的是LRR方法和MMT方法。在六個性能指標上完成實驗,每次統計一天內的總體能量消耗,在一周內重復運行五次(星期一到星期五),計算整體的平均值,基本可以體現云數據中心的整體性能情況,實驗結果如圖2-圖7所示。

圖2 考慮虛擬機關聯性策略的總體能耗性能比較

圖3 考慮虛擬機關聯性策略的虛擬機遷移次數比較

圖4 考慮虛擬機關聯性策略的超負載主機總數比較

圖5 考慮虛擬機關聯性策略的SLATAH值比較

圖6 考慮虛擬機關聯性策略的SLA違規比率值比較

圖7 考慮虛擬機關聯性策略的ESV值比較

從實驗結果可以看出，三種采用了考慮虛擬機關聯性的虛擬機放置策略在虛擬機遷移次數上都小于Cloudsim項目中的LRR-MMT-BFD策略;Approach1、Approach2、Approach3等遷移策略在超負載物理主機累計數量上都遠小于LRR-MMT-BFD策略。Approach1、Approach2、Approach3等遷移策略顯示出云數據中心的SLATAH值也小于LRR-MMT-BFD策略。

從累積超負載物理主機數量、虛擬機遷移次數、SLATAH值等三個指標可以看出，考慮虛擬機關聯性的虛擬機放置方法可以盡可能地減少超負載物理主機事件的發生，即表明本文的策略很少影響云數據中心的QoS指標。

整體云數據中心的ESV指標表明了QoS指標與總體能量消耗的平衡。從實驗可以看出，Approach1、Approach2、Approach3等虛擬機放置策略在ESV性能上都低于LRR-MMT-BFD策略大約80%,驗證了在第三階段虛擬機放置過程中考慮虛擬機之間的資源使用率關聯性的重要性。同時可以發現，Approach1分配策略、Approach2分配策略、Approach3分配策略之間也有性能差異，Approach3策略具有最小的ESV值。這是因為Approach3策略可以在虛擬機重新分配過程中把虛擬機之間的關聯性影響降到最低;Approach3策略可以最小化虛擬機之間的關聯性,最大限度地降低物理主機超負載狀態的概率,最終減少了整個云數據中心的虛擬機遷移次數。

LRR-MMT-BFD策略在虛擬機遷移過程中，只考慮了物理主機能量消耗或者資源使用率(CPU、內存、網絡帶寬、磁盤空間等)這些少量的指標作為遷移因素,往往導致整體云數據中心的物理資源利用效率比較低。Approach2虛擬機分配策略比Approach1和Approach3兩個策略在性能指標上都要差,如果所有候選的虛擬機內部的關聯性都比較小，那么Approach3放置策略的性能將達到最好。

4 結 語

本文提出云數據中心考慮虛擬機關聯性的虛擬機放置策略，包括三類虛擬機放置策略：Approach1,Approach2,Approach3。這三類策略都可以盡量減少那些關聯度比較大的虛擬機在重新分配過程中會出現在相同物理主機上的機會，從而在一定程度上避免了物理主機超負載事件的發生。采用真實的云客戶端的數據，與Cloudsim系統中已有的虛擬機遷移策略比較，本文方法的各個性能指標都優于Cloudsim系統中已有的遷移策略。考慮虛擬機關聯性的虛擬機放置方法可以作為各個企業構造云數據中心的重要參考依據。