秦啟飛　王世振　袁翔　胡志剛

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

關(guān)鍵詞：云計算； 數(shù)據(jù)中心； 虛擬機放置； 能耗； 化學(xué)反應(yīng)優(yōu)化

中圖分類號：TP391 文獻標(biāo)識碼：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 引 言

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

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

2 問題描述

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

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

3.2 基本化學(xué)反應(yīng)操作的設(shè)計

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

1）無損器壁碰撞

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

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

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

（3）利用當(dāng)前解的鄰域函數(shù)產(chǎn)生其所有（或若干）鄰域解，并從中確定若干候選解；

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

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

（6）轉(zhuǎn)步驟（2）。

2）分解反應(yīng)

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

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

3）無損分子碰撞反應(yīng)

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

4）合成反應(yīng)

3.3 算法描述

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

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

4 實驗與分析

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

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

4.2 實驗結(jié)果與分析

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

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

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

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

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

5 總 結(jié)

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

[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īng)管理與多目標(biāo)優(yōu)化[J]. 計算機學(xué)報， 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.