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

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

?

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

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

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

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

云計(jì)算;可用性;虛擬機(jī)遷移;不停歇多臂賭博機(jī)

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

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

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

1 虛擬機(jī)備份

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

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

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

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

2.1 問(wèn)題形式化

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

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

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

(1)

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

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

(2)

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

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

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

ind

丟失的回報(bào)值定義為

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

μ1(t)≥μ2(t)≥μ3(t)≥…≥μN(yùn)(t)

2.2 問(wèn)題求解

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

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

式中:Vt(Ω(t))表示從t(1≤t≤T)時(shí)刻到T時(shí)刻期望的最大回報(bào)值;ε表示決策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)空間過(guò)于龐大,導(dǎo)致很難給出值函數(shù)的最優(yōu)解,因此本文采用單步啟發(fā)式復(fù)用策略,最大化當(dāng)前決策產(chǎn)生的即時(shí)回報(bào)值,而不考慮決策對(duì)系統(tǒng)未來(lái)狀態(tài)產(chǎn)生的影響,計(jì)算復(fù)雜度大大降低,但是解的最優(yōu)性難以保證,因此本文討論了單步啟發(fā)式復(fù)用策略的最優(yōu)性條件。

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

(3)

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

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

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

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

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

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

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

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

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

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

2.3 最優(yōu)解條件

文獻(xiàn)[10]采用相同的方法求解機(jī)會(huì)頻譜訪問(wèn)問(wèn)題(OSA),證明了當(dāng)p11>p01時(shí),利用啟發(fā)式算法求解OSA問(wèn)題具有最優(yōu)解。

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

證畢。

2.4 復(fù)雜度分析

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

3 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

圖2 每個(gè)備份VM的利用率增量

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

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

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

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

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

圖3 不同失效率場(chǎng)景下的平均利用率增量

圖4 不同失效率場(chǎng)景下的regret的對(duì)數(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,說(shuō)明單步啟發(fā)式策略產(chǎn)生的效果在失效率相同的情況下與失效模型關(guān)系不大。這是因?yàn)槭Ш突謴?fù)模型都是單步啟發(fā)式策略的已知條件,并據(jù)此進(jìn)行單步狀態(tài)更新。圖6展示了d-1、d-2兩種情況下備份VM在1 000個(gè)時(shí)間槽內(nèi)的regret變化曲線,兩條曲線幾乎重疊,驗(yàn)證了上述結(jié)論。

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié) 論

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

[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。 作者簡(jiǎn)介:陳鵬飛(1987—),男,博士生;齊勇(通信作者),男,教授,博士生導(dǎo)師。 基金項(xiàng)目:國(guó)家自然科學(xué)基金資助項(xiàng)目(60933003)。

時(shí)間: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