基于負載不確定性的虛擬機整合方法

李雙俐，李志華，2*，喻新榮，閆成雨

(1.江南大學物聯網工程學院，江蘇無錫214122; 2.物聯網應用技術教育部工程研究中心(江南大學)，江蘇無錫214122)(*通信作者電子郵箱lily_lshl@163.com)

0 引言

近年來伴隨著企業計算的爆炸性增長，用戶對云計算的需求也不斷上升。傳統的資源分配方式使得數據中心常處于高負載、高成本的運營狀況［1］，因此，許多云服務提供商開始采用虛擬化技術為用戶分配資源。虛擬化技術使得數據中心能夠快速地進行資源分配，增加了數據中心的靈活性。然而，數據中心的資源管理也因此變得更加復雜，如何制定虛擬機的調度策略變成了合理分配數據中心資源的關鍵問題之一。

高效的虛擬機整合策略能合理地分配資源、降低數據中心能耗、提高服務質量(Quality of Service，QoS)。已有的一些虛擬機整合方法［2－4］為了提高資源利用率和降低數據中心能耗，通過將低負載物理主機上的虛擬機整合到其他物理主機并關閉這些空閑物理主機的方式達到降低能耗的目的;但是，過度的虛擬機整合在應對數據中心負載突然增加時，需要額外消耗一定的時間開啟休眠物理主機［2］，此時，并不能確保服務提供商與用戶簽訂的服務等級協議(Service Level Agreement，SLA)，從而進一步影響數據中心的服務質量。

由于虛擬機整合是一個系統性的問題，文獻［4］將虛擬機整合問題分成物理主機過載檢測、虛擬機選擇、虛擬機放置和物理主機收縮四個階段。虛擬機整合時，首先通過物理主機過載檢測得到過載物理主機集合;然后，針對過載物理主機進行虛擬機選擇，并將這些虛擬機遷出以緩解物理主機的過載風險，遷出的虛擬機需要重新放置在合適的目標物理主機上，繼續提供計算服務;最后，對數據中心中的低負載物理主機進行關閉，從而達到降低數據中心能耗的目的。

虛擬機整合問題目前已得到了廣泛研究，各種算法相繼被提出［4－9］。文獻［4］在物理主機過載檢測方面給出了中位數絕對偏差(Median Absolute Deviation，MAD)算法、四分位距(InterQuartile Range，IQR)算法、局部回歸(Local Regression，LR)算法;在物理主機選擇方面給出了最小遷移時間(Minimum Migration Time，MMT)算法、最大相關度(Maximum Correlation，MC)算法和隨機選擇(Random Selection，RS)算法。近年來，一些以降低能耗為目標的算法［5－6］被提出。文獻［5］通過對 CPU 能耗模型的分析，建立了一個能耗最優的混合整數規劃模型，并據此提出了一種虛擬機放置方法。文獻［6］介紹了一種基于時間序列預測和啟發式裝箱的動態虛擬機整合算法，通過啟發式裝箱算法最大限度地減少所需物理主機數量，降低了數據中心能耗。然而，上述算法對服務質量及資源利用率的關注不足。文獻［7］根據負載變化情況提出了一種彈性資源預測方法，利用輕量級信號處理和統計學算法實現資源請求的動態預測，但未給出具體的整合策略。文獻［8］提出了一種虛擬機負載負相關的虛擬機選擇算法。該算法首先將虛擬機根據負載變化負相關的原則進行配對，然后將配對的兩臺虛擬機放置在同一臺物理主機上。該算法有利于穩定物理主機的工作負載，但缺乏對虛擬機間關聯性的考慮。文獻［9］在文獻［8］的基礎上增加了虛擬機配對迭代次數，但同樣利用兩臺虛擬機配對，忽略了虛擬機整體間的關聯。文獻［7－9］的實驗結果表明基于負載的虛擬機整合算法給數據中心帶來了積極的影響。

針對目前虛擬機整合存在的缺乏對負載穩定性分析的問題，本文通過分析虛擬機資源請求與物理主機工作負載之間的關系，確定物理主機剩余資源對虛擬機的滿足程度，擬合得到虛擬機與物理主機之間的匹配度。利用匹配度進行虛擬機整合能夠穩定物理主機負載，達到提高服務質量、降低能耗的雙重目的。

1 工作負載與虛擬機遷移

1.1 負載分析

通常數據中心為了降低能源消耗，在資源分配時希望能夠充分利用每臺物理主機的資源，從而避免低利用率造成的資源浪費。然而，虛擬機對資源的請求過程是隨機的，對于處于高負載狀態的物理主機，一旦虛擬機請求的資源超過了物理主機的可用資源總和就會發生過載，從而違背云服務提供者與用戶簽訂的服務水平協議，造成服務質量下降。為了提升服務質量，我們傾向于為物理主機預留充足的資源以避免過載，但過多的預留資源又會造成資源浪費，增加能源消耗。本文利用物理主機工作負載和虛擬機資源請求的變化特征進行虛擬機整合，以期達到提高云服務質量的同時能夠充分利用物理主機資源的目的。

在實際情況中物理主機負載呈多峰分布，圖1(a)記錄了數據中心其中一臺物理主機一天內的CPU負載變化情況;為了更清楚地看到其負載變化，圖1(b)選取該主機在第215～234次整合周期期間的CPU負載變化。由圖1可知，物理主機的負載變化具有隨機性。

對于處在活動狀態的物理主機，如果運行在其上的虛擬機在某一時段資源請求較高，那么此時物理主機的負載將出現局部峰值;而如果運行在其上的虛擬機在某一時段資源請求較低，那么物理主機的負載將出現局部谷值。如圖1(b)所示，為了避免主機過載情況的發生，物理主機應為波峰時段預留足夠的資源，然而，這些預留資源在波谷時段的閑置又造成了資源的浪費，這顯然是矛盾的。因此，穩定物理主機的負載，有效避免物理主機負載出現較大的波動，從而減少資源的預留量，這不僅能夠提高物理主機資源利用率，同時也降低了由于物理主機負載不確定性造成的主機過載風險。

圖1 單個物理主機CPU負載變化Fig.1 Workload changing of single physical host CPU

1.2 虛擬機遷移

根據工作負載的特性，在虛擬機遷移過程中如果能夠保持物理主機工作負載的穩定，避免物理主機工作負載出現明顯的波動，那么就能減小物理主機的過載風險，并且增加物理主機的資源利用率。

為了穩定物理主機負載，在虛擬機從過載物理主機上遷出時，應該選擇與物理主機匹配度低的虛擬機，即被選擇的虛擬機的資源請求與物理主機負載在同一時段出現峰值。根據此規則對遷移虛擬機進行選擇，選擇的虛擬機遷出后，能降低物理主機在負載峰值時的過載風險。在放置虛擬機到目標物理主機上時，虛擬機與物理主機的負載應該呈現高匹配度，即當物理主機負載處于高峰值時虛擬機對資源的請求量應處于低谷，避免由于虛擬機的放置使物理主機負載出現突然變化。保證放置的虛擬機在各個時刻都能充分地利用物理主機剩余預留資源，并且能夠穩定物理主機負載，避免由于負載出現較大波動而導致物理主機發生新的過載。

本文所提出的算法利用虛擬機資源請求擬合物理主機工作負載，并通過擬合得到的虛擬機與物理主機的負載匹配度進行虛擬機遷移。在保證物理主機資源充分利用的同時降低其過載概率，提高服務質量。

2 基于負載不確定性的虛擬機整合方法

2.1 虛擬機與物理主機匹配度估算

為了清楚地描述擬合過程，首先對數據中心的各項資源進行抽象。vmlist代表虛擬機集合。向量corhj=［…，，…，］T代表各虛擬機與物理主機hj的負載匹配度。向量b= ［b1，b2，…，bi，…，bt］T代表物理主機hj的CPU剩余可用資源的歷史記錄，其中，bi代表hj在i時刻的CPU剩余可用資源。A= ［vm1，vm2，…，vmi，…，vmm］代表虛擬機請求資源的歷史記錄矩陣，其中列向量vmi代表虛擬機vmi對CPU資源請求的歷史記錄。

為了量化物理主機負載的情況，定義函數 g(vmlist，hj，corhj)，如式(1)所示:

式(1)表示，若將vmlist中的虛擬機按照匹配度向量corhj放置在物理主機hj上后，物理主機負載均衡的程度。物理主機負載越平穩則函數g的值越小。當函數g取得最小值時，可以得到虛擬機在物理主機hj上的一組最優匹配向量corhj，如式(2)所示:

s.t.0 corhj1

根據式(1)及以上分析可知，求解式(2)可得到全部虛擬機對應物理主機的匹配度corhj。將虛擬機按照匹配度降序排列的方式依次放置在物理主機hj上，直至剩余虛擬機都不能再放入hj為止。此時，可以得到使物理主機負載趨于平穩的虛擬機整合方案。

圖2 sigmoid函數Fig.2 sigmoid function

sigmoid函數的圖形是“S”形的，它是嚴格遞增的函數，其中a是sigmoid函數的傾斜參數［10］。修改參數a就可以改變sigmoid函數的傾斜程度，變化趨勢如圖2所示。根據sigmoid函數的特性，本文中令= φ(vi)，則corhj可以表示為向量形式:corhj=［φ(v1)，φ(v2)，…，φ(vi)，…，φ(vm)］T。通過這樣的變換，式(2)轉化為式(4):

顯然，式(4)是一個無約束優化問題。在此采用梯度下降法求解無約束優化問題，利用負梯度作為搜索方向［11］，迭代公式如式(5)所示:

其中:s－(k)代表搜索的梯度負方向;ρk代表沿梯度方向上的搜索步長。對式(4)求導數可以得到函數g在v上的梯度公式。

根據導數與梯度的關系［11］，可求得函數g在v上的梯度，代表梯度向量s－(k)的一個分量，如式(6)所示:

至此，梯度下降法可求解式(4)所示的無約束優化問題。利用梯度下降算法先求出向量v的值，然后根據式(3)計算可以得到虛擬機與物理主機負載匹配度向量corhj。利用梯度下降法求匹配度流程如圖3所示。

圖3 利用梯度下降法求匹配度流程Fig.3 Flow chart of gradient descent method for computing matching degree

2.2 物理主機過載檢測

隨著虛擬機資源請求的變化，物理主機工作負載也隨之改變。對于負載較高的物理主機，若虛擬機請求資源增加，那么將有可能出現虛擬機請求資源超過物理主機可用資源的情況，此時物理主機發生過載。對于每一臺物理主機，可以根據其負載情況計算該物理主機的過載概率，通過過載概率為物理主機選擇合適的過載閾值用于新一輪的虛擬機整合，并通過整合來動態調整物理主機負載，提高服務質量。過載概率與過載閾值的計算如式(7)、(8)所示。

本文將物理主機CPU利用率超過65%的概率作為物理主機的過載概率，如式(7)所示。當物理主機CPU利用率超過65%時，認為主機存在過載風險。在一個檢測周期內物理主機CPU利用率超過65%的次數越多則該物理主機發生過載的風險越大。式(8)通過過載概率計算過載閾值。參數s控制過載概率對過載閾值的影響，s越大則過載概率對過載閾值的影響越大;s越小則過載概率對過載閾值的影響越小。當物理主機過載概率較大時，降低其過載閾值從而降低物理主機的過載風險;當物理主機過載概率較小時，則該主機過載風險較小，將其過載閾值調高，以保證物理主機資源的充分利用。

根據以上分析，本文提出基于工作負載不確定性的過載概率估計(Workload Uncertainty-based Overload Probability Estimation，WUOPE)算法。在進行過載檢測時，當物理主機的CPU利用率ui大于過載閾值Tiu時，則判斷當前物理主機hi過載。WUOPE算法偽代碼如下。

算法1 基于工作負載不確定性的過載概率估計(WUOPE)算法。

2.3 虛擬機選擇

當虛擬機請求資源超過物理主機可用資源時，物理主機同樣會出現過載風險。為了保證云數據中心的服務質量應該將一部分虛擬機遷出過載主機以緩解過載風險。

遷出虛擬機的選擇應遵循以下兩個原則:1)遷移后應保持物理主機負載穩定，避免由于遷移導致的物理主機負載不穩定;2)最小化遷移時間，減少由于遷移帶來服務質量下降的影響。通過利用虛擬機請求資源擬合物理主機剩余可用資源可以得到虛擬機與物理主機的負載匹配度。為了穩定物理主機負載可以優先遷移負載匹配度小的虛擬機，同時為了最小化遷移時間可以優先遷移占用內存小的虛擬機［12］。綜合考慮以上兩點，本文定義虛擬機在物理主機上遷移的優先級priority_s，計算式如式(9)所示:

為了保持物理主機負載穩定，本文提出了一種基于負載不確定性的最小遷移時間選擇 (Workload Uncertainty-based Minimum Migration Time Selection，WUMMT)算法。利用式(9)計算運行在過載物理主機上的虛擬機的遷移優先級，將虛擬機按照遷移優先級降序排列，依次將優先級高的虛擬機遷移出物理主機，直至物理主機的過載風險消除。WUMMT算法偽代碼如下。

算法2 基于負載不確定性的最小遷移時間選擇(WUMMT)算法。

2.4 虛擬機放置

對于因為物理主機過載和收縮而遷移的虛擬機必須為其尋找合適的目標物理主機進行放置。在虛擬機放置時首先要保證待放置物理主機有充足的資源，然后是確保放置虛擬機后目標主機的工作負載穩定性。

在選擇目標物理主機時，應該優先選擇具有相對較高資源使用率的物理主機作為目標主機，這樣更能充分利用物理主機的資源從而提高數據中心的資源利用率。通過式(10)計算出遷移虛擬機在目標主機上的放置優先級:

結合虛擬機與物理主機負載匹配度和虛擬機資源請求情況，本文提出一種基于負載不確定性的FFD的放置(Workload Uncertainty-based FFD allocation，WUFFD)算法。首先在正常運行的主機中挑選資源使用率較高的主機作為目標物理主機;然后計算虛擬機的放置優先級，把高優先級的虛擬機放置在目標主機上，以此類推，直至遷移虛擬機放置完成或目標主機不能再放入任何虛擬機為止。WUFFD算法偽代碼如下。

算法3 基于負載不確定性的優先適應下降的放置(WUFFD)算法。

2.5 虛擬機整合

虛擬機整合包括主機過載檢測、虛擬機選擇、虛擬機放置和物理主機收縮四個階段。本文提出一種基于負載不確定性的虛擬機整合(Workload Uncertainty-based Virtual Machine Consolidation，WU-VMC)方法。首先，WU-VMC方法利用WUOPE方法估算物理主機的過載閾值，判斷物理主機是否存在過載風險;然后，使用WUMMT方法將存在過載風險的物理主機上的一部分虛擬機遷移出物理主機，從而降低物理主機的過載風險;對于遷移出的虛擬機利用WUFFD方法選擇出合適的目標主機進行放置;最后，利用物理主機收縮方法降低能耗，將處于低使用率狀態的物理主機上的虛擬機全部遷出，并用WUFFD方法為其選擇合適的目標主機進行放置，利用循環檢測的方式每次選擇資源使用率最低或為“0”的物理主機進行收縮，關閉或休眠這些物理主機。WU-VMC算法偽代碼如下。

算法4 基于負載不確定性的虛擬機整合(WU-VMC)算法。

3 仿真實驗與分析

3.1 實驗環境

實驗采用 Cloudsim［14］作為仿真平臺。Cloudsim是澳大利亞墨爾本大學的云計算與分布式系統實驗室推出的開源云計算仿真軟件，可以支持大規模數據中心、云聯邦、用戶自定義資源管理策略等方面的仿真建模［15］。

本文通過Cloudsim平臺模擬一個擁有800臺物理主機的數據中心。這些主機根據資源配置的不同分為兩類:一類是HP ProLiant ML110 G4(Intel Xeon 3040 2 Cores 1 860 MHz，4 GB);另一類是 HP ProLiant ML110 G5(Intel Xeon 3075 2 Cores 2260 MHz，4 GB)。同時，模擬四種不同類型的虛擬機:超強 CPU配置的虛擬機 High-CPU Medium Instance(2500 MIPS，0.85 GB)、超大型虛擬機 Extra Large Instance(2000 MIPS，3.75 GB)、小 型 虛 擬 機 Small Instance(1000 MIPS，1.7 GB)和微型虛擬機 Micro Instance(500 MIPS，613 MB)［16］。實驗所采用的工作數據來自文獻［12］，即PlantLab平臺在真實環境下記錄的為期10天的CPU負載數據。表1記錄了10天中虛擬機請求的情況。

3.2 評價指標

為了評價方法性能，本文使用文獻［12］提出的六種性能評價指標:服務等級協議違背率(Service Level Agreement Violations，SLAV)、能源消耗(Energy Consumption，EC)、虛擬機遷移次數(Virtual Machine Migrations，VMM)、服務質量和能耗綜合評價指標(Energy and SLA Violation，ESV)、由于遷移導致的服務下降(Performance Degradation due to Migration，PDM)、運行時SLA違背時間(SLA violation Time per Active Host，SLATAH)。

表1 PlantLab虛擬機請求情況Tab.1 Request status of virtual machine PlantLab

SLATAH指由于活動物理主機在運行時CPU過載導致的違反服務等級協議，定義式如式(11)所示:

PDM代表由于虛擬機遷移導致的服務質量下降，定義式如式(12)所示:

SLAV是用來評價單日內數據中心服務質量的綜合指標，定義式如式(13)所示:

SLAV的值受當日數據中心SLATAH和PDM的綜合影響。當日數據中心的SLATAH與PDM值越低，則綜合值SLAV越小，數據中心服務質量越高。

EC代表數據中心一天的能源消耗。節約能源不僅能降低數據中心的運維成本，更是建設綠色數據中心的重要途徑。同時，低能耗也意味著資源的高利用率。綜合數據中心對低能耗和高服務質量的要求，定義服務質量和能耗綜合評價指標ESV，表達式如公式(14)所示:

ESV的值越低意味著當日數據中心的能源消耗少、服務質量高。

虛擬機在整合過程中的遷移勢必影響數據中心的服務質量，因此在整合過程中，遷移總量VMM的值越低虛擬機整合方法越高效。

3.3 負載穩定性分析

為了驗證WU-VMC方法的效率，本文利用Cloudsim平臺和PlantLab上10 d的數據進行實驗。文獻［4］對虛擬機整合過程進行了深入的研究，并提出了一系列經典整合方法。根據實驗結果，對比分析文獻［4］提出的一系列整合方法與WU-VMC整合方法。

由于負載的穩定性對于虛擬機整合有著十分重要的影響，據此對數據中心活動物理主機的CPU負載情況進行記錄。物理主機負載記錄的時間間隔為5 min，24 h內數據中心共記錄了288次物理主機負載的變化情況。

2011年3月3日數據中心活動物理主機平均負載變化情況如圖4所示。WU-VMC方法的CPU利用率明顯高于MAD-MMT、ST-MMT、IQR-RS三種方法。LR-MC方法的CPU利用率峰值雖然與WU-VMC方法相當，但LR-MC方法CPU利用率波動較大容易造成資源浪費。

圖4 3月3日一天內活動物理主機平均負載變化Fig.4 Average workload change of running physical hosts in March 3rd

活動物理主機的負載標準差可以反映數據中心負載的穩定性。結合圖5(a)可以看出，10 d內WU-VMC方法的活動物理主機CPU資源利用率標準差最小，即利用WU-VMC方法進行虛擬機整合使得數據中心負載更穩定;同時通過圖5(b)可以看出，10 d內使用WU-VMC方法的數據中心活動物理主機CPU平均利用率最高。故而，WU-VMC方法能夠穩定數據中心工作負載，提高數據中心資源利用率。MADMMT方法與其他三種方法由于在整合過程中未充分考慮物理主機與虛擬機的負載變化情況因而出現了負載波動較大、資源利用不充分等現象。

3.4 整合性能分析

利用文獻［12］提出的六種評價指標對本文提出的WU-VMC方法以及文獻［4］提出的 MAD-MMT、LR-MC、IQRRS、ST-MMT四種方法進行對比分析。不同方法在數據中心運行的各項評價指標如表2所示。圖6對各方法的能耗和服務等級協議違背率進行對比。

根據表2可以看出，由于LR-MC方法對虛擬機的過度整合導致其PDM值與SLATAH值最高，即由于遷移導致的服務質量下降和由于過載導致的服務質量下降。結合圖6(a)可知，LR-MC方法由于過度整合，數據中心開啟的物理主機的數量下降，所以能耗比 MAD-MMT、ST-MMT方法低。MAD-MMT方法與 ST-MMT方法由于使用最小遷移時間(MMT)作為虛擬機選擇策略，所以虛擬機遷移對數據中心的服務質量影響小，即PDM值小。IQS-RS方法的綜合評價指標ESV值比其他方法高，故而，在五種方法中IQS-RS方法的整合效率最低。

圖5 10 d內活動物理主機負載性能變化Fig.5 Workload change of running physical hosts within ten days

圖6 不同方法性能對比Fig.6 Performance comparison of different methods

本文所提WU-VMC方法通過穩定物理主機負載提高資源利用率，降低物理主機過載概率。如表2所示，WU-VMC方法與其他四種方法相比，虛擬機遷移次數VMM值降低了63%～67%;由于遷移導致的服務質量下降指標PDM值降低了39%～62%;由于過載導致的服務質量下降指標SLATAH值降低了11%～41%。因此與其他四種方法相比，WU-VMC方法綜合評價指標ESV值下降了65%～83%。

表2 不同方法性能評價結果Tab.2 Performance evaluation rusults of different methods

能耗和服務等級協議違背率是判斷數據中心是否高效的關鍵指標。根據圖6可知，在五種整合方法中，WU-VMC方法的EC值和SLAV值均低于其他四種方法。綜上所述，本文所提WU-VMC方法在虛擬機整合的各個方面都有著較好結果。

4 結語

云數據中心虛擬資源調度和管理是云計算的關鍵和核心內容之一。高效率的資源調度策略不僅能降低數據中心的能耗，而且能提高數據中心的資源利用率。考慮到物理主機當前剩余資源對虛擬機遷移和虛擬機放置的影響，通過利用虛擬機的資源請求擬合物理主機工作負載，計算虛擬機與物理主機的匹配度的核心思想，系統研究并提出了虛擬機整合過程中的主機過載檢測、虛擬機選擇、虛擬機放置和物理主機收縮四個子算法，通過進一步對上述四個子算法進行融合，提出了一種基于負載不確定性的虛擬機整合(WU-VMC)方法。仿真實驗驗證了WU-VMC方法的有效性和高效性。然而本本文僅考慮了CPU這一單一資源的使用情況，忽略了內存、帶寬等因素，沒有綜合考慮CPU、內存、帶寬等因素對虛擬機整合的綜合影響，如何利用多資源約束的多目標算法［17］進行虛擬機整合，將是我們下一步的研究工作。