4

在诸如 PAXOS 和 RAFT 之类的共识算法中，会提出一个值，如果法定人数同意，则将其持久地写入数据存储。在达到法定人数时无法参加的参与者会怎样？他们最终如何赶上？无论我在哪里看，这似乎都留给读者作为练习。

4

3 回答 3

1

看一下 Raft 协议。它只是内置在算法中。如果领导matchIndex者跟踪最高索引（被承诺。从本质上讲，当重新启动时，领导者总是会从其日志中的最后一个条目开始向该跟随者发送条目。因此节点被赶上。nextIndexnextIndex

于 2019-03-19T20:54:46.223 回答
0

Paxos made Simple 中提到了这一点：

由于消息丢失，可以在没有学习者发现的情况下选择一个值。学习者可以询问接受者他们接受了哪些建议，但接受者的失败可能会导致无法知道大多数人是否接受了特定的建议。在这种情况下，学习者只会在选择新提案时才知道选择了什么值。如果学习者需要知道某个值是否已被选择，它可以让提议者使用上述算法发出提议。

还有在 Raft 纸上：

领导者为每个追随者维护一个 nextIndex，这是领导者将发送给该​​追随者的下一个日志条目的索引。

如果一个 follower 的 log 与 leader 的不一致，那么 AppendEntries 一致性检查将在下一个 AppendEntries RPC 中失败。拒绝后，领导者减少 nextIndex 并重试 AppendEntries RPC。最终 nextIndex 将达到领导者和追随者日志匹配的点。发生这种情况时，AppendEntries 将成功，这将删除跟随者日志中的任何冲突条目，并从领导者的日志中附加条目（如果有）。

如果跟随者或候选者崩溃，那么未来发送给它的 RequestVote 和 AppendEntries RPC 将失败。Raft 通过无限期重试来处理这些失败；如果崩溃的服务器重新启动，那么 RPC 将成功完成。

于 2019-04-27T15:40:44.317 回答
0

对于原始的 Paxos 论文，它确实留给读者作为练习。在实践中，使用 Paxos，您可以发送额外的消息，例如否定确认，以在集群周围传播更多信息，作为性能优化。这可用于让节点知道它由于丢失消息而落后。一旦一个节点知道它落后了，它就需要赶上这可以通过其他消息类型来完成。这被描述为Trex multi- paxos引擎中的 Retransmission，我编写该引擎是为了揭开 Paxos的神秘面纱。

Google Chubby paxos 论文Paxos Made Live批评 Paxos 将很多事情留给了执行人员。Lamport 接受过数学培训，并试图在数学上证明当他找到解决方案时，您无法就有损网络达成共识。原始论文在很大程度上提供了一个证明它是可能的，而不是解释如何用它来构建实际系统。现代论文通常描述由一些实验结果支持的一些新技术的应用，同时它们也提供正式的证明，恕我直言，大多数人跳过它并相信它。引入 Paxos 的不可接近的方式意味着许多引用原始论文但没有看到他们描述领导人选举和多 Paxos 的人. 不幸的是，Paxos 仍然是以理论的方式教授的，而不是现代的风格，这导致人们认为它很难，错过了它的本质。

我认为Paxos 很简单，但对分布式系统中的故障进行推理并进行测试以发现任何错误却很困难。原始论文中留给读者的所有内容都不会影响正确性，但会影响延迟、吞吐量和代码的复杂性。一旦您了解了 Paxos 正确的原因，因为它在机械上很简单，就可以在为您的用例和工作负载优化代码时以不违反一致性的方式直接编写所需的其余部分。

例如，Corfu和CURP提供了非常高的性能，一个仅将 Paxos 用于元数据，另一个仅在对相同键进行并发写入时才需要使用 Paxos。这些解决方案不能直接与 Raft 或 Multi-Paxos 一起完成，因为它们解决了特定的高性能场景（例如，kv 存储）。然而，它们表明值得理解的是，对于实际应用程序，如果您的特定工作负载允许您在整体解决方案的某些部分仍然使用 Paxos，您可以进行大量优化。

于 2019-03-20T08:29:57.143 回答