多維度資源環(huán)境下基于矢量代數(shù)模型的虛擬機(jī)部署

張 揚(yáng) 劉 進(jìn)

1(廣西工業(yè)職業(yè)技術(shù)學(xué)院 廣西 南寧 530001)2(廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院 廣西 南寧 530004)

0 引 言

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

虛擬化技術(shù)可使數(shù)據(jù)中心在單個服務(wù)器上部署多個虛擬機(jī)VM實(shí)現(xiàn)資源利用與能效的提升，在維持應(yīng)用性能需求的同時，通過轉(zhuǎn)換物理服務(wù)器至低功耗狀態(tài)實(shí)現(xiàn)能耗的降低[3]?；诖丝紤]，本文提出一種基于蟻群優(yōu)化的虛擬機(jī)VM合并算法ACO-VMPC，求解不同資源類型情況下的資源利用均衡問題。算法利用基于矢量代數(shù)的方法建立了多維資源利用獲取模型，進(jìn)而實(shí)現(xiàn)資源利用的提升與能耗降低的同步優(yōu)化目標(biāo)。

1 相關(guān)研究

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

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

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

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

2 虛擬機(jī)合并模型

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

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

(1)

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

(2)

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

(3)

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

(4)

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

(5)

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

(6)

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

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

(7)

2.3 資源占用與浪費(fèi)模型

(8)

式中：R={CPU,MEM,I/O}。類似地，資源浪費(fèi)可定義為每個單個資源的剩余標(biāo)準(zhǔn)化資源的總和：

(9)

2.4 功耗模型

(10)

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

(11)

3 ACO-VMPC算法設(shè)計(jì)

3.1 基于ACO的VM合并

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

3.2 算法步驟

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

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

以下描述算法過程中的詳細(xì)步驟：

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

τ0=PEFFDL1Norm

(12)

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

(13)

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

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

(14)

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

(15)

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

(16)

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

(17)

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

(18)

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

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

(19)

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

(20)

4 實(shí)驗(yàn)分析

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

表1 蟻群相關(guān)參數(shù)設(shè)置

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

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

圖1 活動PM數(shù)量對比圖

圖2 PE值對比圖

圖3 能耗對比圖

圖4 ACO-VMPC相比基準(zhǔn)算法得到的能效改善比例

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

圖5 資源浪費(fèi)比例

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

圖6 ACO-VMPC算法的計(jì)算時間

5 結(jié) 語

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