使用帶分類參數(shù)貝葉斯網(wǎng)的虛擬機(jī)性能預(yù)測(cè)

尚聰聰,郝 佳,張彬彬,岳 昆

(云南大學(xué) 信息學(xué)院,昆明 650500)

1 引 言

基礎(chǔ)設(shè)施即服務(wù)(Infrastructure as a Service,IaaS)是云計(jì)算[1]的一種資源使用模式,云計(jì)算通過虛擬化技術(shù)向用戶提供計(jì)算、存儲(chǔ)等資源,用戶按需租用這些資源并支付費(fèi)用.目前大部分云服務(wù)提供商,例如阿里云[注]Alibaba Cloud. https://www.aliyun.com/,2018/06/05.、亞馬遜云[注]Amazon EC2. http://aws.amazon.com/ec2/,2018/06/05.等,都是以虛擬機(jī)的形式,向用戶提供可選的若干種CPU、內(nèi)存以及網(wǎng)絡(luò)帶寬等資源配置套件[2].這種業(yè)務(wù)模式,并未真正實(shí)現(xiàn)資源的按需分配,難以適應(yīng)動(dòng)態(tài)變化的資源需求,導(dǎo)致資源利用率低下.為了提高資源利用率以及實(shí)現(xiàn)按應(yīng)用需求分配虛擬機(jī)所需資源,首先需要準(zhǔn)確預(yù)測(cè)特定虛擬機(jī)特征配置下的性能[3].

然而,準(zhǔn)確預(yù)測(cè)虛擬機(jī)特定特征配置下的性能,存在以下困難.一方面,虛擬機(jī)的性能與特征之間存在復(fù)雜的非線性依賴關(guān)系[4,5],虛擬機(jī)的各個(gè)特征之間相互作用共同決定了虛擬機(jī)性能.另一方面,由于虛擬機(jī)上所運(yùn)行的負(fù)載具有復(fù)雜性、動(dòng)態(tài)性以及不確定性,這也增加了虛擬機(jī)性能預(yù)測(cè)的難度.其中,應(yīng)用負(fù)載的復(fù)雜性,是指多個(gè)虛擬機(jī)上的應(yīng)用負(fù)載所需資源不同,可能會(huì)導(dǎo)致物理主機(jī)的資源使用超過所能承受的峰值;應(yīng)用負(fù)載的動(dòng)態(tài)性,是指不同負(fù)載的運(yùn)行情況會(huì)隨著時(shí)間變化而改變,可能會(huì)產(chǎn)生多個(gè)應(yīng)用之間的通信,影響虛擬機(jī)性能;應(yīng)用負(fù)載的不確定性,是指應(yīng)用負(fù)載在不同時(shí)刻所需的資源大小不確定,可能會(huì)導(dǎo)致固定資源特征分配下虛擬機(jī)的性能產(chǎn)生波動(dòng).

學(xué)界已開展了很多虛擬機(jī)性能預(yù)測(cè)的研究,一些研究通過建立虛擬機(jī)特征和性能之間的線性模型,來實(shí)現(xiàn)虛擬機(jī)性能預(yù)測(cè).文獻(xiàn)[6]提出基于硬件計(jì)數(shù)器的虛擬機(jī)性能估算方法;文獻(xiàn)[7]提出基于指數(shù)平滑模型的虛擬機(jī)預(yù)測(cè)算法.然而,雖然線性模型使用簡(jiǎn)單,但它難以有效擬合特征和性能之間的非線性依賴關(guān)系,從而導(dǎo)致模型的預(yù)測(cè)結(jié)果不夠理想.

另一些工作通過建立虛擬機(jī)特征與性能之間的非線性關(guān)系模型來實(shí)現(xiàn)性能預(yù)測(cè).其中,文獻(xiàn)[8]提出基于奇異值近似分解的虛擬機(jī)性能預(yù)測(cè)方法,分析虛擬機(jī)性能的變化趨勢(shì),但難以將結(jié)果進(jìn)行直觀展示;文獻(xiàn)[9]基于馬爾科夫方法來預(yù)測(cè)虛擬機(jī)特定狀態(tài)下的性能,但對(duì)時(shí)間序列太過依賴;文獻(xiàn)[10]提出基于遺傳優(yōu)化的人工神經(jīng)網(wǎng)絡(luò)方法來預(yù)測(cè)不同配置組合情況下虛擬機(jī)性能,并從中找出具有最小資源開銷的特征配置組合;文獻(xiàn)[11]提出基于人工神經(jīng)網(wǎng)絡(luò)的迭代模型來預(yù)測(cè)給定特征配置下的虛擬機(jī)性能,雖然可以對(duì)虛擬機(jī)特征和性能之間存在的非線性關(guān)系建模,但耗費(fèi)大量計(jì)算資源、且容易出現(xiàn)過擬合.綜上所述,上述方法和模型中,虛擬機(jī)特征和性能之間的不確定性依賴關(guān)系仍然難以有效表達(dá),且當(dāng)虛擬機(jī)性能產(chǎn)生波動(dòng)時(shí),這些模型則無法準(zhǔn)確預(yù)測(cè)這種性能波動(dòng)情況.

文獻(xiàn)[12]提出基于貝葉斯網(wǎng)(Bayesian networks,BN)來對(duì)虛擬機(jī)特征和性能之間存在的不確定性依賴關(guān)系建模的方法,用以虛擬機(jī)性能評(píng)估.貝葉斯網(wǎng)模型用條件概率表達(dá)各個(gè)信息要素之間的相關(guān)關(guān)系,能在有限、不完整、不確定的信息條件下進(jìn)行學(xué)習(xí)和推理.BN是一個(gè)有向無環(huán)圖(Directed Acyclic Graphic,DAG),圖中的節(jié)點(diǎn)表示隨機(jī)變量,節(jié)點(diǎn)間的邊表示變量之間的依賴關(guān)系.每個(gè)節(jié)點(diǎn)都有一張條件概率表(Conditional Probability Table,CPT),用來刻畫這種依賴的程度.BN能夠有效地表達(dá)虛擬機(jī)各個(gè)特征以及特征與性能之間存在的非線性依賴關(guān)系,以及這種依賴關(guān)系的強(qiáng)弱,基于BN可進(jìn)行概率推理計(jì)算[13].

然而,對(duì)于一般的BN模型來說,模型的構(gòu)建依賴于數(shù)據(jù)的訓(xùn)練結(jié)果,當(dāng)虛擬機(jī)特征取值的組合未出現(xiàn)在訓(xùn)練數(shù)據(jù)集中時(shí),BN便無法預(yù)測(cè)這些特征所對(duì)應(yīng)的性能.此外,當(dāng)影響虛擬機(jī)性能的特征節(jié)點(diǎn)數(shù)量較多時(shí),會(huì)導(dǎo)致性能節(jié)點(diǎn)的CPT組合情況復(fù)雜,增加參數(shù)計(jì)算以及性能預(yù)測(cè)的復(fù)雜性.

因此,本文采用一種帶分類參數(shù)的BN模型(Class parameter augmented BN,CBN).該模型首先對(duì)虛擬機(jī)進(jìn)行分類,然后基于分類結(jié)果與對(duì)應(yīng)的虛擬機(jī)性能值,構(gòu)造CBN模型以實(shí)現(xiàn)對(duì)任意特征配置下的虛擬機(jī)性能預(yù)測(cè).經(jīng)過對(duì)常見的分類模型比較,基于集成學(xué)習(xí)的隨機(jī)森林(Random Forest,RF)模型與其他分類算法相比,能夠處理高維度的復(fù)雜特征數(shù)據(jù),預(yù)測(cè)速度快且準(zhǔn)確率高,還能夠平衡不均衡數(shù)據(jù)的預(yù)測(cè)誤差,具有分類結(jié)果穩(wěn)定且不易過擬合等優(yōu)點(diǎn)[14].因此,本文采用隨機(jī)森林作為CBN模型的分類器.

綜上,本文的主要工作包括:

1)基于虛擬機(jī)特征數(shù)據(jù)訓(xùn)練隨機(jī)森林模型作分類器.

2)基于虛擬機(jī)的分類和性能數(shù)據(jù),訓(xùn)練CBN模型,用于表達(dá)虛擬機(jī)特征和性能之間的依賴關(guān)系.

3)基于CBN的概率推理預(yù)測(cè)任意虛擬機(jī)特征配置下的虛擬機(jī)性能和性能波動(dòng)情況.

本文第2節(jié)給出CBN模型的構(gòu)造方法,第3節(jié)給出基于CBN預(yù)測(cè)虛擬機(jī)性能的方法,第4節(jié)給出實(shí)驗(yàn)結(jié)果,第5節(jié)總結(jié)全文內(nèi)容并展望將來的工作.

2 CBN模型構(gòu)建

影響虛擬機(jī)性能的特征包括硬件特征、軟件特征以及運(yùn)行時(shí)環(huán)境特征[9].這些特征的不同組合值,構(gòu)成不同配置的虛擬機(jī).當(dāng)某個(gè)應(yīng)用在特定的虛擬機(jī)配置上運(yùn)行時(shí),應(yīng)用的運(yùn)行時(shí)間可以反映當(dāng)前虛擬機(jī)的性能.為了能夠方便地獲取虛擬機(jī)特征-性能數(shù)據(jù),我們把應(yīng)用在特定特征配置虛擬機(jī)上的運(yùn)行時(shí)間作為當(dāng)前虛擬機(jī)的性能值.

假設(shè)共有m種可調(diào)整的虛擬機(jī)特征,其中包括虛擬CPU的個(gè)數(shù)、內(nèi)存大小、同時(shí)運(yùn)行的虛擬機(jī)個(gè)數(shù)等,分別表示為V1,V2…,Vm.假設(shè)每一個(gè)特征都有i種取值情況,如特征Vm的取值為vm1,vm2,…,vmi,則m個(gè)特征可構(gòu)成im種不同虛擬機(jī)特征配置.本文通過RF分類算法,將im種虛擬機(jī)分為r個(gè)類別.在CBN模型中,m個(gè)虛擬機(jī)經(jīng)過分類后構(gòu)成一個(gè)分類節(jié)點(diǎn)Z,Z有r種可能取值,表示為z1,z2,…,zr.下面給出CBN的定義.

定義1.CBN為一個(gè)有向無環(huán)圖,表示為GCBN=(U,E,θ),其中:

·U為GCBN中的節(jié)點(diǎn)集合,包括虛擬機(jī)分類節(jié)點(diǎn)Z和虛擬機(jī)性能節(jié)點(diǎn)T,即U=Z∪T.

·E表示U中各個(gè)節(jié)點(diǎn)之間邊的集合.用e(Ui,Uj)來表示一條由節(jié)點(diǎn)Ui指向節(jié)點(diǎn)Uj的有向邊,則e(Ui,Uj)∈E,i≠j.在CBN模型中,只包含一條由分類節(jié)點(diǎn)Z指向性能節(jié)點(diǎn)T的邊.

·θ表示GCBN中各個(gè)節(jié)點(diǎn)的參數(shù)集合,由各個(gè)節(jié)點(diǎn)的條件概率表構(gòu)成,度量了虛擬機(jī)性能節(jié)點(diǎn)T對(duì)虛擬機(jī)分類節(jié)點(diǎn)Z的依賴程度的大小.

在CBN中,無父親的節(jié)點(diǎn)Z的參數(shù)為邊緣概率分布值P(Z),節(jié)點(diǎn)Z的子節(jié)點(diǎn)T的參數(shù)值為條件概率分布值P(T|Z).P(Z)和P(T|Z)構(gòu)成了CBN的參數(shù)θ.

CBN的構(gòu)建包括結(jié)構(gòu)構(gòu)建和參數(shù)計(jì)算,結(jié)構(gòu)構(gòu)建部分包括RF分類器的訓(xùn)練,以及根據(jù)分類結(jié)果的結(jié)構(gòu)學(xué)習(xí);參數(shù)計(jì)算部分包括對(duì)虛擬機(jī)分類節(jié)點(diǎn)Z和特征節(jié)點(diǎn)T的后驗(yàn)概率計(jì)算.

2.1 CBN模型中隨機(jī)森林分類器訓(xùn)練

隨機(jī)森林回歸算法以CART決策樹[14]為基礎(chǔ),利用Bootstrap重采樣方法,從含有L個(gè)樣本的訓(xùn)練數(shù)據(jù)集D中,有放回地抽取s個(gè)樣本組成新的樣本集合S,該樣本集合稱為Bootstrap樣本.分別對(duì)每個(gè)Bootstrap樣本構(gòu)建一棵CART決策樹,最終根據(jù)所有決策樹分類結(jié)果進(jìn)行投票,將投票結(jié)果作為隨機(jī)森林的最終分類結(jié)果[15].

構(gòu)建決策樹時(shí),我們選用基尼系數(shù)(GINI)作為當(dāng)前虛擬機(jī)特征分裂的依據(jù).選擇具有最小Gain_GINI值的虛擬機(jī)特征Vm及其相應(yīng)的特征值vmi,作為當(dāng)前CART分類樹的最優(yōu)分裂節(jié)點(diǎn)及其相應(yīng)的分裂特征值.Gain_GINI的值越小,則證明被分裂后的樣本“純凈度”越高,則選擇該特征值作為分裂依據(jù)的效果越好.對(duì)于含有s個(gè)虛擬機(jī)特征-性能樣本的集合S來說,它的GINI系數(shù)計(jì)算方式如式(1)所示.

(1)

在(1)中,pk表示虛擬機(jī)分類為第k類的概率,即Z為zk(k∈{1,2,…,r})的概率值.

對(duì)于含有s個(gè)樣本的集合S來說,根據(jù)虛擬機(jī)特征Vm的第i個(gè)屬性值,即vmi,將S劃分為S1和S2兩部分后,Gain_GINI的的計(jì)算方式如(2)所示.

(2)

其中,n1和n2分別為S1和S2中樣本的個(gè)數(shù),GINI(S1)和GINI(S2)的計(jì)算方式類似于公式(1).對(duì)于特征Vm來說,通過公式(2)分別計(jì)算當(dāng)選擇vm1,vm2,…,vmi作為分裂特征值時(shí),對(duì)應(yīng)的Gain_GINI值的大小,并選擇使得Gain_GINI最小的特征值,作為虛擬機(jī)特征Vm的最優(yōu)分裂值.即,

(3)

對(duì)于樣本集S來說,計(jì)算所有特征Vm的最優(yōu)二分方案,選擇其中的最小值,作為樣本集合S的最優(yōu)二分方案,即,

(4)

上述方案中,虛擬機(jī)特征Vm和它的特征值vmi,即為樣本S的最優(yōu)分裂特征及其最優(yōu)分裂特征值.

通過上述方法,可構(gòu)造一棵CART決策樹.當(dāng)給定一組虛擬機(jī)特征配置時(shí),可用該樹預(yù)測(cè)出當(dāng)前特征配置的所屬類別.當(dāng)隨機(jī)森林中一共包含t棵CART分類樹時(shí),它們的分類結(jié)果的投票結(jié)果即為虛擬機(jī)的分類.

綜上,虛擬機(jī)分類的隨機(jī)森林模型構(gòu)建步驟如下:

1)從訓(xùn)練數(shù)據(jù)集D中,采用Bootstrap方法抽取s個(gè)數(shù)據(jù)樣本作為第i棵樹的訓(xùn)練集Dsi(0

2)如果queue非空,則取出一個(gè)節(jié)點(diǎn)node.基于node中的虛擬機(jī)特征-性能數(shù)據(jù)樣本Dnode和m個(gè)虛擬機(jī)特征節(jié)點(diǎn),依次計(jì)算特征節(jié)點(diǎn)Vj(1≤j≤m)的每一個(gè)特征值vjk(1≤k≤r)所對(duì)應(yīng)的Gain_GINI值大小,并找出最小的Gain_GINI值min和對(duì)應(yīng)的特征節(jié)點(diǎn)Vj和特征值vjk.如果min大于閾值q,則根據(jù)分裂特征Vj和特征值vjk將當(dāng)前節(jié)點(diǎn)分裂出兩個(gè)孩子節(jié)點(diǎn),并將兩個(gè)孩子節(jié)點(diǎn)加入隊(duì)列queue,否則不做操作.重復(fù)執(zhí)行上述過程,直到queue為空,完成當(dāng)前決策樹的構(gòu)造.

3)重復(fù)步驟1)和2),直至建立t棵CART分類樹,最終構(gòu)成虛擬機(jī)分類的隨機(jī)森林模型RF.

算法1具體描述了上述思想.

算法1.基于隨機(jī)森林的虛擬機(jī)分類

輸入:D:虛擬機(jī)特征-性能數(shù)據(jù)集;

L:虛擬機(jī)特征-性能數(shù)據(jù)集中的數(shù)據(jù)條數(shù)

t:隨機(jī)森林中決策樹的數(shù)量

m:虛擬機(jī)特征的個(gè)數(shù)

r:虛擬機(jī)特征的取值個(gè)數(shù)

q:GINI系數(shù)最小的閾值

Gm[m]:用于存儲(chǔ)虛擬機(jī)特征的最小Gain_GINI值

Vm[m]:用于存儲(chǔ)最小Gain_GINI值對(duì)應(yīng)的特征值

Gr[r]:用于存儲(chǔ)同一個(gè)虛擬機(jī)特征按不同取值分裂的Gain_GINI值

Vr[r]:用于存儲(chǔ)虛擬機(jī)一個(gè)特征所有取值

輸出:RF:基于隨機(jī)森林的虛擬機(jī)分類模型

步驟:

1.fori←1 totdo

2.Dsi←Bootstrap(S,D)//為第i棵樹選擇樣本Dsi

3.root←makeNode(Dsi)//集合Dsi作為根節(jié)點(diǎn)

4.queue←root//將root加入隊(duì)列

5.whilequeue!=Φdo

6.node←pop(queue)//隊(duì)列取出一個(gè)節(jié)點(diǎn)

7.Dnode←OutData(node)//獲取當(dāng)前node的數(shù)據(jù)

8.forj←1 tomdo

9.r←CountNum(Dnode,j)//當(dāng)前特征取值個(gè)數(shù)

10. fork←1 tordo

11.Gr[k]←Calculate(Gain_GINI(Dnode,j,k))

//計(jì)算虛擬機(jī)特征Vj的取值為vjk時(shí)的Gain_GINI值的大小存儲(chǔ)到數(shù)組Gr[r]中

12.Vr[k]←findValue(Dnode,j,k)//第k個(gè)特征值

13.k←k+1

14.endfor

15.Gm[j]←findNum(MIN(Gr[r]))

//找到Gr[r]數(shù)組中最小的Gain_GINI值

16.Vm[j]←relevantValue(Gm[j],Gr[r],Vr[k])

//找到最小Gain_GINI值對(duì)應(yīng)的特征取值

17.j←j+1

18.endfor

19.min←findNum(MIN(Gm[m]))//最小Gain_GINI值

20.ifmin>q

21.Vj←relevantFeature(min,Gm[m])

//找到最小Gain_GINI值對(duì)應(yīng)的特征

22.vjk←relevantValue(min,Gm[m],Vm[j])

//找到min對(duì)應(yīng)的虛擬機(jī)特征的取值

23.lchild,rchild←makeNode(split(node,Vj,vjk))

//根據(jù)分裂特征和分裂值,將節(jié)點(diǎn)node分成左右節(jié)點(diǎn)

24.queue←lchild,rchild//將節(jié)點(diǎn)存儲(chǔ)到隊(duì)列中

25.endif

26.endwhile

27.RF←root//將root加入隨機(jī)森林中

28.endfor

29.returnRF

基于算法1可實(shí)現(xiàn)對(duì)多個(gè)虛擬機(jī)進(jìn)行分類.當(dāng)給出一組未知虛擬機(jī)特征時(shí),分別由隨機(jī)森林中的t棵樹分類,分類結(jié)果按少數(shù)服從多數(shù)進(jìn)行投票,投票結(jié)果即表示該組特征的分類結(jié)果.算法1運(yùn)行時(shí),假設(shè)每一棵決策樹需要計(jì)算m個(gè)特征的Gain_GINI值系數(shù),則基于含有N個(gè)樣本的訓(xùn)練數(shù)據(jù)集D,來構(gòu)建含有t棵決策樹的隨機(jī)森林時(shí),該算法的時(shí)間復(fù)雜度為O(t(mt*logN)).

例1.

使用表1中的數(shù)據(jù),根據(jù)算法1構(gòu)建CART決策樹.首先計(jì)算每個(gè)屬性的每個(gè)取值的Gain_GINI值.根據(jù)公式(2)可以算出:

CPUnum取1為分裂值時(shí),Gain_GINI值=

2/4(1-(1^2+0^2+0^2))+2/4(1-((1/2)^2+(1/2)^2))=1/4

CPUnum取2為分裂值時(shí),Gain_GINI值=1/4

MemorySize取1024為分裂值時(shí),Gain_GINI值=1/2

MemorySize取512為分裂值時(shí),Gain_GINI值=1/2

CPUFreq取3.3為分裂值時(shí),Gain_GINI值=1/4

CPUFreq取3.6為分裂值時(shí),Gain_GINI值=1/4

表1 虛擬機(jī)特征與分類實(shí)例
Table 1 Example for classification of virtual machines

CPUnum(個(gè))MemorySize(MB)CPUFreq(GHz)Z15123.3z1210243.6z325123.6z2110243.3z1

根據(jù)算法1,我們選取Gain_GINI值最小的屬性和取值作為最優(yōu)分裂特征和分裂值.本例我們選擇CPUnum是否取1作為分裂特征和分裂值,將數(shù)據(jù)分為實(shí)例分為兩部分.第一部分包含z1與z4,第二部分包含z2與z3.對(duì)于第一部分,類別標(biāo)簽只有z1,所以無需再分.對(duì)于第二部分重復(fù)上述步驟,得到MemorySize是否取1024為最優(yōu)分裂特征和分裂值.由此構(gòu)建出如圖1所示的決策樹.

圖1 CART決策樹實(shí)例Fig.1 An example of CART decision tree

2.2 CBN的結(jié)構(gòu)構(gòu)造與參數(shù)學(xué)習(xí)

根據(jù)先驗(yàn)知識(shí),可確定虛擬機(jī)特征將對(duì)虛擬機(jī)性能產(chǎn)生不確定性影響,且它們之間存在相互依賴關(guān)系.所以CBN的結(jié)構(gòu)中只存在一條由Z指向T的有向邊,即e(Z,T).基于算法1可將所有的虛擬機(jī)分為r個(gè)類別,即Z?{z1,z2,…,zr},而性能節(jié)點(diǎn)有j種取值,即T1,T2…Tj.例1是一個(gè)CBN的特征選擇以及結(jié)構(gòu)構(gòu)造示例.

待分類的虛擬機(jī)特征為虛擬CPU個(gè)數(shù)(CPUnum)、內(nèi)存大小(MemorySize)、同時(shí)運(yùn)行的虛擬機(jī)個(gè)數(shù)(coVMS)和物理主機(jī)的CPU主頻(CPUFreq),取值情況如表2所示.運(yùn)行算法1后,這些不同的特征配置被分為4個(gè)類別,即z1,z2,z3,z4,它們所對(duì)應(yīng)的性能值分別為T1,T2,T3,T4.表1展示了具體取值情況.

基于這4個(gè)特征的分類結(jié)果Z和所對(duì)應(yīng)的性能值T,可以構(gòu)造CBN的結(jié)構(gòu).

例2.

對(duì)于CBN的參數(shù)計(jì)算來說,我們運(yùn)用最大似然估計(jì)(Maximum Likelihood Estimation,MLE)來計(jì)算CBN中各個(gè)節(jié)點(diǎn)的參數(shù),即節(jié)點(diǎn)的CPT.計(jì)算公式如(5)所示.

(5)

其中,θijk表示當(dāng)節(jié)點(diǎn)Ui取值為k,且Ui的父節(jié)點(diǎn)取值為j時(shí)節(jié)點(diǎn)Ui的參數(shù).Num((Ui=k),Pa(Ui=j))表示當(dāng)節(jié)點(diǎn)Ui取值為k,且Ui的父節(jié)點(diǎn)取值為j時(shí),虛擬機(jī)特征-性能數(shù)據(jù)集D中的數(shù)據(jù)條數(shù).而Num(Pa(Ui=j))表示Ui的父節(jié)點(diǎn)取值為j時(shí)的數(shù)據(jù)條數(shù).在CBN中,所有節(jié)點(diǎn)的CPT,構(gòu)成了CBN的參數(shù)值θ.

表2 虛擬機(jī)特征、分類與性能實(shí)例
Table 2 Example for features and the classification of virtual machines

CPUnum(個(gè))MemorySize(MB)coVMS(個(gè))CPUFreq(GHz)ZT151213.3z1T12102423.6z2T23150033.6z3T34204813.3z4T4

3 基于概率推理的虛擬機(jī)性能預(yù)測(cè)

基于CBN結(jié)構(gòu)及參數(shù)值,可以預(yù)測(cè)任意虛擬機(jī)特征配置下的的性能.當(dāng)某一組虛擬機(jī)特征配置為{v11,v21,…,vm1}時(shí),經(jīng)過RF算法分類后,該虛擬機(jī)被分為類別zi.基于CBN可得到zi所對(duì)應(yīng)的虛擬機(jī)性能值分別為T1,T2,…,Ti的條件概率.具有最大條件概率值的性能即為CBN預(yù)測(cè)的虛擬機(jī)性能值.

例如,CBN的結(jié)構(gòu)構(gòu)建和參數(shù)計(jì)算情況如圖2所示.圖中節(jié)點(diǎn)Z為虛擬機(jī)分類節(jié)點(diǎn),所有的虛擬機(jī)特征配置被分為3個(gè)類別,即z1,z2和z3,經(jīng)過計(jì)算后,這三個(gè)類別的取值概率分別為0.1,0.4和0.5.而虛擬機(jī)的性能節(jié)點(diǎn)T的取值共有3種,通過MLE可計(jì)算相應(yīng)類別下的條件概率值.圖1中節(jié)點(diǎn)T的CPT展示的是當(dāng)虛擬機(jī)類別為z1時(shí),性能分別為T1,T2和T3的條件概率值.

圖2 CBN示例Fig.2 Example for CBN model

當(dāng)Z的取值為zi時(shí),性能節(jié)點(diǎn)T的取值為Ti的條件概率計(jì)算公式如(6)所示.

(6)

使用RF算法對(duì)虛擬機(jī)的某一組特征進(jìn)行分類后,結(jié)果記為zi,然后用CBN分別預(yù)測(cè)當(dāng)前配置性能為T1,T2,…,Ti的概率.預(yù)測(cè)過程即是計(jì)算P(T=T1|Z=zi)),P(T=T2|Z=zi)),…,P(T=Ti|Z=zi))的過程.最終,我們選擇具有最大后驗(yàn)概率的性能值,作為當(dāng)前配置下虛擬機(jī)性能的預(yù)測(cè)值.

算法2描述了具體的性能預(yù)測(cè)過程.

算法2.基于CBN的虛擬機(jī)性能預(yù)測(cè)

輸入:v11,v21….vm1:待預(yù)測(cè)虛擬機(jī)的虛擬機(jī)配置

j:性能值個(gè)數(shù)

Tj[j]:存儲(chǔ)虛擬機(jī)所有的性能值

Pj[j]:用于存儲(chǔ)每個(gè)性能值的條件概率

輸出:X:CBN預(yù)測(cè)的最大概率值

Ti:基于CBN所預(yù)測(cè)的性能值

步驟:

1.zi←RF(v11,v21….vm1)

//RF根據(jù)m個(gè)特征取值得到分類結(jié)果

2.fork←1 tojdo

3.Pj[k]←Calculate(P(T=Tk|Z=zi))

//分類結(jié)果為zi時(shí),性能為Tk的條件概率

4.endfor

5.X←findMax(Pj[j])//找到性能預(yù)測(cè)最大概率

6.Ti←findPerformance(X,Pj[j],Tj[j])

//根據(jù)X找到對(duì)應(yīng)的性能值,作為性能預(yù)測(cè)值

7.returnXandTi

基于算法2,當(dāng)虛擬機(jī)分類為zi時(shí),分別計(jì)算它所對(duì)應(yīng)的j個(gè)性能值的條件概率,則算法2的時(shí)間復(fù)雜度為O(j).

例3.

假定某臺(tái)虛擬機(jī)配置為CPUnum為2個(gè),MemorySize為1024MB,CPUFreq為3.3GHz.根據(jù)例1的出的CART決策樹可以得到類別為z3.再根據(jù)相應(yīng)的CPT表,查詢z3的性能值,就可以得到該虛擬機(jī)的性能預(yù)測(cè)值.

4 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)環(huán)境如下:Intel(R)Core(TM)i5-6200U處理器;2.40GHz的CPU主頻,8GB內(nèi)存,Windows10 64位操作系統(tǒng),Python 3.5.2:Anaconda 4.2.0(64-bit)為開發(fā)平臺(tái).

為了測(cè)試本文提出的CBN模型在預(yù)測(cè)虛擬機(jī)性能時(shí)的有效性和準(zhǔn)確性,我們使用阿里云公布的批處理任務(wù)運(yùn)行數(shù)據(jù)集BatchInstance做測(cè)試[注]Alibaba ClusterData, https://github.com/alibaba/clusterdata, 2018/08/27..該數(shù)據(jù)集包含了部署在阿里云中的某個(gè)實(shí)際運(yùn)行的集群(共包含13000臺(tái)物理主機(jī))上的虛擬機(jī),在12個(gè)小時(shí)內(nèi)運(yùn)行批處理任務(wù)的信息統(tǒng)計(jì)情況.這個(gè)數(shù)據(jù)集共有34762條數(shù)據(jù),其中包含了任務(wù)開始與結(jié)束的時(shí)間戳、任務(wù)ID、CPU利用率、內(nèi)存利用率等特征,以及所對(duì)應(yīng)的任務(wù)運(yùn)行時(shí)間.

為了驗(yàn)證CBN預(yù)測(cè)的準(zhǔn)確性,選擇任務(wù)ID、最多CPU利用個(gè)數(shù)、平均CPU 利用個(gè)數(shù)、最大內(nèi)存利用情況以及平均內(nèi)存利用情況,作為虛擬機(jī)待分類特征,分別表示為job_id,real_cpu_max,real_cpu_avg,real_mem_max,real_mem_avg.同時(shí),用虛擬機(jī)上任務(wù)的響應(yīng)時(shí)間response_time作為待預(yù)測(cè)的虛擬機(jī)性能.我們將所有虛擬機(jī)性能數(shù)據(jù)分為20個(gè)類別,分別表示為C1,C2,…,C20.采用十折交叉驗(yàn)證的思想,將數(shù)據(jù)均分為10份,輪流將其中9份作為訓(xùn)練數(shù)據(jù)集來建立CBN模型,一份作為測(cè)試數(shù)據(jù)集,進(jìn)行模型構(gòu)建和驗(yàn)證.每次驗(yàn)證都能得到對(duì)應(yīng)的虛擬機(jī)性能預(yù)測(cè)準(zhǔn)確率.我們把實(shí)驗(yàn)分為以下兩類,首先按照特征取值對(duì)虛擬機(jī)分類,采用隨機(jī)森林的分類結(jié)果與決策樹的分類結(jié)果做對(duì)比,驗(yàn)證隨機(jī)森林模型對(duì)虛擬機(jī)分類的準(zhǔn)確性.其次,將CBN對(duì)虛擬機(jī)性能的預(yù)測(cè)結(jié)果和線性模型的結(jié)果做對(duì)比,說明CBN對(duì)于虛擬機(jī)性能預(yù)測(cè)的準(zhǔn)確性.

4.1 隨機(jī)森林算法分類準(zhǔn)確性

為了驗(yàn)證隨機(jī)森林算法對(duì)虛擬機(jī)分類的準(zhǔn)確性,首先根據(jù)BatchInstance數(shù)據(jù)集中的response_time的大小,人為地將不同虛擬機(jī)特征配置分為20個(gè)類別.基于十折交叉驗(yàn)證的思想[16],將數(shù)據(jù)均分為10份,輪流將其中9份作為訓(xùn)練數(shù)據(jù),1份作為測(cè)試數(shù)據(jù),基于這10組數(shù)據(jù)分別運(yùn)行隨機(jī)森林算法和決策樹分類算法,并統(tǒng)計(jì)兩個(gè)算法分類的準(zhǔn)確率.圖3是兩個(gè)算法分類的準(zhǔn)確性對(duì)比情況,橫坐標(biāo)表示實(shí)驗(yàn)結(jié)果,縱坐標(biāo)表示準(zhǔn)確率.

圖3 隨機(jī)森林和決策樹的平均分類準(zhǔn)確率Fig.3 Classification accuracy rate of random forest and decision tree

從圖3中,可以看出,隨機(jī)森林算法在進(jìn)行虛擬機(jī)分類時(shí),準(zhǔn)確率平均可以達(dá)到80.87%,而決策樹的分類準(zhǔn)確率平均只有25.05%.由此可以說明我們提出的基于隨機(jī)森林的虛擬機(jī)分類算法具有較高的準(zhǔn)確率.另外,十組數(shù)據(jù)中,隨機(jī)森林算法分類準(zhǔn)確率最大值與最小值之差為1.1%,而決策樹算法為1.9%.由此可以說明隨機(jī)森林算法對(duì)數(shù)據(jù)的適應(yīng)性更高.

為了驗(yàn)證隨著數(shù)據(jù)量的增長(zhǎng),兩個(gè)模型的分類準(zhǔn)確率是否有所變化,我們做如下測(cè)試:將數(shù)據(jù)集以5000為一個(gè)增長(zhǎng)單位,依次驗(yàn)證數(shù)據(jù)量為5000、10000、15000、20000、25000、30000條時(shí),隨機(jī)森林和決策樹對(duì)虛擬機(jī)分類的準(zhǔn)確性.結(jié)果如圖4所示.

圖4 分類模型準(zhǔn)確率與數(shù)據(jù)量變化關(guān)系對(duì)比Fig.4 Relationships between classification model and amount of data

從圖4中可以得出,對(duì)虛擬機(jī)分類時(shí),隨機(jī)森林算法和決策樹算法分類的準(zhǔn)確率均隨著數(shù)據(jù)量的增長(zhǎng)而增長(zhǎng).隨著數(shù)據(jù)量從5000增長(zhǎng)到30000,隨機(jī)森林算法的分類準(zhǔn)確率提高了10.8%,而決策樹算法的分類準(zhǔn)確率提高了6.4%.

4.2 CBN模型預(yù)測(cè)準(zhǔn)確性

為了驗(yàn)證CBN模型預(yù)測(cè)虛擬機(jī)性能的準(zhǔn)確性,我們用CBN的預(yù)測(cè)結(jié)果和線性模型的預(yù)測(cè)結(jié)果對(duì)比說明.圖5為基于十折交叉驗(yàn)證,用CBN和線性模型來預(yù)測(cè)虛擬機(jī)性能的準(zhǔn)確率.從圖5可以得出,線性模型在預(yù)測(cè)虛擬機(jī)性能時(shí),平均準(zhǔn)確率只能達(dá)到22.7%.而CBN模型在預(yù)測(cè)虛擬機(jī)性能時(shí),平均準(zhǔn)確率達(dá)到76.36%.

圖5 CBN模型和線性模型預(yù)測(cè)結(jié)果準(zhǔn)確率Fig.5 Prediction accuracy rate of CBN and linear model

同樣地,將數(shù)據(jù)量分別設(shè)置為5000、10000、15000、20000、25000、30000條時(shí),對(duì)比CBN和線性模型的虛擬機(jī)性能預(yù)測(cè)準(zhǔn)確性.結(jié)果如圖6所示.

圖6 性能預(yù)測(cè)準(zhǔn)確率與數(shù)據(jù)量變化對(duì)比Fig.6 Relationship between accuracy of CBN and amount of data

圖6中可以看出,CBN模型對(duì)于虛擬機(jī)性能的預(yù)測(cè)準(zhǔn)確率遠(yuǎn)高于線性模型,且準(zhǔn)確率隨著數(shù)據(jù)量的增長(zhǎng)而增長(zhǎng).當(dāng)數(shù)據(jù)量從5000增加到30000時(shí),CBN模型的預(yù)測(cè)準(zhǔn)確率提高了12%.而線性模型的預(yù)測(cè)準(zhǔn)確性卻沒有太大改變,最高的預(yù)測(cè)準(zhǔn)確率只達(dá)到了24%.

圖7 CBN預(yù)測(cè)概率分布與實(shí)際概率分布Fig.7 CBN predictions and experimental data distribution

由于CBN可以預(yù)測(cè)出虛擬機(jī)性能的波動(dòng)情況,我們隨機(jī)選擇四組數(shù)據(jù),用CBN推理出各個(gè)可能取得性能值的概率分布情況,并用推理結(jié)果和實(shí)際數(shù)據(jù)的分布情況作對(duì)比,驗(yàn)證CBN預(yù)測(cè)的虛擬機(jī)性能概率分布是否和實(shí)際情況相符合.具體情況如圖7所示,圖中性能值為虛擬機(jī)上應(yīng)用的運(yùn)行時(shí)間.

從圖7中可以看出,CBN預(yù)測(cè)虛擬機(jī)性能的結(jié)果,與實(shí)際數(shù)據(jù)的分布情況相符合.

為了驗(yàn)證CBN預(yù)測(cè)的虛擬機(jī)性能分布情況是否與實(shí)際的數(shù)據(jù)分布情況相符,分別計(jì)算以上四組數(shù)據(jù)中,最大概率估計(jì)值相對(duì)于從實(shí)際數(shù)據(jù)中統(tǒng)計(jì)得到的概率值的誤差和相對(duì)誤差.

誤差的計(jì)算方式為error=PC-PS,而相對(duì)誤差的計(jì)算方式為relativeerror=|PC-PS|/PS,PC表示由CBN模型所預(yù)測(cè)得到的性能概率值,PS表示從實(shí)際數(shù)據(jù)統(tǒng)計(jì)出來的性能概率值.計(jì)算結(jié)果如表3所示,為了區(qū)分4組數(shù)據(jù),使用1,2,3,4為4組數(shù)據(jù)編號(hào).

表3 CBN預(yù)測(cè)結(jié)果的誤差與相對(duì)誤差
Table 3 Error and relative error of CBN predictions

數(shù)據(jù)集responsetime/sPCPSerrorrelativeerror1400.610.60.011.67%2400.70.660.069.01%3200.790.750.045.33%4500.770.750.022.66%

從表3中可以看出CBN對(duì)于虛擬機(jī)性能分布概率的預(yù)測(cè)誤差中,相對(duì)誤差最低的只有1.67%,而最大的誤差達(dá)到9.01%.通過計(jì)算,可以得出CBN預(yù)測(cè)的平均誤差為:0.0325,而相對(duì)誤差的平均值為:4.67%.

通過以上實(shí)驗(yàn),驗(yàn)證了我們所提出方法在虛擬機(jī)分類,以及虛擬機(jī)性能預(yù)測(cè)時(shí)的有效性和準(zhǔn)確性.

5 總結(jié)與展望

本文針對(duì)虛擬機(jī)特征與性能之間存在不確定性依賴關(guān)系,導(dǎo)致虛擬機(jī)性能難以被準(zhǔn)確預(yù)測(cè)的問題,提出了一種基于帶分類參數(shù)的BN模型,來實(shí)現(xiàn)虛擬機(jī)性能預(yù)測(cè).該模型克服了傳統(tǒng)BN對(duì)于訓(xùn)練集中未出現(xiàn)過的數(shù)據(jù),無法進(jìn)行預(yù)測(cè)的局限性,以及當(dāng)虛擬機(jī)特征節(jié)點(diǎn)過多時(shí),性能預(yù)測(cè)的復(fù)雜度增加、準(zhǔn)確率下降的情況.實(shí)驗(yàn)結(jié)果表明本文提出的方法預(yù)測(cè)虛擬機(jī)性能的高效性和準(zhǔn)確性.

然而,本文提出的隨機(jī)森林模型是將虛擬機(jī)作為一個(gè)整體進(jìn)行分類,針對(duì)虛擬機(jī)不同類型的特征差異性所導(dǎo)致的分類誤差尚未充分考慮.因此,在后續(xù)方案中,我們考慮將多個(gè)虛擬機(jī)的分類細(xì)化,以實(shí)現(xiàn)更加準(zhǔn)確地預(yù)測(cè)虛擬機(jī)的性能.