3

我是分布式系统和共识算法的新手。我理解它是如何工作的，但我对一些极端情况感到困惑：当接受者收到一个 ACCEPT 实例但从未听说过最终的共识或决定是什么时，接受者会做出什么反应。例如，提议者在提交期间或在发送所有 ACCEPT 之后正在启动或失败。在这种情况下会发生什么？

谢谢。

4

2 回答 2

4

这个问题有两个部分：接受者对新提案有何反应？如果接受者从不知道结果，他们会如何反应？

在普通的 paxos 中，接受者实际上不需要知道结果。事实上，不同的接受者在他们的记忆中有不同的值是完全合理的，永远不知道他们拥有的值是否是承诺的值。

paxos的真正意义在于处理第一个问题。并且看到接受者实际上永远不知道它是否具有已提交的值，它必须假设它可以具有已提交的值，但如果它没有已提交的值，则可以替换其值。它是怎么知道的？当收到消息时，提议者总是比较轮数，如果它是旧的，那么接受者会向提议者发出信号，它必须首先“赶上”（一个Nack）。否则，它相信提议者知道它在做什么。

现在谈谈真实系统。一些真正的 paxos 系统可以让接受者不关心承诺的价值是什么：Paxos 只是在那里选择价值是什么。但是许多实际系统使用 Paxos & Friends 来制作数据的冗余副本以便妥善保管。

一些 paxos 系统会继续 paxos-ing，直到所有的接受者都拥有数据。（请注意，在没有来自其他提议者的干扰的情况下，额外的 paxos 轮会将提交的值复制到各处。）其他系统对来自其他提议者的干扰持谨慎态度，并将使用不同的提交消息来告诉接受者（和其他学习者）提交的值是什么.

但是如果提议者崩溃了怎么办？随后的提议者可以提出一个无操作值。如果后续提议者准备好（阶段 1A）并且可以与先前提议者成功发送接受的任何接受者进行通信（阶段 2A），那么它将知道先前提议者试图做什么（通过阶段 1B 中的响应：PrepareAck）。否则，将提交无害的无操作值。

于 2018-10-16T02:31:55.823 回答
2

当接受者收到一个实例的接受但从未收到关于最终共识或决定是什么的回复时，接受者将如何反应。

发送该值的节点通常通过计算对其 ACCEPT 消息的积极响应来了解其值是固定的，直到它看到多数。如果消息被丢弃，则可以重新发送它们，直到有足够的消息通过以确定多数结果。当重复发送消息时，接受者无需执行任何操作，只需准确地遵循算法即可。

例如，提议者在提交期间或在发送所有 ACCEPT 之后正在启动或失败。在这种情况下会发生什么？

的确，这是一个有趣的案例。一个值可能会被大多数人接受，因此是固定的，但没有人知道，因为所有预定的消息都未能到达。

对 PREPARE 消息的响应包含有关已接受值的信息。因此，任何节点都可以发出 PREPARE 消息并了解某个值是否已修复。这实际上是 Paxos 的天才之处。一旦一个值被大多数人接受，如果是固定的，因为运行该算法的任何节点必须在所有消息丢失和崩溃情况下继续选择相同的值。

通常， Paxos 使用一个稳定的领导者，该领导者将 ACCEPT 消息流式传输到具有连续值的连续轮次。如果领导者崩溃，任何节点都可以超时并尝试通过发送 PREPARE 消息来领导。多个节点发出 PREPARE 消息试图引导可能会相互中断，从而提供活锁。然而，一旦价值被固定，他们永远不会对固定的价值产生分歧。他们只能通过竞争来确定自己的价值，直到有足够的信息通过以获得胜利者。

再一次，当新的领导者从崩溃的领导者那里接管时，接受者节点除了遵循算法之外不需要做任何事情。该算法的不变量意味着没有领导者会与任何先前的领导者就固定值相矛盾。新领导者与老领导者合作，接受者可以简单地相信情况就是如此。最终，足够的消息将通过所有节点来学习结果。

于 2018-10-20T20:08:24.703 回答