趙　勉,李　燁

(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院,上?！?00093)

?

基于Q-Learning的虛擬機(jī)動(dòng)態(tài)伸縮算法

趙勉,李燁

(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院,上海200093)

摘要針對(duì)大規(guī)模云環(huán)境中業(yè)務(wù)量變化時(shí)平臺(tái)服務(wù)質(zhì)量和資源消耗的問(wèn)題,提出一種基于Q-Learning的虛擬機(jī)擴(kuò)容/縮容決策算法。將該問(wèn)題轉(zhuǎn)換為馬爾科夫決策模型,為了在業(yè)務(wù)平臺(tái)服務(wù)質(zhì)量和資源消耗之間取得較好的平衡,智能體根據(jù)平臺(tái)當(dāng)前狀態(tài)計(jì)算出最佳策略,執(zhí)行決策并轉(zhuǎn)到下一狀態(tài)。仿真結(jié)果表明,該算法可根據(jù)業(yè)務(wù)量的變化實(shí)時(shí)作出伸縮決策,并提供最合適的虛擬機(jī)資源以滿足業(yè)務(wù)需求,且能提高平臺(tái)的穩(wěn)定性。

關(guān)鍵詞云計(jì)算;虛擬機(jī);動(dòng)態(tài)伸縮;Q-Learning;資源利用率

Q-Learning Based Auto-scaling Algorithm for Virtual Machines

ZHAO Mian,LI Ye

(School of Optical-Electrical and Computer Engineering,University of Shanghai for Science and Technology,Shanghai 200093,China)

AbstractTo solve the problem of service quality and resources cost when the service volume changed in large cloud environment,this paper proposes a scaling method for virtual machines based on the Q-Learning algorithm.First,the problem is modeled as a Markov decision process.In order to achieve a better balance between platform service quality and resources consuming,the agent outputs the best decision according to the current state of the platform.The platform executes the decision and transfers to the corresponding state.The simulation results show that the method can make scaling decisions in real time according to the change of service volume so as to provide appropriate resources of virtual machines matching the requirements of service.The method also can enhance the stability of the platform.

Keywordscloud computing;virtual machine;auto-scaling;Q-Learning;resource utilization

一個(gè)良好的云計(jì)算平臺(tái)應(yīng)該具有高可擴(kuò)展性、高可用性、高可靠性、能按需分配資源和負(fù)載均衡等特性?？缮炜s性是分布式及并行計(jì)算中的重要指標(biāo)之一,描述了應(yīng)用系統(tǒng)通過(guò)改變可用硬件資源和調(diào)度方式來(lái)動(dòng)態(tài)調(diào)整自身整體性能的能力[1]。在大規(guī)模虛擬環(huán)境系統(tǒng)中,利用云計(jì)算可伸縮性的特點(diǎn),可根據(jù)業(yè)務(wù)的資源需求動(dòng)態(tài)伸縮平臺(tái)資源,降低運(yùn)營(yíng)成本,提高資源利用率。

可伸縮性是當(dāng)前云計(jì)算的研究熱點(diǎn)[2-3]。CloudScale[4]應(yīng)用快速傅里葉變換識(shí)別資源并預(yù)測(cè)周期性的資源需求,以實(shí)現(xiàn)云平臺(tái)資源的動(dòng)態(tài)伸縮。在文獻(xiàn)[5]中,利用自回歸滑動(dòng)平均模型預(yù)測(cè)虛擬機(jī)負(fù)載以減少資源消耗。文獻(xiàn)[6~7]提出了混合多種算法的模型來(lái)預(yù)測(cè)虛擬機(jī)數(shù)量需求,能根據(jù)預(yù)測(cè)誤差自動(dòng)選擇最優(yōu)算法。這些根據(jù)預(yù)測(cè)實(shí)現(xiàn)的虛擬機(jī)伸縮方法對(duì)歷史負(fù)載信息的依賴較大,系統(tǒng)運(yùn)行初期預(yù)測(cè)不夠準(zhǔn)確。文獻(xiàn)[8]提出用門限值算法實(shí)現(xiàn)虛擬機(jī)的動(dòng)態(tài)伸縮,雖然該算法目前應(yīng)用較多,但由于門限值算法每次增加或減少的虛擬機(jī)個(gè)數(shù)固定,會(huì)出現(xiàn)平臺(tái)資源不夠或資源浪費(fèi)情況。因此,需要一種能夠根據(jù)業(yè)務(wù)資源變化適當(dāng)增加或減少虛擬機(jī)的算法,以使平臺(tái)既能滿足業(yè)務(wù)需求,又能有較高的資源利用率。

本文提出一種基于Q-Learning的虛擬機(jī)動(dòng)態(tài)伸縮算法。該算法不僅考慮了系統(tǒng)的業(yè)務(wù)需求和資源利用率,同時(shí)考慮了平臺(tái)的穩(wěn)定性。

1算法描述

1.1Q-Learning理論

Q-Learning是一種無(wú)模型、無(wú)監(jiān)督的在線強(qiáng)化學(xué)習(xí)算法。當(dāng)智能體每選擇一個(gè)動(dòng)作后,環(huán)境會(huì)給以正反饋或負(fù)反饋以表示當(dāng)前動(dòng)作正確與否。一般用Q-Learning解決的問(wèn)題均可轉(zhuǎn)換成馬爾科夫決策過(guò)程模型,即由環(huán)境狀態(tài)集合S={s1,s2,…,st,…,sn}、動(dòng)作集合A={a1,a2,…,at,…,an}和學(xué)習(xí)者的決策策略π:S→A等組成[9]。學(xué)習(xí)者能感知到當(dāng)前環(huán)境的狀態(tài)st,從動(dòng)作集合中選取動(dòng)作at,而環(huán)境根據(jù)智能體輸出的動(dòng)作at計(jì)算出一個(gè)回報(bào)值rt評(píng)判當(dāng)前選擇動(dòng)作的好壞。若回報(bào)值為正,則當(dāng)前動(dòng)作使系統(tǒng)狀態(tài)更優(yōu);若回報(bào)值為負(fù),則選擇該動(dòng)作時(shí)系統(tǒng)狀態(tài)性能下降。當(dāng)動(dòng)作集合有不止一個(gè)元素時(shí),回報(bào)值為正的越大越好。智能體通過(guò)不斷的學(xué)習(xí)優(yōu)化一個(gè)可迭代計(jì)算的Q函數(shù)以提高學(xué)習(xí)能力,學(xué)習(xí)的最終目標(biāo)是找到每個(gè)狀態(tài)下的最佳策略以最大化累計(jì)回報(bào),即

(1)

1.2虛擬機(jī)數(shù)量伸縮算法建模

虛擬機(jī)數(shù)量伸縮問(wèn)題可建模成馬爾科夫決策過(guò)程M=〈S,A,T,R〉,模型如圖1所示。

圖1　業(yè)務(wù)平臺(tái)的虛擬機(jī)伸縮模型

業(yè)務(wù)平臺(tái)的虛擬機(jī)伸縮問(wèn)題對(duì)應(yīng)馬爾科夫決策模型中的狀態(tài)集合S、動(dòng)作集合A、轉(zhuǎn)移概率T和回報(bào)函數(shù)R分別如下:(1)狀態(tài)集合S由n個(gè)狀態(tài)構(gòu)成,每個(gè)狀態(tài)可根據(jù)平臺(tái)的業(yè)務(wù)量、資源消耗和資源利用率得到,在t時(shí)刻系平臺(tái)的狀態(tài)記為st;(2)動(dòng)作集合A由n個(gè)動(dòng)作組成,每個(gè)動(dòng)作代表增加或減少虛擬機(jī)的個(gè)數(shù),其值可為正值、零或負(fù)值;(3)表示在某一狀態(tài)si下選擇動(dòng)作ai后跳轉(zhuǎn)到下一狀態(tài)的概率,本算法狀態(tài)中為確定性轉(zhuǎn)移;(4)回報(bào)函數(shù)R。其定義是決策策略好壞的關(guān)鍵,一個(gè)好的回報(bào)函數(shù)能夠讓結(jié)果更接近目標(biāo)值。

回報(bào)函數(shù)可定義為

(2)

式中

(3)

(4)

1.3虛擬機(jī)數(shù)量伸縮算法流程

Q-Learning算法主要通過(guò)回報(bào)函數(shù)選取最優(yōu)動(dòng)作使系統(tǒng)獲得的累計(jì)回報(bào)值最大,基于Q-Learning算法的虛擬機(jī)伸縮算法流程如下:(1)初始化。初始化Q表為零矩陣,獲取α、γ值,根據(jù)系統(tǒng)資源消耗、資源利用率初始化第一個(gè)系統(tǒng)狀態(tài);(2)動(dòng)作的選擇和執(zhí)行;從動(dòng)作集合中選擇某一動(dòng)作,當(dāng)前狀態(tài)執(zhí)行該動(dòng)作后進(jìn)入下一狀態(tài);(3)獲取回報(bào)。系統(tǒng)選擇某一動(dòng)作后根據(jù)式(2)計(jì)算回報(bào)值;(4)根據(jù)式(1)計(jì)算選擇該動(dòng)作的累計(jì)回報(bào)值;(5)重復(fù)步驟(2)~步驟(4)直至計(jì)算完所有動(dòng)作的累計(jì)回報(bào)值;(6)參數(shù)更新。更新Q表,選擇最大累計(jì)回報(bào)值對(duì)應(yīng)的動(dòng)作作為決策結(jié)果,系統(tǒng)狀態(tài)執(zhí)行該動(dòng)作并進(jìn)入下一狀態(tài)。

2算法結(jié)果驗(yàn)證與分析

2.1仿真場(chǎng)景設(shè)計(jì)

如圖2所示,在200min之前,業(yè)務(wù)量呈現(xiàn)平穩(wěn)狀態(tài);在200~290min之間,業(yè)務(wù)量逐漸上升;隨后,系統(tǒng)業(yè)務(wù)量出現(xiàn)振蕩;從620min開(kāi)始業(yè)務(wù)量又趨平穩(wěn);而在700min后的一段時(shí)間業(yè)務(wù)量出現(xiàn)很大抖動(dòng),之后業(yè)務(wù)量逐漸下降。仿真場(chǎng)景包括了實(shí)際業(yè)務(wù)可能出現(xiàn)的各種典型情形。

圖2　業(yè)務(wù)量變化圖

2.2仿真準(zhǔn)備

設(shè)定每臺(tái)虛擬機(jī)容量為4 500 MB,動(dòng)作集合A={-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6},系統(tǒng)可容納最多12臺(tái)虛擬機(jī),資源利用率上限設(shè)為0.8。首先需確定學(xué)習(xí)速率α和折現(xiàn)因子γ,平臺(tái)資源消耗量越近業(yè)務(wù)量則資源利用率更高,若資源消耗量小于業(yè)務(wù)量則表示違約,伸縮次數(shù)越少則系統(tǒng)越穩(wěn)定。不同α和γ取值對(duì)應(yīng)不同的資源消耗量、不同的伸縮次數(shù)。令γ=0.5,不同α值的仿真結(jié)果如圖3所示。從圖3(a)~圖3(e)可見(jiàn),資源消耗量都大于業(yè)務(wù)量,說(shuō)明系統(tǒng)伸縮后的資源能滿足業(yè)務(wù)需求,即均沒(méi)有違約次數(shù);在平臺(tái)業(yè)務(wù)量變化時(shí)只有α=0.1和α=0.3時(shí)資源消耗量及時(shí)變化,但從圖3(a)和圖3(b)中可看出,α=0.1的伸縮次數(shù)比α=0.3的伸縮次數(shù)多,伸縮次數(shù)越多就會(huì)導(dǎo)致平臺(tái)不穩(wěn)定,故可取α=0.3。

圖3　不同α值對(duì)應(yīng)的資源消耗量

此時(shí)取不同的γ,對(duì)應(yīng)的仿真結(jié)果如圖4所示。從圖中可看出,資源消耗量均大于業(yè)務(wù)量,說(shuō)明均沒(méi)有違約次數(shù);γ越大,伸縮次數(shù)越多,系統(tǒng)振蕩越多,也就越不穩(wěn)定。因此,可取γ=0.1。

圖4　不同γ值對(duì)應(yīng)的資源消耗量圖

2.3算法對(duì)比研究

與廣泛應(yīng)用的門限值算法比較。門限值算法中設(shè)置了高門限和低門限,當(dāng)平臺(tái)資源利用率高于高門限值時(shí),平臺(tái)增加虛擬機(jī);當(dāng)平臺(tái)資源利用率低于低門限值時(shí),平臺(tái)減少虛擬機(jī);其中平臺(tái)每次增加或減少的虛擬機(jī)個(gè)數(shù)固定。若高門限值設(shè)置為平臺(tái)資源利用率上限,則在業(yè)務(wù)量突然增加很多且持續(xù)一段時(shí)間時(shí),因平臺(tái)每次增加的資源有限,一段時(shí)間之后平臺(tái)資源才能增加到目標(biāo)值,故平臺(tái)反應(yīng)較慢且違約次數(shù)較多,同樣當(dāng)業(yè)務(wù)量突然減少時(shí),平臺(tái)也不能及時(shí)減少足夠多的虛擬機(jī)這樣會(huì)造成資源浪費(fèi)。綜合以上原因,為使平臺(tái)有較高的資源利用率且違約次數(shù)較低,門限值算法的上下門限取值分別為0.75和0.64。仿真結(jié)果如圖5～圖7所示。

如圖5所示,隨著仿真周期的增加,兩種方法的伸縮次數(shù)都逐漸增加,在第11個(gè)周期結(jié)束時(shí),門限值算法和Q-Learning算法計(jì)算的伸縮次數(shù)分別為991和834,Q-Learning算法略優(yōu),系統(tǒng)更穩(wěn)定。此時(shí)如圖6所示,門限值算法的違約次數(shù)為187,而Q-Learning算法沒(méi)有違約,這說(shuō)明業(yè)務(wù)平臺(tái)用Q-Learning算法實(shí)現(xiàn)的資源伸縮能夠滿足業(yè)務(wù)需求。從圖7比較,Q-Learning算法計(jì)算的系統(tǒng)資源利用率從0.715 1逐漸上升在第6個(gè)周期后趨于平穩(wěn)值0.715 5,而門限值算法資源利用率從0.698 5逐漸上升在第9個(gè)周期后趨于平穩(wěn)值0.699 2,可看出Q-Learning算法收斂較快且資源利用率較高。

圖5　伸縮次數(shù)對(duì)比圖

圖6　違約次數(shù)對(duì)比圖

圖7　資源利用率對(duì)比圖

3結(jié)束語(yǔ)

提出了一種基于Q-Learning的虛擬機(jī)數(shù)量伸縮算法,該算法旨在業(yè)務(wù)量變化時(shí)提高系統(tǒng)服務(wù)質(zhì)量并提高資源利用率。仿真結(jié)果表明,與應(yīng)用廣泛的門限值算法相比,該算法伸縮次數(shù)較少、違約次數(shù)為零、資源利用率較高,即不僅能以消耗較少資源滿足業(yè)務(wù)需求,還能使系統(tǒng)更為穩(wěn)定,在系統(tǒng)性能和資源消耗之間獲得了很好的平衡效果。

參考文獻(xiàn)

[1]劉冬.云計(jì)算環(huán)境下可伸縮實(shí)時(shí)在線交互應(yīng)用關(guān)鍵技術(shù)研究[D].廣州:華南理工大學(xué),2014.

[2]李喬,鄭嘯.云計(jì)算研究現(xiàn)狀綜述[J].計(jì)算機(jī)科學(xué),2011,38(4):32-37.

[3]葉可江,吳朝暉,姜曉紅,等.虛擬化云計(jì)算平臺(tái)的能耗管理[J].計(jì)算機(jī)學(xué)報(bào),2012,35(6):1262-1285.

[4]Caron E,Desprez F,Muresan A.Forecasting for Cloud computing on-demand resources based on pattern matching[J].HAL-INRIA,2010(3):456-463.

[5]Gong Z,Gu X,Wilkes J.PRESS:PRedictive elastic resource scaling for cloud systems[C].Haikou:2010 International Conference on Network and Service Management (CNSM),IEEE,2010.

[6]Lagar-Cavilla H A,Whitney J A,Scannell A M,et al.Snow Flock:rapid virtual machine cloning for cloud computing[C].Beijing:Proceedings of the 4th ACM European Conference on Computer Systems.ACM,2009.

[7]Zhu J,Jiang Z,Xiao Z.Twinkle:A fast resource provisioning mechanism for internet services[C].Guangzhou:INFOCOM Proceedings IEEE,2011.

[8]Bhise V K,Mali A S.EC2 instance provisioning for cost optimization[C].Shenzhen:International Conference on Advances in Computing,Communications and Informatics(ICACCI),IEEE,2013.

[9]李俊濤,周其力.基于改進(jìn)分組遺傳算法的虛機(jī)初始化放置算法[J].電子科技,2015,28(6):17-20.

中圖分類號(hào)TP391

文獻(xiàn)標(biāo)識(shí)碼A

文章編號(hào)1007-7820(2016)03-035-04

doi:10.16180/j.cnki.issn1007-7820.2016.03.009

作者簡(jiǎn)介:趙勉(1989—),女,碩士研究生。研究方向:通信技術(shù)。

收稿日期:2015- 07- 13