包簇框架云資源分配規劃

朱兵偉 陳世平，2

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

0 引 言

隨著虛擬化技術[1]和云計算的快速發展，大量高科技公司涌入云服務市場，如谷歌App Engine、亞馬遜EC2、微軟Azure以及蘋果ICloud等。云計算市場規模越來越大，為服務于快速增長的異構需求和動態變化的用戶群體，大量的數據中心建立起來。為保證數據中心的正常運轉，與其配套的服務器設備、電力資源、冷卻設備的數量急劇增長，同時也產生巨大的云設備運營支出和能源消耗[2]。因此，迫切需要新技術來降低高能耗以及提高資源利用率[3]。

每一個數據中心都有大量的服務器，每一臺服務器需要多個CPU、本地緩存、內存、硬盤及其他資源，數據中心的管理在于：如何合理地將所有虛擬機映射到服務器，將對云資源的使用及能源管理有著重要意義。一方面，在復雜云系統資源限制的條件下，云服務商要滿足所有用戶需求就要啟動更多的服務器，并且按照服務級別協議(SLAS)保證服務質量。另一方面，還要對其性能、開支、資源消耗，以及利潤等目標進行優化。生活中資源需求會隨時間變化，比如，一家公司白天需要許多虛擬機，但晚上需求量特別少，這時我們可將閑置服務器切換進入待機狀態，盡量避免過多服務器處于“饑餓”狀態。

與已有的研究不同，本文主要研究針對包簇框架下云資源預留分配規劃問題，我們將用戶需求定義為對虛擬機總需求量。通過在CloudSim仿真平臺上的大規模云仿真實驗[4]，驗證了本文提出的方法。

1 相關工作

在云虛擬機調度算法中，輪回調度算法(Round robin)[5]思路清晰易于操作，準確評估了數據遷移算法的有效性及有效消除負載傾斜,但龐大的數據遷移造成很大開銷。貪心調度算法(Greedy algorithm)[6]適用于周期性的負載模式或者負載相對穩定模式，因此，要考慮服務器負載的穩定周期，來減少遷移引起的不必要開銷。除了這些經典算法外，國內外研究人員就云資源合理分配這一問題，提出了很多的分配方案。

文獻[7]提出面向業務特征的自適應虛擬機遷移帶寬分配算法，解決負載均衡中數據遷移問題，在控制負載傾斜的環境下，對遷移開銷進行優化。但是服務質量(SLA)方面存在不足之處，一般而言，個人用戶或企業會根據SLA協議要求云服務商保障服務質量，所以，SLA協議是云服務商優化資源配置的前提條件。文獻[8]針對虛擬機調度均衡問題，提出基于遺傳算法的負載均衡調度策略。該方法實現了最佳的負載均衡，減少或避免了動態遷移，從而解決了傳統調度算法造成的負載均衡和高遷移成本問題。但是在實際的云計算環境中，虛擬機可能會有動態變化，而且隨著虛擬機數量的增加，虛擬機的計算成本也可能會增加，并且會有一些無法預測的負載損耗。因此，需要一種監測和分析機制來更好地解決負載平衡的問題。文獻[9]提出了基于時間序列工作負載預測的遷移策略，并且指出影響遷移時間成本的主要因素有內存大小、網絡帶寬、內存占用率等參數，有效地降低虛擬機遷移引起的額外能耗。但遷移過程中，當物理帶寬使用量比較大時可能會導致大量緩存擁塞排隊，并且還會有發送內存與業務運行搶占帶寬的可能，增加了SLA的違反次數。文獻[10]采用基于最佳適配遞降算法進行分配虛擬機，VM按照當前利用率進行降序排列,再依次分配到最小能耗的服務器上。該方法主要利用VM實時遷移和關閉空閑節點，穩定了資源利用率，VM的重新分配節約了大量的能耗。其缺點是引起不必要的虛擬機遷移和增加服務器開關機次數，產生不必要的能耗。文獻[11]通過提高資源利用率來控制云環境能耗，關閉閑置服務器和采用時間序列預測的方法來預測資源需求。該方法以資源利用率最大化為目標，但同時虛擬機遷移也會產生很高的額外費用，而且沒有考慮關閉閑置的服務器來節約成本。

2 包簇系統架構

2.1 包與簇

“包”為虛擬機或其他包的集合(這是個遞歸定義，一個大包可以是許多小包的集合，而這些小包可能是虛擬機的集合，也可能是更小包的集合)[12]。包所需的內存大小，要體現對虛擬機有靈活性的要求，比如，對每臺虛擬機的要求,分配VM的方式。該遞歸定義允許用戶以一種層次結構形式組織自己的資源要求。

“簇”為數據中心拓撲中服務器位置相近或者級別更低的簇的集合。簇所擁有的資源是其組成部分的資源之和。用簇代表每個機架上的服務器，而且低級別簇聚合成高級別簇。要注意的是，每一個低級別簇實際上包含了大量的服務器，而每一個更高級別簇又包含了相當數量的低級別簇[12]。

包內部可能有很多VM，如何體現每一臺VM上的資源有多大，比如內存多大。云資源只是分配給了包，如何體現在包內每一臺VM獲得的資源大小。單位是包，包可以分配給包，也可以分配給包內的VM，具體的VM如何拿到它需要的內存。

2.2 包簇框架

從圖1可知,用戶的需求可看作所需不同類型資源包(虛擬機)的數量，虛擬機與不同類型資源包相互對應的關系,用戶的需求能被資源包內的虛擬機(VM)滿足。同時，不同類型資源的包可根據自身資源需求在不同的簇(服務器)上部署和運行。

圖1 框架結構圖

每個用戶可指定其包結構，或者僅指定最低級別的包，云服務商以一種樹形結構把它們進一步組織成一個多層次的包結構。對于每一個已分配了包的簇，按包層次展開下一層的子包，按簇層次展開下一層的子簇，再把子包分配到相應子簇上。繼續此操作，直至最底層虛擬機分配到最底層服務器。

用戶需求是指所需資源包的個數，只要簇能給包提供足夠的計算資源，比如：CPU、內存、緩存、帶寬等，該包就能實現到該簇的映射。每個包都有一個最大和最小資源需求，簇按照它們最小資源要求進行分配，同一組包內虛擬機可以在分配的簇之間進行遷移和資源共享。

除了允許面向云服務系統和提高用戶靈活性的優勢外，包簇層次結構另一個主要優勢是將一個大型復雜的資源管理問題分解為一系列的小問題，迅速解決并且可以并行解決。

2.3 包簇分配

任意一個簇ρ，該簇擁有N個子簇{H1,H2,…,Hn}，n為該簇中服務器的總數，任意一個包P，該包含有M個子包{V1,V2,…,Vm}。每個子包Vj表示對應所需資源總量的向量，每個子簇Hi表示對應可分配資源總量的向量。

對可用簇Hi資源(如：CPU,內存)的需求：capacitycpu(Hi)和capacitymemory(Hi)，其中i∈{1,2,…,n}，分別代表簇Hi中可進行分配CPU數量和該簇中可用內存大小。

對于?包Vj，其中j∈{1,2,…,m}，

式中：cij表示某一包所需CPU數量。

式中：mij表示某一包所需內存大小。

需要滿足式(1)、式(2)，每個簇Hi使用的資源總量絕對不能超過其資源擁有量，分配過程中，最好不引起遷移，否則增加不必要的費用，能保證距離近效率高的優點。

(1)

(2)

3 分配規劃方法

3.1 服務器預留

存在一個數據中心，有m臺服務器，承載n臺虛擬機，要維持其正常運營需要龐大的能源和資金，用戶群體的異樣性和時間差異性，我們可以將一定時間內處于閑置的服務器轉為待機狀態，達到節能效果。這里須滿足四個基本條件：

(1) 服務器的剩余資源要大于虛擬機請求的資源，且分配后服務器不能負載。

(2) 正常運行服務器數量有99%的把握來第一時間滿足用戶需求，99%從概率論角度提出，保證數據的科學性。

(3) 包優先放在同一個機架或者鄰近的服務器，盡量啟動少的設備，并且相鄰的機架越近越好。

(4) 實現包內資源共享，最好在同一個服務器上或者相鄰機架上。

這樣可以節能，也可以保證時間，我們采用實時測量手段來監測每臺服務器，將監測結果及時反饋給調度中心，首先對服務器性能進行監測，通過二次指數平滑法預測出CPU和內存資源的利用率，來檢測服務器是否負載過重；然后通過中心極限定理預測出服務器正常運行的數量。

式中：at，bt為參數。

最后，得到主機i的使用情況：

其中，n1、n2分別表示CPU和內存利用率的權重。

由此可以知道主機是否負載，滿足條件一。

再計算條件二：

將所有虛擬機編號，令：

令X表示這n萬臺虛擬機中在t時間(1≤t≤T)被申請的數量，則：

定理(中心極限定理) 設隨機變量Xn～B(n,p),n=1,2,…,其中常數p∈(0,1),q=1-q。

定理表明，若X～B(n，p)，則當n充分大事有近似計算公式：

(3)

根據上述的近似計算式(3)可得:

(4)

中心極限定理又稱大數定理，主要用于大量數據的計算，體現數據的科學性、準確性。根據式(4)可知，只需知道虛擬機數量n，就能計算出主機的數量k，滿足條件二，然后再利用0-1背包算法對虛擬機分配，同時根據能耗公式進行比較。

3.2 包簇0-1背包算法

云資源的分配實質就是實現包到簇的映射，最低成本條件下獲得最大的效益是我們的優化目標，本文研究的云資源整數規劃可以看成多重0-1背包問題[13]。我們將每一個簇看成一個包，每一個包看成一個物品。首先，將最上層大型包映射給最上層的大型簇，每個簇應有足夠的資源來支持映射的包的總需求。然后，針對每個簇及該簇所支持的資源包，將其下一級別的包映射到下一級別的簇，遞歸重復該過程，直到所有虛擬機被映射到服務器[14]。設定m個簇,n個包,m、n都為正整數，包j在簇i上運營的能耗為Cij,每個包所需總資源為aij,簇i所擁有的總資源為bi，設Xij∈{0,1}，表示簇i分配給包j的決策變量，則云資源整數規劃問題為

(5)

(6)

(7)

xij∈{0,1}i=1,2,…,m,j=1,2,…,n

(8)

我們根據式(6)-式(8)對式(5)進行拉格朗日松弛，設乘子向量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)是如下的最優值：

xij∈{0,1}j=1,2,…,n

4 仿真實驗

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

4.1 環境搭建

利用擴展仿真模塊來支持包簇系統構架，包簇遞歸的特定0-1背包算法在服務器之間合理分配虛擬機。實驗運行硬件環境：一臺PC機，Linux系統，CPU 主頻2.4 GHz，內存8 GB。對本文提出的方法進行仿真實驗，前提設定主機和虛擬機的硬件配置。

4.1.1 主機配置

根據市場的主機配置，模擬8臺服務器，配置如表1所示，其中CPU單位是MIPS，即衡量CPU速度的一個重要指標。

表1 主機配置

4.1.2 虛擬機配置

由于用戶群體的需求不同，產生多樣性的虛擬機，虛擬機規格如表2所示。

表2 虛擬機配置

4.2 實驗分析

4.2.1 能耗計算

本文提出的方法即服務器預留算法RA(Reserved algorithm)，要求云服務提供者任意時間段都保留固定數目的服務器正常工作，來應對用請求包數量的非線性變化，同時當服務器閑置時自動切換待機狀態，再根據0-1背包算法求出最佳分配值，我們和下面兩個算法進行比較。

最佳適配遞降算法BADA(Best adaptive descending algorithm)，即VM按照當前利用率進行降序排列，將利用率低的虛擬機，依次分配到最小能源消耗的服務器上。該方法優勢主要利用VM實時遷移和關閉空閑節點，穩定了資源利用率，VM的重新分配節約了大量的能耗。

無預留算法UA(Unreserved algorithm)，即當任意需求包到來時，立即尋找合適的服務器，來滿足該用戶的需求；當某一臺服務器處于閑置時，立刻將其關閉，頻繁關閉啟動服務器的同時消耗大量的能源，還會延長用戶等待時間。

將包按照不同的參數進行部署，這些參數包括相同資源、距離、內存、CPU等，簇資源根據當前需要進行分配，記錄三種算法的能耗，CPU平均利用率，內存平均利用率，根據本文提出的能耗模型來對能耗進行分析，實驗結果如圖2所示。

圖2 能耗比較(周期為1小時)

實驗表明，在相同條件下，隨著運行時間的延長，三種算法的能耗有明顯變化，但UA算法的能耗始終高于RA算法，說明服務器預留的可行性，確實降低了能耗。從曲線統計結果可知，UA算法在實驗中需要消耗26.82 kW的能源，而RA只消耗了16.22 kW的能源，節省能源10.6 kW。BADA算法在試驗中消耗了19.99 kW的能源，RA算法比BADA算法節省能源3.77 kW。

4.2.2 CPU和內存平均利用率

我們在模擬數據中心CloudSim實驗平臺上選定50、100到500臺虛擬機進行資源分配，這些虛擬機在相同的環境分配相同的任務，規定的時間內，將運行產生的CPU利用率和內存利用率數據記錄，在云實驗平臺達到平衡時對不同算法進行評估。如圖3、圖4所示。

圖3 CPU利用率

圖4 內存利用率

從圖3、圖4看出，隨著包數量的遞增三種算法資源使用率沒有明顯的關聯，但是，RA算法的CPU利用率和內存利用率較高且穩定，RA算法與BADA算法相比，CPU利用率提高了17.6%，內存提高了13.9%，RA算法比UA算法優越性更為明顯。雖然BADA算法資源使用量比UA算法有明顯優勢，但是不穩定，而UA算法整體資源利用率更偏低。縱向比較，在相同包數量的條件下，RA算法的資源使用率不一定比BADA算法高，但是比UA算法高，說明RA算法確實是提高了虛擬機資源利用率，起到了節約能源的作用。

5 結 語

對任何數據中心而言，不僅要提供購買、安置設備的場地和費用，還要控制運營、維護費用，降低服務器的能耗可有效控制成本費用。本文在分析了服務器高能耗問題后，提出了一種包簇框架下云資源預留的方法來節約能源，并使用0-1背包算法來調整包簇分配方案。在較為準確的服務器預留和較為合理的包簇映射的基礎上，有效減少了服務器關機的次數，也有效降低了能源消耗，對云計算有一定的現實意義。

能耗僅僅是云計算資源優化目標之一，還包括各種性能目標、成本目標及利潤目標等。同時在后續研究中還可以考慮硬盤容量、網絡帶寬等更多類型的資源限制條件，使研究更接近復雜的實際環境。