朱兵偉 陳世平,2
(上海理工大學(xué)光電信息與計(jì)算機(jī)工程學(xué)院 上海 200093) (上海理工大學(xué)信息化辦公室 上海 200093)
隨著虛擬化技術(shù)[1]和云計(jì)算的快速發(fā)展,大量高科技公司涌入云服務(wù)市場,如谷歌App Engine、亞馬遜EC2、微軟Azure以及蘋果ICloud等。云計(jì)算市場規(guī)模越來越大,為服務(wù)于快速增長的異構(gòu)需求和動態(tài)變化的用戶群體,大量的數(shù)據(jù)中心建立起來。為保證數(shù)據(jù)中心的正常運(yùn)轉(zhuǎn),與其配套的服務(wù)器設(shè)備、電力資源、冷卻設(shè)備的數(shù)量急劇增長,同時也產(chǎn)生巨大的云設(shè)備運(yùn)營支出和能源消耗[2]。因此,迫切需要新技術(shù)來降低高能耗以及提高資源利用率[3]。
每一個數(shù)據(jù)中心都有大量的服務(wù)器,每一臺服務(wù)器需要多個CPU、本地緩存、內(nèi)存、硬盤及其他資源,數(shù)據(jù)中心的管理在于:如何合理地將所有虛擬機(jī)映射到服務(wù)器,將對云資源的使用及能源管理有著重要意義。一方面,在復(fù)雜云系統(tǒng)資源限制的條件下,云服務(wù)商要滿足所有用戶需求就要啟動更多的服務(wù)器,并且按照服務(wù)級別協(xié)議(SLAS)保證服務(wù)質(zhì)量。另一方面,還要對其性能、開支、資源消耗,以及利潤等目標(biāo)進(jìn)行優(yōu)化。生活中資源需求會隨時間變化,比如,一家公司白天需要許多虛擬機(jī),但晚上需求量特別少,這時我們可將閑置服務(wù)器切換進(jìn)入待機(jī)狀態(tài),盡量避免過多服務(wù)器處于“饑餓”狀態(tài)。
與已有的研究不同,本文主要研究針對包簇框架下云資源預(yù)留分配規(guī)劃問題,我們將用戶需求定義為對虛擬機(jī)總需求量。通過在CloudSim仿真平臺上的大規(guī)模云仿真實(shí)驗(yàn)[4],驗(yàn)證了本文提出的方法。
在云虛擬機(jī)調(diào)度算法中,輪回調(diào)度算法(Round robin)[5]思路清晰易于操作,準(zhǔn)確評估了數(shù)據(jù)遷移算法的有效性及有效消除負(fù)載傾斜,但龐大的數(shù)據(jù)遷移造成很大開銷。貪心調(diào)度算法(Greedy algorithm)[6]適用于周期性的負(fù)載模式或者負(fù)載相對穩(wěn)定模式,因此,要考慮服務(wù)器負(fù)載的穩(wěn)定周期,來減少遷移引起的不必要開銷。除了這些經(jīng)典算法外,國內(nèi)外研究人員就云資源合理分配這一問題,提出了很多的分配方案。
文獻(xiàn)[7]提出面向業(yè)務(wù)特征的自適應(yīng)虛擬機(jī)遷移帶寬分配算法,解決負(fù)載均衡中數(shù)據(jù)遷移問題,在控制負(fù)載傾斜的環(huán)境下,對遷移開銷進(jìn)行優(yōu)化。但是服務(wù)質(zhì)量(SLA)方面存在不足之處,一般而言,個人用戶或企業(yè)會根據(jù)SLA協(xié)議要求云服務(wù)商保障服務(wù)質(zhì)量,所以,SLA協(xié)議是云服務(wù)商優(yōu)化資源配置的前提條件。文獻(xiàn)[8]針對虛擬機(jī)調(diào)度均衡問題,提出基于遺傳算法的負(fù)載均衡調(diào)度策略。該方法實(shí)現(xiàn)了最佳的負(fù)載均衡,減少或避免了動態(tài)遷移,從而解決了傳統(tǒng)調(diào)度算法造成的負(fù)載均衡和高遷移成本問題。但是在實(shí)際的云計(jì)算環(huán)境中,虛擬機(jī)可能會有動態(tài)變化,而且隨著虛擬機(jī)數(shù)量的增加,虛擬機(jī)的計(jì)算成本也可能會增加,并且會有一些無法預(yù)測的負(fù)載損耗。因此,需要一種監(jiān)測和分析機(jī)制來更好地解決負(fù)載平衡的問題。文獻(xiàn)[9]提出了基于時間序列工作負(fù)載預(yù)測的遷移策略,并且指出影響遷移時間成本的主要因素有內(nèi)存大小、網(wǎng)絡(luò)帶寬、內(nèi)存占用率等參數(shù),有效地降低虛擬機(jī)遷移引起的額外能耗。但遷移過程中,當(dāng)物理帶寬使用量比較大時可能會導(dǎo)致大量緩存擁塞排隊(duì),并且還會有發(fā)送內(nèi)存與業(yè)務(wù)運(yùn)行搶占帶寬的可能,增加了SLA的違反次數(shù)。文獻(xiàn)[10]采用基于最佳適配遞降算法進(jìn)行分配虛擬機(jī),VM按照當(dāng)前利用率進(jìn)行降序排列,再依次分配到最小能耗的服務(wù)器上。該方法主要利用VM實(shí)時遷移和關(guān)閉空閑節(jié)點(diǎn),穩(wěn)定了資源利用率,VM的重新分配節(jié)約了大量的能耗。其缺點(diǎn)是引起不必要的虛擬機(jī)遷移和增加服務(wù)器開關(guān)機(jī)次數(shù),產(chǎn)生不必要的能耗。文獻(xiàn)[11]通過提高資源利用率來控制云環(huán)境能耗,關(guān)閉閑置服務(wù)器和采用時間序列預(yù)測的方法來預(yù)測資源需求。該方法以資源利用率最大化為目標(biāo),但同時虛擬機(jī)遷移也會產(chǎn)生很高的額外費(fèi)用,而且沒有考慮關(guān)閉閑置的服務(wù)器來節(jié)約成本。
“包”為虛擬機(jī)或其他包的集合(這是個遞歸定義,一個大包可以是許多小包的集合,而這些小包可能是虛擬機(jī)的集合,也可能是更小包的集合)[12]。包所需的內(nèi)存大小,要體現(xiàn)對虛擬機(jī)有靈活性的要求,比如,對每臺虛擬機(jī)的要求,分配VM的方式。該遞歸定義允許用戶以一種層次結(jié)構(gòu)形式組織自己的資源要求。
“簇”為數(shù)據(jù)中心拓?fù)渲蟹?wù)器位置相近或者級別更低的簇的集合。簇所擁有的資源是其組成部分的資源之和。用簇代表每個機(jī)架上的服務(wù)器,而且低級別簇聚合成高級別簇。要注意的是,每一個低級別簇實(shí)際上包含了大量的服務(wù)器,而每一個更高級別簇又包含了相當(dāng)數(shù)量的低級別簇[12]。
包內(nèi)部可能有很多VM,如何體現(xiàn)每一臺VM上的資源有多大,比如內(nèi)存多大。云資源只是分配給了包,如何體現(xiàn)在包內(nèi)每一臺VM獲得的資源大小。單位是包,包可以分配給包,也可以分配給包內(nèi)的VM,具體的VM如何拿到它需要的內(nèi)存。
從圖1可知,用戶的需求可看作所需不同類型資源包(虛擬機(jī))的數(shù)量,虛擬機(jī)與不同類型資源包相互對應(yīng)的關(guān)系,用戶的需求能被資源包內(nèi)的虛擬機(jī)(VM)滿足。同時,不同類型資源的包可根據(jù)自身資源需求在不同的簇(服務(wù)器)上部署和運(yùn)行。
圖1 框架結(jié)構(gòu)圖
每個用戶可指定其包結(jié)構(gòu),或者僅指定最低級別的包,云服務(wù)商以一種樹形結(jié)構(gòu)把它們進(jìn)一步組織成一個多層次的包結(jié)構(gòu)。對于每一個已分配了包的簇,按包層次展開下一層的子包,按簇層次展開下一層的子簇,再把子包分配到相應(yīng)子簇上。繼續(xù)此操作,直至最底層虛擬機(jī)分配到最底層服務(wù)器。
用戶需求是指所需資源包的個數(shù),只要簇能給包提供足夠的計(jì)算資源,比如:CPU、內(nèi)存、緩存、帶寬等,該包就能實(shí)現(xiàn)到該簇的映射。每個包都有一個最大和最小資源需求,簇按照它們最小資源要求進(jìn)行分配,同一組包內(nèi)虛擬機(jī)可以在分配的簇之間進(jìn)行遷移和資源共享。
除了允許面向云服務(wù)系統(tǒng)和提高用戶靈活性的優(yōu)勢外,包簇層次結(jié)構(gòu)另一個主要優(yōu)勢是將一個大型復(fù)雜的資源管理問題分解為一系列的小問題,迅速解決并且可以并行解決。
任意一個簇ρ,該簇?fù)碛蠳個子簇{H1,H2,…,Hn},n為該簇中服務(wù)器的總數(shù),任意一個包P,該包含有M個子包{V1,V2,…,Vm}。每個子包Vj表示對應(yīng)所需資源總量的向量,每個子簇Hi表示對應(yīng)可分配資源總量的向量。
對可用簇Hi資源(如:CPU,內(nèi)存)的需求:capacitycpu(Hi)和capacitymemory(Hi),其中i∈{1,2,…,n},分別代表簇Hi中可進(jìn)行分配CPU數(shù)量和該簇中可用內(nèi)存大小。
對于?包Vj,其中j∈{1,2,…,m},
式中:cij表示某一包所需CPU數(shù)量。
式中:mij表示某一包所需內(nèi)存大小。
需要滿足式(1)、式(2),每個簇Hi使用的資源總量絕對不能超過其資源擁有量,分配過程中,最好不引起遷移,否則增加不必要的費(fèi)用,能保證距離近效率高的優(yōu)點(diǎn)。
(1)
(2)
存在一個數(shù)據(jù)中心,有m臺服務(wù)器,承載n臺虛擬機(jī),要維持其正常運(yùn)營需要龐大的能源和資金,用戶群體的異樣性和時間差異性,我們可以將一定時間內(nèi)處于閑置的服務(wù)器轉(zhuǎn)為待機(jī)狀態(tài),達(dá)到節(jié)能效果。這里須滿足四個基本條件:
(1) 服務(wù)器的剩余資源要大于虛擬機(jī)請求的資源,且分配后服務(wù)器不能負(fù)載。
(2) 正常運(yùn)行服務(wù)器數(shù)量有99%的把握來第一時間滿足用戶需求,99%從概率論角度提出,保證數(shù)據(jù)的科學(xué)性。
(3) 包優(yōu)先放在同一個機(jī)架或者鄰近的服務(wù)器,盡量啟動少的設(shè)備,并且相鄰的機(jī)架越近越好。
(4) 實(shí)現(xiàn)包內(nèi)資源共享,最好在同一個服務(wù)器上或者相鄰機(jī)架上。
這樣可以節(jié)能,也可以保證時間,我們采用實(shí)時測量手段來監(jiān)測每臺服務(wù)器,將監(jiān)測結(jié)果及時反饋給調(diào)度中心,首先對服務(wù)器性能進(jìn)行監(jiān)測,通過二次指數(shù)平滑法預(yù)測出CPU和內(nèi)存資源的利用率,來檢測服務(wù)器是否負(fù)載過重;然后通過中心極限定理預(yù)測出服務(wù)器正常運(yùn)行的數(shù)量。
式中:at,bt為參數(shù)。
最后,得到主機(jī)i的使用情況:
其中,n1、n2分別表示CPU和內(nèi)存利用率的權(quán)重。
由此可以知道主機(jī)是否負(fù)載,滿足條件一。
再計(jì)算條件二:
將所有虛擬機(jī)編號,令:
令X表示這n萬臺虛擬機(jī)中在t時間(1≤t≤T)被申請的數(shù)量,則:
定理(中心極限定理) 設(shè)隨機(jī)變量Xn~B(n,p),n=1,2,…,其中常數(shù)p∈(0,1),q=1-q。
定理表明,若X~B(n,p),則當(dāng)n充分大事有近似計(jì)算公式:
(3)
根據(jù)上述的近似計(jì)算式(3)可得:
(4)
中心極限定理又稱大數(shù)定理,主要用于大量數(shù)據(jù)的計(jì)算,體現(xiàn)數(shù)據(jù)的科學(xué)性、準(zhǔn)確性。根據(jù)式(4)可知,只需知道虛擬機(jī)數(shù)量n,就能計(jì)算出主機(jī)的數(shù)量k,滿足條件二,然后再利用0-1背包算法對虛擬機(jī)分配,同時根據(jù)能耗公式進(jìn)行比較。
云資源的分配實(shí)質(zhì)就是實(shí)現(xiàn)包到簇的映射,最低成本條件下獲得最大的效益是我們的優(yōu)化目標(biāo),本文研究的云資源整數(shù)規(guī)劃可以看成多重0-1背包問題[13]。我們將每一個簇看成一個包,每一個包看成一個物品。首先,將最上層大型包映射給最上層的大型簇,每個簇應(yīng)有足夠的資源來支持映射的包的總需求。然后,針對每個簇及該簇所支持的資源包,將其下一級別的包映射到下一級別的簇,遞歸重復(fù)該過程,直到所有虛擬機(jī)被映射到服務(wù)器[14]。設(shè)定m個簇,n個包,m、n都為正整數(shù),包j在簇i上運(yùn)營的能耗為Cij,每個包所需總資源為aij,簇i所擁有的總資源為bi,設(shè)Xij∈{0,1},表示簇i分配給包j的決策變量,則云資源整數(shù)規(guī)劃問題為
(5)
(6)
(7)
xij∈{0,1}i=1,2,…,m,j=1,2,…,n
(8)
我們根據(jù)式(6)-式(8)對式(5)進(jìn)行拉格朗日松弛,設(shè)乘子向量u∈Rn,則松馳問題為:
(9)
xij∈{0,1}i=1,2,…,m,j=1,2,…,n
xij∈{0,1}i=1,2,…,m,j=1,2,…,n
其中zi(u)是如下的最優(yōu)值:
xij∈{0,1}j=1,2,…,n
云計(jì)算環(huán)境下CloudSim是一個具有現(xiàn)代化科學(xué)化的框架模擬仿真平臺,它不僅支持應(yīng)用管理建模,而且支持按需定義主機(jī)、虛擬機(jī)數(shù)量,還支持能耗建模為核心的框架,將任務(wù)分配到指定的虛擬機(jī)上工作,完成對不同算法的模擬測試。
利用擴(kuò)展仿真模塊來支持包簇系統(tǒng)構(gòu)架,包簇遞歸的特定0-1背包算法在服務(wù)器之間合理分配虛擬機(jī)。實(shí)驗(yàn)運(yùn)行硬件環(huán)境:一臺PC機(jī),Linux系統(tǒng),CPU 主頻2.4 GHz,內(nèi)存8 GB。對本文提出的方法進(jìn)行仿真實(shí)驗(yàn),前提設(shè)定主機(jī)和虛擬機(jī)的硬件配置。
4.1.1 主機(jī)配置
根據(jù)市場的主機(jī)配置,模擬8臺服務(wù)器,配置如表1所示,其中CPU單位是MIPS,即衡量CPU速度的一個重要指標(biāo)。
表1 主機(jī)配置
4.1.2 虛擬機(jī)配置
由于用戶群體的需求不同,產(chǎn)生多樣性的虛擬機(jī),虛擬機(jī)規(guī)格如表2所示。
表2 虛擬機(jī)配置
4.2.1 能耗計(jì)算
本文提出的方法即服務(wù)器預(yù)留算法RA(Reserved algorithm),要求云服務(wù)提供者任意時間段都保留固定數(shù)目的服務(wù)器正常工作,來應(yīng)對用請求包數(shù)量的非線性變化,同時當(dāng)服務(wù)器閑置時自動切換待機(jī)狀態(tài),再根據(jù)0-1背包算法求出最佳分配值,我們和下面兩個算法進(jìn)行比較。
最佳適配遞降算法BADA(Best adaptive descending algorithm),即VM按照當(dāng)前利用率進(jìn)行降序排列,將利用率低的虛擬機(jī),依次分配到最小能源消耗的服務(wù)器上。該方法優(yōu)勢主要利用VM實(shí)時遷移和關(guān)閉空閑節(jié)點(diǎn),穩(wěn)定了資源利用率,VM的重新分配節(jié)約了大量的能耗。
無預(yù)留算法UA(Unreserved algorithm),即當(dāng)任意需求包到來時,立即尋找合適的服務(wù)器,來滿足該用戶的需求;當(dāng)某一臺服務(wù)器處于閑置時,立刻將其關(guān)閉,頻繁關(guān)閉啟動服務(wù)器的同時消耗大量的能源,還會延長用戶等待時間。
將包按照不同的參數(shù)進(jìn)行部署,這些參數(shù)包括相同資源、距離、內(nèi)存、CPU等,簇資源根據(jù)當(dāng)前需要進(jìn)行分配,記錄三種算法的能耗,CPU平均利用率,內(nèi)存平均利用率,根據(jù)本文提出的能耗模型來對能耗進(jìn)行分析,實(shí)驗(yàn)結(jié)果如圖2所示。
圖2 能耗比較(周期為1小時)
實(shí)驗(yàn)表明,在相同條件下,隨著運(yùn)行時間的延長,三種算法的能耗有明顯變化,但UA算法的能耗始終高于RA算法,說明服務(wù)器預(yù)留的可行性,確實(shí)降低了能耗。從曲線統(tǒng)計(jì)結(jié)果可知,UA算法在實(shí)驗(yàn)中需要消耗26.82 kW的能源,而RA只消耗了16.22 kW的能源,節(jié)省能源10.6 kW。BADA算法在試驗(yàn)中消耗了19.99 kW的能源,RA算法比BADA算法節(jié)省能源3.77 kW。
4.2.2 CPU和內(nèi)存平均利用率
我們在模擬數(shù)據(jù)中心CloudSim實(shí)驗(yàn)平臺上選定50、100到500臺虛擬機(jī)進(jìn)行資源分配,這些虛擬機(jī)在相同的環(huán)境分配相同的任務(wù),規(guī)定的時間內(nèi),將運(yùn)行產(chǎn)生的CPU利用率和內(nèi)存利用率數(shù)據(jù)記錄,在云實(shí)驗(yàn)平臺達(dá)到平衡時對不同算法進(jìn)行評估。如圖3、圖4所示。
圖3 CPU利用率
圖4 內(nèi)存利用率
從圖3、圖4看出,隨著包數(shù)量的遞增三種算法資源使用率沒有明顯的關(guān)聯(lián),但是,RA算法的CPU利用率和內(nèi)存利用率較高且穩(wěn)定,RA算法與BADA算法相比,CPU利用率提高了17.6%,內(nèi)存提高了13.9%,RA算法比UA算法優(yōu)越性更為明顯。雖然BADA算法資源使用量比UA算法有明顯優(yōu)勢,但是不穩(wěn)定,而UA算法整體資源利用率更偏低。縱向比較,在相同包數(shù)量的條件下,RA算法的資源使用率不一定比BADA算法高,但是比UA算法高,說明RA算法確實(shí)是提高了虛擬機(jī)資源利用率,起到了節(jié)約能源的作用。
對任何數(shù)據(jù)中心而言,不僅要提供購買、安置設(shè)備的場地和費(fèi)用,還要控制運(yùn)營、維護(hù)費(fèi)用,降低服務(wù)器的能耗可有效控制成本費(fèi)用。本文在分析了服務(wù)器高能耗問題后,提出了一種包簇框架下云資源預(yù)留的方法來節(jié)約能源,并使用0-1背包算法來調(diào)整包簇分配方案。在較為準(zhǔn)確的服務(wù)器預(yù)留和較為合理的包簇映射的基礎(chǔ)上,有效減少了服務(wù)器關(guān)機(jī)的次數(shù),也有效降低了能源消耗,對云計(jì)算有一定的現(xiàn)實(shí)意義。
能耗僅僅是云計(jì)算資源優(yōu)化目標(biāo)之一,還包括各種性能目標(biāo)、成本目標(biāo)及利潤目標(biāo)等。同時在后續(xù)研究中還可以考慮硬盤容量、網(wǎng)絡(luò)帶寬等更多類型的資源限制條件,使研究更接近復(fù)雜的實(shí)際環(huán)境。