劉 暢

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

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

劉 暢

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

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

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

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

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

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

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

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

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

(2)四個TPC-W應(yīng)用實例，假設(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)用實例的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ī)在線遷移流程：

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

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

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

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

2 遺傳算法設(shè)計

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

2.1基本流程

遺傳算法的基本運算過程如下：

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

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

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

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

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

2.2初始種群

對于虛擬機(jī)放置問題：

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

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

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

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

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

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

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

圖2 空間分解示意圖

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

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

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

(1)

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

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

(2)

(1)滿足公式(2)約束

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

(3)

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

(2)不滿足公式(2)約束

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

(4)

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

2.4選擇算子

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

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交叉算子

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

圖4 交叉過程

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

2.6變異算子

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

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

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

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

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

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

(2)對群體解空間newP進(jìn)行篩選，選擇依據(jù)是根據(jù)收益最大化原則，見算法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)用實例的CPU資源需求分布函數(shù)：TPC-W-1和TPC-W-2的CPU資源需求分別符合偏距為60、振幅為10的正弦和余弦分布；TPC-W-3、TPC-W-4的CPU資源需求則分別穩(wěn)定在50%和40%。

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

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

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

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

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

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

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

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

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

[7] 李松，羅勇，張銘銳.遺傳算法優(yōu)化BP神經(jīng)網(wǎng)絡(luò)的混沌時間序列預(yù)測[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ī)在線遷移優(yōu)化方法[J].微型機(jī)與應(yīng)用，2017,36(18)：22-25，29.

2017-03-28)

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