數(shù)據(jù)中心中能量與QoS保障的虛擬機(jī)部署

王以伍 陳躍輝

(成都醫(yī)學(xué)院網(wǎng)絡(luò)中心 四川 成都 610083)

0 引 言

隨著云數(shù)據(jù)中心服務(wù)器數(shù)量與規(guī)模的迅猛增加，能耗已經(jīng)成為數(shù)據(jù)中心面臨的主要問題[1]。目前，數(shù)據(jù)中心的能耗已經(jīng)占據(jù)全世界電力供應(yīng)的1.3%，至2020年將增長至8%[2]。數(shù)據(jù)中心的碳排放為全球總量的0.6%，等同于新西蘭一個(gè)國家的碳排放量，至2020年將增長至2.6%，超過德國的碳排放量?；谔摂M化的服務(wù)器合并技術(shù)是目前降低數(shù)據(jù)中心能耗的最重要手段，該技術(shù)使得同一服務(wù)器上可以運(yùn)行多重應(yīng)用，每種應(yīng)用執(zhí)行于各自的虛擬機(jī)上，并將虛擬機(jī)映射至服務(wù)器。此時(shí)，如何在滿足服務(wù)質(zhì)量QoS的同時(shí)設(shè)計(jì)出高能效的虛擬機(jī)部署算法對(duì)數(shù)據(jù)中心的能效將具有重要影響。

為了解決以上問題，本文在數(shù)據(jù)中心環(huán)境下提出了一種能量與QoS保障的虛擬機(jī)部署算法，算法的優(yōu)勢在于：1) 與傳統(tǒng)的服務(wù)器資源同質(zhì)不同，算法考慮了異構(gòu)條件下的服務(wù)器資源，將從全局考慮QoS保障，將虛擬機(jī)部署問題形式化能耗與全局QoS保障間均衡的優(yōu)化問題；2) 通過參數(shù)與進(jìn)化操作的重定義，提出了一種改進(jìn)的粒子群算法對(duì)虛擬機(jī)部署進(jìn)行求解，并以局部適應(yīng)度優(yōu)先策略更新粒子位置，使算法可以更快收斂。

1 相關(guān)研究

已有研究中，MBFD算法[3]是云數(shù)據(jù)中心中具有代表性的虛擬機(jī)部署能量優(yōu)化算法。該算法首先按當(dāng)前CPU占用對(duì)所有虛擬機(jī)進(jìn)行降低排列，然后將虛擬機(jī)分配至帶來功耗增加幅度最小的服務(wù)器上，實(shí)現(xiàn)能耗優(yōu)化。此外，智能群體算法也廣泛應(yīng)用于虛擬機(jī)部署問題的求解，如遺傳算法GA[4]、模擬退火算法SA[5]、粒子群算法PSO[6]等。然而，以上已有工作均是同質(zhì)的數(shù)據(jù)中心環(huán)境，其方法不適用于異構(gòu)數(shù)據(jù)中心環(huán)境。此外，以最小化能耗為目標(biāo)的單目標(biāo)優(yōu)化虛擬機(jī)部署也可以利用群體智能算法ACO[7]、PSO[8]、SA[1]和GA[9]等進(jìn)行求解。但是，盡管此時(shí)算法得到的能耗有所降低，但在應(yīng)用方面并未提供QoS保障，這使得應(yīng)用負(fù)載的執(zhí)行成功率不高。

考慮QoS保障的虛擬機(jī)部署問題的相關(guān)研究中，文獻(xiàn)[10]提出了基于GA的多目標(biāo)虛擬機(jī)部署算法，算法可以實(shí)現(xiàn)活動(dòng)主機(jī)數(shù)量和通信QoS開銷的最小，均衡數(shù)據(jù)中心中多維度資源的同步利用。文獻(xiàn)[11]提出基于GA的虛擬機(jī)部署算法，可以最小化活動(dòng)數(shù)量和最大化資源利用率。文獻(xiàn)[12]則利用PSO實(shí)現(xiàn)了虛擬機(jī)部署問題中能耗最小和資源浪費(fèi)最小。文獻(xiàn)[13]利用一種文化基因算法實(shí)現(xiàn)虛擬機(jī)部署問題的多目標(biāo)優(yōu)化，包括最小化能耗、網(wǎng)絡(luò)流量及最大化經(jīng)濟(jì)收益。問題在于，以上算法均只考慮了單個(gè)維度上的QoS保障，如通信開銷、資源利用率、經(jīng)濟(jì)收益等，沒有設(shè)計(jì)滿足多維度QoS且從全局角度進(jìn)行QoS保障的虛擬機(jī)部署算法。

比較已有研究，本文將設(shè)計(jì)能量與QoS保障的虛擬機(jī)部署算法，算法利用改進(jìn)的粒子群優(yōu)化可以在滿足全局QoS保障的同時(shí)最小化數(shù)據(jù)中心的能耗。

2 能量與QoS模型

表1給出本文有關(guān)參數(shù)說明。

表1 符號(hào)說明

2.1 能耗模型

數(shù)據(jù)中心的能耗主要集中于服務(wù)器主機(jī)上，功耗主要由CPU、內(nèi)存、磁盤和網(wǎng)絡(luò)接口組成，且CPU是其功耗的主要組成部分，也可認(rèn)為，服務(wù)器的CPU利用率即為其資源利用率。CPU利用率可根據(jù)執(zhí)行負(fù)載的變化建立為時(shí)間的函數(shù)，故服務(wù)器的能耗也可基于CPU利用率進(jìn)行建立。將服務(wù)器總體定義為：

(1)

式中：En為時(shí)間段[t1,t2]間服務(wù)器的總能耗，u(t)為變化的CPU利用率，P(u(t))為時(shí)間t時(shí)服務(wù)器的功耗，Pmax為服務(wù)器滿載時(shí)的最大功耗，c為服務(wù)器為空閑狀態(tài)時(shí)的能耗比例。

2.2 QoS效用函數(shù)

數(shù)據(jù)密集型服務(wù)(簡稱服務(wù))的QoS需求包括多種屬性，如：響應(yīng)時(shí)間、可靠性、吞吐量和可用性等。通常，這些屬性可劃分為兩類：積極型QoS屬性和消極型QoS屬性。積極型QoS屬性(如可靠性和可用性)表明其屬性值越大，服務(wù)器運(yùn)行相關(guān)服務(wù)的性能越好。相反，消極型QoS屬性(如響應(yīng)時(shí)間和延時(shí))的屬性值越低，性能越好。本文通過將積極型QoS屬性轉(zhuǎn)換為消極型QoS屬性的方式(乘以-1)而僅考慮消極型QoS屬性。

考慮擁有r種QoS屬性的服務(wù)s的QoS需求矢量qs={q1(s),q2(s),…,qr(s)}，其中，qk(s)值(1≤k≤r)代表服務(wù)s的第k個(gè)屬性值。所有l(wèi)個(gè)服務(wù)的屬性矢量可表示為QS={q1(S),q2(S),…,qr(S)}，S={s1,s2,…,sm}，其中，qk(S)表示所有服務(wù)的第k個(gè)屬性值的累加。表2給出了服務(wù)的QoS屬性值的累加函數(shù)。

表2 QoS屬性值的累加函數(shù)

每種服務(wù)涉及多種QoS屬性，會(huì)帶來不同的量化程度，這不利于滿足全局的QoS保障。因此，需要設(shè)計(jì)一種QoS效用函數(shù)，將QoS屬性值q(s)矢量映射為單一實(shí)數(shù)值?？紤]n臺(tái)服務(wù)器組成的數(shù)據(jù)中心，PS={ps1,ps2,…,psn}，可部署的m臺(tái)虛擬機(jī)集合為VM={vm1,vm2…,vmm}。一種服務(wù)由部署于一臺(tái)主機(jī)上一臺(tái)虛擬機(jī)完成，同時(shí)需要滿足其具體資源需求(即CPU和內(nèi)存)和QoS約束。一種服務(wù)僅運(yùn)行一臺(tái)虛擬機(jī)上，且服務(wù)的QoS通常與虛擬機(jī)提供相關(guān)。因此，QoS效用函數(shù)需要將所有屬性值在多維度以統(tǒng)一計(jì)算的標(biāo)準(zhǔn)化方式將其映射至域[0,1]之間，從而量化全局的QoS保障性能。

定義1QoS效用函數(shù)。假設(shè)有r個(gè)QoS屬性，運(yùn)行于第j臺(tái)服務(wù)器psj(1≤j≤n)的虛擬機(jī)的第i個(gè)服務(wù)si∈S(1≤i≤l)的QoS效用函數(shù)可表示為：

(2)

那么，所有服務(wù)S的QoS效用函數(shù)為：

(3)

同時(shí):

(4)

2.3 能量與QoS保障的虛擬機(jī)部署模型

數(shù)據(jù)中心的虛擬機(jī)部署問題的優(yōu)化目標(biāo)是在滿足全局QoS保障的同時(shí)最小化能耗。通過重寫式(1)和式(2)，可以將能量與QoS保障的虛擬機(jī)部署問題形式化為多目標(biāo)約束最優(yōu)化問題，即帶有全局QoS效用函數(shù)最大化問題(即全局QoS保障)的全局能耗最小化問題，定義為：

(5)

(6)

約束條件包括QoS約束和資源能力約束，即：

(7)

(8)

(9)

(10)

式中：n表示數(shù)據(jù)中心中服務(wù)器的數(shù)量，m表示部署虛擬機(jī)的數(shù)量，Ej表示服務(wù)器j的能耗，Ck表示QoS約束值，Ck≥qk(S)。

式(5)-式(6)定義的虛擬機(jī)部署最優(yōu)化問題為NP問題，該問題需要在滿足所有約束(式(7)-式(10))的前提下實(shí)現(xiàn)最小化能耗和最大化全局QoS效用值，得到最優(yōu)虛擬機(jī)部署方案。本文將提出一種基于改進(jìn)粒子群算法的部署策略，在能量與全局QoS保障均衡下實(shí)現(xiàn)最優(yōu)虛擬機(jī)部署。

3 算法設(shè)計(jì)

3.1 PSO算法

粒子群算法PSO是一種基于群體智能的隨機(jī)式搜索算法。作為一種進(jìn)化計(jì)算技術(shù)，比較同類方法，PSO執(zhí)行速度更快，效率更高，已經(jīng)廣泛應(yīng)用于人工智能神經(jīng)網(wǎng)絡(luò)訓(xùn)練、模糊系統(tǒng)控制等諸多領(lǐng)域。PSO通過迭代式提供侯選解的方式不斷改進(jìn)解的質(zhì)量，使其最終收斂于最優(yōu)解。

PSO中群體的每個(gè)成員即為一個(gè)粒子，每個(gè)粒子代表搜索問題的一個(gè)可行解。每個(gè)粒子擁有兩個(gè)參數(shù)：速率和位置。粒子位置與適應(yīng)度值相關(guān)，可用于評(píng)估解的質(zhì)量。PSO開始于隨機(jī)產(chǎn)生的一個(gè)粒子群，并迭代尋找問題最優(yōu)解。以Xlbest表示粒子找到歷史最優(yōu)解，Xgbest表示整個(gè)種群找到的歷史最優(yōu)解，在每一次迭代中，粒子的速度和位置通過下式進(jìn)行更新：

(11)

(12)

為了求解能量與QoS保障的虛擬機(jī)部署問題，PSO需作以下改進(jìn)：1) 傳統(tǒng)PSO僅適用于求解連續(xù)優(yōu)化問題，不適用于求解離散優(yōu)化問題，這表明PSO的相關(guān)參數(shù)和進(jìn)化操作必須重新定義；2) 必須重新設(shè)計(jì)粒子更新策略和解碼策略，以表達(dá)虛擬機(jī)與服務(wù)器間的映射關(guān)系。

3.2 改進(jìn)PSO

本文對(duì)傳統(tǒng)PSO的改進(jìn)主要針對(duì)兩點(diǎn)：1) 重新定義了PSO的參數(shù)和進(jìn)化操作，使其可以求解能量與QoS保障的虛擬機(jī)部署優(yōu)化這類離散最優(yōu)化問題；2) 采用了一種局適應(yīng)度優(yōu)先策略更新粒子位置信息。

3.2.1相關(guān)定義

傳統(tǒng)PSO僅適用于求解連續(xù)最優(yōu)化問題，無法求解能量與QoS保障的虛擬機(jī)部署優(yōu)化這類離散最優(yōu)化問題。為此，需要重新定義PSO的相關(guān)參數(shù)和進(jìn)化操作。

基于以上五種定義，可將式(11)-式(12)轉(zhuǎn)換為下式：

(13)

(14)

3.2.2局部適應(yīng)度優(yōu)先策略

傳統(tǒng)的PSO采用隨機(jī)選擇策略，可能影響PSO的全局收斂，降低求解效率。為了增強(qiáng)解的質(zhì)量，本文設(shè)計(jì)一種局部適應(yīng)度優(yōu)先策略更新粒子位置。

為了便于表述，將粒子的第一個(gè)維度上的每個(gè)位值稱為局部位置。在一個(gè)最優(yōu)時(shí)段[t1,t2]間運(yùn)行于該服務(wù)器的所有虛擬機(jī)的CPU利用率被稱為局部能量適應(yīng)度，定義為：

(15)

式中：uij(t)表示運(yùn)行于服務(wù)器主機(jī)j的虛擬機(jī)i的CPU利用率，m表示運(yùn)行于服務(wù)器j上的虛擬機(jī)的總數(shù)量。

運(yùn)行于服務(wù)器上的所有虛擬機(jī)的QoS屬性之和稱為局部QoS適應(yīng)度，定義為：

(16)

基于式(15)和式(16)，局部適度度定義為：

(17)

對(duì)于局部適應(yīng)度優(yōu)先策略，當(dāng)PSO需要更新一個(gè)粒子的確定局部位置時(shí)，服務(wù)器上擁有最大適應(yīng)度的虛擬機(jī)將具有更高的概率被選擇去更新局部位置。局部適應(yīng)度代表服務(wù)器的CPU利用率和QoS屬性之和。

3.2.3解碼策略

為了改進(jìn)解的效率，基于服務(wù)器與虛擬機(jī)間一對(duì)多的映射特點(diǎn)，設(shè)計(jì)了一種二維解碼策略，如圖1所示，其中，n為服務(wù)器數(shù)量，m為部署于同一服務(wù)器上的虛擬機(jī)的數(shù)量。

圖1 二維解碼

由圖可知，一個(gè)粒子的第一維為n位二進(jìn)制矢量，矢量中的每一個(gè)位即對(duì)應(yīng)于數(shù)據(jù)中心中的一個(gè)服務(wù)器。這里，“1”代表在當(dāng)前虛擬機(jī)部署方案中對(duì)應(yīng)服務(wù)器是活動(dòng)的，“0”代表服務(wù)器為待機(jī)狀態(tài)。一個(gè)粒子的第二維為部署于服務(wù)器上的虛擬機(jī)組成的集合。那么，每個(gè)虛擬機(jī)子集即與一個(gè)活動(dòng)的服務(wù)器相關(guān)聯(lián)。例如：粒子的第一維的第一個(gè)位值為0，則表明數(shù)據(jù)中心的第一個(gè)服務(wù)器應(yīng)被開啟。第一、第二個(gè)虛擬機(jī)應(yīng)部署于第一個(gè)服務(wù)器上。比較傳統(tǒng)的一維粒子解碼方法，二維解碼策略不僅可以有效縮短粒子解碼長度，降低搜索時(shí)間，而且能夠反映虛擬機(jī)的靜態(tài)優(yōu)化部署特征。

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

4.1 實(shí)驗(yàn)配置

利用CloudSim[14]對(duì)算法進(jìn)行仿真分析。模擬一個(gè)由1 000個(gè)異構(gòu)服務(wù)器組成的數(shù)據(jù)中心環(huán)境，服務(wù)器具體由兩類組成：一類是HP Proliant G4，配置CPU為3 720 MIPS，內(nèi)存為4 GB，峰值功耗為117 W；另一類是HP Proliant G5，配置CPU為5 320 MIPS，內(nèi)存為4 GB，峰值功耗為135 W。服務(wù)器具有不同的性能配置和能耗特征[3]。每個(gè)服務(wù)器運(yùn)行帶有四種QoS屬性(響應(yīng)時(shí)間、可用性、吞吐量和可靠性)的一個(gè)或多個(gè)數(shù)據(jù)密集型服務(wù)，服務(wù)負(fù)載產(chǎn)生現(xiàn)實(shí)的2 500個(gè)Web服務(wù)間。

為了更好地反映實(shí)際的虛擬機(jī)請(qǐng)求，以Amazon EC2的兩類虛擬機(jī)實(shí)例作為虛擬機(jī)請(qǐng)求參數(shù)，包括Micro實(shí)例，配置500 MIPS CPU和613 MB內(nèi)存，以及Small實(shí)例，配置1 000 MIPS CPU和1 700 MB內(nèi)存。

選取改進(jìn)最佳適應(yīng)遞減算法MBFD[3]、最佳適應(yīng)算法BF[15]、能耗優(yōu)化的粒子群算法EOPSO[12]作為性能比較的基準(zhǔn)算法。前兩種算法在裝箱思想對(duì)虛擬機(jī)部署進(jìn)行建模，區(qū)別在于對(duì)于服務(wù)器的資源占用排序分為遞減和遞增排列，兩種算法在優(yōu)化服務(wù)器使用數(shù)量、降低服務(wù)器閑置能耗上擁有較好效果。EOPSO算法與本文同為粒子群優(yōu)化，但其粒子進(jìn)化操作及解碼均與本文有所區(qū)別。其他參數(shù)配置如下：能量模型中參數(shù)c設(shè)置為0.6，粒子群的初始種群設(shè)置為20，粒子進(jìn)化的最大迭代次數(shù)設(shè)置為30，仿真實(shí)驗(yàn)運(yùn)行10次，實(shí)驗(yàn)結(jié)果取其平均值。

4.2 結(jié)果分析

實(shí)驗(yàn)1觀察數(shù)據(jù)中心所有活動(dòng)服務(wù)器的總體能耗情況，結(jié)果如圖2所示?？梢钥闯觯疚乃惴‥QPSO比較其他算法節(jié)省了更多的能耗，且在虛擬機(jī)請(qǐng)求數(shù)量增加時(shí)，其能耗增加的敏感度也是最弱的?？傮w上，EQPSO可以節(jié)省30%左右的能耗，原因在于BF和MBFD算法需要全局信息，即數(shù)據(jù)中心中異構(gòu)服務(wù)器的能耗信息，而僅僅考慮了多維度的資源約束，未考慮在虛擬機(jī)部署過程中不同服務(wù)器的能效的不同。PSOVMP算法雖然也利用粒子群的求解思想，但其求解速度更慢，導(dǎo)致很多非最優(yōu)解，能耗更大。本文算法引入了有效的粒子速率與位置更新機(jī)制，使其更易找到最優(yōu)部署方案，也更易于實(shí)現(xiàn)算法收斂，改進(jìn)了解的質(zhì)量。最終，本文算法得到的活動(dòng)服務(wù)器也較少，總體能耗更低。

圖2 能耗

實(shí)驗(yàn)2觀察全局QoS保障性能，結(jié)果如圖3所示。由于四種QoS屬性擁有不同的單位，需要根據(jù)QoS效用函數(shù)將QoS矢量值映射為單一實(shí)數(shù)值，即進(jìn)行標(biāo)準(zhǔn)化后均映射至[0,1]之間，如此，全局QoS保障的取值范圍為[0,4]。結(jié)果表明，本文算法EQPSO的全局QoS保障平均為2.74，高于其他算法。原因在于其他算法側(cè)重于局部QoS最優(yōu)化，而局部QoS優(yōu)化無法滿足所有數(shù)據(jù)密集型服務(wù)的全局QoS保障。本文算法通過更低的能耗和更高的全局QoS保障獲得了更好的性能。

圖3 全局QoS保障

實(shí)驗(yàn)3觀察服務(wù)器空閑的能耗比例變化對(duì)算法性能的影響，即式(1)中的c值,結(jié)果如圖4所示。實(shí)驗(yàn)中設(shè)置c=0.1，并以步長0.1遞增至0.9，同時(shí)將QoS約束的數(shù)量設(shè)置為1，QoS權(quán)重設(shè)置為0.8。可以看出：1) 當(dāng)c值遞增時(shí)，能耗大幅增加，也反映出本文算法能耗越低時(shí)，c值也越小，即空閑的服務(wù)器數(shù)量越多；2) 全局QoS保障并未隨c值的變化發(fā)生劇烈波動(dòng)。

圖4 服務(wù)器空閑的能耗比例對(duì)性能的影響

實(shí)驗(yàn)4觀察QoS約束數(shù)量對(duì)算法性能的影響，結(jié)果如圖5所示。QoS約束數(shù)量代表數(shù)據(jù)中心中用戶對(duì)數(shù)據(jù)密集型服務(wù)的QoS需求。實(shí)驗(yàn)中設(shè)置QoS約束為1，并以步長1遞增至4，c設(shè)置為0.6，w設(shè)置為0.8，其他屬性權(quán)重隨機(jī)產(chǎn)生于[0,0.2]之間。結(jié)果表明，本文算法得到的能耗與QoS保障并未隨著QoS約束數(shù)量的變化發(fā)生過大波動(dòng)，總體較為平衡，說明算法具有較好的魯棒性，可適應(yīng)于不同數(shù)量的QoS需求。

圖5 QoS約束數(shù)量對(duì)性能的影響

實(shí)驗(yàn)5觀察QoS權(quán)重w對(duì)算法性能的影響，結(jié)果如圖6所示。實(shí)驗(yàn)中設(shè)置w=0.1，并以步長0.1遞增至0.9，同時(shí)將QoS約束的數(shù)量設(shè)置為1，c設(shè)置為0.6。結(jié)果表明：1) 全局QoS保障在w從0.6遞增至0.9時(shí)也是遞增的，即全局QoS保障性能越好，w值越高；2) 算法能耗并未隨著w值的變化發(fā)生劇烈波動(dòng)，穩(wěn)定性較好；3) 綜合比較，在能耗與QoS均較優(yōu)時(shí)，w處于[0.7,0.9]間。

圖6 QoS權(quán)重對(duì)性能的影響

實(shí)驗(yàn)6觀察算法計(jì)算時(shí)間，結(jié)果如圖7所示。實(shí)驗(yàn)中將虛擬機(jī)請(qǐng)求數(shù)量從1 000遞增至2 000，c設(shè)置為0.6，w設(shè)置為0.8。結(jié)果表明，當(dāng)虛擬機(jī)請(qǐng)求數(shù)量遞增時(shí)，算法的計(jì)算時(shí)間增速較慢，計(jì)算時(shí)間與虛擬機(jī)請(qǐng)求數(shù)量之間幾乎為線性關(guān)系，算法具體較好的可擴(kuò)展性，可適應(yīng)于不同規(guī)模的虛擬機(jī)部署請(qǐng)求。

圖7 計(jì)算時(shí)間

5 結(jié) 語

提出了一種基于能量與多維度QoS保障的虛擬機(jī)部署算法。建立了虛擬機(jī)部署的QoS模型，設(shè)計(jì)了一種通用QoS效用函數(shù)，實(shí)現(xiàn)了不同形式QoS的標(biāo)準(zhǔn)量化，并在此基礎(chǔ)上，將虛擬機(jī)部署問題形式化為滿足全局QoS保障的同時(shí)實(shí)現(xiàn)能耗的最小化；設(shè)計(jì)了一種改進(jìn)粒子群算法的虛擬機(jī)部署策略對(duì)優(yōu)化問題進(jìn)行求解，該策略通過相關(guān)參數(shù)和進(jìn)化操作的重新定義，以及局部適應(yīng)度優(yōu)先的粒子位置更新機(jī)制，實(shí)現(xiàn)能耗與全局QoS保障的均衡優(yōu)化。實(shí)驗(yàn)結(jié)果表明，算法不僅在能耗與全局QoS保障性能上是優(yōu)于同類算法的，并且在穩(wěn)定性和可擴(kuò)展性方面也有較好的表現(xiàn)。