paxos - 提议者如何知道其提议未被法定人数的接受者批准？

Question

我在 wiki 上阅读“paxos”，上面写着：“当多个 Proposer 发送冲突的 Prepare 消息时，或者当 Proposer 没有收到 Quorum of 响应（Promise 或 Accepted）时，轮次失败。在这些情况下，必须开始另一轮具有更高的提案编号。” 但我不明白提案人如何区分其提案未获批准与消息传输需要更多时间？

Answer 1

理解 Paxos 的一个棘手部分是原始论文和大多数其他论文，包括 wiki，并没有描述能够在现实世界中使用的完整协议。他们只关注算法的必要性。例如，他们说提议者必须选择比任何先前使用的数字都大的数字“n”。但是他们没有说明如何实际执行此操作，可能发生的故障种类，或者如果两个提议者同时尝试使用相同的提议编号（如都选择 n=2）如何解决这种情况。这实际上完全违反了协议并会导致不正确的结果，但我不确定我是否见过特别提到的。我想这应该是“显而易见的”。

具体到您的问题，没有完美的方法可以使用原始算法来区分差异。实际的实现通常会通过向 Proposer 发送 Nack 消息而不是默默地忽略它来加倍努力。还有很多其他的技巧可以使用，但所有这些技巧，包括小窍门，都有不同的缺点。哪种方法最好通常取决于使用 Paxos 的应用程序类型和它打算运行的环境。

如果您有兴趣，我整理了一篇关于 Paxos 的冗长的描述，其中包括许多实际实现必须解决的问题以及核心组件。它与其他几个问题一起涵盖了这个问题。

Answer 2

针对您的问题，提议者无法区分丢失的消息、延迟的消息、崩溃的接受者或停滞的接受者。在每种情况下，您都没有得到回应。通常情况下，实现将在获得少于法定人数的响应时超时，并在假设消息被丢弃或接受者正在重新启动的情况下重新发送提案。

通常实现添加“nack”消息作为否定确认作为加速恢复的优化。提议者仅从已接受更高承诺的可达节点获得“nack”响应。“nack”既可以显示最高承诺，也可以显示已知已修复的最高实例。这将如何帮助将在下面概述。

我编写了一个名为TRex的 Paxos 实现，其中一些技术尽可能贴近Paxos Made Simple论文中对算法的描述。我在一篇博文中描述了超时和 nack 的实际考虑。

它使用的一个有趣的技术是让一个超时节点以非常低的数字提出第一个提案。这将始终收到“nack”消息。为什么？考虑一个三节点集群，其中一个网络链接在稳定的提议者和另一个节点之间断开。另一个节点将超时并发出准备。如果它发出高准备，它将从第三个节点获得承诺。这将打断稳定的领导者。然后你就有了对称性，两个无法互相发送消息的节点可以与领导层交换而没有前进的进展。

为了避免这种情况，超时节点可以从低准备开始。然后它可以查看“nack”消息以从第三个节点获悉有一个正在取得进展的领导者。它将认为这是已知在 nack 中固定的最高实例将大于本地值。然后超时节点不能发出高准备，而是要求第三个节点向它发送最新的固定和接受的值。通过该增强功能，超时节点现在可以区分稳定的提议者崩溃或连接失败。这种基于“nack”的技术不会影响实现的正确性，它们只是一种优化，以确保快速故障转移和向前进展。