一種基于短期預測的業務彈性伸縮算法

鄭鵬飛 ,尤佳莉 ,王勁林 ,曾學文

(1.中國科學院聲學研究所國家網絡新媒體工程技術研究中心,北京 100190；2.中國科學院大學,北京 100049)

1 概述

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

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

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

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

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

2 問題建模

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

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

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

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

3 算法描述

3.1 業務彈性伸縮

SPESS 算法針對每個業務的每一類虛擬機。算法周期性運行,在每個周期的開始,調整虛擬機在各個站點的部署情況。設周期為T。

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

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

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

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

從式(4)可以推導出：

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

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

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

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

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

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

綜上所述,一個站點應該分配的虛擬機數量為：

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

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

3.2 預測模型

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

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

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

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

4 實驗與結果分析

4.1 實驗設置

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

圖1 仿真場景示意圖

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

4.2 算法效果

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

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

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

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

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

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

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

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

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

4.3 預測模型評估

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

圖6 站點2 的預測結果

表1 D-ARMA 與ARMA 預測誤差對比

5 結束語

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

[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.