一種基于短期預(yù)測的業(yè)務(wù)彈性伸縮算法

鄭鵬飛 ,尤佳莉 ,王勁林 ,曾學(xué)文

(1.中國科學(xué)院聲學(xué)研究所國家網(wǎng)絡(luò)新媒體工程技術(shù)研究中心,北京 100190；2.中國科學(xué)院大學(xué),北京 100049)

1 概述

云計算數(shù)據(jù)中心能夠為業(yè)務(wù)提供彈性的存儲、計算資源,但是增加了到大部分用戶的距離,導(dǎo)致服務(wù)質(zhì)量無法保證；另外,諸如對等網(wǎng)絡(luò)(Peer-to-Peer,P2P)、內(nèi)容分發(fā)網(wǎng)絡(luò)(Content Delivery Network,CDN)等的地理分布式系統(tǒng)的經(jīng)驗表明,將服務(wù)部署到離用戶較近的位置,有較好的概率保證服務(wù)質(zhì)量。因此,一些學(xué)者開始研究結(jié)合云計算和地理分布式系統(tǒng)優(yōu)勢的地理分布云(geographically distributed cloud),其中,IBM 提出了一種聯(lián)邦云架構(gòu)Reservoir[1],文獻[2]使用P2P 協(xié)議將不同校園的資源連接起來提供云計算服務(wù),Metastorage 是一個折衷一致性和延時的聯(lián)邦云存儲系統(tǒng)[3],文獻[4]提出了一種地理分布式的媒體云架構(gòu)。

一個地理分布云包含位于不同地理位置的多個站點。然而,業(yè)務(wù)在哪些站點申請資源,申請多少資源,才能既滿足處理用戶請求的需要,同時避免資源浪費,值得深入研究。

Agile[5]使用排隊論理論預(yù)測三層應(yīng)用程序資源需求。CloudScale[6]應(yīng)用快速傅里葉變換識別資源并預(yù)測周期性的資源需求。在文獻[7]中,自回歸滑動平均模型(Auto Regression Moving Average,ARMA)被用于預(yù)測虛擬機負載以優(yōu)化資源分配。Autoflex[8]提出一個通用的彈性伸縮算法框架。文獻[9-10]提出了混合多種算法的模型來預(yù)測虛擬機數(shù)量需求,能夠根據(jù)預(yù)測誤差自動選擇最優(yōu)的算法。文獻[11]研究了社交網(wǎng)絡(luò)視頻在地理分布云中的部署優(yōu)化問題。文獻[12]使用遺傳算法求解地理分布云的資源部署問題。文獻[13]基于控制論和博弈論求解地理分布云資源部署問題。

大多研究是針對數(shù)據(jù)中心展開的,如文獻[5-10],僅有少部分研究針對地理分布云[11-13]。此外,幾乎所有的研究都只根據(jù)負載預(yù)測結(jié)果調(diào)整資源[5-13],而沒有考慮預(yù)測失敗情況下如何處理請求積壓。

本文對地理分布云的業(yè)務(wù)部署問題進行了研究,提出一種基于短期預(yù)測的業(yè)務(wù)彈性伸縮算法SPESS。該算法除了利用短期預(yù)測模型對用戶請求到達速度進行預(yù)測外,還綜合考慮了系統(tǒng)的當前負載和處理速度來調(diào)整業(yè)務(wù)虛擬機的部署位置和數(shù)量。

2 問題建模

地理分布云站點集合為S。t時刻,一個業(yè)務(wù)從站點s∈S申請的虛擬機數(shù)量為ms(t)。從開始服務(wù)到t時刻,該業(yè)務(wù)總共服務(wù)了n(t)個請求,其中,第i個請求(0≤i≤n(t))在服務(wù)過程中實際上經(jīng)歷了4 個階段：(1) 請求從用戶傳輸?shù)阶罱恼军c,如果該站點沒有部署虛擬機,請求會被轉(zhuǎn)發(fā)給部署有虛擬機的站點進行處理；(2) 如果沒有虛擬機空閑,請求將被排隊；(3) 請求被虛擬機處理；(4) 處理結(jié)果返回給用戶。階段(1)、階段(4)所需時間相同,為傳輸延時tdelay(i),階段(2)和階段(3)所需時間分別為排隊時間tque(i)和處理時間tproc(i),請求的總服務(wù)時間為2 ×tdelay(i) +tque(i) +tproc(i)。系統(tǒng)的第1 個優(yōu)化目標就是降低系統(tǒng)長期的請求平均服務(wù)時間：

業(yè)務(wù)需要為每一個運行中的虛擬機向支付運行成本,設(shè)虛擬機單位時間的運行成本為c,那么站點s∈S到t時刻付出的運行成本為。系統(tǒng)的第2 個優(yōu)化目標就是降低業(yè)務(wù)在所有站點的總運行成本：

在式(1)中,每一個請求的處理時間tproc(i)是固定的,傳輸延時tdelay(i)能夠通過在離用戶最近的站點部署虛擬機來降低,排隊時間tque(i)可以通過增加虛擬機的數(shù)量來降低。而式(2)要求盡可能地降低虛擬機的數(shù)量,因此,式(1)、式(2)是相互矛盾的,需要作出權(quán)衡。

上述模型只考慮了每個業(yè)務(wù)僅使用一類虛擬機的情況,實際上業(yè)務(wù)如果申請了多類虛擬機,每一類虛擬機都可以分別按照上述模型進行建模。

3 算法描述

3.1 業(yè)務(wù)彈性伸縮

SPESS 算法針對每個業(yè)務(wù)的每一類虛擬機。算法周期性運行,在每個周期的開始,調(diào)整虛擬機在各個站點的部署情況。設(shè)周期為T。

當用戶請求到達一個站點時,可能存在2 種情況,如果業(yè)務(wù)已經(jīng)在站點部署,則直接處理請求,否則將其路由給某個能夠進行處理的站點。本周期內(nèi),站點s∈S原始請求(即未經(jīng)過轉(zhuǎn)發(fā)的請求)的到達速度為rs=∑i∈Sr′si,其中r′si是路由到站點i∈S進行處理的速度。那么一個站點s的實際請求到達速度為λs=∑i∈Sr′is。

在傳統(tǒng)的軟件架構(gòu)中,一些硬件和軟件很容易成為系統(tǒng)的性能瓶頸,數(shù)據(jù)庫就是一個典型的例子。隨著技術(shù)的發(fā)展,各類大規(guī)模分布式系統(tǒng)的理論和設(shè)計不斷涌現(xiàn),很多系統(tǒng)能夠支持數(shù)千甚至萬臺服務(wù)器上。在這些系統(tǒng)的設(shè)計規(guī)模內(nèi),系統(tǒng)的處理能力與資源容量近似滿足線性關(guān)系。此外,大部分云計算廠商提供了云數(shù)據(jù)庫、云存儲、負載均衡等服務(wù)來幫助業(yè)務(wù)克服這些性能瓶頸,增強業(yè)務(wù)的擴展能力。因此,本文假設(shè)云計算業(yè)務(wù)能夠充分利用這些優(yōu)勢,其總并發(fā)處理能力和處理速度與虛擬機數(shù)量滿足線性關(guān)系。設(shè)每一個虛擬機的并發(fā)處理能力和處理速度分別為ν和μ,則站點s∈S的并發(fā)處理能力和處理速度分別為msν和msμ,其中ms是本周期站點s的虛擬機數(shù)量。

站點s∈S上一周期未處理完的請求(包括正在排隊和正在處理的請求)數(shù)量為πs。本周期開始后的t時刻,站點未處理的請求數(shù)量為max(π+(λs-msμ)t,0)。定義本周期開始后t時刻的站點負載比為：

式(3)實際上刻畫了站點s負載隨時間的變化趨勢。當bs(t)≥1 表明t時刻s處于滿載狀態(tài),新到達的請求將被排隊,0 ＜bs(t) ＜1 表明t時刻s有能力剩余,bs(t) ＜0 則表示t時刻s處于空閑狀態(tài)。算法關(guān)心周期結(jié)束時的站點負載比bs(T),希望將其控制在一個合理的負載范圍內(nèi),即：

從式(4)可以推導(dǎo)出：

其中,φs∈[0,1]是在權(quán)衡請求處理速度和虛擬機數(shù)量,即權(quán)衡優(yōu)化目標式(1)的排隊時間和優(yōu)化目標式(2)。

前面提到,當站點沒有部署業(yè)務(wù)的虛擬機時,到達的請求被路由到其它的站點,這樣會增加請求的傳輸延時。另外一方面,在一個站點部署虛擬機響應(yīng)用戶請求,需要考慮部署后的負載情況,如果負載較低,會導(dǎo)致資源浪費。因此,需要從整個系統(tǒng)的角度出發(fā),決定哪些站點需要部署虛擬機。

定義站點s∈S的原始站點負載比：

式(6)反映了如果請求都在原站點進行處理時,原站點負載的變化情況。則在周期結(jié)束時,同樣有：

式(8)的主要作用是衡量一個站點是否值得業(yè)務(wù)部署虛擬機。當一個站點已經(jīng)有虛擬機部署時,該站點到達的所有原始請求將在本地處理,此時式(8)的取值ms不超過式(5)；當一個站點尚未部署虛擬機時,式(8)計算出的ms表示如果該站點部署虛擬機,所需要的虛擬機數(shù)量。

此外,業(yè)務(wù)為了管理使用的虛擬機,需要配套的管理系統(tǒng),存在相對固定的基本運營成本,該成本導(dǎo)致在虛擬機過少時,性價比較低。反映到模型中,要么ms=0,要么ms≥θs,其中,θs是一個正整數(shù)。如果僅剩下一個站點部署有虛擬機時,應(yīng)該始終保證該站點ms≥θs,否則無法提供服務(wù)。

綜上所述,一個站點應(yīng)該分配的虛擬機數(shù)量為：

其中,l(s)判斷站點s是否為最后一個部署虛擬機的站點,如是則l(s)=1,否則l(s)=0。

虛擬機數(shù)量的調(diào)整發(fā)生在每個周期的開始,而此時,本周期的rs和λs是未來的數(shù)據(jù),因此,需要進行預(yù)測,預(yù)測所采用的模型將在下文描述。另外,μs是與請求處理時間分布相關(guān)的變量,對于特定的業(yè)務(wù)來說,應(yīng)該是比較穩(wěn)定的。為此,采用了一種較為簡單的方法進行估計。設(shè)最近一個周期完成的請求的平均處理時間為那么μs的估計值為算法周期T的選取也是一個重要問題,一個虛擬機的啟動時間需要幾十秒甚至幾分鐘的時間,周期T不應(yīng)該比這個時間量級更短,此外,周期過長會導(dǎo)致無法及時反映用戶請求到達速度的變化,因此,本文認為周期T的合理取值在數(shù)十分鐘至數(shù)個小時之間。

3.2 預(yù)測模型

每一個需要進行預(yù)測的變量(每個站點s∈S的rs和λs)在不同周期上的取值形成了一個時間序列(Time Series)。在時間序列預(yù)測模型中,差分自回歸移動平均(Autoregressive Integrated Moving Average,ARIMA) 模型在金融等領(lǐng)域被廣泛使用[14],具有實現(xiàn)簡單、短期預(yù)測效果較好等優(yōu)點。因此,本文以ARIMA 為基礎(chǔ),提出一種短期預(yù)測模型,利用變量在過去一段時間內(nèi)的歷史值,預(yù)測本周期的值。

ARIMA(p,d,q)可以表示為：

其中,p為自回歸項數(shù)；q為滑動平均項數(shù)；d使原序列成為平穩(wěn)序列所做的差分次數(shù)(也稱階數(shù))；L是滯后算子(lag operator)；αi是自回歸項的系數(shù)；βi是滑動平均項的系數(shù)；εt是白噪聲序列(white noise sequence)。

確定p,q,d之后,ARIMA 的各項系數(shù)可以通過對歷史數(shù)據(jù)的訓(xùn)練得到。影響時間序列的因素有很多,可能存在此消彼長、突然出現(xiàn)等現(xiàn)象,單憑一次訓(xùn)練得到的模型很難反應(yīng)時間序列的長期變化。因此,本文的預(yù)測模型采用邊訓(xùn)練邊預(yù)測的方式,利用最新的歷史數(shù)據(jù),在預(yù)測前重新訓(xùn)練,修正ARIMA模型。將本文提出的模型稱之為動態(tài)差分自回歸移動平均(Dynamic Autoregressive Integrated Moving Average,D-ARIMA)。

4 實驗與結(jié)果分析

4.1 實驗設(shè)置

設(shè)計如圖1 所示的場景驗證本文提出的算法。在場景中有4 個區(qū)域,一個地理分布云在每一個區(qū)域部署一個站點。在以站點為圓心,延時1 s 為半徑的地理范圍內(nèi),用戶隨機發(fā)起請求。一個業(yè)務(wù)申請了一種虛擬機,在4 個區(qū)域提供服務(wù)。初始情況下,僅有在區(qū)域1 各部署了10 個虛擬機,而各站點維持運行的最少虛擬機數(shù)量也是10。另外,假設(shè)虛擬機的并發(fā)處理速度為20,算法的周期為600 s,φs取值為0.7,D-ARIMA 的p,q,d取值分別為3,1,1。

圖1 仿真場景示意圖

實驗采用WorldCup98[15]第56 天～60 天的日志作為驅(qū)動,該日志包含4 個地區(qū)的訪問分別對應(yīng)實驗場景中的4 個區(qū)域。原日志中不包含處理時間信息,故假設(shè)每一個請求的處理時間正比于文件大小。

4.2 算法效果

統(tǒng)計了4 個站點的請求到達和虛擬機數(shù)量變化趨勢,如圖2 所示。從實驗結(jié)果可以看出,虛擬機數(shù)量的變化與請求到達的速度的變化趨勢是匹配的,說明算法準確地預(yù)測了請求達到的變化趨勢,并能夠按照該趨勢合理地分配虛擬機數(shù)量。

圖3 揭示了實驗過程中所有站點的虛擬機平均負載的變化趨勢。該趨勢圖顯示,盡管存在一定的波動,但是虛擬機的平均負載基本穩(wěn)定在60%～80% 之間,這與實驗設(shè)置的負載控制目標φs=0.7(即70%)是一致的,說明算法具有較強的負載調(diào)控能力。

圖2 站點請求到達數(shù)量和虛擬機數(shù)量變化趨勢

圖3 虛擬機平均負載變化趨勢

圖4 顯示了所有請求的平均傳輸延時變化。當區(qū)域內(nèi)的請求過少時,業(yè)務(wù)會撤銷相應(yīng)站點的所有虛擬機,從而導(dǎo)致該區(qū)域的傳輸延時變大,延時增加量最少1.5 s,而區(qū)域的平均傳輸延時是0.5 s,因此,轉(zhuǎn)發(fā)后的請求的平均延時至少為2 s。圖4 中絕大部分時間內(nèi),請求的平均傳輸延時都遠小于2 s,說明業(yè)務(wù)對站點虛擬機撤銷、重建是合理的。

圖4 所有請求的平均傳輸延時變化趨勢

圖5 的實驗結(jié)果顯示,絕大部分時間內(nèi),站點2請求的排隊時間均接近0 s,但是仍然出現(xiàn)排隊時間特別長的尖峰,這是由于請求壓力突然增大而算法沒有準確預(yù)測該趨勢導(dǎo)致的。不過,這些峰值的持續(xù)時間都很短,說明算法有效地考慮了請求的積壓情況,并能夠調(diào)整資源分配將積壓消除掉。其他站點也有類似的結(jié)論。

綜上所述,本文提出的業(yè)務(wù)彈性伸縮算法SPESS能夠根據(jù)不同地區(qū)的訪問情況,較好地調(diào)整業(yè)務(wù)在地理分布云的部署,從而在服務(wù)質(zhì)量和運行成本之間取得平衡。

圖5 站點2 請求的平均排隊時間變化趨勢

4.3 預(yù)測模型評估

預(yù)測模型是決定算法準確性的關(guān)鍵因素。圖6顯示了本文預(yù)測模型D-ARIMA 對站點2 每周期請求數(shù)量的預(yù)測值與實際值的關(guān)系,從圖中可以發(fā)現(xiàn),算法所采用的預(yù)測模型的預(yù)測值與真實值很接近,且變化趨勢一致。表1 對比了本文的預(yù)測模型與只訓(xùn)練一次的ARIMA 模型[13](即表中的ARIMA)在預(yù)測站點2 每周期原始請求數(shù)量時的預(yù)測誤差,表1 中的誤差標準分別為均方根誤差(Root Mean Square Error,RMSE)、平均絕對誤差(Mean Absolute Error,MAE)、平均絕對百分誤差(Mean Absolute Percentage Error,MAPE)。從表中可以看出,D-ARIMA 的預(yù)測效果要好于ARIMA,這是因為D-ARIMA 能夠根據(jù)用戶請求的變化不斷地調(diào)整預(yù)測模型。

圖6 站點2 的預(yù)測結(jié)果

表1 D-ARMA 與ARMA 預(yù)測誤差對比

5 結(jié)束語

地理分布云的業(yè)務(wù)部署問題研究如何在地理分布云站點上合理分布業(yè)務(wù)的資源。針對該問題,本文提出一種業(yè)務(wù)彈性伸縮算法SPESS,該算法針對每一個業(yè)務(wù)的每一類虛擬機,使用D-ARIMA 預(yù)測模型對用戶請求進行預(yù)測,并結(jié)合負載和處理速度等信息,提前調(diào)整不同站點的虛擬機數(shù)量,以在服務(wù)質(zhì)量和成本之間取得平衡。實驗結(jié)果表明,該算法能夠有效地反映各區(qū)域的用戶請求變化,將負載控制在預(yù)期值附近,而算法所使用的D-ARIMA 預(yù)測模型比ARIMA 具有更小的預(yù)測誤差。

[1]Rochwerger B,Breitgand D,Levy E,et al.The Reservoir Model and Architecture for Open Federated Cloud Computing [ J ].IBM Journal of Research and Development,2009,53(4)：1-11.

[2]Ye Conghuan,Pan Junshan.A New P2P Campus Cloud Framework [C]//Proceedings of 2011 IEEE International Conference on Anti-counterfeiting,Security and Identification.Piscataway,USA：IEEE Press,2011：1-4.

[3]Bermbach D,Klems M,Tai S,et al.Metastorage：A Federated Cloud Storage System to Manage Consistencylatency Tradeoffs [ C]//Proceedings of 2011 IEEE International Conference on Cloud Computing.Piscataway,USA：IEEE Press,2011：452-459.

[4]Zhu W,Luo C,Wang J,et al.Multimedia Cloud Computing [J].IEEE Signal Processing Magazine,2011,28(3)：59-69.

[5]Urgaonkar B,Shenoy P,Chandra A,et al.Agile Dynamic Provisioning of Multi-tier Internet Applications[J].ACM Transactions on Autonomous and Adaptive Systems,2008,3(1)：1-39.

[6]Shen Zhiming,Subbiah S,Gu Xiaohui,et al.Cloudscale：Elastic Resource Scaling for Multi-tenant Cloud Systems[C]//Proceedings of the 2nd ACM Symposium on Cloud Computing.New York,USA：ACM Press,2011：14-19.

[7]Roy N,Dubey A,Gokhale A.Efficient Autoscaling in the Cloud Using Predictive Models for Workload Forecasting [C]//Proceedings of 2011 IEEE International Conference on Cloud Computing.Piscataway,USA：IEEE Press,2011：500-507.

[8]Morais F A,Vilar B F,Lopes R V,et al.Autoflex：Service Agnostic Auto-scaling Framework for Iaas Deployment Models [ C]//Proceedings of the 13th IEEE/ACM International Symposium on on the Cluster,Cloud and Grid Computing.Piscataway,USA：IEEE Press,2013：42-49.

[9]Perng C,Li T,Chang R.Cloud Analytics for Capacity Planning and Instant VM Provisioning [ J].IEEE Transactions on Network and Service Management,2013,10(3)：312-325.

[10]Jiang Y,Perang C,Li T,et al.Asap：A Self-adaptive Prediction System for Instant Cloud Resource Demand Provisioning [ C]//Proceedings of the 11th IEEE International Conference on the Data Mining.Piscataway,USA：IEEE Press,2011：1104-1109.

[11]Yu W,Chuan W,Bo L,et al.Scaling Social Media Applications Into Geo-distributed Clouds [ C ]//Proceedings of IEEE INFOCOM.Piscataway,USA：IEEE Press,2012：684-692.

[12]Zhu J,Zheng Z,Zhou Y,et al.Scaling Service-oriented Applications Into Geo-distributed Clouds [ C ]//Proceedings of the 7th IEEE International Symposium on the Service Oriented System Engineering.Piscataway,USA：IEEE Press,2013：335-340.

[13]Zhang Q,Zhu Q,Zhan M F,et al.Dynamic Service Placement in Geographically Distributed Clouds[J].IEEE Journal on Selected Areas in Communications,2013,31(12)：762-772.

[14]Tsay R S.金融時間序列分析[M].2 版.潘家柱,譯.北京：人民郵電出版社,2009.

[15]Arlitt M,Jin T.1998 World Cup Web Site Access Logs[EB/OL].[2014-04-22].http：//ita.ee.lbl.gov/html/ contrib/WorldCup.html.