基于多目標(biāo)優(yōu)化的虛擬機(jī)部署策略

劉 軍, 代福成, 辛 寧

(1. 東北大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院, 遼寧 沈陽 110169; 2. 中國(guó)空間技術(shù)研究院 通導(dǎo)部, 北京 100000)

如何高效進(jìn)行虛擬機(jī)部署與管理是云數(shù)據(jù)中心性能保障的主要問題之一[1].虛擬機(jī)部署(virtual machine placement,VMP)是指將虛擬機(jī)(virtual machine, VM)分配至物理服務(wù)器(physical server, PS)的過程.其可以理解為在云數(shù)據(jù)中心利用虛擬化技術(shù)把PS的資源抽象為對(duì)應(yīng)的虛擬資源,再被分配到相互獨(dú)立的VM上的過程.不同的部署策略會(huì)導(dǎo)致VM請(qǐng)求最終映射到不同的PS上,從而直接影響VM性能、系統(tǒng)的資源利用率和負(fù)載均衡值等多個(gè)指標(biāo).通常,VM部署后可以通過是否滿足相應(yīng)的服務(wù)等級(jí)協(xié)議(service-level agreement, SLA)來衡量部署結(jié)果,本文將其表述為VM性能.此外過高的資源占用會(huì)導(dǎo)致SLA違例和PS負(fù)載不均衡,而資源利用率過低又會(huì)導(dǎo)致大量的資源浪費(fèi)和能源消耗.因此,本文針對(duì)VMP過程提出改進(jìn)的深度強(qiáng)化學(xué)習(xí)算法與聚類算法來優(yōu)化這些指標(biāo),在智能化完成VMP過程時(shí),將優(yōu)化目標(biāo)及目標(biāo)占比,以及資源狀態(tài)同時(shí)輸入預(yù)測(cè)器,從而輸出最優(yōu)的部署決策,并加入多維信息的反饋,每一維信息代表一個(gè)優(yōu)化的目標(biāo),從而可以兼顧多個(gè)優(yōu)化目標(biāo),另外為了更快地完成部署,對(duì)資源池中的PS利用改進(jìn)后的均值聚類算法進(jìn)行處理,減少不必要的搜索時(shí)間.

1 相關(guān)工作分析

針對(duì)VMP問題,當(dāng)前學(xué)者提出了不同的算法來優(yōu)化不同的目標(biāo).Gharehpasha等提出了一種將正余弦算法與蟻群算法相結(jié)合的VMP策略,其目標(biāo)是通過平衡活躍服務(wù)器的數(shù)量來最小化云中的功耗和減少資源浪費(fèi)[2];Azizi等提出了一種貪婪隨機(jī)虛擬機(jī)部署算法,通過將VMP部署在更節(jié)能的PS上同時(shí)優(yōu)化系統(tǒng)能耗和資源利用率[3]; Fang等提出了一種改進(jìn)蟻群優(yōu)化算法,同時(shí)平衡物理機(jī)之間的負(fù)載和物理機(jī)內(nèi)部的負(fù)載[4].Han等基于馬爾科夫模型動(dòng)態(tài)部署虛擬機(jī)來減少能源消耗[5].另外,啟發(fā)式算法也可以作為VMP問題的求解方法,例如以最小化能耗為單目標(biāo)的VMP可以利用群智能算法:蟻群算法[6-7]、粒子群算法[8]、模擬退火算法[9]、遺傳算法[10-11]等求解.為了解決多目標(biāo)的VMP問題,Gaggero等通過模型預(yù)測(cè)控制來設(shè)計(jì)虛擬機(jī)和物理機(jī)之間的最優(yōu)映射,實(shí)現(xiàn)云資源的服務(wù)級(jí)別、能源占用、硬件或軟件中斷以及安全策略多個(gè)目標(biāo)之間的權(quán)衡[12].Zhao等提出在滿足虛擬機(jī)可靠性的前提下盡可能地降低能源消耗的VMP算法[13].Liu等針對(duì)基于度量和仿真的調(diào)度算法代價(jià)大、耗時(shí)長(zhǎng)的特點(diǎn),提出了一種自適應(yīng)的調(diào)度算法評(píng)價(jià)方法,該方法只對(duì)不同調(diào)度算法的獎(jiǎng)勵(lì)函數(shù)進(jìn)行了修改,不需要重構(gòu)過程,可以量化調(diào)度算法對(duì)服務(wù)質(zhì)量和運(yùn)行成本的影響[14].Alresheedi等將魚群算法和正余弦算法相結(jié)合實(shí)現(xiàn)多目標(biāo)優(yōu)化,目的是盡可能地加長(zhǎng)PS的開機(jī)時(shí)間,同時(shí)降低功耗,并最大限度地減少違反服務(wù)協(xié)議的情況[15].然而,一方面目前大多數(shù)VMP算法的研究都是基于某約束下的單目標(biāo)優(yōu)化,未考慮復(fù)雜環(huán)境中部署策略的設(shè)計(jì)需要同時(shí)考慮多個(gè)目標(biāo)；另一方面目前的多目標(biāo)部署算法通常是將多目標(biāo)按權(quán)重進(jìn)行線性組合作為目標(biāo)函數(shù),一旦環(huán)境變化,不能短時(shí)間內(nèi)快速優(yōu)化某個(gè)特定的目標(biāo),不適用于動(dòng)態(tài)變化的環(huán)境.

因此,為了解決動(dòng)態(tài)變化環(huán)境中VMP的多目標(biāo)優(yōu)化問題,本文提出一種基于強(qiáng)化學(xué)習(xí)算法(deep Q network,DQN)和均值聚類的VMP(K-means and DQN-based virtual machine placement, KDQNVMP)策略,首先提出改進(jìn)K-means算法對(duì)資源池中的PS按照資源屬性進(jìn)行聚類,然后提出一種基于強(qiáng)化學(xué)習(xí)的VMP多目標(biāo)優(yōu)化算法(DQN-based virtual machine placement, DQNVMP),該算法將強(qiáng)化學(xué)習(xí)算法的獎(jiǎng)勵(lì)由單一信號(hào)改為多維目標(biāo)組成的向量形式,同時(shí)設(shè)定目標(biāo)占比向量決定每個(gè)優(yōu)化目標(biāo)的權(quán)重,其中占比由資源池狀態(tài)反饋決定;本文將優(yōu)化目標(biāo)設(shè)定為VM性能、資源利用率和負(fù)載均衡值,利用改變目標(biāo)占比來達(dá)到動(dòng)態(tài)優(yōu)化多目標(biāo)的目的,從而解決動(dòng)態(tài)環(huán)境下VMP多目標(biāo)優(yōu)化問題,與現(xiàn)有算法不同的是本算法可以針對(duì)性地改變多目標(biāo)占比來適應(yīng)環(huán)境的變化.

2 VMP數(shù)學(xué)模型

本文主要解決VMP過程中的多目標(biāo)優(yōu)化問題,為了更好地描述所提出的DQNVMP算法,下面進(jìn)行數(shù)學(xué)上的描述.

本文假設(shè)數(shù)據(jù)中心(data center,DC)由N個(gè)PS組成:

DC={PS1,PS2,…,PSN} .

(1)

每一個(gè)PS表示為計(jì)算資源R1、內(nèi)存資源R2、存儲(chǔ)資源R3的集合:

PSt={R1,R2,R3} .

(2)

虛擬機(jī)VMs請(qǐng)求序列由M個(gè)VM生成請(qǐng)求組成:

VMs={VM1,…,VMM} .

(3)

每個(gè)VM請(qǐng)求表示為對(duì)計(jì)算資源E1、內(nèi)存資源E2、存儲(chǔ)資源E3的需求集合:

VMj={E1,E2,E3} .

(4)

VM性能vmp可以用來衡量生成VM是否符合要求,定義為需求值與實(shí)際提供值之間的歐氏距離:

(5)

資源池的資源利用率r_utiltotal是指VMP完成后實(shí)際使用的資源和總資源的比值.每一種資源定義見式(6),總資源定義見式(7):

(6)

(7)

其中:r_utilRp表示資源Rp的資源利用率;usedRp表示當(dāng)前資源Rp使用量;totalRp表示資源Rp的總量.

資源池的負(fù)載均衡度r_blb是指VMP完成后系統(tǒng)中的每一個(gè)PS的資源利用率與均值的偏差程度,每一種資源定義見式(8),總體定義見式(9):

(8)

(9)

基于上述的數(shù)學(xué)模型,本文所提出的KDQNVMP算法主要解決在M個(gè)VM請(qǐng)求映射到N個(gè)PS的過程中,隨著資源的動(dòng)態(tài)變化,同時(shí)優(yōu)化vmp,r_utiltotal,r_blb等多個(gè)目標(biāo)的問題.

3 VMP策略設(shè)計(jì)

本文所提出的VMP策略KDQNVMP主要包括兩部分:優(yōu)化K-means算法和DQNVMP算法,如圖1所示.首先利用優(yōu)化均值算法對(duì)PS資源在邏輯上進(jìn)行聚類,形成包括:計(jì)算資源、內(nèi)存資源、計(jì)算內(nèi)存資源、計(jì)算存儲(chǔ)資源、存儲(chǔ)資源等集群,然后利用提出的DQNVMP算法對(duì)VMP請(qǐng)求進(jìn)行分配資源,完成VMP請(qǐng)求到PS的映射.

圖1 KDQNVMP部署策略結(jié)構(gòu)圖

3.1 服務(wù)器資源預(yù)處理

VMP過程可以理解為每個(gè)VM根據(jù)自身的資源需求尋找目標(biāo)PS的過程.由于不同PS之間資源屬性的差異,對(duì)于特定的VM資源請(qǐng)求,并不是所有的PS都可以滿足;而聚類的過程可以按照相似度將同一類PS聚合在一起,產(chǎn)生一系列資源簇.此外,本文引入了強(qiáng)化學(xué)習(xí)算法,空間的范圍會(huì)直接影響算法訓(xùn)練的時(shí)間以及完成部署的時(shí)間,因此,在資源池中按照PS的資源類型進(jìn)行聚類會(huì)極大地優(yōu)化本文的DQNVMP算法.

在聚類算法選取方面,本文使用K-means聚類算法將資源類型劃分為若干資源簇.在原始K-means算法中,聚類中心是根據(jù)樣本點(diǎn)之間的距離進(jìn)行確定的,這樣隨機(jī)確定的第一個(gè)樣本點(diǎn)就會(huì)對(duì)結(jié)果造成不穩(wěn)定的影響,此外由于噪聲點(diǎn)的存在也會(huì)導(dǎo)致最終的聚類結(jié)果不準(zhǔn)確.因此,本文提出了改進(jìn)思路:首先根據(jù)樣本的相似性距離定義每個(gè)樣本的密度屬性,然后選取密度值最大的樣本點(diǎn)作為聚類中心,最后根據(jù)密度和距離選取其他聚類中心.在聚類中心更新時(shí),根據(jù)密度屬性確定孤立點(diǎn),將孤立點(diǎn)的權(quán)重降低,避免孤立點(diǎn)對(duì)集群聚類中心的更新影響,然后進(jìn)行聚類,最后得到滿足一定誤差條件的聚類結(jié)果.具體改進(jìn)方式如下.

1) 初始聚類中心優(yōu)化.在傳統(tǒng)K-means算法中,不同的聚類中心選取策略會(huì)得到不同的結(jié)果,通常情況下,基于距離因素,會(huì)選擇相聚較遠(yuǎn)的兩個(gè)點(diǎn)作為聚類中心,但是這樣會(huì)受噪聲點(diǎn)的影響,導(dǎo)致選取的初始聚類中心變化很大.因此,本文將每個(gè)點(diǎn)周圍分布的數(shù)據(jù)點(diǎn)數(shù)量作為該點(diǎn)的密度屬性,然后在高密度值的區(qū)域內(nèi)按照距離因素進(jìn)行聚類中心的選取:密度最大的點(diǎn)作為第一個(gè)聚類中心,接著在區(qū)域內(nèi)依次選取與已有聚類中心最小距離最大的點(diǎn)作為接下來的聚類中心.聚類中心的數(shù)量由下文的適應(yīng)度函數(shù)確定.這樣根據(jù)樣本的密度屬性和距離屬性的聚類就可以保證聚類結(jié)果有著較好的穩(wěn)定性.其中密度屬性定義為公式(10), 距離屬性定義如式(11)所示:

D(PSx)={PSp∈DC|dis(PSp,PSx)≤r} ,

(10)

(11)

其中:dis(PSp,PSx)表示PSp和PSx之間的距離;r為閾值半徑,其取值為每對(duì)數(shù)據(jù)樣本距離的平均值;DC代表數(shù)據(jù)中心的所有樣本集.

2)基于最大適應(yīng)度函數(shù)的k值選擇.理想的聚類結(jié)果應(yīng)該是保證類別之間數(shù)據(jù)相似度最小,類別內(nèi)部的相似度最大.因此,本文通過定義適應(yīng)度函數(shù)來確定最優(yōu)的k值,從而獲得最優(yōu)的聚類結(jié)果,本文將適應(yīng)度函數(shù) Fitness 設(shè)定為

(12)

(13)

(14)

式中:Dis_out代表類間距;Dis_in代表類內(nèi)距;a,b為常系數(shù),取值受到樣本數(shù)量和維數(shù)的影響;PSi是第i類的聚類中心元素;dis(PSi,PSj)表示PSi和PSj之間的距離;ni是第i類中的樣本數(shù);Si,j是屬于第i類的第j個(gè)樣本.

通過對(duì)式(12)分析,可以發(fā)現(xiàn)Fitness的取值受k值影響,通過對(duì)式(13)和式(14)分析,可以看出隨著k值的增加Dis_out和Dis_in的值都在變小,不同的是Dis_out的下降速度要比Dis_in快一些,如果只是用Dis_out與Dis_in的比值表示適應(yīng)度函數(shù),則結(jié)果就是關(guān)于k的單調(diào)遞增函數(shù),無法獲得最優(yōu)解;因此,本文對(duì)Dis_in作了線性變換,通過微積分原理可以知道適應(yīng)度函數(shù)就是關(guān)于k的單峰值函數(shù),就可以通過實(shí)驗(yàn)找出最理想的k值;通過對(duì)初始聚類結(jié)果的不斷調(diào)整,最后按照資源屬性劃分為k個(gè)PS集群.對(duì)迭代停止條件的確定可以通過簇中變化率小于一定閾值或者一定的迭代次數(shù)作為終止,在本文中,考慮到PS的宕機(jī)問題對(duì)聚類結(jié)果的影響,設(shè)置一定的迭代次數(shù)作為算法的結(jié)束條件.

改進(jìn)后的K-means算法流程圖如圖2所示.首先,輸入資源池中所有PS數(shù)據(jù)集合,根據(jù)式(10)計(jì)算所有樣本點(diǎn)的密度屬性,選擇具有最高密度的樣本點(diǎn)作為第一個(gè)聚類中心,根據(jù)式(12)確定滿足最優(yōu)適應(yīng)度函數(shù)的類別數(shù)目k,然后依次找出與已有聚類中心距離最遠(yuǎn)的點(diǎn),直到確定k個(gè)初始聚類中心;然后根據(jù)式(11)計(jì)算其余樣本點(diǎn)與每個(gè)資源簇中心的距離,并在每次劃歸樣本點(diǎn)后根據(jù)每個(gè)聚類簇中所有樣本的均值進(jìn)行樣本中心的更新,當(dāng)算法迭代的次數(shù)達(dá)到本文設(shè)定的閾值時(shí),按照資源屬性輸出k個(gè)不同的PS集群.

圖2 聚類算法流程圖

3.2 DQNVMP部署算法設(shè)計(jì)

考慮到VMP過程中,每個(gè)VMP是離散的,而且沒有固定的部署策略可以參考,需要利用VMP之后的結(jié)果來評(píng)估VMP策略的優(yōu)劣,因此,選用強(qiáng)化學(xué)習(xí)算法中基于值的Q學(xué)習(xí)算法完成VMP過程,且根據(jù)環(huán)境數(shù)據(jù)尺度大的特點(diǎn),引入了融合神經(jīng)網(wǎng)絡(luò)的Q學(xué)習(xí)算法,即DQN算法,并進(jìn)一步提出了具有多目標(biāo)優(yōu)化特性的DQNVMP算法來更好地完成VMP.三種算法的模型結(jié)構(gòu)對(duì)比見圖3,DQN算法通過利用神經(jīng)網(wǎng)絡(luò)解決了Q學(xué)習(xí)算法中數(shù)據(jù)維度和規(guī)模過大導(dǎo)致的時(shí)空復(fù)雜的問題,而DQNVMP算法通過改變網(wǎng)絡(luò)的輸入與輸出解決了DQN算法中優(yōu)化目標(biāo)單一的問題.與DQN不同的是,在DQNVMP算法中的神經(jīng)網(wǎng)絡(luò)的作用不是建立狀態(tài)和獎(jiǎng)勵(lì)值的關(guān)系,而在網(wǎng)絡(luò)的輸入端加入優(yōu)化目標(biāo)和優(yōu)化目標(biāo)占比,然后訓(xùn)練網(wǎng)絡(luò)去估計(jì)每個(gè)動(dòng)作的優(yōu)化目標(biāo)值,從而選擇出滿足環(huán)境變化的最優(yōu)動(dòng)作,達(dá)到優(yōu)化多個(gè)目標(biāo)的目的.

圖3 Q-learning,DQN和DQNVMP的模型結(jié)構(gòu)對(duì)比

DQNVMP算法框架是在強(qiáng)化學(xué)習(xí)(reinforcement learning,RL)中引入了深度學(xué)習(xí)(deep learning,DL),其可能帶來如下問題:首先是DL需要大量帶標(biāo)簽的數(shù)據(jù)進(jìn)行神經(jīng)網(wǎng)絡(luò)的訓(xùn)練,RL只有單個(gè)獎(jiǎng)勵(lì)返回值;其次DL樣本獨(dú)立,RL狀態(tài)的改變與前一時(shí)刻的狀態(tài)有關(guān);最后DL目標(biāo)是相對(duì)固定的,而RL的代理隨著環(huán)境的變化而改變動(dòng)作.因此,如圖4所示,DQNVMP算法對(duì)此作出如下改進(jìn):通過Q-Learning算法使用獎(jiǎng)勵(lì)來構(gòu)造標(biāo)簽;使用一個(gè)全連接神經(jīng)網(wǎng)絡(luò)作為當(dāng)前預(yù)測(cè)器輸出當(dāng)前F值,使用另外一個(gè)相同結(jié)構(gòu)的神經(jīng)網(wǎng)絡(luò)作為目標(biāo)預(yù)測(cè)器輸出目標(biāo)F值.然后每隔一定時(shí)間間隔更新目標(biāo)預(yù)測(cè)器的參數(shù),而當(dāng)前預(yù)測(cè)器的參數(shù)每回合都進(jìn)行更新.這樣就可以有效地利用神經(jīng)網(wǎng)絡(luò)解決RL算法在處理大數(shù)據(jù)量時(shí)的空間和時(shí)間消耗問題.

圖4 DQNVMP算法框架圖

在實(shí)現(xiàn)算法時(shí),本文使用一個(gè)參數(shù)化的函數(shù)預(yù)測(cè)器來選擇動(dòng)作,表示為

(15)

at=argmaxa∈AgTF(st,mt,a,g;θ) .

(16)

本文所提的函數(shù)預(yù)測(cè)器F的網(wǎng)絡(luò)結(jié)構(gòu)如圖5所示.輸入包括狀態(tài)s、優(yōu)化目標(biāo)m、目標(biāo)占比g,然后通過神經(jīng)網(wǎng)絡(luò)模型預(yù)測(cè)每個(gè)動(dòng)作的價(jià)值,即每個(gè)動(dòng)作帶來測(cè)量目標(biāo)值的改變.此外,在選擇最優(yōu)動(dòng)作時(shí),引入競(jìng)爭(zhēng)網(wǎng)絡(luò)結(jié)構(gòu)[16],將預(yù)測(cè)結(jié)果輸出分成兩路:上路代表動(dòng)作期望流E(s,m,g),指的是所有動(dòng)作的價(jià)值的平均值;下路代表動(dòng)作優(yōu)勢(shì)流A(s,m,g),用于顯示每個(gè)動(dòng)作之間的價(jià)值差別.最后,式(17)將動(dòng)作期望流和動(dòng)作優(yōu)勢(shì)流的和作為每個(gè)動(dòng)作的價(jià)值進(jìn)行輸出,根據(jù)價(jià)值選擇最優(yōu)動(dòng)作.

P={Pa1,…,PaN}={A1(s,m,g)+
E(s,m,g),…,AN(s,m,g)+E(s,m,g)} .

(17)

其中:Ap(s,m,g)+E(s,m,g)表示動(dòng)作ap的價(jià)值；N為動(dòng)作空間的維數(shù).

圖5 函數(shù)預(yù)測(cè)器F的網(wǎng)絡(luò)結(jié)構(gòu)

函數(shù)預(yù)測(cè)器F是根據(jù)代理收集的經(jīng)驗(yàn)進(jìn)行訓(xùn)練的.代理與環(huán)境采用ε-greedy策略進(jìn)行交互,交互過程隨著固定的時(shí)間步數(shù)或者終止事件的發(fā)生而結(jié)束.過程中代理將收集到的大量經(jīng)驗(yàn)存放在經(jīng)驗(yàn)池D中,然后每一次從經(jīng)驗(yàn)池中隨機(jī)取出部分樣本進(jìn)行訓(xùn)練,經(jīng)驗(yàn)池D的定義:

D={si,mi,gi,ai;fi},i=1,…,N.

(18)

其中:si代表狀態(tài)輸入;mi代表優(yōu)化目標(biāo)輸入;gi代表目標(biāo)占比輸入;ai代表采取的動(dòng)作;fi是該動(dòng)作對(duì)應(yīng)的預(yù)測(cè)值的輸出.最后使用回歸損失函數(shù)進(jìn)行預(yù)測(cè)器的訓(xùn)練:

(19)

訓(xùn)練過程就是對(duì)預(yù)測(cè)器輸出結(jié)果的優(yōu)化,優(yōu)化的目標(biāo)則是目標(biāo)函數(shù)值逐漸達(dá)到最小值,這里采用Adam 算法作為優(yōu)化算法[17].通過訓(xùn)練,神經(jīng)網(wǎng)絡(luò)的參數(shù)不斷更新.當(dāng)代理搜集到新的經(jīng)驗(yàn)時(shí),代理使用的訓(xùn)練集和預(yù)測(cè)集都會(huì)發(fā)生變化,為了預(yù)測(cè)結(jié)果的穩(wěn)定性,本文保留M個(gè)最近的經(jīng)驗(yàn)記憶;對(duì)于目標(biāo)占比的設(shè)計(jì),在訓(xùn)練時(shí)可以采取兩種方式:固定目標(biāo)占比或者隨機(jī)目標(biāo)占比;而實(shí)際環(huán)境中,反饋網(wǎng)絡(luò)的引入會(huì)根據(jù)資源池的狀態(tài)進(jìn)行調(diào)整目標(biāo)占比.

此外,代理遵循ε-greedy策略,以概率1-Pε貪婪地選取最優(yōu)動(dòng)作,以概率Pε隨機(jī)地選取動(dòng)作,隨機(jī)性保證了可以獲得比經(jīng)驗(yàn)更優(yōu)的動(dòng)作.故本文將Pε的初始值設(shè)置為1,這樣代理可以在訓(xùn)練開始階段尋找更多的動(dòng)作選擇,隨著迭代過程的進(jìn)行,Pε以α的比例下降,在最優(yōu)的探索與利用平衡點(diǎn)獲得Pε的最優(yōu)值.使得在模型訓(xùn)練的初始階段,可以有更多的動(dòng)作空間進(jìn)行選擇,從而不會(huì)錯(cuò)過任何最優(yōu)選擇,而在訓(xùn)練一段時(shí)間之后,可以根據(jù)之前的最優(yōu)結(jié)果減少搜索空間,加快訓(xùn)練.迭代公式:

(20)

DQNVMP算法的偽代碼如表1所示:

表1 DQNVMP算法

在預(yù)測(cè)器F完成訓(xùn)練之后,就可以根據(jù)資源池的狀態(tài)改變獎(jiǎng)勵(lì)目標(biāo),部署過程只需將當(dāng)前資源狀態(tài)輸入預(yù)測(cè)器,預(yù)測(cè)器會(huì)輸出每個(gè)VM對(duì)應(yīng)的PS,或者當(dāng)前VM無法部署.具體流程圖見圖6,假設(shè)數(shù)據(jù)中心DC中包含N臺(tái)物理服務(wù)器PS,對(duì)于M個(gè)虛擬機(jī)請(qǐng)求的序列VMs,通過本文的部署策略得出所有VM的放置結(jié)果:

VMs-PS={w1,w2,…,wM} .

(21)

其中,wi代表虛擬機(jī)VMi所部署在PS的編號(hào),對(duì)于放置失敗的虛擬機(jī),其對(duì)應(yīng)的wi的值為0.

4 仿真實(shí)驗(yàn)

本文實(shí)驗(yàn)環(huán)境為Windows系統(tǒng),具有8核的CPU和16GB內(nèi)存的PC機(jī),采用Python語言,基于離散事件仿真框架SimPy搭建數(shù)據(jù)中心調(diào)度仿真框架CloudsimPy,并與深度學(xué)習(xí)框架TensorFlow相結(jié)合進(jìn)行改進(jìn)算法的實(shí)驗(yàn)結(jié)果驗(yàn)證.并與粒子群算法PSO、遺傳算法GA以及DQN算法進(jìn)行比較.參數(shù)信息見表2;對(duì)于DQN和DQNVMP,神經(jīng)網(wǎng)絡(luò)的隱藏層的維度設(shè)為400,代理累計(jì)獎(jiǎng)勵(lì)值的學(xué)習(xí)率γ=0.9.設(shè)置Pε=1,α=0.95.經(jīng)過一定次數(shù)的迭代后收斂到最優(yōu)值,從經(jīng)驗(yàn)池中選取的訓(xùn)練樣本規(guī)模為150.拷貝周期T=10，經(jīng)過8 000次迭代后進(jìn)行測(cè)試.假設(shè)資源池中含有200臺(tái)異構(gòu)PS,并按照HP DL388 Gen10,Lenovo 1288H V5和ThinkSystem SR50 3種類型隨機(jī)分布,具體配置參數(shù)如表3所示.同時(shí)為了保證實(shí)驗(yàn)結(jié)果的真實(shí)性,部署請(qǐng)求選取來自阿里巴巴數(shù)據(jù)集群的2017年的服務(wù)請(qǐng)求日志數(shù)據(jù).為了使測(cè)試結(jié)果具有可對(duì)比性,這里的智能優(yōu)化算法和強(qiáng)化學(xué)習(xí)算法均使用相同的測(cè)試數(shù)據(jù)進(jìn)行測(cè)試.

圖6 虛擬機(jī)部署流程圖

表2 對(duì)比算法參數(shù)設(shè)置

表3 物理服務(wù)器配置

為了驗(yàn)證本文優(yōu)化后的K-means算法的有效性,本文將優(yōu)化的聚類部署算法與原算法進(jìn)行比較,結(jié)果對(duì)比如圖7所示.可以看出,KDQNVMP算法的平均完成時(shí)間比DQNVMP算法的平均完成時(shí)間減少了34.07%,極大地優(yōu)化了強(qiáng)化學(xué)習(xí)算法完成虛擬機(jī)部署的時(shí)間.

圖7 虛擬機(jī)部署請(qǐng)求的部署時(shí)間優(yōu)化

對(duì)于待優(yōu)化的目標(biāo):虛擬機(jī)可靠性表示為VM請(qǐng)求資源與獲得資源的參數(shù)化距離,其值越小表示VM性能越好;資源池資源利用率代表對(duì)物理資源的使用情況,其值表示資源是否被充分利用;負(fù)載均衡值是指每個(gè)活躍PS的資源利用率與均值的差值,其值越小表示越接近均衡.為了便于觀察,對(duì)所有目標(biāo)值進(jìn)行歸一化處理見式(22),使最后指標(biāo)值處于[0,1]之間.

(22)

圖8為DQNVMP算法優(yōu)化目標(biāo)隨著迭代次數(shù)的變化情況,在開始迭代的時(shí)候?qū)⒋齼?yōu)化目標(biāo)占比設(shè)置為g=[虛擬機(jī)性能,資源利用率,負(fù)載均衡值]=[1,0,0];隨著迭代過程的進(jìn)行,資源池的狀態(tài)在不斷改變,優(yōu)化目標(biāo)也在不斷變化;從圖中可以看出,由于開始時(shí)設(shè)定的唯一優(yōu)化目標(biāo)是VM性能,因此虛擬機(jī)可靠性的值在不斷縮小,說明虛擬機(jī)性能在不斷提升,部署的虛擬機(jī)多數(shù)為成功的;但是,由于未將利用率和負(fù)載均衡看作優(yōu)化目標(biāo),二者的值都沒有得到很好的優(yōu)化.當(dāng)?shù)? 000次以后,資源利用率的值降低到了一定的程度,此時(shí)通過反饋,會(huì)將優(yōu)化目標(biāo)占比調(diào)整為g=[0.5,1,0],從圖中可以看到資源利用率的值在不斷地優(yōu)化,直到4 000次迭代時(shí),由于系統(tǒng)的負(fù)載均衡值過高,說明虛擬機(jī)分配不合理,此時(shí)通過反饋調(diào)節(jié)將優(yōu)化目標(biāo)占比設(shè)定為g=[0.3,0.5,1],可以發(fā)現(xiàn)4 000次以后,系統(tǒng)的負(fù)載均衡值在不斷地縮小,說明PS之間的差異在減少,有很好的負(fù)載均衡;在以后的迭代過程中,會(huì)根據(jù)要求進(jìn)行目標(biāo)占比調(diào)整,在5 000次迭代之后,可以看出,系統(tǒng)中的3個(gè)指標(biāo)都相對(duì)趨于穩(wěn)定,說明此時(shí)在執(zhí)行VMP時(shí)已經(jīng)可以同時(shí)優(yōu)化多個(gè)目標(biāo).在實(shí)際環(huán)境中,如果沒有明確的要求,系統(tǒng)會(huì)動(dòng)態(tài)地調(diào)整目標(biāo)占比的值,達(dá)到動(dòng)態(tài)平衡及優(yōu)化多目標(biāo)的目的.如果需要優(yōu)化某種特定目標(biāo),只需要改變目標(biāo)占比向量即可.

圖8 優(yōu)化目標(biāo)值隨迭代次數(shù)的變化情況

圖9為KDQNVMP算法與其他算法在服務(wù)器數(shù)量一致時(shí),部署成功率隨虛擬機(jī)請(qǐng)求數(shù)量變化的對(duì)比圖,其中部署成功率是指成功部署的虛擬機(jī)請(qǐng)求數(shù)與已提交虛擬機(jī)請(qǐng)求總數(shù)的比值.從圖中可以看出,KDQNVMP算法成功部署的虛擬機(jī)數(shù)量較其他算法多,這是由于在KDQNVMP算法中,虛擬機(jī)的可靠性和資源利用率作為動(dòng)態(tài)優(yōu)化目標(biāo),代理會(huì)根據(jù)資源池的變化動(dòng)態(tài)調(diào)整優(yōu)化目標(biāo),進(jìn)而使得更多發(fā)送請(qǐng)求的虛擬機(jī)被成功部署.

圖10表示在相同的任務(wù)序列的前提下,同樣的服務(wù)器數(shù)量不同部署算法的最大可完成任務(wù)數(shù)量對(duì)比圖.圖中記錄連續(xù)任務(wù)失敗的閾值為最大可部署虛擬機(jī)數(shù)量,這樣就可以避免單個(gè)任務(wù)失敗導(dǎo)致的數(shù)據(jù)錯(cuò)誤.從圖中可以看出KDQNVMP算法較其他算法可以部署更多的虛擬機(jī)請(qǐng)求,這是由于導(dǎo)致部署失敗的原因是資源不足以滿足虛擬機(jī)的請(qǐng)求值,而KDQNVMP算法中,將資源池資源利用率和各個(gè)服務(wù)器的負(fù)載均衡作為優(yōu)化目標(biāo),極大地減少了資源碎片帶來的資源浪費(fèi)問題,從而部署了更多的虛擬機(jī).

圖9 虛擬機(jī)部署成功率隨虛擬機(jī)部署請(qǐng)求數(shù)量的變化

圖10 最大虛擬機(jī)部署數(shù)量隨服務(wù)器數(shù)量的變化

圖11為不同虛擬機(jī)請(qǐng)求數(shù)量下各個(gè)算法的部署完成時(shí)間的對(duì)比圖.從圖中可以看出,隨著虛擬機(jī)請(qǐng)求數(shù)量的增加,KDQNVMP算法的部署速度較其他算法更快,這是因?yàn)殡S著數(shù)量的增加,學(xué)習(xí)代理可以掌握更完善的模型,從而在保證優(yōu)化目標(biāo)時(shí),保證部署速度的執(zhí)行,此外,聚類之后對(duì)搜索空間進(jìn)行了減小,也極大優(yōu)化了訓(xùn)練速度.綜上,可以發(fā)現(xiàn)通過不斷地改變不同目標(biāo)的占比可以很好完成多目標(biāo)的動(dòng)態(tài)優(yōu)化.在KDQNVMP算法中,通過反饋資源池的狀態(tài),計(jì)算出此時(shí)的多個(gè)優(yōu)化目標(biāo)值,并調(diào)整目標(biāo)占比,可以達(dá)到同時(shí)優(yōu)化多目標(biāo)的目的.對(duì)于有特定需求的任務(wù)請(qǐng)求,也可以根據(jù)任務(wù)的要求進(jìn)行目標(biāo)占比設(shè)定,從而達(dá)到部署結(jié)果的最優(yōu)化.

圖11 虛擬機(jī)部署時(shí)延隨虛擬機(jī)部署請(qǐng)求數(shù)量的變化

5 結(jié) 語

基于聚類算法和強(qiáng)化學(xué)習(xí)算法提出了適合VMP的KDQNVMP策略,重點(diǎn)解決了VMP過程中保證部署速度的同時(shí)對(duì)VM可靠性、資源池利用率和負(fù)載均衡值等多個(gè)目標(biāo)的優(yōu)化問題.與其他算法進(jìn)行對(duì)比,該算法在完成多目標(biāo)優(yōu)化時(shí)能夠同時(shí)優(yōu)化VM性能、資源利用率和負(fù)載均衡值,從而在VMP完成時(shí)間、VM請(qǐng)求部署成功率和最大可部署VM數(shù)量方面較其他算法都有所提高.由于該智能算法可以由代理進(jìn)行自主決策,根據(jù)資源池環(huán)境的變化動(dòng)態(tài)地改變優(yōu)化目標(biāo).所以,在應(yīng)用該算法時(shí),只需要給定環(huán)境獎(jiǎng)勵(lì),智能體就可以自主地尋找最優(yōu)策略.此外,對(duì)于強(qiáng)化學(xué)習(xí)算法而言,環(huán)境的復(fù)雜度越高,優(yōu)化的目標(biāo)越多,代理就可以更好地完成動(dòng)作的訓(xùn)練,從而獲得最優(yōu)的結(jié)果.故本文所提出的基于動(dòng)態(tài)目標(biāo)優(yōu)化的強(qiáng)化學(xué)習(xí)策略在解決其他復(fù)雜目標(biāo)優(yōu)化問題時(shí)具有可以針對(duì)多目標(biāo)中的單目標(biāo)快速優(yōu)化的優(yōu)勢(shì).