單步啟發式策略的備份虛擬機復用策略

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

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

?

單步啟發式策略的備份虛擬機復用策略

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

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

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

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

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

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

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

1 虛擬機備份

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

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

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

2 單步啟發式策略

2.1 問題形式化

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

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

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

(1)

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

本文目的在于尋找最優策略π*,最大化有限時間區段或者無限時間區段的折現回報值為

(2)

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

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

備份VM經過分時復用后的利用率比只為高優先級VM提供備份時增加了,在決策時間長度T內,策略π產生的備份VM的利用率增量定義為

ind

丟失的回報值定義為

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

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

2.2 問題求解

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

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

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

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

(3)

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

通過Markov穩態方程計算出穩態情況下,備份VMj處于‘0’、‘1’的概率為

單步啟發式VM復用過程如下。

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

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

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

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

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

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

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

2.3 最優解條件

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

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

證畢。

2.4 復雜度分析

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

3 實驗結果

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

問題一 單步啟發式算法產生的調度方案效果。

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

圖1 regret的對數隨決策時間的變化曲線

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

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

問題二 當系統參量變化時,單步啟發式算法產生的效果變化。

在云系統中,軟件運行時的內外環境頻繁變動,本文主要探討了高優先級VM的失效率變化、失效模型類型變化、可感知的備份VM的數量變化對單步啟發式復用策略的影響。

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

表1 失效率及相應的模型參數

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

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

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

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

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

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

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

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

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

圖8 VM失效率為0.05時regret的對數與K之間的關系

圖9 VM失效率為0.2時regret的對數與K之間的關系

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

本實驗設定備份VM的數量N=500,可感知的備份VM的數量K=400,失效模型采用參數α=17、β=1的Weibull分布,恢復模型采用參數μ=1、δ=0.5的Lognormal分布,討論當次優先級VM在失效率為0.01、0.05、0.1、0.2時,備份VM可備份的次優先級VM的數量上限。圖10展示了失效VM的覆蓋率隨次優先級VM數量變化的曲線。以失效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,即使在次優先級VM頻繁失效的情況下,備份比例仍可以達到1∶4。在保證失效VM被100%覆蓋的情況下,單步啟發式策略仍可以在次優先級失效率較高時獲得1∶3的備份比。

圖10 失效VM的覆蓋率隨次優先級VM數量變化曲線

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

表2單步啟發式算法執行單步決策的運行時間ms

4 結 論

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

[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—),男,博士生;齊勇(通信作者),男,教授,博士生導師。 基金項目:國家自然科學基金資助項目(60933003)。

時間:2015-11-04

網絡出版地址:http:∥www.cnki.net/kcms/detail/61.1069.T.20151104.2222.002.html

10.7652/xjtuxb201601016

TP301

A

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