許利軍， 王付強

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

0 引 言

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

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

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

1 虛擬機部署與功耗模型

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

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

圖1 能效虛擬機部署模型

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

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

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

(1)

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

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

(2)

2 SLA違例指標

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

SLAV=SLATAH×PDM

(3)

(4)

(5)

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

3 虛擬機部署策略

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

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

圖2 基于CPU負載的VM部署

本文設計一種基于需求的方法，基于每個VM的實際MI/s進行VM合并。該方法的最終分配結果如圖3所示。可以得出，該方法僅部署了兩臺物理服務器，每臺的實際利用率為70%。

圖3 基于需求的VM部署

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

算法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 虛擬機遷移選擇

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

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

圖4 過載服務器的上門限值

圖5 低載服務器的下門限值

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

Minimize |R|

式中：uj為主機j當前的CPU占用；uj(v)為分配給虛擬機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 算法流程與時間復雜度分析

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

圖6 算法流程

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

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

K+NM=O(3NM+N)

6 仿真實驗

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

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

DVFS(Dynamic Voltage and Frequency

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

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

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

實驗結果的評價指標包括：

TEC(Total Energy Consumption)，總能耗。

SLAV(SLA Violations)，SLA違例。

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

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

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

圖7 總體能耗圖8 SLA違例

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

圖9 VM遷移量圖10 平均活動物理服務器數量

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

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

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

7 結 語

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