蘭文姍，陳冬林，李 偉，鄂雪妮

(1．武漢理工大學(xué)經(jīng)濟(jì)學(xué)院，湖北 武漢 430070;2．福建新奇特車業(yè)服務(wù)有限公司上海分公司，上海 201824)

為保證自身利益和服務(wù)質(zhì)量，云計(jì)算服務(wù)提供商與客戶通常需要簽訂服務(wù)等級(jí)協(xié)議(service－level agreement，SLA)［1］。然而云計(jì)算環(huán)境下數(shù)據(jù)中心的大規(guī)模性，服務(wù)器之間可能存在的異構(gòu)性，以及節(jié)點(diǎn)之間可能存在負(fù)載不均等現(xiàn)象，都可能嚴(yán)重威脅到機(jī)器性能，導(dǎo)致系統(tǒng)無法按時(shí)按量地提供服務(wù)，造成SLA違約［2］。因此，研究在云計(jì)算環(huán)境下如何建立有效的負(fù)載均衡機(jī)制以保證SLA具有重要的理論和現(xiàn)實(shí)意義。

在負(fù)載均衡的研究上，劉萬軍等［3］利用一種改進(jìn)的粒子群優(yōu)化算法對(duì)云計(jì)算負(fù)載均衡問題進(jìn)行求解;文獻(xiàn)［4］通過隨機(jī)爬山的局部優(yōu)化算法來分配虛擬機(jī)任務(wù)，提出了一種資源負(fù)載均衡調(diào)度算法，實(shí)現(xiàn)了在減少任務(wù)執(zhí)行時(shí)間的同時(shí)提高資源的負(fù)載均衡度;DOMINIQUE［5］通過神經(jīng)預(yù)測器來動(dòng)態(tài)感知未來負(fù)載需求，相應(yīng)地開關(guān)服務(wù)器來節(jié)約能耗，并把用戶請(qǐng)求調(diào)度到虛擬機(jī)上;馮小靖等提出了云計(jì)算環(huán)境下的DPSO資源負(fù)載均衡算法，運(yùn)用離散粒子群算法實(shí)現(xiàn)資源負(fù)載均衡［6］;DHINESH等提出了一種蜜蜂行為激發(fā)的負(fù)載均衡算法，以實(shí)現(xiàn)負(fù)載均衡下虛擬機(jī)的最大吞吐量，同時(shí)減少執(zhí)行時(shí)間和等待時(shí)間［7］;LU等提出了JIQ(加入空閑隊(duì)列)的分布式負(fù)載均衡算法，從而減小任務(wù)排隊(duì)等待時(shí)間［8］;ANTON等提出了基于系統(tǒng)能耗的云數(shù)據(jù)中心資源管理，同時(shí)考慮QoS期望與設(shè)備能耗特點(diǎn)來實(shí)現(xiàn)系統(tǒng)資源調(diào)度與負(fù)載均衡［9］。但是這些研究在通過虛擬機(jī)遷移實(shí)現(xiàn)負(fù)載均衡時(shí)往往以降低系統(tǒng)能耗或減小系統(tǒng)處理時(shí)間為目標(biāo)，鮮有基于SLA的負(fù)載均衡策略研究。另外，負(fù)載均衡策略中缺乏一個(gè)全面的負(fù)載狀態(tài)獲取模型，導(dǎo)致在執(zhí)行虛擬機(jī)遷移時(shí)需要對(duì)所有主機(jī)的負(fù)載進(jìn)行判斷，搜索范圍大、效率低。

針對(duì)上述問題提出了基于SLA的云計(jì)算負(fù)載均衡機(jī)制，設(shè)計(jì)負(fù)載評(píng)價(jià)方法和虛擬機(jī)遷移效益模型，引入基于時(shí)間序列的預(yù)測算法預(yù)測負(fù)載來指導(dǎo)調(diào)度，實(shí)現(xiàn)保證SLA的資源負(fù)載均衡調(diào)度，并通過CloudSim進(jìn)行仿真實(shí)驗(yàn)，驗(yàn)證可行性。

1 關(guān)鍵技術(shù)

1．1 基于SLA的資源負(fù)載獲取

準(zhǔn)確實(shí)時(shí)地掌握負(fù)載的信息是進(jìn)行系統(tǒng)負(fù)載均衡的前提，只有選取合適的指標(biāo)才能正確反映當(dāng)前系統(tǒng)的負(fù)載狀況，進(jìn)而實(shí)現(xiàn)負(fù)載均衡，提高系統(tǒng)性能。服務(wù)平均響應(yīng)時(shí)間是一段時(shí)間內(nèi)所有請(qǐng)求響應(yīng)時(shí)間的平均值，是SLA協(xié)議中經(jīng)常用到的一種簡單的性能觀測和評(píng)估指標(biāo)［10］，服務(wù)提供商只有滿足服務(wù)平均響應(yīng)時(shí)間這一性能指標(biāo)才能獲得應(yīng)有的收益，否則將受到一定的懲罰。

任務(wù)SLA模型定義如下:

式中:Pricek為第k種任務(wù)用戶的SLA在滿足的情況下所支付的單位時(shí)間使用費(fèi)用;rtk為對(duì)于這種類型的任務(wù)用戶所能接受的平均響應(yīng)時(shí)間;Penaltyk為如果該類型任務(wù)的SLA違約，資源提供商需要支付的SLA違約罰金。

在資源提供商方面，一個(gè)云計(jì)算數(shù)據(jù)中心擁有物理主機(jī)N臺(tái)，在第j臺(tái)物理主機(jī)即Hj中的第i個(gè)虛擬機(jī)可表示為VMij，其響應(yīng)時(shí)間為ηi，于是該虛擬機(jī)上第k種任務(wù)類型的響應(yīng)時(shí)間為ηik。則資源負(fù)載狀況可以通過如下指標(biāo)進(jìn)行評(píng)價(jià)。

(1)虛擬機(jī)的效用:

式中，Uik為第k種任務(wù)的虛擬機(jī)VMi效用函數(shù)。若某虛擬機(jī)的響應(yīng)時(shí)間小于該虛擬機(jī)對(duì)應(yīng)任務(wù)類型SLA所規(guī)定的，那么Uik＞0;若該虛擬機(jī)的響應(yīng)時(shí)間大于任務(wù)SLA所規(guī)定的，那么Uik＜0;則可以看出－1＜Uik＜1。

(2)虛擬機(jī)資源利用率:

式中:VUi為某一個(gè)虛擬機(jī)的系統(tǒng)資源利用率;VUcpu為虛擬機(jī)CPU利用率;VUmemory為虛擬機(jī)的內(nèi)存利用率;VUbandwidth為虛擬機(jī)的帶寬利用率;p為其加權(quán)值且p1+p2+p3=1。

(3)主機(jī)利用率。對(duì)于主機(jī)Host層來說，主機(jī)Hj的利用率可以用每臺(tái)主機(jī)上總共運(yùn)行的虛擬機(jī)對(duì)CPU、內(nèi)存、帶寬資源利用率為變量的函數(shù)來表示，即Hj=f(VU1，…，VUi)。

(4)機(jī)器熱態(tài)。定義高負(fù)載閾值為Thresholdhigh，當(dāng)Uik＜0，且VUi＞Thresholdhigh時(shí)，VMi處于熱點(diǎn)狀態(tài)，Uik越接近－1說明負(fù)載越重。對(duì)于物理主機(jī)Hj，當(dāng)Hj＞Thresholdhigh時(shí)，Hj處于熱點(diǎn)狀態(tài)。

(5)機(jī)器冷態(tài)。定義低負(fù)載閾值為Thresholdlow，當(dāng)Uik＞0且VUi＜Thresholdlow時(shí)，VMi處于冷點(diǎn)狀態(tài)，Uik越接近于1說明該虛擬機(jī)負(fù)載越輕。對(duì)于物理主機(jī)Hj，當(dāng)Hj＜Thresholdlow時(shí)，Hj處于冷點(diǎn)狀態(tài)。

1．2 基于時(shí)間序列的負(fù)載預(yù)測

根據(jù)研究顯示，CPU負(fù)載具有很強(qiáng)的自相似性和長相關(guān)性，引入基于時(shí)間序列的負(fù)載預(yù)測機(jī)制，根據(jù)已有的負(fù)載監(jiān)測數(shù)據(jù)預(yù)測未來的主機(jī)負(fù)載來指導(dǎo)虛擬機(jī)均衡調(diào)度的觸發(fā)，從而避免觸發(fā)無謂的遷移。

假設(shè)現(xiàn)有檢測的歷史負(fù)載值L1，L2，…，Lt，這里選擇相對(duì)有效的一段時(shí)間內(nèi)的歷史數(shù)據(jù)，減小過多或較久遠(yuǎn)的歷史數(shù)據(jù)對(duì)結(jié)果的影響，提取負(fù)載值的時(shí)間序列{Lt}建立ARMA模型:

為了減小計(jì)算復(fù)雜度，減少計(jì)算時(shí)間，使用AR模型(autoregressive model)即ARMA模型的自回歸部分，令θi=0則有:

下一時(shí)刻Lt+1預(yù)測值可以表示為:Lt+1=c+，其中φi，…，φt為該模型的參數(shù)，c為常數(shù)(通常情況下會(huì)被忽略)，at為一組獨(dú)立分布的隨機(jī)變量。

1．3 市場驅(qū)動(dòng)的虛擬機(jī)遷移效益分析

設(shè)計(jì)遷移策略應(yīng)保證系統(tǒng)受益大于產(chǎn)生的額外開銷。筆者從市場驅(qū)動(dòng)的角度，在以減少SLA違約的同時(shí)獲得更大的收益來衡量遷移效益。

(1)虛擬機(jī)遷移開銷比:

啟動(dòng)遷移的時(shí)刻，通過虛擬機(jī)的遷移數(shù)據(jù)量Mi和網(wǎng)絡(luò)可用帶寬Bi，可以計(jì)算遷移時(shí)間Δti，根據(jù)文獻(xiàn)［11］的研究，在Δti時(shí)間內(nèi)VMi遷移時(shí)的系統(tǒng)消耗了相當(dāng)于所占有CPU資源的10%。

(2)虛擬機(jī)遷移費(fèi)用(migration cost，MC):

(3)違約嚴(yán)重程度(default degree，DD):

當(dāng)服務(wù)處于SLA違約狀態(tài)，Uik的值越小，則虛擬機(jī)的響應(yīng)速度越慢，違約程度則越嚴(yán)重。

(4)違約金(penalty)。遷移前違約金總和為:

式中:Ni為虛擬機(jī)VMi上等待任務(wù)的總數(shù);etk為任務(wù)的預(yù)計(jì)執(zhí)行時(shí)間。

這里規(guī)定當(dāng)任務(wù)的違約程度為1時(shí)，單個(gè)任務(wù)的違約罰金為其執(zhí)行費(fèi)用。

遷移后的違約金總和為:

(5)遷移收益(revenue)。遷移后收益為:

遷移前預(yù)計(jì)收益為:

(6)遷移估計(jì)益處(profit):

只有當(dāng)遷移估計(jì)益處Profitij大于0時(shí)進(jìn)行虛擬機(jī)遷移，否則不予遷移。所需遷移的虛擬機(jī)按照遷移益處從大到小的順序排列遷移優(yōu)先級(jí)。

1．4 基于概率定位的虛擬機(jī)選擇

若每一個(gè)目的主機(jī)Hj的資源利用率為Ui，那么虛擬機(jī)遷移到該主機(jī)上的概率為:

例如，有一列候選目的主機(jī)集合H=(H1，H2，H3，H4，H5)，其資源利用率分別為u=(0．2，0．4，0．4，0．3，0．1)，則根據(jù)式(14)可得定位概率為P=(0．22，0．17，0．17，0．19，0．25)。

通過一個(gè)random函數(shù)隨機(jī)生成一個(gè)［0，1］之間的小數(shù)，然后根據(jù)該數(shù)最后落在哪個(gè)目標(biāo)節(jié)點(diǎn)的概率空間中，將虛擬機(jī)遷移到這個(gè)目標(biāo)節(jié)點(diǎn)。當(dāng)random=0．1，選中主機(jī)H1;當(dāng)random=0．8，則選中主機(jī)H5。

資源利用率越低，其被選中的概率空間也越大，該物理主機(jī)被選為虛擬機(jī)遷移目的主機(jī)的概率越大。因此，基于概率的隨機(jī)定位思想能在一定程度上解決群聚效應(yīng)問題，由于各個(gè)物理主機(jī)被定位概率的計(jì)算是相互獨(dú)立的，這樣能更好地實(shí)現(xiàn)數(shù)據(jù)中心的負(fù)載均衡。

2 基于SLA的云數(shù)據(jù)中心負(fù)載均衡機(jī)制

基于SLA的云數(shù)據(jù)中心負(fù)載均衡機(jī)制包括負(fù)載均衡器，負(fù)載評(píng)價(jià)，負(fù)載預(yù)測，遷移估計(jì)，執(zhí)行虛擬機(jī)遷移等步驟(如圖1所示)。在負(fù)載均衡調(diào)度觸發(fā)時(shí)，通過收集各節(jié)點(diǎn)負(fù)載信息，基于類型劃分的任務(wù)SLA信息對(duì)資源池中的虛擬機(jī)、物理機(jī)進(jìn)行負(fù)載狀態(tài)獲取，得到需要進(jìn)行負(fù)載均衡的熱點(diǎn)主機(jī)列表;根據(jù)負(fù)載預(yù)測得到候選均衡主機(jī)列表，進(jìn)而得到候選虛擬機(jī)遷移列表;遷移估計(jì)模塊對(duì)候選虛擬機(jī)遷移進(jìn)行遷移效益分析，計(jì)算此刻虛擬機(jī)列表中各類虛擬機(jī)上任務(wù)違反SLA的違約金以及遷移代價(jià)，并按照收益從高到低得出優(yōu)先級(jí)列表，根據(jù)優(yōu)先級(jí)列表的順序進(jìn)行虛擬機(jī)遷移使系統(tǒng)達(dá)到負(fù)載均衡。

圖1 基于SLA的云數(shù)據(jù)中心負(fù)載均衡機(jī)制示意圖

虛擬機(jī)遷移策略包括3個(gè)主要策略:觸發(fā)策略、選擇策略和定位策略。

(1)觸發(fā)策略。通過負(fù)載評(píng)價(jià)對(duì)系統(tǒng)內(nèi)機(jī)器的冷熱態(tài)進(jìn)行標(biāo)識(shí)。利用負(fù)載預(yù)測機(jī)制對(duì)熱點(diǎn)主機(jī)進(jìn)行負(fù)載預(yù)測，預(yù)測計(jì)算未來的n個(gè)負(fù)載值，判斷其中m個(gè)負(fù)載值是否都大于閾值，且下兩個(gè)預(yù)測時(shí)刻的負(fù)載值是否全都大于閾值，若是則觸發(fā)遷移。當(dāng)n=m=1，即為傳統(tǒng)的單閾值觸發(fā)策略。

(2)選擇策略。首先獲取熱點(diǎn)主機(jī)中每一個(gè)虛擬機(jī)上的任務(wù)信息，并進(jìn)行遷移效益分析，得到遷移估計(jì)益處。若遷移估計(jì)益處大于0，則將該虛擬機(jī)放進(jìn)虛擬機(jī)遷移列表，并且按照遷移估計(jì)益處從大到小排列虛擬機(jī)遷移優(yōu)先級(jí)，得到虛擬機(jī)遷移列表。

(3)定位策略。通過選擇策略得到虛擬機(jī)遷移列表之后，就需要考慮將這些需要遷移的虛擬機(jī)遷移到那些合適的物理主機(jī)。將由負(fù)載評(píng)價(jià)所得的所有可用的冷點(diǎn)主機(jī)放入候選目的主機(jī)列表，利用各主機(jī)資源利用率，得到主機(jī)定位概率，通過Random函數(shù)生成隨機(jī)小數(shù)，確定虛擬機(jī)遷移的目的主機(jī)。

3 實(shí)驗(yàn)及結(jié)果分析

由于CloudSim的局限性，筆者實(shí)驗(yàn)采取超過負(fù)載閾值即觸發(fā)遷移的操作。觀察從觸發(fā)遷移之后每隔10 s的罰金與利潤情況。任務(wù)參數(shù)、虛擬機(jī)參數(shù)和物理主機(jī)參數(shù)如表1～表3所示。

表1 任務(wù)參數(shù)列表

表2 虛擬機(jī)參數(shù)列表

表3 主機(jī)參數(shù)列表

該實(shí)驗(yàn)設(shè)置有4種任務(wù)類型組成的等待隊(duì)列，每種任務(wù)類型各10個(gè)，這里任務(wù)類型即為對(duì)應(yīng)虛擬機(jī)類型。第一組任務(wù)需要提供高性能的計(jì)算資源，租金和罰金是最高的;第二組任務(wù)需要提供較高性能的計(jì)算資源，租金和罰金相對(duì)于第一組較低;第三組任務(wù)只需提供一般的計(jì)算資源，租金罰金較第二類低;第四組任務(wù)提供較低性能的計(jì)算資源，租金罰金最低。

試驗(yàn)中設(shè)計(jì)了一種得不償失的情況，任務(wù)組對(duì)應(yīng)的虛擬機(jī)的遷移代價(jià)大，但任務(wù)的違約程度低，等待任務(wù)少并且違約罰金較低，在與文獻(xiàn)［12］的遷移策略相比時(shí)發(fā)現(xiàn)，面對(duì)這種任務(wù)組的情況，筆者算法基于SLA的遷移益處估計(jì)，考慮了遷移組的優(yōu)先級(jí)，使得那些重罰金的違約任務(wù)及時(shí)遷移，而文獻(xiàn)［12］算法則忽略了或沒有優(yōu)先處理某些服務(wù)違約罰金較高但需要被遷移的任務(wù)組，而遷移罰金較低的任務(wù)組得到的收益少于遷移罰金重的任務(wù)所帶來的罰金代價(jià)。在這種情況下沒有有效抑制罰金的快速上升，致使利潤降低。負(fù)載均衡算法下罰金與利潤比較如圖2所示。

4 結(jié)論

云計(jì)算環(huán)境下數(shù)據(jù)中心的大規(guī)模性以及節(jié)點(diǎn)之間可能存在負(fù)載不均等現(xiàn)象，使得云計(jì)算負(fù)載均衡研究受到重視。筆者從市場驅(qū)動(dòng)角度出發(fā)，提出了基于SLA的云數(shù)據(jù)中心負(fù)載均衡機(jī)制，設(shè)計(jì)了針對(duì)SLA的負(fù)載評(píng)價(jià)指標(biāo)，建立虛擬機(jī)遷移效益模型，確定負(fù)載遷移的優(yōu)先級(jí)，以最大化收益為約束均衡調(diào)度實(shí)現(xiàn)系統(tǒng)負(fù)載均衡。通過仿真實(shí)驗(yàn)對(duì)比，證實(shí)了負(fù)載均衡策略能夠較好地保證SLA。

圖2 負(fù)載均衡算法下罰金與利潤比較圖

［1］PATEL P，RANABAHU A，SHETH A．Service level agreement in cloud computing［C］∥Cloud Workshops at OOPSLA．［S．l．］:［s．n．］，2009:1154－1167．

［2］MAURER M，EMEAKAROHA V C，BRANDIC I，et al．Cost－benefit analysis of an SLA mapping approach for defining standardized cloud computing goods［J］．Future Generation Computer Systems，2012，28(1):39－47．

［3］劉萬軍，張孟華，郭文越．基于MPSO算法的云計(jì)算資源調(diào)度策略［J］．計(jì)算機(jī)工程，2011(11):43－48．

［4］BROTOTI M，KOUSIK D，PARAMARTHA D．Load balancing in cloud computing using stochastic hill climbing:a soft computing approach［J］．Procedia Technology，2012(4):783－789．

［5］DOMINIQUE A H．Optimized resource allocation＆task scheduling challenges in cloud computing environments［C］∥2010 International Conference on Cloud and Service Computing．［S．l．］:［s．n．］，2010:7－15．

［6］馮小靖，潘郁．云計(jì)算環(huán)境下的DPSO資源負(fù)載均衡算法［J］．計(jì)算機(jī)工程與應(yīng)用，2013，49(6):105－108．

［7］DHINESH B L D，VENKATAKRISHNA P．Honey bee behavior inspired load balancing of tasks in cloud computing environments［J］．Future Generation Computer Systems，2013，29(13):2292－2303．

［8］LU Y，XIE Q，KLIOT G，et al．Join－idle－queue:a novel load balancing algorithm for dynamically scalable web services［J］．Performance Evaluation，2011，68(11):1056－1071．

［9］ANTON B，ABAWAJY J，BUYYA R．Energy－aware resource allocation heuristics for efficient management of data centers for cloud computing［J］．Future Gener-ation Computer Systems，2012，28(5):755－768．

［10］EMILIANO C，LUCA S．Mechanisms for SLA provisioning in cloud－based service providers［J］．Computer Networks，2013，57(2):795－810．

［11］JIN H，GAO W，WU S，et al．Optimizing the live migration of virtual machine by CPU scheduling［J］．Journal of Network and Computer Applications，2011(7):1088－1096．

［12］MAGULURI S T，SRIKANT R，YING L．Stochastic models of load balancing and scheduling in cloud computing clusters［C］∥INFOCOM，2012 Proceedings IEEE．［S．l．］:［s．n．］，2012:702－710．