多維度資源環境下基于矢量代數模型的虛擬機部署

張 揚 劉 進

1(廣西工業職業技術學院 廣西 南寧 530001)2(廣西大學計算機與電子信息學院 廣西 南寧 530004)

0 引 言

為了滿足用戶對于計算能力的快速增長的需求，諸如Amazon和Google等云供應商可以在全世界范圍內部署數以百萬計的大規模數據中心提供相應計算能力，以此實現云計算能力[1]。作為一種新興的計算模式，云計算可以以虛擬化形式提供無限的計算、存儲和通信資源能力，而處于互聯網上的用戶可按其需求以即付即用的商業模式使用這些資源。研究表明，由于整個云系統中服務器與數據設備的能耗已經占據數據中心能耗的55%以上[2]，能耗問題已經成為管理云數據中心的總體擁有成本TCO的關鍵問題。大規模數據中心的高能耗會導致更大的碳排放，對大氣產生不利影響。資源利用不充分是導致高能耗的另一個重要問題，由于傳統的數據中心中，服務器的滿負載運行僅占總運行時間的10%～15%，這會導致資源過量提供的浪費。由于云系統可通過彈性方式提供虛擬的未受限且安全可用的服務資源，因此，云數據中心中資源提供的過量成為一種普遍現象。

虛擬化技術可使數據中心在單個服務器上部署多個虛擬機VM實現資源利用與能效的提升，在維持應用性能需求的同時，通過轉換物理服務器至低功耗狀態實現能耗的降低[3]。基于此考慮，本文提出一種基于蟻群優化的虛擬機VM合并算法ACO-VMPC，求解不同資源類型情況下的資源利用均衡問題。算法利用基于矢量代數的方法建立了多維資源利用獲取模型，進而實現資源利用的提升與能耗降低的同步優化目標。

1 相關研究

虛擬機部署與合并是虛擬云數據中心中降低能量成本和提高資源利用率的常用手段。大多數研究應用貪婪啟發式方法將VM合并建模為裝箱問題，并設計了相關裝箱貪婪算法進行問題求解，如：首次適應遞減算法FFD[4]、最佳適應算法BF[5]、最佳適應遞減算法BFD[6-7]等。然而，VM合并作為NP-hard問題，貪婪方法無法確保產生近似最優解。而且，大多數方法在進行資源利用平均值的估計時，均無法獲取服務器資源的多維利用率。

約束規劃CP模型是求解VM合并的另一種常用方法。文獻[8]提出一種VM提供與部署方法，可以實現云數據中心中較高的VM裝配效率。文獻[9]設計了一種服務器合并管理方法，可以在集群中實現最小化的活動服務器數量和VM遷移開銷。然而，CP模型的應用會限制數據中心中服務器與VM總數量的域，從而限制搜索空間。

目前，蟻群優化算法ACO已經證明可成功求解一維裝箱與虛擬機合并問題。文獻[10]結合局部搜索算法提出一種基于ACO的裝箱問題求解方法。文獻[11]則設計一種性能優于遺傳算法的改進ACO裝箱求解方法。文獻[12]提出了一種性能優于FFD的改進ACO進行VM合并求解。然而，算法僅僅評估了在維持其他資源需求不變時，VM所需求的處理器數量發生改變時的情形，這實質上已簡化為一維資源模型。文獻[13]設計一種多目標ACO算法降低云數據中心的資源浪費和功耗，文中考慮了兩種資源(CPU和內存)，并證明了算法性能優于遺傳算法和傳統ACO算法。

綜合分析，當前工作擁有以下幾點不足：1) 缺乏對多維度資源利用率的建模與分析，而云數據中心是可提供多種類型的資源；2) 在進行虛擬機部署時未考慮數據中心能耗與資源利用率均衡優化。結合以上兩點，本文設計一種基于蟻群優化的虛擬機部署與合并算法，引入多維度資源利用模型，并基于矢量代數獲取多維度資源的利用信息，最后利用蟻群優化的手段，同步優化多維度資源環境下云數據中心的資源利用率與能耗，獲得最優的虛擬機部署解。

2 虛擬機合并模型

云供應商可以提供對于每種資源特定需求的不同VM，該VM實例在其個體資源能力上各不相同。云VM實例可寄宿不同種類的應用，適應實時的動態資源需求，以獲得并適應負載的動態預測與評估。由于VM實例與動態負載具有這些特征，云數據中心中在不同資源維度間進行資源需求的互補是常見的。進一步，由于云的提供方式為按需和即付即用，用戶可以根據其需求隨機創建和終止若干VM服務。由此，云數據中心中的VM創建與終止是實時動態的，這將導致服務器資源的分割，從而降低服務器資源利用率。VM合并是虛擬數據中心中解決以上難題的常用手段，它可以在考慮多維度資源需求的情況下在最小數量的物理服務器上進行VM的裝箱，以實現節省能耗和最大化服務器資源利用率的目的。

2.1 多維矢量裝箱下的虛擬機部署模型

(1)

式中：x為VM與PM間的部署矩陣。

(2)

令y為PM分配矢量，當Pi上至少部署一個VM時，元素yi=1，否則yi=0，表示為：

(3)

ACO-VMPC算法的目標即為在可用物理主機PM上部署VM，并實現：1) 在所有維度上活動PM的資源利用率最大化；2) 活動PM的功耗最小化。由于數據中心中服務器的功耗主要集中于CPU的運行，那么，活動PM的數量越少，所有維度上的資源利用越高，能耗也越少。因此，將目標函數f形式化為y上的單目標最小化函數，表示為：

(4)

PM的資源能力約束(即：對于每一資源類型，所部署的VM的需求Dk不能超過主機PM的資源能力Ck)可表達為：

(5)

同時，需要確保每個VM至多分配至一個PM上，即：

(6)

2.2 基于矢量代數的多維資源利用模型

在PM上部署VM時，對于任意部署與合并算法而言，最重要的是度量多資源類型下的全局利用率，由于可能出現單一資源類型過載而無法改進其利用率，而其他類型的資源未充分利用，出現低載情況。為了取得資源利用的均衡和全局資源利用率的提高，本文在部署算法中設計一種基于矢量代數的資源互補性利用獲取機制。模型在VM合并過程中考慮CPU、內存和網絡I/O三種服務器資源，PM的標準資源能力表示為單元立方(Resource Cube)，三個維度分別代表三種資源類型。RCV和RUV分別表示PM的總資源能力和當前資源占用。為了度量PM當前資源占用的不平衡度，引入資源不平衡矢量RIV計算RUV與RCV間的矢量差。給定一個PM在部署一個VM后的RUV=Ci′+Mj′+Ik′，C、M和I分別為CPU、內存和網絡I/O的當前資源占用情況，RIV=(C-H)i′+(M-H)j′+(I-H)k′，H=(C+M+I)/3。當選擇VM至PM上進行部署時，擁有最小RIV的VM即為所有不同維度下PM資源占用最平衡的目標VM。RIV的計算方法為：

(7)

2.3 資源占用與浪費模型

(8)

式中：R={CPU,MEM,I/O}。類似地，資源浪費可定義為每個單個資源的剩余標準化資源的總和：

(9)

2.4 功耗模型

(10)

式中：Efull和Eidle分別為當PM完全利用(即CPU100%繁忙時)和空閑時的平均能耗。由于服務器的功耗利用是非正比例的，在VM部署后可關閉或掛起空閑服務器。因此，VM部署決策x下的總能耗可表示為：

(11)

3 ACO-VMPC算法設計

3.1 基于ACO的VM合并

ACO是受螞蟻種群行為啟發形成的一種智能計算方法，其智能螞蟻的數量即代表所優化問題的解，該解是通過不斷選擇可行解的成分并以信息素度量解的質量的形式獲取的。ACO-VMPC算法中，將VM與PM間的分配方式定義為解的成分，與所有VM-to-PM分配所關聯的信息素等級則代表一個VM至一個PM的分配意愿，然后動態地計算每個VM-to-PM對的啟發值，該啟發值即代表PM上全局資源利用與平衡資源利用兩個目標上分配VM時所考慮的偏好。

3.2 算法步驟

ACO-VMPC算法的偽代碼如算法1所示，其詳細解釋如下：算法輸入包括主機PM集合P、主機的總資源能力RCV、虛擬機集合V、VM的資源需求矢量RDV、螞蟻集合及相關螞蟻算法參數，輸出為螞蟻尋優后得到的全局最優部署解GBS。步驟3對螞蟻算法的相關參數進行初始化設置，并為每一個VM-PM對設置信息素，且全局最優解置為空。信息素等級利用n×m的矩陣τ表示。每只螞蟻由一個空解、一個PM集合和一個隨機VM集合開始執行(步驟6-步驟12)。在while循環體內，螞蟻被隨機選擇，并利用概率決策規則在所有可行VM中選擇一個VM分配至當前PM(步驟11-步驟22)。如果當前PM被充分占用或有不可行VM分配至PM上，則啟用一個新的空閑PM進行部署VM(步驟14-步驟16)。

當所有螞蟻建立了相應解后，比較當前循環中的所有解，尋找依據目標函數f(式(4))得到的全局最優解GBS，擁有最小目標f值的解則選擇為當前的GBS(步驟23-步驟28)。計算信息素增加量，對每個VM-PM對的信息素等級進行更新，以模擬螞蟻信息素的揮發和沉積(步驟29-步驟34)。算法僅增加屬于GBS中的VM-PM對的信息素。然后，重復搜索新解的過程，直到解的質量無法進一步改進為止，即步驟35。

算法1 ACO-VMPC算法

1. Input:set of PMsPand their RCVCi, set of VMsVand their RDVDj, set ofantsantSet, set of parameters{nAnts,nCycleTerm,β,ω,δ,q0}

2. Output:GBS

3. initialize parameters,set pheromone value for each VM-PM pair(τv,p) toτ0,GBS=?,nCycle=0

4. repeat

5. for allant∈antSetdo

6.ant.solution=?,ant.pmList=P

7.ant.p=1,ant.vmList=V

8. Shuffleant.vmList

9. end for

10.antList=antSet,nCycle=nCycle+1

11. whileantList≠? do

12. pick anantat random fromantList

13. ifant.vmList≠? then

14. ifFVant(ant.p)=? then

15.ant.p=ant.p+1

16. end if

17. choose a VMvfromFVant(ant.p) accord.to Eq.16

18.ant.solution.xp,v=1,ant.vmList.remove(v)

19. else

20.ant.solution.f=p,antList.remove(ant)

21. end if

22. end while

23. for allant∈antSetdo

24. ifant.solution.f

25.GBS=ant.solution

26.nCycle=0

27. end if

28. end for

29. compute △τ

30. for allp∈Pdo

31. for allv∈Vdo

32.τv,p=(1-δ)×τv,p+δ×△τv,p

33. end for

34. end for

35. untilnCycle=nCycleTerm

以下描述算法過程中的詳細步驟：

1) 信息素與初始信息素總量的定義。ACO算法的開始，蟻群開始行動時，每個VM-PM解的成分均擁有固定量的初始信息素。參考FFDL1Norm算法[11]產生的解計算初始信息素的量：

τ0=PEFFDL1Norm

(12)

式中：PEFFDL1Norm為FFDL1Norm算法得到的解的裝箱效率PE。算法產生的任意解sol的PE為：

(13)

2) 啟發信息的定義。搜索解的過程中，啟發值ηv,p代表選擇解成分v-p的收益度量。由于ACO-VMPC算法的目標是以均衡方式對VM進行裝箱從而降低活動PM的數量，本文將啟發值定義為同時偏好均衡所有維度的資源利用和更高的全局資源利用率，即：

ηv,p=ω×|lgmagRIVp(v)|+(1-ω)×Utilizationp(v)

(14)

式中：magRIVp(v)為分配VMv后PMp的RIV值。magRIVp(v)的對數用于為導致更小RIV的v-p對賦予更高的啟發值。參數ω為均衡資源均衡利用與全局資源利用的相對因子。Utilizationp(v)為當分配VMv時PMp的全局資源利用：

(15)

3) 偽隨機正比例規則。構造分配解時，一個螞蟻k根據以下的偽隨機正比例規則選擇VMs分配至PMp：

(16)

式中：q為[0,1]間的隨機數，q0為區間[0,1]間的參數，τv,p為當VM-PM對v-p時的當前信息素值，β為非負參數，表示在決策規則中信息素量與啟發值間的相對因子。FVk(p)定義為螞蟻k分配至PMp的可行VM集合：

(17)

若q≤q0，得到更高τv,p×[ηv,p]β值的v-p對被選擇為解的成分；否則，依據以下隨機正比例規則得到的概率Pk(v,p)選擇VMv：

(18)

4) 全局信息素更新。為了使算法在子迭代中得到全局最優解GBS，信息素的全局更新規則將應用于每個v-p對的信息素值上，具體規則為：

τv,p=(1-δ)×τv,p+δ×Δτv,p

(19)

式中：δ為全局信息素延遲參數，且0<δ<1；Δτv,p為應用于每個v-p對上的信息素加強值。

(20)

4 實驗分析

由于缺乏大規模測試床和可重復實驗的現實云環境設施，本節采用仿真評估的方法分析所提算法的性能，仿真環境為CloudSim，編程環境為Java。CloudSim平臺具有開源性，且使用最廣泛，其內核提供了虛擬引擎，可以在單個數據中心節點上創建并管理多個獨立、協同的虛擬機，并基于GridSim和離散事件驅動，可以模擬創建多種云計算環境中的實體，包括可以創建數據中心、物理服務器、虛擬機以及組件間可進行的消息傳輸，及消息的時鐘管理等。仿真環境中構建的云數據中心由異構主機PM集群組成，對于每種資源類型的VM資源需求可表示為PM總資源能力的百分占比。同時，利用參考VM資源需求Ref=z%的形式表示每種隨機產生在區間[0,2z]中的VM資源需求Dr，r∈{CPU,MEM,I/O}。實驗中分別設置參考值為Ref=10%,15%,20%，25%，對應的期望平均PE=10,6.7,5和4。在仿真平臺下，為了實驗結果的一般性，利用相同的參數配置，構建10次獨立的仿真實驗，且每個實驗運行20次，結果取其平均值。與ACO-VMPC相關的蟻群優化參數設置如表1所示。

表1 蟻群相關參數設置

選擇以下幾種算法進行性能比較：1) 文獻[12]提出的基于自適應最大最小蟻群優化的VM合并算法MMVMC；2) 文獻[10]提出的矢量貪婪算法VectorGreedy，在多維資源的評估方面同樣使用了矢量代數機制進行VM合并；3) 文獻[6]提出的基于列的平均評估算法FFDVolume；4) 文獻[11]提出的基于L1標準平均評估的FFDL1Norm算法。

圖1-圖4給出了1 000個VM需求時算法的各項性能指標，包括活動PM的數量、VM裝箱效率、總體功耗及能效改善效率。實驗中設置Eidle=162 W，Efull=215 W。由圖可知，ACO-VMPC在各項指標上均優于其他算法。同時，ACO-VMPC算法獲得了接近于期望平均值的PE。以上結果表明，ACO-VMPC算法中的信息素更新機制和偽隨機正比例規則下的螞蟻尋優是有效可行的，它可以找到虛擬機與主機間的能效最優映射解。相比而言，MMVMC算法得到的活動PM數量僅次于本文算法結果，原因在于該算法采用了自適應最大最小蟻群優化機制，但其信息素的更新機制是基于傳統蟻群搜索算法的。另外三種算法中，矢量貪婪算法VectorGreedy綜合性能是最優的，它與另外兩種算法的最大區別在于有效地進行了虛擬機的合并，這使得最終的活動的主機數量有所降低，資源利用率也更高。

圖1 活動PM數量對比圖

圖2 PE值對比圖

圖3 能耗對比圖

圖4 ACO-VMPC相比基準算法得到的能效改善比例

圖5給出了算法得到的活動PM的總資源浪費情況，以標準化百分比表示，部署VM數量為1 000。結果表明，ACO-VMPC算法較其他算法極大降低了資源浪費，這是由于ACO-VMPC在每個服務器上以互補性的資源需求進行了VM合并，改善了全局資源利用，從而實現了在不同資源維度上降低資源浪費的目的。其他四種算法中，MMVMC算法采用了自適應最大最小蟻群優化機制，相對而言比另外三種算法得到資源利用率更高，浪費率更低，但其傳統的信息素更新機制在進行螞蟻尋優時的效率仍然低于本文算法ACO-VMPC，故其資源浪費率高于ACO-VMPC。矢量貪婪算法VectorGreedy同樣利用了虛擬機合并機制，在多數的VM需求比例下的資源浪費率要低于FFDL1Norm和FFDVolume算法，說明動態的虛擬機合并對于提高資源利用率的重要性。

圖5 資源浪費比例

為了觀察ACO-VMPC算法的時間復雜性，圖6給出算法獲得最優解GBS時的計算時間。實驗仿真環境配置為Core i5-2400 3.10 GHz CPU(4 cores)和內存4 GB的工作站主機，編程語言為Java環境。可以看出，算法的計算時間會隨著VM數量的增加基本呈現非線性遞增，且遞增幅度較小，平均花費時間約為25 s。由此可見，在虛擬機規模增大使得算法搜索最優解空間的增加的情況下，本文算法的運行時間并未出現過快的增加，這得益于尋優過程中信息素更新機制和偽隨機正比例規則下的螞蟻尋優是有效可行的，算法具有很好的適應性。

圖6 ACO-VMPC算法的計算時間

5 結 語

為了優化云數據中心的能耗與資源利用率，本文提出一種基于蟻群算法的虛擬機部署與合并算法。算法首先將虛擬機合并問題形式化為多維度裝箱問題，然后，設計了基于矢量代數的多維資源利用模型，從而獲取資源的利用與浪費模型，最后通過改進的蟻群優化算法求解虛擬機合并問題。仿真實驗驗證了算法的性能。