云計算資源管理中的預(yù)測模型綜述

張飛飛，吳 杰，呂智慧

（復(fù)旦大學(xué) 計算機科學(xué)技術(shù)學(xué)院，上海200433）

0 引 言

云計算技術(shù)的不斷發(fā)展，使得云計算能夠靈活地、可擴展地、按需地為應(yīng)用分配所需資源。然而，靜態(tài)地為虛擬機分配物理資源可能會產(chǎn)生一些問題。如果根據(jù)應(yīng)用的最高負載分配資源可能會導(dǎo)致資源利用率比較低，然而分配資源少了又將導(dǎo)致違反應(yīng)用的服務(wù)等級協(xié)議 （SLA）。為了有效地管理資源，實現(xiàn)資源利用率最大化，云計算通常采用基于預(yù)測技術(shù)的資源管理方法。

目前，在云資源管理方法中存在很多種預(yù)測模型，這些模型各有優(yōu)缺點及適用環(huán)境。本文將這些模型分為三大類，分別介紹了這些預(yù)測模型的特點，并列出了每種預(yù)測模型的主要特征。通過對這些模型的分析，我們給出了基于預(yù)測技術(shù)的動態(tài)云資源管理方法的一般流程。雖然這些模型在某些云環(huán)境中能夠很好的進行預(yù)測，然而應(yīng)用的多樣化致使這些模型并不能適用于所有的情況，也就是說這些預(yù)測模型本身還存在一些不足之處。針對這些不足，本文從以下幾方面展望了云計算預(yù)測模型的發(fā)展方向。

1 預(yù)測模型介紹

預(yù)測技術(shù)由來已久，也有一些比較成熟的預(yù)測模型。文獻 ［1］研究了一些短期預(yù)測模型，包括差分自回歸移動平均模型 （ARIMA），自回歸模型 （AR），霍爾特－溫特斯指數(shù)平滑模型 （Holt－Winters exponential smoothing）。文獻［2］通過采用自回歸分?jǐn)?shù)整合滑動平均 （FARIMA）過程同時提供短期預(yù)測和長期預(yù)測。文獻 ［2］提出一種全局方法進行長期預(yù)測。這些傳統(tǒng)模型相對復(fù)雜，考慮到預(yù)測給系統(tǒng)帶來的開銷，云計算系統(tǒng)通常并不會直接采用這些模型。

隨著云計算技術(shù)的發(fā)展，為了實現(xiàn)虛擬資源的有效管理，預(yù)測技術(shù)被引入到云資源管理中。目前大部分的預(yù)測模型都是基于時間序列分析。本文將預(yù)測模型分為三類：基礎(chǔ)預(yù)測模型，基于反饋的預(yù)測模型和多時間序列預(yù)測模型。其中基礎(chǔ)預(yù)測模型和基于反饋的預(yù)測模型是單時間序列的預(yù)測模型，其分類如圖1所示。

圖1 預(yù)測模型分類

下面分類介紹每個預(yù)測模型及其特點：

1.1 基礎(chǔ)預(yù)測模型

文獻 ［3］提出一種預(yù)測方法，該方法主要用于云資源自動調(diào)整大小時應(yīng)用負載的預(yù)測。這個方法采用了二階自回歸移動均值 （ARMA）模型過濾器，其表達式如下

式中：變量β和γ的值分別為0.8和0.15，λ （t）——t時刻負載值。這個算法是ARMA模型的簡單應(yīng)用，存在一些不足點。第一，原始數(shù)據(jù)未經(jīng)處理。通常原始數(shù)據(jù)存在一些干擾數(shù)據(jù)，需經(jīng)過預(yù)處理，將干擾數(shù)據(jù)過濾出去，這樣有助于提高預(yù)測的準(zhǔn)確度。第二，將變量β和γ賦值固定值會影響算法的靈活性，降低算法的適應(yīng)能力。

文獻 ［4］采用指數(shù)平滑 （ES）方法預(yù)測請求訪問速率，其模型如下

式中：T1——時間粒度，該模型預(yù)測T1時間之后的訪問速率，即＾Λik（t＋T1），為上個樣本數(shù)據(jù)Λik（t）和預(yù)測數(shù)據(jù)＾Λik（t）的加權(quán)平均值，0＜γik（t）＜1。此模型通過重估計平滑因子γik（t）動態(tài)獲得合適的平滑指數(shù)模型，其中γik（t）定義為平滑誤差A(yù)ik（t）與絕對誤差Eik（t）的比值，即γik（t）＝Aik（t）／Eik（t）。在這個模型中，平滑因子的估計很重要，因為這個值直接影響到算法的準(zhǔn)確性。

文獻 ［5］提出一種模型來預(yù)測系統(tǒng)在將來某時刻需要的物理機數(shù)量。這個預(yù)測模型基于自回歸分析來進行預(yù)測，其模型如下

其中預(yù)測值m0為參數(shù)向量a與歷史需求值mi（i＜0）的內(nèi)積，參數(shù)向量a可以通過最小二乘法獲得。

以上3個模型都是通過歷史數(shù)據(jù)直接建模并預(yù)測，沒有考慮到負載模式的特點，這會使得預(yù)測模型的適用性受到限制，即在某些情況中預(yù)測準(zhǔn)確度可能會降低。

文獻 ［6］提出了一個適用于周期性負載模式的模型，該模型如下

式中：T——負載周期，y（t）——負載值。這個模型包括兩個部分，參數(shù)ak所在部分為周期預(yù)測，它是y值在周期T上的自回歸。參數(shù)bj所在部分為局部調(diào)整，考慮到y(tǒng)（t）與緊跟在y（t）之前的值的相關(guān)性。參數(shù)n和m為這兩個部分的階。這個模型對周期性負載進行預(yù)測時準(zhǔn)確度比較高，但是當(dāng)負載不存在明顯的周期性時，該預(yù)測模型無法保證其準(zhǔn)確性。

文獻 ［7］提出了一種應(yīng)用于云計算環(huán)境的可預(yù)測性彈性資源伸縮方案 （PRESS），該方案采用輕量級的信號處理與統(tǒng)計分析的方法對云環(huán)境中資源需求進行預(yù)測。該模型利用信號處理技術(shù)觀察序列的特征，通過快速傅里葉轉(zhuǎn)換計算負載的主頻，設(shè)為fd，PRESS得到大小為Z的模式窗口，其中Z＝ （1／fd）×r，r為采樣頻率。將原始序列分為Q＝ W／Z 個模式窗口：P1＝ ｛l1，…，lz｝，P2＝｛lz＋1，…，l2Z｝，…，PQ＝ ｛l（Q－1）Z，…，lQZ｝。PRESS評估所有窗口對Pi和Pj之間是否包含相似模式，如果所有模式窗口都相似，PRESS將所有窗口相同位置樣本值的平均值作為預(yù)測窗口的值。如果負載沒有相似模式，PRESS采用離散馬爾科夫鏈進行短期預(yù)測。該預(yù)測模型考慮到了負載的模式，并針對不同的負載模式采用了不同的預(yù)測方法。

1.2 基于反饋的預(yù)測模型

盡管基礎(chǔ)預(yù)測模型在某些云計算環(huán)境中能夠滿足系統(tǒng)需求，但是為了保證應(yīng)用的SLA，也有一些預(yù)測模型會在預(yù)測出結(jié)果之后再進行一些工作，比如增加一個補償值，或者是通過考慮反饋信息進一步完善預(yù)測模型的性能等。

文獻 ［8］為數(shù)據(jù)庫即服務(wù)系統(tǒng)提出了一種動態(tài)資源分配架構(gòu) （DRAF）。在他們使用的預(yù)測模型中，時間序列被看作是趨勢與噪聲的組合，Pi，k（t）＝Tri.k（t）＋ei，k，其中Tri，k（t）表示趨勢，ei，k表示噪聲。Tri，k（t）通過自回歸分析得到，ei，k認為是正態(tài)分布。趨勢模式可以表示為Tri.k（t）＝b0＋b1t＋b2t2。噪聲用兩個參數(shù)表示，均值μ和標(biāo)準(zhǔn)差σ。根據(jù)正態(tài)分布表，μ＋1.96σ可以覆蓋95%的噪音，所以ei，k＝μ＋1.96σ。為了減少因資源不足造成應(yīng)用性能降低的情況，作為一種彌補手段，會在預(yù)測值之上增加一個補償值。然而這樣直接加上一個補償值有時候可能造成資源的浪費。

文獻 ［9］提出了CloudScale系統(tǒng)，它采用在線資源需求預(yù)測和預(yù)測誤差處理來實現(xiàn)云環(huán)境中自適應(yīng)資源分配。資源需求預(yù)測經(jīng)常存在高估或低估的情況。高估時可能會造成一些資源的浪費，但是應(yīng)用的性能不會受到影響；然而，低估卻會導(dǎo)致違反服務(wù)等級協(xié)議，因此該模型的重點在于消除低估誤差。CloudScale采用在線的自適應(yīng)的填補方法來解決低估誤差。一種方法是在預(yù)測的需求之上再加上一個額外的補償值。另一種方法是在系統(tǒng)運行過程中出現(xiàn)資源不足時，直接將其資源配額提高到做大，或者是通過因子a（a＞1）逐步加大。這個模型提示我們預(yù)測模型可以通過有效的控制預(yù)測誤差來提高本身的性能。

文獻 ［10］提出了一種虛擬資源控制系統(tǒng)AutoControl，在這個系統(tǒng)中，模型估算器輸入過去資源分配信息和應(yīng)用性能信息，得到應(yīng)用將來的性能目標(biāo)，然后優(yōu)化器分配所需資源。對于每一個控制階段，模型估算器重新計算線性模型。這個線性模型用來逼近應(yīng)用的資源分配 （ua）與其性能 （ya）之間的量化關(guān)系。他們的關(guān)系可以表示如下

其中a1（k）和a2（k）描述了應(yīng)用過去和當(dāng)前性能之間的關(guān)系。參數(shù)向量b0（k）和b1（k）描述了應(yīng)用當(dāng)前性能和最近資源分配之間的關(guān)系。有了性能目標(biāo)，優(yōu)化器就可以進行所需資源的分配。這個模型充分結(jié)合了控制論的理論，應(yīng)用將來資源需求量由應(yīng)用的性能和過去資源分配情況共同決定。

1.3 多時間序列預(yù)測模型

在多時間序列預(yù)測中，模型不但考慮了同種資源的自相關(guān)性，同時考慮不同資源之間的交叉相關(guān)性。在某些情況下，考慮不同資源的交叉相關(guān)性能夠提高預(yù)測模型的預(yù)測效果。

文獻 ［11］分別從微觀和宏觀的角度出發(fā)對數(shù)據(jù)中心資源的消耗進行預(yù)測。在微觀的預(yù)測中使用了自回歸方法，具體表示如下

式 中：X1j（t）——CPU 的 使 用，X2j（t）——內(nèi) 存 的 使 用，ε1j（t），ε2j（t）——白噪聲 WN （0，σ2）。

文獻 ［12］提出了應(yīng)用于云計算環(huán)境的多時間序列模型，該模型用于虛擬機負載的特征描述和預(yù)測。該模型首先將虛擬機進行分組，然后進行預(yù)測。預(yù)測分3個步驟：首先，以不同時間粒度分析虛擬機負載在時間上的相關(guān)性和不同虛擬機在空間上的相關(guān)性，并決定最優(yōu)時間間隔來建模；其次，從原先的分組中找出可預(yù)測的分組；最后，進行預(yù)測。該模型采用隱馬爾科夫模型 （HMM）進行預(yù)測。估計出狀態(tài)轉(zhuǎn)換以及觀察頻率之后，給定時刻t的觀察可以計算出在時刻t＋l時觀察概率ot＋l

根據(jù)這個概率估計就可以預(yù)測在時刻t＋l最可能的觀察

下一個觀察就代表了將會出現(xiàn)哪些組。為了提高預(yù)測的準(zhǔn)確度，這個方法采用了一種綜合負載時間相關(guān)性和空間相關(guān)性的聚類算法。

文獻 ［13］提出了一個在線系統(tǒng) （ASAP）來預(yù)測云系統(tǒng)虛擬機需求，它采用兩層模式進行建模和預(yù)測。第一層是多個子模型的自回歸組合，在這個組合中，每個子預(yù)測模型的權(quán)重根據(jù)預(yù)測誤差進行調(diào)整。這些子預(yù)測模型包括移動均值，自回歸，神經(jīng)網(wǎng)絡(luò)等。第二層考慮到不同虛擬機之間的關(guān)系并利用這種關(guān)系來提高預(yù)測的健壯性，不同序列之間的相關(guān)性能夠幫助消除噪聲數(shù)據(jù)的干擾。設(shè)cov（t）ij表示資源類型i與它的第j個相關(guān)資源的協(xié)方差，則類型i在時刻t的需求為

2 預(yù)測模型的分析與比較

2.1 模型分類

本文將預(yù)測模型分為三類：基礎(chǔ)預(yù)測模型，基于反饋的預(yù)測模型和多時間序列預(yù)測模型。經(jīng)過對不同預(yù)測模型的分析發(fā)現(xiàn)，基于反饋的預(yù)測模型和多時間序列預(yù)測模型的核心都是基于基礎(chǔ)預(yù)測模型實現(xiàn)的，同時多時間序列預(yù)測模型可以引入反饋信息的分析以提高其性能，所以多時間序列可以同時兼顧到基于反饋預(yù)測模型的優(yōu)點。我們將這三類模型之間的關(guān)系表示如圖2所示。

2.2 分析與比較

本節(jié)我們將分類對預(yù)測模型進行分析和比較，對于每種類型，采用不同的屬性進行描述。

2.2.1 基礎(chǔ)預(yù)測模型

表1列出了基礎(chǔ)預(yù)測模型的主要特征。其核心方法是自回歸，自回歸方法是預(yù)測技術(shù)的基本方法且應(yīng)用廣泛。本文介紹的預(yù)測模型大部分是采用最小二乘法估計參數(shù)。對于ES模型，平滑因子γik（t）的評估直接影響這個模型的準(zhǔn)確度。在這類模型中，PRESS［7］和稀疏自回歸模型可以對周期性負載進行相對長期的預(yù)測，其它模型都是短期預(yù)測，對于長期預(yù)測無法保證預(yù)測的準(zhǔn)確度。

圖2 預(yù)測模型關(guān)系

2.2.2 基于反饋的預(yù)測模型

表2列出了基于反饋的預(yù)測模型的主要特征。為了保證服務(wù)等級協(xié)議 （SLA），避免因資源不足導(dǎo)致應(yīng)用服務(wù)性能降低，最簡單的一種方法就是在預(yù)測結(jié)果之上再加上一個額外的補償值。這種方法相對簡單，但是可能會造成資源的浪費。第二種方法就是根據(jù)應(yīng)用的反饋信息，預(yù)測模型重新建模，估計模型參數(shù)，使得預(yù)測模型能夠?qū)崟r的響應(yīng)應(yīng)用的變化。

2.2.3 多時間序列預(yù)測模型

表3列出了多時間序列預(yù)測模型的主要特征。此類預(yù)測模型在建模時不但需要考慮同種資源的自相關(guān)性，同時考慮不同資源之間的交叉相關(guān)性。當(dāng)系統(tǒng)中不同資源之間存在相關(guān)性時，多序列模型能夠更好的反映出引起資源變化的因素，有助于提高預(yù)測的準(zhǔn)確度。同時，采用資源間的交叉相關(guān)性能夠幫助消除噪聲數(shù)據(jù)對模型準(zhǔn)確度的影響。

隨著云計算技術(shù)的不斷發(fā)展，動態(tài)資源供應(yīng)已成為云計算環(huán)境不可或缺的一部分。為了實現(xiàn)資源的有效利用并保證服務(wù)的質(zhì)量，幾乎所有的資源供應(yīng)方案都采用了預(yù)測技術(shù)。在應(yīng)用預(yù)測模型的時候需要準(zhǔn)確度與復(fù)雜性兼顧。通常準(zhǔn)確度越高的模型復(fù)雜度相對越高，會給系統(tǒng)帶來一定的開銷，所以在設(shè)計與選擇預(yù)測模型時應(yīng)考慮云環(huán)境的需求，選擇適用于它的預(yù)測模型。

2.3 基于預(yù)測的資源供應(yīng)一般流程

根據(jù)上面的討論，我們總結(jié)出云計算環(huán)境中資源供應(yīng)方案通常包含以下幾步：建模，預(yù)測，誤差糾正，性能分析，重建模，如圖3所示。

表1 基礎(chǔ)預(yù)測模型的分析與比較

表2 基于反饋的預(yù)測模型的分析與比較

表3 多時間序列預(yù)測模型的分析與比較

圖3 基于預(yù)測的資源供應(yīng)框架

3 未來發(fā)展

我們介紹并分析了應(yīng)用于云計算資源管理方法中的預(yù)測模型。為了更有效的輔助云計算資源管理，預(yù)測模型也隨之發(fā)展與完善，從最基本的基礎(chǔ)模型，到基于反饋的預(yù)測模型以及多時間序列預(yù)測模型。雖然預(yù)測模型得到了不斷的進步與發(fā)展，其中仍有一些需解決的問題，這些問題可以從以下3個方面進行說明：

（1）誤差糾正：很明顯，預(yù)測模型的準(zhǔn)確度直接影響了資源管理的有效性。為了實現(xiàn)資源利用率最大化，同時保證應(yīng)用性能，云計算系統(tǒng)需準(zhǔn)確地為應(yīng)用分配所需的資源。資源分配的依據(jù)就是預(yù)測模型得到的預(yù)測值，所以高準(zhǔn)確度的預(yù)測更有助于實現(xiàn)云計算資源管理的目標(biāo)。在預(yù)測中，誤差是不可避免，可以通過誤差修正以提高預(yù)測模型的準(zhǔn)確度。在基于反饋的預(yù)測模型中，一些模型就是利用了預(yù)測值與觀察值之間的差值進行誤差糾正，比如增加一個補償值或是增大虛擬機資源配額。這些誤差修正方法相對簡單，而且本身也存在很多問題。比如，補償值的大小如何確定，資源配額多大合適，以及何時進行誤差糾正等等。如果有一個好的誤差糾正方法，預(yù)測模型的準(zhǔn)確度也將得到提高。

（2）應(yīng)用性能保證：預(yù)測模型輔助云計算資源管理更好地管理與分配資源，然而在應(yīng)用運行過程中應(yīng)用資源不足的情況時有發(fā)生，所以我們并不能完全依賴預(yù)測模型。應(yīng)用運行時可以通過應(yīng)用的性能參數(shù) （響應(yīng)時間，吞吐量等）或是SLA指標(biāo)觀察應(yīng)用當(dāng)前運行狀態(tài)，一旦監(jiān)測到參數(shù)或指標(biāo)不滿足要求時，云資源管理應(yīng)即刻做出反應(yīng)。為了實現(xiàn)這一目的，有一些預(yù)測模型引入了控制論的方法。在這類模型中，實時地監(jiān)測應(yīng)用的運行狀態(tài)，并在不滿足要求時立刻做出響應(yīng)。然而控制論方法在云計算資源管理中的應(yīng)用還處在初期，有很大的研究空間。

（3）新型預(yù)測模型：目前很多的預(yù)測模型都是基于統(tǒng)計分析方法的，然而也存在一些其它的預(yù)測模型，例如文獻 ［14］中采用的基于遺傳算法的預(yù)測模型，文獻 ［2］中采用的基于人工神經(jīng)網(wǎng)絡(luò)的預(yù)測模型以及文獻 ［7］中采用的馬爾科夫鏈模型等等。對于預(yù)測技術(shù)，也許存在其它更好的方法來使得預(yù)測結(jié)果更準(zhǔn)確，開銷更小等，所以新型的預(yù)測模型是值得研究的。

4 結(jié)束語

云計算作為一種新型的計算模式受到了廣泛關(guān)注。在工業(yè)界已有一些成功案例，比如Google公司的AppEngine，Microsoft公司的Azure，IBM公司的Blue Cloud，Amazon公司的EC2和S3等。云計算資源管理一直都是云計算的核心，是實現(xiàn)云計算靈活性，可伸縮性，資源共享等特征的基礎(chǔ)。為了實現(xiàn)動態(tài)資源供應(yīng)，云計算資源管理通常需要借助預(yù)測技術(shù)來實現(xiàn)。

本文分析與討論了應(yīng)用于云計算環(huán)境的預(yù)測模型，包括基礎(chǔ)預(yù)測模型，基于反饋的預(yù)測模型和多時間序列預(yù)測模型，并在此基礎(chǔ)上總結(jié)了云計算環(huán)境中動態(tài)資源供應(yīng)方法的一般流程。我們可以看到預(yù)測模型從基礎(chǔ)模型到基于反饋的預(yù)測模型及多時間序列預(yù)測模型，它一直都在發(fā)展與完善。然而這些模型中還是存在一些不足之處，我們從誤差糾正，保證應(yīng)用性能和發(fā)展新模型3個方面介紹了預(yù)測模型還需完善的地方。預(yù)測模型作為云計算資源管理的輔助手段，它的發(fā)展必將有助于云計算技術(shù)的進步。

［1］Taylor J W，de Menezes L M，McSharry P E.A comparison of univariate methods for forecasting electricity demand up to a day ahead ［J］.International Journal of Forecasting，2006，22（1）：1－16.

［2］Sorjanmaa A，Hao J，Reyhani N，et al.Methodology for long－term prediction of time series ［J］.Neurocomputing，2007，70 （16－18）：2861－2869.

［3］Roy N，Dubey A，Gokhale A.Efficient autoscaling in the cloud using predictive models for workload forecasting ［C］／／Washington，DC：IEEE 4th International Conference on Cloud Computing，2011：500－507.

［4］Ardagna D，Casolari S，Panicucci B.Flexible distributed capacity allocation and load redirect algorithms for cloud systems［C］／／Washington，DC：IEEE 4th International Conference on Cloud Computing，2011：163－170.

［5］Guaenter B，Jain N， Williams C. Managing cost，performance，and reliability tradeoffs for energy－aware server provisioning ［C］／／Shanghai： Proceedings IEEE INFOCOM，2011：1332－1340.

［6］Chen G，He W，Liu J，et al.Energy－aware server provisioning and load dispatching for connection－intensive internet services ［C］／／Francisco，California：5th USENIX Symposium on Networked Systems Design and Implementation，2008：337－350.

［7］Gong Z，Gu X，Wilkes J.PRESS：Predictive elastic resource scaling for cloud systems ［C］／／Niagara Fall：International Conference on Network and Service Management，2010：9－16.

［8］Zhu J，Gao B，Wang Z，et al.A dynamic resource allocation algorithm for database－as－a－service ［C］／／Washington，DC：IEEE International Conference on Web Services，2011：564－571.

［9］Shen Z，Subbiah S，Gu X，et al.CloudScale：Elastic resource scaling for multi－tenant cloud systems ［C］／／Cascais，Portugal：2nd ACM Symposium on Cloud Computing，2011：1－14.

［10］Padala P，Hou K Y，Shin KG，et al.Automated control of multiple virtualized resources ［C］／／Nuremberg，Germany：ACM European Conference on Computer Systems，2009：13－26.

［11］Tan J，Dube P，Meng X，et al.Exploiting resource usage patterns for better utilization prediction ［C］／／Minneapolis，MN：31st International Conference on Distributed Computing Systems Workshops，2011：14－19.

［12］Khan A，Yan X，Tao S，et al.Workload characterization and prediction in the cloud：A multiple time series approach［C］／／Hawaii：13th IEEE／IFIP Network Operations and Management Symposium，2012：1287－1294.

［13］Yexi J，Chang－shing P，Tao L，et al.ASAP：A self－adaptive prediction system for instant cloud resource demand provisioning ［C］／／Vancouver，BC：11th IEEE International Conference on Data Mining，2011：1104－1109.

［14］Luque C，María J，F(xiàn)errán V，et al.Time series forcasting by means of evolutionary algorithms ［C］／／Long Beach，IEEE International Conference on Parallel and Distributed Processing Symposium，2007：1－7.