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

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

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

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

0 引言

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

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

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

1 基于Markov過(guò)程的可用性模型

1.1 模型的建立

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

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

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

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

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

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

1.2 PM分配子模型

1.2.1 hot PM分配子模型

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

其中：H23=。

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

1.2.2 warm PM分配子模型

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

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

1.2.3 cold PM分配子模型

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

其中：H12=。

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

圖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)概率方法對(duì)模型進(jìn)行求解，進(jìn)而在此基礎(chǔ)上對(duì)可用性進(jìn)行評(píng)估，避免了設(shè)定指標(biāo)權(quán)重系數(shù)的人為干擾。

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

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

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

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

在排序之后，可以利用現(xiàn)有的Markov 過(guò)程求解穩(wěn)態(tài)概率公式求解每一個(gè)狀態(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 仿真實(shí)驗(yàn)與結(jié)果分析

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

3.1 可用性評(píng)估指標(biāo)

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

1）至少存在一個(gè)可用PM的概率。

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

2）至少存在K個(gè)可用PM的概率。

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

3.2 結(jié)果與分析

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

表1 本文模型默認(rèn)取值Tab.1 Default values of proposed model

1）至少存在一個(gè)可用PM的概率。

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

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

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

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

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

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

2）至少存在K個(gè)可用PM的概率。

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

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

4 結(jié)語(yǔ)

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