一種基于強化學習的云應用彈性伸縮算法

帥 斌 龍士工

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

0 引 言

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

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

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

強化學習相對閾值與時間序列分析的優點是當負載規律變化時能動態地調整策略,重新在環境中學習達到最優策略。文獻[9-11]提出使用Q-學習算法實現彈性伸縮,文獻[12]對SaaS云服務提供商的彈性伸縮策略使用了Q-學習算法,文獻[13-14]對數據流處理應用實現彈性提出有模型的強化學習,文獻[15]通過減少狀態集使Q-學習算法更快達到收斂。

僅有少部分研究Q-學習算法的收斂問題,如文獻[14-15]。此外,幾乎所有研究使用的都是單步更新的Q-學習算法[9-15],缺少多步更新算法的優勢。

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

1 問題建模

1.1 架構設計

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

圖1 云資源彈性伸縮架構

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

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

1.2 MDP

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

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

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

(1)

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

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

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

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

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

WSLA1{T(u,w)>TSLA}

(2)

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

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

圖2 MDP空間過程

圖3展示了MDP的時間過程,隨著時間增加,狀態也隨之不斷變化,時間越長狀態越多算法學習到的信息越多。

圖3 MDP時間過程

2 算法描述

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

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

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

(3)

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

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

2.1 PDS與學習策略

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

圖4 當前狀態與PDS和下一狀態關系

(4)

(5)

(6)

(7)

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

(8)

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

2.2 多步更新

(9)

式(9)表示在當前時刻的狀態與遍歷表所得的狀態不同時,便進行衰減,而當前時刻的狀態與遍歷表得到的狀態相同時便進行一次標記。由式(7)可得TD誤差δ為：

(10)

(11)

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

算法1PDS-Lambda算法

輸入 起始狀態-s0折扣因子-β

學習率-α衰減因子-λ

2.s=s0;

//初始化狀態

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

//每個時刻進行學習

4.a=π(s);

//式(8)

//式(10)

//式(9)

//式(11)

//式(9)

11. end for

12. forai∈A(s) do

//式(6)

14. end for

15.s←s′;

//轉換狀態

16. end for

3 仿真實驗

3.1 實驗設置

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

圖5 負載變化趨勢

設置SLA的違約時間為10 s,請求的最大響應時間超過這個值時就會導致一個處罰。設置學習率α=0.6,折扣因子β=0.8,衰減系數λ=0.8,實例成本、重新配置成本和SLA違約成本的權重各為：

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

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

(12)

3.2 算法復雜度分析

表1 算法時間與空間復雜度

3.3 算法評估

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

表2 算法性能比較

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

圖6 平均成本變化趨勢

4 結 語

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