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

秦啟飛　王世振　袁翔　胡志剛

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

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

中圖分類號：TP391 文獻(xiàn)標(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 引 言

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

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

2 問題描述

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

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

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

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

1）無損器壁碰撞

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

（1）給定算法參數(shù)，每一次迭代都把當(dāng)前分子w′作為禁忌算法的當(dāng)前解，置禁忌表為空，藐視準(zhǔn)則定義為：當(dāng)前解的物理機(jī)使用個(gè)數(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)的禁忌對象替換最早進(jìn)入禁忌表的禁忌對象，同時(shí)用y替換“best so far”狀態(tài)，然后轉(zhuǎn)步驟6；否則，繼續(xù)以下步驟；

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

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

2）分解反應(yīng)

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

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

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

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

4）合成反應(yīng)

3.3 算法描述

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

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

4 實(shí)驗(yàn)與分析

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

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

4.2 實(shí)驗(yàn)結(jié)果與分析

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

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

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

為了進(jìn)一步說明CROTS算法的求解效率，實(shí)驗(yàn)對ACO、CRO以及CROTS三種算法的收斂性情況進(jìn)行了實(shí)驗(yàn)比較。

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

5 總 結(jié)

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

[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]李強(qiáng)， 郝沁汾， 肖利民，等. 云計(jì)算中虛擬機(jī)放置的自適應(yīng)管理與多目標(biāo)優(yōu)化[J]. 計(jì)算機(jī)學(xué)報(bào)， 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.