能耗與性能均衡的云計算虛擬機(jī)部署優(yōu)化算法

許利軍， 王付強(qiáng)

(1.新鄉(xiāng)學(xué)院 計算機(jī)與信息工程學(xué)院，河南 新鄉(xiāng) 453003；2.武漢理工大學(xué) 計算機(jī)學(xué)院，武漢 430063)

0 引 言

云計算已經(jīng)成為學(xué)術(shù)界和產(chǎn)業(yè)界的熱點問題，它帶來了遞增式廣域式應(yīng)用和規(guī)模式經(jīng)濟(jì)的計算模型[1-2]。由于云計算的快遞發(fā)展，云服務(wù)提供商越來越多的建立大規(guī)模數(shù)據(jù)中心以滿足用戶對多類型資源的需求[3]。云數(shù)據(jù)中心的加速建立帶來了急劇增長的能耗問題，正成為云服務(wù)提供者面臨的巨大難題。能耗的增加除了增加云服務(wù)的運營成本和總體投入，還會加重碳排放[4]。除了任務(wù)執(zhí)行過程中造成的數(shù)據(jù)中心能源消耗，空閑服務(wù)器仍然消耗滿載時能源的30%[5]，因此，服務(wù)器的低載問題同樣需要進(jìn)行優(yōu)化。虛擬化的服務(wù)器合并技術(shù)是提高數(shù)據(jù)中心能效的有效手段之一，它可以降低活動服務(wù)器的使用數(shù)量，消除閑置能耗。

相關(guān)工作中，文獻(xiàn)[6]中在大規(guī)模虛擬化系統(tǒng)中提出了一種新的功耗管理算法，實現(xiàn)了硬件擴(kuò)展和虛擬機(jī)合并。文獻(xiàn)[7]中虛擬機(jī)的動態(tài)遷移被定義為優(yōu)化問題，優(yōu)化目標(biāo)是最小化云物理主機(jī)的能耗。以上工作并未從用戶的角度考慮性能方面的SLA違例問題。文獻(xiàn)[8]中提出一種高效的合并算法，同步實現(xiàn)能耗和SLA違例的降低。算法引入一種SLA感知資源分配機(jī)制，考慮了能耗與性能間的均衡以及主機(jī)占用與虛擬機(jī)在映射主機(jī)的相關(guān)性因素。文獻(xiàn)[9]中研究了虛擬化數(shù)據(jù)中心中功耗與性能有效的資源管理問題，以通過同步最小化功耗和SLA違例的方式最大化提供者收益為目標(biāo)，設(shè)計了一種資源分配算法。文獻(xiàn)[10]中引入一種改進(jìn)裝箱算法優(yōu)化虛擬機(jī)遷移，優(yōu)化資源分配。同時引入一個閾值定義虛擬機(jī)的遷移時機(jī)，以合并的手段降低主機(jī)利用數(shù)量。但該方法未考慮頻繁切換和虛擬機(jī)遷移的開銷問題。

顯然地，目前云環(huán)境中的虛擬機(jī)部署問題主要涉及單目標(biāo)和雙目標(biāo)優(yōu)化[6-12]，即在主機(jī)使用數(shù)量、SLA違例和應(yīng)用服務(wù)質(zhì)量(Quality of Service,QoS)性能保障、或數(shù)據(jù)中心能耗和虛擬機(jī)(Virtual Machine,VM)遷移等因素上進(jìn)行選擇優(yōu)化。以上目標(biāo)通常相互沖突。降低主機(jī)使用量，VM需要頻繁遷移；降低SLA違例，VM需要頻繁合并與遷移，勢必會開啟更多主機(jī)[13-14]；能耗與主機(jī)利用率相關(guān)，主機(jī)使用數(shù)量最少，并不一定能耗最小等。本文將考慮主機(jī)能耗、SLA違例及VM遷移量的相互關(guān)聯(lián)，實現(xiàn)一種性能與能耗均衡的虛擬機(jī)部署算法。

1 虛擬機(jī)部署與功耗模型

圖1所示為本文中云數(shù)據(jù)中心的能效虛擬機(jī)部署框架圖。具體包括兩個主要模塊：

(1) 虛擬機(jī)VMs分析模塊。該模塊決定每個VM請求的每秒百萬指令數(shù)(Million Instructors Per Second,MI/s)和內(nèi)存，以及基于前端服務(wù)器計算的來自用戶的VM請求數(shù)量得到的每個時間間隔內(nèi)系統(tǒng)運行的VMs。

圖1 能效虛擬機(jī)部署模型

(2) 虛擬機(jī)部署策略模塊。該模塊處理兩個參數(shù)：①由VMs分析模塊計算的資源需求；②數(shù)據(jù)中心設(shè)備的當(dāng)前狀態(tài)(開/關(guān))以及每個開啟服務(wù)器的可用資源。模塊(2)試圖尋找最小的服務(wù)器數(shù)量以完成VMs的資源需求。

云數(shù)據(jù)中心中計算節(jié)點的功耗主要由CPU、內(nèi)存、磁盤存儲及網(wǎng)絡(luò)帶寬構(gòu)成。比較其他系統(tǒng)資源，CPU消耗了大部分能源。因此，本文將關(guān)注于CPU功耗及其管理。CPU利用率通常正比于全局系統(tǒng)負(fù)載，為了簡化模型，本文應(yīng)用一種負(fù)載與功耗成線性關(guān)系的功耗模型。研究表明，空閑服務(wù)器的能耗仍約占CPU滿載能耗的70%，這表明將空閑服務(wù)器切換至睡眠模式可以降低總體功耗。應(yīng)用以下功耗模型：

P(u)=kPmax+(1-k)·Pmaxu

(1)

式中：Pmax為服務(wù)器滿負(fù)載時的最大功耗;k為空閑服務(wù)器的功耗比例，一般為70%；u為CPU利用率。

一般地，由于負(fù)載的不斷變化，CPU的利用率會隨著時間而發(fā)生改變，因此，u是時間的函數(shù)，表示為u(t)，物理主機(jī)的總能耗E可定義為某段時間間隔內(nèi)功耗函數(shù)的積分形式：

(2)

2 SLA違例指標(biāo)

QoS需求通常以服務(wù)等級協(xié)議SLAs進(jìn)行形式化描述，通常以最小吞吐量或最大響應(yīng)時間進(jìn)行衡量。由于不同的QoS特征對于不同的的應(yīng)用類型是不盡相同的，有必要定義一種通用的與負(fù)載類型無關(guān)的度量標(biāo)準(zhǔn)，以評估基礎(chǔ)設(shè)施中部署虛擬機(jī)所交付的SLA等級。本文使用SLA違例SLAV指標(biāo)度量算法性能，該指標(biāo)由每個活動主機(jī)的SLA違例時間(SLA Time of Active Host,SLATAH)和由于VM遷移帶來的性能下降(Performance Degration Model,PDM)構(gòu)成，具體定義為：

SLAV=SLATAH×PDM

(3)

(4)

(5)

式中：Tsi為主機(jī)i經(jīng)過的100%利用率的總持續(xù)時間；Tai為主機(jī)i為活動狀態(tài)的總時間；N為服務(wù)器數(shù)量；Cdj為表示遷移導(dǎo)致的虛擬機(jī)j的性能降低的估算；Crj為生命周期內(nèi)虛擬機(jī)j請求的總的CPU能力。

3 虛擬機(jī)部署策略

云環(huán)境中的虛擬機(jī)合并技術(shù)可以減少主機(jī)使用數(shù)量，從而降低主機(jī)的閑置能耗。先前的工作多利用每個VM的最大CPU負(fù)載作為標(biāo)準(zhǔn)對VMs進(jìn)行排序與合并。然而，由于處理器功耗的改變，該方法可能導(dǎo)致云數(shù)據(jù)中心的高能耗。以下利用一個算例闡述該問題的影響。

假設(shè)一個云數(shù)據(jù)中心的資源提供者擁有3個物理服務(wù)器，標(biāo)識為S1、S2和S3，每個服務(wù)器擁有一個CPU，性能為1 000 MI/s?，F(xiàn)需要配置5臺虛擬機(jī)VMs，標(biāo)識為VM1、 VM2、VM3、VM4和VM5，其最大性能需求分別為250、500、1 000、750、500 MI/s。假設(shè)所有物理服務(wù)器初始是空閑的，且第1個到達(dá)的用戶在每個VM上的需求為100、200、600、300、200 MI/s。如果利用基于靜態(tài)VM最大CPU負(fù)載方法進(jìn)行VM合并，則分配結(jié)果如圖2所示?？梢缘贸?，3個物理服務(wù)器的實際利用率分別為40%、40%和60%。

圖2 基于CPU負(fù)載的VM部署

本文設(shè)計一種基于需求的方法，基于每個VM的實際MI/s進(jìn)行VM合并。該方法的最終分配結(jié)果如圖3所示?？梢缘贸?，該方法僅部署了兩臺物理服務(wù)器，每臺的實際利用率為70%。

圖3 基于需求的VM部署

為了降低云數(shù)據(jù)中心的能耗，本文設(shè)計了一種基于能效的VM部署啟發(fā)式算法(Virtual Machine Power Aware,VMPA)解決VM部署問題。在VMPA中，首先根據(jù)動態(tài)請求的MIPS對VMs進(jìn)行降序排列。排序后，為每個VM尋找提供最少功耗增加的最優(yōu)服務(wù)器。算法充分利用節(jié)點的異構(gòu)性，優(yōu)先選擇功效最高的節(jié)點利用。該步驟中，首先，在所有充分利用和非空閑服務(wù)器中選擇最佳服務(wù)器，如果沒有找到分配VM的服務(wù)器，算法嘗試在所有非充分利用的服務(wù)器尋找最優(yōu)服務(wù)器。最后，如果所有服務(wù)器均無法找到目標(biāo)，算法從空閑服務(wù)器上開啟新的服務(wù)器進(jìn)行VM部署。VMPA算法的偽代碼如算法1所示。VMPA算法的時間復(fù)雜度為O(n×m)，其中，n為部署的VM數(shù)量，m為物理服務(wù)器的數(shù)量。

算法1VMPA-Virtual Machine Placement Algorithm

1. Input: ServerListH={h1,h2,…,hn}, VMListV={v1,v2,…,vm}

2. Output: Solution of VMs placement

3. Initialize EmptyServerListE, Underutilized Server ListU

4. SortVMsInDecreasing MIPS

5. ForviinV

6. InitializePmin←MAX

7. Initialize HV←NULL

8. ForhjinH

9. Ifhjhas no placed VMs

10. EmptyServerListE←hj

11. Else ifhjis an underutilized server

12. UnderutilizedServerListU←hj

13. Else ifhjhas enough resources

14.P(u)=k×Pmax+(1-k)×Pmax×u

15. IfP

16. HV←hj

17.Pmin←P

18. If HV=NULL

19. ForuiinE

20. Return 13-17

21. If HV=NULL

22. ForejinE

23. Return 13-17

24. If HV≠NULL

25. HV←HV(vi)

26. Else

27. Return infeasible placement

28. Return VMs placement solution

4 虛擬機(jī)遷移選擇

對于VM遷移，考慮引進(jìn)一種基于CPU上下限的雙門限值，使得CPU利用率保持在雙門限值之間。如果CPU利用率低于下限值，則該服務(wù)器視為低載主機(jī)，所有VMs需要從該主機(jī)上遷移出去，然后將該主機(jī)切換至睡眠模式以降低空閑功耗。如果CPU利用率超過上限值，則該服務(wù)器視為過載主機(jī)，需要遷移部分VMs以降低CPU利用率。雙門限值方法如圖4和圖5所示。

為了從過載主機(jī)上選擇最佳VMs進(jìn)行遷移，本文設(shè)計了一種VM遷移算法(Virtual Machine Migration Selection Algorithm, VMMSA)，可以使得遷移VMs的數(shù)量最少。VMMSA算法中，需要考慮兩個條件：①該虛擬機(jī)的CPU占用大于主機(jī)上所有虛擬機(jī)的CPU占用與門限值之差；②若該虛擬機(jī)從主機(jī)遷移，門限值與新的CPU占用之差是所有虛擬機(jī)遷移情況中值最小的。算法運行至主機(jī)CPU利用率低于上門限值為止，可以實現(xiàn)遷移的VMs數(shù)量達(dá)到最少以降低遷移開銷。

圖4 過載服務(wù)器的上門限值

圖5 低載服務(wù)器的下門限值

令Vj表示當(dāng)前分配到主機(jī)j上的虛擬機(jī)集合，Q(Vj)表示Vj的冪集，包括空集和全集的所有子集。VMMSA算法尋找的遷移虛擬機(jī)集合表法為R。

Minimize |R|

式中：uj為主機(jī)j當(dāng)前的CPU占用；uj(v)為分配給虛擬機(jī)v的CPU占用率。VMMSA算法的偽代碼如算法2所示。

算法2VMMSA-Virtual Machine Migration Selection Algorithm

1. Input: ServerListH={h1,h2,…,hn}

2. Output: MigratedVMListM

3. ForhjinH

4. Receive VMList deployed onhj

5. VMListSortDecreasingCpuUtilization

6. Receive R_CPU inhj

7. Initialize Ratio←MAX

8. While R_CPU >Upper

9. Forvmin VMList

10. If VM.Cpu>R_CPU-Upper

11. r←VM.Cpu-(R_Cpu-Upper)

12. ifr

13. Ratio←r

14. BestVM←vm

15. Else if Ratio==MAX

16. BestVM←vm

17. Break

18. Update R_CPU = R_CPU-BestVM.Cpu

19. M←vm

20. Delete BestVM from VMList

21. If R_Cpu

22.M←all VMs onhj

23. ReturnM

5 算法流程與時間復(fù)雜度分析

算法首先處理過載服務(wù)器上的VMs和新到達(dá)的VMs，將以上VMs部署到目標(biāo)服務(wù)器上后，對低載服務(wù)器上VMs進(jìn)行重新分配，并關(guān)閉低載服務(wù)器。然后，從過載服務(wù)器上選擇合適的VMs與新到達(dá)的VMs進(jìn)行合并作為VM部署算法的輸入。圖6所示為所提算法的流程圖。

圖6 算法流程

假設(shè)N為物理服務(wù)器的數(shù)量，M為待部署于服務(wù)器上的VMs數(shù)量，H為新到達(dá)的VMs數(shù)量，L為過載服務(wù)器數(shù)量，K為低載服務(wù)器數(shù)量，VMPA算法的時間復(fù)雜度為O(N×M)，VMMSA算法的時間復(fù)雜度為N。因此，算法時間復(fù)雜度為

2N+H+N(M+H)+NM+

K+NM=O(3NM+N)

6 仿真實驗

為了評估算法性能，本節(jié)在CloudSim平臺[15]中實現(xiàn)了所提的虛擬機(jī)部署算法。云環(huán)境包括一個數(shù)據(jù)中心，由N個異構(gòu)物理節(jié)點組成。根據(jù)CPU的不同處理能力，物理節(jié)點劃分為兩種類型，表示為(1 800 MI/s, 2 600 MI/s)。兩種類型物理節(jié)點均包括兩個CPU內(nèi)核、4GB RAM和1GB/s網(wǎng)絡(luò)帶寬。每個VM請求一個CPU內(nèi)核，性能需求分別為2 500、 2 000、1 500、500 MI/s, RAM為0.8、1.7、1.5、0.6GB，帶寬為100 MB。每個VM運行一個Web應(yīng)用或其他類型可變負(fù)載的應(yīng)用任務(wù)，可建模形成為均勻隨機(jī)分布的CPU利用率。應(yīng)用任務(wù)的計算量為150 000 MI，等同于250 MI/s的CPU在100%利用的狀態(tài)下運行10 min。初始狀態(tài)下，所有VMs根據(jù)資源請求特征按100%利用率進(jìn)行分配。實驗中模擬實現(xiàn)了以下4種VM部署策略進(jìn)行性能分析：

STA(Single Threshold Algorithm)，單門限值算法。

DVFS(Dynamic Voltage and Frequency

Scaling)[12]，動態(tài)電壓/頻率調(diào)整算法。

MPA(Maximum Power Algorithm)，最大功耗算法。

VMPA-VMMSA，本文提出的能效算法。

實驗結(jié)果的評價指標(biāo)包括：

TEC(Total Energy Consumption)，總能耗。

SLAV(SLA Violations)，SLA違例。

VMMN(VM Migration Number)，VM遷移數(shù)量

ANAS(Average Number of Active Servers)，平均活動服務(wù)器數(shù)量

實驗1觀察算法在以上4項性能指標(biāo)上的情況，結(jié)果如圖7～10所示。圖7是算法得到的總能耗情況，可以看出，MPA消耗了最多的能耗，由于該算法在所有物理服務(wù)器上均保持100%的CPU利用率，并未考慮VMs的部署問題。DVFS可以根據(jù)CPU利用率動態(tài)調(diào)整其電壓和頻率狀態(tài)，從而降低節(jié)點功耗。STA通過設(shè)置服務(wù)器利用的上門限值，并以此為限制進(jìn)行VMs部署，保持服務(wù)器的總利用率在該門限值以下。然而，STA可能導(dǎo)致低載服務(wù)器。不同于STA，VMPA-VMMSA算法通過上下門限的雙門限值方法可以實現(xiàn)VMs合并。當(dāng)服務(wù)器利用率低于下門限時，該服務(wù)器上的所有VMs需要遷移至其它服務(wù)器，并關(guān)閉該服務(wù)器，進(jìn)而降低總體能耗。圖8中，DVFS和MPA擁有更小的SLA違例，由于這兩種算法中請求的資源量等同于分配的資源量。VMPA-VMMSA擁有比STA更小的SLA違例，由于雙門限值方法更加有效，它可以激動更少的物理主機(jī)。但在圖9中，VMPA-VMMSA擁有更高的VMs遷移量?；陬愃频睦碛桑疚乃岬乃惴ɡ昧烁俚幕顒游锢矸?wù)器，如圖10所示。

圖7 總體能耗圖8 SLA違例

實驗2觀察雙門限值對性能的影響，結(jié)果如圖11、12所示。當(dāng)上門限值增加時，總能耗將減少，由于此時更少的服務(wù)器被激活使用。同時，這將導(dǎo)致更多的VMs合并和更多的SLA違例，如圖12所示。下門限值對性能的影響幅度相對較小，但其趨勢與上門限值的改變是類似的。

圖9 VM遷移量圖10 平均活動物理服務(wù)器數(shù)量

圖3觀察單門限與雙門限方法的性能，結(jié)果如圖13所示。由于單門限值僅設(shè)置上門限以確保服務(wù)器不出現(xiàn)過載情況，這將導(dǎo)致可能出現(xiàn)低載服務(wù)器和更多的額外能耗。雙門限值方法可以通過設(shè)置下門限值和VM遷移的方法合并VMs減少活動服務(wù)器數(shù)量，進(jìn)而降低能耗。同時，雙門限值可能擁有比單門限值方法更高的SLA違例。

實驗4觀察雙門限值方法中上下門值的間隔大小對算法性能的影響，結(jié)果如圖14所示。

可以看出，下門限值的增加將導(dǎo)致SLA違例的增加。同時，對于相同的下門限值，上門限值越高，能耗越小，SLA違例越高，這是因為上下門限值間的間隔越大，將導(dǎo)致要通過VM遷移進(jìn)行更多的VM合并，以得到更少的活動服務(wù)器。

7 結(jié) 語

利用動態(tài)遷移和切換節(jié)點至睡眠薩爾動態(tài)虛擬機(jī)合并技術(shù)可以使云資源提供者優(yōu)化資源利用和降低數(shù)據(jù)中心能耗。然而，向用戶提供高可靠QoS，實現(xiàn)能耗與性能的平衡也是必不可少的，由于激進(jìn)的合并策略可能導(dǎo)致應(yīng)用執(zhí)行性能的下降。為了解決這一問題，提出了一種自適應(yīng)的虛擬機(jī)部署算法。新算法能夠?qū)崿F(xiàn)動態(tài)的虛擬機(jī)合并與遷移以降低能耗，同時確保高等級的SLA，并降低虛擬機(jī)優(yōu)化部署過程中的遷移量。仿真實驗結(jié)果表明該算法是有效可行的。