拜占庭容錯中的狀態(tài)轉換算法研究

陳 柳，周 偉

(1.武漢工程大學電氣信息學院，湖北 武漢 430073;2.華中師范大學計算機學院，湖北 武漢 430079)

0 引言

隨著Internet越來越普遍的使用，以及企業(yè)和政府對網絡服務的越來越嚴重的依賴，拜占庭錯誤[1-5]對企業(yè)和政府的損害也越來越嚴重。互聯(lián)網不斷開放的同時為惡意攻擊提供了廣闊的實施環(huán)境，軟件系統(tǒng)不斷復雜的同時伴隨著不斷增多的錯誤操作和軟件錯誤。因此，建立一個能抵抗惡意攻擊，能容拜占庭錯誤的系統(tǒng)是高可用系統(tǒng)研究的一個新挑戰(zhàn)。

現(xiàn)有的拜占庭容錯協(xié)議[1-5]不支持具有狀態(tài)的主動服務，因此本文設計新的狀態(tài)轉移算法，該算法能夠用于拜占庭容錯中的復制品狀態(tài)轉移，且支持復制品具有狀態(tài)。

在拜占庭容錯協(xié)議[1-5]中，復制品tk出現(xiàn)以下情況時，使用狀態(tài)轉換協(xié)議[6]重建自己的狀態(tài)。

(1)從錯誤中恢復;

(2)獲知有新的穩(wěn)定的檢查點[7-8]，且檢查點的編號大于自己日志中消息編號的上限。

狀態(tài)轉換協(xié)議的關鍵是有效地從其他正確復制品處獲得最新的狀態(tài)[9-10]，要達成此目標需減少從其他復制品處獲得的信息數(shù)量，減少對其他復制品的負擔。

1 算法描述

本文中最新的狀態(tài)[11-13]是指最新的穩(wěn)定檢查點的狀態(tài)，如果復制品不知道當前最新的檢查點編號，本協(xié)議也能夠成功完成狀態(tài)更新。假設需要更新狀態(tài)的復制品是ti，State Transfer協(xié)議過程詳述如下:

Step1 復制品ti向其他復制品廣播發(fā)送消息，其中 n 是要獲取狀態(tài)的檢查點編號。如果ti不知道最新檢查點編號，設置n=?。

Step2 復制品tj收到消息后判斷n的值。如果n=?，tj向ti發(fā)送最新的穩(wěn)定檢查點ntj的摘要消息mptsttj=〈POSTSTATE，v，ntj，n.ckp.stj，n.ckp.resulttj，tj〉σti，其中 n.ckp.stj是復制品 tj在檢查點 n 的狀態(tài)文件，n.ckp.resulttj是tj在檢查點n的以往結果摘要的文件。

如果n≠?且復制品tj最新的穩(wěn)定檢查點ntj=n，tj向ti發(fā)送 poststate消息 mptsttj=〈POSTSTATE，v，n，n.ckp.stj，n.ckp.resulttj，tj〉σti;如果 n≠? 且復制品tj最新的穩(wěn)定檢查點ntj＞n，tj向ti發(fā)送poststate消息mptsttj=〈POSTSTATE，v，n，n.ckp.stj，n.ckp.resulttj，tj〉σti。

如果n≠?且復制品tj最新的穩(wěn)定檢查點ntj＜n，說明復制品tj的狀態(tài)也過時了，tj向ti發(fā)送poststate消息mptsttj=〈POSTSTATE，v，n，?，?，tj〉σti，ti收到狀態(tài)文件為空的消息就知道tj的狀態(tài)過時不能用了。同時 tj也需要進行 State Transfer協(xié)議，返回Step1。

Step3 復制品ti收到poststate消息后，從消息集合 M 中找出其中具有相同〈v，n，n.ckp.s，n.ckp.result〉的子集合 Mk，如果所有的|Mk|＜f+1，復制品ti返回Step1，重新廣播發(fā)送getstate消息，直到收到至少f+1個具有相同的檢查點編號和狀態(tài)摘要文件的消息。

如果|Mk|≥f+1，則Mk中的n是視圖v最新的檢查點編號，n.ckp.s 和 n.ckp.result是最新的狀態(tài)摘要文件。復制品 ti將文件 n.ckp.s和 n.ckp.result與自己的 n.ckp.sti和 n.ckp.resultti文件進行比較，找出其中不一樣的狀態(tài)和缺失的狀態(tài)信息，將需要修改和補充的狀態(tài)片段信息形成文件Gs和Gresult。

Step4 復制品tj收到消息mfcstti后判斷n的值。如果tj最新的穩(wěn)定檢查點編號ntj＞n，說明在此期間tj形成了新的穩(wěn)定檢查點，tj重新向ti發(fā)送poststate消息，返回 Step3;如果 ntj=n，復制品 tj根據(jù) Gs和Gresult的指引，從本地的狀態(tài)信息中找出ti需要的狀態(tài)片段，形成文件Ps和Presult。

最后復制品tj向ti發(fā)送fetch-response消息=〈FETCH-RESPONSE，v，n，Ps，Presult，tj〉σtj。

Step5 復制品ti收到fetch-response消息后，從消息集合 M 中找出其中具有相同〈v，n，Ps，Presult〉的子集合Mk，如果所有的|Mk|＜f+1，說明視圖v出現(xiàn)了新的穩(wěn)定檢查點，復制品ti返回Step3，根據(jù)新收到的poststate消息確定最新的檢查點編號。

如果|Mk|≥f+1，則ti根據(jù)Ps和 Presult更新自己的服務狀態(tài)，至此狀態(tài)轉換結束。

2 算法分析

本節(jié)詳細描述在所選擇的軟硬件環(huán)境下實現(xiàn)State Transfer算法后的測試結果，檢驗算法的效率，實驗選擇的硬件平臺如表1所示。

表1 硬件平臺配置

進行測試的軟件平臺配置如表2所示。

表2 軟件配置

實驗時設置錯誤復制品數(shù)f=1，不斷重啟一個復制品t1，迫使其開始狀態(tài)轉換過程。服務設計為順序對若干page進行修改。圖1顯示的是t1重啟后開始狀態(tài)轉換的周期，橫軸是需要獲取的狀態(tài)元數(shù)據(jù)的個數(shù)。從圖1中可以看出狀態(tài)轉換周期基本是隨著需要獲取的狀態(tài)元數(shù)據(jù)個數(shù)線性增長。當元數(shù)據(jù)個數(shù)為400時，狀態(tài)轉換周期偏離了線性增長，這是因為t1進行狀態(tài)轉換時，出現(xiàn)了新的穩(wěn)定的檢查點，導致協(xié)議執(zhí)行回歸到前一階段，增加了轉換的時間。

圖1 State Transfer周期

圖2 狀態(tài)轉換周期對比

服務設計為順序和隨機對若干頁面進行修改時所需要的時間是不同的。圖2顯示的是當進行狀態(tài)轉換時獲取的狀態(tài)元數(shù)據(jù)連續(xù)和隨機時的狀態(tài)轉換周期的對比。從圖2中可以看出當需要更新的元數(shù)據(jù)較少時，數(shù)據(jù)是否連續(xù)對t1的狀態(tài)轉換周期影響較明顯，但是隨著元數(shù)據(jù)的增加，這種影響逐漸減小。

3 結束語

本文提出了一種適用于有狀態(tài)復制品的狀態(tài)轉換算法，適用于復制品能夠主動改變自身狀態(tài)的拜占庭容錯中的狀態(tài)恢復。在實驗床上進行了詳細的實驗分析，結果驗證了算法的有效性。

[1]Castro M，Liskov B.Byzantine fault tolerance can be fast[C]//International Conference on Dependable Systems and Networks.Redmond，WA，USA，2001:513-518.

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

[3]王天鍔，張大方，楊金民.基于代理的Byzantine一致性協(xié)議的研究[J].計算機工程與科學，2005，27(4):57-59.

[4]余發(fā)江，張煥國.可信安全計算平臺的一種實現(xiàn)[J].武漢大學學報:理學版，2004，50(1):69-73.

[5]張煥國，等，可信計算研究進展[J].武漢大學學報:理學版，2006，52(5):513-518.

[6]Zhao W.Byzantine fault tolerant coordination for Web services atomic transactions[C]//Proceedings of the 5th International Conference on Service-Oriented Computing.2007:307-318.

[7]Pallemulle S L，Thorvaldsson H D，Goldman K J.Byzantine fault-tolerant Web services for N-tier and service oriented architectures[C]//The 28th International Conference on Distributed Computing Systems.Washington，2008:260-268.

[8]Amir Y，et al.Byzantine replication under attack[C]//IEEE International Conference on Dependable Systems and Networks with FTCS and DCC.Charlottesville，Virginia，2008:197-206.

[9]Liu Ling-xia，Wu Zhao-xue，Qian Yuan，et al.Fault-tolerant Web services[J].Computer Science，2009，36(1):24-28.

[10]Allen Clement，Edmund Wong，Lorenzo Alvisi，et al.Making Byzantine fault tolerant systems tolerate Byzantine faults[C]//Proceedings of the 6th USENIX Symposium on Networked Systems Design and Implementation.2008:153-168.

[11]Zhao W，Zhang H.Proactive service migration for longrunning Byzantine fault-tolerant systems[J].IET Software，2009，3(2):154-164.

[12]Merideth M G，et al.Thema:Byzantine-fault-tolerant middleware for Web-service applications[C]//24th IEEE Symposium on Reliable Distributed Systems. Orlando，F(xiàn)lorida.2005:131-142.

[13]OASIS.Web Services Reliable Messaging[EB/OL].http://docs.oasis-open.org/ws-rx/wsrm/200702，2009-02-02.