为什么使用no-op填补paxos事件之间的空白是合法的？

Question

我们知道事件遵循及时的顺序,并且当事件1-5和10被确定时发生,但此后6-9和11还没有.在上面的论文中,它说我们只需用无操作值填写6-9之间的差距,然后简单地记录11和11之间的新事件.

因此,在这种情况下,由于已经记录了事件10,我们知道某些事件必须在5到10之间发生,但由于某些故障而未被Paxos记录.如果我们只是填写无操作值,这些事件将在我们的录音中丢失.

更糟糕的是,如果我在上面链接的论文中说,事件实际上是来自客户端的命令,那么在中间丢失一些命令可能会使整个操作集合非法(如果没有任何命令可以跳过或命令他们很重要).

那么,为什么Paxos为事件之间的差距填补无操作价值仍然是合法的呢？(如果由于上面关注的无操作值,整个记录集可能无效.)此外,是否有更好的方法从这些间隙中恢复而不是使用no-op？

Answer 1

这是一个多部分的答案。

提出无操作值是发现尚未到达节点的命令的方法。我们不会简单地用 no-op 命令填充间隙中的每个插槽：我们建议每个插槽都填充一个 no-op。如果任何对等方已经接受了命令，它将在Prepare-ack消息中返回该命令，并且提议者将在接受轮中使用该命令而不是 no-op。

例如，假设一个节点位于临时网络分区后面，并且无法与其他节点一起玩插槽 6-9。它知道它在学习槽 10 中的命令时错过了。然后它建议无操作以了解在这些槽中决定的内容。

实际的实现也有一个带外学习协议来批量学习大量的转换。

命令在完全决定之前不是命令；在那之前，它只是一个建议的命令。Paxos 是关于在来自多个客户端的竞争命令之间进行选择。客户必须准备好让他们的命令被拒绝，因为选择了另一个客户的命令。

实际实现都是关于选择客户端命令的顺序。他们的世界观是预写日志，他们将命令放置在该日志中。如果没有选择他们的命令，他们会在下一个插槽中重试。（有很多方法可以减少争用；Lamport 提到将请求转发给领导者，例如在 Multi-Paxos 中所做的。）

实际系统也有一些方法可以在建议之前知道命令是否无效；例如知道一组读取和一组写入。这很重要，原因有二。首先，它是一个异步的多客户端系统，当客户端的命令到达服务器时，任何事情都可能发生变化。其次，如果两个并发命令不冲突，那么两者都应该能够成功。