关于筏算法的困惑
Confusion about raft algorithm
在论文《In Search of an Understandable Consensus Algorithm》中，图8（d）和（e）中的一个问题是，一些旧的日志可能会被覆盖，永远不会回来。
在第 5.4.2 节中，它说 “为了消除图 8 中的问题，Raft 从不通过计算副本来提交前任期的日志条目。只有来自领导者当前任期的日志条目通过计算副本来提交；一旦以这种方式提交了当前任期的条目，那么由于日志匹配属性”.
，所有先前的条目都会被间接提交
我对那部分感到困惑，它在图 8 中是如何工作的？什么会发生什么不会？
通过将规则添加到图 8。
Raft never commits log entries from previous terms by counting replicas.
所以现在我们不再提交以前任期的日志条目，让我们看看图 8 会再次发生什么。我修改了图 8 以显示应用规则后的情况。
(a) 和 (b) 工作相同。
从 (c) 开始，索引 2 处的日志条目追加到 term 2，因为步骤 (a)，我在其中画了一个黄色圆圈。所以它来自于以前的条款。因此，领导者不会根据规则复制该条目（带有黑色十字的黄色 2）。它必须从索引 3 处的条目开始复制。
此规则在图 2“服务器规则”领导者规则 3.1 中也提到：
Send AppendEntries RPC with entries startting at nextIndex.
nextIndex 用 last log index + 1 初始化，因此它应该从 (c) 处的日志索引 3 开始，而不是索引 2。
因此对于原始(c)处的假设程序，不可能在log 3（第4项处附加的粉红色）复制多数之前将log 2附加到多数。 和 (d) 不会发生。
更新：2020-12-04
@coderx 和@OrlandoL 对 (a)、(b) 以及 S5 如何不能成为领导者进行了讨论。他们的讨论使这个答案更完整，所以我在这里放一个参考。
基本上，（a），（b）不是必不可少的条件，在某些情况下，S5不会选举领导者，例如S3，S4也有同样的机会成为领导者。 （详见评论）
这些假设是正确的，S5 可能不会成为领导者，并且不会发生以下过程。
但是让我们回到论文图 8 并阅读该图的注释：
A time sequence showing why a leader cannot determine commitment using log entries from older terms. In
(a) S1 is leader and partially replicates the log entry at index 2.
In (b) S1 crashes; S5 is elected leader for term 3 with votes
from S3, S4, and itself, and accepts a different entry at log
index 2.
IMO，作者说的是S5被选为leader的情况。如此一来，整个过程就成了场景。
正如@OrlandoL 提到的，在 MIT 6.824 实验室中，您应该考虑所有条件以实现正确的 Raft 实现。
希望对您有所帮助。
Raft 不提交前任的条目，因为前任的这些条目可能会被未来的领导者覆盖，就像 (d) 中的领导者 S5。
假设 (c) 中的领导者 S1 在任期 2 的索引 2 处提交了条目，那么该条目将被 S1、S2 和 S3 应用。然后 S1 崩溃了，S5 完全有可能像 (d) 那样成为领导者，因为它的日志比 S2、S3 和 S4 更新。 S5 将用自己的任期 3 条目覆盖索引 2 处的任期 2 条目。这意味着领导者 S5 覆盖已提交的条目！一些服务器（S1、S2 和 S3）已应用该条目对于第 2 项，其他人（S4、S5）将在索引 2 处应用第 3 项的条目，这违反了图 3 中的状态机安全。
因此 (c) 中任期 4 的领导者 S1 不能在索引 2 处提交任期 2 的条目，除非它像 (d) 中那样在索引 3 处提交自己任期的条目，如任期 4 的条目。一旦第 4 期索引 3 处的条目被提交，第 2 期索引 2 处的条目将自动提交，并且它们永远不会被未来的领导者覆盖。 （候选人只有在拥有上一任期的所有已提交条目时才能成为领导者。）
在论文《In Search of an Understandable Consensus Algorithm》中，图8（d）和（e）中的一个问题是，一些旧的日志可能会被覆盖，永远不会回来。
在第 5.4.2 节中，它说 “为了消除图 8 中的问题，Raft 从不通过计算副本来提交前任期的日志条目。只有来自领导者当前任期的日志条目通过计算副本来提交；一旦以这种方式提交了当前任期的条目，那么由于日志匹配属性”.
，所有先前的条目都会被间接提交我对那部分感到困惑，它在图 8 中是如何工作的？什么会发生什么不会？
通过将规则添加到图 8。
Raft never commits log entries from previous terms by counting replicas.
所以现在我们不再提交以前任期的日志条目，让我们看看图 8 会再次发生什么。我修改了图 8 以显示应用规则后的情况。
(a) 和 (b) 工作相同。
从 (c) 开始，索引 2 处的日志条目追加到 term 2，因为步骤 (a)，我在其中画了一个黄色圆圈。所以它来自于以前的条款。因此，领导者不会根据规则复制该条目（带有黑色十字的黄色 2）。它必须从索引 3 处的条目开始复制。
此规则在图 2“服务器规则”领导者规则 3.1 中也提到：
Send AppendEntries RPC with entries startting at
nextIndex.
nextIndex 用 last log index + 1 初始化，因此它应该从 (c) 处的日志索引 3 开始，而不是索引 2。
因此对于原始(c)处的假设程序，不可能在log 3（第4项处附加的粉红色）复制多数之前将log 2附加到多数。 和 (d) 不会发生。
更新：2020-12-04
@coderx 和@OrlandoL 对 (a)、(b) 以及 S5 如何不能成为领导者进行了讨论。他们的讨论使这个答案更完整，所以我在这里放一个参考。
基本上，（a），（b）不是必不可少的条件，在某些情况下，S5不会选举领导者，例如S3，S4也有同样的机会成为领导者。 （详见评论）
这些假设是正确的，S5 可能不会成为领导者，并且不会发生以下过程。
但是让我们回到论文图 8 并阅读该图的注释：
A time sequence showing why a leader cannot determine commitment using log entries from older terms. In (a) S1 is leader and partially replicates the log entry at index 2. In (b) S1 crashes; S5 is elected leader for term 3 with votes from S3, S4, and itself, and accepts a different entry at log index 2.
IMO，作者说的是S5被选为leader的情况。如此一来，整个过程就成了场景。
正如@OrlandoL 提到的，在 MIT 6.824 实验室中，您应该考虑所有条件以实现正确的 Raft 实现。
希望对您有所帮助。
Raft 不提交前任的条目，因为前任的这些条目可能会被未来的领导者覆盖，就像 (d) 中的领导者 S5。
假设 (c) 中的领导者 S1 在任期 2 的索引 2 处提交了条目，那么该条目将被 S1、S2 和 S3 应用。然后 S1 崩溃了，S5 完全有可能像 (d) 那样成为领导者，因为它的日志比 S2、S3 和 S4 更新。 S5 将用自己的任期 3 条目覆盖索引 2 处的任期 2 条目。这意味着领导者 S5 覆盖已提交的条目！一些服务器（S1、S2 和 S3）已应用该条目对于第 2 项，其他人（S4、S5）将在索引 2 处应用第 3 项的条目，这违反了图 3 中的状态机安全。
因此 (c) 中任期 4 的领导者 S1 不能在索引 2 处提交任期 2 的条目，除非它像 (d) 中那样在索引 3 处提交自己任期的条目，如任期 4 的条目。一旦第 4 期索引 3 处的条目被提交，第 2 期索引 2 处的条目将自动提交，并且它们永远不会被未来的领导者覆盖。 （候选人只有在拥有上一任期的所有已提交条目时才能成为领导者。）