基于Markov過程的IaaS系統(tǒng)可用性建模與分析方法

楊哂哂，吳慧珍，莊黎麗，呂宏武

（1.上海商學(xué)院網(wǎng)絡(luò)中心，上海 200235；2.哈爾濱工程大學(xué)計算機科學(xué)與技術(shù)學(xué)院，哈爾濱 150001）

（*通信作者電子郵箱lvhongwu@hrbeu.edu.cn）

0 引言

云計算（cloud computing）是一種典型的效應(yīng)計算模式，允許用戶像購買水電一樣以“按需使用的方式”采購計算服務(wù)，極大降低了計算密集型服務(wù)的成本［1］。美國國家技術(shù)標準與技術(shù)研究院（National Institute of Standards and Technology，NIST）將云計算劃分為三個層次，包括基礎(chǔ)設(shè)施即服務(wù)（Infrastructure as a Service，IaaS）、平臺即服務(wù)（Platform as a Service，PaaS）和軟件即服務(wù)（Software as a Service，SaaS）。其中IaaS 大多出租給基礎(chǔ)服務(wù)運營商（Infrastructure Service Provider，ISP），為終端用戶提供可以隨時部署操作系統(tǒng)和應(yīng)用的基礎(chǔ)計算環(huán)境；IaaS 的提供商一般和用戶簽署有服務(wù)等級協(xié)議（Service Level Agreements，SLA），主要規(guī)定了服務(wù)的可用性等級以及相應(yīng)的違約懲罰；IaaS 對服務(wù)的可用性具有更高要求，任何不可用的狀態(tài)都將對其商譽和收益帶來極大損失［2］。因此，高可用性對于IaaS具有更重要意義。

目前已經(jīng)有大量工作對IaaS 的可用性進行了研究，包括物理機器（Physical Machine，PM）排隊機制、虛擬機器（Virtual Machine，VM）遷移和異構(gòu)工作流影響等。文獻［3-4］重點研究了VM 遷移對可用性的影響，但是PM 對于IaaS 云系統(tǒng)可用性的影響更加基礎(chǔ)化。文獻［5-6］研究了基于容器的IaaS 的可用性，但是考慮到容器的安全隔離性問題還沒有得到全面解決，在可預(yù)見的將來并不能完全取代現(xiàn)有VM 方式。文獻［7］中分析了批量任務(wù)等異構(gòu)工作流對云計算系統(tǒng)可用性的影響，在此基礎(chǔ)上文獻［8-9］分別對不同的PM 分配策略進行了研究。與從任務(wù)流角度分析可用性不同，本文遵循文獻［4］僅關(guān)注于IaaS 系統(tǒng)對于任務(wù)處理的思路，屏蔽任務(wù)流的復(fù)雜性，這也是本領(lǐng)域絕大多數(shù)研究采用的方式。此外，其他大量研究還分析了VM 容量規(guī)劃［10］和關(guān)鍵影響因素分析［11］等問題。本領(lǐng)域的主要工作還集中在PM 隊列調(diào)度策略對可用性的影響，在文獻［12-15］中主要研究了不同PM 隊列調(diào)度策略對可用性的影響，但目前的研究主要分析至少存在一個VM可用的概率，不能分析存在任意N個VM 可用的情況，無法滿足批任務(wù)同時需要N個VM 時云計算系統(tǒng)服務(wù)可用性的分析。

據(jù)此，本文提出了一種IaaS系統(tǒng)可用性分析方法，通過建立IaaS 系統(tǒng)PM 分配的狀態(tài)轉(zhuǎn)移概率空間模型，描述PM 失效、恢復(fù)以及成功部署任務(wù)的概率，從而獲得系統(tǒng)處于可用狀態(tài)的穩(wěn)態(tài)概率。本文研究可以用于定量分析一個IaaS系統(tǒng)存在任意多個可用PM的概率。

1 基于Markov過程的可用性模型

1.1 模型的建立

IaaS系統(tǒng)規(guī)模巨大，能夠包含數(shù)以百萬計的計算節(jié)點，據(jù)相關(guān)報道其能耗相當于一個美國中型城市。為了節(jié)能通常將IaaS 計算節(jié)點分為hot PM、warm PM 和cold PM 三類。hot PM可以直接部署VM 并運行服務(wù)，部署時延極短；warm PM 又稱為hot standby PM，它處于熱待機狀態(tài)，在部署VM 之前有一定時延；cold PM 又稱為cold standby PM，PM通常處于關(guān)機狀態(tài)，需要較多時間部署VM。每一種PM 都會被組織成一個資源池，由系統(tǒng)進行調(diào)度。

為了簡化可用性建模，假設(shè)IaaS 可用性僅與計算資源的可用性相關(guān)，所有其他原因引發(fā)的不可用狀態(tài)都可以等價于計算資源的不可用。同時，由于IaaS 主要提供基礎(chǔ)設(shè)施給云服務(wù)提供商，因此關(guān)注的重點在于PM 的分配，且VM 部署的影響在其他文獻［2-3，7］中已有研究，本文不再作為重點。在此基礎(chǔ)上，對系統(tǒng)可用狀態(tài)的描述，將轉(zhuǎn)化為對PM 分配過程的建模。假設(shè)每次任務(wù)到達時，請求分配一個正常且可部署VM的PM，當需要分配多個VM 時等價于多次任務(wù)請求。上述三種PM 所處的狀態(tài)均可以分為三類：正常且可部署VM 的PM、失效PM 和正常已部署滿VM 的PM，于是系統(tǒng)狀態(tài)可以用當前時刻所有PM所處狀態(tài)來刻畫。

假設(shè)系統(tǒng)在時刻t的狀態(tài)為St，為了表述簡便當不指定特定時刻時簡記為：

其中：ξhot=(Nhot，Dhot，F(xiàn)hot)；ξhot各元素分別代表正常且可部署VM的PM數(shù)量、正常已部署滿VM的PM數(shù)量和失效PM數(shù)量。同理，ξwarm=(Nwarm，Dwarm，F(xiàn)warm)，ξcold=(Ncold，Dcold，F(xiàn)cold)。

本文借鑒現(xiàn)有IaaS 可用性模型［10，13］，建立一種基于Markov 過程的IaaS 可用性模型，按照PM 資源分配的三個階段分別對應(yīng)三種PM 分配子模型。三種PM 分配子模型分別用于描述hot PM、warm PM 和cold PM 資源池內(nèi)部的PM 調(diào)度，包含PM 的失效、VM 成功部署和釋放。IaaS 會優(yōu)先選擇hot PM 分配子模型，從hot PM 資源池中分配PM；若不存在則依次由warm PM 和cold PM 分配子模型查找剩余的兩個資源池，若仍然沒有可用的cold PM，則進入不可用狀態(tài)Unavail。當服務(wù)完成后，將PM 掛起，為了節(jié)省能源，優(yōu)先填補到低能耗的資源池中，且保持各資源池中PM 數(shù)量不變。三種子模型通過計算資源的轉(zhuǎn)換關(guān)系相協(xié)作，構(gòu)成系統(tǒng)整體模型，原理如圖1所示。

圖1 可用性模型的原理Fig.1 Schematic diagram of availability model

其中每一個子模型都對應(yīng)一個Markov 鏈，將在1.2 節(jié)中分別論述，由有限個Markov 鏈簡單組合而成的系統(tǒng)模型也是一個Markov 過程。而各子模型之間狀態(tài)轉(zhuǎn)移概率P1、P2、Q1、Q2可以通過各子模型的轉(zhuǎn)換關(guān)系求得。本文采用采用經(jīng)典的Lv 方法［8］計算狀態(tài)轉(zhuǎn)移概率，假設(shè)每個轉(zhuǎn)移動作的延遲都服從指數(shù)分布，轉(zhuǎn)移概率為動作時延的數(shù)學(xué)期望的倒數(shù)。

1.2 PM分配子模型

1.2.1 hot PM分配子模型

hot PM 子模型如圖2 所示。假設(shè)初始時刻ξhot=(h，0，0)，狀態(tài)之間的轉(zhuǎn)移分為橫向和斜向兩個部分，其中，橫向負責PM 資源的分配和釋放，斜向描述了PM 失效過程。IaaS 系統(tǒng)先判斷正要分配的hot PM 是否已經(jīng)失效，如果沒有失效，就正常分配PM，Dhot的數(shù)量就會增加。如果發(fā)現(xiàn)將分配的hot PM失效，那么進行斜向轉(zhuǎn)移，F(xiàn)hot的數(shù)量就會增加。由于ξwarm、ξcold在此過程中保持不變，系統(tǒng)初始狀態(tài)S可以記為一個分塊矩陣，

其中：H23=。

當最終不存在hot PM，將由整體模型控制轉(zhuǎn)入warm PM分配子模型。每一個warm PM 分配子模型可以用系統(tǒng)此時包含的hot PM 的狀態(tài)唯一標識，例如warm PM 分配子模型W(h-i，i)代表當有i個PM 已經(jīng)失效，其余（h-i）個hot VM 已分配完畢時轉(zhuǎn)入此子模型。

1.2.2 warm PM分配子模型

warm PM 分配子模型負責對warm PM 進行資源分配。不失一般性，以warm PM 分配子模型W(h-i，i)為例進行討論。記此時的ξhot狀態(tài)為H1=(0，h-i，i)。若warm PM 資源池中初始有w個PM，則起始狀態(tài)可以表示為：

其中：H3=ξcold，而H1和H3在狀態(tài)轉(zhuǎn)移過程中保持不變。warm PM 分配子模型W(h-i，i)的資源分配對應(yīng)的Markov 過程與hot PM 分配類似，如圖3 所示。當最終不存在hot PM，將由整體模型控制轉(zhuǎn)入cold PM 分配子模型。每一個cold PM 分配子模型可以用系統(tǒng)此時包含的hot PM 和warm PM 的狀態(tài)唯一標識。

1.2.3 cold PM分配子模型

cold PM 分配過程與hot PM 和cold PM 類似，也可以描述為一個Markov 鏈。不失一般性以標號為的cold PM分配子模型為例進行討論。在此子模型中，初始時刻ξhot=(0，h-i，i)，ξwarm=(0，w-j，j)，cold PM 資源池中初始有c個PM，則起始狀態(tài)可以表示為：

其中：H12=。

因此，cold PM 分配過程如圖4 所示，其中H12在此過程中保持不變。

圖2 hot PM分配子模型Fig.2 hot PM allocation sub-model

圖3 warm PM分配子模型W（h-i，i）Fig.3 warm PM allocation sub-model W（h-i，i）

圖4 cold PM分配子模型C（h-i，i；w-j，j）Fig.4 cold PM allocation sub-model C（h-i，i；w-j，j）

2 模型求解

本文采用穩(wěn)態(tài)概率方法對模型進行求解，進而在此基礎(chǔ)上對可用性進行評估，避免了設(shè)定指標權(quán)重系數(shù)的人為干擾。

首先，將系統(tǒng)所有狀態(tài)表示為一個向量。

若初始狀態(tài)hot PM、warm PM 和cold PM 的數(shù)量分別為h、c、w，由圖2～4 可以得到共有1 個hot PM 子模型，(h+1)個warm PM 子模型和(h+1) ×(w+1)個cold PM 子模型，則整個模型除了狀態(tài)Unavail共有狀態(tài)數(shù)量：

由式（1）可知，狀態(tài)S的任意一個矩陣SS可表示為：

為了表示的方便，將這些狀態(tài)按照矩陣S的所有元素Sij組成的向量(S11，S12，…，S33)的各元素數(shù)值依次由小到大排序，序號分別為1，2，…，Ntotal。

在排序之后，可以利用現(xiàn)有的Markov 過程求解穩(wěn)態(tài)概率公式求解每一個狀態(tài)的穩(wěn)態(tài)概率［4，7］。若πS代表狀態(tài)S的穩(wěn)態(tài)概率，所有πS和πUnavail組成穩(wěn)態(tài)概率向量Π=(π1，π2，…，πNtotal，πUnavail)，Q為一步狀態(tài)轉(zhuǎn)移概率矩陣，且Q=(quv)。其中Quv表示從狀態(tài)u到狀態(tài)v的轉(zhuǎn)移概率，u，v∈{1，2，…，Ntotal，Unavail}。則穩(wěn)態(tài)概率［4，7］可以用式（7）求解。

3 仿真實驗與結(jié)果分析

本章將通過實例驗證IaaS 可用性評估的有效性，主要是由于系統(tǒng)實測的可用性分析方法存在諸多限制：1）需要長期觀察云計算系統(tǒng)的運行狀況并記錄故障次數(shù)，涉及不同時間段、不同硬件主機和不同虛擬機的運行并進行大量統(tǒng)計；2）觀察周期很長，某些云系統(tǒng)的潛在故障發(fā)生周期甚至需要幾年；3）如果采用實驗仿真，需要人為定期注入故障進行觀察統(tǒng)計，這在某些商業(yè)云系統(tǒng)中很難被許可，觀察的數(shù)據(jù)也可能難以覆蓋實際故障集合。所以本文只是利用形式化方法針對提出的可用性模型進行驗證。

3.1 可用性評估指標

本文不但考慮了存在PM 可用的概率，即至少存在一個可用PM，而且為了滿足批量任務(wù)的部署需求，通常需要考察存在至少K個計算資源的概率PK。因此主要考察以下兩個指標。

1）至少存在一個可用PM的概率。

直接計算至少存在一個可用PM 的概率較為復(fù)雜，可以利用不存在可用PM的概率間接求解。

2）至少存在K個可用PM的概率。

其中：S 是指任意狀態(tài)；Nhot、Nwarm、Ncold是指處于狀態(tài)S時對應(yīng)的可部署的hot PM、warm PM和cold PM的數(shù)量。

3.2 結(jié)果與分析

本文采用的Markov 過程建模是一個理論模型，對于任意給定的目標系統(tǒng)，通過改變模型中的參數(shù)均可通過推導(dǎo)得到可用性的分析結(jié)果，實例不具有唯一性。因此可以任意選取一個私有云計算系統(tǒng)實例進行分析。假設(shè)該系統(tǒng)具有30 個hot PM 計算資源、20 個warm PM 計算資源和20 個Cold PM 的IaaS 系統(tǒng)。借鑒文獻［9-10］的參數(shù)設(shè)定，假定hot PM、warm PM 和cold PM 平均部署時延的數(shù)學(xué)期望分別為0.02 h、0.05 h 和0.2 h，PM 平均釋放時間均為0.2 h，故障時間間隔分別為100 h、200 h 和400 h。采用Huang 方法［8］得到系統(tǒng)默認參數(shù)如表1 所示。因為本文模型包含大量的參數(shù)，各個參數(shù)的取值都對可用性的分析有很大的影響，本文將對參數(shù)依次進行分析，來驗證各個參數(shù)的影響。為了簡化計算，提高求解效率，本文利用Eclipse Bio-PEPA Plugin工具包輔助求解。

表1 本文模型默認取值Tab.1 Default values of proposed model

1）至少存在一個可用PM的概率。

由式（8）可得當參數(shù)取值如表1 所示時，其中不可用狀態(tài)有21×21=441 個，可用性的值為0.955 2。當改變Nhot、Nwarm、Ncold的值時，得到Pavail的變化如圖5所示。

如圖5 可見，隨著hot PM、warm PM 和cold PM 數(shù)量的增長，可用性逐漸增加，并且cold PM 的趨勢更為陡峭。因為當cold PM 被調(diào)用時已經(jīng)沒有其他可用的資源，如果cold PM 不足將直接進入不可用狀態(tài)，因此cold PM 數(shù)量影響較大。對于Hot PM 和Warm PM 而言，當它們數(shù)量不足時，還可以繼續(xù)調(diào)用Cold PM，因此對最終進入不可用狀態(tài)的影響并不顯著。

圖5 PM數(shù)量對可用性的影響Fig.5 Impact of PM number on availability

當改變各關(guān)鍵參數(shù)λh、λw、λc、φh、φw、φc的值時，得到Pavail的變化如圖6所示。

圖6 PM的變遷速率對可用性的影響Fig.6 Impact of PM transition rate on availability

當λh、λw、λc等變遷速率加快時，可用性Pavail呈下降趨勢，原因主要是變遷速率加快等于單位時間內(nèi)需要部署PM數(shù)量增多，等價于負載壓力加大。因為在本實例中PM 數(shù)量較少，Pavail會逐漸降低，尤其是λc變遷速率加快時如果沒有充足的PM 將快速進入不可用狀態(tài)。此外還以PM 成功釋放的變遷速率為例分析了φh、φw、φc等關(guān)鍵參數(shù)對可用性的影響，隨著變遷速率的增長，單位時間內(nèi)有更多完成任務(wù)的PM 可供調(diào)度和部署任務(wù)，因此加快PM 的執(zhí)行速率有利于提升云計算系統(tǒng)的可用性，尤其是φc的影響更為明顯，因為根據(jù)調(diào)度關(guān)系沒有充足的cold PM 意味著直接進入不可用狀態(tài)，cold PM 執(zhí)行速率的提升等價于更多備用的PM 可用，降低了進入不可用狀態(tài)的概率。

2）至少存在K個可用PM的概率。

最終考察至少存在K個可用PM 的概率，以便可以部署超級任務(wù)或者批量任務(wù)。如圖7 可見，存在K個可用PM 的概率逐漸降低，即隨著同時需要的PM 數(shù)量的增加，PK的概率逐漸減小，原因在于PM 失效問題的存在以及部分PM 可能已經(jīng)被部署使得可用的PM 數(shù)量減少。因此應(yīng)該對批量任務(wù)一次性需要PM 的數(shù)量事先進行分析，以保證可以達到系統(tǒng)規(guī)定的可用性。

圖7 至少存在K個可用PM的概率Fig.7 Probability of existing at least K PM available

4 結(jié)語

針對現(xiàn)有IaaS 可用性模型難以分析多個可用PM 概率的問題，本文提出了一種基于Markov 過程的IaaS 系統(tǒng)可用性分析方法。結(jié)合PM 調(diào)度過程建立了可用性分析模型可以分析至少存在一個可用PM的概率以及至少存在K個可用PM的概率。實驗結(jié)果顯示增加PM 尤其是cold PM 的數(shù)量有助于提升可用性。本文的研究沒有考慮任務(wù)排隊帶來的影響，在后續(xù)的研究工作中，將結(jié)合任務(wù)排隊等更多影響因素分析云計算系統(tǒng)可用性的關(guān)鍵影響因素。