protocols - 为什么我们需要在共识协议的视图变化中进行总排序？

Question

在他们著名的文章中，Miguel Castro 和 Barbara Liskov 证明了 PBFT 共识协议的提交阶段是这样的：

这可确保副本在同一视图中就​​请求的总顺序达成一致，但不足以确保跨视图更改的请求的总顺序。副本可能会在不同视图中收集具有相同序列号和不同请求的准备好的证书。提交阶段按如下方式解决了这个问题。每个副本 i 多播 <COMMIT, v, n, i>_{α_i} 说它具有准备好的证书并将此消息添加到其日志中。然后每个副本收集消息，直到它拥有一个仲裁证书，其中包含 2 f + 1 条 COMMIT 消息，用于相同的序列号 n 和来自不同副本（包括它自己）的视图 v。我们将此证书称为已提交证书，并说当副本具有准备好的和已提交的证书时，该请求是由副本提交的。

但是为什么我们需要保证视图更改的总顺序呢？如果领导者/主副本失败并触发视图更改，那么丢弃前一个视图中的所有内容就足够了吗？什么情况下提交阶段阻止了这个解决方案没有？

如果这太明显了，请道歉。我是分布式系统的新手，我还没有找到任何直接回答这个问题的来源。

标签： protocolsdistributed-computingdistributeddistributed-systemconsensus

Answer 1

这有一个概念上的原因。该系统在客户看来是一个黑匣子。这个盒子的整个想法是提供对某些服务的可靠访问，因此，它应该掩盖特定副本的故障。否则，如果您在每次视图更改时丢弃所有内容，客户端将不断丢失其数据。所以基本上，您的解决方案与规范相矛盾。确切地需要提交阶段来防止这种情况。如果请求只有在有 2f + 1 个 COMMIT 消息时才被“接受”，那么即使所有 f 个副本都发生故障，其余节点也可以恢复所有已提交的请求，这提供了对系统的持久访问。

还有一个技术原因。从理论上讲，系统是异步的，这意味着您甚至不能保证视图更改只会因故障而发生。一些副本可能只是怀疑leader有故障而改变视图。使用您的解决方案，即使没有副本出现故障，系统也可能会丢弃它接受的所有内容。

如果您是分布式系统的新手，我建议您看看容忍非拜占庭故障的经典协议（例如，Paxos），它们更简单，但以类似的方式解决问题。

编辑

当我说“客户不断丢失他们的数据”时，这比听起来要多一些。我说的是特定客户端请求对系统的影响。让我们看一个键值存储。客户通过我们的“黑匣子”将一些与一些A相关联。“黑匣子”现在根据任何其他并发（或简单的并行）请求对该请求进行排序。然后它在所有副本中复制它并最终通知. 没有提交阶段就没有排序，在两个不同的视图中，我们的“黑匣子”可以选择两种不同的客户端请求执行顺序。话虽如此，以下是可能的：valuekeyA

1. 一次t，A联想value到key并且“盒子”批准了这一点，
2. 当时t+1，B联想value_2和key“盒子”批准了这一点，
3. 当时t+2，C读value_2自key，
4. 查看更改（对客户不可见），
5. 当时t+3，D从. value_key

请注意，（5）可能不是因为“框”不知道value_2（正如您提到的值本身可以重新提交），而是因为它不知道之前它首先写入value然后用value_2. 在新视图中，系统需要以某种方式对这两个请求进行排序，但没有运气，该决定与过去不一致。

最终同步是保证协议活跃性的一种方式，但是，它不能防止上述情况。最终同步表明您的系统最终会像同步系统一样运行，但您不知道什么时候，在那之前任何奇怪的事情都可能发生。如果在异步期间违反了安全属性，那么显然整个系统是不安全的。