基于在線學(xué)習(xí)的云計(jì)算資源預(yù)留策略

郭鵬

(安徽電子信息職業(yè)技術(shù)學(xué)院 軟件學(xué)院，安徽 蚌埠 233000)

為了滿足用戶的實(shí)時(shí)需求，云計(jì)算需要預(yù)留足夠的資源(例如內(nèi)存、CPU)來滿足應(yīng)用程序處于運(yùn)行狀態(tài)時(shí)的要求[1-2]。資源預(yù)留需要準(zhǔn)確地滿足實(shí)時(shí)的需求：資源的過度配置會(huì)導(dǎo)致運(yùn)營成本過高，而資源配置不足可能會(huì)嚴(yán)重降低服務(wù)質(zhì)量，造成中斷和實(shí)時(shí)部署額外資源[3]。現(xiàn)有的資源預(yù)留策略大多使用機(jī)器學(xué)習(xí)這一類方法，但是機(jī)器學(xué)習(xí)算法的探索與應(yīng)用階段具有一定的不可預(yù)測性，可能會(huì)導(dǎo)致資源預(yù)留無法滿足真實(shí)需求。因此，本文提出一種基于在線學(xué)習(xí)的云計(jì)算資源預(yù)留策略，通過實(shí)時(shí)在線學(xué)習(xí)來及時(shí)、準(zhǔn)確地進(jìn)行資源預(yù)留。

1 系統(tǒng)模型

(1)

如式(2)所示，當(dāng)違反資源i的約束沒有超過閾值，則認(rèn)為策略π是一個(gè)可行的策略，即

(2)

因此，資源i的可行約束可以重寫為：

(3)

我們的目標(biāo)是找到一個(gè)能夠使總成本最小化的策略，但由于每一個(gè)時(shí)隙t中的資源請(qǐng)求λt是未知的，這樣的目標(biāo)是難以達(dá)到的。為了解決這個(gè)問題，采用在線凸優(yōu)化框架對(duì)問題進(jìn)行求解。

采用誤差這個(gè)性能指標(biāo)，來對(duì)在線算法的魯棒性進(jìn)行評(píng)價(jià)[4]。誤差是策略π與基準(zhǔn)策略之間的累積損失差。令x*表示基準(zhǔn)策略，可以通過求解下述的問題得到x*。

(4)

于是，誤差R的定義如下：

(5)

通常，對(duì)手的動(dòng)作需要受到資源的約束，即對(duì)手的資源請(qǐng)求不能超過資源i的有限值Λi,max。但是，Λi,max的取值會(huì)影響算法：若Λi,max的值太小，則會(huì)導(dǎo)致算法不穩(wěn)定；若Λi,max的值太大，則資源請(qǐng)求很容易超出資源的總量，導(dǎo)致算法性能下降。

當(dāng)策略π沒有誤差時(shí)，認(rèn)為策略π具有與基準(zhǔn)策略相同的平均性能。然后，引入一類基準(zhǔn)策略，以確保對(duì)時(shí)間T內(nèi)K個(gè)時(shí)隙的都沒有違反約束：

(6)

當(dāng)K與T相同時(shí)，能得到原始的基準(zhǔn)。隨著K值的下降，基準(zhǔn)能夠在一段較短的時(shí)間內(nèi)確保約束不被違反，因此會(huì)產(chǎn)生較高的成本。

2 基于李雅普諾夫的優(yōu)化策略

在時(shí)隙t中調(diào)用在線資源預(yù)留策略以將決策從xt-1更新為xt。為了解釋OLRRS如何執(zhí)行策略更新，實(shí)現(xiàn)以下三個(gè)過程：約束凸化、預(yù)測隊(duì)列以及漂移加懲罰。

由于高斯過程的分位函數(shù)是一個(gè)擬凸函數(shù)，可以為FΛ設(shè)計(jì)一個(gè)凸包絡(luò)函數(shù)，即：

(7)

(8)

如式(9)所示，將預(yù)測隊(duì)列向量定義為Q，該向量中的每個(gè)元素表示每種資源的虛擬隊(duì)列，其中包含過去迭代中預(yù)測的違反約束概率的和。

(9)

通過預(yù)測變量隊(duì)列獲得了時(shí)間平均約束后，接下來解釋如何在OLRRS中更新xt。為了結(jié)合成本和預(yù)測隊(duì)列，使用李雅普諾夫優(yōu)化中的漂移加懲罰技術(shù)，該技術(shù)用于解決受約束的隨機(jī)網(wǎng)絡(luò)優(yōu)化問題[5]。隊(duì)列長度和成本之間的重要性是通過懲罰參數(shù)V控制的。具體來說，首先考慮二次李雅普諾夫漂移，用來衡量我們的策略對(duì)預(yù)測隊(duì)列的影響。二次李雅普諾夫漂移需要滿足如下所示的條件：

(10)

(11)

變量x增大會(huì)使漂移項(xiàng)Δ(t)變小，但同時(shí)會(huì)導(dǎo)致成本VC(x)增加。在最小化漂移加懲罰的過程中，可以在兩個(gè)相互矛盾的目標(biāo)之間取得平衡。在每個(gè)時(shí)隙t中，可以找到漂移加懲罰上限的極小值，并產(chǎn)生了一種在線策略。

進(jìn)一步添加一個(gè)以xt-1為中心的二次正則化器，以確保下一次迭代xt與上次迭代xt-1的值之間變化不大。

在漂移加懲罰的基礎(chǔ)上加入了額外項(xiàng)α‖xt-xt-1‖2，有

(12)

觀察函數(shù)g(x)，可以對(duì)g(x)關(guān)于資源I進(jìn)行分解，然后通過求解每一個(gè)子問題得到資源預(yù)留策略。這能為每個(gè)時(shí)隙t生成了一個(gè)bang-bang臨時(shí)預(yù)留策略。必須保持穩(wěn)定的預(yù)留策略，以允許對(duì)服務(wù)器和資源的操作。與此同時(shí)，使用的正則器，以步長為1/2α的梯度下降法來更新資源。令梯度為零，就能求解得到xi，即

(13)

3 性能評(píng)估

在本小節(jié)中，將本算法與Dynamic Mirror Descent(DMD)框架[6]的實(shí)現(xiàn)進(jìn)行比較，采用真實(shí)的公共數(shù)據(jù)集[7]。數(shù)據(jù)集包含有關(guān)方面的詳細(xì)信息：(1)資源的實(shí)際使用情況；(2)資源的請(qǐng)求；(3)將資源放置在大型集群中的約束。測量使用群集上資源的實(shí)際使用情況，測量的時(shí)間粒度為1 d。

圖1和圖2分別是CPU資源和內(nèi)存資源的使用情況。由圖可知，對(duì)于CPU和內(nèi)存兩種資源，OLRRS都會(huì)較為準(zhǔn)確地預(yù)留資源，并針對(duì)真實(shí)需求變化及時(shí)地做出快速響應(yīng)。DMD卻無法及時(shí)適應(yīng)動(dòng)態(tài)變化，并有違反資源約束的情況發(fā)生。

圖1 CPU資源使用情況 圖2 內(nèi)存資源使用情況

4 結(jié)論

本文設(shè)計(jì)了一種用于云計(jì)算的在線資源預(yù)留策略(OLRRS)。由于云端的工作負(fù)載多變且難以預(yù)測，因此在云環(huán)境中進(jìn)行資源預(yù)留是一個(gè)具有挑戰(zhàn)性的課題。OLRRS使用李雅普諾夫優(yōu)化技術(shù)來進(jìn)行資源策略的調(diào)整：一方面最小化超額配置的資源，提高資源使用率；另一方面，避免了預(yù)留過少的資源導(dǎo)致無法滿足用戶的真實(shí)需求。實(shí)驗(yàn)結(jié)果驗(yàn)證了本算法在資源分配方面的有效性。未來的工作集中于從理論方面證明本算法的性能。