云環(huán)境下基于CROTS算法的虛擬機放置策略

秦啟飛　王世振　袁翔　胡志剛

摘 要：隨著越來越多數據中心的構建和部署，能耗問題成為研究熱點。作為一種有效的節(jié)能策略，虛擬機整合受到了研究人員和業(yè)界的關注。針對傳統(tǒng)的虛擬機放置策略的不足，利用化學反應優(yōu)化算法CRO求解數據中心的虛擬機放置問題，并通過禁忌搜索算法提高CRO算法中器壁無損碰撞對解的勘探能力。仿真實驗表明，相對于傳統(tǒng)的貪婪放置策略FFD和基于ACO的放置策略，提出的CROTS算法可有效降低數據中心物理機的使用個數，進而降低了數據中心的能耗。

關鍵詞：云計算； 數據中心； 虛擬機放置； 能耗； 化學反應優(yōu)化

中圖分類號：TP391 文獻標識碼：A

Abstract：More and more data centers are created，and energy consumption becomes the research hotspot. As a kind of effective energy saving strategy， VM consolidation is focused by researcher and industry. Due to the shortage of the traditional VM consolidation，this paper used a new metaheuristic algorithm called CRO（Chemical Reactive Optimization）to solve the VM consolidation problem in data centers and used Local Search to improve the ability of seeking the solutions. Experimental results show that this method is more excellent than other methods， which can decrease the number of servers and can reduce the energy consumption of data centers.

Key words：cloud computing； data center； VM placement； energy； CROTS

1 引 言

云計算是一種新興的計算模式，然而，在云計算技術促進IT發(fā)展并帶來巨大經濟效益的同時，也消耗了大量的電能。近期分析報告顯示[1]：截至2011年，世界范圍內的計算中心的年均耗電量已經超過3 兆kW，且其增長呈明顯的加速趨勢。因此，有效控制數據中心的能耗量已經成為各國科研和應用領域的一個亟待解決的問題。在數據中心，隨著虛擬機的不斷創(chuàng)建與撤銷，分布在物理資源上的虛擬機必將分散，從而導致部分服務器的使用率非常低。如何合理地確定虛擬機到服務器的映射對整體物理資源池的利用率以及能耗有著直接影響，已經成為云計算領域的研究熱點。

大多研究主要將虛擬機放置問題建模為裝箱問題并采用貪婪算法去尋找一個近似最優(yōu)的方案，常用的貪婪算法主要有：首次適配FFD，最優(yōu)適配BFD和最差適配WFD（WorstFit Decreasing）三種。例如，IBM的Verma等[2]設計的pMapper采用FFD選擇虛擬機的放置位置。文獻[3]提出了一種虛擬機遷移框架EnaCloud，采用最優(yōu)適配BFD的啟發(fā)式算法確定虛擬機的放置。文獻[4]提出了一種改進BFD（BestFit Decreasing）算法并應用到虛擬機放置問題中，通過模擬實驗驗證了其性能。文獻[5，6]在一個同構的計算環(huán)境中將虛擬機放置建模為1維裝箱問題，只考慮CPU資源，所提出的虛擬機遷移算法沒有考慮當前的虛擬機分配情況。類似地，文獻[7]和文獻[8]也將虛擬機放置問題簡化為一維分配問題，僅考慮了CPU和內存資源。除此之外，一些研究將VM放置問題建模為多維裝箱問題，即MDBP問題。如文獻[9]將異構計算環(huán)境下的虛擬機分配問題建模為MDBP，然后通過實驗比較了多個貪婪算法的性能。在文獻[10]中，李強等人則將能耗感知的虛擬機放置問題歸結為多維QoS約束下的最優(yōu)規(guī)劃問題，并設計了一個基于遺傳算法的求解策略。近期，Albert等人[11]提出了一種新的元啟發(fā)式方法，稱之為化學反應優(yōu)化算法。該算法模擬化學反應中的分子碰撞，以及分子從高能狀態(tài)向低能狀態(tài)不斷轉變的過程，最終驅使分子進入最穩(wěn)定的狀態(tài)。CRO相對于以往的智能算法表現(xiàn)出了更強的問題求解能力。鑒于CRO算法求解的高效性，本文將禁忌搜索算法與之相結合以提高CRO局部搜索的能力，并應用到虛擬機放置問題的求解中，取得了較好的效果。

2 問題描述

虛擬機配置是數據中心的核心功能之一，其配置過程如圖1所示。首先，根據來自用戶應用的大量虛擬機配置請求，數據中心內的虛擬機配置規(guī)劃器根據監(jiān)控服務器或者通過負載預測獲得的服務器負載信息，確定服務器是否過載。然后采用智能算法獲得虛擬機配置的全局最優(yōu)解（本文基于CRO和禁忌算法）。最后，數據中心的遷移規(guī)劃器根據虛擬機的配置方案確定相應的遷移規(guī)劃。其中，虛擬機實時遷移（Live Migration）是一種有效的遷移機制，已經在一些服務器中得到了應用。

示例圖2表示ID為3和4的虛擬機放在1號物理機上，ID為2和7的虛擬機放在2號物理機上，ID為1、3和6的虛擬機放在3號物理機上。

3.2 基本化學反應操作的設計

CRO有4種分子反應，即無損器壁碰撞、無損分子間碰撞、分解和合成。

1）無損器壁碰撞

在這個反應中，一個分子將撞擊容器并導致分子結構發(fā)生局部改變。通過這個反應，原始的解w′將從它的鄰域w1中得到一個新的結構w，相當于局部搜索。為了提高分子加快算法的收斂速度，本文使用禁忌搜索算法實現(xiàn)無損器壁碰撞，具體步驟如下。

（1）給定算法參數，每一次迭代都把當前分子w′作為禁忌算法的當前解，置禁忌表為空，藐視準則定義為：當前解的物理機使用個數少于best so far，則忽視禁忌表屬性，用當前解代替best so far。；

（2）判斷算法終止條件是否滿足？若是，則結束算法并輸出優(yōu)化結果；否則，繼續(xù)以下步驟；

（3）利用當前解的鄰域函數產生其所有（或若干）鄰域解，并從中確定若干候選解；

（4）判斷候選解是否滿足藐視準則？若滿足，則用滿足藐視準則的最佳狀態(tài)y替代x成為新的當前解，即x=y，并用與y對應的禁忌對象替換最早進入禁忌表的禁忌對象，同時用y替換“best so far”狀態(tài)，然后轉步驟6；否則，繼續(xù)以下步驟；

（5）判斷候選解對應的各對象的禁忌屬性，選擇候選解集中非禁忌對象對應的最佳狀態(tài)為新的當前解，同時用與之對應的禁忌對象替換最早進入禁忌表的禁忌對象元素；

（6）轉步驟（2）。

2）分解反應

發(fā)生分解反應時，一個分子w將變成兩個新的分子w1和w2。這兩個新分子的結構與原來的分子結構有很大的差異。本文算法中，用Order Crossover（OX）算子實現(xiàn)分解。

在OX算子中，第一個母體是原來的分子w，第二個母體是隨機創(chuàng)建的一個解。w1由w的前半部分和隨機解的后半部分組合得到。而w2由w的后半部分和隨機解的前半部分組合得到。

3）無損分子碰撞反應

無損分子碰撞是兩個分子碰撞后發(fā)生微小的變化又分開。這個反應有點類似無損器壁碰撞，但是不同的是這個反應涉及到兩個分子，并且沒有分子動能（KE）丟失到中央能量緩沖區(qū)。我們用OX算子實現(xiàn)這個反應。

4）合成反應

3.3 算法描述

在算法開始之初，需要初始化如下參數：PopSize， KELossRate， MoleColl， buffer， InitialKE，α，β。其中PopSize表示種群大小，KELossRate表示動能丟失率，MoleColl取值為[0，1]，是每次迭代時判斷單分子碰撞和多分子碰撞的參數。α，β分別代表單分子碰撞和多分子碰撞選擇的極限值。當一個分子的撞擊次數超過α后，它的優(yōu)越性還沒提升則會發(fā)生分解反應。β代表一個分子所擁有的最小的動能，如果低于這個值則會發(fā)生合成反應。目標函數值就等價于分子的勢能值，要找最小的函數值就得找到最穩(wěn)定的勢能最小的分子。

迭代開始之后，會隨機產生一個[0，1]之間的整數K，當K大于MoleColl時則發(fā)生單分子碰撞，反之則發(fā)生多分子碰撞。迭代過程會一直繼續(xù)直到達到停止標準，最終輸出一個近似最優(yōu)解。

4 實驗與分析

4.1 實驗環(huán)境設置

在Myeclipse中采用面向對象的java語言實現(xiàn)CROTS算法，并將該算法與CRO、ACO和FFD等算法進行性能上的比較，同時也分析了算法在不同的虛擬機請求規(guī)模時的性能。模擬的集群系統(tǒng)包含600個物理服務器（設置了600個物理服務器是為了考慮最差的放置情況，一臺虛擬機占用一臺物理服務器），每個服務器包含CPU，內存，存儲和帶寬四種資源，為了更方便的考察該算法性能，在本次實驗中只考慮物理結點一個因素，假設QOS、SLA等其他因素都滿足條件，本次實驗適用在同構環(huán)境，600臺物理服務器的性能是一樣的，分別是10000MIPS、50GB內存、1TB存儲、10G的帶寬。實驗模擬的虛擬機數目在{100， 200， 300， 400， 500，，600}內取值。類似于Amazon EC2的虛擬機實例，實驗設置了四種虛擬機類型，其資源請求數目分別為：（1000， 4， 20，1）， （2000， 8， 50， 2）， （3000， 16， 100， 2）， （5000， 24， 200，4）。基于文獻[ 11]對實際服務器（Dell PowerEdge1950）功耗的測量，實驗設定服務器在空閑pidle和滿負載pmax 時的功耗大小分別為171瓦特和218瓦特。為了對比不同算法的能耗大小，實驗設定計算周期T為24小時。

4.2 實驗結果與分析

實驗中，為了考慮到公平性，對所有算法的虛擬機請求序列設置為一樣，對虛擬機數目分別為100、200、300、400、500、600時進行10次運算最終取平均值。本文中算法的優(yōu)化目標是使物理機數最少和降低能耗，根據公式（6）中的能耗模型，物理機數和它的資源利用率對能耗有直接影響，通過實驗證明了真實性。

圖3顯示不同虛擬機數目情況下4種放置算法得到的能耗比較情況。隨著虛擬機數目的增多，四種算法得到的能耗也逐漸增大。與FFD和ACO算法相比，CRO算法在能耗指標上平均降低了13.5%和9.9%。而與CRO算法相比，CROTS算法在能耗指標上平均降低了3.1%。這主要因為物理服務器的使用數目與數據中心的能耗有直接的關系，CRO和CROTS算法相對于FFD和ACO算法來說，能夠獲得更優(yōu)的放置解。

圖4比較了不同虛擬機配置數目情況下四種算法得到的物理服務器的數目比較。隨著虛擬機數目的增多，四種算法的物理服務器的數目也在增大。其中，F(xiàn)FD算法的性能最差，其所需要的平均物理服務器數目分別是ACO、CRO、CROTS算法的1.04、1.09、1.13倍。表明算法CROTS相對于其他三種算法，具有最好的求解能力。而且從圖4中可以看出當虛擬機規(guī)模越大，CROTS算法的性能越好，這是因為CROTS適合求解大規(guī)模優(yōu)化問題。

為了進一步說明CROTS算法的求解效率，實驗對ACO、CRO以及CROTS三種算法的收斂性情況進行了實驗比較。

從圖5可以看出CROTS混合算法的收斂速度要比ACO和CRO快，因為在CRO算法無損器壁碰撞反應中加入禁忌搜索，使得解的收斂速度更快，在60000次評估左右就基本上達到穩(wěn)定。表明CROTS在尋找最優(yōu)解方面具有明顯優(yōu)勢。

5 總 結

隨著數據中心基礎設施規(guī)模的增大，能耗問題越來越突出。虛擬機整合能夠有效的降低能耗，本文提出基于CROTS的虛擬機放置策略。通過CRO與禁忌搜索算法相結合，進一步提高了CRO算法的性能。實驗結果與傳統(tǒng)的貪婪算法和ACO相比，所提出的混合算法能夠有效的減少物理結點的使 用數量，從而達到節(jié)約能耗的目的。下一步的工作將考慮多目標同時優(yōu)化以及CROTS算法在解決虛擬機放置問題上的各個參數的最優(yōu)設置。參考文獻

[1] RICCIARDI S，CAREGLIO D，BOADA G S， et al. Saving energy in data center infrastructures [C]. Proceedings of the First International Conference on Data Compression， Communications and Processing， 2011：265-270.

[2] VERMA A，AHUJA P，NEOGI A. pmapper： power and migration cost aware application placement in virtualized systems[C]. In proceedings of 9th ACM/IFIP/USENIX international conference on middleware， 2008，243-264.

[3] Bo Li， Jianxin Li， Jinpeng Huai， et al. Enacloud： An energysaving application live placement approach for cloud computing environments[C]. In proceedings of international conference on Cloud computing， 2009.

[4] BELOGLAZOV A，BUYYA R.Adaptive thresholdbased approach for energyefcient consolidation of virtual machines in cloud data centers[C]. In proceedings of the 8th workshop on Middleware for Grids， Clouds and e-Science. 2010， 41-46.

[5] BORGETTO D，COSTA G D，PIERSON J M，et al. Energyaware resource allocation[C]. In Proceedings of the 10th IEEE/ACM International Conf on Grid Computing. 2009， 183-188.

[6] SUBRAMANIAN C，VASAN A，SIVASUBRAMANIAM A.Reducing data center power with server consolidation： Approximation and evaluation[C]. In Proceedings of the 17th IEEE Conf on High Performance Computing， 2010， 1-10.

[7] KHAN S U，ARDIL C.Energy efficient resource allocation in distributed computing systems[C]. In proceedings of International Conference on Distributed， High Performance and Grid Computing， 2009， 667-673.

[8] KHARGHARIA B，HARIRI S，SZIDAROVSZKY F，et al. Autonomic power & performance management for largescale data centers[C]. In proceedings of the 21th IEEE Conf on High Performance Computing， 2007， 1-8.

[9] STILLWELL M，SCHANZENBACH D，VIVIEN F，CASANOVA H.Resource allocation algorithms for virtualized service hosting platforms[J].Journal of Parallel and Distributed Computing， vol.70， no.9， pp. 962-974， 2010.

[10]李強， 郝沁汾， 肖利民，等. 云計算中虛擬機放置的自適應管理與多目標優(yōu)化[J]. 計算機學報， 2011， 34（12）：2253-2264.

[11]FELLER E，RILLING L，MORIN C.EnergyAware Ant Colony Based Workload Placement in Clouds[C]. In proceedings of the 12th IEEE/ACM International Conferece on Grid Computing， 2011， 26-33.