梁 毅，曾紹康，梁巖德，丁 毅

(北京工業(yè)大學(xué)信息學(xué)部,北京 100124)

1 引言

隨著大數(shù)據(jù)產(chǎn)業(yè)的發(fā)展，數(shù)據(jù)中心得到了較為廣泛的關(guān)注和較大的投入建設(shè)。負(fù)載是數(shù)據(jù)中心應(yīng)用的運(yùn)行實(shí)例，也是數(shù)據(jù)中心資源使用的主體。以Web服務(wù)、流式計(jì)算為代表的在線負(fù)載是其中一類長(zhǎng)時(shí)運(yùn)行、延遲敏感的負(fù)載。由于在線負(fù)載受到用戶行為驅(qū)動(dòng)，負(fù)載強(qiáng)度具有較大的波動(dòng)性，在運(yùn)行過(guò)程中其資源需求動(dòng)態(tài)變化。在線負(fù)載資源需求預(yù)測(cè)一直以來(lái)都是數(shù)據(jù)中心資源管理領(lǐng)域的研究熱點(diǎn)?？焖?、準(zhǔn)確的在線負(fù)載資源需求預(yù)測(cè)是數(shù)據(jù)中心合理分配資源、保障負(fù)載執(zhí)行效率的關(guān)鍵。

數(shù)據(jù)中心在線負(fù)載資源預(yù)測(cè)方法已得到廣泛關(guān)注和研究?？偨Y(jié)而言，既有方法可分為3類：基于簡(jiǎn)單統(tǒng)計(jì)分析方法、基于時(shí)間序列分析方法和基于機(jī)器學(xué)習(xí)方法。

簡(jiǎn)單統(tǒng)計(jì)分析方法是指通過(guò)對(duì)資源使用數(shù)據(jù)采用統(tǒng)計(jì)分組、相關(guān)分析等方法分析在線負(fù)載資源使用情況，對(duì)當(dāng)前在線負(fù)載資源需求進(jìn)行預(yù)測(cè)[1,2]。然而，單純采用簡(jiǎn)單統(tǒng)計(jì)分析的方式無(wú)法更準(zhǔn)確地挖掘在線負(fù)載資源使用的特征和變化趨勢(shì)。

針對(duì)簡(jiǎn)單統(tǒng)計(jì)分析方法的不足，時(shí)間序列分析方法被引入數(shù)據(jù)中心資源預(yù)測(cè)。既有工作主要采用AR(Auto Regressive model)分析法[3 - 5]、自相關(guān)和互相關(guān)方法[6,7]以及ARIMA(Auto Regressive Integrated Moving Average)方法[8 - 13]對(duì)數(shù)據(jù)中心單負(fù)載及混部負(fù)載場(chǎng)景下應(yīng)用的CPU、內(nèi)存、磁盤(pán)及網(wǎng)絡(luò)資源需求進(jìn)行預(yù)測(cè)。然而，上述時(shí)間序列分析方法多適用于短期預(yù)測(cè)，難以對(duì)在線負(fù)載的長(zhǎng)時(shí)運(yùn)行的資源需求進(jìn)行準(zhǔn)確預(yù)測(cè)。

隨著機(jī)器學(xué)習(xí)的發(fā)展，相關(guān)算法被廣泛應(yīng)用到了在線負(fù)載資源預(yù)測(cè)中。既有工作主要采用多元線性回歸方法[14 - 16]、聚類方法[17,18]、支持向量回歸方法[19 - 21]及馬爾科夫模型[22 - 25]進(jìn)行應(yīng)用資源使用預(yù)測(cè)。文獻(xiàn)[26]針對(duì)在線負(fù)載，測(cè)試了線性回歸、神經(jīng)網(wǎng)絡(luò)和支持向量回歸等算法在CPU需求預(yù)測(cè)上的性能，發(fā)現(xiàn)在各算法中支持向量回歸算法的預(yù)測(cè)結(jié)果更準(zhǔn)確且表現(xiàn)最優(yōu)。然而，機(jī)器學(xué)習(xí)算法的預(yù)測(cè)準(zhǔn)確度依賴于大規(guī)模樣本數(shù)據(jù)的訓(xùn)練，而大規(guī)模數(shù)據(jù)的訓(xùn)練會(huì)導(dǎo)致較大的時(shí)間開(kāi)銷，無(wú)法滿足在線負(fù)載實(shí)時(shí)性的場(chǎng)景。

然而，上述研究成果尚存在2點(diǎn)不足：(1)既有基于簡(jiǎn)單統(tǒng)計(jì)分析和時(shí)間序列分析的預(yù)測(cè)方法多著眼于短期預(yù)測(cè)，難以獲得較為準(zhǔn)確的長(zhǎng)期預(yù)測(cè)值；(2)既有基于機(jī)器學(xué)習(xí)的預(yù)測(cè)方法準(zhǔn)確度依賴于大規(guī)模樣本數(shù)據(jù)，且具有較大的時(shí)間開(kāi)銷，難以適應(yīng)在線負(fù)載快速響應(yīng)、延遲敏感的需求。

針對(duì)上述問(wèn)題，本文將在線負(fù)載資源使用的周期性特征引入資源預(yù)測(cè)中，提出基于周期性特征的在線負(fù)載資源預(yù)測(cè)方法PRP(Periodical characteristic based Resource Prediction)。PRP通過(guò)資源使用變化周期識(shí)別和資源使用樣本子序列分類，將在線負(fù)載的長(zhǎng)期資源預(yù)測(cè)轉(zhuǎn)化為短期預(yù)測(cè)，通過(guò)加權(quán)綜合不同類資源使用子序列獲得快速、準(zhǔn)確的在線負(fù)載資源預(yù)測(cè)。本文的主要貢獻(xiàn)可歸納為3個(gè)部分：

(1)提出了基于自相關(guān)函數(shù)的在線負(fù)載資源使用周期識(shí)別方法。應(yīng)用自相關(guān)函數(shù)對(duì)在線負(fù)載資源序列的周期進(jìn)行識(shí)別和量化，利用其周期性特征將長(zhǎng)期資源預(yù)測(cè)轉(zhuǎn)化為周期間資源使用的比對(duì)統(tǒng)計(jì)。

(2)提出基于K-Means聚類的資源使用子序列分類方法。針對(duì)資源使用量以及變化趨勢(shì)，采用K-Means聚類算法對(duì)按照周期劃分的子序列集進(jìn)行分類；最終依據(jù)分類，采用線性加權(quán)方法計(jì)算資源需求預(yù)測(cè)值。

(3)對(duì)本文提出的在線負(fù)載資源預(yù)測(cè)方法PRP進(jìn)行了性能評(píng)測(cè)。實(shí)驗(yàn)結(jié)果表明，與既有基于ARIMA算法、支持向量回歸算法和馬爾可夫模型的在線負(fù)載資源預(yù)測(cè)方法相比，PRP方法可使預(yù)測(cè)平均相對(duì)誤差最大降低28.3%,12.3%和27.4%。同時(shí)，隨著預(yù)測(cè)時(shí)間步長(zhǎng)的增加，PRP方法在預(yù)測(cè)準(zhǔn)確度和時(shí)間開(kāi)銷上的優(yōu)勢(shì)逐步增加。

2 在線負(fù)載周期性特征分析

本節(jié)將分析在線負(fù)載資源使用的周期性特征。

2.1 任務(wù)知識(shí)

請(qǐng)求到達(dá)波動(dòng)性是在線負(fù)載的典型特征。隨著在線負(fù)載用戶群體的擴(kuò)增、服務(wù)訪問(wèn)或數(shù)據(jù)采集行為習(xí)慣的趨同，負(fù)載請(qǐng)求波動(dòng)的周期性特征具有一定的普遍性。圖1中展示了3個(gè)不同的在線負(fù)載場(chǎng)景下請(qǐng)求強(qiáng)度的變化統(tǒng)計(jì)。

Figure 1 Examples of online workload user request/data arrival intensity圖1 在線負(fù)載用戶訪問(wèn)量/數(shù)據(jù)到達(dá)強(qiáng)度

從圖1中可以分析出，在線負(fù)載請(qǐng)求強(qiáng)度呈明顯的周期性變化，在周期內(nèi)數(shù)據(jù)呈相似的變化趨勢(shì)。以圖1a NASA網(wǎng)站1個(gè)月的用戶訪問(wèn)量為例，其用戶訪問(wèn)以24 h為1個(gè)周期發(fā)生變化，大多數(shù)周期內(nèi)的用戶訪問(wèn)量在500～8 000次以相似的趨勢(shì)波動(dòng)。但是，也有少數(shù)周期內(nèi)數(shù)據(jù)量變化有異?，F(xiàn)象。其中，在第8和第9個(gè)周期內(nèi)，用戶訪問(wèn)量在0～4 000 波動(dòng)，在第13個(gè)周期內(nèi)，用戶訪問(wèn)量最多達(dá)到了13 000以上。同樣，圖1b和圖1c分別展示了曼徹斯特大學(xué)的學(xué)生1周內(nèi)對(duì)YouTube網(wǎng)站的用戶訪問(wèn)情況和國(guó)內(nèi)某互聯(lián)網(wǎng)公司的流式日志數(shù)據(jù)到達(dá)強(qiáng)度趨勢(shì)，其中流式日志業(yè)務(wù)是在線負(fù)載中典型的流式計(jì)算負(fù)載。除此之外，伯克利大學(xué)主頁(yè)訪問(wèn)、法國(guó)世界杯體育網(wǎng)站[27]訪問(wèn)等數(shù)據(jù)也均呈現(xiàn)為較典型的周期性特征。具體而言,上述在線負(fù)載的訪問(wèn)具有如下共性特征：(1)負(fù)載請(qǐng)求以小時(shí)、天或者周為周期，具有相同的變化趨勢(shì)；(2)大多數(shù)周期間，數(shù)據(jù)的變化幅度相同或相似，存在少量周期間數(shù)據(jù)變化幅度有較大差異。

2.2 在線負(fù)載資源使用周期性特征分析

在線負(fù)載請(qǐng)求到達(dá)強(qiáng)度是影響其資源使用的核心因素，本文提出假設(shè)：周期性的用戶訪問(wèn)/數(shù)據(jù)到達(dá)強(qiáng)度會(huì)引發(fā)在線負(fù)載的周期性資源使用特征。為此，通過(guò)1組實(shí)驗(yàn)進(jìn)行分析。

既有數(shù)據(jù)中心多采用容器技術(shù)部署在線負(fù)載，并進(jìn)行資源隔離。因此，本文假設(shè)數(shù)據(jù)中心多在線負(fù)載間的資源使用干擾較小?；谌萜骷夹g(shù)，部署單在線負(fù)載，分析其資源使用特征。本文采用典型的Web類型負(fù)載——TPC-W，在數(shù)據(jù)中心單在線負(fù)載的場(chǎng)景下，設(shè)置用戶訪問(wèn)量變化周期為1 h，周期內(nèi)用戶訪問(wèn)符合正弦分布，用戶訪問(wèn)強(qiáng)度為40次/秒～120次/秒。

以上實(shí)驗(yàn)展示了在周期性的用戶訪問(wèn)強(qiáng)度下，在線負(fù)載資源使用變化的情況。分析可知，在用戶訪問(wèn)強(qiáng)度變化以1 h為周期的情況下，其資源使用量的變化周期也為1 h。另外，在相同的用戶訪問(wèn)強(qiáng)度下，每個(gè)資源周期內(nèi)的數(shù)值波動(dòng)范圍相同，周期間的變化趨勢(shì)也有較強(qiáng)的相似性。在第3個(gè)周期(圖2中橫坐標(biāo)170～230)，我們將請(qǐng)求強(qiáng)度變化從40次/秒～120次/秒提高到40次/秒～160次/秒，在圖2a中可以看到，在本周期內(nèi)負(fù)載的內(nèi)存使用量變化從1 700 MB～2 500 MB變?yōu)? 700 MB～2 700 MB，增長(zhǎng)明顯。同樣，在第7個(gè)周期(圖2中橫坐標(biāo)410～470)，將線程變化從40次/秒～120次/秒降低到40次/秒～80次/秒，其內(nèi)存和CPU使用量在第7個(gè)周期內(nèi)也呈現(xiàn)明顯的降低。

Figure 2 Variations in resource consuming of online services圖2 在線負(fù)載運(yùn)行的資源使用情況

綜上，具有周期性請(qǐng)求/數(shù)據(jù)到達(dá)強(qiáng)度的在線負(fù)載，其資源使用量會(huì)隨著請(qǐng)求/數(shù)據(jù)到達(dá)變化，且呈現(xiàn)相近的周期特征。

3 基于周期性特征的在線負(fù)載資源預(yù)測(cè)方法PRP

本文將在線負(fù)載資源使用的周期性特征引入資源預(yù)測(cè)中。如圖3所示是在線負(fù)載資源預(yù)測(cè)方法PRP的框架。

Figure 3 Overview of PRP圖3 在線負(fù)載資源預(yù)測(cè)方法PRP框架

PRP方法首先應(yīng)用自相關(guān)函數(shù)法對(duì)在線負(fù)載資源使用量樣本序列進(jìn)行周期識(shí)別；其次將樣本序列依據(jù)周期進(jìn)行劃分得到子序列集；再次計(jì)算所有子序列間的相似度，并根據(jù)相似度進(jìn)行子序列劃分；最終根據(jù)預(yù)測(cè)時(shí)刻點(diǎn)在各類子序列中對(duì)應(yīng)時(shí)刻點(diǎn)的資源使用變化率計(jì)算資源需求預(yù)測(cè)值。

3.1 在線負(fù)載資源使用的周期識(shí)別

本文選用自相關(guān)函數(shù)方法對(duì)在線負(fù)載的內(nèi)存和CPU資源使用量進(jìn)行周期量化識(shí)別。自相關(guān)函數(shù)被廣泛用于信號(hào)的潛在周期性檢測(cè)中。對(duì)于1個(gè)有限長(zhǎng)度的離散序列，當(dāng)序列中2個(gè)變量存在關(guān)系時(shí)，隨著其中1個(gè)變量數(shù)值的確定，另1個(gè)變量會(huì)有不同的取值，但是該變量的取值有一定的規(guī)律性。這種統(tǒng)計(jì)規(guī)律可以通過(guò)自相關(guān)函數(shù)來(lái)表示，如式(1)所示：

(1)

其中，N是有限長(zhǎng)的離散序列y的長(zhǎng)度，x表示元素下標(biāo)，k表示自變量。

自相關(guān)函數(shù)有以下性質(zhì)：

性質(zhì)1周期函數(shù)的自相關(guān)函數(shù)依然存在周期性，并且其周期性與原函數(shù)周期頻率相同。

性質(zhì)2自相關(guān)函數(shù)具有偶函數(shù)特點(diǎn)，即R(k)=R(-k)。

性質(zhì)3任意函數(shù)的自相關(guān)函數(shù)都會(huì)周期性地存在極大值和極小值，并且在相鄰的極大值和極小值之間，自相關(guān)函數(shù)是單調(diào)的。

本文的目的是利用自相關(guān)函數(shù)的特性計(jì)算出內(nèi)存和CPU使用量序列的周期值。

由于內(nèi)存和CPU的預(yù)測(cè)方法以及周期相同，因此，下面均以資源使用序列統(tǒng)一指代內(nèi)存和CPU序列，L={l1,l2,…,ln}，其中l(wèi)i表示第i個(gè)時(shí)間點(diǎn)對(duì)應(yīng)的資源使用量，n為資源使用量樣本總數(shù)。具體的判別和度量流程如下所示：

方法1在線負(fù)載資源使用周期識(shí)別方法

(1)收集在線負(fù)載資源使用數(shù)據(jù)；

(2)以5 s為固定步長(zhǎng)，截取樣本數(shù)據(jù)，構(gòu)建在線負(fù)載資源序列ML；

(3)根據(jù)式(1)計(jì)算出序列ML的自相關(guān)序列MR；

(4)求取MR中任意2個(gè)相鄰的極大值，計(jì)算它們的時(shí)間距離t_maxi；

(5)將所有t_maxi求和，然后取平均值；

(6)所得到的平均值即為資源使用序列ML的周期。

3.2 在線負(fù)載資源使用樣本子序列分類

在線負(fù)載資源使用樣本子序列分類的目的是在序列周期識(shí)別的基礎(chǔ)上，統(tǒng)計(jì)具有不同資源使用量及變化趨勢(shì)的子序列類，最終為資源預(yù)測(cè)提供依據(jù)。

本文采用歐氏距離作為資源使用樣本子序列間相似度度量，稱為子序列距離，計(jì)算如式(2)所示：

(2)

其中，pi表示第i個(gè)序列，pj表示第j個(gè)序列,pik表示第i個(gè)序列中的第k個(gè)元素?cái)?shù)據(jù)，同理，pjk表示第j個(gè)序列中的第k個(gè)元素?cái)?shù)據(jù)。

顯然，子序列距離越大，序列間相似度越小，反之則序列間相似度越大。同時(shí)，本文采用聚類方法對(duì)資源使用樣本子序列進(jìn)行分類。如第2節(jié)所述，在線負(fù)載資源使用的周期性特征呈現(xiàn)出多數(shù)周期間資源使用量值及變化幅度相同或相似，少數(shù)周期間則存在較大差異的特點(diǎn)。因此，本文將在線負(fù)載資源使用樣本子序列分為常規(guī)序列和異常序列。其中，常規(guī)序列是指在線負(fù)載資源使用子序列中數(shù)據(jù)變化范圍相似的大多數(shù)的子序列，異常序列是指在線負(fù)載資源使用子序列中數(shù)據(jù)變化發(fā)生異常的子序列。本文首先給出如下定義：

定義1全局子序列最大距離：所有資源使用樣本子序列之間距離的最大值dmax：

dmax=max({d(xi,xj)|xi∈X,xj∈X})

(3)

其中，d(xi,xj)表示xi、xj之間的距離,X表示樣本序列集合。

定義2全局子序列最小距離:所有資源使用樣本子序列之間距離的最小值dmin：

dmin=min({d(xi,xj)|xi∈X,xj∈X})

(4)

其中，d(xi,xj)表示樣本序列xi,xj之間的距離,X表示樣本序列集合。

定義3子序列類距離閾值：所有資源使用樣本子序列類中序列之間距離的最大值：

α=(dmax-dmin)×a+dmin

(5)

其中，0

本文選擇K-Means聚類算法[24]進(jìn)行在線負(fù)載資源使用樣本子序列分類,它將1個(gè)給定的數(shù)據(jù)集劃分為用戶指定的k個(gè)聚簇，有著較高的執(zhí)行效率。在線負(fù)載資源使用子序列分類的K-Means算法如算法1所示。

算法1在線負(fù)載資源使用子序列分類的K-Means算法

輸入：在線負(fù)載資源使用子序列集，子序列類距離閾值α，常規(guī)子序列占比閾值δ，子序列分類數(shù)K。

輸出：子序列分類集合C。

1C←?;/*初始化子序列分類集合*/

2O←?;/*初始化中心點(diǎn)集合*/

3 Fori

4oi←RandomSelect(X);

5O←O∪{oi};

6 End For

7 Repeat:

8 ForxiinXDo：

9j←MinDistance(xi,O);

10Cj←Cj∪{xi}；

11 End For

12 Fori

13max_point_distancei←MaxDistance(Ci);/*計(jì)算每個(gè)簇內(nèi)最大距離*/

14maxD←maxD∪{max_point_distancei};

15si←Scale(ni,N);/*計(jì)算每個(gè)簇內(nèi)數(shù)據(jù)量占總的子序列數(shù)量比例*/

16maxS←maxS∪{si};

17 End For

18maxDistance←Max(maxD);/*計(jì)算所有簇距離的最大值*/

19maxScale←Max(maxS);/*計(jì)算所有簇所占子序列總量比值的最大值*/

20 UntilmaxDistance<α&maxScale>δ;

21 ReturnC

算法1依據(jù)用戶指定的子序列分類數(shù)量進(jìn)行子序列聚類,從所有在線負(fù)載資源使用樣本子序列中隨機(jī)選取初始類簇中心點(diǎn)，并進(jìn)行迭代計(jì)算。其迭代收斂條件有2個(gè)：(1)任一類簇中子序列的最大距離不超過(guò)定義的閾值，這保障了所獲得的子序列分類中，每一類子序列間具有相似的資源使用量和變化規(guī)律；(2)規(guī)模占比最大的類簇其規(guī)模占比應(yīng)超過(guò)設(shè)定的比例閾值，這是因?yàn)楦鶕?jù)本文第2節(jié)的觀測(cè)結(jié)果，在線負(fù)載資源使用周期性呈現(xiàn)出多數(shù)周期間資源使用量及變化規(guī)律相似，少數(shù)周期間差異較大的特點(diǎn)。通過(guò)約束規(guī)模占優(yōu)子序列類的占比閾值，進(jìn)一步保障聚類結(jié)果與實(shí)際場(chǎng)景中子序列分類情況吻合。

3.3 在線負(fù)載資源預(yù)測(cè)

在周期識(shí)別和序列分類的基礎(chǔ)上，本節(jié)提出具有周期性特征的在線負(fù)載資源預(yù)測(cè)方法。

令NL={nl1,nl2,…,nlS}表示資源使用樣本集合，其中nli(1≤i≤S)，表示第i類子序列集合，S是樣本類總量,nli={sli_1,sli_2,…,sli_K}表示按時(shí)間排列的第i類樣本子序列集合，K是序列類的總量。sli_j={eli_j_1,eli_j_2,…,eli_j_T}，1≤j≤K，eli_j_t表示1個(gè)采樣周期內(nèi)第t個(gè)采樣時(shí)刻的資源使用量，1≤t≤T，T是采樣周期時(shí)長(zhǎng)。本文首先給出以下定義：

定義4子序列類比例：在經(jīng)過(guò)周期分割的所有在線負(fù)載資源使用子序列中，每一類子序列所占子序列總數(shù)的比例，可以用式(6)表示：

(6)

其中，|nli|為第i類子序列集合中的序列總數(shù),S是樣本類的總量。

定義5子序列資源使用變化率：對(duì)任意子序列中采樣時(shí)刻t的資源使用變化率Rnli_j_t可表示為：

(7)

(8)

定義7子序列資源預(yù)測(cè)值:第i類子序列在下1個(gè)周期的采樣時(shí)刻t的資源使用預(yù)測(cè)值pli_t可表示為：

pli_t=eli_K_t×(1+Anli_t)

(9)

定義8在線負(fù)載資源預(yù)測(cè)值:最終的在線負(fù)載在下1周期t時(shí)刻的資源使用預(yù)測(cè)值lnext_t可表示為:

(10)

其中，wi為第i類樣本子序列的預(yù)測(cè)權(quán)重。

由上述定義可知，對(duì)于在線負(fù)載資源需求的預(yù)測(cè)實(shí)質(zhì)上是依據(jù)歷史資源使用樣本數(shù)據(jù)中各類樣本子序列出現(xiàn)的概率，對(duì)子序列中對(duì)應(yīng)時(shí)間點(diǎn)的資源使用變化率進(jìn)行加權(quán)平均，進(jìn)而形成預(yù)測(cè)時(shí)間點(diǎn)相對(duì)于上1個(gè)周期相應(yīng)時(shí)間點(diǎn)的資源使用變化率，最終計(jì)算出預(yù)測(cè)時(shí)間點(diǎn)的資源需求量。

4 性能測(cè)試與分析

本節(jié)從預(yù)測(cè)準(zhǔn)確度和計(jì)算效率的角度對(duì)PRP方法進(jìn)行性能評(píng)測(cè)。針對(duì)在線負(fù)載的主要資源需求，選取CPU和內(nèi)存2類資源進(jìn)行預(yù)測(cè)。

本文分別選取TPC-W和HiBench中的流式計(jì)算負(fù)載WordCount作為測(cè)試負(fù)載。上述負(fù)載分別是在線負(fù)載中Web服務(wù)和流式計(jì)算的典型代表。負(fù)載的請(qǐng)求/數(shù)據(jù)到達(dá)強(qiáng)度符合泊松分布和正弦分布。測(cè)試基礎(chǔ)環(huán)境由5臺(tái)服務(wù)器組成，服務(wù)器具體配置包括：Intel(R) Xeon(R) CPU E526600@2.20 GHZ*4，16 GB內(nèi)存，1 TB磁盤(pán)，千兆以太網(wǎng)。實(shí)驗(yàn)軟件環(huán)境主要包括Apache 2.4和Spark 2.3.1。實(shí)驗(yàn)選取預(yù)測(cè)平均相對(duì)誤差(MRE)作為預(yù)測(cè)準(zhǔn)確度的量化評(píng)價(jià)指標(biāo)；選取預(yù)測(cè)時(shí)間開(kāi)銷作為預(yù)測(cè)計(jì)算效率的量化評(píng)價(jià)指標(biāo)。

Figure 4 MRE of memory utilization prediction of streaming workloads圖4 流負(fù)載內(nèi)存資源預(yù)測(cè)誤差

實(shí)驗(yàn)選取既有成果中基于ARIMA算法、馬爾可夫(Markov)模型以及支持向量回歸(SVR)的在線負(fù)載資源預(yù)測(cè)方法進(jìn)行性能對(duì)比。這3種方法分別作為時(shí)間序列分析類和機(jī)器學(xué)習(xí)類方法被廣泛應(yīng)用于在線負(fù)載資源預(yù)測(cè)問(wèn)題，是較為有代表性的預(yù)測(cè)方法。

為了模擬長(zhǎng)期預(yù)測(cè)，本文根據(jù)樣本中包含的采樣時(shí)刻點(diǎn)數(shù)量M，從第2M的時(shí)刻點(diǎn)開(kāi)始對(duì)每隔30 s的資源需求進(jìn)行預(yù)測(cè)，預(yù)測(cè)總量為100個(gè)時(shí)間點(diǎn)。

4.1 流式計(jì)算負(fù)載資源預(yù)測(cè)準(zhǔn)確度評(píng)測(cè)

實(shí)驗(yàn)選取WordCount作為流式計(jì)算負(fù)載，設(shè)置請(qǐng)求/數(shù)據(jù)到達(dá)服從泊松分布，通過(guò)配置不同的請(qǐng)求/數(shù)據(jù)到達(dá)強(qiáng)度以及變化周期構(gòu)造不同的資源使用周期性特征，具體配置如表1所示。預(yù)測(cè)的樣本數(shù)據(jù)通過(guò)運(yùn)行一段時(shí)間負(fù)載獲得，采樣周期為5 s，樣本規(guī)模分別為10 800,14 400，18 000。

圖4和圖5分別展示了在數(shù)據(jù)到達(dá)符合泊松分布的情況下，PRP方法和其他對(duì)比方法的預(yù)測(cè)平均相對(duì)誤差。由圖4和圖5可知，在各種數(shù)據(jù)到達(dá)強(qiáng)度-周期配置下，PRP的預(yù)測(cè)準(zhǔn)確度均優(yōu)于既有方法的，其中，CPU和內(nèi)存資源預(yù)測(cè)平均相對(duì)誤差最大分別下降了25.4%和27.9%。同時(shí)，實(shí)驗(yàn)顯示隨著樣本規(guī)模的減小，PRP的預(yù)測(cè)準(zhǔn)確度優(yōu)勢(shì)更為顯著。這是因?yàn)椋琍RP方法利用周期識(shí)別，將長(zhǎng)期資源預(yù)測(cè)轉(zhuǎn)化為短周期內(nèi)資源的比對(duì)預(yù)測(cè)，克服了既有方法對(duì)于大規(guī)模樣本數(shù)據(jù)的依賴。因此，PRP方法在樣本數(shù)據(jù)有限或長(zhǎng)期預(yù)測(cè)的場(chǎng)景下具有較好的性能優(yōu)勢(shì)。

Figure 5 MRE of CPU utilization prediction of streaming workloads圖5 流負(fù)載CPU資源預(yù)測(cè)誤差

Table 1 Data arrival and variation period settings
表1 數(shù)據(jù)到達(dá)強(qiáng)度和周期變化分組

取值組數(shù)據(jù)到達(dá)強(qiáng)度/(MB/s)周期/min1[1,5]152[1,10]153[1,20]154[1,5]305[1,10]306[1,20]307[1,5]458[1,10]459[1,20]45

4.2 Web負(fù)載資源預(yù)測(cè)準(zhǔn)確度評(píng)測(cè)

實(shí)驗(yàn)選取TPC-W作為Web負(fù)載，請(qǐng)求到達(dá)同樣服從泊松分布。對(duì)于TPC-W負(fù)載通過(guò)改變請(qǐng)求發(fā)生數(shù)量來(lái)改變請(qǐng)求的到達(dá)強(qiáng)度。請(qǐng)求到達(dá)強(qiáng)度與周期設(shè)置如表2所示。預(yù)測(cè)樣本數(shù)據(jù)的獲取和規(guī)模同4.1節(jié)，預(yù)測(cè)樣本獲取、樣本數(shù)據(jù)規(guī)模以及預(yù)測(cè)時(shí)刻點(diǎn)的選取同4.1節(jié)。

Table 2 Request arrival intensity and variation period settings表2 請(qǐng)求到達(dá)強(qiáng)度變化和周期變化分組

圖6和圖7分別展示了在請(qǐng)求到達(dá)符合泊松分布的情況下，PRP方法和其他對(duì)比方法的預(yù)測(cè)平均相對(duì)誤差。由圖6和圖7可以獲得與4.1節(jié)相同的結(jié)論。對(duì)于Web負(fù)載，PRP可分別最大降低CPU和內(nèi)存資源預(yù)測(cè)平均相對(duì)誤差22.6%和24.1%。

Figure 6 MRE of memory utilization prediction of web workloads圖6 Web負(fù)載內(nèi)存資源預(yù)測(cè)誤差

Figure 7 MRE of CPU utilization prediction of web workloads圖7 Web負(fù)載CPU資源預(yù)測(cè)誤差

隨著樣本規(guī)模減小，PRP方法的預(yù)測(cè)性能優(yōu)勢(shì)更為顯著。然而，相對(duì)于流式計(jì)算負(fù)載而言，Web負(fù)載的資源預(yù)測(cè)平均相對(duì)誤差平均上升了7.9%。這是由于TPC-W具有更為復(fù)雜的計(jì)算邏輯，對(duì)計(jì)算資源消耗的波動(dòng)較流式WordCount負(fù)載更大，在資源使用樣本子序列分類數(shù)量受限的情況下，僅用較為簡(jiǎn)單的線性加權(quán)方法計(jì)算資源預(yù)測(cè)值，無(wú)法更為精細(xì)地識(shí)別周期內(nèi)資源使用的變化規(guī)律。

4.3 在線負(fù)載資源預(yù)測(cè)計(jì)算效率分析

本節(jié)評(píng)測(cè)PRP和其他對(duì)比方法在不同的樣本規(guī)模下資源預(yù)測(cè)的計(jì)算效率。實(shí)驗(yàn)選取流式WordCount和TPC-W作為測(cè)試負(fù)載，改變樣本規(guī)模統(tǒng)計(jì)預(yù)測(cè)所需的時(shí)間開(kāi)銷。

對(duì)于流式WordCount，實(shí)驗(yàn)設(shè)置數(shù)據(jù)到達(dá)強(qiáng)度為1 MB/s～10 MB/s，變化周期為20 min，數(shù)據(jù)到達(dá)符合泊松分布。實(shí)驗(yàn)結(jié)果如圖8所示。

Figure 8 Time overhead of resource prediction of streaming workloads圖8 流式計(jì)算負(fù)載資源預(yù)測(cè)時(shí)間開(kāi)銷

以請(qǐng)求到達(dá)強(qiáng)度變化為40次/秒～80次/秒、變動(dòng)周期為20 min的TPC-W負(fù)載產(chǎn)生的資源序列為樣本數(shù)據(jù)的情況下，實(shí)驗(yàn)結(jié)果如圖9所示。

Figure 9 Time overhead of resource prediction of web workloads圖9 Web負(fù)載資源預(yù)測(cè)時(shí)間開(kāi)銷

在上述實(shí)驗(yàn)中，PRP的預(yù)測(cè)平均相對(duì)誤差均小于其他比較方法的，最小下降率為9.3%(由于篇幅限制，本節(jié)不再列出預(yù)測(cè)準(zhǔn)確度的測(cè)試數(shù)據(jù))。然而，由圖8和圖9可知，隨著樣本數(shù)據(jù)規(guī)模的增大，PRP方法在預(yù)測(cè)過(guò)程中的時(shí)間開(kāi)銷增長(zhǎng)率平均為6.7%，而3種對(duì)比方法的時(shí)間開(kāi)銷平均增長(zhǎng)率分別為16.7%,19.6%和12.5%。這是因?yàn)镻RP在第1次預(yù)測(cè)的過(guò)程中，已完成周期的識(shí)別，結(jié)合周期性特征，后面新增加的樣本數(shù)據(jù)不用再進(jìn)行周期識(shí)別，減小了時(shí)間開(kāi)銷。而在其他3種方法中，每1次建模和預(yù)測(cè)都要對(duì)全部的數(shù)據(jù)進(jìn)行訓(xùn)練，這樣才能保持一定的準(zhǔn)確度。因此，隨著樣本的增大，其他3種方法的時(shí)間開(kāi)銷明顯增加。

綜上而言，由于PRP充分利用了在線負(fù)載資源使用的周期性特征，將長(zhǎng)期預(yù)測(cè)轉(zhuǎn)化為短周期的資源使用比對(duì)預(yù)測(cè)，因此避免了性能預(yù)測(cè)中的反復(fù)建模問(wèn)題，在資源使用變化周期被識(shí)別后，僅通過(guò)簡(jiǎn)單的周期間資源使用統(tǒng)計(jì)即可獲得預(yù)測(cè)值，同時(shí)保障了預(yù)測(cè)的準(zhǔn)確性。

5 結(jié)束語(yǔ)

針對(duì)當(dāng)前在線負(fù)載資源預(yù)測(cè)方法無(wú)法進(jìn)行長(zhǎng)期準(zhǔn)確的預(yù)測(cè)和由于依賴海量樣本數(shù)據(jù)導(dǎo)致的較大的時(shí)間開(kāi)銷問(wèn)題，本文提出了一種基于周期性特征的在線負(fù)載資源預(yù)測(cè)方法PRP。該方法在分析提取在線負(fù)載資源使用周期性特征的基礎(chǔ)上，采用自相關(guān)函數(shù)方法量化計(jì)算在線負(fù)載資源使用周期，根據(jù)周期計(jì)算結(jié)果將資源使用樣本序列劃分成多個(gè)子序列；然后將子序列分類；最后加權(quán)綜合每一類子序列資源使用變化率，計(jì)算在線負(fù)載資源使用的預(yù)測(cè)值。大量的實(shí)驗(yàn)表明,PRP方法在長(zhǎng)期預(yù)測(cè)的準(zhǔn)確度和時(shí)間開(kāi)銷方面優(yōu)于對(duì)比方法。

在進(jìn)一步的研究工作中，將致力于提升樣本子序列分類精度，并在此基礎(chǔ)上使用更為復(fù)雜的資源預(yù)測(cè)方法進(jìn)行預(yù)測(cè)。