陳 柳，周 偉

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

0 引言

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

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

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

(1)從錯(cuò)誤中恢復(fù);

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

狀態(tài)轉(zhuǎn)換協(xié)議的關(guān)鍵是有效地從其他正確復(fù)制品處獲得最新的狀態(tài)[9-10]，要達(dá)成此目標(biāo)需減少?gòu)钠渌麖?fù)制品處獲得的信息數(shù)量，減少對(duì)其他復(fù)制品的負(fù)擔(dān)。

1 算法描述

本文中最新的狀態(tài)[11-13]是指最新的穩(wěn)定檢查點(diǎn)的狀態(tài)，如果復(fù)制品不知道當(dāng)前最新的檢查點(diǎn)編號(hào)，本協(xié)議也能夠成功完成狀態(tài)更新。假設(shè)需要更新?tīng)顟B(tài)的復(fù)制品是ti，State Transfer協(xié)議過(guò)程詳述如下:

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

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

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

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

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

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

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

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

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

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

2 算法分析

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

表1 硬件平臺(tái)配置

進(jìn)行測(cè)試的軟件平臺(tái)配置如表2所示。

表2 軟件配置

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

圖1 State Transfer周期

圖2 狀態(tài)轉(zhuǎn)換周期對(duì)比

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

3 結(jié)束語(yǔ)

本文提出了一種適用于有狀態(tài)復(fù)制品的狀態(tài)轉(zhuǎn)換算法，適用于復(fù)制品能夠主動(dòng)改變自身狀態(tài)的拜占庭容錯(cuò)中的狀態(tài)恢復(fù)。在實(shí)驗(yàn)床上進(jìn)行了詳細(xì)的實(shí)驗(yàn)分析，結(jié)果驗(yàn)證了算法的有效性。

[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é)議構(gòu)建具有入侵容忍能力的Web服務(wù)研究[J].微電子學(xué)與計(jì)算機(jī)，2008，25(3):35-37.

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

[4]余發(fā)江，張煥國(guó).可信安全計(jì)算平臺(tái)的一種實(shí)現(xiàn)[J].武漢大學(xué)學(xué)報(bào):理學(xué)版，2004，50(1):69-73.

[5]張煥國(guó)，等，可信計(jì)算研究進(jìn)展[J].武漢大學(xué)學(xué)報(bào):理學(xué)版，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.