Raft共识算法

发表于 |

本文来自我的文章分布式一致性和分布式共识协议太长，因此将其中的Raft部分单独列出来作为一篇文章。

Raft协议的设计者们认为Paxos协议非常难于理解，并且需要作出很多修改才能够应用到工程中，因此设计了偏重于实现的Raft协议，这甚至体现在他们的论文标题《In Search of an Understandable Consensus Algorithm(Extended Version)》上，此外作者也提供了一个C++版本的实现liblogcabin。Raft协议主要分为三个模块，Leader election、Log replication和Safety。
Raft将服务器节点分为Leader、Candidate和Follower三种，协调者被称为领袖/主(Leader)，参与者被称为群众(Follower)。相对于其他的协议，Raft中的Leader更强，这体现在：

  1. Leader是唯一的。
  2. Log entries只能从Leader发送给其他服务器，事实上Follower不主动发送，而只响应来自Leader和Candidate的请求。
  3. 客户端只能和Leader交互，如果客户端首先连上了Follower，那么会被Follower转发给Leader。
  4. Raft的独特之处还在于其在Leader election的过程中Raft使用了随机计时器进行超时。此外，Raft还提供了一个joint consensus的算法处理Membership changes的问题。

Raft基础概念

状态

Raft协议要求在每个节点上维护以下的状态：

共有状态

注意currentTerm、votedFor、log[]这三个状态是持久化的，其他的则是volatile的。

  1. currentTerm
    这个在后面的讨论中非常常用，表示了当前服务器已知的最新任期。
  2. votedFor
    顾名思义。
  3. log[]
    这个是日志，是我们需要维护一致性的对象。
  4. commitIndex
    已知的最大的已经被提交(Commit)的日志条目的index。
    对Follower来说，这个是根据来自Leader的AppendEntriesRPC中的leaderCommit字段来更新。
  5. lastApplied
    一旦commitIndex > lastApplied，那么就将[lastApplied + 1, commitIndex]区间里的日志条目依次apply到复制状态机上。我们这里仍然要特别注意提交(commit)与应用(apply)区别。一个是针对日志，一个是针对RSM。

Leader专用状态

  1. nextIndex[]：对于每一个服务器，Leader下一个需要发送给它的日志条目的索引值。初始值（当某个节点成为Leader后进行这项初始化）为Leader的logs.size()。在一些实现中会使用commitIndex + 1。
  2. matchIndex[]：对于每一个服务器，已经复制给他的日志的最大索引值。初始值为-1，这个值是非常保守的。
    这两个值是Leader用来同步各Follower的日志的，但是当一个节点成为Leader时，它实际上并不知道其他节点上的日志情况，所以它给出的值都是需要调整的。这个调整的过程非常巧妙，它是和日志复制一同进行的。我们将在Log replication部分详细说明。

任期

Raft中的Leader具有任期term机制，每个term只会对应一个Leader，所以可以通过term唯一标识这个Leader。每个节点维护有自己已知最新的currentTerm，出于网络分区等原因，它不一定是全局最新的。服务器之间通信时会交换各自的任期号，根据论文5.1节，如果一个节点检查到自己的currentTerm小于对方在RPC（包括Request和Response）中附带的term，则更新到较大的任期值；相对应地，如果检测到自己的大于对方的，则忽略对方的请求。当一个Leader发现自己具有过期的任期时，它会立刻切换成Follower。
注意，一个有较大任期号的RequestVote请求并不意味着发送该请求的节点是Leader。但是一个较大任期号的AppendEntries请求一定是来自Leader的，因为只有Leader会发送AppendEntries。

一个有趣的问题（一个离题的讨论）

在Raft编程实践中，当节点收到一个Candidate的RequestVote请求时更新term的做法，在判断选举结束时会有一些麻烦。一般地，假如观测Candidate节点，当它收到足够的票数时我们能够知道新Leader被决议出来，并且就是自己。但假如我们观测Follower节点，那么当它第一次收到新Leader合法的AppendEntries心跳时我们知道新Leader被决议出来，并且是发送方。但我们发现第一次和第二次并不是那么好区分，因为无论是第几次，我们观测的节点始终是Follower，而term也始终没有变（不然说明Leader又换了）。所以我们会使用另外的状态leader_name来维护Leader的名字，并在第一次收到心跳时设置其值为发送方，在丢失Leader或发现选举开始时将其值清空。这样我们就可以通过值是否为空来判断是否是第一次收到心跳了，于是我们能够准确找出选举结束的时刻。

日志与日志约束

来自客户端的请求被表示成一系列将被应用到复制状态机上的指令，这些指令在Raft集群的所有节点上被记录为日志条目(Log Entries)。在每个日志条目中记录了对应的term以及是否该条目已经被提交。Raft协议下要求日志满足以下的约束（论文图3），这些约束贯穿Raft整个算法，并且是相互密不可分的。

  1. 领导人只附加原则(Leader Append-Only)（论文节5.3详细论述）
    Leader绝对不会删除或者覆盖自己的日志，只会增加。上文中已经说了在Log replication部分会介绍一个Leader优雅的逐步同步Follower的日志，以求达到和自己一致的方法。而这换句话说也就意味着当Leader和Follower不一致时，永远是Follower顺应Leader，此时Follower的日志可能会被Leader覆盖。
  2. 日志匹配原则(Log Matching)（论文节5.3详细论述）
    这个原则包含以下两个小点：
    1. 如果不同节点上的日志中的两个条目具有相同的index和term，那么这两个条目的内容是一致的。
      这个特性为下面的领导人完全性提供了必要保证。
      我们知道一个日志条目必然是由某个Leader在某个index创建的，根据领导人只附加原则，每个领导人在index创建的日志条目必然是unique的，因为日志的删除和覆盖不被允许。而在论述任期机制时我们又知道term是能唯一标识Leader的。综上，可以仅根据index和term唯一标识一个日志条目。
    2. 如果不同节点上的日志中的两个条目具有相同的index和term，那么这两个日志index前的部分也相同。
      这是由AppendEntriesRPC这个RPC中prevLogIndex和prevLogTerm两个字段保证的。当一个AppendEntriesRPC命令到达时，Follower会比较自己是否具有prevLogIndex和prevLogTerm所标记的条目，如果没有（这意味着诸如Leader宕机等情况导致的诸如没有能够全部复制到所有节点的情况）则拒绝这次添加（此时AppendEntriesRPC失败了），并且会削减掉自己已知的不符合Leader日志的部分（可以查看后文有关AppendEntriesRPC的部分）。因此每一次的AppendEntriesRPC都会附带一次check，从而保证了这条性质，有点类似于归纳法(induction)。
      根据日志匹配原则，我们在实现时可断言logs.size() == logs.back().index() + 1 == last_log_index() + 1。除非出现了Log compact的情况，这也是我们在实现时应当小心使用log.size()和logs[]的原因。
  3. 领导人完全性(Leader Completeness)
    这个特性是Raft的一个核心特性。如果某个日志条目在某个term中已经被提交，那么这个条目必然出现在所有具有更大的term的Leader中，在这里已提交是必须的，我们将在Log replication中进行详细说明。这个规定实际上保证了选出的Leader拥有所有已经提交的日志条目，容易看出，我们先前的领导人只附加原则实际上为这个特性提供了条件。
    根据这篇文章的介绍，我们发现领导人完全性是Raft容易实现的一个重要原因。通过领导人完全性原则，Raft协议不再允许日志空洞，也就是说Leader必须含有全部已提交记录，一个日志落后的节点不可能被选为Leader。而在Paxos协议族中的一些协议是允许具有日志空洞的节点成为Leader，再在后面异步地填自己的日志空洞的。而在Raft中，只有Leader通过AppendEntriesRPC单向向全部Follower复制日志。
  4. 状态机安全特性(State Machine Safety)
    如果一个Leader已经apply了位于index的日志条目，那么没有任何服务器可以在这个index上apply一个不同的日志条目。
    状态机安全特性实际上保证了所有的服务器都会按照相同的顺序提交相同的日志给RSM（论文5.4.3节旁注）。事实上根据领导人完全性可以证明状态机安全性，首先一个被apply的日志必须是已提交并与Leader相同的。如果某个较早term上的日志条目被apply的话，日志匹配原则能够保证所有之后term对应的Leader都拥有相同的日志条目，因此他们稍后也会apply相同的日志条目。
    Raft协议保证一旦条目被提交，那么它是持久化的(durable)（不会被丢失或更改），并且一定会被所有可用的复制状态机执行（论文5.3节）。

选举限制(论文5.4.1节)

再次总结一下，上面四点日志约束实际上保证了在Raft中的日志是连续的，中间不会出现空洞。Raft的论文提到除了Leader-based的共识算法，其他的共识算法并不保证这个特性，例如Viewstamped Replication（此外，还有基于zxid的Zookeeper协议）中，日志是可以拥有空洞的。对于这些协议，需要有一个额外的机制来方便性Leader找回空洞处日志。

要求日志连续，实际上方便了Follower和Leader之间的同步过程，所有的日志复制是单向从Leader到Follower的，Leader只需要关注Follower上一次的同步位置即可。而在选举过程中，我们也只需要比较最后一个log的index和term即可，不需要去比较其他的日志条目了。这也是Raft协议在实现上方便性的来源之一，但也可能会导致一些性能问题。

在上文中可以看到，实际上通过选举来保证领导人完全性原则，也就是只有拥有全部已提交日志的Candidate才有可能胜选，注意，未提交的日志无所谓。因为Candidate至少需要majority票，所以一旦它当选了，说明每一条被提交的日志，会出现在其中至少一台Server上。如果说这个Candidate的日志不比majority中任何其他节点的旧，那么他必然持有了所有的已提交日志。

【注】这里如何日志的新旧，查看“【如何比较日志新旧】”说明。

RPC

Raft中定义了两种主要的RPC包，AppendEntriesRPC和RequestVoteRPC。

AppendEntriesRPC

AppendEntriesRPC具有心跳包和推送日志的作用。此外，通过AppendEntriesRPC还可以发现选举产生的新Leader，可以参考先前讨论任期时提到的有趣的问题。这个RPC包含以下部分

  1. term
    表示Leader的当前任期号。为了表示区别，**下面写作rpc_term_id**。
  2. leaderId
    表示当前领导人的id，这样来自客户端的请求能被Follower转发给Leader。
  3. prevLogIndex和prevLogTerm
    表示新日志条目之前的index和其对应的term，这个是为了保障先前提到的日志匹配原则。Leader在构造这两个字段时实际上是根据自己维护的nextIndex[]和matchIndex[]来计算的。
  4. entries
    entries就是我们要维护的日志条目。
  5. leaderCommit
    表示Leader已经提交的日志的序号，这样其他的服务器才能知道Leader当前的提交位置，并跟随提交。
    注意Leader可能已经Commit了我还没有的日志，即我们不能assert(request.leader_commit() <= last_log_index())(可以参考我的代码)。

AppendEntriesRPC Response

Follower在接受到该RPC后会发送回执：

  1. term表示当前的任期号
  2. success
    表示这次添加是否成功，它的判定规则如下：
    1. 当rpc_term_id < term时返回false，显然我们不接受一个较老的Leader。
    2. 当不存在满足prevLogIndex的条目时返回false。这个暗示Leader要发靠前一点的Log。
    3. 即使存在prevLogIndex的条目，但这个条目的term不同于prevLogTerm时，删除从prevLogIndex开始的所有项目。
      这里的“不同于”是非常重要的，如果Follower拥有Leader发来的所有的Entries（也就是Leader的更短），他也是不能删除自己后面的Entry的。当Follower收到RPC时，prevLogIndex肯定是可能大于等于Follower的log大小的，例如Leader收到了Client的新Log。但prevLogIndex也是可能小于Follower的，最普遍的一种情况是Leader刚选举出来，还在试探Log。还有一种情况是Follower拥有了先前某个Leader复制的一些Log，而当前的Leader没有。还有一些情况是我们收到了经历了时延的RPC，这曾经导致我希望对RPC编号来解决这个问题，但实际上没必要。在我的代码中，会列举这些情况，以及相关日志。
    4. 添加所有我们log中没有的条目。
    5. 同步leaderCommit。
    特别地，对于心跳包，我们同样应当进行这样的检测。

RequestVoteRPC

  1. term
    表示Candidate的任期号
  2. candidateId
    表示Candidate的id
  3. lastLogIndex和lastLogTerm
    表示Candidate的最后日志条目的index和term，每个投票者会比较对方是否新于自己的，从而进行投票。

RequestVoteRPC Response

投票者在接受到该RPC后会基于term和投票规则进行判定，并发送回执

  1. term
  2. voteGranted表明是否同意

Leader election

投票过程

在2PC中我们看到，参与者必须对协调者有timeout机制，否则整个系统会阻塞，Raft同样有这样的功能，并且Raft的election timeout是在150ms-300ms之间随机的，且每个节点不同。Leader存活时会不停的往所有的节点发送RPC心跳包，考虑一个节点在election timeout时间中没有接到心跳包的情况。站在全局的角度来看，这可能是老Leader挂了，所以得选举出一个新的Leader出来；这也可能是网络延迟/分区的原因，因此可能在选举途中或者结束后老Leader又回来了。但站在这个节点的角度来看，它只能认为Leader已经挂了，因此成为Candidates参加Leader选举。此时它执行下面两个操作：

  1. 递增自己的currentTerm
  2. 发送RequestVoteRPC消息给所有节点，这时候节点们根据一定规则进行投票

【Q】对于一个合法的RequestVote请求，我们需要更新自己的term么？
根据Raft论文中的“Rules for Servers”条目，只要我们在RPC中发现了一个更新的term，就需要更新自己的term。

成为Leader需要获得整个集群共$N$个节点中过半数（$\ge N/2+1$，例如3个节点则需要两个，4个节点则需要3个）的票，才能成为新的Leader，这是为了保证最多只会有一个Candidate赢得选举。投票可能产生三种结果：

  1. 自己成为Leader
    获得过半数票的节点自动成为Leader，并开始发送心跳包，也就是entries字段为空的AppendEntriesRPC。如果其余的节点发现rpc_term_id大于等于自己的currentTerm时就可以知道已经选出一个新主了，此时选举结束，Candidate重新变为Follower，并同步自己的currentTerm与新主一致。
    假设先前是老Leader发生网络分区从而导致选举的产生，在新Leader产生后网络又恢复了。此时他收到了来自新Leader的心跳包。显然这个心跳包中的rpc_term_id比老Leader自己的currentTerm要大，根据任期的约束，老Leader知道了新Leader的存在，切回Follower状态并更新任期。如果老Leader在发现新Leader依然履行了一次职责，发送了一个AppendEntriesRPC。首先它会被Candidate和已经发现新Leader的节点拒绝，因为它们的任期号肯定比老Leader的要大。
  2. 别人成为Leader
    对应于第一种情况，此时自己发现了大于等于自己的Leader传来的心跳，于是自己退出选举。
  3. 没有Leader产生
    这发生在没有节点获得过半数的票的情境下，例如有很多Follower的timeout时间比较接近，在选举开始时都timeout变成了Candidate，这时候每个Candidate都会投给自己，所以没有Candidate能获得大多数。此时认为currentTerm + 1届的任期以没有Leader告终，节点们开始下一轮的election timeout。由于每个节点election timeout时间都是随机的，所以下一次出现timeout时间接近的可能性并不高。

投票原则

在上一节中我们提到收到RequestVoteRPC请求的节点会根据一定规则进行投票，事实上这是非常重要的，因为我们需要维护领导人完全性的原则。在Raft原论文中，这一部分是放到Safety章节来说明的，因此有必要在阅读此部分时首先查看Log replication章节。

Log replication部分的一个规则：当Leader创建的某日志条目被成功复制到过半数的服务器上时，Leader才能提交该条目。那么，一个Candidate必须得到过半数的节点的支持才能当选。因为这样才能保证每一个已经提交的日志条目必然存在在这里面至少一个节点上。

【如何比较日志新旧】下面进行另一个断言：

  1. 如果两份日志最后的条目的term不同，那么term大的日志新。
  2. 如果两份日志最后的条目term相同，那么日志长的那个就新。
  3. 如果一个Candidate的日志和大多数的节点至少一样新，那么它一定持有了所有已经提交的日志条目。

具体原因我们在稍后讨论，现在这个断言描述了给VoteFor某个RequestVoteRPC的条件：

  1. 远端的term（也就是在RequestVoteRPC传递的）不能小于自己的term
  2. 远端的lastLogTerm不能小于自己的lastLogTerm
    注意这个条件不能省略，因为脑裂的节点可以无限增加自己的currentTerm，所以实际上仍然需要通过比较日志来决定谁是最新的。
  3. 如果远端和自己的lastLogTerm相等，那么远端的lastLogIndex不能小于自己的lastLogIndex

注意，有时候一个刚竞选成功的Leader会收到同term的Candidate的Vote请求，而它会给一个Candidate投票。参考下面的log。这应该是一个错误的实现导致的，**当Leader竞选成功时，不需要重置其vote_for**。

Log replication

一旦由当前Leader创建的某日志条目被成功复制到过半数的服务器上时，这个Leader可以Commit该条目及自己日志中该条目之前的所有条目（论文5.4.2节会提到一些细节证明）。这里要求至少过半数实际上为前面的选举投票顺利进行提供了保障，剩余的节点（可能因为宕机或者脑裂没收到）可以在后面慢慢AppendEntries。不需要全部成功复制的原因会在Safety中进行论证。有意思的是即使先前的条目可能是由其他Leader创建的，但这也不影响提交。马上可以看到，这种方式实际上是唯一正确提交较旧的term的日志条目的方法。

在AppendEntriesRPC中，Leader还通过leaderCommit字段来告知所有的Follower自己当前的提交位置，每个服务器会试图在本地提交直到commitIndex的日志。注意到有的服务器可能在本地并没有这个commitIndex的日志，因此它只能提交到自己最新日志条目的index位置。在更新完后，每个节点会更新lastApplied，从而将新的commitIndex后面的日志条目应用到复制状态机上。在apply之后，Leader便可以向客户返回结果。

不能提交来自较旧任期的日志条目(论文5.4.2节)

Leader在commit了一条日志后，立刻宕机会怎么样呢？

Leader在commit了一条日志后，立刻宕机会怎么样呢？，我认为领导人完全性(Leader Completeness)要求如果某个日志条目在某个term中已经被提交，那么这个条目必然出现在所有具有更大的term的Leader中。因此不具备该entry的节点不可能被选举为新Leader。所以这个被commit的日志在后续的raft流程中肯定还是commit的。但是注意新Leader不能提交来自较旧任期的日志条目。

另外，还需要注意commitIndex是volatile的。在紧随其后的一节中，将看到已经被存储到大多数节点中的较旧的日志条目也可能被未来的Leader所覆盖掉。但因为“不能提交来自较旧任期的日志条目”，所以在c阶段是不能Commit的。这就导致安全性并没有被破坏，如果不Commit和Apply，Client也就一直不知道成功还是失败，所以即使将来Commit的时候这个版本被覆盖掉，大不了就告诉Client失败了呗。

进一步讨论：论文5.4.2节

如果一个LogEntry已经出现在多数节点上，那么可以认为它已经被Commit了么？
上一章节已经知道不可以这样认为，因为已经被persist到majority节点中的较旧term的LogEntry也可能被未来的Leader所覆盖掉。因此，此时不能告诉客户端该LogEntry已经成功Commit了。

通过这个性质，保证了两点：

  1. 不会丢失数据
    领导人完全性要求不能丢失已经Commit的数据。为了满足这个性质，在这种情况下，我们就不Commit了。
  2. 不会读未提交
    无论是通过写日志来读，还是ReadIndex，我们都有了一个参照，就是如果Noop被提交了，那么Noop之前的日志是已提交的。

我们来看这个经典的对Figure8的讨论。

下面的一张图来自原论文的Figure8，展示了当前Leader对具有较旧的term的日志条目进行提交时的一种情况。其中一个已经被存储到大多数节点中的较旧的日志条目(c阶段中的term 2 index 2)也会被未来的Leader(d term 3 index 2)覆盖掉。这也是在提到领导人完全性原则时我们强调了已提交三个字的原因。

  1. (a)
    首先查看a阶段，此时S1是Leader（被粗黑框框中），生成一个黄色块的条目并复制给S2，此时由于未超过半数，所以S1不能进行提交。
  2. (b)
    S1未能继续复制黄色条目而崩溃了，此时S5透过S3、S4和S5的选票成为Leader（此时S1已挂，而S2的lastLogIndex和lastLogTerm会让它反对S5）。S5紧接着创建了一个蓝色块条目放到了索引2处，此时如果S5继续复制它的蓝色方块，那么S1和S2的黄色方块肯定会被覆盖掉，不过在这个例子中S5都没来得及复制就挂掉了。
  3. (c)
    S1恢复了，此时它的term是4，最大。S1因为lastLogTerm更大，所以可以得到S4的票。此外，它的lastLogTerm和S2的一样，且lastLogIndex也和S2一样，所以还能获得S2的票。因此S1成功当竞选。
    现在进入图上的c阶段，这时候S1继续它复制黄色log的未竞伟业，同时创建了一个红色块。S1将黄色log继续复制给S3，这时候如果假设可以提交较旧的条目，S1已经可以提交黄色块了。
  4. (d)
    如果S1又挂了，因此不仅没能成功提交黄色块，连红色块都没来得及复制，这就进入了d阶段。S5恢复了，此时它的lastLogTerm最大，因此通过S2、S3、S4当选。这时候它稳定了，于是覆盖了所有的黄色和红色LogEntry。
    可以深入看到这个不一致性，Index为2处的日志被覆盖式地提交了两次，分别是蓝色和黄色。
  5. (e)
    如果S1成功复制了日志到S2和S3，这就对应了e阶段。此时红色的LogEntry就能提交了。

如何解决这个问题呢？Raft禁止提交一个较旧的term的条目，即使它已被复制到大部分节点。我们来看看这条规则是如何进行修复的：

  1. (c)
    c阶段中，S1的term是4，但是它不能提交term 2 index 2这个日志。当然，它还是可以继续复制这条日志的。
    只有当term 4 index 3这条红色的Entry被复制到大多数之后，才可以提交。
  2. (d)
    d阶段中，蓝色Log，即term 3 index 2已经被复制到所有机器上了，但是S5仍然不能哪怕是提交自己之前Append的日志。

说说这里我的个人理解，我认为这个原因是因为一个冲突：

  1. Raft的投票原则是基于lastLogTerm和lastLogIndex的，也就是说谁大谁是Leader，才有尝试提交日志的权力。而Follower只能被动更新leaderCommit。
  2. 一个被复制到大多数节点上的日志，未必具有一个最新的log term。那么新当选的Leader完全可以不respect这个日志。

而新的Leader提交了一条日志，实际上就在日志层面固化了自己的“存在”。

为什么不 persist commit index？

被复制到大多数节点，并不意味着被Commit，我们可以参考课后习题的第2题来进一步了解。Raft协议中并没有把commitIndex作为一个需要persist的内容，这是因为commitIndex作为一个易失字段并不影响Raft的正确性：

  1. 如果一个新Leader“接盘”了，如何确定哪些log已经被提交了呢？
    很简单，添加一个no-op操作就行。
  2. 其他节点可以读取leaderCommit来确定commit到的log位置
    注意某些Follower可能没有到leaderCommit的所有日志。

再次强调，commitIndex是不可能倒退的。虽然，在一些issue中可以看到，保存commitIndex可以实现快速的恢复。但事实上，从课后习题的第2题中可以看到，在Leader切换的时候，很难精确判断哪些日志是能被Commit的，哪些是不行的。所以我们借助于提交一条Noop来避免这种模棱两可的情况。

幽灵复现

在paxos中，讲到了幽灵日志的问题。

对日志不一致问题的处理

下面关注Leader的复制请求的结果。其实通过前文已经知道，在正常情况下，Leader的日志始终是和Follower的一致的，所以来自Leader的AppendEntriesRPC始终会是成功的。但一旦Leader或者Follower出现崩溃或者网络发生脑裂，日志就会处于不一致状态。例如有些Follower会比Leader少条目或多条目，这时候就违背了日志匹配原则，导致失败，我们稍后看到这个失败实际上会被用来进行恢复一致性的工作。多条目看起来不可思议，但如下图所示，f就是一种情况，多出来的三个term为2的条目，这是可能是由于它是term为2时的Leader，并且添加了一些日志，但是在提交前崩溃了。

对于这种不一致的状态，Raft有简单粗暴的方法来处理，就是强制Follower直接复制Leader的日志，这同时也是领导人只附加原则的要求。而这么做的保证则来自于根据领导人完全性原则，Leader能选举出来就意味着是具有完全的日志的。因此现在的思路就是把Follower一直删到满足日志匹配原则的点为止。

在这个同步过程中，nextIndex[]和matchIndex[]就派上了用场。nextIndex[]维护了Leader下一个需要发送给Follower的日志序号，当Leader刚选举成功时，它是不知道各个Follower的日志相对于自己的情况的，因此默认nextIndex[]都为自己最后一条日志加一。但这样发出去的日志可能不会被接受，原因是根据之前提到过的日志匹配原则，如果Follower没有Leader的最后一条日志，那么它必然不能匹配Leader发送的AppendEntriesRPC中的prevLogIndex和prevLogTerm所标记。因此它会返回给Leader一个拒绝，此时Leader就会减小对应的nextIndex并重试。特别注意这个过程中Follower的日志有可能被Leader覆盖的。Raft论文指出这里可以进行优化（论文5.3节旁注），但这个优化并不是很必要的，因为现实中失败很少发生，而且也不大可能会造成很多的日志不一致的问题。

容易看出，这种算法是非常优雅的，因为它把恢复一致性的过程和正常增加日志的过程统一起来了，我们不需要对恢复一致性过程额外进行设计，可想而知这个额外设计是相当麻烦的，因为还要考虑在回复一致性过程中出现失败的情况。

有关强制复制日志的细节

由于实现细节的问题，可能会导致MIT 6.824 Lab2的TestFigure8Unreliable2C过不了，可以查看代码的on_append_entries_request函数的847-881行(node.h)，对比下一个commit。

其实这里有个简单的场景，比如AppendEntries的发生了reorder。第一次收到的是[1,2,3]，第二次收到的是[1,2]，不能把3给删除掉。

Safety

这一部分的论述对应了原论文安全性论证部分，证明了上面的Leader election和Log replication的算法是可靠的。

有关领导人完全性的论述 论文5.4.3节

利用反证法证明领导人完全性，也就是已经被提交的日志必定出现在 term 更大的 Leader 的日志中。
提出反命题：存在一个 term 为 T 的 Leader 提交的日志条目没有被其后的某个 term 为 U 的 Leader 所拥有。不失普遍性地，假设中 U 是第一个没有这个日志条目的任期，也就是说所有这中间 term 的 Leader 都保有这个日志条目。
进行下面的推导：

  1. 根据领导人只附加原则，这个记录在 U 竞选时就不存在在 U 的日志中。
  2. 考虑到这个日志条目已经被提交，所以 Leader T 一定已经把它复制到过半数的集群上了；同时考虑到 Leader U 当选，所以它也收到了过半数的票。因此至少有一个节点它既拥有 Leader T 的日志条目又投票给了 Leader U。
  3. 现在考虑这个投票者。它必然在投票给 Leader U 前接受了来自这个 Leader T 的日志。
    如果它在投票后才接受到来自 Leader T 的 AppendEntriesRPC，那么它肯定会拒绝这条RPC。因为当收到来自 Leader U 的 RequestVoteRPC 时，这个投票者就已经更新自己的 currentTerm 了。因此现在它的 currentTerm 肯定大于 RPC 中的 rpc_term_id，即 T。
  4. 这个投票者在投票时也保留了这个来自 Leader T 的日志。
    而 Follower 只有在日志和 Leader 冲突时才会丢日志。
  5. 既然这个投票者给 Leader U 投票，那么 Leader U 的日志必然不会比投票者的日志要旧。接下来从 index 更大和 term 更新两种情况来讨论。
  6. 首先，假如投票者和 Leader U 当前的 term 是相同的，那么 Leader U 就会拥有更大的 index，也就是日志更长。既然如此 Leader U 应当具有投票者当前所有的日志。推出矛盾。
  7. 其次，如果 Leader U 的最后一条日志的 term 要比投票者的最后一条日志大。并且是要大于 T 的，因为投票者的最后一条日志的 term 至少是 T，因为投票者拥有那一条 Leader T 在任期内提交的日志。现在，Leader U 的最后一条日志一定来自于一个 T 之后的 Leader，因为 term 更大。而这个 Leader 一定拥有 T 这个日志，这是根据我们的假设。那么根据日志匹配原则的要求，Leader U 也应当包含这个日志条目。推出矛盾。

有关非Leader节点故障的讨论 论文5.5节

Follower 和 Candidate 节点的故障是相对简单的：

  1. 如果还未完成 RPC 就宕机
    在重启后，可以继续完成。
  2. 如果完成了，但还没有回复
    在重启后，仍然会收到相同的 RPC。因为这个是幂等的。

有关可用性的讨论 论文5.6节

  1. RPC 的 broadcast time 应该远小于选举超时时间。
  2. 选举超时时间应该远小于 MTBF
    MTBF 指的是一个 Server 每一次 Fail 的时间间隔。这是为了使得整个集群能向前推进，因为当 Leader 挂掉之后，系统至少会 unavailable 一个选举超时。

有关脑裂和网络分区的讨论

由于某些节点的失效，部分节点的网络连接会断开，并形成一个与原集群一样名字的集群，这种情况称为集群脑裂(split-brain)现象。这个问题非常危险，因为两个新形成的集群会同时读取和修改集群的数据。Raft 能够解决由于网络分区导致的脑裂，从脑裂过程中和脑裂恢复后两个阶段来讨论。

  1. 在脑裂过程中，Raft 仍然保证了至少 $N/2+1$ 的共识。特别地，当网络分区多于两块的时候，会不会存在有两个分区中都选出了新的 term 相同的 Leader 呢？这是不可能的，因为成为 Leader 必须达到全局多数 $N/2+1$ 张票，最多只能有一个。所以当分区较多的时候，很可能无法选出新 Leader。另外某节点也不容易去“获得当前分区的多数票”，因为它也无法界定当前分区的范围。
  2. 脑裂恢复遵循 Raft 选举，所以不会导致日志出错。

尽管如此，老 Leader 可能会给客户端返回老数据。例如老 Leader 被分在了少数派中，多数派中可以选出一个新 Leader，并提交一些新的日志。这时候老 Leader 还是可以响应用户请求的，毕竟它不知道新 Leader 的产生，也就无法转发请求给新 Leader。这样老 Leader 就返回了旧的数据给用户。这里强一致被破坏了，可以通过下面的方式来解决：

  1. Leader 需要提交一个日志才能返回读请求。
  2. ReadIndex 或者 LeaseRead。

Membership changes

Joint Consensus

相比整体下线集群在重新启动的方法，Raft提供另一个方案。为了保障安全性，我们需要在新旧配置的过渡期间确保四个基本原则的基石之一，Leader与term一一对应不会被打破。论文指出直接做切换时不现实的，如下图所示，当集群规模从3变为5时，存在时间点使得集群分划为两个部分，其中绿色部分使用旧配置$C_{old}$进行选举，蓝色部分使用新配置$C_{new}$进行选举。因此Raft使用两个阶段实现配置转换。

两阶段的转换有很多种方法，例如可以在第一阶段禁用旧配置，然后在新阶段启用新配置，这样在两个阶段之间系统不能响应客户请求。Raft的解决方案是第一阶段切换到一个过渡的称为joint consensus的配置上，当joint consensus被提交之后，系统再转换到新配置上，这样就不会存在新老配置共存的问题。joint consensus阶段要求如下：

  1. 日志条目应当被复制到对应到新旧两种配置的所有机器上。
  2. 两种配置中的任意服务器都可以作为Leader。
  3. 选举和提交日志的共识必须同时经由两种配置的多数同意。也就是说要得到两种配置下各自的过半票数。

在下图中，虚线部分表示已创建未提交的日志配置条目，实现部分表示被提交的配置条目。可以看到配置转换过程被分为三个阶段：

  1. 从Leader收到配置变更请求到在$C_{old, new}$被提交前
    此时单独根据$C_{old}$决议。
    首先，Leader在收到配置变更请求后，生成一个表示$C_{old, new}$这个配置的日志条目，并按照通常的方式AppendEntry。一旦这个日志提交成功，集群进入joint consensus状态。特别地，节点只要收到新配置的AppendEntry就会切换到新配置，无论这个AppendEntry有没有被提交。因此提交成功只是说明进入了joint consensus状态，此时很多节点已经切换到了配置$C_{old, new}$。
    当Leader提交了配置$C_{old, new}$对应的日志条目时，它一定是使用的这个配置进行的决议。当Leader在这一阶段崩溃时，新选举的Leader可能是$C_{old, new}$，也可能是$C_{old}$。
  2. 在$C_{new}$被提交后到配置变更完成
    此时单独根据$C_{new}$决议。
    特别地，如果Leader使用$C_{new}$配置的话，这个时间节点可以提前到$C_{new}$被创建。
  3. 在1和2的中间阶段，即joint consensus状态
    在这一阶段配置$C_{old, new}$已被提交，此时$C_{old}$退出舞台。由于Leader已被提交，所以领导人完全性原则保证了没有$C_{old, new}$的Candidate注定选举失败。此时Leader节点可以安全地去AppendEntry配置$C_{new}$的条目了。

几个 Issue

  1. 刚加入的新节点没有日志
    这里指的是计算多数的时候不考虑新节点的投票权。此时它们仅接受日志的复制，不参与包括 commit、vote 之类的投票。
    当然，对于 vote 而言，就算计算票数，这些落后的节点也应该投赞成票。
    对于复制 log 场景，通常的实现会引入 Learner 机制，让节点先追上日志，再 promote 成为 Voter。但这个优化一定是需要的么？我想未必。因为 Leader 只要在新旧 quorum 中都达到多数就可以 commit 了。
  2. Leader 不在新配置里面
    当 Leader 提交完 $C_{new}$ 后，就要 Step Down 回到 Follower 状态。这也说明了有一段时间 Leader 会去管理一个不包含自己的集群。
  3. 删除节点
    被删除的节点不会收到来自 Leader 的 RPC 了，因此可能会超时，继而发送 RequestVoteRPC 来竞选，从而影响可用性。为了解决这个问题，所有节点可以忽略这些投票请求，直到他们认为现在存在一个 Leader。
  4. 只要收到并持久化完新配置的 Entry 后，该节点就要以新配置执行，而无论配置是否已经提交
    这是因为只有当每个节点在 AppendEntry 完之后生效，才能保证 Leader 在 Commit 完这个 Entry 之后知道这个配置生效了。如果等到 Commit 之后再生效，那么 Leader 就没有机会知道什么时候生效了。

实现

liblogcabin的实现方案是列出一个Configuration类，这个类包含以下几个关键信息

  1. Configuration::State state
    这是个enum类型，包含四种可能值BLANK、STABLE、STAGING、TRANSITIONAL。分别对应于集群初始化、正常运行、Issue1的解决方案和joint consensus状态。
  2. quorumAll()
    是否获得当前配置下的多数票，这里需要根据TRANSITIONAL分类讨论。

一定需要两步么？

有一种单步变更方案，也就是每一次只添加或者删除一个节点，从而避免 joint consensus。这个方案的直觉是每次只修改一个节点，那么 $C_{new}$ 和 $C_{old}$ 不可能形成两个不相交的多数派。

但很遗憾这种方式是存在漏洞的，并且构造很简单。不妨假设按照 $C_{new}$ 来提交 confchange entry，也就是 confchange entry 提交需要的 quorum 包含被添加的节点。这个构造比较简单，类似于 Figure8：

  1. 假设需要往集群中先后加入两个节点 u 和 v，当 term=0 的 Leader 即下面的 ori_0 添加完 u 节点后，它可能只将这个 confchange entry 复制给了 u，然后就宕机了。
  2. 然后新选举出的 term=1 的 Leader 即下面的 ori_1 添加节点 v，这个时候它将 confchange entry 复制给了包括 v 在内的节点，并且正好达到 quorum。比如假设原集群大小为 4，添加 v 之后大小为 5，那么 {ori_1, ori_2, v} 就是这样的一个 quorum。然后它可以提交一些日志，然后它也宕机了。
  3. 之后，term=0 的 Leader，即 ori_0 又重启了，显然它并没有收到 term=1 的 Leader 的任何 entry，包括添加 v 在内的 entry。但是它依然可以被选举为 term=2 的 Leader。比如在上面的例子中，它可以通过 {ori_0, ori_3, u} 选举成功。
  4. 容易看出，这就是一个 Figure8 的 case 了。因为 term=2 的 Leader 并没有 term=1 的 Leader 已经提交的 entry，所以它会命令 {ori_1, ori_2} 将它们删除。因此，添加 v 节点的这条日志就被删除了。

解决方案很简单，就是和 Figure8 一样，新 Leader 必须先提交一条日志之后，再进行成员变更。

问题来了，如果按照 $C_{old}$ 老配置来提交，会避免这个问题么？我认为答案是肯定的。但这会导致减少成员时，需要更大的 quorum。比如从 4 个节点变为 3 个节点，那么用 $C_{new}$ 则 quorum 会从 3 变成 2，而用 $C_{old}$ 则 quorum 始终是 3。

Log compaction

Raft采用了Snapshot的方法来实现日志压缩，具体来说是每个Follower自己做Snapshot。这种方法是独立于Raft的Strong Leader的原则的，这是由于每个节点的Snapshot的状态对Leader来说是透明的。
论文中指出这样做是合乎情理的，这是由于用来做Snapshot的东西都是从状态机跑出来的，是经过一致性检验的，不会存在冲突。Snapshot只是Follower去reorganize自己数据的行为。此外，由Leader创建日志而非Follower创建日志有以下的弊端：

  1. 网络开销
    这是因为Leader要将Snapshot复制到每个Follower，而这是冗余的，因为Follower实际上有全部信息。
  2. 实现复杂

InstallSnapshot

当Leader发现Follower[i]的next_index已经严重落后，落到了自己的snapshot里面，即满足 next_index[i] <= get_base_index() 时，就应当发送InstallSnapshot RPC催促其补上。这个RPC应当包含Leader自己持久化的log，并且应该是已经提交了的。

当Follower收到这个RPC时首先进行例行判断，例如term是否大于等于自己的current_term并更新，否则拒绝。如果自己是Candidate要切换回Follower，重新超时等等。接着直接dump下来Leader的snapshot。

一个Snapshot表示state machine到last_included_index为止的状态，因此last_included_index必须位于已apply（而不是commit）的日志。在创建snapshot之后，我们可以将直到last_included_index的所有日志压缩成一个日志。

持久化

我们需要区分持久化persist和快照snapshot技术。persist指持久化论文Figure2列出的vote_for、current_term和logs三个状态。特别注意诸如commit_index是volatile的。

关于持久化的问题

为什么必须要持久化voteFor

见习题6

为什么必须要持久化term

显然，恢复后简单设置term为0肯定是不行的。
那么如果我们设置term为log里面最新的term，是否可以呢？答案肯定也是不可以。
在这里修改了知乎上一个例子。假设有机器S1、S2和S3，其中S1和S2是分区的（注意S1/S3，S2/S3这两个是连通的）。

  1. S1成为Leader
    显然，是通过S3的票上位的。S2因为分区，并没有收到请求，因此保持term为0。
  2. S1添加了<1,1,a>，即index为1，term为1，内容为a
  3. S1没有进行任何复制就宕机了，但没有恢复
  4. S3也宕机并重启了
    因为S3没有缓存之前的term即1，所以读取log，发现为空，即term为0
  5. 在新一轮选举中S3成为Leader
    可以发现，是S2投票的。S1这个时候还在宕机呢。
  6. S3添加了<1,1,b>，并且提交了
  7. S3宕机了
  8. S1和S3从宕机中恢复了
    此时，S1的日志是<1,1,a>，S2和S3的日志是<1,1,b>。那么原则上S1和S3都有可能成为Leader。那么<1,1>处的日志到底是a还是b呢？

为什么必须要持久化logs

见习题6。

为什么不需要持久化commitIndex

见“有关领导人完全性的论述(论文5.4.3节)”。
持久化 commitIndex 的好处是在宕机重启后，能够知道可以 apply 到哪里。不然就得跑一轮算法才能更新到 commitIndex 了。

为什么不需要持久化lastApplied

我认为这个取决于我们状态机的实现。
如果我们的状态机做不到幂等，那我觉得重启之后lastApplied是0，再搞一遍，肯定就有问题。

其他问题

网络要求

我目前认为 raft 可以跑在 reorder 的网络上，例如 udp。我确实遇到过一些 reorder 的问题，但后来被证明是实现所致，如 下面这个问题

Supposed order:

  1. Leader -> A, entry 1
  2. Leader -> A, heartbeat, prev_log_index = 1
  3. Leader -> A, entry 2
  4. Leader crash

Arrived order:

  1. Leader -> A, entry 1
  2. Leader -> A, entry 2
  3. Leader -> A, heartbeat, prev_log_index = 1
    Problem may arised if we mistakenly erased entry 2.
  4. Leader crash

Note that entry 1 could already be committed, so in this case, we will mistakenly erase a committed entry.

Peer A will only commit upto min(leaderCommit, lastLogIndex).

Raft的优化

优化选举

Prevote

Prevote 是 Follower 在超时进入 Candidate 状态前的行为。此时 Follower 进入 PreCandidate 状态，进行一轮 Prevote。只有当 Prevote 获得大多数节点的赞同时，Follower 才会正式超时。Prevote 的引入减少了由于网络抖动等因素导致的主节点切换现象。

优化写日志

减轻 Leader 压力

Raft 要求 log 必须被持久化。其实在如 Kudu 的实现中，Leader 的日志未必要持久化。实际上只要有 Quorum 个节点持久化了日志，Leader 也可以提交，从而减少自己的磁盘负担。

Batch

Batch 策略指将多个来自客户端的请求打包到一个 Raft Log 中。这有点类似于 WriteBatch 写入。

异步Append

这里的异步指的是可以先并行发送 log 给所有的 Follower，然后在 Append 给自己。

Pipeline

在有关复制状态机的介绍中已经介绍了有关 Pipeline 的机制。

当 Leader 向 Follower 发送了一个 AppendEntries 请求之后，它需要等待返回才能更新 next_index 从而继续后面的流程。Pipeline 允许 Leader 在发送一个请求之后立即更新 next_index，从而不等待返回以发送后面的请求。这么做的原因是认为网络在大多数情况下是正常的。但如果不幸在过程中出了问题，就可能需要重新发送 log。

在这样的实现中可以在 RPC 消息的回复中附带上 last_log_index 和 last_log_term。

优化Apply

异步Apply

使用一个新线程去 Apply 已经 Commit 的 log。
这么做的好处是，前面的 Append Log Entry 部分和 Apply 分离了，能提高吞吐量。
注意，因为 Raft 不允许日志空洞，以及顺序 Commit 的特性，导致可以认为已经 Commit 的日志就可以 Apply，但对于诸如 MultiPaxos 这样允许日志空洞的协议是不行的。

乱序Apply

见分布式一致性详解。

exact once 语义

优化 InstallSnapshot

Follower Snapshot

由 Follower 节点而非 Leader 节点发送 Snapshot。这种做法能够降低 Leader 的负担。

增量 Snapshot

在发送 Snapshot 时，不发送全部的数据，而是根据 Follower 当前存储中的数据版本，去发送增量的数据。

优化成员变更

成员变更的一阶段办法

需要被正确实现，见前面的论述。

Learner

刚加入的节点，需要追日志或者 Snapshot，从而才能赶上 Leader 的进度。这个过程可能对 Quorum 产生影响，从而影响可用性。例如，从 3 变成 4 时，Quorum 会从 2 变成 3。因为新增的节点在追日志，所以无法提供 commit 的票数，因此这要求老节点的三个 Node 一个都不能坏，实际降低的可用性。

解决方案是新节点作为 Learner 追日志，不参与投票。

优化读

Leader 的 ReadIndex

Leader 在返回结果之前，需要询问一遍 quorum，确认自己此时还是 Leader。

Follower 的 ReadIndex

又称为 Follower Read 或者 Learner Read。

当上层支持事务时，Follower Read 可以变为给定事务的 start_ts，提供事务对应 write 记录的 commit_index。

注意，即使 apply index 超过了之前请求的 commit index，那么也不破坏线性一致性。因为它没有破坏“一旦某个读操作返回了某个特定值，那么后续的读操作要么返回这个值，要么返回后面的写对应的值”。

ReadIndex 和线性一致

Lease Read

Lease Read 和 Follower Read 的相互影响

Waitfree

Raft 的缺陷的讨论

日志和选举

Paxos 引入的 proposal number n 标注了 proposal value v 的版本。如果存在已知的 proposal value v，那么发送 accept 请求时必须带上已知的最大的 v。

可以看到，Paxos 对 v 的决议过程和 Leader 是没有关系的。在 Ongaro 等的 MultiPaxos 构造中可以看到，他们使用了 firstUnchosenIndex 来记录某个 Server 已知的第一个没有被 chosen 的 entry，Leader 会首先推动这个 entry 上的 Paxos 算法。换句话说，如果像 MultiPaxos 那样管理日志，就可以看做启动多个 instance 去决议多个 v。那么并不一定需要一个 Leader，就更不用说什么“领导人完全性”原则了。

但如果把决议 v 的值不看做是某个日志条目，而是选出后续负责管理日志复制任务的 Leader 的 id（比如像 Palf 那样选出后续 clog Leader），就可以发现 Paxos 的“选举”是多阶段的，而 Raft 的选举是一阶段的。Paxos 之所以这样做，是为了引入 order，让 proposal number 更大的 v 能够 override 掉比它小的，最终胜出的就是被 chosen 的值。

除此之外，可以看出，Raft 本身相对于 Basix Paxos 多了定序的功能。它之所以能够定序，是因为有了 Leader。Leader 通过日志将 Order 持久化了。

Raft 则不一样。首先我们不在讨论 term，因为它是用来比较两次不同的选举的。那么决定一个 Leader 是否能当选，不再是它用什么样的 n 去发送 Prepare 请求，而是它自己日志的新旧程度，这是一个确定值。Raft 的四个原则统一起来，起到的作用之一就是让日志可以作为比较节点新旧的工具。 换句话说，Raft 选举的实质是谁状态更新，谁就更容易当选。这个方案目前来看，无论是否效果最优，但确实代价比较大。

Leader or not?

Basic Paxos 和 EPaxos 实际上是不需要一个 Leader 的。但在工业界，选择一个 Leader，让它去协调所有的决议，会是一个更加简便快速的方案。共识算法未必要服务于所有决议的决策过程，这也是 Onganro 等在博士论文中指出的那样。

Raft习题讲解

MIT6.824

见MIT 6.824做题笔记。

官方习题

本习题来自于作者的博客，知乎提供了中文版。

1

下面四幅图中，哪些 Server Configuation 在 Raft 中是合法的呢？

a 是不合法的，这是因为 term 应该是递增的。创建 index=4 的 Leader 一定是从一个 term 大于等于 3 的 Leader 中获得 index=3 的条目的，我认为，AppendEntriesRPC 附有当前 Leader 的 term，当 index=4 的 Leader 在添加 index=3 的条目时候，它的 term 必然不会小于当前 Leader 的 term，即 3。
d 是不合法的，Raft 日志不允许空洞，但 Paxos 允许。

2

下面哪些日志是可能被安全地 apply 的？我们把机器从上到小编号为 S1 到 S5。

首先，我们现在的 term 是4。在这个任期中，Leader 创建了一个<7,4>，没有达到 quorum，这个肯定是提交不了的。
用类似的办法，通过比较 quorum，可以排除到只剩下面5个条目，用 <Index,Term> 表示如下。

1
<1,1>, <2,1>, <3,2>, <4,2>, <5,2>

我们知道，“当Leader创建的某日志条目被成功复制到过半数的服务器上时，Leader可以提交该条目”，但我们不能忽略Figure8的情况，即“不能提交来自较旧任期的日志条目”，所以要等到<7,4>被提交之后，才能安全提交S1的1到5的日志。
后来看答案发现，题目不是这个意思，比如说commitIndex是volatile的，没啥讨论的意义。所以题目的意思是，从一个全局的视野，根据Log判断哪些Entry是可以被安全地commit的。实际上，虽然我们有了Leader for term 4，但由于这个Leader可能没来得及提交<7,4>就Fail，导致重新选举，到时候新Leader可能就不是它了。所以这个问题等价于从日志判断讨论Leader可能是谁，然后我们假设这些节点分别成为了Leader，可能移除掉哪些Entry。
S1：LastLogTerm为4，秒杀所有，足够quorum。
S2：LastLogTerm秒杀除S1外所有，足够quorum。
S3：它的LastLogTerm比S4要大，有1票；它的LastLogTerm和S5一样，此时需要比较LastLogIndex，这个比不过S5，因此总共2票，不够quorum。
S4：它的LastLogTerm比S1/S2/S3/S4要小，只有1票，不够quorum。
S5：它的LastLogTerm比S4要大，有1票；它的LastLogTerm和S3一样，但是LastLogIndex比S3大，因此总共3票，足够quorum。

下面，我们就要在S1、S2和S5中间取一个交集。特别地，如果S2当选，可能会移除掉S1现有的从index=3开始的所有条目。这也对应了我们“已经被存储到大多数节点中的较旧的日志条目也可能被未来的Leader所覆盖掉”的论述。
综上，只有1和2是可以safely applied的。

从这个case可以看出，不能通过判断Leader的Majorty的matchIndex来判断哪些日志是可以提交的。例如，我们可以假设S1短暂成为Leader，此时matchIndex为3的节点有S1、S3、S5三个。但我们不能认为<3,2>就可以被提交了，因为可能S1马上挂掉，然后S2选举成功，把这些日志全部干掉了。

3

下图显示了一个6台服务器集群中的日志，此时刚刚选出term为7的新Leader。对于图中每一个Follower，给定的日志是否可能在一个正常运行的Raft系统中存在？
首先，我们确定一点，就是index=1和2的日志条目是已经被提交了的。
a是不合法的，因为违背了日志匹配原则。事实上因为a的<5,3>和选出的Leader是Match的，因此它前面index=3和4的term也应该和Leader是Match的，即都是3。
b是不合法的，原因类似于a。
我认为c是不合法的，因为此时Leader的term才是5，怎么可能会出现一个term为6的条目呢？但是我这里做错了，c是合法的，而且我看错了，现在Leader的term是7。例如，当大家都只具有日志<1,1>, <2,1>的时候（但不一定就是这个条件），其实c可能自己是term为6的Server，它在还没有来得及复制自己任期内的日志的情况下就挂掉了。
d是不合法的，因为term没有单调递增，可以参考第一条。
e是合法的，原因类似于c，其实它可以看做是最一开始的Leader，然后被分区了。

4

假设硬件或软件错误破坏了 Leader 为某个特定 Follower 存储的nextIndex值。这是否会影响系统的安全？
我认为是不会的，因为nextIndex的设计就是volatile的。
事实上，如果nextIndex太小，相当于Leader发送了多余的日志，AppendEntriesRPC会返回一个成功，此时Leader就会增加nextIndex，这样通过有限次AppendEntriesRPC，nextIndex就会重新收敛到准确值。
如果nextIndex太大，AppendEntriesRPC会返回一个失败，此时Leader会减小nextIndex。
事实上，当一个Leader新被选举出时，他就是通过这种机制得知每个Follower的nextIndex的。
当然，我们也没必要每次逐一递增或者递减，我们在正文部分提到过一些优化点。

5

假设你实现了Raft，并将它部署在同一个数据中心的所有服务器上。现在假设你要将系统部署到分布在世界各地的不同数据中心的每台服务器，与单数据中心版本相比，多数据中心的Raft需要做哪些更改？为什么？
这个题目我还真不知道怎么回答，贴一下标准答案。
We’d need to set the election timeouts higher: my expected broadcast time is higher, and the election timeout should be much higher than the broadcast time so that candidates have a chance to complete an election before timing out again. The rest of the algorithm does not require any changes, since it does not depend on timing.

6

【这一条主要考察Raft三个持久化项目的原因】

每个Follower都在其磁盘上存储了3个信息：当前任期（currentTerm）、最近的投票（votedFor）、以及所有接受的日志记录（log[]）。

a. 假设Follower崩溃了，并且当它重启时，它最近的投票信息已丢失。该Follower重新加入集群是否安全（假设未对算法做任何修改）？

这个是不安全的，事实上我也犯过类似的错误，即Leader election/投票原则 这个章节列出的问题。7104成了Leader，但是重置了voteFor，导致后面投票给了7103，从而出现了两个Leader。
其实还有一个节点S2会既投票给S1又投票给S3的场景，假设一个容量为3的集群，即S1和S2票了S1成为Leader，但是S2迅速重启，并且忘了投票给S1，此时S2收到了S3的投票请求，并投票给了S3，此时S3也会称为Leader。

b. 现在，假设崩溃期间Follower的日志被截断（truncated）了，日志丢失了最后的一些记录。该Follower重新加入集群是否安全（假设未对算法做任何修改）？

这个是不安全的。容易发现，丢失最后一些记录的影响是有可能成为Majority的日志条目达不到Majority了。而又因为根据题目2的思路，我们可以（也只能）单纯通过日志判断哪些日志条目是可以被安全提交的，所以这些达不到Majority的日志可能在丢失前已经被提交，但在丢失后被认为没有提交。

在答案中，还举例解释了可能的后果，即这会导致这些被提交的entry被覆盖。同样地，对于一个3节点的集群：
S1作为term2的Leader，添加了index=1的条目<1,2,X>，X是这个条目的内容。稍后，由于这个记录已经被复制到了S1和S2，所以它被成功提交。
此后，S2重启，并丢失了所有记录。
后面由于一些网络抖动的因素，S1被分区，S3变成了term3的Leader（通过S2和S3的票，因为他们的LogEntries都是空），然后它添加了index=1的条目<1,3,Y>，这个条目同样可以被提交。那么此时index=1处的值既被提交为了X又被提交为了Y，不一致性发生了。

7

即使其它服务器认为Leader 崩溃并选出了新Leader后，老Leader依然可能继续运行。新的 Leader 将与集群中的多数派联系并更新它们的term，因此，老的Leader将在与多数派中的任何一台服务器通信后立即下台。
然而在此期间，它也可以继续充当Leader，并向尚未被新Leader联系到的Follower发出请求；此外，客户端可以继续向老的Leader发送请求。
我们知道，在选举结束后，老的Leader不能commit任何新的Log Entry，因为这样做获得多数派中的至少一台服务器的认可。但是，老的Leader是否有可能执行一个成功AppendEntries RPC，从而完成对选举开始前收到的旧日志记录的提交？如果可以，这是否会给Raft协议带来问题？

这个题目描述的场景我没有真实遇到过，所以只能分析。首先老Leader的RPC只能发给少数派Follower，这些Follower也并未知晓新Leader的产生。但是如果新选出的Leader有包含老Leader的旧日志的话，那么其实这些旧日志是能够达到Majority的要求的。但对于是否会被覆盖这一点，我并没有什么结论。

看答案，实际上是可能存在这种情况的，这也发生在新Leader包含了老Leader这一部分的日志。
在答案中给了一个具体的例子，涉及到一个5个节点的集群。
S1，日志为空，通过S1、S2和S3的票成为了term2的Leader。稍后，它添加日志<1,2,X>，并且复制到S2。
此后，这个S2通过S2、S4、S5的票成为了Leader。这里按照投票原则，S3也应该会投票的啊？其实S3和S1被分区了。
在这之后，S1完成发送<1,2,X>到S3，在此时，S1完成了<1,2,X>的提交，即使它不再是这个term的Leader了。这个论述其实和我上面的论述是一致的，而下面给出了为啥不会被覆盖的论证。

这个是安全的，因为新Leader也具有老Leader提交的Entry，这会导致这个Entry被持久化，这是因为：
这Entry肯定也在一些给新Leader L投票的机器S上存在，并且必须在S投票之前就存在。log completeness check要求在投票时检查对端的lastLogTerm和lastLogIndex必须至少都大于等于自己的。下面我们分类讨论：
如果L是S之后的第一个Leader，那么必然有L.lastLogTerm == S.lastLogTerm && L.lastLogIndex >= S.lastLogIndex，即L拥有S拥有的所有Entry，包括我们担心的那一条。
如果L是S之后的第二个Leader，那么如果他从前一个Leader M中收到了Entry，那么必然有 L.lastLogTerm > S.lastLogTerm，但是M肯定在复制自己的Entry之前，就已经将我们担心的那一条日志复制给了L，因此这也是安全的。由此扩展，我们可以推论到任何其他的Leader。

8

在配置变更过程中，如果当前Leader不在C-new中，一旦C-new的日志记录被提交，它就会下台。然而，这意味着有一段时间，Leader不属于它所领导的集群（Leader上存储的当前配置条目是C-new，C-new不包括 Leader）。假设修改协议，如果C-new不包含Leader，则使Leader在其日志存储了C-new时就立即下台。这种方法可能发生的最坏情况是什么？

首先，下台意味着什么呢？在C-new之前，C-old已经结束使命，配置C-joint已被提交，任何决议的提交都需要经过new和old的过半数的同意才行。那么下台意味着只要C-new日志被Leader存储，它就立即变成Follower，那么这个集群不再具有Leader，从而会发生选举，选举也是按照C-joint来选举的。考虑如果选出一个在C-old中的Leader，那么它会重复之前的流程，增加一个C-new，然后下台。这个流程会一直重复到C-old中的Majority都得到了C-new日志，这样剩余没有C-new日志的C-old机器也不能被选举为Leader了。这里注意，我们在讨论一个最坏的情况，就是每一次选举都是C-old中被选中，并且也不进行任何复制，因此所有C-new中的所有机器都没有收到C-new的日志。所以产生的结果就是最坏会有|C-old/2|次冗余选举。

Reference

  1. https://mp.weixin.qq.com/s?__biz=MzIzOTU0NTQ0MA==&mid=2247494453&idx=1&sn=17b8a97fe9490d94e14b6a0583222837&scene=21#wechat_redirect
    有关幽灵日志的相关内容
  2. https://github.com/ongardie/raft.tla/blob/master/raft.tla
    关于Raft的TLA的内容
  3. https://www.zhihu.com/question/382888510
    讲解了为什么currentTerm需要持久化
  4. https://zhuanlan.zhihu.com/p/47025699
    有关幽灵日志的讨论
  5. http://oceanbase.org.cn/
    郁白在OB的实践
  6. http://oceanbase.org.cn/?p=160
    成员变更
  7. https://thesquareplanet.com/blog/students-guide-to-raft/

    The if here is crucial. If the follower has all the entries the leader sent, the follower MUST NOT truncate its log.