云環境下節點失效檢測機制研究

劉艾俠

(寶雞職業技術學院 計算機系， 寶雞 721013)

云環境下節點失效檢測機制研究

劉艾俠

(寶雞職業技術學院 計算機系， 寶雞 721013)

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

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

0 引言

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

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

1 拜占庭容錯模型設計

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

圖1 BFT容錯模型

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

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

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

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

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

2 節點失效檢測算法實現

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

圖2 云環境下基于四個節點的拜占庭容錯模型原理

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

圖3 云環境下基于四個節點的拜占庭矩陣算法原理

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

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

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

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

3 實驗測試

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

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

表1是節點1的實驗測試數據，如表1所示。

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

表1 節點1測試數據

圖4 節點1可靠性示意圖

表2是節點2的實驗測試數據，如表2所示。

表2 節點2測試數據

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

表3是節點3的實驗測試數據，如表3所示。

表4是節點4的實驗測試數據，如表4所示。

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

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

圖5 節點2可靠性示意圖

節點3測試數據周期限定時間BFTTCTimeR12500PassPass23381.03023700PassPass35991.06133000PassPass20841.09343800PassPass32561.12653200PassPass18921.16062800PassPass26531.195

表4 節點4測試數據

圖6 節點3和節點4可靠性示意圖

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

4 總結

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

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

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

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

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

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

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

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

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

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

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

[11] 荊繼武, 王晶, 林璟鏘,等. 基于門限簽名方案的BQS系統的服務器協議[J]. 軟件學報, 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-)，女，陜西周至人，大學本科，講師，研究方向：計算機技術。

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

TP311

A

2016.11.20)