[TOC]

参考资料

1. raft论文原文
2. raft论文中文译文
3. raft毕业论文
4. raft理解
5. 一文带你了解 Raft 一致性协议的关键点
6. Raft 配置变更 Configuration changes
7. 论文细节探究

1. 什么是共识算法

共识算法（consensus algorithm）是复制状态机的背景下提出来的。

复制状态机是通过复制日志来实现的。每一台服务器保存着一份日志，日志中包含一系列的命令，状态机会按顺序执行这些命令。因为每一台计算机的状态机都是确定的，所以每个状态机的状态都是相同的，执行的命令是相同的，最后的执行结果也就是一样的了。如何保证复制日志一致就是一致性算法的工作了。

共识算法就是管理日志复制的算法。在这个方法中，一组服务器上的状态机，计算出相同状态的相同副本，因此即使有一些服务器崩溃了这组服务器也还能继续执行。使用复制状态机的例子有 Chubby 和 ZooKeeper。

应用于实际系统的共识算法一般有以下特性：

• 确保安全性（从来不会返回一个错误的结果），即使在所有的非拜占庭（Non-Byzantine）情况下，包括网络延迟、分区、丢包、冗余和乱序的情况下。
• 高可用性，只要集群中的大部分机器都能运行，可以互相通信并且可以和客户端通信，这个集群就可用。因此，一般来说，一个拥有 5 台机器的集群可以容忍其中的 2 台的失败（fail）。服务器停止工作了我们就认为它失败（fail）了，没准一会当它们拥有稳定的存储时就能从中恢复过来，重新加入到集群中。
• 不依赖时序保证一致性，时钟错误和极端情况下的消息延迟在最坏的情况下才会引起可用性问题。
• 通常情况下，一条命令能够尽可能快的在大多数节点对一轮远程调用作出响应时完成，一少部分慢的机器不会影响系统的整体性能。

Paxos共识算法就是难懂，所以提出了raft共识算法。

2. Raft共识算法基础

2.1. 算法的术语和定义

在raft中，在任何时刻，每一个服务器节点都处于这三个状态之一：

• leader：raft赋予leader全部的管理复制日志的责任来实现一致性。领导人从客户端接收日志条目，把日志条目复制到其他服务器上，并且当保证安全性的时候告诉其他的服务器应用日志条目到他们的状态机中。拥有一个领导人大大简化了对复制日志的管理。例如，领导人可以决定新的日志条目需要放在日志中的什么位置而不需要和其他服务器商议，并且数据都从领导人流向其他服务器。一个领导人可以宕机，可以和其他服务器失去连接，这时一个新的领导人会被选举出来。
• candidate：候选人，用于选举候选人的角色
• follower：他们不会发送任何请求，只是简单的响应来自领导者或者候选人的请求。
  在通常情况下，系统中只有一个领导人并且其他的节点全部都是跟随者。

raft角色转换

在raft中，时间被划分成一个个的任期（term），每个任期的开始都是一次选举的结束，选举成功后，leader会管理整个集群直到结束。raft保证一个任期内至多只有一个leader。

任期是单调递增的，每个节点都会存储一个当前任期号(currentTerm)，在服务器节点通信的时候，会交换任期，如果一个服务器节点的当前任期号小于其他人的当前任期号，则会更新自己的任期号会更大的任期号，如果这个服务器节点刚好是leader或candidate，则会立即转换为follower。如果一个服务器节点发现请求的任期号过期，则会直接这个请求。

2.1.1. 状态（state）

• 所有节点上持久化的状态

状态名	解释
currentTerm	节点上看到的最新任期（term）号，初始为0，单调递增
votedFor	当前任期中，收到投票的候选人Id（没有则为空）
log[]	日志条目数组，每条日志包含一个用户状态机执行的命令，以及leader收到日志时的任期（初始为1）

• 所有机器的易变状态

状态名	解释
commitIndex	最新待提交（commit）的log index，初始为0，单调递增
lastApplied	最新已应用（apply）的log index，初始为0，单调递增

• leader上的易变状态

状态名	解释
nextIndex[]	记录leader向每个节点待发送的日志条目index，初始化为leader最新日志index值+1
matchIndex[]	记录每个节点已复制的最大日志index，初始为0，单调递增

2.1.1. 追加日志RPC（AppendEntries RPC）

leader上调用这个rpc，用以复制日志到其他节点(5.3节)，同时也用于检测心跳(5.2节)。

参数	解释
term	leader的任期
leaderId	leader节点的id，follower用于重定向
prevLogIndex	本次追加日志的前一条日志index
prevLogTerm	本次追加日志的前一天日志所对应的任期
entries[]	追加的日志条目内容（性能考虑，可能是多条批量发送，为空则是用于检测心跳）
leaderCommit	leader的commitIndex

prevLogIndex、prevLogTerm用于保证收到的日志是连续的。

返回值	解释
term	当前任期号，如果大于leader任期，则leader需要更新任期
success	follower包含索引为prevLogIndex且任期为prevLogTerm的日志，则为true

rpc接收端处理逻辑：

1. 如果leader任期小于自己的任期就返回false（5.1节）
2. 如果自己不存在索引、任期和prevLogIndex、prevLogTerm匹配的日志，则返回false(5.3节)
3. 如果存在一条日志索引和prevLogIndex相同，但是任期和prevLogTerm不同，则删除从该位置开始的所有日志(5.3节)
4. 如果leader复制的日志不存在，直接追加
5. 如果leaderCommit > commitIndex，设置本地commitIndex为min(leaderCommit, index of last new entry)

2.1.2. 投票RPC

candidate调用这个rpc，用于收集选票

参数	解释
term	候选人的任期
candidateId	候选人Id
lastLogIndex	候选人最新一条日志的index（5.4小节）
lastLogTerm	候选人最新一条日志的任期（5.4小节）

返回值	解释
term	当前任期，如果大于candidate任期，则dandidate需要更新任期
voteGranted	候选人获得选票则为true

rpc接收端处理逻辑：

1. term小于本地的currentTerm，返回false（5.1小节）
2. 如果votedFor为空或者是候选人Id，并且候选人日志至少和rpc接收端一样新，则设置voteGranted为true（5.2/5.4小节）

2.1.3. 服务器节点的规则

1. 所有节点：
   1. 如果commitIndex > lastApplied，增加lastApplied，并把log[lastApplied]应用到状态机
   2. 如果RPC请求参数或者响应结果包含了term > currentTerm，把currentTerm设置为term，并且角色转为follower
2. follower(5.2小节)：
   1. 响应来自leader或者candidate的请求
   2. 选举定时器超时发生前，没有收到leader的追加日志请求或者没有投票给candidate，则自己转为candidate
3. candidate
   1. 当转换成canditate角色之后，发起选举：
      1. 增加currentTerm
      2. 投票给自己
      3. 重置选举定时器
      4. 发起选举rpc给所有其他节点
   2. 如果获得了过半的选票，则转换为leader
   3. 如果收到其他leader发送的追加日志rpc，则转换为follower
   4. 选举超时，则开始新一轮选举
4. leader
   1. 一旦当选：发心跳给其他所有节点，并且周期地发送心跳，防止选举超时，维持leader地位
   2. 如果收到收到客户端的请求，追加日志到本地log，成功应用（apply）到状态机后，响应客户端
   3. 如果某个follower的最新日志index 大于等于 leader记录的nextIndex，向follower发送nextIndex开始的追加日志rpc
      1. 如果成功，更新leader上对follower记录的nextIndex和matchIndex （5.3小节）
      2. 如果因为日志不一致失败，减小nextIndex并重试（5.3小节）
   4. 如果存在一个N，满足 ( N > commitIndex && 大多数的matchIndex[i] 大于等于N && log[N].term = currentTerm ) ，设置commitIndex为N（5.3/5.4小节）

2.2. 问题分解

为了便于理解，raft将问题分解成四个子问题：

• 领导（leader）选举
• 日志复制
• 安全性
• 成员变化

后续章节会围绕这几个问题进行阐述。

2.3. 特性

特性	解释
选举安全特性	对于一个给定的任期号，最多只会有一个领导人被选举出来（5.2 节）
领导人只附加原则	领导人绝对不会删除或者覆盖自己的日志，只会增加（5.3 节）
日志匹配原则	如果两个日志在相同的索引位置的日志条目的任期号相同，那么我们就认为这个日志从头到这个索引位置之间全部完全相同（5.3 节）
领导人完全特性	如果某个日志条目在某个任期号中已经被提交，那么这个条目必然出现在更大任期号的所有领导人中（5.4 节）
状态机安全特性	如果一个领导人已经将给定的索引值位置的日志条目应用到状态机中，那么其他任何的服务器在这个索引位置不会应用一个不同的日志（5.4.3 节）

3. raft选主

raft使用心跳机制来触发选主。当节点启动的时候，都是follower。如果一个follower收到leader或者candidate的合法请求，它将保持follower状态。如果follower的选举定时器超时之前都没有收到任何请求（如leader的心跳请求），即选举超时，则会发起新的选举。

选举开始的时候，follower会增加自己的currentTerm，然后转换为candidate角色，同时投票给自己，并且并行的向集群中的其他服务器节点发送请求投票的 RPCs 来给自己投票。candidate会继续保持着当前状态直到以下三件事情之一发生：

1. 他自己赢得了这次的选举。candidate获得了大多数选票（大多数原则保证了最多只会有一个candidate赢得此次选举），则成为leader。每一个服务器节点最多会对一个任期号投出一张选票，按照先来先服务的原则（注意：5.4 节在投票上增加了一点额外的限制）。一旦成为leader就会发送心跳rpc来维持自己的leader地位。
2. 其他的服务器节点成为领导者。等待投票阶段，canditate可能从其他节点收到声明它是leader的追加日志rpc，如果canditate的term小于或等于leader的term，则承认其leader地位，并转为follower角色。如果candidate的term大于leader的term，则rpc返回失败状态，且继续保持candidate状态。
3. 一段时间之后没有任何一个获胜的人。选票被瓜分，可能导致本轮选举没有胜出者。每一个candidate因为选举超时会重新发起新的一轮选举。选举超时时间设为一个随机值。降低没有胜出者的概率。

4. 日志复制

每条日志条目除了日志本身，还带有leader收到指令时的任期号，以及一个索引值用于表明在日志集合中的位置。索引值一定是唯一且递增的，相同索引的日志条目内容和任期号相同。任期号用于检测多个日志副本之间的冲突。

一旦有了leader，leader就开始为client服务，并且将客户端的请求，追加到日志中，然后并行地发起追加日志RPC给follower节点，让他们复制这条日志条目。当日志被安全复制后，leader会应用这条日志条目到状态机，然后将执行结果回复client。如果有follower宕机或者运行缓慢或者网络丢包，leader会不断重试追加日志rpc，直到所有的follower都成功复制。

如上所述，leader决定了什么时候把日志条目应用到状态机中是安全的；这种日志条目被称为已提交。一旦日志条目复制到了大多数节点上，leader就会提交并应用该日志条目及其之前的所有条目到状态机，包括其他leader创建的条目。通过这个机制，Raft 算法保证所有已提交的日志条目都是持久化的并且最终会被所有可用的状态机执行。leader记录了将会被提交的日志index，并通过追加日志rpc的commitIndex参数，将其发送给follower。一旦跟随者知道一条日志条目已经被提交，那么他也会将这个日志条目及其之前的日志条目应用到本地的状态机中（按照日志的顺序）。

raft还时刻保证了两个特性，保证了日志匹配原则：

1. 不同节点的日志，如果两个条目的任期和索引一样，那么日志存储的指令一定一样。
2. 不同节点的日志，如果两个条目的任期和索引一样，那么他们之前的所有日志条目也全部一样。

第一个特性来自这样的一个事实，领导人最多在一个任期里在指定的一个日志索引位置创建一条日志条目，同时日志条目在日志中的位置也从来不会改变。第二个特性由附加日志 RPC 的一个简单的一致性检查所保证。在发送附加日志 RPC 的时候，领导人会把新的日志条目紧接着之前的条目的索引位置和任期号包含在里面。如果跟随者在它的日志中找不到包含相同索引位置和任期号的条目，那么他就会拒绝接收新的日志条目。归纳法可以证明第二个特性。

raft中leader处理不一致的方法是强制follower复制leader的日志来解决。也就是说，follower会将冲突的日志覆盖掉。在安全性章节中，会讨论如何通过增加一些限制来保证安全性。为了让follower保持一致，那么leader需要找到两者最后达成一致的地方，然后删除follower上从那以后的日志，辅助自己的日志给follower。follower和leader日志不一致的时候，追加日志rpc就会失败，leader会根据follower返回的信息，减小nextIndex（以任期为粒度减小，不需要one by one），重新发送追加日志rpc。

5. 安全性

前面章节的讨论还不能完全保证leader和follower的一致性。例如，一个跟随者可能会进入不可用状态同时领导人已经提交了若干的日志条目，然后这个跟随者可能会被选举为领导人并且覆盖这些日志条目；因此，不同的状态机可能会执行不同的指令序列。

raft通过在leader选举的时候，增加一些限制来保证了任何的领导人对于给定的任期号，都拥有了之前任期的所有被提交的日志条目（领导人完整特性）。

5.1. 选举限制

raft在投票选举的时候，candidate必须要包含了所有已经提交的条目才可以赢得选举，具体方法是请求投票rpc中增加了一个限制：投票RPC中包含了候选人的日志信息，然后投票人会拒绝为那些日志没有自己新的投票请求投票。candidate为了赢得选举必须联系集群中的大部分节点，这意味着每一个已经提交的日志条目在这些服务器节点中肯定存在于至少一个节点上。如果candidate的日志至少和大多数的服务器节点一样新（这个新的定义会在下面讨论），那么他一定持有了所有已经提交的日志条目。

何为更新的日志：

• 如果两份日志最后的条目任期号（lastLogTerm）不同，那么任期号大的日志更新。
• 如果两份日志最后的条目任期号（lastLogTerm）相同，那么日志索引（lastLogIndex）更大的那个就更新。

currentTerm只是用于忽略老的Term的vote请求，或者提升自己的currentTerm，并不参与Log新旧的决策。 Log新旧的比较，是基于lastLogTerm和lastLogIndex进行比较，而不是基于currentTerm和lastLogIndex进行比较。

5.2. 提交之前任期的日志

raft提交之前任期提交的日志

如图的时间序列展示了为什么领导人无法决定对老任期号的日志条目进行提交。在 (a) 中，S1 是领导者，部分的复制了索引位置 2 的日志条目。在 (b) 中，S1 崩溃了，然后 S5 在任期 3 里通过 S3、S4 和自己的选票赢得选举，然后从客户端接收了一条不一样的日志条目放在了索引 2 处。然后到 (c)，S5 又崩溃了；S1 重新启动，选举成功，开始复制日志。在这时，来自任期 2 的那条日志已经被复制到了集群中的大多数机器上，但是还没有被提交。如果 S1 在 (d) 中又崩溃了，S5 可以重新被选举成功（通过来自 S2，S3 和 S4 的选票），然后覆盖了他们在索引 2 处的日志（如果通过日志副本数判断，任期2的这条日志已经提交，被覆盖就违背了状态机安全特性）。反之，如果在崩溃之前，S1 把自己主导的新任期里产生的日志条目复制到了大多数机器上，就如 (e) 中那样，那么在后面任期里面这些新的日志条目就会被提交（因为 S5 就不可能选举成功）。 这样在同一时刻就同时保证了，之前的所有老的日志条目就会被提交。

如果通过计算副本数目的方式去提交一个之前任期内的日志条目，上图的问题根本在于S1在时序(c) 的任期4内提交了一个之前任期2的log，这样S1提交的日志中最大的term仅仅是2，那么一些日志比较旧的server，比如S5(它最日志的term为 3)，就有机会成为leader，并覆盖S1提交的日志。

为了消除上述的情况，Raft 永远不会通过计算副本数目的方式去提交一个之前任期内的日志条目。只有领导人当前任期里的日志条目通过计算副本数目可以被提交；一旦当前任期的日志条目以这种方式被提交，那么由于日志匹配特性，之前的日志条目也都会被间接的提交。具体到上图中，解决办法就是S1在时序(c)的任期term4提交term2的旧日志时，旧日志必须附带在当前term 4的日志下一起提交。这样就把S1日志的最大term提高到了4，让那些日志比较旧的S5没有机会竞选成为Leader，也就不会用旧的日志覆盖已经提交的日志了。

这里需要注意当前任期的日志已提交状态是通过计算副本数目决定的，因为如果当前任期的日志已提交，那么现在大多数机器都已经有了该日志，且更新了任期，那么leader挂了之后，新主必然是在这些有新日志的机器产生。

5.3. 安全性论证

论文在本小节对领导人完全特性进行论证（过程略过）。通过领导人完全特性，就能证明状态机安全特性。

6. follower和candidate崩溃

目前为止，都只关注了leader崩溃的情况。跟随者和候选人崩溃后的处理方式比领导人要简单的多，并且他们的处理方式是相同的。如果跟随者或者候选人崩溃了，那么后续发送给他们的 RPCs 都会失败。Raft 中处理这种失败就是简单的通过无限的重试；如果崩溃的机器重启了，那么这些 RPC 就会完整的成功。如果一个服务器在完成了一个 RPC，但是还没有响应的时候崩溃了，那么在他重新启动之后就会再次收到同样的请求。Raft 的 RPCs 都是幂等的，所以这样重试不会造成任何问题。例如一个跟随者如果收到附加日志请求但是他已经包含了这一日志，那么他就会直接忽略这个新的请求。

7. 时间和可用性

Raft 的要求之一就是安全性不能依赖时间：整个系统不能因为某些事件运行的比预期快一点或者慢一点就产生了错误的结果。但是，可用性（系统可以及时的响应客户端）不可避免的要依赖于时间。例如，如果消息交换比服务器故障间隔时间长，候选人将没有足够长的时间来赢得选举；没有一个稳定的领导人，Raft 将无法工作。

领导人选举是 Raft 中对时间要求最为关键的方面。Raft 可以选举并维持一个稳定的领导人,只要系统满足下面的时间要求：

广播时间（broadcastTime） << 选举超时时间（electionTimeout） << 平均故障间隔时间（MTBF）

上述不等式中，广播时间指的是从一个服务器并行的发送 RPCs 给集群中的其他服务器并接收响应的平均时间；选举超时时间就是前文介绍选主使用的选举超时时间（超时时间在follower也有用到，follower在选举超时时间内未收到leader的心跳/追加日志 rpc或给某个candidate投票，自己则会变成candidate）；平均故障间隔时间就是对于一台服务器而言，两次故障之间的平均时间。

广播时间必须比选举超时时间小一个量级，这样领导人才能够发送稳定的心跳消息来阻止跟随者开始进入选举状态；通过随机化选举超时时间的方法，这个不等式也使得选票瓜分的情况变得不可能；选举超时时间应该要比平均故障间隔时间小上几个数量级，这样整个系统才能稳定的运行。当领导人崩溃后，整个系统会大约相当于选举超时的时间里不可用；我们希望这种情况在整个系统的运行中很少出现。

广播时间和平均故障间隔时间是由系统决定的，但是选举超时时间是我们自己选择的。Raft 的 RPCs 需要接收方将信息持久化的保存到稳定存储中去，所以广播时间大约是 0.5 毫秒到 20 毫秒，取决于存储的技术。因此，选举超时时间可能需要在 10 毫秒到 500 毫秒之间。大多数的服务器的平均故障间隔时间都在几个月甚至更长，很容易满足时间的需求。

8. 集群成员变化(待更新)

8.1. 一次性变更多个节点

集群成员发生变化，需要让集群节点的配置更新，这个更新过程中， 不能发生一个任期里出现两个leader。不幸的是，任何服务器直接从旧的配置直接转换到新的配置的方案都是不安全的。一次性自动的转换所有服务器是不可能的，所以在转换期间整个集群存在划分成两个独立的大多数群体的可能性（见下图）

raft configure change1

直接从一种配置转到新的配置是十分不安全的，因为各个机器可能在任何的时候进行转换。在这个例子中，集群配额从 3 台机器变成了 5 台。不幸的是，存在这样的一个时间点，两个不同的领导人在同一个任期里都可以被选举成功。一个是通过旧的配置，一个通过新的配置。途中，假设server1是leader，箭头所指的时刻，如果server3和server1的网络出现问题，导致server3转为candidate发起选主，那么server3可能通过server4和server5的投票成为主，进而存在server1和server3两个主。

为了避免上图的情况，配置修改需要使用两阶段方法。raft中，集群先切换到一个叫做共同一致的过渡配置，一旦共同一致的过渡配置已提交，系统就切换到新配置上。共同一致是新老配置的结合。此处不继续展开讨论，可参见[6. Raft 配置变更 Configuration changes]。

8.2. 一次性变更一个节点

在论文中，一次变更多个节点的 Cluser Membership 变更方式并没有更充实的说明（Security、 Avaliable ）。在作者的毕业论文中[3]，详细介绍了一次只能变更一个节点的 Single Cluser MemberShip Change 机制，并且作者也说明了在实际工程实现过程中更加推荐 Single 方式，首先因为简单，再则所有的集群变更方式都可以通过 Single 一次一个节点的方式达到任何想要的 Cluster 状态。开源界raft实现，如ETCD，大都采用这个算法。

[5]在上图中，问题的根本原因在于，在红色箭头处出现了两个不相交的多数派（Server3、Server4、Server 5 认知到新的 5 Node 集群；而 1、2 Server 的认知还是处在老的 3 Node 状态）。在网络分区情况下（比如 S1、S2 作为一个分区；S3、S4、S5 作为一个分区），2个分区分别可以选举产生2个新的 Leader（属于configuration< Cold>的 Leader 以及 属于 new configuration < Cnew > 的 Leader） 。这就导致了 Safty 没法保证；核心原因是对于 Cold 和 CNew 不存在交集，不存在一个公共的交集节点充当仲裁者的角色。

如果每次只允许出现一个节点变更(增加 or 减小)，那么 Cold 和 CNew 总会相交。 如下图所示：

raft configure change2

这个算法有几个要点：

1. 由于 Single 方式无论如何 Cold 和 CNew 都会相交，所以 raft 采用了直接提交一个特殊的 replicated LogEntry 的方式来进行 single 集群关系变更。
2. 跟普通的 LogEntry 提交的不同点，configuration LogEntry 不需要 commit 就生效，只需要 append 到 Log 中即可。
3. 后一轮 MemberShip Change 的开始必须在前一轮 MemberShip Change Commit 之后进行，以避免出现多个 Leader 的问题。

8.2.1. 为何后一轮MemberShip Change必须在前一轮commit之后进行

raft configure change3

如上图所示，如在前一轮 membership configure Change 未完成之前，又进行下一次 membership change 会导致问题，所以外部系统需要确保不会在第一次 Configuration 为成功情况下，发起另外一个不同的 Configuration 请求。( PS：由于增加副本、节点宕机丢失节点进行数据恢复的情况都是由外部触发进行的，只要外部节点能够确保在前一轮未完成之前发起新一轮请求，即可保障。)

8.2.2. Single MemberShip Change LogEntry 只需要 Append 持久化到 Log（而不需要 commit）即可应用

raft configure change4

一方面是可用性方面的考虑，如上图所示：Leader S1 接收到集群变更请求将集群状态从（S1、S2、S3、S4）变更为 （S2、S3、S4）；提交到所有节点并 commit 之后，返回客户端集群状态变更完成（如下状态 a），S1 退出（如下状态b）；由于 Basic Raft 并不需要 commit 消息实施传递到其他 S1、S2、S3 节点，S1 退出之后，S1、S2、S3 由于没有接收到 Leader S1 的心跳，导致进行选举，但是不幸的是 S4 故障退出。假设这个时候 S2、S3 由于 Single MemberShip Change LogEntry 没有 Commit 还是以（S1、S2、S3、S4）作为集群状态，那么集群没法继续工作。但是实质上在（b）状态 S1 返回客户端集群状态变更请求完成之后，实质上是认为可独立进入正常状态。

另一方面，即使没有提交到一个多数派，也可以截断，没什么问题(<font color=red>这里待展开讨论</font>)。
另外还有个问题，Raft 协议 Configuration 请求和普通的用户写请求是可以并行的，所以在并发进行的时候，用户写请求提交的备份数是无法确保是在 Configuration Change 之前的备份数还是备份之后的备份数。但是这个没有办法，因为在并发情况下本来就没法保证，这是保证 Configuration 截断系统持续可用带来的代价。(只要确保在多数派存活情况下不丢失即可（PS：一次变更一个节点情况下，返回客户端成功，其中必然存在一个提交了客户端节点的 Server 被选举为Leader）。

8.3. No-op LogEntry提交

前文讨论过旧任期的日志提交问题。这里简单回顾下。

在 Leader 通过竞选刚刚成为 Leader 的时候，有一些等待提交的 LogEntry （即 SN > CommitPt 的 LogEntry），有可能是 Commit 的，也有可能是未 Commit 的（比如之前任期的日志）。

所以为了防止出现非线性一致性（Non Linearizable Consistency）；即之前已经响应客户端的已经 Commit 的请求回退，并且为了避免出现上图中的 Corner Case，往往我们需要通过下一个 Term 的 LogEntry 的 Commit 来实现之前的 Term 的 LogEntry 的 Commit （隐式commit），才能保障提供线性一致性。

但是有可能接下来的客户端的写请求不能及时到达，那么为了保障 Leader 快速提供读服务，系统可首先发送一个 NO-OP LogEntry 来保障快速进入正常可读状态。

No-op LogEntry在后文【客户端交互】中会再次提到。

9. 日志压缩

日志压缩，一方面可以加速重启恢复速度或新增节点追齐状态速度，一方面是减小节点的压力。

raft snapshot

上图展示了 Raft 中快照的基础思想。每个服务器独立的创建快照，只包括已经被提交的日志。主要的工作包括将状态机的状态写入到快照中。Raft 也包含一些少量的元数据到快照中：最后被包含索引指的是被快照取代的最后的条目在日志中的索引值（状态机最后应用的日志），最后被包含的任期指的是该条目的任期号。保留这些数据是为了支持快照后紧接着的第一个条目的附加日志请求时的一致性检查，因为这个条目需要前一日志条目的索引值和任期号。为了支持前文提到的集群成员更新，快照中也将最后的一次配置作为最后一个条目存下来。一旦服务器完成一次快照，他就可以删除最后索引位置之前的所有日志和快照了。

尽管通常服务器都是独立的创建快照，但是领导人必须偶尔的发送快照给一些落后的跟随者。这通常发生在当领导人已经丢弃了下一条需要发送给跟随者的日志条目的时候。幸运的是这种情况不是常规操作：一个与领导人保持同步的跟随者通常都会有这个条目。然而一个运行非常缓慢的跟随者或者新加入集群的服务器将不会有这个条目。这时让这个跟随者更新到最新的状态的方式就是通过网络把快照发送给他们。

9.1. 安装快照rpc

9.1.1. 请求接口

参数	解释
term	leader的任期
leaderId	leader节点的id，follower用于重定向
lastIncludedIndex	快照中包含的最后日志条目的索引值
lastIncludedTerm	快照中包含的最后日志条目的任期号
offset	分块在快照中的字节偏移量
data[]	从偏移量开始的快照分块的原始字节
done	如果这是最后一个分块则为 true

9.1.2. 返回接口

返回值	解释
term	当前任期号，如果大于leader任期，则leader需要更新任期

9.1.3. 接收者实现

1. 如果term < currentTerm就立即回复
2. 如果是第一个分块（offset 为 0）就创建一个新的快照
3. 在指定偏移量写入数据
4. 如果 done 是 false，则继续等待更多的数据
5. 保存快照文件，丢弃具有较小索引的任何现有或部分快照
6. 如果现存的日志条目与快照中最后包含的日志条目具有相同的索引值和任期号，则保留其后的日志条目并进行回复
7. 丢弃整个日志
8. 使用快照重置状态机（并加载快照的集群配置）

10. 客户端交互

这一节将介绍客户端是如何和 Raft 进行交互的，包括客户端如何发现领导人和 Raft 是如何支持线性化语义的。这些问题对于所有基于一致性的系统都存在，并且 Raft 的解决方案和其他的也差不多。

Raft 中的客户端发送所有请求给领导人。当客户端启动的时候，他会随机挑选一个服务器进行通信。如果客户端第一次挑选的服务器不是领导人，那么那个服务器会拒绝客户端的请求并且提供他最近接收到的领导人的信息（附加条目请求包含了领导人的网络地址）。如果领导人已经崩溃了，那么客户端的请求就会超时；客户端之后会再次重试随机挑选服务器的过程。

我们 Raft 的目标是要实现线性化语义（每一次操作立即执行，只执行一次，在他调用和收到回复之间）。但是，如上述，Raft 是可以执行同一条命令多次的：例如，如果领导人在提交了这条日志之后，但是在响应客户端之前崩溃了，那么客户端会和新的领导人重试这条指令，导致这条命令就被再次执行了。解决方案就是客户端对于每一条指令都赋予一个唯一的序列号。然后，状态机跟踪每条指令最新的序列号和相应的响应。如果接收到一条指令，它的序列号已经被执行了，那么就立即返回结果，而不重新执行指令。

只读的操作可以直接处理而不需要记录日志。但是，在不增加任何限制的情况下，这么做可能会冒着返回脏数据的风险，因为领导人响应客户端请求时可能已经被新的领导人作废了，但是他还不知道。线性化的读操作必须不能返回脏数据，Raft 需要使用两个额外的措施在不使用日志的情况下保证这一点。首先，领导人必须有关于被提交日志的最新信息。领导人完全特性保证了领导人一定拥有所有已经被提交的日志条目，但是在他任期开始的时候，他可能不知道哪些是已经被提交的。为了知道这些信息，他需要在他的任期里提交一条日志条目。Raft 中通过领导人在任期开始的时候提交一个空白的没有任何操作的日志条目（No-op log entry）到日志中去来实现。第二，领导人在处理只读的请求之前必须检查自己是否已经被废黜了（他自己的信息已经变脏了如果一个更新的领导人被选举出来）。Raft 中通过让领导人在响应只读请求之前，先和集群中的大多数节点交换一次心跳信息来处理这个问题（多一次rpc势必带来不小的开销）。可选的，领导人可以依赖心跳机制来实现一种租约（lease read）的机制，但是这种方法依赖时间来保证安全性（假设时间误差是有界的）。更多的实现方案讨论，见同目录的文章——【Raft线性一致性读实现方案】。