劉艾俠

(寶雞職業(yè)技術(shù)學(xué)院 計算機系， 寶雞 721013)

云環(huán)境下節(jié)點失效檢測機制研究

劉艾俠

(寶雞職業(yè)技術(shù)學(xué)院 計算機系， 寶雞 721013)

針對云計算系統(tǒng)的可靠性問題，設(shè)計云環(huán)境下基于拜占庭容錯模型的節(jié)點失效檢測機制。當(dāng)云環(huán)境系統(tǒng)中發(fā)生節(jié)點失效或者節(jié)點超時，利用設(shè)計的拜占庭容錯算法，自動檢測出系統(tǒng)的失效節(jié)點并且隔離，提高系統(tǒng)的檢測精度。算法通過構(gòu)造節(jié)點矩陣檢測出失效節(jié)點。仿真實驗表明，該模型能夠有效的隔離云環(huán)境中失效節(jié)點和超時節(jié)點，大大提高了系統(tǒng)的可靠性。該模型還提供了反向恢復(fù)，當(dāng)所有節(jié)點通過拜占庭容錯模塊，若失效節(jié)點數(shù)大于總節(jié)點數(shù)的1/3，系統(tǒng)將反向恢復(fù)到輸入緩沖器。

云計算； 失效檢測； 容錯算法； 緩沖器

0 引言

云計算(cloud computing)是基于互聯(lián)網(wǎng)的相關(guān)服務(wù)的增加、使用和交付模式，具有資源共享的特性。在云環(huán)境下由于使用了大量廉價的服務(wù)器集群，節(jié)點失效不可避免。因此如何處理節(jié)點失效，提高云計算系統(tǒng)的容錯能力，是云計算學(xué)術(shù)研究中的一個熱點[1-2]。傳統(tǒng)的拜占庭算法有OM算法和SM算法，但是這些算法都是有前提條件[3]，像OM算法需要發(fā)令者將他的命令發(fā)給每一個副官并且每個副官采用他從發(fā)令者發(fā)來的命令，如果沒有收到任何命令，那么使用撤退命令。像SM算法需要忠誠將軍的簽名是不能偽造的，內(nèi)容修改可檢測并且每個人都可以分辨將軍的簽名，叛徒可以偽造叛徒司令的簽名[4]。文獻[5]中，為了保證應(yīng)用系統(tǒng)7×24的可用性，提出了ECA(Event Condition--Action)模式：通過持續(xù)監(jiān)視系統(tǒng)的異常行為，執(zhí)行所對應(yīng)容錯、調(diào)度操作。通過定位失效節(jié)點，方便系統(tǒng)運維人員準(zhǔn)確地了解系統(tǒng)行為，也能夠避免由于錯誤觸發(fā)相關(guān)容錯、調(diào)度機制給系統(tǒng)帶來的擾動。文獻[6]中，針對傳統(tǒng)拜占庭容錯算法Quorum算法存在的系統(tǒng)存儲空間利用率低的問題，提出了一種糾錯碼拜占庭容錯Quorum(Erasure-code Byzantine Fault-tolerance Quorum，E-BFQ)方法，通過采用糾錯碼來作為系統(tǒng)的冗余策略，可以提高系統(tǒng)的可靠性，且占用系統(tǒng)存儲空間更少。文獻[7]中，為提高無線Mesh網(wǎng)絡(luò)(WMN)的可靠性，構(gòu)建一個WMN拜占庭容錯網(wǎng)絡(luò)結(jié)構(gòu)，并提出一種拜占庭算法，用以改進現(xiàn)有WMN路由協(xié)議，能對異常節(jié)點信息進行容錯處理，增強網(wǎng)絡(luò)的容錯能力。

針對不同類型云計算節(jié)點失效的問題，本文設(shè)計一種基于拜占庭容錯模型的節(jié)點失效檢測機制。通過該模型，系統(tǒng)能夠自動檢測出失效節(jié)點并隔離，從而提高了系統(tǒng)的可靠性，具備更高的失效檢測精確度。在此基礎(chǔ)上提出基于該模型的節(jié)點失效檢測算法，最后通過仿真實驗驗證該算法的正確性和有效性。

1 拜占庭容錯模型設(shè)計

如圖1所示，在云計算系統(tǒng)中，設(shè)置M個節(jié)點(VM1,VM2,…,VMm)，每個節(jié)點從輸入緩沖器中獲取數(shù)據(jù)，拜占庭容錯模型(以下簡稱BFT模型)如圖1所示。拜占庭容錯模塊是負責(zé)對節(jié)點輸出結(jié)果進行拜占庭算法，防止失效節(jié)點對系統(tǒng)輸出的干擾。輸出結(jié)果通過時間計算模塊，時間計算模塊是用來計算每個非失效節(jié)點上進程的運行時間。在此基礎(chǔ)上，可靠性計算模塊負責(zé)計算每個節(jié)點的可靠性。然后，所有的結(jié)果都轉(zhuǎn)發(fā)到選擇模塊，選擇模塊用于選擇可靠性最高的結(jié)果。具有最高可靠性的結(jié)果就是系統(tǒng)的輸出結(jié)果。下面對BFT模型的每一個模塊進行描述。

圖1 BFT容錯模型

拜占庭容錯模塊(BFT)收集每個虛擬機發(fā)送的信息，通過設(shè)計的拜占庭算法，找出失效節(jié)點并且隔離，將正確結(jié)果輸出到時間計算模塊，如果節(jié)點是失效節(jié)點，其結(jié)果不通過時間計算模塊。

時間計算模塊(TC)是計算每個模塊產(chǎn)生輸出結(jié)果所需要的時間。TC模塊將結(jié)果傳遞給可靠性計算模塊，它只通過正確結(jié)果。如果某一節(jié)點的運行時間超過限定時間，該節(jié)點將不通過下一模塊進行可靠性計算。如果TC模塊限定時間太小，所有的節(jié)點不能產(chǎn)生結(jié)果，那么TC模塊進行反向恢復(fù)，恢復(fù)到輸入緩沖器，TC模塊提高自身的限定時間。

可靠性計算模塊(RC)負責(zé)評估每個節(jié)點的可靠性。在開始時，每個節(jié)點的可靠性假設(shè)為1。如果一個處理節(jié)點能夠在限定時間內(nèi)產(chǎn)生正確的結(jié)果，其可靠性會提高，未能在限定時間內(nèi)產(chǎn)生正確的結(jié)果，可靠性降低。系統(tǒng)設(shè)有一個最小和最大的可靠性水平，如果任何處理節(jié)點的可靠性低于最低可靠性水平或者大于最大可靠性水平，RC停止該節(jié)點的進一步工作，并隔離它。如果所有節(jié)點的可靠性低于最低可靠性水平或者大于最大可靠性水平，系統(tǒng)停止進一步工作，恢復(fù)到輸入緩沖器，重新設(shè)置最小最大可靠性水平。

選擇模塊(SM)選擇在一個計算周期內(nèi)具有最高可靠性的節(jié)點作為最終輸出。如果兩個節(jié)點具有相同的最高可靠性水平，那么具有較小的IP地址的節(jié)點被選定為輸出。設(shè)置一個系統(tǒng)可靠性水平(sl)，這是實現(xiàn)通過結(jié)果的最小可靠性水平。SM比較最佳的可靠性與sl的大小，最佳的可靠性水平應(yīng)大于或等于sl。如果沒有達到sl的值，執(zhí)行反向恢復(fù)，恢復(fù)到輸入緩沖器。在檢查點的幫助下向后進行。

BFT模型提供了一種自動向前恢復(fù)機制。如果一個節(jié)點不能產(chǎn)生輸出或時間超時，系統(tǒng)將不會失效，它在其余的節(jié)點上繼續(xù)運作。這種機制會產(chǎn)生輸出直到所有的節(jié)點都失效，恢復(fù)到初始位置。

2 節(jié)點失效檢測算法實現(xiàn)

在失效節(jié)點數(shù)小于m/3的前提下(m是云計算節(jié)點總數(shù))，設(shè)計了云環(huán)境下基于拜占庭容錯模型的節(jié)點失效檢測算法(以下簡稱BFT算法)。該算法在節(jié)點相互傳遞信息時，構(gòu)造了一維矩陣(m*1，m是節(jié)點數(shù))，然后將m個一維矩陣構(gòu)造成m*m的節(jié)點矩陣。通過對節(jié)點矩陣的列由少數(shù)服從多數(shù)判斷出是否有失效節(jié)點，有失效節(jié)點刪除。下面舉例四個節(jié)點中出現(xiàn)一個失效節(jié)點(方便模型的分析)，通過對拜占庭問題的研究，設(shè)計了一種矩陣算法，能夠?qū)菡纪煞N情況結(jié)合為一種算法，假設(shè)A、B、C、D是四個云計算中的節(jié)點，其中C節(jié)點失效，現(xiàn)在要檢測出C節(jié)點是失效節(jié)點，假設(shè)A發(fā)送1為正確消息，B發(fā)送2為正確消息，D發(fā)送4為正確消息，C向其它節(jié)點發(fā)送不同的錯誤消息，如圖2所示：

圖2 云環(huán)境下基于四個節(jié)點的拜占庭容錯模型原理

每個節(jié)點將自己的有效消息和收到其它的節(jié)點的消息，構(gòu)成一個4*1的一維消息矩陣，則A(1，2，x，4)，B(1，2，y，4)，C(1，2，3，4)，D(1，2，z，4)，可以看出C節(jié)點向其他3個節(jié)點發(fā)送了不一樣的數(shù)據(jù)，但是有效的節(jié)點還不能夠判定哪個節(jié)點發(fā)生了故障，因此每個節(jié)點將收到的一維信息矢量再發(fā)送給其他節(jié)點，如圖3所示：

圖3 云環(huán)境下基于四個節(jié)點的拜占庭矩陣算法原理

這樣每一個節(jié)點就會生成一個矩陣，如下所示：

最后，對矩陣的每一列進行選擇，每個節(jié)點按照少數(shù)服從多數(shù)的規(guī)則，如果節(jié)點矩陣的某一列中某一個數(shù)占多數(shù)(如矩陣A中第二列2最多，表示2為B正確消息)，那么我們選擇這個值作為正確的結(jié)果。如果某一列中沒有某個數(shù)占多數(shù)，則該列表為error，由此可以得到A、B、D三個節(jié)點為有效節(jié)點，C節(jié)點發(fā)生了故障，那么各個節(jié)點收到的消息為A(1，2，error，4)，B(1，2，error，4)，D(1，2，error，4)。在判斷C節(jié)點的時候，雖然沒有某個數(shù)占多數(shù)，但A、B、C三個節(jié)點判斷的數(shù)是一樣的，都是(x，y，z)，那么各個節(jié)點得出的結(jié)果也是一致的?？梢姡珹、B、D三個節(jié)點實現(xiàn)了協(xié)調(diào)容錯，得出了共同的正確結(jié)果。

該拜占庭矩陣容錯模型，通過構(gòu)造矩陣傳遞信息，可以準(zhǔn)確并且有效的檢測出失效節(jié)點的位置，大大提高了效率。

可靠性計算模塊(RC)算法是評估每個有效節(jié)點的可靠性。最初節(jié)點的可靠性被設(shè)置為1。該算法需要輸入三個變量:f，minR，maxR。f是一個可靠性因子，即增加或減少節(jié)點的可靠性。minR是最小可靠性水平，如果一個節(jié)點達不到這個水平，它被停止執(zhí)行進一步的操作。maxR是最大可靠性水平，節(jié)點的可靠性不能超過這一水平。變量的值(f，minR，maxR，sl)依賴于實時應(yīng)用，用戶決定每個變量的值。這些變量的計算不在此研究范圍中。

3 實驗測試

在CloudSim環(huán)境下，模擬云計算環(huán)境中的用戶、代理、資源信息服務(wù)等對象，用XML語言進行描述，并將所有的云計算模擬信息存放在config.xml配置文件中,在startEntity方法中調(diào)用擴展的拜占庭容錯等算法[7-8]。

設(shè)置環(huán)境變量[9]：reliability=1.000，f=0.3，sl=0.8，maxR=1.180，minR=0.940。創(chuàng)建虛擬機，在虛擬機上建立資源代理，仿真步驟如下[10]：初始化CloudSim庫、創(chuàng)建數(shù)據(jù)中心、創(chuàng)造代理Broker、創(chuàng)建虛擬機、創(chuàng)建云任務(wù)、調(diào)用算法、啟動仿真、結(jié)果統(tǒng)計。創(chuàng)建了4個節(jié)點，這是因為拜占庭問題的前提是失效節(jié)點數(shù)小于m/3(m是云計算節(jié)點總數(shù))，因此這里設(shè)置4個虛擬機，這樣當(dāng)有1個節(jié)點失效的時候，BFT模塊能夠通過算法找出失效節(jié)點并且隔離，這樣對后續(xù)的模塊計算可靠性不會產(chǎn)生失效。該實驗具有6個計算周期，在這個實驗中，我們有一個輸入緩沖器，該輸入緩沖器提供節(jié)點的輸入。BFT模塊收集每個虛擬機發(fā)送的信息，通過設(shè)計的拜占庭算法，找出失效節(jié)點，將正確結(jié)果輸出到TC模塊，如果某節(jié)點是失效節(jié)點，其結(jié)果不通過TC模塊。TC模塊檢查每個虛擬機結(jié)果的時效性，然后通過結(jié)果到可靠性計算模塊。RC計算三個模塊的可靠性后，將結(jié)果傳遞到選擇模塊SM，在所有的結(jié)果中選擇最佳的可靠性。

表1是節(jié)點1的實驗測試數(shù)據(jù)，如表1所示。

系統(tǒng)設(shè)置的各個節(jié)點初始的可靠性是1.000。在第1個周期后，節(jié)點1是有效節(jié)點，其可靠性增加了3%，為1.030。在第2個周期后，由于節(jié)點1運行超時，可靠性降低了3%，為0.999。第3個周期，由于拜占庭容錯算法，檢測出節(jié)點1為故障節(jié)點，節(jié)點可靠性降低，為0.969。第4個周期類似第2個周期，第5個周期類似于第3個周期的情況，第六個周期，節(jié)點1為有效節(jié)點，節(jié)點的可靠性增加到0.939。圖1是節(jié)點1在6個計算周期中可靠性的變化圖，其中在周期4,5,6中節(jié)點的可靠性低于系統(tǒng)設(shè)置的最小可靠性，如果最終它們是系統(tǒng)的輸出結(jié)果，不符合要求，那么系統(tǒng)將反向恢復(fù)，如圖4所示：

表1 節(jié)點1測試數(shù)據(jù)

圖4 節(jié)點1可靠性示意圖

表2是節(jié)點2的實驗測試數(shù)據(jù)，如表2所示。

表2 節(jié)點2測試數(shù)據(jù)

系統(tǒng)設(shè)置的各個節(jié)點初始的可靠性是1.000。其中在周期1,2,3中節(jié)點2都是有效節(jié)點，節(jié)點的可靠性依次增加3%。周期4節(jié)點超時，可靠性降低。在周期5中，節(jié)點2發(fā)生故障，可靠性降低。在第六個周期中，節(jié)點是有效節(jié)點，可靠性增加為1.059。圖2是節(jié)點2在6個計算周期中可靠性的變化圖，如圖5所示。

表3是節(jié)點3的實驗測試數(shù)據(jù)，如表3所示。

表4是節(jié)點4的實驗測試數(shù)據(jù)，如表4所示。

因為節(jié)點3和節(jié)點4在6個周期中都是有效節(jié)點并且沒有超時，所以它們的可靠性逐漸遞增，如圖6所示。

在第1個周期中，4個節(jié)點都是有效節(jié)點，通過RC模塊后，產(chǎn)生的可靠性都是1.030，由于VM4具有最小的IP，因此SM選擇最高可靠性節(jié)點VM4。在周期2中，VM1運行時間超過限定時間，但是不影響其他節(jié)點的正常運行，VM2、VM3、VM4的可靠性相等，SM選擇IP最小的節(jié)點VM4。

圖5 節(jié)點2可靠性示意圖

節(jié)點3測試數(shù)據(jù)周期限定時間BFTTCTimeR12500PassPass23381.03023700PassPass35991.06133000PassPass20841.09343800PassPass32561.12653200PassPass18921.16062800PassPass26531.195

表4 節(jié)點4測試數(shù)據(jù)

圖6 節(jié)點3和節(jié)點4可靠性示意圖

在周期3中，VM1失效，通過BFT模塊，能夠找出失效節(jié)點并且隔離，VM1不通過后續(xù)模塊，其余三個節(jié)點的可靠性相等，SM選擇IP最小的節(jié)點VM4。在周期4中,VM1和VM2都超時，但是不影響其他節(jié)點的正常運行,VM3、VM4的可靠性相等，SM選擇IP最小的節(jié)點VM4。在周期5中，VM1和VM2都失效，這個違背了拜占庭模型的前提，因此SM選擇的VM4是有問題的，這種情況不符合模型的理論依據(jù)，參照模型，系統(tǒng)執(zhí)行反向恢復(fù)，恢復(fù)到輸入緩沖器。在周期6中，4個節(jié)點都有效，且均為超過限定時間，但是最高可靠性是VM4的1.195，超過了maxR的1.180，系統(tǒng)執(zhí)行反向恢復(fù)，恢復(fù)到輸入緩沖器，重新設(shè)置maxR。

4 總結(jié)

與傳統(tǒng)的云計算系統(tǒng)模型相比，本文方法具有較高的節(jié)點失效檢測精度，并能夠有效屏蔽節(jié)點超時失效，從而提高了系統(tǒng)的容錯能力。本文設(shè)計的模型較以往的容錯模型具有以下幾處優(yōu)點：基于傳統(tǒng)的拜占庭算法，本文設(shè)計了拜占庭容錯算法沒有局限性，通過構(gòu)造矩陣的方式，化繁為簡，更具有普遍性和適用性；該模型具有反向恢復(fù)系統(tǒng)，當(dāng)系統(tǒng)的失效節(jié)點數(shù)超過總節(jié)點數(shù)的1/3，或者由于系統(tǒng)設(shè)置的參數(shù)導(dǎo)致系統(tǒng)未能找出最終輸出的最高可靠性的節(jié)點，系統(tǒng)可以反向恢復(fù)，重新設(shè)置參數(shù)，恢復(fù)系統(tǒng)，找出系統(tǒng)的最高可靠性。模型中加入這種機制，提高了系統(tǒng)的可靠性，當(dāng)系統(tǒng)出現(xiàn)超時節(jié)點過多或者節(jié)點可靠性過大過小，系統(tǒng)可以通過反向恢復(fù)，通過改變參數(shù)，重新正向執(zhí)行，找出系統(tǒng)的最高可靠性的節(jié)點。

[1] 鄒立新, 丁建立. 基于拜占庭協(xié)議的入侵容忍系統(tǒng)模型設(shè)計[J]. 計算機工程, 2005, 31(s1):88-90.

[2] 孫周軍, 易鋒, 肖文名,等. 基于拜占庭協(xié)議構(gòu)建具有入侵容忍能力的Web服務(wù)研究[J]. 微電子學(xué)與計算機, 2008, 25(3):35-37.

[3] 吳雄飚, 林建人, 進 王,等. 基于信任的IP網(wǎng)絡(luò)兩階段容錯容侵路由機制:, CN 101296181 A[P]. 2008.

[4] 齊平, 李龍澍, 李學(xué)俊. 具有失效恢復(fù)機制的云資源調(diào)度算法[J]. 浙江大學(xué)學(xué)報(工學(xué)版), 2015, 49(12):2305-2315.

[5] 田冠華, 孟丹, 詹劍鋒. 云計算環(huán)境下基于失效規(guī)則的資源動態(tài)提供策略[J]. 計算機學(xué)報, 2010, 33(10):1859-1872.

[6] 程仕偉, 潘郁. 云計算環(huán)境下基于可信性的動態(tài)資源分配策略[J]. 計算機工程, 2011, 37(11):45-48.

[7] 付小青, 沈劍. 能容納拜占庭錯誤的身份認證協(xié)議[J]. 華中科技大學(xué)學(xué)報(自然科學(xué)版), 2005, 33(5):22-25.

[8] 王吉喆, 趙蘊龍, 吳靜. WMN中拜占庭容錯網(wǎng)絡(luò)結(jié)構(gòu)及算法[J]. 計算機工程, 2011, 37(20):83-86.

[9] 陸正福, 晁巍. 具有長時安全性的高性能異或秘密共享協(xié)議的研究[J]. 云南大學(xué)學(xué)報:自然科學(xué)版, 2014(3):321-328.

[10] Liu Haijiao, Jing Jiwu, Lin Jingqiang,等. Building an Intrusion Tolerant Repository[J]. 中國科學(xué)院大學(xué)學(xué)報, 2006, 23(1):46-51.

[11] 荊繼武, 王晶, 林璟鏘,等. 基于門限簽名方案的BQS系統(tǒng)的服務(wù)器協(xié)議[J]. 軟件學(xué)報, 2010, 21(10):2631-2641.

Research of Node Failure Detection Mechanism in Cloud Environment

Liu Aixia

(Baoji Professional Technology Institute， Baoji 721013, China)

In view of the problem of reliability of cloud computing system, node failure detection mechanism based on Byzantine fault-tolerant model in cloud environment is designed. When the node failure or time-out occurs in cloud environment system, the designed Byzantine fault-tolerant algorithm is utilized to automatically detect and isolate system failure node, and improve the test accuracy. The failure node is detected by constructing node matrix. Simulation experiments show that the model can effectively isolate node failure or timeout in cloud environment, greatly improving the reliability of the system. The model also provides a reverse recovery. When all the nodes go through the Byzantine fault-tolerant module, if the failure node number is more than one third of the total number of nodes, the system will reverse back to the input buffer.

Cloud computing; Failure detection; Fault-tolerant algorithm; Buffer

劉艾俠(1982-)，女，陜西周至人，大學(xué)本科，講師，研究方向：計算機技術(shù)。

1007-757X(2017)05-0059-04

TP311

A

2016.11.20)