基于SLA的云數(shù)據(jù)中心負(fù)載均衡理論研究

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

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

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

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

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

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

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

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

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

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

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

(1)虛擬機的效用:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(2)虛擬機遷移費用(migration cost，MC):

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

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

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

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

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

遷移后的違約金總和為:

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

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

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

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

1．4 基于概率定位的虛擬機選擇

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

例如，有一列候選目的主機集合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)。

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

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

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

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

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

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

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

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

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

3 實驗及結(jié)果分析

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

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

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

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

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

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

4 結(jié)論

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