关于raft算法的困惑

Question

在论文 \xe3\x80\x8a In Search of an Understanding Consensus Algorithm \xe3\x80\x8b 中，图 8 显示了（d）和（e）中的一个问题，即一些旧日志可能会被覆盖并且永远不会回来。

\n\n

在第 5.4.2 节中，它说\xe2\x80\x9c 为了消除如图 8 中的问题，Raft 从不通过计算副本来提交前一项的日志条目。通过计算副本数，仅提交来自leader\xe2\x80\x99s当前任期的日志条目；一旦以这种方式提交了当前术语中的条目，则由于 Log Matching Property\xe2\x80\x9d ，所有先前的条目都会间接提交。

\n\n

我对这部分感到困惑，它在图 8 中是如何工作的？什么会发生，什么不会发生？

\n

Answer 1

将规则添加到图 8 中。

\n

\n

Raft 从不通过计算副本来提交之前术语的日志条目。

\n

\n

因此，现在我们不再提交之前术语中的日志条目，让我们看看图 8 中会再次发生什么。我修改了图 8 以显示应用规则后的情况。\n

\n

(a) 和 (b) 的作用相同。

\n

从 (c) 开始，索引 2 处的日志条目附加到步骤 (a) 以来的第 2项，我在其中画了一个黄色圆圈。从前面的术语来看也是如此。因此，领导者不会根据规则复制该条目（带有我的黑色十字的黄色 2）。它必须从索引 3 处的条目开始复制。

\n

这个规则在图2“服务器规则”leader的规则3.1中也提到过：

\n

\n

发送 AppendEntries RPC，其中条目从 开始nextIndex。

\n

\n

nextIndex 使用 初始化last log index + 1，因此它应该从 (c) 处的日志索引 3 开始，而不是从索引 2 开始。

\n

因此，对于原始 (c) 处的假设过程，不可能在日志 3\xef\xbc\x88（在第 4\xef\xbc\x89 项上附加的粉色日志）之前将日志 2 附加到多数复制。(d) 不会发生。

\n

更新：2020-12-04

\n

@coderx 和 @OrlandoL 讨论了 (a)、(b) 以及 S5 如何成为领导者的评论。他们的讨论使这个答案更加完整，所以我在这里放了一个参考。

\n

基本上，(a)、(b)不是必然发生的条件，有些情况下S5不会当选领导者，例如S3、S4有相同的机会成为领导者。（详细请看评论）

\n

这些假设是正确的，S5 可能不会成为领导者，并且以下过程不会发生。

\n

但是让我们回到论文图 8 并阅读该图的注释：

\n

\n

时间序列显示了为什么领导者无法使用旧术语中的日志条目确定承诺。在\n(a) 中，S1 是领导者，并部分复制索引 2 处的日志条目。\n在 (b) 中，S1 崩溃；S5 通过 S3、S4 及其自身的投票\n被选为第 3 期的领导者，并接受日志\n索引 2 处的不同条目。

\n

\n

IMO，作者正在谈论S5当选领导者的情况。这样整个过程就很热闹了。

\n

正如 @OrlandoL 提到的，在 MIT 6.824 实验室中，您应该考虑所有条件以实现正确的 Raft 实现。

\n

希望这可以帮助。

\n