2022-07-29 22:27 已编辑门头沟学院芯片研发

关注

实用的拜占庭容错

摘要

本文介绍了一种新的能够容忍拜占庭式故障的复制算法。我们相信，拜占庭容错算法在未来将变得越来越重要，因为恶意攻击和软件错误将越来越常见，并可能导致故障节点表现出任意行为。以前的算法假设是一个同步系统，或者在实践中使用太慢，而本文中描述的算法是实用的：它可以在互联网这样的异步环境中工作，并包含了几个重要的优化，可以将以前算法的响应时间提高一个数量级以上。我们使用我们的算法实现了一个拜占庭容错NFS服务，并测量了它的性能。结果显示，我们的服务只比标准的无复制NFS慢3%。

介绍

恶意攻击和软件错误越来越普遍。工业和政府对在线信息服务的日益依赖使恶意攻击更具吸引力，并使成功攻击的后果更加严重。此外，由于软件的规模和复杂性的增长，软件错误的数量也在增加。由于恶意攻击和软件错误会导致故障节点表现出拜占庭（即任意）行为，拜占庭容错算法变得越来越重要。

本文提出了一种新的、实用的状态机复制算法[17,34]，它可以容忍拜占庭故障。该算法提供了最多(n-1)/3个副本同时故障的有效性和安全性。这意味着客户最终会收到对他们请求的回复，并且这些回复根据线性化是正确的[14,4]。该算法在像互联网这样的异步系统中工作，它包含了重要的优化，使其能够有效地执行。

在容忍拜占庭错误（从[19]开始）的协议和复制技术方面有大量的工作。然而，大多数早期的工作（如[3,24,10]）要么关注旨在证明理论可行性的技术，但这些技术效率太低，无法在实践中使用，要么假设同步，即依赖于消息延迟和进程速度的已知边界。与我们最接近的系统Rampart[30]和SecureRing[16]被设计为实用的，但它们依赖于同步假设的正确性，这在恶意攻击的存在下是危险的。攻击者可能会延迟非故障节点或它们之间的通信，直到它们被标记为故障并从复制组中排除，从而危及服务的安全性。这样的拒绝服务攻击通常比获得对非故障节点的控制更容易。

我们的算法不容易受到这种类型的攻击，因为它不依赖于同步来保证安全。此外，它提高了Rampart和secuering的性能超过一个量级，如第7节解释。它只使用一次消息往返来执行只读操作，两次消息往返来执行读写操作。在正常运行时，采用基于消息认证码（MAC）的高效认证方案；公钥加密被认为是Rampart中主要的延迟[29]和吞吐量[22]瓶颈，它只在出现故障时使用。

为了评估我们的方法，我们实现了一个复制库，并使用它实现了一个真正的服务：一个支持NFS协议的拜占庭容错分布式文件系统。我们使用Andrew基准[15]来评估系统的性能。结果显示，在正常情况下，我们的系统只比Digital Unix内核中的标准NFS守护进程慢3%。

因此，本文的贡献如下：

它描述了第一个在异步网络中正确地经受拜占庭故障的状态机复制协议。
它描述了一些重要的优化，允许算法执行良好，以便它可以在实际系统中使用。
它描述了拜占庭容错分布式文件系统的实现。
提供了量化复制技术成本的实验结果。

本文的其余部分组织如下。我们从描述我们的系统模型开始，包括我们的失败假设。第三节描述了该算法所解决的问题，并给出了正确性条件。算法在第4节中描述，一些重要的优化在第5节中描述。第6节描述我们的复制库，以及我们如何使用它来实现拜占庭容错NFS。第7节介绍了我们的实验结果。第8节讨论了相关工作。最后对所取得的成果进行了总结，并对未来的研究方向进行了讨论。

系统模型

我们假设一个异步的分布式系统，其中节点通过网络连接。网络可能会导致消息传递失败、延迟、重放（复制）或乱序传递。

我们使用拜占庭失效模型，即故障节点可以任意行为，只受下面提到的限制。我们假设独立的节点故障。为了使这个假设在存在恶意攻击时成立，需要采取一些步骤，例如，每个节点应该运行不同的服务代码和操作系统的实现，并且应该有不同的根密码和不同的管理员。可以从相同的代码库[28]获得不同的实现，对于低复制程度，可以从不同的供应商购买操作系统。n版本编程，即不同的程序员团队产生不同的实现，是某些服务的另一种选择。

我们使用加密技术来防止欺骗和重放，并检测损坏的消息。我们的消息包含公钥签名[33]，消息认证码[36]，以及由抗冲突哈希函数[32]产生的消息摘要。我们将节点i签名的消息m表示为 $<m>_{\sigma_{i}}$ ，消息m的摘要表示为D(m)。我们遵循的惯例是签署消息摘要并将其附加到消息的明文中，而不是签署整个消息（ $<m>_{\sigma_{i}}$ ，应该这样解释）。所有副本都知道其他副本的公钥以验证签名。

我们允许一个非常强大的对手协调故障节点、延迟通信或延迟正确的节点，以便对复制的服务造成最大的损害。我们确实假设对手不能无限期地延迟正确的节点。我们还假设对手（以及它控制的故障节点）是计算绑定的，因此（有很高的概率）它无法破坏上面提到的加密技术。例如，对手无法为没有故障的节点生成有效签名，无法从摘要中计算摘要汇总的信息，也无法找到具有相同摘要的两条消息。我们使用的密码技术被认为具有这些特性[33,36,32]。

服务属性

我们的算法可以用于实现任何具有状态和一些操作的确定性复制服务。这些操作并不局限于对服务状态的某些部分进行简单的读写；它们可以使用状态和操作参数执行任意的确定性计算。客户端向复制的服务发出请求以调用操作并阻塞等待应答。复制服务由副本实现。如果客户端和副本遵循第4节中的算法，并且没有攻击者可以伪造他们的签名，那么它们就没有错误。

该算法在保证不超过(n-1)/3个副本故障的前提下，保证了安全性和活动性。安全性意味着复制服务满足线性化[14]（修改为考虑到拜占庭错误的客户端[4]）：它的行为就像一个集中实现，每次原子地执行一个操作。安全要求有错误副本数量的限制，因为错误副本的行为可以是任意的，例如，它可以破坏自己的状态。

无论有多少错误的客户端正在使用服务（即使它们与错误的副本勾结），安全性都是提供的：错误的客户端执行的所有操作都被非错误的客户端以一致的方式观察。特别是，如果服务操作被设计为保留服务状态上的一些不变量，则有故障的客户机不能破坏这些不变量。

安全属性不足以防范错误的客户端，例如，在一个文件系统中，错误的客户端可以将垃圾数据写入一些共享文件。但是，我们通过提供访问控制来限制有故障的客户机可能造成的损害：如果发出请求的客户机没有调用操作的权限，我们就对客户机进行身份验证并拒绝访问。另外，服务可能提供更改客户机访问权限的操作。由于该算法确保所有客户机都能一致地观察访问撤销操作的影响，因此它提供了一种强大的机制来从故障客户机的攻击中恢复。

该算法不依赖于同步来提供安全性。因此，它必须依靠同步来提供活力；否则，它可以用于在异步系统中实现共识，这是不可能的[9]。我们保证存活性，也就是说，如果最多(n-1)/3个副本是错误的，并且延迟的增长速度不会比无限快，那么客户端最终会收到对其请求的回复。这里，延迟是指从消息第一次发送到目的地接收到消息之间的时间（假设发送方不断重传消息，直到消息被接收到）。（在[4]中可以找到更精确的定义。）这是一个相当弱的同步假设，只要网络故障最终得到修复，它在任何真实系统中都可能是正确的，但它使我们能够规避[9]中不可能的结果。

我们算法的弹性是最优的：3f+1是允许异步系统在多达f个副本故障时提供安全性和活性属性的最小副本数量（参见[2]的证明）。之所以需要这么多副本，是因为必须能够在与n-f副本通信后继续进行，因为f副本可能出现故障且没有响应。但是，有可能f个没有响应的副本没有故障，因此，响应的副本中有f个可能是故障的。即便如此，仍然必须有足够的响应，使非错误副本的响应数超过错误副本的响应数，即n-2f>f。因此n>3f。

该算法没有解决容错隐私的问题：一个错误的副本可能会泄露信息给攻击者。在一般情况下，提供容错隐私是不可行的，因为服务操作可能使用它们的参数和服务状态执行任意计算；副本需要清楚地知道这些信息，以便高效地执行这些操作。即使存在对服务操作不透明的参数和状态部分的恶意副本[13]阈值，也可以使用秘密共享方案[35]来获取隐私。我们计划在未来研究这些技术。

我们的算法是状态机复制的一种形式[17,34]：服务被建模为一个状态机，在分布式系统的不同节点上复制。每个状态机副本维护服务状态并实现服务操作。我们用R表示副本的集合，并在{0,...,|R|-1}中用一个整数来标识每个副本。为了简单起见，我们假设R=3f+1，其中f是可能出错的副本的最大数量；尽管可能有超过3f+1个副本，但是额外的副本会降低性能（因为正在交换更多更大的消息），而不能提供更好的弹性。

副本在一系列称为视图的配置中移动。在视图中，一个副本是主副本，其他副本是备份副本。视图按顺序编号。一个视图的主视图是副本p，使p = v mod |R|，其中v为视图号。当主服务器出现故障时，将执行视图更改。Viewstamped Replication[26]和Paxos[18]使用了类似的方法来容忍良性故障（如第8节中讨论的那样）。

该算法的工作原理大致如下：

客户端向主服务器发送调用服务操作的请求
主服务器将请求多播给备份服务器
副本执行请求并向客户端发送应答
客户端等待1个来自不同副本的相同结果的回复；这是操作的结果。

与所有状态机复制技术[34]一样，我们对副本提出了两个要求：它们必须是确定性的（即，在给定的状态和给定的参数集中执行操作必须始终产生相同的结果），并且它们必须在相同的状态中启动。考虑到这两个需求，该算法通过确保所有非错误副本在失败的情况下对请求执行的总顺序达成一致来确保安全属性。

本节的其余部分将描述该算法的简化版本。我们省略了关于节点如何从由于空间不足而导致的故障中恢复的讨论。我们还省略了与消息重发相关的细节。此外，我们假设消息认证是使用数字签名实现的，而不是基于消息认证码的更有效的方案；第5节进一步讨论了这个问题。在[4]中使用I/O自动机模型[21]对该算法进行了详细的形式化描述。

客户端

客户端c通过向主服务器发送 $<REQUEST,o,t,c>_{\sigma_{c}}$ 消息来请求执行状态机操作o。时间戳t用于确保客户端请求执行的精确的一次语义。c请求的时间戳是完全有序的，这样以后的请求的时间戳就比以前的请求的时间戳要高；例如，时间戳可以是发出请求时客户端的本地时钟值。

副本发送给客户端的每条消息都包含当前视图号，允许客户端跟踪视图，从而跟踪当前主视图。客户端使用点对点消息向它认为是当前主服务器的对象发送请求。主服务器使用下一节描述的协议原子地将请求多播给所有备份。

副本直接向客户端发送对请求的应答。回复的形式为 $<REPLY,v,t,c,i,r>_{\sigma_{i}}$ ，其中v是当前视图号，t是相应请求的时间戳，i是副本号，r是执行请求操作的结果。

客户端等待来自不同副本的f+1个具有有效签名的回复，并且t和r是相同的，然后才接受结果r。这确保了结果是有效的，因为最多可以有f个副本出错。

如果客户机没有很快收到响应，它将把请求广播给所有副本。如果请求已经被处理，副本只需重新发送应答;副本会记住它们发送给每个客户机的最后一条回复消息。否则，如果副本不是主服务器，它会将请求转发给主服务器。如果主服务器没有将请求多播到组，那么它最终会被足够多的副本怀疑是错误的，从而导致视图更改。

在本文中，我们假设客户端在发送下一个请求之前等待一个请求完成。但是我们可以允许客户端发出异步请求，同时保留它们的排序约束。

通常情况下操作

每个副本的状态包括服务的状态、一个包含该副本已接受消息的消息日志，以及一个表示该副本当前视图的整数。我们在4.3节中描述了如何截断日志。

当主服务器p接收到客户端请求m时，它启动一个三阶段协议，以原子方式将请求多播到副本。主服务器立即启动协议，除非正在进行协议的消息数量超过给定的最大值。在本例中，它缓冲了请求。缓冲请求稍后作为一个组播，以减少消息流量和CPU开销的沉重负载；这种优化类似于事务系统[11]中的组提交。为了简单起见，我们在下面的描述中忽略此优化。

这三个阶段分别是准备、准备和执行。预准备和准备阶段用于对在同一视图中发送的请求进行完全排序，即使提出请求排序的主节点出现故障。准备和提交阶段用于确保提交的请求跨视图完全有序。

在预准备阶段，主服务器向请求分配一个序列号n，向所有备份组广播一个带m的预准备消息，并将消息添加到其日志中。消息的形式为 $<<PRE-PREPARE,v,n,d>_{\sigma_{p}},m>$ ，其中v表示消息发送的视图，m是客户端的请求消息，d是m的摘要。

请求不包含在预先准备的消息中，以保持其小。这很重要，因为预准备消息被用作在视图更改中为请求分配了视图序号的证明。此外，它将协议与将请求传输到副本的协议解耦，使请求完全有序；允许我们对协议消息使用针对小消息优化的传输，对大请求使用针对大消息优化的传输。

备份接收提供的预准备消息：

请求和预准备消息中的签名是正确的，d是m的摘要；
它在视图v中；
它没有接受视图v和序列号n包含不同摘要的预准备消息；
预准备消息中的序列号介于低水位h和高水位H之间。

最后一个条件通过选择一个非常大的序列号来防止错误的主元耗尽序列号空间。我们将在4.3节中讨论H和h如何前进。

如果备份i接受了 $<<PRE-PREPARE,v,n,d>_{\sigma_{p}},m>$ 消息，它进入准备阶段，向所有其他副本组播一个 $<PREPARE,v,n,d,i>_{\sigma_{i}}$ 消息，并将这两个消息添加到它的日志中。否则，它什么也不做。

一个副本（包括主副本）接受准备消息并将它们添加到日志中，前提是它们的签名正确，它们的视图号等于副本当前的视图号，并且它们的序列号在h和H之间。

我们定义断言prepared(m,v,n,i)为真，如果且仅当副本i插入到它的日志中：请求m，视图v中为m准备的一个序列号为n的预准备，以及2f从不同的备份中匹配预准备。副本通过检查准备文件是否具有相同的视图、序号和摘要来验证准备文件是否与准备文件相匹配。

算法的预准备和准备阶段保证非错误副本对视图中请求的总顺序达成一致。更准确地说，它们确保以下不变量：如果prepared(m,u,n,i)为真，那么对于任何没有错误的副本j（包括i=j）和任何m'(D(m')≠D(m))，prepared(m',v,n,j)为假。这是正确的，因为准备好的(m,v,n,i)和R=3f+1意味着至少f+1个非错误的副本已经发送了一个预先准备好的或准备好的m在视图v中，序列号为n。因此，为了准备好的(m,v,n,j)是正确的，至少一个这些副本需要发送两个冲突的准备（或预准备，如果它是v的主准备），即两个准备具有相同的视图和序列号和不同的摘要。但这是不可能的，因为副本没有故障。最后，我们对消息摘要强度的假设确保了m≠m'和D(m)=D(m')的概率可以忽略不计。

副本i在 $prepared(m,v,n,i)$ 为真时向其他副本发送一个 $(COMMIT,v,n,D(m),i)_{\sigma_{i}}$ 。这将开始提交阶段。副本接受提交消息，并将它们插入到日志中，前提是它们被正确签名，消息中的视图号等于副本的当前视图，序号在h和H之间。

我们定义了committed和committed-local断言如下：committed(m, u,n)当且仅当准备(m,v,n,i)对于某个集合+1的非错误副本中的所有i为真；并且committed-local(m,v,n,i)为真，当且仅当prepared(m,v,n,i)为真，并且我已经接受了来自不同副本的2f+1个提交（可能包括它自己的），这些副本匹配pre-prepare for m；如果commit和pre-prepare具有相同的视图、序号和摘要，commit和pre-prepare就匹配。

提交阶段确保以下不变：如果committ-local(m,v,n,i)对于某些非故障i为真，那么committed(m,u,n)为真。这个不变量和4.4节中描述的视图变更协议确保非错误副本在本地提交请求的序列号上一致，即使它们在每个副本上提交了不同的视图。此外，它确保任何在本地非错误副本提交的请求最终将在f+1或更多非错误副本提交。

每个副本i在提交后执行m请求的操作——local(m,v,n,i)为真，i的状态反映了所有较低序列号的请求的顺序执行。这确保了所有非错误副本按照提供安全属性所需的相同顺序执行请求。在执行请求的操作之后，副本向客户端发送一个应答。副本会丢弃那些时间戳低于上次发送给客户端的响应时间戳的请求，以保证精确一次的语义。

我们不依赖于有序的消息传递，因此副本有可能乱序提交请求。这无关紧要，因为它会记录预准备、准备和提交消息，直到可以执行相应的请求。

图1展示了该算法在正常情况下无主故障时的运行情况。副本0是主副本，副本3故障，C是客户端。

垃圾收集

本节讨论用于从日志中丢弃消息的机制。为了保证安全，消息必须保存在副本的日志中，直到它知道他们关心的请求已经被至少f+1个非错误副本执行，并且它可以在视图更改时向其他副本证明这一点。此外，如果某些副本错过了所有非故障副本所丢弃的消息，则需要通过传输全部或部分服务状态来更新该副本。因此，副本还需要一些证据来证明国家是正确的。

在执行每一个操作后生成这些证明将是昂贵的。相反，它们是周期性地生成的，当执行一个序列号可以被某个常数（例如，100）整除的请求时。我们将把执行这些请求产生的状态称为检查点，我们会说一个有证明的检查点是一个稳定的检查点。

一个副本维护服务状态的几个逻辑副本：最后一个稳定检查点，零个或多个不稳定的检查点，以及一个当前状态。可以使用写时复制技术来减少存储状态额外副本的空间开销，如第6.3节所述。

检查点的正确性证明如下所示。当一个副本i产生一个检查点时，它向其他副本发送一条消息< checkpoint, n, d,i).;，其中n是最后一个请求的序列号，它的执行反映在状态中，d是状态摘要。每个副本在它的日志中收集检查点消息，直到它有2f+1个序列号n的相同摘要d由不同的副本签名（可能包括它自己的这样的消息）。这两个2f+1消息是检查点正确性的证明。

一个具有证明的检查点变得稳定，副本从其日志中丢弃所有序列号小于或等于n的pre-prepare、prepare和commit消息；它还丢弃所有较早的检查点和检查点消息。

计算证明是有效的，因为可以使用增量密码学[1]（如第6.3节所讨论的）来计算摘要，而且很少生成证明。

检查点协议用于提高低水位和高水位标记（这限制了将被接受的消息）。低水位标记h等于最后一个稳定检查点的序列数。高水位标志H=h+k，其中k足够大，所以副本不会停滞等待检查点变得稳定。例如，如果检查点每100个请求使用一次，那么k可能是200。

视图的变化

视图更改协议允许系统在主服务器失败时继续工作，从而提供活动性。视图更改是由防止备份无限期等待请求执行的超时触发的。备份正在等待一个请求，如果它收到一个有效的请求，但没有执行它。当备份接收到一个未运行的请求时，启动一个计时器。当它不再等待执行请求时，它会停止计时器，但如果此时它正在等待执行其他请求，则会重新启动计时器。

如果视图v中备份i的定时器到期，备份将启动视图更改，将系统移动到视图v+1。它停止接收消息（checkpoint,view-change和new-view消息除外），并向所有副本组播（view-change,0+1,n,C,P,i）消息。这里n是最后稳定的序列号检查点年代我，C是一组2f+1有效检查点信息证明的正确性的年代，和P是一组包含一组点为每个请求m，准备我的序列数高于n。每一组点包含一个有效的预先加工信息（没有相应的客户端消息）和2f匹配，有效准备签署消息不同的备份相同的观，序列号和m的消化。

当视图u+1的主节点p从其他副本接收到视图v+1的2f条有效的视图变更消息时，它会向所有其他副本发送一条 $(NEW-VIEW,v+1,V,O)_{\sigma_{P}}$ 消息，其中包含了主节点接收到的有效的视图变更消息加上主节点已经发送（或将要发送）的v+1的视图变更消息，并且是一组预先准备的消息（没有附带请求）。O的计算方法如下：

主节点确定在v中准备消息中最新的稳定检查点的序号min-s和最高的序号max-s。
主节点为视图v+1为min-s和max-s之间的每个序列号n创建一个新的预准备消息。有两种情况：（1）在V中某个视图改变消息的P分量中至少有一个序列号为n的集合；（2）没有这样的集合。在第一种情况下，主进程创建了一个新的消息 $<PRE-PREPARE,v+1,n,d>_{\sigma_{p}}$ ，其中d是预准备消息中的请求摘要，在V中视图编号最高的序列编号为n。在第二种情况下，它创建了一个新的预准备消息 $<PRE-PREPARE,v+1,n,d^{null}>_{\sigma_{p}}$ ，其中d^null是一个特殊的null请求的摘要，一个空请求像其他请求一样通过协议，但它的执行是无操作的。（Paxos[18]使用了类似的技术来填补空白。）

接下来，主节点将消息追加到它的日志中。如果min-s大于其最新的稳定检查点的序列号，主服务器也会在其日志中插入带有min-s序列号的检查点的稳定性证明，并像4.3节中讨论的那样丢弃日志中的信息。然后它进入视图v+1：此时它能够接受视图v+1的消息。

如果正确签名，如果备份包含的视图更改消息对视图v+1有效，并且集合O正确，则备份接收视图v+1的新视图消息；它通过执行类似于主节点创建O的计算来验证O的正确性，然后按照主节点的描述将新信息添加到日志中，向所有其他副本广播O中的每个消息的准备，将这些准备添加到它的日志中，并进入视图v+1。

之后，协议按照第4.2节的描述继续进行。副本在min-s和max-s之间重做消息协议，但它们避免重新执行客户端请求（通过使用它们存储的关于发送给每个客户端的最后一个应答的信息）。

一个副本可能丢失一些请求消息m或一个稳定检查点（因为这些不会在新视图消息中发送）。它可以从另一个副本获得缺失的信息。例如，副本i可以从V中检查点消息认证其正确性的副本中获得丢失的检查点状态s。由于这些副本中的f+1是正确的，副本i将总是获得s或稍后认证的稳定检查点状态s。我们可以通过对状态进行分区并使用最后一个修改它的请求的序列号标记每个分区，从而避免发送整个检查点。要使副本更新，只需要向它发送过期的分区，而不是整个检查点。

正确性

本节简要证明了算法的安全性和有效性；详细信息可以在[4]中找到。

安全性

如前所述，如果所有非故障副本对本地提交的请求的序列号达成一致，则该算法将提供安全性。

在第4.2节中，我们证明了如果prepared(m,v,n,i)为真，对于任何没有错误的副本j（包括i = j）和任意m'(D(m')≠D(m))， prepared(m'，v,n, j)为假。这意味着两个非错误副本在本地同一视图中提交的请求的序列数是一致的。

视图更改协议确保非错误副本也同意在不同副本的不同视图中本地提交的请求的序列数。只有当committed(m,v,n)为真时，请求m才会提交到视图v中序列号为n的非故障副本上。这意味着有一个集合R₁包含至少f+1个非错误副本，这样准备的(m,v,n,i)对于集合中的每个副本i都为真。

如果没有收到v'的新视图消息，非错误副本将不会接受视图v'>v的预准备（因为只有在那个时候它们才进入视图）。但是对于视图u'>v，任何正确的新视图消息都包含了来自(2f +1)副本集合R2中每个副本i的正确视图更改消息。因为有3f+1个副本，R必须在至少一个没有故障的副本k中相交。k的视图更改消息将确保m在前一个视图中准备的事实传播到后续视图，除非新视图消息中包含一个稳定检查点的视图更改消息，且序列号大于n。在第一种情况下，算法对具有相同序列号n和新视图号的m重做原子组播协议的三个阶段。这是很重要的，因为它可以防止任何在前一个视图中被分配了序号n的不同请求被提交。在第二种情况下，新视图中的副本将不会接受任何序列号低于n的消息。在两种情况下，副本将同意本地提交的序列号为n的请求。

活性

为了提供活性，副本在无法执行请求时必须移动到一个新的视图。但是，当至少有2f+1个无故障副本在同一个视图中时，最大化这段时间是很重要的，并确保这段时间呈指数增长，直到执行某些请求的操作。我们通过三种方式来实现这些目标。

第一，避免从一个视图变化太快，一个副本,多播视图更改消息视图v+1等待2f+1视图更改消息视图v+1，然后开始其计时器过期一段时间T后，如果计时器到期之前接收到一个有效的新视图消息v+1或在它执行一个请求之前没有执行之前的新视图,它开始视图改变视图v+2但这一次它将等待2T开始前一个视图改变视图v+3。

第二，如果一个副本从其他副本那里收到了比它当前视图大的f+1个有效的视图更改消息，它就发送一个视图更改消息给这个集合中最小的视图，即使它的定时器还没有过期；这可以防止它太晚开始下一次视图更改。

第三，错误的副本无法通过频繁更改视图来阻碍进程。一个错误的副本不能通过发送view-change消息来引起视图更改，因为视图更改只有在至少f+1个副本发送view-change消息时才会发生，但当它是主副本时（通过不发送消息或发送坏消息）可以引起视图更改。但是，因为视图v的主视图是副本p，p=v mod |R|，所以主视图不能连续故障超过f个视图。

这三种技术保证了活动，除非消息延迟的增长速度永远快于超时周期，而这在实际系统中是不可能的。

非确定性

状态机副本必须是确定性的，但许多服务涉及某种形式的非确定性。例如，NFS中的time-last-modified是通过读取服务器的本地时钟来设置的；如果在每个副本上独立执行此操作，那么非错误副本的状态将会发散。因此，需要某种机制来确保所有副本选择相同的值。通常，客户端无法选择该值，因为它没有足够的信息;例如，它不知道它的请求相对于其他客户机的并发请求将如何排序。相反，主服务器需要独立地或根据备份提供的值选择该值。

如果主节点独立选择不确定的值，它将该值与关联的请求连接起来，并执行三个阶段协议，以确保非错误副本对请求和值的序列号达成一致。这可以防止一个故障的主服务器通过向不同的副本发送不同的值而导致副本状态的偏离。但是，出错的主服务器可能会向所有副本发送相同的、不正确的值。因此，副本必须能够仅根据服务状态确定该值是否正确（如果不正确，应该如何处理）。

此协议对于大多数服务（包括NFS）来说足够了，但偶尔必须由副本参与选择值以满足服务的规范。这可以通过向协议添加一个额外的阶段来完成:主节点获取备份提议的经过身份验证的值，将其中的2f+1与关联的请求连接起来，并为连接的消息启动三个阶段的协议。副本通过对2f+1值及其状态的确定性计算来选择值，例如，取中值。在一般情况下，多余的阶段可以被优化掉。例如，如果副本需要一个“与本地时钟足够接近3”的值，那么当它们的时钟在一些增量内同步时，可以避免额外的相位。

优化

本节将介绍一些改进算法在正常情况下的性能的优化。所有的优化都保持了活性和安全性。

减少通信

我们使用三个优化来降低通信成本。第一种方法避免发送大部分大型回复。客户端请求指定一个副本来发送结果；所有其他副本发送只包含结果摘要的回复。摘要允许客户端检查结果的正确性，同时对于大量响应显著减少了网络带宽消耗和CPU开销。如果客户端没有从指定的副本接收到正确的结果，它像往常一样重新传输请求，请求所有副本发送完整的应答。

第二个优化将操作调用的消息延迟数量从5减少到4。一旦准备好的断言保存了请求，副本就试探性地执行请求，它们的状态反映了所有序列号较低的请求的执行，并且已知这些请求都已提交。执行请求后，副本向客户端发送试探性的响应。客户端等待2f+1个匹配的试探性回复。如果它接收到如此多的请求，则保证最终提交请求。否则，客户端重新传输请求并等待f+1个非试探性的应答。

一个暂时执行的请求可能会中止，如果有一个视图更改，它被一个空请求取代。在这种情况下，副本将其状态还原为new-view消息中的最后一个稳定检查点或最后一个检查点状态（取决于哪个具有更高的序列号）。

第三个优化改进了不修改服务状态的只读操作的性能。客户端向所有副本广播一个只读请求。副本在检查请求是否通过了正确的身份验证、客户端是否具有访问权限以及请求实际上是只读的之后，会在试探性状态下立即执行请求。他们只在所有反映在试探性状态的请求都提交后才发送回复；这对于防止客户端观察未提交状态是必要的。客户端等待来自不同副本的2f+1响应，得到相同的结果。如果并发写入影响结果的数据，客户端可能无法收集2f+1这样的响应；在这种情况下，它在重传计时器过期后将请求作为普通的读写请求重新传输。

密码学

在第4节中，我们描述了使用数字签名对所有消息进行身份验证的算法。然而，我们实际上只对很少发送的视图更改和新视图消息使用数字签名，并使用消息身份验证码（MACs）对所有其他消息进行身份验证。这消除了以前系统中的主要性能瓶颈[29,22]。

然而，相对于数字签名，MAC有一个基本的限制——无法证明消息对第三方是真实的。第4节中的算法和之前用于状态机复制的拜占庭容错算法[31,16]依赖于数字签名的额外能力。通过利用特定的不变量，我们修改了算法来规避这个问题，例如，不变量：在两个没有错误的副本上，没有两个不同的请求准备相同的视图和序列号。改进后的算法在[5]中进行了描述。这里我们概述一下使用MACs的主要含义。

MACs的计算速度比数字签名快三个数量级。例如，200MHz的Pentium Pro需要43ms生成MD5摘要的1024位模RSA签名，0.6ms验证签名[37]，而在我们的实现中，在相同的硬件上计算64字节消息的MAC只需要10.3s。还有其他的公钥密码系统生成签名的速度更快，例如椭圆曲线公钥密码系统，但是签名验证的速度较慢[37]，在我们的算法中，每个签名都要验证多次。

每个节点（包括活动客户端）与每个副本共享一个16字节的秘密会话密钥。我们通过对消息与密钥的连接应用MD5来计算消息认证码。与使用最终MD5摘要的16个字节不同，我们只使用最不重要的10个字节。这种截断具有明显的优势，可以减少MACs的大小，并提高MACs对某些[27]攻击的弹性。这是秘密后缀方法[36]的一种变体，只要MD5是抗碰撞的[27,8]，它就是安全的。

回复消息中的数字签名将被单个MAC取代，这已经足够了，因为这些消息只有一个目标接收方。所有其他消息（包括客户端请求，但不包括视图更改）中的签名都被我们称为身份验证器的MACs向量所取代。除了发送方，验证方对每个副本都有一个表项;每个表项都是用发送方共享的密钥和对应于该表项的副本计算出来的MAC。

验证验证器的时间是恒定的，但生成验证器的时间会随着副本的数量线性增长。这不是问题，因为我们不希望有大量的副本，而且MAC和数字签名计算之间存在巨大的性能差距。此外，我们可以高效地计算验证器；对消息应用MD5一次，通过对相应的会话密钥应用MD5，得到的上下文用于计算每个向量条目。例如，在一个有37个副本的系统中（即一个可以容忍12个同时故障的系统），验证器的计算速度仍然比1024位模数RSA签名快两个数量级以上。

验证器的大小随着副本的数量线性增长，但增长缓慢：它等于30×(n-1)/3字节。在n≤13的情况下（即系统可以容忍4个同时发生的故障），验证器比RSA签名更小，其模量为1024位，这在大多数配置中都是正确的。

实现

本节描述我们的实现。首先我们讨论复制库，它可以用作任何复制服务的基础。在第6.2节中，我们描述了如何在复制库之上实现一个复制的NFS。然后，我们描述如何有效地维护检查点和计算检查点摘要。

复制库

复制库的客户端接口由一个单独的过程（调用，带一个参数）和一个包含调用状态机操作请求的输入缓冲区组成。调用过程使用我们的协议在副本上执行所请求的操作，并从各个副本的应答中选择正确的应答。它返回一个指向包含操作结果的缓冲区的指针。

在服务器端，复制代码对应用程序的服务器部分必须实现的过程进行多次向上调用。有一些过程用于执行请求（execute）、维护服务状态的检查点（创建检查点、删除检查点）、获取指定检查点的摘要（获取摘要）和获取缺失的信息（获取检查点、设置检查点）。执行过程接收一个包含所请求操作的缓冲区作为输入，执行操作，并将结果放置在输出缓冲区中。其他程序将在第6.3和6.4节中进一步讨论。

节点之间的点对点通信使用UDP实现，到副本组的组播使用UDP通过IP组播[7]实现。每个服务都有一个IP多播组，其中包含所有副本。这些通信协议是不可靠的；它们可能会重复、丢失消息或乱序传递消息。

该算法允许无序交付并拒绝重复。视图更改可用于从丢失的消息中恢复，但这是昂贵的，因此执行重传非常重要。在正常操作中，从丢失的消息中恢复是由接收端驱动的:备份端在消息过期时向主端发送否定确认，而主端在长时间超时后重新发送预准备消息。对否定确认的回复可以包括稳定检查点的一部分和丢失的消息。在视图更改期间，副本会重传视图更改消息，直到它们收到匹配的新视图消息，或者它们会转移到后面的视图。

复制库目前不实现视图更改或重新传输。这不会影响第7节中给出的结果的准确性，因为算法的其余部分已经完全实现了（包括触发视图更改的定时器的操作），而且我们已经将完整的算法正式化，并证明了它的正确性[4]。

BFS：拜占庭容错文件系统

我们使用复制库实现了BFS，这是一个拜占庭容错的NFS服务。图2显示了BFS的架构。我们选择不修改内核NFS客户端和服务器，因为我们没有Digital Unix内核的源代码。

容错NFS服务导出的文件系统与任何常规NFS文件系统一样挂载在客户机机器上。应用程序进程不加修改地运行，并通过内核中的NFS客户机与挂载的文件系统交互。我们依靠用户级中继进程来协调标准NFS客户端和副本之间的通信。中继接收NFS协议请求，调用复制库的调用过程，并将结果发送回NFS客户端。

每个副本运行一个带有复制库和NFS V2守护进程的用户级进程，我们将其称为snfsd（用于简单的nfsd）。复制库接收来自中继的请求，通过向上调用与snfsd进行交互，并将NFS应答包成它发送给中继的复制协议应答。

我们使用一个固定大小的内存映射文件来实现snfsd。所有的文件系统数据结构，例如，inode，块和它们的空闲列表，都在映射文件中。我们依靠操作系统来管理内存映射文件页的缓存，并将修改后的页异步写入磁盘。当前的实现使用8KB的块和索引节点，其中包含NFS状态信息和256字节的数据，这些数据用于在目录中存储目录条目，在文件中存储块的指针，在符号链接中存储文本。目录和文件也可以以类似Unix的方式使用间接块。

我们的实现确保所有状态机副本都以相同的初始状态启动，并且是确定性的，这是使用我们的协议实现的服务正确性的必要条件。主节点建议time-last-modified和time-last-accessed的值，副本选择建议值中较大的一个，并且比为早期请求选择的所有值的最大值大一个。我们不需要同步写入来实现NFS V2协议语义，因为BFS通过复制[20]实现了修改数据和元数据的稳定性。

维护检查点

介绍snfsd如何维护文件系统状态检查点。回想一下，每个副本维护状态的几个逻辑副本：当前状态、一些还不稳定的检查点，以及最后一个稳定检查点。

snfsd直接在内存映射文件中执行文件系统操作以保持局部性，并且它使用写时复制来减少与维护检查点相关的空间和时间开销。snfsd为内存映射文件中的每个512字节块维护一个写时复制位。当复制代码调用make_checkpoint upcall时，snfsd设置所有写时复制位并创建一个（易变的）检查点记录，其中包含当前序列号（它作为upcall的参数接收）和一个块列表。该列表包含自检查点被使用以来被修改的块的副本，因此，它最初是空的。记录还包含当前状态的摘要;我们将在第6.4节讨论如何计算摘要。

当在执行客户端请求时修改内存映射文件的一个块时，snfsd检查该块的写时拷贝位，如果设置了该值，则将该块的当前内容及其标识符存储在最后一个检查点的检查点记录中。然后，它用它的新值覆盖该块，并重置它的写时复制位。snfsd保留检查点记录，直到被告知通过删除检查点向上调用丢弃它，这是由复制代码在稍后的检查点变得稳定时做出的。

如果复制代码需要将检查点发送到另一个副本，它将调用get检查点upcall。snfsd首先在稳定检查点的检查点记录中查找该块的值，然后在以后的检查点记录中查找该块的值。如果块不在任何检查点记录中，它将返回当前状态的值。

使用即写即拷技术，以及我们最多保留2个检查点的事实，确保保存多个状态逻辑副本的空间和时间开销很低。例如，在第7节描述的Andrew基准测试中，平均检查点记录大小仅为182块，最大为500块。

计算检查点消化

snfsd计算检查点状态摘要，作为生成检查点向上调用的一部分。尽管检查点只是偶尔使用，但增量地计算状态摘要是很重要的，因为状态可能很大。snfsd使用了一个名为AdHash[1]的增量式抗碰撞单向哈希函数。该函数将状态划分为固定大小的块，并使用一些其他哈希函数（例如，MD5）来计算通过连接块索引和每个块的块值获得的字符串的摘要。状态摘要是块的摘要以某个大整数为模的总和。在我们当前的实现中，我们使用写时复制技术中的512字节块，并使用MD5计算它们的摘要。

为了递增地计算状态摘要，snfsd维护一个表，其中每个512字节的块都有一个散列值。这个散列值是通过将md5应用到块索引中并与最后一个检查点时的块值相连接而获得的。当调用make_checkpointis时，snfsd（从相关的检查点记录）获取前一个检查点状态的摘要。它通过对与当前块值相连的块索引应用MD5来为每个写时复制位被重置的块计算新的哈希值。然后，它将新的哈希值添加到d中，从d中减去旧的哈希值，并更新表以包含新的哈希值。只要修改块的数量少，这个过程是有效的；如上所述，Andrew基准测试的每个检查点平均有182个块被修改。

性能评估

本节使用两个基准测试来评估系统的性能：微基准测试和Andrew基准测试[15]。微基准测试提供了与服务无关的复制库性能评估；它测量调用空操作（即不执行任何操作的操作）的延迟。

Andrew基准测试用于比较BFS与其他两个文件系统：一个是数字Unix中的NFS V2实现，另一个与BFS相同，只是没有复制。第一个比较表明，我们的系统的延迟与许多用户每天使用的商业系统的延迟相似，从而表明我们的系统是实用的。第二个比较允许我们在实际服务的实现中准确地评估算法的开销。

实验装置

实验测量正常情况下的行为（即，没有视图更改），因为这是决定系统性能的行为。所有的实验都是在一个客户端运行两个中继进程和四个副本的情况下进行的。四个副本可以容忍一个拜占庭的错误;我们希望这种可靠性级别足以满足大多数应用程序。副本和客户端在相同的DEC 3000/400 Alpha工作站上运行。这些工作站有133 MHz的Alpha 21064处理器，128 MB内存，并运行数字Unix 4.0版本。文件系统由每个副本存储在DEC RZ26磁盘上。所有工作站通过10Mbit/s交换以太网连接，并具有DEC LANCE以太网接口。该交换机是一个DEC EtherWORKS 8T/TX。实验在一个独立的网络上进行。

检查点之间的间隔是128个请求，这将导致在任何实验中发生多次垃圾收集。预准备消息中副本接受的最大序列号为256加上最后一个稳定检查点的序列号。

微型基准测试

微基准测试测量调用空操作的延迟。它评估一个没有状态的简单服务的两个实现的性能，该服务实现了具有不同大小的参数和结果的空操作。第一个实现是使用我们的库复制的，第二个是不复制的，直接使用UDP。表1报告了在客户机上测量的只读和读写操作的响应时间。它们是通过对三次单独运行的10,000次操作调用进行计时获得的，我们报告了三次运行的中值。与中位数的最大偏差始终低于报告值的0.3%。我们用a/b表示每个操作，其中a和b是操作参数的大小，结果为KBytes。

复制库带来的开销是由于额外的计算和通信。例如，读写0/0操作的计算开销大约为1.06ms，其中包括执行加密操作所花费的0.55ms。剩余的1.47ms的开销是由于额外的通信；复制库引入了额外的消息往返，它发送更大的消息，并且相对于没有复制的服务，它增加了每个节点接收的消息数量。

只读操作的开销要低得多，因为第5.1节中讨论的优化降低了计算和通信开销。例如，只读0/0操作的计算开销大约为0.43ms，其中包括执行加密操作所花费的0.23ms，而通信开销仅为0.37ms，因为执行只读操作的协议使用了一次往返。

表1显示了4/0和0/4操作的相对开销较低。这是因为复制库引入的开销中有很大一部分与操作参数和结果的大小无关。例如，在读写0/4操作中，大消息（应答）只经过网络一次（如5.1节所述），并且只增加了处理应答消息的加密开销。读写4/0操作的开销更高，因为大消息（请求）会经过两次网络，增加了处理请求和预准备消息的加密开销。

需要注意的是，这种微基准测试代表了算法的最坏情况开销，因为操作不执行任何工作，且未复制的服务器提供的保证非常弱。大多数服务将需要更强的保证，例如，经过身份验证的连接，相对于实现这些保证的服务器，我们的算法引入的开销将更低。例如，相对于使用MACs进行身份验证的非复制服务版本，复制库的开销对于读写0/0操作仅为243%，对于只读4/0操作仅为4%。

我们可以估计一个相对于Rampart[30]算法的性能增益的大致下界。Reiter报告说，Rampart在一个由4个SparcStation 10s[30]组成的10 Mbit/s以太网网络中，对一个空消息的多rpc有45毫秒的延迟。multiRPC对于主服务器调用状态机操作已经足够了，但是对于任意客户端调用操作，它将需要添加额外的消息延迟和额外的RSA签名和验证来验证客户端;这将导致至少65ms的延迟（使用[29]中报告的RSA计时）。即使我们将这个延迟除以1.7，即DEC 3000/400和SparcStation 10的SPECint92评级之比，我们的算法仍然将调用读写和只读0/0操作的延迟分别降低了10和20以上。请注意，这种扩展是保守的，因为网络占了Rampart延迟[29]的很大一部分，而Rampart的结果是使用300位弹性RSA签名获得的，这在今天被认为是不安全的，除非用于生成它们的密钥非常频繁地刷新。

目前还没有公布SecureRing[16]的性能数据，但它会比Rampart慢，因为它的算法在关键路径上有更多的消息延迟和签名操作。

Andrew基准

Andrew基准测试[15]模拟软件开发工作负载。它有五个阶段：（1）递归地创建子目录；（2）复制源树；（3）检查树中所有文件的状态而不检查其数据；（4）检查所有文件中的每一个字节数据；（5）对文件进行编译和链接。

我们使用Andrew基准测试来比较BFS与其他两种文件系统配置：NFS-std（数字Unix中的NFS V2实现）和BFS-nr（与BFS相同但没有复制）。BFS-nr在客户端运行两个简单的UDP中继，在服务器端运行一个与snfsd版本链接的薄贴面，其中删除了所有检查点管理代码。此配置不会在回复客户端之前将修改后的文件系统状态写入磁盘。因此，它不实现NFS V2协议语义，而BFS和NFS-std都实现了。

在NFS v2协议的18个操作中，只有getattr是只读的，因为文件和目录的最后一次访问时间属性是由其他操作设置的，例如：读取和查找。结果是我们对只读操作的优化很少被使用。为了显示这种优化的影响，我们还在BFS的第二个版本上运行了Andrew基准测试，该版本将查找操作修改为只读。这种修改违反了严格的Unix文件系统语义，但在实践中不太可能产生不利影响。

对于所有配置，使用Digital Unix内核中的标准NFS客户端实现，使用相同的挂载选项，实际的基准测试代码在客户端工作站上运行。与基准测试最相关的选项有：UDP传输、4096字节读写缓冲区、允许异步客户端写入以及允许属性缓存。

我们报告了对每个配置运行基准的平均10次。运行基准的总时间的样本标准差始终低于报告值的2.6%，但在前四个阶段的个别时间，它高达14%。这种高差异也存在于NFS-std配置中。报告的平均误差在个别阶段低于4.5%，在整个阶段低于0.8%。

表2为BFS和BFS-nr的结果。BFS-strict和BFS-nr之间的比较表明，该服务的拜占庭容错开销很低——BFS-strict只需要26%的时间来运行完整的基准测试。这种开销比微基准测试中观察到的要低，因为客户机在运行时间中的很大一部分用于操作之间的计算，即在接收一个操作的应答和发出下一个请求之间的计算，而服务器上的操作执行一些计算。但是整个基准测试阶段的开销并不统一。造成这种情况的主要原因是客户端在操作之间花费的计算时间的变化；前两个阶段的相对开销较高，因为客户机在操作之间的计算花费了大约40%的总时间，而在最后三个阶段花费了大约70%的时间。

表中显示，将只读优化应用于查找可以显著提高BFS的性能，并将相对于BFS-nr的开销降低20%。这种优化在前四个阶段有显著的影响，因为在BFS-strict中等待查找操作完成的时间至少占这些阶段运行时间的20%，而不到最后一个阶段运行时间的5%。

表3显示了BFS vs NFS-std的结果。这些结果表明BFS可以用于实际测试，BFS-strict只需要多3%的时间就可以运行完整的基准测试。因此，可以用BFS替换数字Unix中的NFS V2实现（许多用户每天都在使用它），而不会影响这些用户感知到的延迟。而且，对查找操作进行只读优化的BFS实际上比NFS-std快2%。

BFS相对于NFS-std的开销在所有阶段都不相同。对于阶段1、2和5，这两个版本的BFS都比NFS-std快，但对于其他阶段则慢一些。这是因为在阶段1、2和5中，客户端发出的大部分操作（21%到40%之间）是同步的，也就是说，在响应客户端之前，需要NFS实现来确保修改后的文件系统状态的稳定性。NFS-std通过将修改后的状态写入磁盘来获得稳定性，而BFS通过使用复制（如在Harp[20]中）以较低的延迟获得稳定性。在阶段3和4中，NFS-std比BFS（和BFS-nr）更快，因为客户机在这些阶段中不发出同步操作。

结论

本文描述了一种新的状态机复制算法，它能够容忍拜占庭故障，并可用于实践：它是第一个在像Internet这样的异步系统中正常工作的算法，它将以前的算法的性能提高了一个数量级以上。

本文还描述了NFS的拜占庭容错实现BFS。BFS证明了使用我们的算法实现真实服务是可能的，其性能接近无复制服务——BFS的性能仅比数字Unix中标准NFS实现的性能差3%。这种良好的性能归功于许多重要的优化，包括用消息身份验证码向量替换公钥签名、减少消息的大小和数量以及增量检查点管理技术。

拜占庭容错算法在未来很重要的一个原因是，即使出现软件错误，它们也能让系统继续正确工作。不是所有的错误都能存活;我们的方法无法掩盖发生在所有副本上的软件错误。然而，它可以掩盖在不同副本上独立发生的错误，包括不确定的软件错误，这是最成问题和持久的错误，因为它们最难检测。事实上，我们在运行系统的时候遇到了这样的软件bug，尽管如此，我们的算法仍然能够继续正确运行。

在改进我们的制度方面还有很多工作要做。一个特别有趣的问题是减少实现我们的算法所需的资源数量。只有当一些完整副本失败时，可以通过使用f副本作为协议中涉及的见证人来减少副本的数量。我们也相信，有可能将国家的副本数量减少到f+1，但细节仍有待研究。