一種基于強(qiáng)化學(xué)習(xí)的云應(yīng)用彈性伸縮算法

帥 斌 龍士工

(貴州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 貴州 貴陽(yáng) 550025) (貴州省公共大數(shù)據(jù)重點(diǎn)實(shí)驗(yàn)室 貴州 貴陽(yáng) 550025)

0 引 言

云計(jì)算技術(shù)是當(dāng)前流行的并正在發(fā)展的技術(shù),云計(jì)算主要有三個(gè)市場(chǎng)：基礎(chǔ)設(shè)施作為服務(wù)(IaaS)、平臺(tái)即服務(wù)(PaaS)、軟件即服務(wù)(SaaS)。云計(jì)算的特點(diǎn)之一就是彈性,這使得云用戶(hù)可以根據(jù)自己的業(yè)務(wù)需求動(dòng)態(tài)地增加或釋放計(jì)算機(jī)資源,并且用戶(hù)只需要為自己正在使用的資源付費(fèi),而正是由于這個(gè)特性,吸引著Web應(yīng)用的服務(wù)商把他們的應(yīng)用移動(dòng)到云上來(lái)。比如網(wǎng)站Groupon就把自己的網(wǎng)站部署到了Amazon EC2(IaaS)和Force.com(PaaS)這兩個(gè)云服務(wù)提供商的云上。

基礎(chǔ)設(shè)施服務(wù)(IaaS)提供商的彈性功能分為兩類(lèi)：提供給用戶(hù)需要的一類(lèi)資源(如網(wǎng)絡(luò)帶寬、CPU、存儲(chǔ)等)為垂直彈性；提供實(shí)例(虛擬機(jī)或容器)為橫向彈性。因此有效地利用云的彈性功能,能夠自動(dòng)和及時(shí)地提供和釋放云資源是至關(guān)重要的。如果提供的資源過(guò)多,那么會(huì)造成資源閑置形成資源浪費(fèi),同時(shí)需要支付的成本也增加了。然而如果提供的資源過(guò)少,會(huì)使得應(yīng)用的性能下降,響應(yīng)時(shí)間變長(zhǎng),造成用戶(hù)服務(wù)協(xié)議(SLA)違約。這種使得云用戶(hù)能夠有最少的管理,同云服務(wù)提供商有最少的交互就能實(shí)現(xiàn)動(dòng)態(tài)地增加或釋放資源,并且能滿(mǎn)足用戶(hù)服務(wù)質(zhì)量(QoS)的是彈性伸縮技術(shù)[1]。

現(xiàn)在云計(jì)算中能實(shí)現(xiàn)彈性伸縮的方法有多種,其中比較傳統(tǒng)的是基于閾值的方法,該方法主要通過(guò)提前設(shè)定好閾值來(lái)調(diào)整云資源,如文獻(xiàn)[2-4]。另一種實(shí)現(xiàn)彈性伸縮的是基于時(shí)間序列分析的方法,如文獻(xiàn)[5]中通過(guò)自回歸預(yù)測(cè)與指數(shù)平滑和前饋(BP)人工神經(jīng)網(wǎng)絡(luò)提出了一個(gè)基于需求預(yù)測(cè)的云計(jì)算彈性伸縮策略,文獻(xiàn)[6]提出了一個(gè)基于指數(shù)平滑法的預(yù)測(cè)模型,文獻(xiàn)[7]中以差分自回歸移動(dòng)平均模型進(jìn)行負(fù)載預(yù)測(cè)。文獻(xiàn)[8]以時(shí)間序列分析與閾值的混合方法提出一個(gè)預(yù)測(cè)模型。

強(qiáng)化學(xué)習(xí)相對(duì)閾值與時(shí)間序列分析的優(yōu)點(diǎn)是當(dāng)負(fù)載規(guī)律變化時(shí)能動(dòng)態(tài)地調(diào)整策略,重新在環(huán)境中學(xué)習(xí)達(dá)到最優(yōu)策略。文獻(xiàn)[9-11]提出使用Q-學(xué)習(xí)算法實(shí)現(xiàn)彈性伸縮,文獻(xiàn)[12]對(duì)SaaS云服務(wù)提供商的彈性伸縮策略使用了Q-學(xué)習(xí)算法,文獻(xiàn)[13-14]對(duì)數(shù)據(jù)流處理應(yīng)用實(shí)現(xiàn)彈性提出有模型的強(qiáng)化學(xué)習(xí),文獻(xiàn)[15]通過(guò)減少狀態(tài)集使Q-學(xué)習(xí)算法更快達(dá)到收斂。

僅有少部分研究Q-學(xué)習(xí)算法的收斂問(wèn)題,如文獻(xiàn)[14-15]。此外,幾乎所有研究使用的都是單步更新的Q-學(xué)習(xí)算法[9-15],缺少多步更新算法的優(yōu)勢(shì)。

因此本文對(duì)IaaS云服務(wù)提供商上Web應(yīng)用的彈性問(wèn)題進(jìn)行了研究建模,提出一種基于強(qiáng)化學(xué)習(xí)的彈性伸縮算法PDS-lambda。該算法只學(xué)習(xí)動(dòng)態(tài)未知的信息,同時(shí)采用多步更新,旨在使算法更快收斂到最優(yōu)策略,最后通過(guò)仿真實(shí)驗(yàn)同文獻(xiàn)[15]的Q-學(xué)習(xí)算法和文獻(xiàn)[14]的PDS單步更新算法的性能進(jìn)行了對(duì)比。

1 問(wèn)題建模

1.1 架構(gòu)設(shè)計(jì)

為了及時(shí)和自動(dòng)地增加或減少虛擬機(jī)(VM),來(lái)應(yīng)對(duì)Web應(yīng)用迅速變化的負(fù)載,本文對(duì)Web應(yīng)用的彈性伸縮策略如圖1所示。

圖1 云資源彈性伸縮架構(gòu)

負(fù)載均衡器是Web應(yīng)用的入口,它接收所有用戶(hù)的請(qǐng)求,將其分配到已安裝Web應(yīng)用程序的VM上,然后將響應(yīng)發(fā)送回用戶(hù)。當(dāng)管理服務(wù)器增加或減少VM時(shí),負(fù)載均衡器還必須更新VM表,并調(diào)整負(fù)載平衡策略。

管理服務(wù)器包括監(jiān)視系統(tǒng)和云資源管理系統(tǒng)。監(jiān)視系統(tǒng)持續(xù)監(jiān)視Web應(yīng)用的用戶(hù)請(qǐng)求,收集用戶(hù)服務(wù)協(xié)議(SLA)違約和虛擬機(jī)使用信息。云資源管理系統(tǒng)在每個(gè)時(shí)間段對(duì)監(jiān)視系統(tǒng)得到的信息進(jìn)行算法分析,根據(jù)算法結(jié)果對(duì)IaaS云服務(wù)提供商進(jìn)行租賃，采取合適的彈性擴(kuò)張操作或直接采取彈性收縮操作來(lái)調(diào)整其擁有的VM數(shù)量,并將改變后的VM表發(fā)送給負(fù)載均衡器。本文把以上過(guò)程模型化為馬爾可夫決策過(guò)程(MDP)。

1.2 MDP

定義1MDP為6元組〈S,A,P,R,α,β〉,S表示有限狀態(tài)集,A(s)為每個(gè)狀態(tài)s的有限動(dòng)作集,P(s′|s,a)為在狀態(tài)s選擇動(dòng)作a∈A(s)轉(zhuǎn)移到狀態(tài)s′的概率,R(s,a)為在狀態(tài)s采取動(dòng)作a的成本,α∈[0,1]是學(xué)習(xí)率,β∈[0,1]是未來(lái)成本的折扣因子。

在狀態(tài)st=(1,wt)時(shí),動(dòng)作集為A(s)∈(0,+1)；狀態(tài)st=(Umax,wt)時(shí),動(dòng)作集為A(s)∈(0,-1)；除此之外每個(gè)狀態(tài)s的動(dòng)作集為A(s)∈(+1,0,-1)。Web應(yīng)用在時(shí)刻t開(kāi)始時(shí)選擇動(dòng)作+1、0、-1分別代表增加虛擬機(jī)、不改變、減少虛擬機(jī)。

由于狀態(tài)中的HTTP請(qǐng)求到達(dá)速度無(wú)法確定,因此在狀態(tài)s下采取動(dòng)作a后轉(zhuǎn)移到狀態(tài)s′的狀態(tài)轉(zhuǎn)移概率與HTTP請(qǐng)求到達(dá)速度有關(guān),因此P(s|s′,a)：

(1)

對(duì)每個(gè)狀態(tài)-動(dòng)作對(duì)的成本R(s,a)的評(píng)估,從三個(gè)方面來(lái)進(jìn)行考慮：

1) 運(yùn)行虛擬機(jī)的成本,運(yùn)行u+a個(gè)虛擬機(jī)的總成本為cVM(s,a),運(yùn)行每個(gè)VM的成本為rVM,則運(yùn)行u+a個(gè)虛擬機(jī)的成本為cVM(s,a)=(u+a)rVM。

2) 重新配置成本,無(wú)論什么時(shí)候進(jìn)行彈性擴(kuò)張或彈性收縮操作時(shí),Web應(yīng)用都會(huì)經(jīng)歷一個(gè)十分短暫的停機(jī)的時(shí)間,這段時(shí)間不會(huì)處理請(qǐng)求,盡管這段時(shí)間會(huì)非常小,但對(duì)于一個(gè)穩(wěn)定的應(yīng)用來(lái)說(shuō)這仍然不可忽視。把動(dòng)作-1、+1成本考慮為一個(gè)常量rRC。

3) SLA違約成本,請(qǐng)求的響應(yīng)時(shí)間超過(guò)SLA違約的時(shí)間閾值TSLA時(shí),會(huì)獲得一個(gè)SLA違約成本,考慮該成本為一個(gè)常量rSLA。

對(duì)上述三個(gè)成本進(jìn)行歸一化處理后使用簡(jiǎn)單加權(quán)和法,獲得狀態(tài)-動(dòng)作對(duì)的成本R(s,a)為：

WSLA1{T(u,w)>TSLA}

(2)

式中：WVM+WRC+WSLA=1，代表上述三個(gè)成本的權(quán)重值其和為1。1{a≠0}表示當(dāng)采取動(dòng)作a=0時(shí)取值為0,而當(dāng)采取動(dòng)作a=+1,-1時(shí)取值為1；1{T(u,w)>TSLA}表示當(dāng)沒(méi)有產(chǎn)生SLA違約時(shí)取值為0,而當(dāng)有SLA違約時(shí)取值為1。

MDP是算法與Web應(yīng)用之間通過(guò)動(dòng)作a、狀態(tài)s、和成本R相互循環(huán)作用的過(guò)程。圖2展示了MDP空間過(guò)程,在時(shí)刻t,算法從Web應(yīng)用得到狀態(tài)st與成本Rt,作出決策動(dòng)作at,在t+1時(shí)刻Web應(yīng)用反饋給算法新的狀態(tài)st+1,和成本Rt+1。

圖2 MDP空間過(guò)程

圖3展示了MDP的時(shí)間過(guò)程,隨著時(shí)間增加,狀態(tài)也隨之不斷變化,時(shí)間越長(zhǎng)狀態(tài)越多算法學(xué)習(xí)到的信息越多。

圖3 MDP時(shí)間過(guò)程

2 算法描述

算法是MDP的核心,這一部分將著重介紹本文提出的PDS-lambda算法。由式(1)知模型中狀態(tài)轉(zhuǎn)移概率并不確定,與請(qǐng)求到達(dá)速度變化有關(guān),而請(qǐng)求到達(dá)速度的變化是完全隨機(jī)的過(guò)程,強(qiáng)化學(xué)習(xí)中的時(shí)序差分(TD)算法的思想能解決狀態(tài)轉(zhuǎn)移概率不確定的問(wèn)題,TD算法需要在環(huán)境中不斷采取動(dòng)作然后觀測(cè)狀態(tài)-動(dòng)作產(chǎn)生的成本,來(lái)更新?tīng)顟B(tài)-動(dòng)作值函數(shù)Q(s,a)。

TD中典型的Q-學(xué)習(xí)算法需要不斷維護(hù)一個(gè)Q表,在每個(gè)時(shí)刻采取相應(yīng)的動(dòng)作a,在Q-學(xué)習(xí)算法中選取動(dòng)作a的方法是γ-貪婪策略即以1-γ的概率隨機(jī)選取一個(gè)動(dòng)作,以γ的概率選取最優(yōu)的Q(s,a)值,然后觀察狀態(tài)-動(dòng)作對(duì)產(chǎn)生的回報(bào)R(s,a)來(lái)對(duì)Q表進(jìn)行更新。對(duì)Q表的更新公式如下：

Q(s,a)←Q(s,a)+α[R(s,a)+

(3)

本文中PDS-lambda算法是在TD算法的思想上建立的,PDS-lambda算法同TD算法一樣需要不斷維護(hù)一個(gè)具有狀態(tài)-動(dòng)作值函數(shù)Q(s,a)的Q表,但本文算法同TD算法的不同之處在于對(duì)Q表的更新方法不同,其次本文算法的學(xué)習(xí)策略即在每個(gè)時(shí)刻選取動(dòng)作a的方法也不同。

PDS-lambda算法將由下面兩個(gè)部分進(jìn)行描述,第一部分引入了PDS實(shí)現(xiàn)對(duì)Q表更新方法的第一次改進(jìn),并且介紹了本算法的學(xué)習(xí)策略；第二部分引入多步更新的思想在PDS的基礎(chǔ)上實(shí)現(xiàn)對(duì)Q表更新方法的第二次改進(jìn)。

2.1 PDS與學(xué)習(xí)策略

PDS-lambda算法在每個(gè)時(shí)刻t的末尾根據(jù)上一個(gè)狀態(tài)st=(ut,wt)采取動(dòng)作a∈A(st)后轉(zhuǎn)移到下一個(gè)狀態(tài)st+1=(ut+1,wt+1)。但狀態(tài)的轉(zhuǎn)移過(guò)程是需要時(shí)間的，不能立刻觀測(cè)到,其中Web應(yīng)用在狀態(tài)st+1的虛擬機(jī)數(shù)量ut+1可以根據(jù)采取的動(dòng)作a直接獲得,而請(qǐng)求到達(dá)速度wt+1是無(wú)法預(yù)知的，只有時(shí)刻t+1快結(jié)束時(shí)才能獲得它的值。因此本文的算法在狀態(tài)st和狀態(tài)st+1之間引入了決策后狀態(tài)(PDS),來(lái)改變對(duì)Q表的更新方式。

圖4 當(dāng)前狀態(tài)與PDS和下一狀態(tài)關(guān)系

(4)

(5)

(6)

(7)

PDS-Lambda算法的學(xué)習(xí)策略決定了在每個(gè)時(shí)刻對(duì)當(dāng)前狀態(tài)應(yīng)該選取哪個(gè)動(dòng)作。HTTP請(qǐng)求到達(dá)速度并不會(huì)因采取的動(dòng)作不同而改變,因此PDS-Lambda算法只需要學(xué)習(xí)HTTP請(qǐng)求到達(dá)速度這個(gè)未知?jiǎng)討B(tài)信息,不需要隨機(jī)探索的動(dòng)作,在學(xué)習(xí)階段中該算法采取的學(xué)習(xí)策略只需不斷選取最優(yōu)。算法的學(xué)習(xí)策略π(s)如下：

(8)

式(8)表示在每個(gè)狀態(tài)下選取有最小Q函數(shù)值的動(dòng)作。

2.2 多步更新

(9)

式(9)表示在當(dāng)前時(shí)刻的狀態(tài)與遍歷表所得的狀態(tài)不同時(shí),便進(jìn)行衰減,而當(dāng)前時(shí)刻的狀態(tài)與遍歷表得到的狀態(tài)相同時(shí)便進(jìn)行一次標(biāo)記。由式(7)可得TD誤差δ為：

(10)

(11)

PDS-Lambda算法的偽代碼如算法1所示。

算法1PDS-Lambda算法

輸入 起始狀態(tài)-s0折扣因子-β

學(xué)習(xí)率-α衰減因子-λ

2.s=s0;

//初始化狀態(tài)

3. fort=1,2,3,... do

//每個(gè)時(shí)刻進(jìn)行學(xué)習(xí)

4.a=π(s);

//式(8)

//式(10)

//式(9)

//式(11)

//式(9)

11. end for

12. forai∈A(s) do

//式(6)

14. end for

15.s←s′;

//轉(zhuǎn)換狀態(tài)

16. end for

3 仿真實(shí)驗(yàn)

3.1 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)采用云平臺(tái)模擬軟件cloudsim[16]進(jìn)行仿真,從而對(duì)算法的性能進(jìn)行評(píng)估。在這個(gè)部分對(duì)Q-學(xué)習(xí)算法[15]、PDS單步更新算法[14]、PDS-lambda多步更新算法進(jìn)行仿真。實(shí)驗(yàn)環(huán)境如下,用cloudsim模擬器創(chuàng)建一個(gè)有20臺(tái)主機(jī)的數(shù)據(jù)中心,一個(gè)代理(broker),在這里broker可以模擬為Web應(yīng)用,在開(kāi)始時(shí)broker擁有5個(gè)VM,每個(gè)VM的CPU(MIPS)為1 000。

圖5 負(fù)載變化趨勢(shì)

設(shè)置SLA的違約時(shí)間為10 s,請(qǐng)求的最大響應(yīng)時(shí)間超過(guò)這個(gè)值時(shí)就會(huì)導(dǎo)致一個(gè)處罰。設(shè)置學(xué)習(xí)率α=0.6,折扣因子β=0.8,衰減系數(shù)λ=0.8,實(shí)例成本、重新配置成本和SLA違約成本的權(quán)重各為：

WVM=2/5,Wrc=1/5,WSLA=2/5

本文使用平均成本(average cost,AC)來(lái)評(píng)估算法的收斂快慢,其數(shù)值越快達(dá)到最小,收斂速度越快,越節(jié)約成本,t為時(shí)刻且{t≥1|t∈N},平均成本計(jì)算如下：

(12)

3.2 算法復(fù)雜度分析

表1 算法時(shí)間與空間復(fù)雜度

3.3 算法評(píng)估

對(duì)三個(gè)算法所用虛擬機(jī)平均數(shù)量、重新配置次數(shù)、SLA違約次數(shù)的分析結(jié)果如表2所示。結(jié)果反映三個(gè)算法使用的虛擬機(jī)平均數(shù)量相差不大,但使用PDS后算法在SLA違約和重新配置次數(shù)上面有非常明顯的減少,而PDS-Lambda算法相比PDS單步更新算法使用了多步更新能最快達(dá)到收斂形成最優(yōu)策略從而有最少的SLA違約次數(shù)和重新配置次數(shù)。

表2 算法性能比較

圖6展示了實(shí)驗(yàn)中的Q-學(xué)習(xí)算法、單步更新PDS算法和PDS-Lambda算法的平均成本,可以看到隨著時(shí)間的變化PDS-Lambda算法表現(xiàn)出了一個(gè)最快的收斂,能最快地到達(dá)穩(wěn)定的平均成本。并且從最后穩(wěn)定狀態(tài)上來(lái)看,PDS-Lambda算法和單步更新PDS算法都能實(shí)現(xiàn)比Q-學(xué)習(xí)算法更低平均成本。

圖6 平均成本變化趨勢(shì)

4 結(jié) 語(yǔ)

多數(shù)使用強(qiáng)化學(xué)習(xí)的彈性伸縮算法都沒(méi)有研究算法的收斂時(shí)間。本文針對(duì)IaaS云服務(wù)提供商上Web應(yīng)用,提出一種基于強(qiáng)化學(xué)習(xí)的PDS-lambda算法,該算法用來(lái)實(shí)現(xiàn)自動(dòng)控制虛擬機(jī)資源的彈性擴(kuò)張和彈性收縮,使部署在IaaS云服務(wù)提供商上的云Web應(yīng)用有更好的可靠性、適應(yīng)性和自動(dòng)性,通過(guò)加快收斂讓其滿(mǎn)足服務(wù)質(zhì)量同時(shí)盡可能節(jié)約成本。強(qiáng)化學(xué)習(xí)的方法中存在的普遍問(wèn)題是算法在收斂到最優(yōu)策略的過(guò)程中時(shí)會(huì)有一個(gè)比較差的性能表現(xiàn),因此要盡量減少這部分收斂時(shí)間來(lái)提高算法性能,實(shí)驗(yàn)結(jié)果表明,該算法利用PDS與多步更新的方法能比已經(jīng)有的強(qiáng)化學(xué)習(xí)算法更快達(dá)到收斂,節(jié)約成本。在未來(lái)的工作之中,希望將該算法進(jìn)一步應(yīng)用在一個(gè)真實(shí)的云環(huán)境Web應(yīng)用之中,來(lái)評(píng)估其實(shí)現(xiàn)彈性伸縮時(shí)的性能表現(xiàn)。