陳 曉，江建慧

（同濟大學軟件學院 上海 嘉定區(qū) 201804）

動態(tài)可配置的兩階段虛擬機容錯分配方法

陳 曉，江建慧

（同濟大學軟件學院 上海 嘉定區(qū) 201804）

提出了一種隨著虛擬機資源請求和應用程序可用性水平不斷變化的兩階段虛擬機容錯分配方法。第一階段根據(jù)虛擬機資源請求變化求解不同的虛擬機初始分配方案集合，第二階段通過虛擬機在線遷移與虛擬機熱備份技術，根據(jù)應用程序可用性水平不斷變化求解虛擬機容錯分配方案。實驗結果表明，與現(xiàn)有的方法相比，該文提出的兩階段虛擬機容錯分配方法性能更好，系統(tǒng)可用度更高。

可用度； 數(shù)據(jù)中心； 動態(tài)可配置； 虛擬機容錯分配； 兩階段算法

云計算系統(tǒng)結構包括組織層、統(tǒng)一資源層、平臺層與應用層［1］。虛擬化技術是云計算系統(tǒng)結構統(tǒng)一資源層中最關鍵的技術，可以提高主機的利用率，降低構建數(shù)據(jù)中心的成本。同時也會降低數(shù)據(jù)中心的可靠性，從2006年～2013年亞馬遜云計算服務（amazon web services， AWS）宕機數(shù)據(jù)統(tǒng)計分析可知，排名前三位的分別是電源、存儲以及虛擬機［2］。因此在數(shù)據(jù)中心服務器整合過程中，研究虛擬機管理的可靠性問題是當前的研究熱點。虛擬機容錯技術與數(shù)據(jù)中心服務器整合中虛擬機容錯分配技術也隨之被關注。

當前虛擬機容錯技術主要分為兩類：一類是將云計算系統(tǒng)失效節(jié)點上放置的虛擬機在線遷移到其他節(jié)點［3］。另一類是利用增量式檢查點思想，實現(xiàn)虛擬機熱備份系統(tǒng)，主機在運行過程中在一定的時間間隔內將修改后的數(shù)據(jù)同步到備份機［4-5］。

數(shù)據(jù)中心服務器整合主要分為虛擬機初始（靜態(tài)）分配［6］和虛擬機動態(tài)管理［7］。已有工作研究以可靠性為目的的虛擬機容錯分配問題。文獻［8］研究在虛擬機初始分配階段多種服務部署到不同的虛擬機時，怎樣找到最小的物理節(jié)點數(shù)量，同時保證系統(tǒng)能容忍多節(jié)點失效問題，但是未考慮在動態(tài)管理階段虛擬機分配方法。文獻［9］研究多個物理節(jié)點連續(xù)失效時虛擬機的分配序列，在任意時刻保證總有一定數(shù)量的虛擬機正常運行，但是未考慮虛擬機動態(tài)分配過程中新的約束引入。文獻［10］提出一種基于云計算應用組件排序的容錯框架，首先找出云計算應用的關鍵組件，然后對這些關鍵組件選擇合適的軟件容錯結構，提高云計算應用可靠性，但未考慮部署組件的虛擬機分配問題。文獻［11］研究基于約束編程（constraint programming， CP）的可配置的虛擬機分配方法，提出了14種可配置應用程序可用性要求的約束，但是該方法只考慮了基于虛擬機在線遷移的容錯結構，同時未考慮虛擬機初始分配對動態(tài)分配的影響。

為了解決上述問題，本文提出一種動態(tài)可配置的兩階段虛擬機容錯分配方法，不僅考慮虛擬機在線遷移，還考慮虛擬機熱備份，并提出一種基于CP的兩階段算法，研究虛擬機初始分配對動態(tài)可配置的虛擬機容錯分配的影響。

1 虛擬機容錯管理結構

1.1 系統(tǒng)結構

動態(tài)可配置虛擬機容錯分配管理結構構建在云計算系統(tǒng)統(tǒng)一資源層，如圖1所示。

圖1 動態(tài)可配置虛擬機容錯分配管理結構

統(tǒng)一資源層上由k個機架（rack）構成集群，第k個機架放置 nk個物理節(jié)點（node）。每個物理節(jié)點的操作系統(tǒng)之上是虛擬機管理器（virtual machine manager， VMM），其上放置的虛擬機有兩類，一類是提供服務的虛擬機，另一類是服務虛擬機對應的冗余虛擬機（virtual machine replication， VMRE）。監(jiān)控器負責接收VMM傳遞過來的數(shù)據(jù)，同時動態(tài)接收新的約束。全局控制器包含容錯模型求解器與模型管理器。模型管理器接收來自監(jiān)控器傳遞的數(shù)據(jù)和新的物理節(jié)點與虛擬機加入請求，并將這些數(shù)據(jù)按照容錯模型求解器需要的格式處理，然后周期性地傳遞給容錯模型求解器。容錯模型求解器求解虛擬機分配策略，并將其傳遞給容錯策略執(zhí)行器。容錯策略執(zhí)行器將容錯分配策略解析成VMM可執(zhí)行的指令，然后傳遞給需要再次分配虛擬機的物理節(jié)點上的VMM并執(zhí)行。

1.2 狀態(tài)遷移

虛擬機容錯分配策略是物理節(jié)點與虛擬機的一系列動作集合，這些動作使物理節(jié)點與虛擬機從一種狀態(tài)變成另一種狀態(tài)。

物理節(jié)點狀態(tài)比較簡單，共有運行（online）與關機（offline）兩種狀態(tài)，通過執(zhí)行關閉與啟動動作改變物理節(jié)點狀態(tài)，物理節(jié)點狀態(tài)遷移如圖2所示。

圖2 物理節(jié)點狀態(tài)遷移

圖3 虛擬機狀態(tài)遷移

虛擬機的狀態(tài)與操作系統(tǒng)進程的狀態(tài)較類似，根據(jù)虛擬機管理軟件（如Libvirt）對虛擬機定義狀態(tài)，共包含5個狀態(tài)，分別是：初始、就緒、運行、掛起與停機，虛擬機狀態(tài)遷移如圖3所示。設虛擬機動作集合A=｛Suspend， Launch， Migrate， Switch， Unmove，Close｝，分別表示虛擬機掛起、啟動、遷移［12］、切換［4］、保持不變以及關閉，時間開銷根據(jù)實際環(huán)境測定。

2 動態(tài)可配置虛擬機容錯分配模型

2.1 虛擬機容錯分配模型

根據(jù)圖1中監(jiān)控器反饋的數(shù)據(jù)，對那些分配條件發(fā)生變化的虛擬機，需要重新找出虛擬機行向量（V）與物理節(jié)點行向量（N）之間的映射關系，要求滿足虛擬機資源請求，模型求解目標是使重新分配所花費的時間開銷最小。為了求解該模型，將虛擬機容錯分配分成兩個階段，第一階段為虛擬機初始分配（virtual machine initial allocation， VMIA），第二階段為動態(tài)可配置虛擬機容錯分配（dynamic configurable virtual machine fault tolerance allocation，DCVMFTA）。

根據(jù)1.2小節(jié)虛擬機狀態(tài)遷移描述，可以將虛擬機的遷移動作看作從初始（initial）狀態(tài)到最終（final）狀態(tài)的遷移。設n表示物理節(jié)點數(shù)量、v表示虛擬機數(shù)量、p表示物理資源的種類（資源維度）；Ni表示物理節(jié)點i的p維資源向量，表示虛擬機j初始狀態(tài)對資源的需求，表示虛擬機j最終狀態(tài)對資源的需求；aj表示虛擬機j的執(zhí)行動作； dtj表示虛擬機j執(zhí)行狀態(tài)轉移動作t的時間，t∈A； ctj表示虛擬機j執(zhí)行狀態(tài)轉移動作t的時刻；wtj表示虛擬機j執(zhí)行狀態(tài)轉移動作t的權重（Unmove的權重為0，其他動作的權重均為1）；X表示已使用物理節(jié)點數(shù)量， xi表示若存在虛擬機放置在物理節(jié)點i，其值為1，否則為0。為了形式化描述兩階段問題，給出兩個定義。

定義 1 虛擬機行向量V與物理節(jié)點行向量N的映射函數(shù)為g，即g：V→N。

定義 2 四元組T=（V，gini（V），A，gfin（V））表示?虛擬機j∈V，初始被分配到物理節(jié)點 gini（j），然后經過執(zhí)行動作a∈A，最終被分配到物理節(jié)點gfin（j），這一執(zhí)行過程表示虛擬機在動態(tài)管理過程中的狀態(tài)轉移。

1） VMIA。VMIA主要研究V與N的映射方案，要求滿足虛擬機資源請求與物理節(jié)點的資源匹配限制條件，目標是使用的物理節(jié)點數(shù)量最少。式（1）給出VMIA問題的目標函數(shù)，即使用的物理節(jié)點數(shù)量最小。式（2）給出VMIA的約束條件，即放置在物理節(jié)點上的所有虛擬機每個維度的資源請求總和不能超過該物理節(jié)點所擁有的資源。

2） DCVMFTA。DCVMFTA主要研究在VMIA求解方案基礎上，隨著虛擬機分配條件的變化，求解V與N的再次映射方案。虛擬機分配條件發(fā)生變化主要有兩類情況：一類是隨著應用程序的變化，某些虛擬機對物理資源請求的增加或者減少；另一類是虛擬機可用性水平的動態(tài)配置。式（3）給出了求解DCVMFTA問題的目標函數(shù)，表示所有虛擬機的狀態(tài)遷移執(zhí)行動作的時間開銷之和最小。式（4）給出DCVMFTA的約束條件，表示任意時刻對任意虛擬機j∈V，在執(zhí)行狀態(tài)遷移動作之前時刻（l＜dtj+ctj）的資源請求與執(zhí)行狀態(tài)遷移動作之后時刻（l≥ctj）的資源請求之和小于放置之上的物理節(jié)點i所擁有的資源。其中，l表示任意時刻。

2.2 可配置虛擬機容錯分配描述

根據(jù)圖1可知，監(jiān)控器動態(tài)接收新的約束，這些約束主要為提高數(shù)據(jù)中心可靠性虛擬機與物理節(jié)點映射的約束規(guī)則。共有兩類約束，分別是分散（spread）與冗余（redundancy）。

1） Spread表示給定的虛擬機集合中任意兩個虛擬機不能放置在同一物理節(jié)點上，主要是為了防止單點故障而導致虛擬機與其對應的冗余虛擬機同時失效。Spread的描述為spread（V），其約束模型為：

2） Redundancy表示給定的虛擬機集合的冗余水平，主要是對提供關鍵服務的虛擬機進行冗余備份并同步。Redundancy的描述為redundancy（V，k），k為虛擬機冗余數(shù)量，一般k=2時，屬于虛擬機雙機熱備份，其約束模型如下：

2.3 系統(tǒng)可用度（availability）

虛擬機容錯分配系統(tǒng)周期性地對無法滿足需求的虛擬機進行再次分配，因此，可以量化動態(tài)可配置的虛擬機容錯分配系統(tǒng)的可用度［11］。完成一次虛擬機容錯分配所需要的時間為求解時間（Ts）與預測分配時間（Tr）之和，用（Ts+Tr）表示。定義系統(tǒng)平均修復時間（mean time to repair， MTTR）：MTTR=（Ts+Tr）×σ，σ表示需要重新分配的虛擬機比例。設虛擬機重新分配的時間周期為Tp，那么系統(tǒng)可用度A如式（7）所示，Tp一般取值為1小時。

3 基于CP的兩階段算法

由2.1節(jié)的描述可知，VMIA與DCVMFTA屬于約束滿足問題，因此可以用CP方法求解該類問題［9，11］。兩階段算法流程如圖4所示。第一階段基于CP方法求解VMIA問題，產生虛擬機分配方案X，然后進入第二階段循環(huán)選擇X并對DCVMFTA問題求解，輸出虛擬機容錯分配方案P。

圖4 兩階段算法流程

3.1 VMIA問題求解

基于CP方法求解VMIA問題一般需要搜索較大的解空間，因此求解時間非常大，為了減少算法搜索空間，可以采用等價類與上下界限定優(yōu)化方法。在VMIA問題求解中，等價虛擬機指任意兩個虛擬機的請求資源完全相同；等價物理節(jié)點指任意兩個物理節(jié)點所擁有的資源完全相同。

在VMIA問題求解中，所需物理節(jié)點數(shù)量的下界為大于所有虛擬機請求的每個維度資源總和除以對應的所有物理節(jié)點資源總和的最大值，設下界為那么

上界的選取規(guī)則為：若啟發(fā)式算法求解結果存在，則為上界，否則選擇虛擬機數(shù)量與物理節(jié)點數(shù)量的最小值，以降序首次適應（first fit descending，F(xiàn)FD）算法為例，Xffd為FFD算法求解結果，設上界為Xupper，有：

基于CP的VMIA問題求解步驟如下：

1） 初始化相關資源，包括N、V、Ni、Vjini、計數(shù)變量z以及迭代次數(shù)閾值Nmax；

2） 對物理節(jié)點向量N、虛擬機向量V按等價類方式從大到小排序，排序規(guī)則是按照內存、CPU資源依次從大到小，排序后物理節(jié)點向量Ν′、虛擬機向量V′；

3） 將VMIA問題約束轉換成CP約束，并設置搜索空間的上下界，即Xupper、Xlower，進入模型器求解；

4） 若找到可行解，則將其放入方案向量X，更新計數(shù)變量z=z+1；

5） 若z＜Nmax，則轉到步驟3），否則轉步驟6）；

6） 輸出分配方案集合X。

3.2 DCVMFTA問題求解

DCVMFTA問題是在VMIA問題的方案之上求解。DCVMFTA問題等價物理節(jié)點與VMIA問題相同，而等價虛擬機指對任意兩個虛擬機，它們在同一個物理節(jié)點上并且請求的資源完全相同。DCVMFTA問題求解的搜索空間上下界與VMIA問題相同?；贑P的DCVMFTA問題求解步驟如下：

1） 根據(jù)監(jiān)控器的數(shù)據(jù)獲取需要重新分配的虛擬機向量V，初始化虛擬機動作向量A、相應的時間 dtj，時間計數(shù)變量o=0、計算時間閾值 tmax，以及預測最優(yōu)分配時間Mbest=0；

2） 從方案X中選取未被選擇的方案x，若x存在，則轉步驟3）；否則，轉步驟6）；

3） 若o＜tmax，則將DCVMFTA問題約束轉換成CP約束；否則設置本次分配方案pl為空，轉步驟2）；

4） 運行基于CP的模型求解器，如果分配方案pl不存在，則轉步驟5），更新時間計數(shù)變量o=o+opl，opl為本次求解時間；否則，保存pl，更新Mbest，若Mbest＞Mpl，則Mbest=Mpl，重置o=0，轉步驟2）；

5） 擴充V，若V非全集，轉步驟3）；否則設置本次分配方案pl為空，轉步驟2）；

6） 輸出分配方案集合P與預測最優(yōu)分配方案執(zhí)行時間Mbest。

4 實驗與分析

本文在BtrPlace［11］基礎上實現(xiàn)了動態(tài)可配置的兩階段虛擬機容錯分配原型系統(tǒng)HABtrPlace。選取了基準程序RUBiS（rice university bidding system）［11］模擬真實云計算服務實例評估其性能，實例基于RUBiS負載的三層結構。模擬3 000～7 000個虛擬機在1 500個物理節(jié)點上動態(tài)可配置容錯分配過程，這些虛擬機對應的實例個數(shù)依次為174、233、295、335、402，比較FFDPlace［8］、BtrPlace與HABtrPlace，求解DCVMFTA問題的時間與系統(tǒng)可用度。

實驗求解的硬件配置為：CPU采用雙路E5-2620 V2，主頻： 2.1 GHZ，內存：32 GB，操作系系統(tǒng)：centos 6.4 x86_64，Java SDK版本1.8 update 5。

圖5給出了不同虛擬機容錯分配方法求解DCVMFTA問題的時間?？梢钥闯?，隨著待分配虛擬機數(shù)量增多，DCVMFTA問題求解時間增加，HABtrPlace求解時間最小，說明隨著求解問題規(guī)模增加，本文提出的方法具有更小的求解時間。

圖5 不同分配方法的DCVMFTA問題求解時間

圖6給出不同虛擬機容錯分配方法的系統(tǒng)可用度。從圖中可以看出，隨著待分配虛擬機數(shù)量的增多，基于HABtrPlace的虛擬機容錯分配方法可用度最高，說明隨著求解問題規(guī)模的增加，本文提出的虛擬機容錯分配方法具有更高系統(tǒng)可用度。同時，從圖中可知，系統(tǒng)可用度均在0.99以上，并且隨著待分配的虛擬機數(shù)量增加，系統(tǒng)可用度隨之下降，這是因為待分配的虛擬機數(shù)量越多，則求解時間與預測再次分配的執(zhí)行時間越大，系統(tǒng)可用度隨之下降。

圖6 不同虛擬機容錯分配方法的系統(tǒng)可用度

圖7給出VMIA問題求解方案對DCVMFTA問題求解時間影響。從圖中可以看出，隨著物理節(jié)點放置虛擬機數(shù)量限制增多，DCVMFTA問題求解時間反而下降，這是由于使用的物理節(jié)點越多，虛擬機在物理節(jié)點的放置越分散，隨著新的可靠性約束條件動態(tài)配置，需要再次分配的虛擬機數(shù)量會隨之減小。

圖7 VMIA對DCVMFTA問題求解時間影響

圖8給出VMIA問題求解方案對系統(tǒng)可用度影響，可看出，隨著物理節(jié)點放置虛擬機數(shù)量限制增多，系統(tǒng)可用度隨之增大，這是由于隨著使用的物理節(jié)點數(shù)量增多，DCVMFTA問題求解時間與預測執(zhí)行時間隨之減小，這樣系統(tǒng)可用度則隨之增大。

圖8 VMIA問題求解方案對系統(tǒng)可用度影響

從圖5～圖8的分析可知，本文提出的虛擬機容錯分配方法求解時間更小，系統(tǒng)可用度更高。同時，DCVMFTA問題求解時間與系統(tǒng)可用度不僅與問題規(guī)模相關，還受VMIA問題求解方案的影響。

5 結 束 語

針對數(shù)據(jù)中心服務器整合的可靠性問題，本文提出一種動態(tài)可配置的兩階段虛擬機容錯分配方法。隨著虛擬機請求資源和用戶對應用程序可用性水平的不斷變化，通過虛擬機在線遷移與虛擬機熱備份技術，構建了一種動態(tài)可配置的兩階段虛擬機容錯分配模型，提出了一種基于CP的兩階段算法求解該模型。實驗結果表明，與現(xiàn)有的方法相比，本文提出的方法求解時間更少，系統(tǒng)可用度更高。下一步研究工作考慮其他因素對虛擬機容錯分配的影響，例如，功耗、云計算系統(tǒng)服務等級合約等。

［1］ FOSTER I， YONG Z， RAICU I， et al. Cloud computing and grid computing 360-degree compared［C］//Proceedings of Grid Computing Environments Workshop. Austin， TX： IEEE，2008： 1-10.

［2］ CHEN Huai-lin. A qualitative and quantitative study onavailability of cloud computing［EB/OL］. ［2013-10-22］. http：//www.valleytalk.org/w p-content/uploads/2013/10/.

［3］ XU F， LIU F M， LIU L H， et al. iAware： Making live migration of virtual machines interference-aware in the cloud［J］. IEEE Transactions on Computers， 2014， 63（12）：012-3025.

［4］ BRENDAN C， GEOFFREY L， DUTCH M， et al. Remus：High availability via asynchronous virtual machine replication［C］//Proceedings of the 5th USENIX Symposium on Networked Systems Design and Implementation. San Francisco： USENIX Association， 2008： 161-174.

［5］ ZHU J， JIANG Z F， XIAO Z， et al. Optimizing the performance of virtual machine synchronization for fault tolerance［J］. IEEE Transactions on Computers， 2011， 60（12）：1718-1729.

［6］ WANG Y F， WANG X R. Virtual batching： Request batching for server energy conservation in virtualized data centers［J］. IEEE Transactions on Parallel and Distributed Systems，2013， 24（8）： 1695-1705.

［7］ XIAO Z， SONG W J， CHEN Q. Dynamic resource allocation using virtual machines for cloud computing environment［J］. IEEE Transactions on Parallel and Distributed Systems， 2013， 24（6）： 1107-1117.

［8］ MACHIDA F， KAWATO M， MAENO Y. Redundant virtual machine placement for fault-tolerant consolidated server clusters［C］//Proceedings of 2010 IEEE Network Operations and Management Symposium. Osaka： IEEE， 2010： 32-39.

［9］ BIN E， BIRAN O， BONI O， et al. Guaranteeing high availability goals for virtual machine placement［C］// Proceedings of the 31st International Conference on Distributed Computing Systems. Minneapolis： IEEE， 2011：700-709.

［10］ ZHENG Z B， ZHOU T C， LYU M R， et al. Component ranking for fault-tolerant cloud applications［J］. IEEE Transactions on Services Computing， 2012， 5（4）： 540-550.

［11］ HERMENIER F， LAWALL J， MULLER G. BtrPlace： a flexible consolidation manager for highly available applications［J］. IEEE Transactions on Dependable and Secure Computing， 2013， 10（5）： 273-286.

［12］ LIU H K， JIN H， XU C Z. Performance and energy modeling for live migration of virtual machines［C］// Proceedings of the 20th International Symposium on High Performance Distributed Computing. San Jose： IEEE， 2011：171-182.

編 輯 蔣 曉

A DynamFica Culot-nTfi oglu erraanbclee TAwllooc-Pathiaosne MViertthuoadl Machine

CHEN Xiao and JIANG Jian-hui
（School of Software Engineering， Tongji University Jiading Shanghai 201804）

A two-phase virtual machine （VM） fault-tolerance allocation method is proposed according to the constantly change of resources request of VMs and the availability levels of applications. In the first stage， the initial allocation plans of VMs are solved according to the change of resources request of VMs. In the second stage，through live migration of VMs technology and hot standby of VMs technology， the fault-tolerance allocation plan of VMs is solved according to the constantly change of the availability levels of applications. Experimental results demonstrate that the proposed method shows up better performance and higher availability compared with the existing methods.

availability； data center； dynamic configuration； fault-tolerance allocation of VMs；two-phase algorithm

TP302.8

A

10.3969/j.issn.1001-0548.2016.02.022

2015 - 02 - 11；

2015 - 10 - 27

國家自然科學基金重點項目（61432017）；國家自然科學基金青年項目（61404092）；江蘇省產學研聯(lián)合創(chuàng)新資金項目子課題（BY2013095-5-06）

陳曉（1987 - ），男，博士，主要從事容錯計算、軟件可靠性等方面的研究.