raft算法的混淆

Question

在“寻找可理解的协商一致算法”的论文中，图8显示了(d)和(e)中的一个问题，即一些旧日志可能被覆盖，永远不会返回。

在5.4.2节中，它说“为了消除如图8所示的问题，Raft从不通过计算副本来提交以前术语中的日志条目。只有来自领导者当前术语的日志条目是通过计数副本来提交的；一旦以这种方式提交了来自当前项的条目，那么所有以前的条目都会由于日志匹配属性“”而间接提交。

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

Answer 1

通过将规则添加到图8中。

Raft从不通过计算副本来提交以前条款中的日志条目。

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

​

(a)及(b)工程相同。

从(c)开始，从步骤(a)开始，在项2中添加索引2的日志条目，其中我画了一个黄色的圆圈。因此，，它是从以前的术语，。因此，领队不会按照规则复制该条目(黄色2和我的黑色十字)。它必须从索引3的条目开始复制。

图2“服务器规则”领导人的规则3.1中也提到了这个规则：

发送AppendEntries RPC，条目从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)中，S1是领导者，在索引2中部分复制日志条目。在(b) S1崩溃中，S5在S3、S4和S4本身的中被选为第3学期的领导者，并接受日志索引2的不同条目。

国际海事组织，作者谈论的是S5当选为领导人的案例。这样，整个过程就成了场景。

正如@OrlandoL所提到的，在麻省理工学院6.824实验室中，您应该考虑到所有条件都有一个正确的Raft实现。

希望这能有所帮助。

Answer 2

Raft不提交上一学期的条目，因为上一学期的条目可能会被未来的领导者覆盖，就像(d)中的领导者S5一样。

假设(c)中的领导者S1在第2项的索引2处提交了条目，那么该条目将由S1、S2和S3应用。然后S1崩溃了，S5完全有可能成为像in (d)这样的领导者，因为它的日志比S2、S3和S4更新得多。S5会用自己的条目3覆盖索引2的条目。，这意味着领导者S5覆盖了提交的条目！一些服务器(S1、S2和S3)已经应用了第二学期的条目，其他服务器(S4、S5)则会在索引2处应用第3项条目，这违反了图3中的国家机器安全。

因此，(c)中第4项的领导者S1不能在索引2中提交第2项的条目，除非它提交了自己的项项，如在(d)项中的4项项在索引3处的条目。一旦提交了第4期索引3的条目，第2期的index2条目就自动提交，它们永远不会被未来的领导者覆盖。(候选人只有在有上一届所有已承诺的候选人时才能成为领导人。)