一種面向數(shù)據(jù)中心的能耗感知虛擬機放置策略

楊 傲，馬春苗，伍衛(wèi)國，王思敏，趙 坤

(1.西安交通大學 計算機科學與技術學院，陜西 西安 710049；2.廣東浪潮大數(shù)據(jù)研究有限公司，廣東 廣州 510000)

隨著云計算的廣泛使用，數(shù)據(jù)中心的規(guī)模不斷擴大，因此帶動降低數(shù)據(jù)中心運行能耗方面的研究不斷發(fā)展。從IT設備系統(tǒng)層面來看，主要通過作業(yè)調度實現(xiàn)負載均衡達到節(jié)能效果；從虛擬機層面看，能夠通過虛擬機(Virtual Machine，VM)整合、調度等方法實現(xiàn)節(jié)能目的。其中，虛擬機放置(Virtual Machine Placement，VMP)問題被看成一種可變大小的裝箱問題(Variable Size Bin Packing Problem，VSBPP)[1]，本質上來說它是將請求的虛擬機序列通過各種計算方式得出需要放置的對應物理機(Physical Machine，PM)，放置位置以能夠實現(xiàn)最好的服務質量(Quality of Service，QoS)、最低的能耗開銷等為目標。目前主要有兩類虛擬機放置方法，分別為基于啟發(fā)式算法的虛擬機放置策略以及基于資源探測的虛擬機放置策略。

在基于啟發(fā)式算法的虛擬機放置策略中，文獻[2]綜合考慮負載均衡、虛擬機分配性能等因素，在此基礎上提出基于改進粒子群的虛擬機優(yōu)化配置算法，利用此優(yōu)化算法實現(xiàn)了目標問題的優(yōu)化。文獻[3]從目前異構數(shù)據(jù)中心的角度出發(fā)，提出了一種基于模擬退火技術的虛擬機放置策略，通過棄用物理活動的機器來最大程度地降低功耗，并減少制造周期。文獻[4]提出了一種基于離散版本的粒子蟻群的能耗感知算法，在不違反服務水平協(xié)議(Service Level Agreement，SLA)的情況下，采用了有效的最小化適應度函數(shù)來減少功耗。文獻[5]以優(yōu)化云數(shù)據(jù)中心的可用性和能耗為目標，提出了一種改進的遺傳算法(Improved Genetic Algorithm，I-GA)來解決虛擬機放置問題。該算法提出了一個虛擬層次結構模型，并與遺傳算法相結合，通過對I-GA初始種群生成步驟的創(chuàng)新，該模型能夠在解決可用性和能源消耗問題方面實現(xiàn)近最優(yōu)解。文獻[6]基于一種改進的基于排列的遺傳算法和多維資源感知的最優(yōu)匹配分配策略，提出了一種混合虛擬機放置算法。提出的虛擬機放置算法旨在通過最小化虛擬機的活動服務器數(shù)量來提高云數(shù)據(jù)中心的能耗率，并試圖實現(xiàn)活動服務器的多維資源(CPU、RAM和帶寬)的平衡使用，從而減少資源浪費。文獻[7]提出一種基于文化基因算法(Memetic Algorithm，MA)的虛擬機放置方法，該方法針對云數(shù)據(jù)中心運營情況建立了最小化能耗、最小化運行時服務等級協(xié)議違例率以及最大化資源利用率的多目標優(yōu)化模型，將虛擬機按照資源請求情況進行分類，并利用該分類方法改進了MA，利用改進后的MA求解多目標優(yōu)化模型，得到虛擬機放置方案。除此之外，還有利用和諧搜索算法[8]以及磷蝦群算法[9]等。

此外，一些研究也從虛擬機以及物理機的資源探測方面入手。文獻[10]兼顧考慮物理機資源浪費和網絡總流量兩個方面，將虛擬機放置建模為多目標優(yōu)化問題，同時最小化物理機資源浪費以提高數(shù)據(jù)中心物理機使用效率和最小化網絡總流量以改善數(shù)據(jù)中心網絡的擴展性，設計了一種基于多目標蟻群優(yōu)化的虛擬機放置算法來求解該問題。文獻[11]認為最佳適應算法(Best Fit，BF)能夠很好適用于云數(shù)據(jù)中心環(huán)境，因此采用最佳適應算法作為數(shù)據(jù)中心虛擬機放置算法，能夠有助于節(jié)省未充分利用的物理服務器，并且虛擬機映射到數(shù)據(jù)中心中的服務器時能有效地做出響應。文獻[12]通過考慮虛擬機的 CPU 和內存要求分配時受限于物理機的容量，受最佳擬合遞減算法的啟發(fā)，開發(fā)了該精確算法的4種變體以解決多容量約束下的多目標問題。文獻[13]研究了如何平衡多種資源的使用，在最大限度提高虛擬機放置的服務速率的同時，緩解資源的碎片化，從而避免物理資源的浪費和不良的性能。為了解決這種雙目標優(yōu)化問題，提出一種聯(lián)合裝箱啟發(fā)式和遺傳算法，以較低的時間復雜度獲得近似最優(yōu)解。文獻[14]提出一種基于最佳適應法放置的虛擬機放置策略，稱為空間感知最佳擬合減少(Space Aware Best Fit Decreasing，SABFD)，首先根據(jù)CPU利用率以降序對待遷移的虛擬機進行排序，具有足夠計算資源的PM將接收第一個虛擬機，而后將選擇具有最少可用計算資源的PM作為第2個虛擬機的目標主機；依此類推，直到完成所有虛擬機的放置。

從上述研究中，可以看出最佳適應法用于平衡多種資源的使用十分有效，而遺傳算法作為經典的進化算法可以較快地獲得較好的優(yōu)化結果。然而，目前研究尚未考慮數(shù)據(jù)中心服務器的環(huán)境溫度，若在高溫區(qū)域位置持續(xù)增加服務器負載，則可能導致局部熱點問題，使得制冷設備處于過度制冷狀態(tài)，導致數(shù)據(jù)中心運行能耗整體提高。筆者提出的能耗感知虛擬機放置策略，通過將最佳適應法和遺傳算法結合并進行一定改進，在降低數(shù)據(jù)中心運行能耗的基礎上避免熱點出現(xiàn)。該方法首先收集當前數(shù)據(jù)中心所有物理機的可用資源信息，然后按照CPU資源可用大小進行排序，依照溫度上升最小值確定虛擬機放置位置，當所有位置確定后將目標序列二進制化，通過遺傳算法最終尋找最優(yōu)解。遺傳算法是以能耗及溫度為目標，因此得出的最優(yōu)解在降低能耗的基礎上避免熱點出現(xiàn)，保證數(shù)據(jù)中心安全運行。

1 算法概述

目前絕大部分數(shù)據(jù)中心都采用虛擬化技術，將硬件資源例如CPU、內存、帶寬等進行抽象再轉換后交付給用戶使用，虛擬化技術打破了傳統(tǒng)實體結構之間的物理隔閡，能夠更方便更高效地完成客戶請求的資源和任務，因此當前數(shù)據(jù)中心主要通過請求虛擬機方式完成對物理資源的分配[15]。隨著數(shù)據(jù)中心的規(guī)模不斷擴大，服務器運行能耗也隨之上升，由于服務器運行功耗及發(fā)熱量與CPU、內存等利用率呈正相關，因此請求虛擬機放置在不同物理機，將會產生不同的能耗結果。虛擬機放置問題本質上來說，是將虛擬機請求序列通過算法計算得出最適合物理機放置位置，物理機在初始階段能夠看做是一個空盒子，等待合適的虛擬機將其放入，若確定某個虛擬機的放置位置后，目標物理機可用的CPU、內存以及帶寬資源則會相應地減少，因此物理機能夠看做是一個可變大小的箱子。這樣將問題轉化為裝箱問題，能夠將CPU、內存、帶寬以及溫度等多維問題轉化為箱子編號的一維問題，進而將物理機序列二進制化，極大地簡化了數(shù)據(jù)處理的復雜度，更方便進行后續(xù)計算。

上述介紹了目前常見的虛擬機放置算法，但是暫時還未有在放置過程中考慮服務器物理溫度的研究。筆者提出的算法通過將能耗與溫度信息進行關聯(lián)，實現(xiàn)多目標優(yōu)化。算法流程圖如圖1所示。

圖1 算法流程圖

首先收集當前所有物理機的信息，包括可用CPU、內存、帶寬資源以及當前物理機的溫度。由于服務器能耗以及溫度主要是與CPU利用率相關，因此對物理機按照CPU可用資源從小到大進行排序。對于每一個虛擬機，采用最佳適應算法確定放置位置，若有多個物理機符合要求，則根據(jù)文中提出的溫度迫切值計算方法從中選擇出溫度迫切值最小的物理機作為目標位置。當所有虛擬機序列都確定好位置后得到目標虛擬機序列，將二進制化后的序列作為遺傳算法的初始種群，先對序列進行交叉以及變異操作，再根據(jù)筆者提出的適應度函數(shù)采用輪盤賭法選擇出下一代種群，通過遺傳算法的多次迭代后得出最優(yōu)解。其中，最佳適應法的時間復雜度為O(n3)，遺傳算法的時間復雜度為O(n2)，則算法整體的時間復雜度為O(n3)+O(n2)，也就是O(n3)。

2 最佳適應法分析

最佳適應算法最初應用于計算機內存分配，算法首先將空閑內存分區(qū)按照升序的方式排列，在進行內存分配時從排序好的空閑內存中從小到大查找，將第一個符合要求的分區(qū)作為目標區(qū)域，因此后續(xù)相對較大的分區(qū)能夠保留。在內存分配應用中指標為一維尺度，同樣也可將其擴展至三維尺度，在筆者提出的算法中分別將CPU、內存以及帶寬資源作為指標進行匹配。

首先收集物理機的可用CPU、內存、帶寬資源以及溫度信息，假設有M個物理機，對所有物理機首先按照CPU可用大小以升序方式排列。對于請求的虛擬機序列，先后處理的順序將會造成不同的結果，因此將其隨機排列模擬不同的到達次序，假設有N個虛擬機，隨機生成x個序列Px，序列Pi中每一個值代表虛擬機請求編號。在算法運行過程中，所有的物理機以及虛擬機應該滿足以下條件：

(1)

(2)

(3)

(4)

(5)

tj

(6)

(7)

其中，xij是一個二進制數(shù)組，表示虛擬機Vi是否分配至物理機Sj，yj是一個二進制數(shù)組，表示物理機Sj是否分配虛擬機，tj表示物理機Sj分配后溫度，Tth為預定的溫度閾值，vcpu、vmem及vBW分別代表虛擬機請求的CPU、內存及帶寬資源，pcpu、pmem、pBW分別代表物理機所擁有的資源，N是虛擬機總量，M是物理機總量。

Hj=|bj-tavg|+|tj-tavg|， ?j∈{1，2，…，M} 。

(8)

其中，tavg為物理機初始平均溫度，計算公式如下：

(9)

通常物理機運行溫度受多方面因素影響，其中散熱部件包括服務器風扇以及制冷設備等，主要產熱部件為CPU，實驗過程中綜合考慮了產熱與散熱的相互作用，確定了物理機溫度與CPU利用率呈正相關。實驗收集了服務器運行時溫度信息與負載信息，采用多項式擬合方法，最終物理機溫度與CPU利用率關系如下：

(10)

其中，Uj為物理機j的CPU利用率。Uj由以下公式獲得：

(11)

對所有符合要求的物理機計算溫度迫切值，將最大值的物理機作為當前虛擬機目標放置位置，同時更新物理機可用資源信息。最佳適應算法篩選物理機序列的算法描述如算法1所示，主體為3層循環(huán)計算，時間復雜度為O(n3)。

算法1最佳適應算法篩選物理機序列。

輸入：x個虛擬機序列p，每個序列長度為N；有序物理機序列yk，長度為M。

輸出：目標物理機序列q。

① Function_FF(p){

② FOR(i=0 tox)

③ FOR(j=0 toN)

④ FOR(k=0 toM)

⑤ IF(yk可用資源符合虛擬機pij)

⑥ calculateHk//使用H參數(shù)記錄當前物理機溫度迫切值

⑦ IF(Hkhas not value)//沒有任何物理機的可用資源符合虛擬機請求

⑧ throw error

⑨ select the max value ofHkas target position

⑩ update the rest resource of server//更新包括可用CPU、內存以及帶寬資源

3 遺傳算法分析

遺傳算法(Genetic Algorithm，GA)是一種優(yōu)化算法，其靈感來自于大自然中種群發(fā)展規(guī)律，種群在不斷進化發(fā)展過程中，具有高適應環(huán)境的個體會不斷延續(xù)優(yōu)質基因到下一代個體中，通過對種群中存在的個體進行遺傳操作的迭代，產生了新的種群。在遺傳算法中，染色體的表示、選擇、交叉、變異以及適應度函數(shù)是算法的關鍵。傳統(tǒng)遺傳算法流程是：隨機生成含有n個染色體的種群Y，通過適應度函數(shù)計算Y中每個染色體的適應度值。染色體P1和P2是根據(jù)適應度值從Y種群中選擇出來的，在P1和P2中應用交叉概率為Cp的單點或者多點交叉法產生新的后代Q，然后在后代Q中應用概率為Mp的一致性變異操作產生新的后代Q′，新的后代將會放置在新的種群中。應用同樣的方法對種群中所有的染色體重復進行選擇、交叉、變異操作，直到新的種群完成。遺傳算法通過變異率和交叉率能夠動態(tài)地改變搜索過程，最終獲得最優(yōu)解。同時由于遺傳算法可以評估多個個體，產生多個最優(yōu)解，因此具有更好的全局搜索能力。遺傳算法的本質為二重迭代，時間復雜度為O(n2)。

3.1 交叉、變異以及選擇操作分析

遺傳算法中交叉和變異操作是產生新個體的關鍵，也是影響遺傳算法性能和最終結果的關鍵。交叉用于結合兩個或者多個父代遺傳信息來產生后代，比較流行的交叉算法有單點交叉、兩點交叉、多點交叉、順序交叉等。筆者選擇單點交叉法，在單點交叉中，選擇一個交叉點，將超過此點位置后方的遺傳信息進行相互調換。圖2展示了調換過程，它交換了父代交叉點后的信息，產生了新的個體。

圖2 單點交叉操作

在交叉過程中，如果概率過大或者相互交叉基因量過多，則產生新個體的速度就會過快，具有高適應度的個體結構更加容易被破壞，導致遺傳算法無法朝著最優(yōu)解的方向發(fā)展。相反，若交叉概率過低或者交叉的基因量過少，則不易產生新的個體，導致迭代過程過于緩慢，甚至整個求解過程停滯不前。因此文中算法考慮一種基于迭代次數(shù)的動態(tài)交叉計算方法，在算法初期，生成的種群中個體的差異度較大，通過交叉、變異操作后到后期，由于優(yōu)勝劣汰規(guī)則，大部分高適應度個體都保留了下來，個體之間的差異度會隨著遺傳的發(fā)展而減小。因此對于算法中交叉操作率以及交叉的基因數(shù)量，應隨著迭代次數(shù)而減小。對于交叉點的選擇如下：

(12)

其中，t為當前遺傳代數(shù)，tmax為迭代總次數(shù)。

圖3 替換變異操作

選擇是遺傳算法中的重要步驟，它決定序列是否參與后續(xù)迭代過程；遺傳算法的收斂速度也取決于選擇的高效性。流行的選擇算法有輪盤賭、排名法、競賽法及隨機抽樣法。文中選用輪盤賭法。輪盤賭法是以輪盤游戲為思路，首先計算種群中所有個體的適應度值f(xi)，i∈[0，N]，隨后根據(jù)

(13)

計算個體選擇概率，再根據(jù)公式

(14)

計算個體的累計概率作為輪盤的選擇概率。在輪盤構造完成后生成隨機數(shù)r，選擇出下一輪迭代個體。在選擇過程中，適應度函數(shù)作為確定選擇概率方法，其高效性顯得尤為重要。

3.2 適應度函數(shù)分析

適應度函數(shù)在遺傳算法中起著重要的作用。首先適應度函數(shù)是用來衡量當前種群質量的重要方式，函數(shù)有多個輸入接口，代表當前種群評估指標；在文中，有兩個評估指標，分別為種群的能耗指標以及溫度指標。能耗指標能夠保證遺傳算法迭代中能夠找出能耗最小的虛擬機放置位置，數(shù)據(jù)中心服務器能耗建模的方法主要分為基于組件的能耗模型以及基于系統(tǒng)利用率的模型。文中采用基于系統(tǒng)利用率的能耗模型，模型如下：

Pserver=c0ur+c1u+c2，

(15)

其中，u為CPU利用率，c0、c1和c2為實驗中需要確定的參數(shù)，r為實驗浮動參數(shù)，浮動范圍為0.5～1.5。

為了避免數(shù)據(jù)中心在運行過程中出現(xiàn)熱點問題，請求的虛擬機應該避免放置在溫度過熱的區(qū)域。評估方法如下所示：

(16)

其中，bj為物理機當前溫度，Tth為設定的溫度閾值，tj為物理機啟動虛擬機后的預測溫度，由式(10)計算可得。

至此，可得遺傳算法中適應度函數(shù)為

F=Pserver+αT，

(17)

其中，α為動態(tài)可調參數(shù)，根據(jù)數(shù)據(jù)中心的規(guī)模動態(tài)調整，浮動范圍為0.1～0.8。

4 實驗結果與分析

目前數(shù)據(jù)中心能耗優(yōu)化的實驗多數(shù)都是在仿真平臺上實驗的，這是出于對數(shù)據(jù)中心安全性和穩(wěn)定性的考慮。常用的仿真平臺包括GreenCloud、6sigmaDC、EnergyPlus和CloudSim等。本次實驗通過cloudsim仿真平臺完成。cloudsim是墨爾本大學中Gridbus項目孵化的云計算仿真平臺，它能夠模擬數(shù)據(jù)中心各種實體類，如物理機、虛擬機、網關以及實體類之間的交互關系[16]。

為了進行實驗對比，設計了4組對照實驗，分別為首次適應法(First Fit，F(xiàn)F)、正余弦優(yōu)化算法(Sine Cosine Algorithm，SCA)、遺傳算法(Genetic Algorithm，GA)以及隨機分配法(Random)。在實驗中BF算法以CPU資源作為參考對象，SCA中控制參數(shù)r1從2線性下降至0，遺傳算法迭代次數(shù)為200次。現(xiàn)在假設數(shù)據(jù)中心有3種不同的物理機配置，同時虛擬機請求資源類型也有3種。物理機配置如表1所示，虛擬機請求資源類型如表2所示。

表1 物理機配置表

表2 虛擬機配置表

為了檢測本算法是否能夠找到最優(yōu)解，首先使用小樣本進行實驗，小樣本實驗能夠列舉所有解決方案，因此存在最優(yōu)解。實驗中，分別使用5、6、7、8、10個虛擬機樣本，假設物理機的數(shù)量與虛擬機的數(shù)量相等，由數(shù)學分析可知，在每個場景中，放置位置一共有n!種，n為虛擬機個數(shù)。通過比較不同算法的能耗結果來推測該算法是否可以找到n!種可能中的最優(yōu)解。實驗結果如表3所示。

由表3可知，SCA算法、GA算法與筆者提出的算法都能找到最優(yōu)解，而FF算法與Random算法都未能找出最優(yōu)解，相比于FF算法，Random算法求得的能耗平均值更高，也符合預期結果。此外，隨著虛擬機以及物理機的數(shù)量增加，運行能耗也相應地提高，同樣符合預期結果。

表3 不同算法的能耗結果 W

此外，對比了不同規(guī)模數(shù)量的物理機以及虛擬機在不同方法下的能耗情況，同樣在表2以及表3隨機生成物理機以及虛擬機，對比方法包括Random、FF、SCA和GA。數(shù)量規(guī)模為5組，分別為data100、data150、data200、data250、data300，代表虛擬機以及物理機數(shù)量分別為100、150、200、250、300。其中迭代算法迭代次數(shù)為20x規(guī)模。實驗結果如圖4所示。

圖4 不同算法的能耗對比圖

由圖4可知，在不同數(shù)量集的條件下，文中算法所得到的能耗均最低，因此驗證了筆者提出的算法能夠有效地降低數(shù)據(jù)中心運行能耗。此外，在FF以及Random算法中，由于未對放置位置進行優(yōu)化，因此，相比其他算法能耗最高。在小樣本數(shù)據(jù)中，由于物理機數(shù)量較少，因此整體能耗較低，各個算法之間的能耗差值較小，但隨著物理機的數(shù)量增多，不同算法間的能耗差別逐漸體現(xiàn)。

筆者提出的算法結合最佳適應算法與遺傳算法，在BF算法階段能夠首先對虛擬機的請求進行資源對比，能夠有效地去除無效個體。此外，在遺傳算法交叉階段采用動態(tài)交叉點選擇，種群在初始階段，個體的相互差異較大，在迭代末期，差異小，因此交叉點的動態(tài)選擇能耗保證高適應度值的個體結構不被破壞。從表4以及表5隨機生成1 000個物理機以及500個虛擬機，分別對遺傳算法以及文中算法進行5 000次迭代計算，計算結果如圖5所示。

圖5 兩種算法迭代過程

由圖5可知，文中的混合算法在2 500次左右收斂，而傳統(tǒng)遺傳算法在實驗過程中，在5 000次迭代后收斂速度過于緩慢，未在本圖予以展示。因此能夠驗證本算法相比于遺傳算法能夠更快地收斂，得到最優(yōu)解。

為了模擬出更加貼近數(shù)據(jù)中心真實運行環(huán)境，使用更加豐富的虛擬機以及物理機配置模擬虛擬機請求情況以及物理機剩余資源，驗證本算法能夠使數(shù)據(jù)中心溫度分布更加均勻，進而能夠避免熱點的出現(xiàn)。物理機配置如表4所示，虛擬機請求配置如表5所示。

表4 物理機配置表

表5 虛擬機配置表

首先從物理機配置表中隨機生成800個物理機，代表當前數(shù)據(jù)中心可用物理機以及可用資源量，再從虛擬機配置表中隨機生成1 000個虛擬機以及虛擬機請求資源量，模擬當前數(shù)據(jù)中心某段時間虛擬機的請求。同時設定本算法中遺傳算法迭代次數(shù)為2 000次，在確定虛擬機啟動的位置后，給各個虛擬機分配相同的任務；執(zhí)行完成任務后，可得出各類算法執(zhí)行任務后的能耗以及溫度。通過實驗得出采用FF、SCA以及Random算法最終的能耗分別約為62.32kW·h、54.87kW·h和76.78kW·h，而筆者提出的算法最終能耗約為47.38kW·h，能耗降低比例分別約為23.97%、13.65%和38.29%，因此能夠證明筆者提出的算法能夠降低數(shù)據(jù)中心運行能耗。為了驗證筆者提出的算法能夠有效地避免數(shù)據(jù)中心熱點問題出現(xiàn)，從800個物理機中隨機挑選出20個物理機的運行信息，其中物理機結束任務后的溫度如圖6所示，各類算法溫度均差圖如圖7所示。

圖6 物理機溫度圖

圖7 各類算法溫度均差

由以上結果可知，F(xiàn)F算法、SCA算法以及Random算法最終溫度分布波動較大，而筆者提出的算法溫度波動較小。通過圖5，同樣能夠驗證此觀點。此外，通過計算，4種算法任務執(zhí)行后溫度方差分別為18.5、18.0、9.7、3.1，標準差分別為4.2、4.1、3.1、1.7。因此，根據(jù)實驗結果可以驗證，文中提出的算法能夠有效降低數(shù)據(jù)中心運行過程中出現(xiàn)熱點的概率。

5 結束語

首先對虛擬機放置方法進行闡述，可將虛擬機放置問題看作是可變裝箱問題。隨后介紹了本算法的兩個組成部分，分別為最佳適應算法以及遺傳算法。最佳適應算法以可用CPU資源作為參考對象，按照可用CPU資源大小對物理機進行排序，且筆者提出一種判斷溫度趨勢的迫切值方法，在進行虛擬機放置計算時提供有效的參考值。通過最佳適應算法生成的目標物理機序列作為遺傳算法的初始種群，在制定好高效的適應度函數(shù)之后，對種群進行交叉、變異以及選擇操作，使得種群向著最優(yōu)解不斷迭代。最后在仿真計算平臺cloudsim上進行實驗，通過實驗數(shù)據(jù)充分驗證了筆者提出的算法能夠降低數(shù)據(jù)中心運行能耗以及避免熱點問題出現(xiàn)。