基于拜占庭容错的Checkpoint协议

周 伟，陈 柳，2

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

0 引言

随着电子商务［1-2］和基于Web应用的迅猛发展，越来越多的关键应用使用Web服务来构造，如支付网关、LBS［3-5］等。为了防止发生灾难性后果，在这些关键的分布式应用程序中进行错误容忍是必须的。目前研究者们对高可用系统的研究一般集中在良性错误，如服务器崩溃、拒绝服务攻击等，但缺乏对更为严重的恶意攻击的研究，譬如软件错误、错误操作、密钥丢失、服务器被黑客控制等。这种由恶意攻击引起的错误，被称为拜占庭错误［6-9］。由Web服务组成的分布式应用程序具有强自治、松耦合、多层架构、跨平台等特点，现有的拜占庭容错协议不再适用。本文根据Web服务的新特点，对适用于Web服务的拜占庭容错Checkpoint协议［10-11］展开研究，旨在为现有Web服务进行拜占庭容错提供支持。

本文根据Web服务的特点，设计一种拜占庭容错 Checkpoint协议［12-13］。Checkpoint协议在复制品中定期创建检查点，将复制品都认可的稳定状态保存，这些检查点可以在复制品进行状态转换［14-15］和前摄恢复时提供历史数据。与其他的拜占庭容错Checkpoint协议相比，该协议最大的改进在于允许Web服务改变自身的状态，这一点对于Web服务，尤其是组合服务尤其重要。

1 算法描述

Checkpoint协议的主要功能是设置一些检查点(Checkpoint)，检查点的ID以该检查点对应的请求编号命名，当前视图中检查点n被称为稳定的检查点的前提是，视图中至少2f+1(f是发生拜占庭错误的最大复制品数)复制品已经完成了编号小于n的所有请求。检查点n稳定后，复制品可以删除日志中所有小于n的消息，从而保证日志不会无限增长。

进行Checkpoint协议时，需要服务复制品进入静止状态，此状态下复制品停止从消息队列中取新的消息进行处理。设定复制品每从消息队列中取出K个消息后进入静止状态，进行Checkpoint协议，协议完成后，复制品重新开始从消息队列中获取消息进行处理。

检查点之间的间隔时间必须合理设置，如果设置过长，一旦复制品出错就会丢失很多的状态信息，如果设置过短，又会给系统增加过多的负担。设计Checkpoint协议时，设置K=Length/2，其中Length是复制品中消息队列的长度。

假设服务复制品的集合 T={t1，t2，…，tn}，每个复制品的抽象状态集合 S={s1，s2，…，sm}，这些抽象状态存放在磁盘对应的分区集合P={p1，p2，…，pm}中。

为了减少服务复制品之间发送消息的数量，协议指定一个复制品为Checkpoint协议的发起者，由它开始发送checkpoint消息。

Checkpoint协议过程描述如下:

Step1 服务复制品ti自上一个稳定的检查点后，执行了K个请求进入静止状态，准备建立新的稳定的检查点，并停止从消息队列中取新的消息进行处理。ti计算新检查点的编号n，n满足如下条件:

M是复制品消息队列中的消息编号集合，函数processed(i)判断消息mi是否被复制品处理了。

如果是返回值为true，否则为false。

如果消息队列中没有消息，n的值为复制品最后处理的消息的编号。

Step2 ti将当前的检查点n的状态信息存储到本地磁盘。

状态信息由以下部分组成:

(1)服务的抽象状态;

(2)请求者编号、请求的编号和结果。

服务的抽象状态 si存放在状态文件 n.ckp.si中，已经处理完毕的请求者编号、请求编号和结果存放在文件 n.ckp.resulti中。

计算每一个抽象状态si的状态文件n.ckp.si的摘要值 D(n.ckp.si)，将这些摘要值放入文件n.ckp.s中，并计算得到n.ckp.s的摘要值 ds，如图 1所示。

图1 计算服务的状态摘要

对保存的过往请求和结果摘要文件n.ckp.result计算其摘要值dres=D(n.ckp.result)。计算服务状态和过往计算结果的摘要值是为了快速比较2个服务的状态是否相同。

如果服务复制品ti是Checkpoint协议的发起者，ti计算出检查点n的状态摘要值后，向其他复制品广播发送checkpoint消息mchkptti=〈CHECKPOINT，v，n，ds，dres，ti〉σti。

发送checkpoint消息后，ti启动计时器。如果计时器到期，ti没有收到f+1个相同的checkpoint-response消息，将计时器的时间变为原来的2倍，再次发送checkpoint消息。

Step3 复制品tj在进入静止状态后，启动计时器。如果在计时器超时前，复制品tj收到Checkpoint协议的发起者ti发送的mchkptti=〈CHECKPOINT，v，n，ds，dres，ti〉σti消息，验证消息未被修改且来自于 ti后，就发送checkpoint-response消息mchkreptj=〈CHECK-RESPONSE，v，n'，d's，d'res，tj〉σtj给 ti，其中n'是tj准备建立的检查点序号，d's和d'res是n'对应的状态文件摘要。

如果计时器超时前，复制品tj未收到ti发送的mchkptti消息，tj向其他复制品广播发送 checkpoint消息mchkpttj=〈CHECKPOINT，v，n'，d's，d'res，tj〉σtj。Step4 如果复制品ti收到2f+1个具有相同〈v，n'，d's，d'res〉的 checkpoint-response 消息，说明检查点n'可以成为稳定的检查点。

如果 n=n'∧ds=d's∧dres=d'res，ti向其他复制品广播checkpoint-stable消息mchkstbti=〈CHECK-STABLE，v，n，ds，dres，ti〉σti，ti删除日志中消息编号小于n的所有消息，删除上一个稳定检查点的状态文件，退出静止状态，开始从消息队列中取新的消息进行处理，然后等待下一个检查点的到来，如图2所示。

图2 Checkpoint协议过程

如果 n=n'∧(ds≠d's∨dres≠d'res)，说明 ti处理消息的过程与其他复制品相同，但状态有缺失，需要调用State Transfer协议进行状态转换。

如果n＜n'，说明ti处理消息的进度落后于其他复制品，也需要进行State Transfer协议进行状态转换，使其与其他复制品的状态和进度相同。

如果n＞n'，说明ti处理消息的进度快于其他复制品，此时可以先不保存此检查点。

Step5 如果复制品tj收到checkpoint-stable消息mchkstbti=〈CHECK-STABLE，v，n，ds，dres，ti〉σti，验证该消息未被修改且来自于ti后，tj知道n成为稳定的检查点，删除日志中消息编号小于n的所有消息，删除上一个稳定检查点的状态文件。tj退出静止状态，开始从消息队列中取新的消息进行处理，然后等待下一个检查点的到来，转到 Step1重新开始的Checkpoint周期。

2 实验结果与分析

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

表1 硬件平台配置

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

表2 软件配置

Checkpoint各阶段所需要的平均时间、checkpoint消息、checkpoint-response消息和checkpoint-stable消息的大小相同，加密和解密的时间也取值相同，如表3所示。

表3 Checkpoint各阶段平均时间

Checkpoint协议的发起者ti完成Checkpoint协议所需总时间Tchk可由式(1)得到:

化简可得:

根据表3、式(1)和式(2)，可以计算出f=1，…，5时的预测的Checkpoint周期。

实验时，设置每个复制品消息队列长度Length=512，检查点之间的间隔k=Length/2=256。设置f=1，…，5，记录下 Checkpoint协议发起者 ti的 50次Checkpoint周期，计算其平均值，与预测的Checkpoint周期进行比较，如图3所示。

从图3可以看出，实际周期比预测值稍大，这是因为实际执行时复制品需要比较收到的〈v，n，ds，dres〉是否与自己的相同，这部分时间因为没法度量没有加到预测值中。

图3 Checkpoint周期

进行Checkpoint协议时，复制品需要进入静止状态，不会处理请求，这必然会降低系统的吞吐率。实验时设置复制品总数为3，复制品消息队列长度Length=512，检查点的间隔K值发生变化，记录下1000次请求的平均响应周期，如图4所示。

图4 K值变化时的平均响应周期

从图4可以看到，K值越小，系统的平均响应周期就越大。

3 结束语

本文根据Web服务的特点，提出了一种基于拜占庭容错的Checkpoint协议。该协议的主要功能是设置一些检查点和设置检查点之间的合理时间间隔值K，为恢复协议提供正确的时间点。

本文根据协议的过程，进行了理论分析，计算出协议整个过程所需要的周期，并与实验结果进行了比较，结果说明了协议的有效性。

［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］Microsoft Inc.Bing Maps Now Easier Than Ever［EB/OL］.http://www.microsoft.com/maps/，2011-03-01.

［3］Mastercard.MasterCard Payment Gateway Overview［EB/OL］.https://www.mastercardpaymentgateway.com/mpgpublic/welcome.do，2013-07-08.

［4］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.

［5］Leslie Lamport，Robert Shostak，Marshall Pease.The Byzantine generals problem［J］.ACM Transactions on Programming Languages and Systems，1982，4(3):382-401.

［6］Aghdaie N，Tamir Y.Implementation and evaluation of transparent fault-tolerant Web Service with kernel-level support［C］//Proceeding of the IEEE International Conference on Computer Communications.2002.

［7］Santos G T，Lung L C，Montez C.FTWeb:A fault tolerant infrastructure for Web services［C］//Proceeding of the 20059th IEEE International EDOC Enterprise Computing Conference(EDOC’05).Enscheda，Netherlands，2005:95-105.

［8］Ramakrishna Kotla，Allen Clement，Edmund Wong，et al.Zyzzyva:Speculative Byzantine fault tolerance［C］//Proceeding of the 21th ACM Symposium on Operating System Principles(SOSP).Stevenson，Washington，2007:45-58.

［9］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.2009:153-168.

［10］OASIS.Web Services Reliable Messaging［EB/OL］.http://docs.oasis-open.org/ws-rx/wsrm/200702，2009-02-02.

［11］孙周军，易锋，肖文名，等.基于拜占庭协议构建具有入侵容忍能力的Web服务研究［J］.微电子学与计算机，2008，25(3):35-37.

［12］王天锷，张大方，杨金民.基于代理的Byzantine一致性算法的研究［J］.计算机工程与科学，2005(4):57-59.

［13］余发江，张焕国.可信安全计算平台的一种实现［J］.武汉大学学报:理学版，2004，50(1):69-73.

［14］张焕国，罗捷，金刚，等.可信计算研究进展［J］.武汉大学学报:理学版，2006，52(5):513-518.

［15］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.