基于遺傳算法的虛擬機(jī)在線(xiàn)遷移優(yōu)化方法

劉 暢

(國(guó)網(wǎng)冀北電力有限公司秦皇島供電公司 信息通信分公司，河北 秦皇島 066000)

基于遺傳算法的虛擬機(jī)在線(xiàn)遷移優(yōu)化方法

劉 暢

(國(guó)網(wǎng)冀北電力有限公司秦皇島供電公司 信息通信分公司，河北 秦皇島 066000)

虛擬機(jī)在線(xiàn)遷移是云計(jì)算研究熱點(diǎn)。目前已有的研究工作未能考慮Web應(yīng)用資源需求的變化規(guī)律，可能會(huì)存在因虛擬機(jī)循環(huán)遷移而導(dǎo)致的Web應(yīng)用性能頻繁違約現(xiàn)象。提出一種基于Web應(yīng)用資源需求變化分析的虛擬機(jī)遷移優(yōu)化方法，以虛擬機(jī)資源需求小于物理機(jī)資源供給為約束條件，將虛擬機(jī)和物理機(jī)空間布局的穩(wěn)定性刻畫(huà)成收益。每次執(zhí)行虛擬機(jī)在線(xiàn)遷移操作時(shí)，都以收益最大化作為待遷移虛擬機(jī)和目標(biāo)物理機(jī)的選擇依據(jù)。實(shí)驗(yàn)結(jié)果表明，與已有方法相比，本方法能減少超過(guò)50%的性能違約次數(shù)。

虛擬機(jī)；循環(huán)遷移；在線(xiàn)遷移；遺傳算法

Abstract: VM live migration is a hot topic, and previous work ignores the periodic change of resource requirements for a Web application. It may do VM live migration between two physical machines periodically. In this paper, we propose a benefit-sensitive approach based on analysis of periodic changes on resource requirement. Here, the benefit means the stability in spatial topological between VMs and physical machines. Experimental results based on live workload traces show that our approach can effectively reduce performance violations by as much as 50% compared with previous work.

Key words:virtual machine; cyclic migration; live migration; genetic algorithm

0 引言

虛擬機(jī)在線(xiàn)遷移[1-3]是指運(yùn)行時(shí)變更虛擬機(jī)內(nèi)存的物理位置，卻不需要重啟的一種資源調(diào)整技術(shù)。它強(qiáng)調(diào)的是虛擬機(jī)實(shí)例的位置變遷，而不是資源總量的改變。虛擬機(jī)在線(xiàn)遷移操作具有運(yùn)行時(shí)重新綁定Web應(yīng)用與物理機(jī)關(guān)系的能力，適用于Web應(yīng)用負(fù)載動(dòng)態(tài)變化，物理機(jī)資源供給無(wú)法滿(mǎn)足(該物理機(jī)上虛擬機(jī)資源需求)的場(chǎng)景。其本質(zhì)是找到虛擬機(jī) (Web應(yīng)用)和物理機(jī)的最佳部署關(guān)系，又稱(chēng)為“虛擬機(jī)放置”問(wèn)題。

已有研究工作或忽略虛擬機(jī)在線(xiàn)遷移操作對(duì)Web應(yīng)用性能的影響(能耗敏感方法)，或容忍一定程度的Web應(yīng)用性能違約(遷移代價(jià)敏感方法)。除此之外，已有方法通常是以某一時(shí)間點(diǎn)的Web應(yīng)用資源需求作為虛擬機(jī)在線(xiàn)遷移的決策依據(jù)，在長(zhǎng)期負(fù)載模式(Time-of-day)下，存在“循環(huán)遷移”和頻繁Web應(yīng)用性能違約現(xiàn)象。所謂“循環(huán)遷移”[4-6]，即虛擬機(jī)i某一時(shí)刻從物理機(jī)j遷移到物理機(jī)k，另一時(shí)刻從物理機(jī)k遷回物理機(jī)j的現(xiàn)象。

針對(duì)已有方法不足，本章提出了收益(Benefit-sensitive)敏感的放置優(yōu)化方法。該方法將虛擬機(jī)和物理機(jī)空間布局的穩(wěn)定性刻畫(huà)成收益，并以收益最大化作為虛擬機(jī)放置優(yōu)化的依據(jù)。具體而言，首先將具體Web應(yīng)用和物理機(jī)的空間布局抽象成遺傳算法中的個(gè)體，將可能的空間布局抽象成遺傳算法中的群體。然后，基于收益最大化原則構(gòu)建遺傳算法的適應(yīng)度函數(shù)，適應(yīng)度最大的個(gè)體即為滿(mǎn)足約束條件的最優(yōu)解。實(shí)驗(yàn)結(jié)果表明，本方法與Energy-sensitive方法和Cost-sensitive方法相比，會(huì)多消耗約50%的能耗成本，但能有效減少Web應(yīng)用性能違約次數(shù)。

本文給出了循環(huán)遷移現(xiàn)象分析，介紹了放置優(yōu)化平臺(tái)的設(shè)計(jì)。其中，遷移決策是該平臺(tái)的核心組件，詳細(xì)描述了基于遺傳算法的虛擬機(jī)放置優(yōu)化算法，通過(guò)實(shí)驗(yàn)驗(yàn)證了本方法的有效性及相關(guān)工作介紹。

1 循環(huán)遷移現(xiàn)象

在初始條件下虛擬機(jī)和物理機(jī)的部署關(guān)系如下：

(1)三臺(tái)物理機(jī)Server1、Server2和Server3，假設(shè)每臺(tái)物理機(jī)配置都是1 vCPU，2 GB內(nèi)存；

(2)四個(gè)TPC-W應(yīng)用實(shí)例，假設(shè)實(shí)例都部署在配置為1vCPU和1 GB內(nèi)存的虛擬機(jī)上。其中，TPC-W-1、TPC-W-4部署在Server1上，TPC-W-2部署在Server2上，TPC-W-3部署在Server3；

(3)除了CPU資源，假設(shè)其他資源不存在瓶頸。

表1給出了應(yīng)用實(shí)例的CPU資源需求分布函數(shù)：TPC-W-1和TPC-W-2的CPU資源需求分別符合偏距為60、振幅為10的正弦和余弦分布；TPC-W-3、TPC-W-4的CPU資源需求則分別穩(wěn)定在50%和40%。

表1 Web應(yīng)用資源需求分布函數(shù)

常用決策算法下虛擬機(jī)在線(xiàn)遷移流程：

(1)從第15分鐘開(kāi)始，TPC-W-4應(yīng)用部署到虛擬化平臺(tái)中，此時(shí)Server1、Server2和Server3的CPU資源空閑率均為50%。因此會(huì)采用“隨機(jī)策略”將TPC-W-4應(yīng)用部署并運(yùn)行在Server1上。

(2)從第33分鐘開(kāi)始，TPC-W-1和TPC-W-4的CPU資源需求均為50%， Server1資源供給面臨瓶頸，虛擬化平臺(tái)會(huì)觸發(fā)虛擬機(jī)在線(xiàn)遷移操作。會(huì)采用“隨機(jī)策略”選擇待遷移虛擬機(jī)，假設(shè)是TPC-W-4。根據(jù)效用理論，已有研究會(huì)選擇Server3作為目標(biāo)物理機(jī)。因?yàn)樵诘?3分鐘，Server2空閑CPU資源為50%，而Server3空閑CPU資源為60%，認(rèn)為物理機(jī)CPU空閑率越高，其效用越大。

(3)從第42分鐘開(kāi)始，TPC-W-3和TPC-W-4的資源需求大于Server3的資源供給，虛擬化平臺(tái)再次觸發(fā)虛擬機(jī)在線(xiàn)遷移操作。同樣的原理TPC-W-4被選擇成待遷移對(duì)象，Server1被選擇成目標(biāo)物理機(jī)。因?yàn)樵诘?2分鐘，Server2的CPU資源空閑率為50%，而Server1為60%。

隨著時(shí)間的推移，部署TPC-W-4應(yīng)用的虛擬機(jī)會(huì)周期性地在Server1和Server3之間進(jìn)行切換，出現(xiàn)“循環(huán)遷移”現(xiàn)象。這是因?yàn)樘摂M機(jī)資源需求小于物理機(jī)資源供給的約束條件會(huì)周期性違背。

2 遺傳算法設(shè)計(jì)

遺傳算法(Genetic Algorithm, GA)是模擬達(dá)爾文生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)理的生物進(jìn)化過(guò)程的計(jì)算模型，是一種通過(guò)模擬自然進(jìn)化過(guò)程搜索最優(yōu)解的方法，該算法具有自組織、自適應(yīng)、自學(xué)習(xí)和群體進(jìn)化功能，有很強(qiáng)的解決問(wèn)題的能力，在許多領(lǐng)域都得到了應(yīng)用。

2.1基本流程

遺傳算法的基本運(yùn)算過(guò)程如下：

(2)個(gè)體適應(yīng)度評(píng)估：計(jì)算群體P(t)中個(gè)體的適應(yīng)性，即滿(mǎn)足目標(biāo)約束的能力。

(3)選擇運(yùn)算：將選擇算子作用于群體，選擇目的是將優(yōu)良個(gè)體直接遺傳到下一代。選擇操作建立在群體中個(gè)體適應(yīng)度評(píng)估的基礎(chǔ)上。

(4)交叉運(yùn)算：將交叉算子作用于群體。交叉是指將兩個(gè)父代個(gè)體的部分結(jié)構(gòu)加以替換，重組生成新個(gè)體的操作。

(5)變異運(yùn)算：將變異算子作用于群體，即修改父代個(gè)體的部分結(jié)構(gòu)操作。

(6)終止條件：群體P(t)經(jīng)過(guò)選擇、交叉和變異操作生成新一代群體P(t+1)。若t=T，則進(jìn)化過(guò)程的中最大適應(yīng)度個(gè)體為最優(yōu)解。

2.2初始種群

對(duì)于虛擬機(jī)放置問(wèn)題：

(1)個(gè)體表示虛擬機(jī)和物理機(jī)的空間布局關(guān)系，是由用戶(hù)指定的。如圖1所示，12臺(tái)虛擬機(jī)和3臺(tái)物理機(jī)至少存在兩種不同的空間布局關(guān)系。

長(zhǎng)期以來(lái)，西部地區(qū)經(jīng)濟(jì)社會(huì)發(fā)展滯后，金融發(fā)展水平薄弱，人力資本存量較低。尤其是當(dāng)前，西部地區(qū)作為區(qū)域協(xié)調(diào)發(fā)展戰(zhàn)略的推進(jìn)方和脫貧攻堅(jiān)戰(zhàn)的主戰(zhàn)場(chǎng)，如何促進(jìn)西部地區(qū)的經(jīng)濟(jì)又好又快發(fā)展成為新時(shí)代的重要課題。因此，現(xiàn)階段從人力資本視角研究西部地區(qū)金融發(fā)展與經(jīng)濟(jì)增長(zhǎng)之間的相互關(guān)系，從而揭示如何實(shí)現(xiàn)西部地區(qū)金融發(fā)展與經(jīng)濟(jì)增長(zhǎng)的良性循環(huán)，對(duì)于我國(guó)繼續(xù)實(shí)施西部大開(kāi)發(fā)戰(zhàn)略、“一帶一路”倡議以及實(shí)現(xiàn)全面建成小康社會(huì)的宏偉目標(biāo)都具有重要的理論和現(xiàn)實(shí)意義。

圖1 基于組編碼的虛擬機(jī)放置

(2)基因表示個(gè)體的組成。如圖1所示，該個(gè)體由3個(gè)基因組成，分別為A、B和C。

(3)種群表示個(gè)體的集合。為了便于算法理解和計(jì)算，種群的一個(gè)關(guān)鍵問(wèn)題是如何高效描述虛擬機(jī)和物理機(jī)空間布局與個(gè)體的映射關(guān)系，即編碼與譯碼問(wèn)題。

編碼目的是構(gòu)建物理機(jī)與虛擬機(jī)空間布局到個(gè)體的表示，通常包括3種遺傳編碼方法：(1)基于箱子的表示；(2)基于物品的表示；(3)基于組的表示。考慮到搜索效果和效率要素，本文采用基于組的編碼方式。比如，圖1所示個(gè)體由3個(gè)基因組成，可表示為A{2，4，7，5}、B{8，10，11，12}、C{1，3，6，9}；圖2所示個(gè)體由3個(gè)基因組成，可表示為A{2，4，7}、B{5，8，10，11，12，1}、C{3，6，9}。

譯碼的目的是將個(gè)體基因快速地轉(zhuǎn)化為物理機(jī)和虛擬機(jī)空間布局表現(xiàn)，它是能否有效執(zhí)行遺傳算法的關(guān)鍵。譯碼采用文獻(xiàn)[7]提出的空間分解方法。考慮到存在CPU、內(nèi)存、網(wǎng)絡(luò)IO和磁盤(pán)IO四種資源，采用四維空間的分割方法。如圖2所示，當(dāng)一個(gè)虛擬機(jī)放入一個(gè)物理節(jié)點(diǎn)時(shí)，該物理節(jié)點(diǎn)被分割成四維空間，即上空間、前空間、左空間和右空間。當(dāng)執(zhí)行選擇、交叉和變異等算子操作，改變虛擬機(jī)在物理節(jié)點(diǎn)上的放置位置時(shí)，虛擬機(jī)必須滿(mǎn)足目標(biāo)物理節(jié)點(diǎn)的空間約束。

圖2 空間分解示意圖

2.3適應(yīng)度函數(shù)

由于個(gè)體表示全局物理機(jī)與虛擬機(jī)的空間布局，因此，適應(yīng)度最高的個(gè)體即為最優(yōu)解。本小節(jié)基于兩階段收益最大化原理構(gòu)建適應(yīng)度函數(shù)。

假設(shè)虛擬化平臺(tái)是由M臺(tái)物理機(jī)PM和N臺(tái)虛擬機(jī)VM構(gòu)成的，對(duì)于當(dāng)前物理機(jī)與虛擬機(jī)的空間布局(假設(shè)運(yùn)行在物理機(jī)i上的虛擬機(jī)集合是VMSetOn(PMi))，每臺(tái)物理機(jī)的收益為Benefit(PMt),1≤t

(1)

由圖3所示可見(jiàn)，物理機(jī)收益與其上部署的虛擬機(jī)及虛擬機(jī)的資源消耗相關(guān)。具體而言，對(duì)于任何一個(gè)采樣點(diǎn)t，可根據(jù)是否違反公式(2)約束，將收益函數(shù)細(xì)分為兩種構(gòu)建方法。

圖3 虛擬機(jī)在線(xiàn)遷移示意圖

(2)

(1)滿(mǎn)足公式(2)約束

此時(shí)物理機(jī)的收益函數(shù)可由公式(3)描述，說(shuō)明物理機(jī)的收益是與多維資源使用的均衡度相關(guān)，且物理機(jī)資源使用越均衡，其收益也越大。例如，CPU、內(nèi)存和網(wǎng)絡(luò)IO的使用率均為50%的場(chǎng)景，要比CPU使用率60%、內(nèi)存使用率40%，而網(wǎng)絡(luò)IO使用率50%的場(chǎng)景更為均衡，收益也越高。

(3)

其中，?i表示收益因子，需要用戶(hù)配置。

(2)不滿(mǎn)足公式(2)約束

此時(shí)物理機(jī)的收益函數(shù)可由公式(4)描述，說(shuō)明物理機(jī)的收益是與違反公式(2)約束的時(shí)間點(diǎn)相關(guān)，且違約的時(shí)間越晚，收益越大。比如，虛擬機(jī)A和B部署在物理機(jī)Server1上，若將虛擬機(jī)A遷移到物理機(jī)Server2，公式(3)違約的時(shí)間點(diǎn)發(fā)生在中午12點(diǎn)；而遷移虛擬機(jī)B，公式(3)違約的時(shí)間點(diǎn)發(fā)生在發(fā)生在下午6點(diǎn)，說(shuō)明遷移虛擬機(jī)A是最優(yōu)的，收益也最大。

(4)

其中，β表示收益因子，N表示每天資源需求采樣點(diǎn)個(gè)數(shù)，t表示公式(4)中發(fā)生第1次違約的采樣點(diǎn)標(biāo)識(shí)。

2.4選擇算子

對(duì)所有個(gè)體按照適應(yīng)度進(jìn)行降序排列，選擇q個(gè)適應(yīng)度最大的個(gè)體作為下一代個(gè)體的輸入?；谶x擇算子的個(gè)體選擇算法如下：第1～10行表示對(duì)當(dāng)前種群中的個(gè)體按照適應(yīng)度從大到小排序。第11行表示從當(dāng)前種群中選擇q個(gè)適應(yīng)度最大的個(gè)體作為下一代種群的輸入。

Generatingnewpopulationsfromselectionoperator

Input：PopulationSizeM;Nextgenerationfromselectionoperatorq；

Fitnessfitness(p)

Output：PopulationPop.

1.intcnt= 0;

2. Randomly generate an initial populationP(0)

3. New population new P, and new P[0]=0

4. fori in newP

5. if new P[i]

6. break;

7.endif

8.insertfitness(cnt)atnewP[i].

9. cnt++;

10.endfor

11. select first p elements ofnewP to the next generation P(1)

2.5交叉算子

交叉是指將兩個(gè)父代個(gè)體的部分結(jié)構(gòu)加以替換，重組生成新個(gè)體的操作。如圖4所示，交換物理機(jī)A和物理機(jī)B上標(biāo)識(shí)為5和12的虛擬機(jī)是一個(gè)具體的交叉實(shí)例。

圖4 交叉過(guò)程

交叉算子需考慮死鎖約束問(wèn)題。由于CPU約束，VM1只有在VM2從物理機(jī)B遷移到物理機(jī)A之后才能從物理機(jī)A遷移到物理機(jī)B。同時(shí)，由于CPU約束，VM2只有在VM1從物理機(jī)機(jī)A遷移到物理機(jī)B之后才能從物理機(jī)B遷移到物理機(jī)A。這樣就形成了遷移死鎖。通過(guò)引入額外的物理機(jī)可打破遷移死鎖現(xiàn)象。具體而言，首先將VM1遷移到引入的物理機(jī)C上，然后將VM2遷移到物理機(jī)A，最后將VM1從物理機(jī)C遷移到物理機(jī)B。

2.6變異算子

變異是指修改父代個(gè)體部分結(jié)構(gòu)的操作，例如個(gè)體indv1={A{2，4 }、B{8，10}}變異成indv2={A{2，7}、B

表2 Web應(yīng)用資源需求分布函數(shù)

{8，10}}。由于個(gè)體組成元素是虛擬機(jī)，虛擬機(jī)不存在憑空創(chuàng)建的可能，因此，變異操作可以看成是特殊的交換操作。

2.7遺傳算法實(shí)現(xiàn)

基于收益最大化的遺傳算法實(shí)現(xiàn)如下：

(1)首先初始化群體P(t)，然后分別將選擇算子、交叉算子和變異算子作用到初始化群體P(t)，得到群體解空間newP，見(jiàn)算法1～18行；

(2)對(duì)群體解空間newP進(jìn)行篩選，選擇依據(jù)是根據(jù)收益最大化原則，見(jiàn)算法12～19行。

Geneticalgorithmbasedonbenefitmaximization

Input：PopulationSizeM;

Probabilityforcrossoveroperatorp1；

Probabilityformutationoperatorp2;

Output：PopulationPop.

1.intt= 0;

2. Randomly generate an initial population P(0)

3. New population new P

4.whilet

5.forindividualpinP(t)

6. Select operation to new P

7.endfor

8.ifrandom (0, 1)

9.forindividualpinP(t)

10. Crossover operation to new P

11.endfor

12.endif

13.ifrandom (0, 1)

14.forindividualpinP(t)

15. Mutation operation to new P

16.endfor

17.endif

18. t=t+1;

19.foriinnew P

20.forj in new P

21.ifbenefit(i)

22. exchange elementsi,j in newP

23.endif

24.endfor

25.endfor

26. select first p elements of new P to the next

generation P(cnt)

27.end

3 結(jié)論

表2給出了應(yīng)用實(shí)例的CPU資源需求分布函數(shù)：TPC-W-1和TPC-W-2的CPU資源需求分別符合偏距為60、振幅為10的正弦和余弦分布；TPC-W-3、TPC-W-4的CPU資源需求則分別穩(wěn)定在50%和40%。

從第15分鐘開(kāi)始，TPC-W-4應(yīng)用部署到虛擬化平臺(tái)中，此時(shí)Server1、Server2和Server3的CPU資源空閑率均為50%。本文采用“隨機(jī)策略”將TPC-W-4應(yīng)用部署并運(yùn)行在Server1上。

從第33分鐘開(kāi)始，TPC-W-1和TPC-W-4的CPU資源需求均為50%， Server1資源供給面臨瓶頸，vMigration平臺(tái)會(huì)觸發(fā)虛擬機(jī)在線(xiàn)遷移操作，根據(jù)遺傳算法的適應(yīng)度函數(shù)，算法會(huì)發(fā)現(xiàn)TPC-W-1遷移到Server3，或者TPC-W-4遷移到Server2，或者TPC-W-4遷移到Server3，都會(huì)違反虛擬機(jī)資源需求小于物理機(jī)資源供給的約束(資源供需平衡約束)。只有TPC-W-1遷移到Server2方案，才能滿(mǎn)足資源供需平衡約束。因此，TPC-W-1遷移到Server2方案的收益是最大的，也是虛擬機(jī)放置的最優(yōu)解。

由此可見(jiàn)，本方法考慮了全局物理機(jī)空間狀態(tài)穩(wěn)定性，能間接打破虛擬機(jī)“循環(huán)遷移”的觸發(fā)條件。

[1] 張梁,羅宇.基于openstack的虛擬機(jī)定時(shí)任務(wù)的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算技術(shù)與自動(dòng)化, 2015,34(2):127-131.

[2] 田苗苗,李俊.面向低能耗的虛擬機(jī)部署和遷移策略[J]. 微型機(jī)與應(yīng)用, 2015,34(18):23-25.

[3] 王加昌，曾輝，何騰蛟，等.面向數(shù)據(jù)中的虛擬機(jī)部署及優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用，2013，33(10)：2772-2777.

[4] 董健康，王洪波.IaaS環(huán)境下改進(jìn)能源效率和網(wǎng)絡(luò)性能的虛擬機(jī)放置方法[J].通信學(xué)報(bào)，2014，35(1)：72-81.

[5] 周舟，胡志剛.云環(huán)境下面向能耗降低的虛擬機(jī)部署算法[J].華南理工大學(xué)學(xué)報(bào)，2014，42(5)：109-114.

[6] 高林，宋相倩，王潔萍.云計(jì)算及其關(guān)鍵技術(shù)研究[J].微型機(jī)與應(yīng)用，2011，30(10)：5-7.

[7] 李松，羅勇，張銘銳.遺傳算法優(yōu)化BP神經(jīng)網(wǎng)絡(luò)的混沌時(shí)間序列預(yù)測(cè)[J].計(jì)算機(jī)工程與應(yīng)用，2011，47(29)：52-55.

Virtual machine live migration optimization method based on genetic algorithm

Liu Chang

(State Grid Jibei Electric Power Co., Ltd., Qinhuadao Power Supply Company, Qinhuangdao 066000, China)

TP311

A

10.19358/j.issn.1674- 7720.2017.18.007

劉暢.基于遺傳算法的虛擬機(jī)在線(xiàn)遷移優(yōu)化方法[J].微型機(jī)與應(yīng)用，2017,36(18)：22-25，29.

2017-03-28)

劉暢(1974-)，通信作者，男，本科，工程師，主要研究方向：信息安全等。E-mail:101378822@qq.com。