拜占庭容错中的状态转换算法研究

陈 柳，周 伟

(1.武汉工程大学电气信息学院，湖北 武汉 430073;2.华中师范大学计算机学院，湖北 武汉 430079)

0 引言

随着Internet越来越普遍的使用，以及企业和政府对网络服务的越来越严重的依赖，拜占庭错误[1-5]对企业和政府的损害也越来越严重。互联网不断开放的同时为恶意攻击提供了广阔的实施环境，软件系统不断复杂的同时伴随着不断增多的错误操作和软件错误。因此，建立一个能抵抗恶意攻击，能容拜占庭错误的系统是高可用系统研究的一个新挑战。

现有的拜占庭容错协议[1-5]不支持具有状态的主动服务，因此本文设计新的状态转移算法，该算法能够用于拜占庭容错中的复制品状态转移，且支持复制品具有状态。

在拜占庭容错协议[1-5]中，复制品tk出现以下情况时，使用状态转换协议[6]重建自己的状态。

(1)从错误中恢复;

(2)获知有新的稳定的检查点[7-8]，且检查点的编号大于自己日志中消息编号的上限。

状态转换协议的关键是有效地从其他正确复制品处获得最新的状态[9-10]，要达成此目标需减少从其他复制品处获得的信息数量，减少对其他复制品的负担。

1 算法描述

本文中最新的状态[11-13]是指最新的稳定检查点的状态，如果复制品不知道当前最新的检查点编号，本协议也能够成功完成状态更新。假设需要更新状态的复制品是ti，State Transfer协议过程详述如下:

Step1 复制品ti向其他复制品广播发送消息，其中 n 是要获取状态的检查点编号。如果ti不知道最新检查点编号，设置n=Ø。

Step2 复制品tj收到消息后判断n的值。如果n=Ø，tj向ti发送最新的稳定检查点ntj的摘要消息mptsttj=〈POSTSTATE，v，ntj，n.ckp.stj，n.ckp.resulttj，tj〉σti，其中 n.ckp.stj是复制品 tj在检查点 n 的状态文件，n.ckp.resulttj是tj在检查点n的以往结果摘要的文件。

如果n≠Ø且复制品tj最新的稳定检查点ntj=n，tj向ti发送 poststate消息 mptsttj=〈POSTSTATE，v，n，n.ckp.stj，n.ckp.resulttj，tj〉σti;如果 n≠Ø 且复制品tj最新的稳定检查点ntj＞n，tj向ti发送poststate消息mptsttj=〈POSTSTATE，v，n，n.ckp.stj，n.ckp.resulttj，tj〉σti。

如果n≠Ø且复制品tj最新的稳定检查点ntj＜n，说明复制品tj的状态也过时了，tj向ti发送poststate消息mptsttj=〈POSTSTATE，v，n，Ø，Ø，tj〉σti，ti收到状态文件为空的消息就知道tj的状态过时不能用了。同时 tj也需要进行 State Transfer协议，返回Step1。

Step3 复制品ti收到poststate消息后，从消息集合 M 中找出其中具有相同〈v，n，n.ckp.s，n.ckp.result〉的子集合 Mk，如果所有的|Mk|＜f+1，复制品ti返回Step1，重新广播发送getstate消息，直到收到至少f+1个具有相同的检查点编号和状态摘要文件的消息。

如果|Mk|≥f+1，则Mk中的n是视图v最新的检查点编号，n.ckp.s 和 n.ckp.result是最新的状态摘要文件。复制品 ti将文件 n.ckp.s和 n.ckp.result与自己的 n.ckp.sti和 n.ckp.resultti文件进行比较，找出其中不一样的状态和缺失的状态信息，将需要修改和补充的状态片段信息形成文件Gs和Gresult。

Step4 复制品tj收到消息mfcstti后判断n的值。如果tj最新的稳定检查点编号ntj＞n，说明在此期间tj形成了新的稳定检查点，tj重新向ti发送poststate消息，返回 Step3;如果 ntj=n，复制品 tj根据 Gs和Gresult的指引，从本地的状态信息中找出ti需要的状态片段，形成文件Ps和Presult。

最后复制品tj向ti发送fetch-response消息=〈FETCH-RESPONSE，v，n，Ps，Presult，tj〉σtj。

Step5 复制品ti收到fetch-response消息后，从消息集合 M 中找出其中具有相同〈v，n，Ps，Presult〉的子集合Mk，如果所有的|Mk|＜f+1，说明视图v出现了新的稳定检查点，复制品ti返回Step3，根据新收到的poststate消息确定最新的检查点编号。

如果|Mk|≥f+1，则ti根据Ps和 Presult更新自己的服务状态，至此状态转换结束。

2 算法分析

本节详细描述在所选择的软硬件环境下实现State Transfer算法后的测试结果，检验算法的效率，实验选择的硬件平台如表1所示。

表1 硬件平台配置

进行测试的软件平台配置如表2所示。

表2 软件配置

实验时设置错误复制品数f=1，不断重启一个复制品t1，迫使其开始状态转换过程。服务设计为顺序对若干page进行修改。图1显示的是t1重启后开始状态转换的周期，横轴是需要获取的状态元数据的个数。从图1中可以看出状态转换周期基本是随着需要获取的状态元数据个数线性增长。当元数据个数为400时，状态转换周期偏离了线性增长，这是因为t1进行状态转换时，出现了新的稳定的检查点，导致协议执行回归到前一阶段，增加了转换的时间。

图1 State Transfer周期

图2 状态转换周期对比

服务设计为顺序和随机对若干页面进行修改时所需要的时间是不同的。图2显示的是当进行状态转换时获取的状态元数据连续和随机时的状态转换周期的对比。从图2中可以看出当需要更新的元数据较少时，数据是否连续对t1的状态转换周期影响较明显，但是随着元数据的增加，这种影响逐渐减小。

3 结束语

本文提出了一种适用于有状态复制品的状态转换算法，适用于复制品能够主动改变自身状态的拜占庭容错中的状态恢复。在实验床上进行了详细的实验分析，结果验证了算法的有效性。

[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]孙周军，等.基于拜占庭协议构建具有入侵容忍能力的Web服务研究[J].微电子学与计算机，2008，25(3):35-37.

[3]王天锷，张大方，杨金民.基于代理的Byzantine一致性协议的研究[J].计算机工程与科学，2005，27(4):57-59.

[4]余发江，张焕国.可信安全计算平台的一种实现[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，Florida.2005:131-142.

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