陸 樂 陳世平,2

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

0 引 言

云計(jì)算技術(shù)剛出現(xiàn)時(shí)，其主要方向是如何使其成為高性能計(jì)算的巨大數(shù)據(jù)中心，并通過按需使用來使得云服務(wù)商獲得報(bào)酬而從中獲利。然而，計(jì)算能力的日益普及也帶來了問題，特別是能源效率問題。

在為數(shù)據(jù)的處理、存儲(chǔ)和通信上，數(shù)據(jù)中心消耗了不可估量的能量，而消耗的能源對二氧化碳的消散具有巨大的影響，增加了溫室效應(yīng)所形成的碳排放對生物和環(huán)境造成破壞性影響。據(jù)估計(jì)，世界總能源的約10%被互聯(lián)網(wǎng)消耗。數(shù)據(jù)中心的能源成本每五年翻一番。2011年，數(shù)據(jù)中心的能源消耗量約為10 000萬千瓦，已造成40 568 000噸的二氧化碳排放。另根據(jù)美國自然資源保護(hù)委員會(huì)(NRDC)的數(shù)據(jù)，到2020年將達(dá)到1 390億千瓦時(shí)[1]。

由此可知，在云計(jì)算中能耗問題是一個(gè)十分重要的研究方向,而對于能耗的優(yōu)化，又有著不同的方向，例如計(jì)算機(jī)硬件的能源優(yōu)化、虛擬化技術(shù)的提升、虛擬機(jī)放置策略以及云計(jì)算任務(wù)分配優(yōu)化等。其中，虛擬機(jī)放置策略是非常重要的一個(gè)研究方向之一。現(xiàn)有的研究已經(jīng)提出了一些十分有效的算法來實(shí)現(xiàn)虛擬機(jī)放置策略，用以提升服務(wù)器的使用率，從而使云計(jì)算更環(huán)保高效。

文獻(xiàn)[2]中提出了降低云計(jì)算基礎(chǔ)設(shè)施能耗的研究，該技術(shù)允許最大限度地減少物理服務(wù)器的數(shù)量，并允許虛擬機(jī)遷移到有限數(shù)量的服務(wù)器上，以便讓集中式物理服務(wù)器利用最大資源，將其他服務(wù)器設(shè)置為低功耗模式。然而該算法需要依靠許多參數(shù)例如CPU、內(nèi)存和網(wǎng)絡(luò)帶寬等來判斷服務(wù)器過載或負(fù)載的時(shí)間。

此外，一般用于能耗優(yōu)化算法的有能耗感知最佳適應(yīng)遞減算法PABFD(Power Aware Best Fit Decreasing)[3]。PABFD算法的思想是按照當(dāng)前CPU利用率的降序?qū)λ刑摂M機(jī)進(jìn)行排序，然后將新虛擬機(jī)分配給物理機(jī)，從而使得物理機(jī)的能耗最小化。

啟發(fā)式算法也常常被用于解決此類問題。文獻(xiàn)[4]提出了一種適用于虛擬機(jī)放置策略的改進(jìn)遺傳算法。文獻(xiàn)[5]使用模擬退火算法，文獻(xiàn)[6]使用粒子群算法進(jìn)行節(jié)能的虛擬機(jī)放置。

除此之外，還有通過多目標(biāo)的虛擬機(jī)放置策略來進(jìn)行能耗優(yōu)化。文獻(xiàn)[7]通過使用粒子群算法，使得不同資源得到有效利用，從而實(shí)現(xiàn)了能耗最小化。在文獻(xiàn)[8-9]中，通過使用遺傳算法來解決多目標(biāo)虛擬機(jī)放置，盡可能減少了運(yùn)行物理機(jī)的數(shù)量以及通信流量，同時(shí)最大化利用了數(shù)據(jù)中心內(nèi)同時(shí)使用的不同資源。文獻(xiàn)[10]同樣使用了遺傳算法，通過最大限度地減少運(yùn)行物理機(jī)數(shù)量并最大化資源使用效率來降低功耗。此外，文獻(xiàn)[11-12]中，還使用蟻群優(yōu)化算法來最小化能耗、減少額外的資源浪費(fèi)。文獻(xiàn)[13]通過蟻群算法重新放置虛擬機(jī)，以減少資源的能耗和負(fù)載平衡。在文獻(xiàn)[14]中，通過使用生物地理優(yōu)化算法BBO(Biogeography-Based Optimization)來同時(shí)降低功耗、減少資源浪費(fèi)、提升服務(wù)器均衡性，并減少了虛擬機(jī)間流量、存儲(chǔ)流量和遷移時(shí)間。

以上的研究方案均有以下的問題：其一是虛擬機(jī)與物理機(jī)的映射層次過于扁平，所有的映射關(guān)系都是在單個(gè)虛擬機(jī)與單個(gè)物理機(jī)之間進(jìn)行，不但造成分配時(shí)間過長，而且一旦發(fā)生資源的變化，所有的映射關(guān)系都會(huì)重新分配。其二是能耗管理的靈活性不高，所有的能耗計(jì)算都是在物理機(jī)的基礎(chǔ)上計(jì)算，沒有更加高層次的精細(xì)化能耗管理方案，對于減少物理機(jī)集群節(jié)點(diǎn)的計(jì)算也不夠清晰。

基于以上的文獻(xiàn)總結(jié)，本文基于文獻(xiàn)[15]提出了一種新的云計(jì)算虛擬機(jī)放置策略——即包簇映射框架。在這個(gè)框架的基礎(chǔ)上，建立一個(gè)基于CPU使用率的能耗模型，并以最小化能耗為目標(biāo)，通過不同的約束條件，使用改進(jìn)的匈牙利算法進(jìn)行虛擬機(jī)和物理機(jī)的高效分配，盡可能地提升分配速度并有效降低能耗，以滿足未來綠色云計(jì)算的趨勢。

1 問題描述

1.1 包簇概念

在包簇映射框架中，包(Package)和簇(Cluster)是兩個(gè)重要的概念，分別是對應(yīng)虛擬機(jī)和物理機(jī)多級層次的抽象定義。在這里，把一個(gè)資源共享的虛擬機(jī)群組稱之為包，包的需求是需要根據(jù)云計(jì)算用戶的需求所定制的。同時(shí)，組成包的元素不僅僅是虛擬機(jī)，也可以是包，也即多個(gè)低級別的包可以被組成一個(gè)高級別的包。通過這樣的構(gòu)建方式，可以由虛擬機(jī)、低級別包和高級別包組成一個(gè)具有清晰組織層次的需求結(jié)構(gòu)。對簇來說也是一樣的定義，物理機(jī)組成低級別簇，低級別簇又可以組成高級別的簇，從而同樣組成一個(gè)多級別的層次結(jié)構(gòu)。由此，虛擬機(jī)放置策略從原來的虛擬機(jī)與物理機(jī)之間扁平的映射關(guān)系轉(zhuǎn)換為包與簇之間的映射關(guān)系。這樣的好處就在于，把虛擬機(jī)與物理機(jī)之間的映射問題進(jìn)一步降解規(guī)模，提高了虛擬機(jī)的分配效率以及資源共享，更易于實(shí)現(xiàn)對虛擬機(jī)和物理機(jī)的精細(xì)化管理。

1.2 包簇模型

有了以上的概述，就可以對包簇框架進(jìn)行進(jìn)一步定義。假設(shè)在包的層次結(jié)構(gòu)中有一任意包γ，在包γ下可能存在M個(gè)虛擬機(jī)或子包v，在這里虛擬機(jī)或子包的數(shù)量限制為1≤v≤M。在包簇框架分配時(shí)，要將同級別的包γ分配給同級別的簇ρ，假設(shè)簇ρ下有M個(gè)服務(wù)器或子簇p，1≤p≤N。本文需要解決的是：在最小化能耗的前提下來將M個(gè)子包分配到N個(gè)子簇上，并且保證要使子包的子包(或虛擬機(jī))映射到子簇的子簇(或物理機(jī))上。

可以用一個(gè)資源分配矩陣表示包簇映射的框架關(guān)系：

(1)

式中：xv,p[t]代表在任意時(shí)間t中，子包v是否分配給子簇p。xv,p[t]=[1|0]也即xv,p[t]的取值只有0或1，當(dāng)子包v分配給子簇p，則xv,p[t]=1，否則xv,p[t]=0。

在這里同時(shí)要求：

(2)

式(2)代表了在任意時(shí)間t內(nèi)，每一個(gè)子包v都必須且只能分配一個(gè)子簇p上，但是一個(gè)子簇上可以承載多個(gè)子包，這是為了保證所有的需求包都可以獲取對應(yīng)的資源。

此外，假設(shè)i代表一種資源，存在J種資源。這個(gè)資源代表了每一個(gè)子包所需的資源量，每一項(xiàng)代表一個(gè)類型，相應(yīng)的子簇也同樣如此。

有了包簇映射的關(guān)系，還需要對其給予一些約束，即任意的子簇可用資源總量必須大于該子簇上所分配到的子包的需求總量：

(3)

式中:Rv,i[t]表示每一個(gè)子包v在時(shí)間t對資源i的需求總量。Ap,i[t]則表示每一個(gè)子簇p在時(shí)間t對資源i的可用總量，其中i=1,2,…,J。

1.3 能耗模型

服務(wù)器的能耗占數(shù)據(jù)中心的大部分總能耗，因此，本文的目標(biāo)是最大限度地減少數(shù)據(jù)中心內(nèi)所有物理機(jī)的總功耗。而物理機(jī)中的各個(gè)部分都會(huì)消耗功耗，如內(nèi)存、網(wǎng)絡(luò)接口、磁盤存儲(chǔ)器、CPU、電源等，但能耗與CPU利用率之間存在線性關(guān)系[16-17]。所以可得：

Pph=k·Pmax+(1-k)·Pmax·uph,cpu

(4)

式中：Pph代表了物理機(jī)ph當(dāng)前功率，k是空閑物理機(jī)運(yùn)行所損耗功率的參數(shù)，Pmax則代表當(dāng)前物理機(jī)在滿負(fù)荷的時(shí)候所產(chǎn)生的最大能耗，也即額定功率，uph,cpu代表CPU使用率，0≤uph,cpu≤1。當(dāng)uph,cpu=1時(shí)，Pph=Pmax，即物理機(jī)能耗達(dá)到最大功率，即額定功率；當(dāng)uph,cpu=0時(shí)，Pph=k·Pmax，代表達(dá)到物理機(jī)達(dá)到最小功率，即空閑功率。

但式(4)僅僅是用于表示物理機(jī)的能耗，在包簇框架下，任意一個(gè)簇包含了一個(gè)或多個(gè)子簇或服務(wù)器，每個(gè)服務(wù)器的CPU使用率是各不相同的，同時(shí)每一個(gè)CPU的k和Pmax又都有所差異，要滿足這些多樣化的條件，需要對式(4)做一些調(diào)整和補(bǔ)充：

(5)

式中:Pρ[t]代表在時(shí)間t中，子簇p的上層功率，當(dāng)簇ρ是最底層簇時(shí)，直接使用物理機(jī)的能耗進(jìn)行計(jì)算，kp代表物理機(jī)p的CPU運(yùn)行時(shí)所損耗功率的參數(shù)，Pp,max代表物理機(jī)p在CPU滿負(fù)荷的時(shí)候所產(chǎn)生的最大能耗，up則代表物理機(jī)p的CPU使用率；當(dāng)簇ρ不是最底層簇時(shí)，Pp代表子簇p的能耗，只需要將子簇p下的所有簇或物理機(jī)的能耗值相加，即可取得整個(gè)簇的能耗。

總能耗的公式為：

(6)

式中：t代表時(shí)間,1≤t≤T,M為子包V的個(gè)數(shù)，N為子簇W的個(gè)數(shù)，1≤V≤M,1≤W≤N。

在包簇框架下，包簇資源分配的目的就是使得能耗最小化：

(7)

約束條件為式(2)、式(3)。

可以看出，要使得能耗最小化，也就是盡可能降低CPU使用率，減少簇的個(gè)數(shù)，從而減少簇的能耗，同時(shí)又要保證每一個(gè)子包都分配到對應(yīng)的子簇上，且需求的資源量沒有超過可用資源量。

2 基于包簇框架的虛擬機(jī)放置算法

2.1 匈牙利算法

匈牙利算法HM(Hungarian Method)一種用于解決多項(xiàng)式時(shí)間分配問題的組合優(yōu)化算法。它的工作原理是將給定的成本矩陣(Costs Matrix)最小化為機(jī)會(huì)成本矩陣(Opportunity Costs Matrix)。如果能夠?qū)⒊杀揪仃囎钚』矫苛泻兔啃兄辽儆幸粋€(gè)0元素的程度，那么有可能做出更好的分配(機(jī)會(huì)成本都為0)。

匈牙利算法的一般數(shù)學(xué)模型是，存在N個(gè)資源，需要分配給N個(gè)對象，并保證總成本最低。公式如下：

Xi,j=[0|1]

(8)

式中:i=1,2,…,N,j=1,2,…,N，當(dāng)Xi,j=0時(shí)，則說明資源i沒有分配給對象j，當(dāng)Xi,j=1時(shí)，則說明資源i分配給對象j。

假設(shè)Ci,j是資源i分配給對象j的成本，那么數(shù)學(xué)模型可以表示為：

(9)

(10)

(11)

式(9)表示最小化資源分配給對象，式(10)和式(11)分別代表了一個(gè)資源只能分配給一個(gè)對象，且一個(gè)對象也只能接受一個(gè)資源，兩者之間是一一對應(yīng)的關(guān)系。

對于匈牙利算法來說，雖然解決了分配問題，仍然存在以下問題：

(1) 分配問題，匈牙利算法只能是一個(gè)資源分配且只分配給一個(gè)對象，而在包簇映射框架中，多個(gè)包可以分配給一個(gè)簇；

(2) 匈牙利算法在大多數(shù)情況下是收斂的，但處理一些特殊情況，是無法找出最優(yōu)解的，而且矩陣階數(shù)越多，越會(huì)存在不收斂的情況，在包簇映射框架中，高階分配矩陣是很常見的。

2.2 改進(jìn)的匈牙利算法

根據(jù)上述的問題，本文參考了文獻(xiàn)[18]提出的快速降階匈牙利算法，在此基礎(chǔ)上通過改進(jìn)算法，設(shè)計(jì)了改進(jìn)的匈牙利算法IHM(Improved Hungarian Method)。

對于提出的第一個(gè)問題，在計(jì)算成本矩陣前，可以做如下的處理：

(1) 將成本矩陣的列數(shù)按照行數(shù)進(jìn)行轉(zhuǎn)化，分割成一個(gè)行數(shù)和列數(shù)完全相等的矩陣。

(2) 如果分割的矩陣最后一個(gè)不滿足行數(shù)和列數(shù)相等，那么就用×補(bǔ)足。

而對于第二個(gè)問題，則需要對整個(gè)匈牙利算法進(jìn)行改進(jìn)：

(3) 逐行(列)的每個(gè)元素減去該行(列)最小值，如果步驟(2)中補(bǔ)足的是行，則順序相反。

(4) 逐行(列)檢查是否存在單獨(dú)的0元素，并且該0元素也是在列(行)上是單獨(dú)的0元素，如果存在，則選中它，并刪除該列和行的其他0元素。

(5) 如果同一行(列)存在0元素在其所在的列(行)是單獨(dú)的0元素，那么就進(jìn)行如下步驟：

① 在其所在的列(行)中找到所有的次小元素，并找出最大值；

② 選中最大值所在的0元素，劃去所在的行和列；

③ 把剛才與其比較的行(列)減去自己行(列)的最小值。

(6) 如果列(行)存在單獨(dú)的0元素，而在行(列)上的其他0元素不是該列(行)上的單獨(dú)0元素，那么就選中這個(gè)0元素，劃去其他的0。

(7) 如果所有行(列)上，都不存在單獨(dú)的0元素，那么就任意選擇0元素最少的行(列)中的任意一個(gè)0，如果行(列)存在相同的情況，就進(jìn)行列(行)的0元素個(gè)數(shù)對比，選擇最少的0元素。

(8) 重復(fù)步驟(3)至(7)，直到找出所有的0。

2.3 實(shí)例驗(yàn)證

由于在包簇映射的框架中，經(jīng)常會(huì)遇到包多于簇的情況發(fā)生(也即虛擬機(jī)的個(gè)數(shù)永遠(yuǎn)大于等于物理機(jī)的個(gè)數(shù))，現(xiàn)假定有7個(gè)包要分配到5個(gè)簇上，并且能夠保證5個(gè)簇上的資源足夠能滿足7個(gè)包所需要的資源(上層包簇所分配的必要條件)，它們之間的能耗矩陣如表1所示。

表1 分配7個(gè)包給5個(gè)簇的能耗矩陣

首先轉(zhuǎn)換為成本矩陣：

并用×元素補(bǔ)齊第二個(gè)矩陣中缺失的部分：

接下來對兩個(gè)矩陣進(jìn)行改進(jìn)的匈牙利算法求解：

矩陣1：

矩陣2：

所以，最后的分配方案為：

方案1：包1分配給簇5；包2分配給簇1；包3分配給簇2；包4分配給簇4；包5分配給簇3；包6分配給簇1；包7分配給簇4；

方案2：包1分配給簇5；包2分配給簇1；包3分配給簇4；包4分配給簇2；包5分配給簇3；包6分配給簇1；包7分配給簇4。

3 相關(guān)實(shí)驗(yàn)

3.1 能耗模型

在進(jìn)行實(shí)驗(yàn)前，首先需要計(jì)算出式(4)中的Pmax和k。通過觀察可發(fā)現(xiàn)，兩者都是定值，也即k·Pmax代表了空閑功率。根據(jù)文獻(xiàn)[19]可知如下參數(shù)，表2是CPU類型為Intel Core 2 Duo 2.93 GHz 和Intel Core i5 2.5 GHz的服務(wù)器的能耗值，單位為W。

表2 不同CPU的服務(wù)器參數(shù)

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

為了驗(yàn)證本文IHM算法的有效性，在Cloudsim[20]上進(jìn)行仿真實(shí)驗(yàn)。要對比的算法分別是：基于包簇映射框架下改進(jìn)的匈牙利算法IHMPC(Improved Hungarian Method based on Package-Cluster)，在引言中所提及的能耗感知最佳適應(yīng)遞減算PABFD(Power Aware Best Fit Decreasing)[3]，以及混合遺傳算法HGA(Hybrid Genetic Algorithm)[4]。

實(shí)驗(yàn)主要分為兩部分，實(shí)驗(yàn)1是驗(yàn)證三種算法的分配時(shí)間；實(shí)驗(yàn)2是驗(yàn)證三種算法在相同時(shí)間內(nèi)的CPU使用率以及能耗變化情況。

實(shí)驗(yàn)1分配時(shí)間

分別用不同數(shù)量的虛擬機(jī)和物理機(jī)進(jìn)行分配時(shí)間的測試。在IHMPC算法中，包簇映射的層次結(jié)構(gòu)為3層結(jié)構(gòu)，頂層包之下各有10個(gè)包，二級包下的虛擬機(jī)個(gè)數(shù)分配為虛擬機(jī)總個(gè)數(shù)除以10；簇的分配個(gè)數(shù)比包少一半，但層次結(jié)構(gòu)相同。例如，500臺虛擬機(jī)分配到150臺服務(wù)器上，包簇結(jié)構(gòu)為1個(gè)頂層包，10個(gè)二級包，50個(gè)虛擬機(jī)；1個(gè)頂層簇，5個(gè)二級簇，50個(gè)服務(wù)器。

圖1是三種算法在不同虛擬機(jī)和服務(wù)器個(gè)數(shù)的情況下的分配時(shí)間?？梢钥闯觯皟煞N算法在虛擬機(jī)和服務(wù)器數(shù)量變多的情況下，分配時(shí)間也逐漸變多，而IHMPC始終保持了比較良好的分配時(shí)間，在虛擬機(jī)數(shù)量、服務(wù)器數(shù)量超過600/220臺時(shí)，平均比PABFD算法快了將近56.2%，比HGA算法快了將近34.8%。

實(shí)驗(yàn)2CPU使用率以及能耗

為了更好地模擬數(shù)據(jù)中心的龐大數(shù)據(jù)量，在實(shí)驗(yàn)2中模擬了10 000臺服務(wù)器和15 000臺虛擬機(jī)。需要特別說明的是，在包簇映射框架下，需要對包的結(jié)構(gòu)層次進(jìn)行劃分，分為5層包結(jié)構(gòu)，如圖2所示。

本次實(shí)驗(yàn)共劃分了1個(gè)頂層包、3個(gè)二級包、5個(gè)三級包、10個(gè)四級包，在這里的四級包又稱為底層包，每一個(gè)底層包中又包含了100臺虛擬機(jī)。相應(yīng)地，簇結(jié)構(gòu)也要?jiǎng)澐譃?個(gè)二級簇、10個(gè)三級簇、10個(gè)四級簇，每一個(gè)底層簇又包含了50個(gè)服務(wù)器。

圖3是在不同時(shí)間下，三者算法的CPU使用率，可以看出，在相同的條件下，本文提出的IHMPC算法，由于能夠使虛擬機(jī)較為平均地放置在物理機(jī)上，與前兩者相比，在CPU使用率上始終不超過68%，較好地保持了在較低的水平，實(shí)現(xiàn)了負(fù)載均衡。

圖4是在不同時(shí)間下，三者算法的能耗值曲線圖。從圖中可以看出，由于保持了較低的CPU使用率，使得改進(jìn)算法的總能耗也比前兩種算法功耗更少，尤其在25分鐘至50分鐘左右的CPU使用高峰時(shí)段，平均比PABFD算法的總能耗降低了4.8%，比HGA算法的總能耗降低了3.7%。這證明所提出的IHMPC算法在能耗優(yōu)化上有明顯的優(yōu)勢，也滿足了云計(jì)算中虛擬機(jī)的快速分配以及服務(wù)器的負(fù)載均衡。

圖3 不同時(shí)間下的CPU使用率

圖4 不同時(shí)間下的能耗值

4 結(jié) 語

本文首先沿用了一種新的虛擬機(jī)放置策略，即基于包簇映射框架的資源分配結(jié)構(gòu)，在此基礎(chǔ)上，設(shè)計(jì)了能耗模型和改進(jìn)的匈牙利算法來進(jìn)行能耗優(yōu)化。所提出的算法同時(shí)滿足了分配速度和能耗。在虛擬機(jī)和物理機(jī)數(shù)量巨大的情況下，數(shù)據(jù)中心依然能夠較快地完成分配。在能耗上，始終保持CPU使用率在一個(gè)較平均的水平，以達(dá)到降低能耗的目標(biāo)。實(shí)驗(yàn)結(jié)果表明，與其他算法相比，該算法在相同條件下可以大大降低云計(jì)算系統(tǒng)的能耗。