包簇框架云資源分配規(guī)劃

朱兵偉 陳世平，2

(上海理工大學(xué)光電信息與計(jì)算機(jī)工程學(xué)院 上海 200093) (上海理工大學(xué)信息化辦公室 上海 200093)

0 引 言

隨著虛擬化技術(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)證了本文提出的方法。

1 相關(guā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é)約成本。

2 包簇系統(tǒng)架構(gòu)

2.1 包與簇

“包”為虛擬機(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)存。

2.2 包簇框架

從圖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ù)雜的資源管理問題分解為一系列的小問題，迅速解決并且可以并行解決。

2.3 包簇分配

任意一個簇ρ，該簇?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)

3 分配規(guī)劃方法

3.1 服務(wù)器預(yù)留

存在一個數(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)行比較。

3.2 包簇0-1背包算法

云資源的分配實(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

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

云計(jì)算環(huán)境下CloudSim是一個具有現(xiàn)代化科學(xué)化的框架模擬仿真平臺，它不僅支持應(yīng)用管理建模，而且支持按需定義主機(jī)、虛擬機(jī)數(shù)量，還支持能耗建模為核心的框架，將任務(wù)分配到指定的虛擬機(jī)上工作，完成對不同算法的模擬測試。

4.1 環(huán)境搭建

利用擴(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 實(shí)驗(yàn)分析

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é)約能源的作用。

5 結(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)境。