帥 斌 龍士工

(貴州大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院 貴州 貴陽 550025) (貴州省公共大數(shù)據(jù)重點實驗室 貴州 貴陽 550025)

0 引 言

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

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

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

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

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

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

1 問題建模

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

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

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

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

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

1.2 MDP

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

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

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

(1)

對每個狀態(tài)-動作對的成本R(s,a)的評估,從三個方面來進(jìn)行考慮：

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

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

3) SLA違約成本,請求的響應(yīng)時間超過SLA違約的時間閾值TSLA時,會獲得一個SLA違約成本,考慮該成本為一個常量rSLA。

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

WSLA1{T(u,w)>TSLA}

(2)

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

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

圖2 MDP空間過程

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

圖3 MDP時間過程

2 算法描述

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

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

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

(3)

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

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

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

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

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

(4)

(5)

(6)

(7)

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

(8)

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

2.2 多步更新

(9)

式(9)表示在當(dāng)前時刻的狀態(tài)與遍歷表所得的狀態(tài)不同時,便進(jìn)行衰減,而當(dāng)前時刻的狀態(tài)與遍歷表得到的狀態(tài)相同時便進(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

//每個時刻進(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 仿真實驗

3.1 實驗設(shè)置

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

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

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

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

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

(12)

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

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

3.3 算法評估

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

表2 算法性能比較

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

圖6 平均成本變化趨勢

4 結(jié) 語

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