單步啟發(fā)式策略的備份虛擬機復(fù)用策略

陳鵬飛,李昕怡,齊勇,張小輝

(西安交通大學(xué)電子與信息工程學(xué)院,710049,西安)

?

單步啟發(fā)式策略的備份虛擬機復(fù)用策略

陳鵬飛,李昕怡,齊勇,張小輝

(西安交通大學(xué)電子與信息工程學(xué)院,710049,西安)

針對云環(huán)境中的備份虛擬機(VM)利用率過低的問題,提出了基于不停歇多臂賭博機(RMAB)方法的備份VM分時復(fù)用策略,并給出了獲得最優(yōu)解的條件。該策略將每個備份VM形式化為具有“空閑”(1)和“占用”(0)兩種狀態(tài)的Markov過程,將多個備份VM的調(diào)度問題形式化為具有多個Markov過程的Markov決策問題(MDP),最終目標是期望在有限的備份VM數(shù)量下,最大化備份VM的利用率同時保證系統(tǒng)整體的可用性不會明顯降低。然而,利用傳統(tǒng)的動態(tài)規(guī)劃方法求解該問題時會出現(xiàn)維度爆炸的現(xiàn)象,從而導(dǎo)致問題不可解,故將該Markov決策問題轉(zhuǎn)化為RMAB問題,然后利用簡單易操作的單步啟發(fā)式算法進行求解,并通過計算單步最優(yōu)獲得長期最優(yōu)解,在特定條件下該策略可以保證得到的解為最優(yōu)解。模擬實驗結(jié)果表明:所提方法將備份VM與服務(wù)VM之間的備份比例從1∶1擴展成1∶M(M?1),同時保證失效VM的恢復(fù)比率不低于96%,相應(yīng)地備份VM的利用率顯著提高;在VM失效率較低的條件下,備份VM利用率比1∶1備份時提高了89%;利用該備份VM調(diào)度策略,有助于減少整個云計算平臺的建設(shè)和運維費用。

云計算;可用性;虛擬機遷移;不停歇多臂賭博機

云基礎(chǔ)設(shè)施可以通過虛擬化技術(shù)彈性地管理計算資源,進行靈活地硬件資源共享,以節(jié)省硬件成本和能耗成本。但是,復(fù)雜的云計算軟件棧中的bug、瞬息多變的運行時環(huán)境以及隨機出現(xiàn)的硬件失效等導(dǎo)致云系統(tǒng)的可用性保障難度驟增。為了保障云應(yīng)用的高可用性,云基礎(chǔ)設(shè)施往往采用冗余備份的方式,為相關(guān)虛擬機(VM)實例提供一個或者多個備份實例。然而,過度的冗余備份會造成計算資源的浪費,增加云基礎(chǔ)平臺的運維成本。

長久以來學(xué)術(shù)界和工業(yè)界一直聚焦于尋求一種高效的VM預(yù)留或者整合策略,以提高用于生產(chǎn)即直接提供服務(wù)的虛擬資源或者硬件資源的利用率,如文獻[1-2]等通過設(shè)計新的任務(wù)調(diào)度器或者虛擬機調(diào)度器,達到提高資源利用率的目的。為了達到VM的k-resilient[3]即允許k個物理機同時失效,每個VM至少需要提供k個備份。假定在最弱的容錯條件下即1-resilient,有n個VM提供服務(wù),云基礎(chǔ)平臺共需要分配2n個虛擬機,如果采用熱備份,計算資源和能耗是沒有容錯情況的兩倍。然而,對于單個VM來說失效是稀疏事件,備份VM大部分時間處于空閑狀態(tài),如果利用空閑的備份VM對其他需要備份的VM進行備份,即對備份VM進行分時復(fù)用,可以減少備份VM的數(shù)量,同時減少能耗。解決該問題的難點包括:①大規(guī)模的云環(huán)境中包含成百上千的備份VM,每個備份VM都有各自特定的變化規(guī)律,如果把每個VM形式化為一個變量,問題最終形式化為超高維資源優(yōu)化分配問題,而對此問題的精確求解幾乎是不可能的,因此如何設(shè)計算法通過降維或者問題分解的方法解決超高維優(yōu)化問題是主要難點;②在云環(huán)境中,任意時刻都會出現(xiàn)多個VM失效,如何保證盡可能多的失效VM得到備份,也是問題的難點之一;③由于VM失效是動態(tài)變化的,因此要求調(diào)度策略可以實時在線決策,在每個時間槽內(nèi)能快速輸出調(diào)度結(jié)果;④調(diào)度策略在保證備份VM得到充分利用的同時,不能明顯影響到系統(tǒng)的整體可用性,在有限的備份VM條件下計算出能夠進行備份容錯的VM上限也是難點之一。

針對以上問題及難點,本文將備份VM復(fù)用問題形式化為包含‘0’、‘1’兩狀態(tài)的不停歇多臂賭博(RMAB)問題[4],通過將m維的優(yōu)化問題分解為m個一維優(yōu)化問題,給出了VM失效模型已知情況下的優(yōu)化算法,并給出了算法最優(yōu)解條件。模擬實驗結(jié)果表明了本文提出的方法的有效性。

1 虛擬機備份

軟件系統(tǒng)運行過程中,由于受到軟件自身Bug、硬件損壞、斷電以及其他外界環(huán)境變化的影響,會出現(xiàn)性能下降和失效現(xiàn)象。軟件失效的特征規(guī)律在軟件可靠性領(lǐng)域一直是個開放性話題,目前廣泛采用的失效模型(兩次失效之間的間隔時間分布)有Weibull分布[5]和Poisson分布[6]。軟件出現(xiàn)失效后,系統(tǒng)管理員會采取一定的措施,例如重啟等恢復(fù)系統(tǒng),恢復(fù)時間通常服從Lognormal分布[5]。從軟件的長期運行過程看,軟件系統(tǒng)一直處于“失效-恢復(fù)”的循環(huán)過程中。本文主要討論失效時間符合Weibull分布和Poisson分布、恢復(fù)時間符合Lognormal分布時的情況。

為了保障云平臺的可用性,大量VM用于冗余備份。冗余備份的方式主要分為熱備份和冷備份,熱備份是指主服務(wù)VM實例與備份VM同時運行在多臺物理機上,兩者之間的運行狀態(tài)時刻保持同步,例如Remus[7]等;冷備份不需要主服務(wù)VM與備份VM同時運行以保持運行狀態(tài)的一致性,而是當主服務(wù)VM需要備份時,備份VM再啟動,運行狀態(tài)或者負載從主服務(wù)VM拷貝到備份VM。本文只討論該種備份方式,利用虛擬機在線遷移技術(shù)(live migration),將即將失效的VM遷移到備份服務(wù)器上,等VM恢復(fù)后備份VM關(guān)閉,原VM提供服務(wù),采用這種方式既能保證軟件運行時狀態(tài)的一致性又能減少軟件的懸停時間。

針對備份資源的有效利用問題,文獻[8]設(shè)計了Yank系統(tǒng),可以利用一個備份服務(wù)器對多個Transient服務(wù)器進行備份,但是當VM轉(zhuǎn)移到Stable服務(wù)器上后,仍然是1∶1的備份,與本文強調(diào)的對備份系統(tǒng)的分時復(fù)用策略不同。文獻[9]討論如何通過減少備份供電基礎(chǔ)設(shè)施,例如UPS等,達到降低數(shù)據(jù)中心建設(shè)成本的目的,與本文的核心思想一致。本文第一次利用RMAB模型,對備份虛擬資源進行有效利用。

2 單步啟發(fā)式策略

2.1 問題形式化

本文提出的策略適用于以下場景:一部分VM擁有專屬的備份VM,稱之為高優(yōu)先級VM,當高優(yōu)先級VM需要備份時,可以立即遷移到相應(yīng)的備份VM上;一部分VM沒有專屬的備份VM,稱之為次優(yōu)先級VM,當次優(yōu)先級VM需要備份時,依據(jù)本文提出的調(diào)度方案選擇合適的備份VM進行遷移,如果出現(xiàn)高優(yōu)先級VM與次優(yōu)先級VM爭用備份VM情況,高優(yōu)先級VM優(yōu)先調(diào)度。

開始階段,云系統(tǒng)為特定的N個高優(yōu)先級VM按照1∶1的比例分配了N個備份VM,以保證這些VM的高可用性,備份VM是這組高優(yōu)先級VM狀態(tài)的直接反映即高優(yōu)先級VM正常,備份VM空閑;高優(yōu)先級VM異常,備份VM忙碌,因此在后續(xù)部分,本文不再關(guān)注這N個高優(yōu)先級VM的狀態(tài),而只關(guān)注N個備份VM的狀態(tài)。每個備份VM的狀態(tài)按照獨立同分布的Markov過程演化,令sj(t)和Sj分別表示備份VMj(j=1,2,…,N)在t時刻的狀態(tài)和狀態(tài)空間,令Pj表示備份VMj的狀態(tài)轉(zhuǎn)移矩陣,S(t)={sj(t),j∈{1,2,…,N}}表示N個備份VM在t時刻的狀態(tài)。用狀態(tài)‘1’表示備份VM空閑,‘0’表示備份VM被占用,則備份VM的狀態(tài)演化過程可以表述為包含‘0’、‘1’兩狀態(tài)的Markov過程。其中,sj(t)∈{0,1},S(t)∈{0,1}N,Sj={0,1},狀態(tài)轉(zhuǎn)移矩陣為

在t時刻感知這N個備份VM狀態(tài),選擇當前狀態(tài)為‘1’的備份VM,利用這些備份VM可以為其他失效VM提供備份。

(1)

π:Ω(t)→A(t), |A(t)|=K,t=1,2,…,T

本文目的在于尋找最優(yōu)策略π*,最大化有限時間區(qū)段或者無限時間區(qū)段的折現(xiàn)回報值為

(2)

式中:β為折現(xiàn)因子,0≤β≤1,表示當前的決策產(chǎn)生的后續(xù)回報比即時回報的價值小;Rπ(Ω(t))表示信念狀態(tài)為Ω(t)時,采取策略π產(chǎn)生的回報;Ω(1)為初始信念狀態(tài),當T為有限值時,為有限時段的決策,當T→∞時,為無限時段的決策,本文只討論有限時段的決策。

為了評價算法的優(yōu)劣,本文提出了失效VM的恢復(fù)率、備份VM的利用率增量和丟失的回報值3個度量指標。假設(shè)在t時刻失效的次優(yōu)先級VM的個數(shù)為ft,在T個決策時間槽內(nèi)策略π產(chǎn)生的失效VM的恢復(fù)率定義為

備份VM經(jīng)過分時復(fù)用后的利用率比只為高優(yōu)先級VM提供備份時增加了,在決策時間長度T內(nèi),策略π產(chǎn)生的備份VM的利用率增量定義為

ind

丟失的回報值定義為

式中:μj(t)為t時刻將所有備份VM的回報值按序排列后的第j大回報值,不失一般性地令

μ1(t)≥μ2(t)≥μ3(t)≥…≥μN(t)

2.2 問題求解

本文將備份VM的調(diào)度問題轉(zhuǎn)化為不停歇的多臂賭博問題,解決不停歇的多臂賭博問題的核心思想是將一個M維的超高維優(yōu)化問題分解為M個一維優(yōu)化問題,計算復(fù)雜度大大降低,本文利用該思想進行求解,提出了單步啟發(fā)式算法,并對解的最優(yōu)條件進行了分析。

針對VM失效模型已知的情況,本文提出了“單步啟發(fā)式復(fù)用策略”。求解式(2)的最優(yōu)解,可以采用動態(tài)規(guī)劃的方法迭代求解,有限時段T內(nèi)的值函數(shù)為

式中:Vt(Ω(t))表示從t(1≤t≤T)時刻到T時刻期望的最大回報值;ε表示決策A(t)中備份VM狀態(tài)為‘1’的集合,A(t)ε表示決策A(t)中備份狀態(tài)為‘0’的集合,信念狀態(tài)Ω(t+1)按照式(1)更新。由于云系統(tǒng)中備份VM的數(shù)量巨大,信念狀態(tài)Ω(t)的狀態(tài)空間過于龐大,導(dǎo)致很難給出值函數(shù)的最優(yōu)解,因此本文采用單步啟發(fā)式復(fù)用策略,最大化當前決策產(chǎn)生的即時回報值,而不考慮決策對系統(tǒng)未來狀態(tài)產(chǎn)生的影響,計算復(fù)雜度大大降低,但是解的最優(yōu)性難以保證,因此本文討論了單步啟發(fā)式復(fù)用策略的最優(yōu)性條件。

單步啟發(fā)式復(fù)用策略的求解目標不再是式(2),而是退化為

(3)

只需計算在t時刻使得即時回報R(Ω(t))最大化的策略π,即將所有備份VM在t時刻的即時回報R(ωj(t))(1≤j≤N)按照降序排列,選擇前K個最大回報值對應(yīng)的備份VM,該算法實現(xiàn)了從N維優(yōu)化到一維的降維目標。在利用單步啟發(fā)式復(fù)用策略求解之前,需要根據(jù)VM失效模型計算出備份VM的狀態(tài)轉(zhuǎn)移矩陣以及初始信念狀態(tài)Ω(1)。

通過Markov穩(wěn)態(tài)方程計算出穩(wěn)態(tài)情況下,備份VMj處于‘0’、‘1’的概率為

單步啟發(fā)式VM復(fù)用過程如下。

輸出:從t到t+T之間選擇出備份VM序列。

(1)計算每個備份VM的轉(zhuǎn)移矩陣P以及初始信念狀態(tài)Ω(1);

(2)在t時刻對所有備份VM的信念狀態(tài)進行排序;

(3)選擇前K個信念狀態(tài)最大的備份VM;

(4)感知由步驟(3)選出的K個備份VM的狀態(tài),將失效VM調(diào)度到狀態(tài)為‘1’的備份VM上;

(5)根據(jù)式(1)更新信念狀態(tài),計算t+1時刻的調(diào)度決策;

(6)重復(fù)步驟(2)～(5)直至t+T時刻。

2.3 最優(yōu)解條件

文獻[10]采用相同的方法求解機會頻譜訪問問題(OSA),證明了當p11>p01時,利用啟發(fā)式算法求解OSA問題具有最優(yōu)解。

定理1 對于具有兩狀態(tài)‘0’和‘1’的N個通信信道,且每個信道遵從獨立同分布的Markov過程的OSA問題,無論從N個信道中選擇一個還是K(1p01時,解是最優(yōu)的。

證畢。

2.4 復(fù)雜度分析

由單步啟發(fā)式算法的描述可以看出,算法主要包括對備份VM信念狀態(tài)的排序過程和對備份VM狀態(tài)的更新過程。給定N個備份VM,決策時間長度為T,采用快速排序方法,在一個時間槽內(nèi)排序過程的時間復(fù)雜度為O(NlogN),狀態(tài)更新過程的時間復(fù)雜度為O(N),總的時間復(fù)雜度為O(NlogN),因此在T個時間槽內(nèi)的時間復(fù)雜度為O(T*NlogN)。與POMDP等方法的指數(shù)復(fù)雜度相比,單步啟發(fā)式算法的時間復(fù)雜度大大降低了。

3 實驗結(jié)果

首先,根據(jù)高優(yōu)先級VM的失效、恢復(fù)規(guī)律,產(chǎn)生了備份VM的初始利用規(guī)律。為了模擬VM失效模型及恢復(fù)模型,利用Matlab按照“正?！А毖h(huán)產(chǎn)生符合特定分布的隨機數(shù)?！罢！彪S機數(shù)表示高優(yōu)先級VM的失效間隔時間,也是備份VM的空閑時間;“失效”隨機數(shù)表示高優(yōu)先級VM的修復(fù)時間,也是備份VM的忙碌時間。然后,將隨機數(shù)按照單位時間離散成‘0’、‘1’二值序列,表示特定時刻某個VM所處的狀態(tài),例如利用失效模型產(chǎn)生隨機數(shù)4,二值化為“1111”,表示在4個連續(xù)時間槽內(nèi)備份VM是空閑的。本文共模擬了N(N=50,100,150,200,500)個備份VM,每個備份VM的失效及恢復(fù)模型都是獨立同分布的,且包含1 000個“0,1”值。在每個時間槽內(nèi)(模擬時間單位為min),利用單步啟發(fā)式復(fù)用算法選擇K個備份VM,按照感知能力的不同,分析K取不同值時的算法性能,另外本文針對不同的次優(yōu)先級VM失效率f,討論了有限備份次優(yōu)先級VM的數(shù)量上限。模擬實驗程序采用Matlab實現(xiàn),通過實驗分析,回答了以下3個問題。

問題一 單步啟發(fā)式算法產(chǎn)生的調(diào)度方案效果。

在此實驗中,備份VM數(shù)量N為500,初始階段每個備份VM空閑時間分別服從參數(shù)α=17、β=1的Weibull分布,忙碌時間服從參數(shù)μ=1、δ=0.5的Lognormal分布,每個VM的平均效率為0.05,模塊可感知的備份VM數(shù)量為400,決策時間長度為1 000個時間槽。利用單步啟發(fā)式復(fù)用策略得出的regret的對數(shù)如圖1所示。由圖中觀察得到,regret的對數(shù)值隨著決策時間增加呈現(xiàn)收斂趨勢,說明單步啟發(fā)式復(fù)用策略具有對數(shù)最優(yōu)。這是因為隨著決策次數(shù)增加,單步啟發(fā)式策略不斷感知新的備份VM的狀態(tài),單步更新的“信念狀態(tài)”越來越能精確反映每個備份VM的“權(quán)重”,選擇策略也漸進趨向最優(yōu)策略。

圖1 regret的對數(shù)隨決策時間的變化曲線

圖2展示了采用單步啟發(fā)式策略對空閑的備份VM進行調(diào)度后,每個備份VM的利用率增量。從圖中看出,單步啟發(fā)式復(fù)用策略在上述場景下將備份VM的利用率平均提高了86.5%,使備份VM的空閑時段得到了充分利用,節(jié)省了資源。

圖2 每個備份VM的利用率增量

問題二 當系統(tǒng)參量變化時,單步啟發(fā)式算法產(chǎn)生的效果變化。

在云系統(tǒng)中,軟件運行時的內(nèi)外環(huán)境頻繁變動,本文主要探討了高優(yōu)先級VM的失效率變化、失效模型類型變化、可感知的備份VM的數(shù)量變化對單步啟發(fā)式復(fù)用策略的影響。

(1)失效率變化。本文通過調(diào)整失效模型或者恢復(fù)模型的參數(shù)達到調(diào)整失效率的目的。設(shè)定失效模型為Weibull分布,恢復(fù)模型為Lognormal分布,K=400,備份VM的數(shù)量為500。討論表1中4種情況下單步啟發(fā)式復(fù)用策略的效果。

表1 失效率及相應(yīng)的模型參數(shù)

圖3比較了不同失效率情況下,500個備份VM經(jīng)過復(fù)用后的平均利用率增量。隨著失效率的增加,備份VM的利用率增量逐漸降低。這是因為失效率增加后,每次經(jīng)過單步啟發(fā)式策略選擇出的400個備份VM集合中狀態(tài)為‘0’的備份VM增加,即與高優(yōu)先級VM出現(xiàn)資源爭用的情況增多,但即使在高失效率0.2的情況下,單步啟發(fā)式復(fù)用策略仍然獲得了71.7%的利用率增量。與利用率增量變化情況相似,regret也隨著失效率增加而增加,如圖4所示。

圖3 不同失效率場景下的平均利用率增量

圖4 不同失效率場景下的regret的對數(shù)的變化情況

(2)失效模型類型變化。固定失效率為0.05,K=400,備份VM的數(shù)量為500,討論兩種分布:失效模型采用參數(shù)λ為17的Poisson分布(d-1);失效模型采用參數(shù)α=17、β=1的Weibull分布,恢復(fù)模型均為參數(shù)μ=1、δ=0.5的Lognormal分布(d-2)。圖5展示了d-1、d-2兩種情況下備份VM的利用率增量,從圖中可以看出,利用率增量相差并不大,平均增量都是0.84,說明單步啟發(fā)式策略產(chǎn)生的效果在失效率相同的情況下與失效模型關(guān)系不大。這是因為失效和恢復(fù)模型都是單步啟發(fā)式策略的已知條件,并據(jù)此進行單步狀態(tài)更新。圖6展示了d-1、d-2兩種情況下備份VM在1 000個時間槽內(nèi)的regret變化曲線,兩條曲線幾乎重疊,驗證了上述結(jié)論。

圖5 d-1、d-2兩種情況下備份VM的利用率增量

圖6 d-1、d-2兩種情況下備份VM的regret的對數(shù)的變化曲線

(3)K值變化。固定失效模型和恢復(fù)模型,備份VM的數(shù)量為500,調(diào)整K值,觀察單步啟發(fā)式策略的效果。圖7展示了失效模型參數(shù)α=17、β=1的Weibull分布,恢復(fù)模型參數(shù)μ=1、δ=0.5的Lognormal分布時備份VM的平均利用率隨K值的變化情況,從圖中可以直觀看出,利用率增量隨著K值增加而增加。這是因為K值決定了可感知的備份數(shù)量以及備份VM被調(diào)度的數(shù)量,被調(diào)度的備份VM數(shù)量越多,利用率增量也就越大,而且K與利用率增量之間遵循線性關(guān)系。regret的對數(shù)與K值之間卻沒有單調(diào)的線性關(guān)系,圖8展示了VM失效率較低時的regret變化情況,regret的對數(shù)值隨著K值增加而增加。但是,當VM失效率較高時,K=100、400時的regret對數(shù)曲線幾乎重疊在一起,與K值之間不存在單調(diào)線性關(guān)系,如圖9所示。

通過上述分析發(fā)現(xiàn),單步啟發(fā)式復(fù)用策略的決策效果受VM失效率以及可感知的備份VM數(shù)量K的影響較大,但是在失效率固定時不受失效模型類型的影響。上述3種因素與決策效果之間存在復(fù)雜的線性以及非線性關(guān)系,本文只給出了定性分析,定量關(guān)系將在后續(xù)工作中進行討論。

圖7 利用率增量隨K值變化的情況

圖8 VM失效率為0.05時regret的對數(shù)與K之間的關(guān)系

圖9 VM失效率為0.2時regret的對數(shù)與K之間的關(guān)系

問題三 在滿足可用性要求的前提下,備份VM能備份的次優(yōu)先級VM數(shù)量的上限。

本實驗設(shè)定備份VM的數(shù)量N=500,可感知的備份VM的數(shù)量K=400,失效模型采用參數(shù)α=17、β=1的Weibull分布,恢復(fù)模型采用參數(shù)μ=1、δ=0.5的Lognormal分布,討論當次優(yōu)先級VM在失效率為0.01、0.05、0.1、0.2時,備份VM可備份的次優(yōu)先級VM的數(shù)量上限。圖10展示了失效VM的覆蓋率隨次優(yōu)先級VM數(shù)量變化的曲線。以失效VM覆蓋率96%為基準,從圖10中可以看出,當失效率為0.01、0.05、0.1、0.2時,500個備份VM可以備份的VM上限分別為9 000,8 000,6 000和2 000,備份比例為1∶18,1∶16,1∶12和1∶4,即使在次優(yōu)先級VM頻繁失效的情況下,備份比例仍可以達到1∶4。在保證失效VM被100%覆蓋的情況下,單步啟發(fā)式策略仍可以在次優(yōu)先級失效率較高時獲得1∶3的備份比。

圖10 失效VM的覆蓋率隨次優(yōu)先級VM數(shù)量變化曲線

本實驗討論單步啟發(fā)式算法的運行時間與可感知的備份VM的數(shù)量K和備份VM的數(shù)量N之間的關(guān)系,算法的執(zhí)行單步?jīng)Q策即T=1時的運行時間如表2所示。從表2可以看出,算法的執(zhí)行時間處在ms級水平,完全可以做到實時決策,而且運行時間隨著N值增加而增加,兩者存在單調(diào)變化關(guān)系,但與K值之間不存在單調(diào)變化關(guān)系,說明單步啟發(fā)式算法的執(zhí)行時間與N相關(guān)但是與K無關(guān)。

表2單步啟發(fā)式算法執(zhí)行單步?jīng)Q策的運行時間ms

4 結(jié) 論

為了充分利用過度冗余的備份虛擬資源,本文提出了基于RMAB問題的單步啟發(fā)式復(fù)用策略。該策略將單個備份VM描述為獨立同分布的Markov隨機過程,按照特定的概率轉(zhuǎn)移矩陣進行單步狀態(tài)更新,通過最大化單步回報達到備份VM利用率最大化的目的。此外,本文給出了在特定失效、恢復(fù)模型下的最優(yōu)解條件,從理論上證明了單步啟發(fā)式復(fù)用策略的最優(yōu)性。模擬實驗結(jié)果表明,單步啟發(fā)式復(fù)用策略可以將傳統(tǒng)的1∶1備份擴展成1∶M(M?1),同時保證失效VM的恢復(fù)率不低于96%,相應(yīng)備份虛擬資源的利用率顯著提高。在VM失效率較低的條件下,備份虛擬資源利用率比1∶1備份時提高了89%,從而可以有效減少云計算平臺的建設(shè)和運維費用。

[1] JAYASINGHE D, PU C. Improving performance and availability of services hosted on IaaS clouds with structural constraint-aware virtual machine placement [C]∥Proceedings of the 8th IEEE International Conference on Services Computing. Piscataway, NJ, USA: IEEE, 2011: 72-79.

[2] VERMA A, DASGUPTA G, TAPAN K, et al. Server workload analysis for power minimization using consolidation [C]∥Proceedings of the 2009 Conference on USENIX Annual Technical Conference. Berkeley, CA, USA: USENIX, 2009: 28.

[3] BIN E, BIRAN O. Guaranteeing high availability goals for virtual machine placement [C]∥Proceedings of the 31st International Conference on Distributed Computing Systems. Piscataway, NJ, USA: IEEE, 2011: 700-709.

[4] WHITTLE P. Restless bandits: activity allocation in a changing world [J]. Journal of Applied Probability, 1988, 25(2): 287-298.

[5] SCHROEDER B, GIBSON G A. A large-scale study of failures in high-performance computing systems [J]. IEEE Transactions on Dependable and Secure Computing, 2010, 7(4): 337-350.

[6] OKAMURA H, TADASHI D, SHUNJI O. Software reliability growth models with normal failure time distributions [J]. Reliability Engineering & System Safety, 2013, 11(6): 135-141.

[7] CULLY B, LEFEBVRE G. Remus: high availability via asynchronous virtual machine replication [C]∥Proceedings of the 5th USENIX Symposium on Networked Systems Design and Implementation. Berkeley, CA, USA: USENIX, 2008: 161-174.

[8] SINGH R, IRWIN D, SHENOY P, et al. Yank: enabling green data centers to pull the plug [C]∥Proceedings of the 10th USENIX Symposium on Networked Systems Design and Implementation. Berkeley, CA, USA: USENIX, 2013: 143-155.

[9] WANG D, GOVINDAN S, ANAND S, et al. Under provisioning backup power infrastructure for datacenters [C]∥Proceedings of the 19th International Conference on Architectural Support for Programming Languages and Operating Systems. New York, USA: ACM, 2013: 177-192.

[10]AHMAD S, HAJI A, LIU M. Multi-channel opportunistic access: a case of restless bandits with multiple plays [C]∥Proceedings of the 47th Annual Allerton Conference on Communication, Control and Computing. Piscataway, NJ, USA: IEEE, 2009: 1361-1368.

(編輯 趙煒)

Multiplexing of Backup Virtual Machine Based on Single-Step Heuristic Policy

CHEN Pengfei,LI Xinyi,QI Yong,ZHANG Xiaohui

(School of Electronics and Information Engineering, Xi’an Jiaotong University, Xi’an 710049, China)

Based on the restless multi-arm bandit (RMAB) approach, a multiplexing strategy of backup virtual machines (VMs) is proposed to resolve the problem of low utilization of backup VMs in the cloud environment, and the optimal condition is given. This strategy regards an individual backup VM as a Markov process with two states, namely “idle” (1) and “backup” (0), and models the scheduling of multiple backup VMs as a Markov decision problem (MDP) consisting of multiple Markov processes. The goal of this strategy is to maximize the utilization of backup VMs without obvious reduction in the system availability under the constraint of limited backup VMs. However, this problem is computationally intractable with traditional dynamic programming methods due to the curse of dimensionality. Therefore, this paper transforms the original MDP problem to a RMAB problem and adopts a simple single-step heuristic policy to resolve it. By calculating the single-step optimal solution, the long-term optimal solution can be obtained. Under specific conditions, the optimal solution of this strategy is guaranteed. The results of simulation experiments show that the proposed policy can achieve the goal of extending the backup ratio between backup VMs to service VMs from 1∶1 to 1∶M (M? 1) while the failed VM assurance rate is no lower than 96%. Correspondingly, the utilization of backup resources is significantly enhanced. When the failure rate of service VM is low, the utilization of backup resources can be raised 89% compared with the 1∶1 backup. The building and operation costs of a cloud platform can be reduced with the help of this backup VM scheduling strategy.

cloud computing; availability; VM migration; restless multi-armed bandit

2015-05-10。 作者簡介:陳鵬飛(1987—),男,博士生;齊勇(通信作者),男,教授,博士生導(dǎo)師。 基金項目:國家自然科學(xué)基金資助項目(60933003)。

時間:2015-11-04

網(wǎng)絡(luò)出版地址:http:∥www.cnki.net/kcms/detail/61.1069.T.20151104.2222.002.html

10.7652/xjtuxb201601016

TP301

A

0253-987X(2016)01-0100-08