Raft 协议详解

重点了解：三个子问题、两个实际问题、三种角色、选主的五种角色转换

Raft 是一种用于替代 Paxos 的 共识算法，使用 Quorum 机制来实现共识和容错
能为在计算机集群之间部署有限状态机提供一种通用方法，并确保集群内的任意节点在某种状态转换上保持一致

相比于 Paxos，Raft 的目标是提供更清晰的逻辑分工使得算法本身能被更好地理解
同时它安全性更高，并能提供一些额外的特性

1. 三个子问题

Raft 核心算法由三个子问题组成的：选主（Leader election）、日志复制（Log replication）、安全性（Safety）
这三部分共同实现了 Raft 核心的共识和容错机制

选主（Leader election）

Raft 集群必须存在一个主节点（Leader），客户端向集群发起的所有操作都必须经由主节点处理
没有主节点集群就无法工作，所以应该先票选出一个主节点，才能再去考虑其它事情

日志复制（Log replication）

那主节点（Leader）需要承载什么工作呢？
它会负责接收客户端发过来的操作请求，将操作包装为 日志 同步给其它节点
在保证 大部分 节点都同步了本次操作后，就可以安全地给客户端回应响应了
这一部分工作在 Raft 核心算法中叫日志复制 （ Log replication ）

安全性（Safety）

然后，因为主节点的责任是如此之大，所以节点们在选主的时候一定要谨慎，只有 符合条件 的节点才可以当选主节点
此外主节点在处理操作日志的时候也一定要谨慎
为了保证集群对外展现的一致性，不可以 覆盖或删除 前任主节点已经处理成功的操作日志
所谓的谨慎处理，其实就是在选主和提交日志的时候进行一些限制，这一部分在 Raft 核心算法中叫安全性 （ Safety ）

2. 两个实际问题

在实际的应用中，还需要解决不断增在的日志问题，以及动态更变成员问题
Raft 分别给出解决方案：日志压缩 （ Log compaction ）和集群成员变更 （ Cluster membership change ）

日志压缩（解决日志无限增长问题）

Raft 将操作包装成为了日志，集群每个节点都维护了一个不断增长的日志序列，状态机只有通过重放日志序列才能得到
但由于这个日志序列可能会随着时间流逝不断增长，因此我们必须有一些办法来避免无休止的磁盘占用和过久的日志重放
Raft 采用了快照的方式来减少不断积累的日志，这一部分叫日志压缩

两阶段切换集群成员配置（解决集群成员动态更变问题）

一个 Raft 集群不太可能永远是固定几个节点，总有扩缩容的需求，或是节点宕机需要替换的时候
直接更换集群成员可能会导致严重的 脑裂 问题
Raft 给出了一种安全变更集群成员的方式：两阶段切换及群成员配置。这一部分叫集群成员变更

3. 三种角色

Raft 集群中每个节点都处于以下三种角色之一：

• Leader : 所有请求的处理者，接收客户端发起的操作请求，写入本地日志后同步至集群其它节点
• Follower : 请求的被动更新者，从 Leader接收更新请求，写入本地文件
  如果客户端的操作请求发送给了 Follower，会首先由 Follower 重定向给 Leader
• Candidate : 如果 Follower 在一定时间内没有收到 Leader 的心跳，则判断 Leader 可能已经故障
  此时启动 Leader Election 选主过程，本 Follower 节点切换为 Candidate 直到选主结束

4. Term 和 Index

4.1 Term（任期）

与 ZAB 的年代 Epoch 相似，用来唯一标识当前的 Leader（一个 term 也可能没有 Leader）
每开始一次新的选举，称为一个任期，每个 term 都有一个严格递增的整数与之关联

每当 Candidate 触发 Leader election 时都会增加 term
如果一个 Candidate 赢得选举，他将在本 term 中担任 Leader 的角色

但并不是每个 term 都一定对应一个 Leader
有时候某个 term 内会由于选举超时导致选不出 Leader，这时 Candicate 会递增 term 号并开始新一轮选举

Term 更像是一个逻辑时钟（logic clock）的作用
有了它，就可以发现哪些节点的状态已经过期
每一个节点都保存一个 current term，在通信时带上这个 term 号

4.2 Index（索引）

与 ZAB 的计数器相似，用来唯一标识一个 Leader 任期期间的所有日志
每一个新的日志都对应一个唯一的 index

5. 通信消息类型

节点间通过 RPC 来通信，主要有三类 RPC 请求

• RequestVote RPCs : 用于 Candidate 拉票选举
• AppendEntries RPCs : 用于 Leader 向其它节点复制日志以及同步心跳
• InstallSnapshot RPC ：用于 Leader 同步其他节点的快照

6. 选主的五种角色转换

• 转化图（五条线）

  

• 详细转换规则

  • 选主发生时，首先发生 Follower 向 Candidate 的转换
  • 选主超时时，发生 Candidate 向 Candidate 的自我转换
  • 选主成功时，发生 Candidate 向 Leader 的转换
  • 选主时收到其他自称是 Leader 的消息，且判断为合法，发生 Candidate 向 Follower 的转换
  • 选主后，认为自己是 Leader 的节点收到其他 Leader 的消息，且判断为合法，发生 Leader 向 Follower 的转换

4.1 选主基本概念

**选主（Leader election）**就是在分布式系统内抉择出一个主节点来负责一些特定的工作
在执行了选主过程后，集群中每个节点都会识别出一个特定的、唯一的节点作为 Leader

和其它一致性算法相比，Raft 赋予了 Leader 节点更强的领导力，称之为 Strong Leader
比如说日志条目只能从 Leader 节点发送给其它节点而不能反着来，这种方式简化了日志复制的逻辑，使 Raft 变得更加简单易懂

Raft 的选主基于一种心跳机制，集群中每个节点刚启动时都是 Follower 身份
Leader 会周期性的向所有节点发送心跳包来维持自己的权威
心跳包中会携带当前 已经安全复制（已 committed）的日志索引 ，可表示为 (term, index)

4.2 选主的时机

如果一个 Follower 在一段时间内没有收到任何心跳，也就是选举超时
那么它就会主观认为系统中没有可用的 Leader，并发起新的选举
这种方法同时适用于集群刚刚启动时，各节点会在等待超时后发起新的选举

但如果所有节点在同一时刻启动，经过同样的超时时间后同时发起选举
那整个集群都会变得低效不堪，极端情况下甚至会一直选不出一个主节点

Raft 巧妙的使用了一个随机化的定时器，让每个节点的超时时间在一定范围内随机生成（150ms-300ms）
这样就大大的降低了多个节点同时发起选举的可能性
保证了同一时刻只有一个节点发起选举，从而成功选出 Leader

若 Follower 想发起一次选举，则需要先增加自己的当前 term，并将身份切换为 Candidate
然后它会向集群其它节点发送“请给自己投票”的消息（RequestVote RPC）

其他节点收到某节点的的投票请求后，就会将超时时间重置，防止在同一个任期同时出现多个 Candidate 节点
当然如果是在收到投票请求之前就已经超时，自然就会有多个 Candidate 了，这并不影响

4.3 选主成功

每个节点针对每个 term 只能投出一张票，并且按照先到先得的原则
这个规则确保只有一个 Candidate 会成为 Leader

当 Candicate 从整个集群的 大多数（N/2+1）节点获得了针对同一 term 的选票时
它就赢得了这次选举，立刻将自己的身份转变为 Leader 并开始向其它节点发送心跳来维持自己的权威

4.4 选主失败（承认或保持）

Candidate 在等待投票回复的时候，可能会突然收到其它自称是 Leader 的节点发送的心跳包
如果这个心跳包里携带的 term 不小于 该 Candidate 当前的 term
那么 Candidate 会承认这个 Leader，并将身份切回 Follower
这说明其它节点已经成功赢得了选举，其它节点只需立刻跟随即可
但如果心跳包中的 term 比自己小，Candidate 会拒绝这次请求并保持选举状态

4.5 选主超时

Candidate 既没有赢也没有输
如果有多个 Follower 同时成为 Candidate，选票是可能被瓜分的
如果没有任何一个 Candidate 能得到大多数节点的支持，那么每一个 Candidate 都会超时
此时 Candidate 需要增加自己的 term，然后发起新一轮选举

如果这里不做一些特殊处理，选票可能会一直被瓜分，导致一直选不出 Leader 来
所以 Raft 在这里就做了特殊处理，就是前面提到的 随机化选举超时时间

4.6 放弃 Leader 身份

当 Leader 节点发生了宕机或网络断连，此时其它 Follower 会收不到Leader 心跳
首个触发超时的节点会变为 Candidate 并开始拉票（由于随机化各个 Follower 超时时间不同）

由于该 Candidate 的 term 大于原 Leader 的 term，因此所有 Follower 都会投票给它
最后这名 Candidate 就会变为新的 Leader

一段时间后原 Leader 恢复了，收到了来自新 Leader 的心跳包
发现心跳中的 term 大于自己的 term，此时该节点会立刻切换为 follower 并跟随的新 Leader

7. 日志复制

Raft 的共识算法通常基于 状态复制机（ Replicated State Machine ）模型
所有节点从同一个 state 出发，经过一系列同样操作 log 的步骤，最终也必将达到一致的 state
也就是说，只要我们保证集群中所有节点的 log 一致，那么经过一系列应用（apply）后最终得到的状态机也就是一致的

所以，Raft 负责保证集群中所有节点 log 的一致性
这种保证通过 Leader （Strong Leader）来实现
将所有 log 都交给 leader 节点处理，并由 leader 节点复制给其它节点，就能够保证 log 的一致性了，这个过程就叫做日志复制

5.1 整体流程

一旦 Leader 被票选出来，它就承担起领导整个集群的责任了
开始接收客户端请求，并将操作包装成日志，并复制到其它节点上去

整体流程如下：

• Leader 为客户端提供服务，客户端的每个请求都包含一条即将被状态复制机执行的指令
• Leader 把该指令作为一条新的日志附加到自身的日志集合
  然后向其它节点发起 附加条目请求（ AppendEntries RPC ），来要求它们将这条日志附加到各自本地的日志集合
• 当这条日志已经确保被 安全的复制（大多数节点都已经复制）后
  Leader 会将该日志 apply 到它本地的状态机中，然后把操作成功的结果返回给客户端
• 如果某个 Follower 宕机了或者运行的很慢，或者网络丢包了
  则会一直给这个 Follower 发 AppendEntriesRPC 直到日志一致

每条日志除了存储状态机的操作指令外，还会拥有一个唯一的整数索引值（log index）来表明它在日志集合中的位置
此外，每条日志还会存储一个 term 号，表示 Leader 收到这条指令时的当前任期
term 相同的 log 是由同一个 Leader 在其任期内发送的

当一条日志被 Leader 节点认为可以安全的 apply 到状态机时，称这条日志是 committed
那么什么样的日志可以被 commit 呢？答案是： 当 leader 得知这条日志被集群过半的节点复制成功时
尽管有的节点拥有的日志可能并不完整

Raft 保证所有 committed 日志都已经被持久化 ，且 最终 一定会被状态机 apply
~这里表明了一个特点：Raft 保证的只是集群内日志的一致性，而我们真正期望的集群对外的状态机一致性需要我们做一些额外工作~

5.2 日志一致性的保证

Raft 保证：如果不同的节点日志集合中的两个日志条目拥有相同的 term 和 index，那么它们一定存储了 相同的指令

为什么可以作出这种保证？
因为 Raft 要求 Leader 在一个 term 内针对同一个 index 只能创建一条日志，并且永远不会修改它

同时 Raft 也保证：如果不同的节点日志集合中的两个日志条目拥有相同的 term 和 index，那它们之前所有的日志条目也全部相同

这是因为 Leader 发出的 AppendEntries RPC 中会额外携带上一条日志的 (term, index)
如果 Follower 在本地找不到相同的 (term, index) 日志，则 拒绝接收这次新的日志

5.3 可能出现日志不一致的场景

在所有节点正常工作的时候，Leader 和 Follower的日志总是保持一致，AppendEntries RPC 也永远不会失败
然而任意节点却随时可能宕机的风险，如何在这种情况下继续保持集群日志的一致性才是我们真正要解决的问题

• 图示

  

  上图展示了一个 term8 的 leader 刚上任时，集群中日志可能存在的混乱情况

  例如 Follower 可能缺少一些日志（a ~ b）
  可能多了一些未提交的日志（c ~ d）
  也可能既缺少日志又多了一些未提交日志（e ~ f）

  ~注：Follower 不可能比 Leader 多出一些已提交（committed）日志
  这一点是通过选举上的限制来达成的，会在安全性进行介绍~

• 场景分析

  1. 场景 a~b：Follower 日志落后于 Leader

     这种场景其实很简单，即 Follower 宕机了一段时间
     Follower-a 从收到 (term6, index9) 后开始宕机
     Follower-b 从收到 (term4, index4) 后开始宕机

  2. 场景 c：Follower 日志比 Leader 多 term6

     当 term6 的 Leader 正在将 (term6, index11) 向 Follower 同步时，该 leader 发生了宕机
     且此时只有 Follower-c 收到了这条日志的 AppendEntries RPC
     然后经过一系列的选举，term7 可能是选举超时，也可能是 leader 刚上任就宕机了
     最终 term8 的 Leader 上任了，成就了我们看到的场景 c

  3. 场景 d：Follower 日志比 leader 多 term7

     当 term6 的 Leader 将 (term6, index10) 成功 commit 后，发生了宕机
     此时 term7 的 Leader 走马上任，连续同步了两条日志给 Follower
     然而还没来得及 commit 就宕机了，随后集群选出了 term8 的 Leader

  4. 场景 e：Follower 日志比 Leader 少 term5 ~ 6，多 term4

     当 term4 的 Leader 将 (term4, index7) 同步给 Follower
     且将 (term4, index5) 及之前的日志成功 commit 后，发生了宕机，紧接着 follower-e 也发生了宕机
     这样在 term5~7 内发生的日志同步全都被 Follower-e 错过了
     当 Follower-e 恢复后，term8 的 Leader 也刚好上任了

  5. 场景 f：Follower 日志比 Leader 少 term4 ~ 6，多 term2 ~ 3

     当 term2 的 Leader 同步了一些日志（index4 ~ 6）给 follower 后
     尚未来得及 commit 时发生了宕机，但它很快恢复过来了，又被选为了 term3 的 leader
     它继续同步了一些日志（index7~11）给 Follower，但同样未来得及 commit 就又发生了宕机
     紧接着 Follower-f 也发生了宕机，当 Follower-f 醒来时，集群已经前进到 term8 了

5.4 处理日志不一致问题

Raft 强制要求 Follower 必须复制 Leader 的日志集合来解决不一致问题

也就是说，Follower 节点上任何与 Leader 不一致的日志，都会被 Leader 节点上的日志所覆盖
这并不会产生什么问题，因为某些选举上的限制，如果 Follower 上的日志与 leader 不一致
那么该日志在 Follower 上 一定是未提交的，未提交的日志并不会应用到状态机，也不会被外部的客户端感知到

要使得 Follower 的日志集合跟 Leader 的保持完全一致，Leader 必须先找到二者间 最后一次 达成一致的地方
因为一旦这条日志达成一致，在这之前的日志一定也都一致
这个确认操作是在 AppendEntries RPC 的一致性检查步骤完成的

Leader 针对每个 follower 都维护一个 next index ，表示下一条需要发送给该 Follower 的日志索引
当一个 Leader 刚刚上任时，它初始化所有 next index 值为自己最后一条日志的 index+1
但凡某个 Follower 的日志跟 Leader 不一致，那么下次 AppendEntries RPC 的一致性检查就会失败
在被 Follower 拒绝这次 Append Entries RPC 后，Leader 会减少 next index 的值并进行重试

最终一定会存在一个 next index 使得 leader 和 follower 在这之前的日志都保持一致
极端情况下 next index 为1，表示 Follower 没有任何日志与 leader 一致，leader 必须从第一条日志开始同步

针对每个 Follower，一旦确定了 next index 的值
Leader 便开始从该 index 同步日志，Follower 会删除掉现存的不一致的日志，保留 Leader 最新同步过来的

整个集群的日志会在这个简单的机制下自动趋于一致
此外要注意，Leader 从来不会覆盖或者删除自己的日志，而是强制 Follower 与它保持一致

这就要求集群票选出的 Leader 一定要具备“日志的正确性”，这也就关联到了前文提到的：选举上的限制

8. 安全性和正确性

前面提到了选主和复制日志是如何进行的
但是到目前为止我们描述的这套机制还不能保证每个节点的状态机会严格按照相同的顺序 apply 日志，如以下场景：

1. Leader 将一些日志复制到了大多数节点上，进行 commit 后发生了宕机
2. 某个 Follower 并没有被复制到这些日志，但它参与选举并当选了下一任 Leader
3. 新的 Leader 又同步并 commit 了一些日志，这些日志覆盖掉了其它节点上的上一任 committed 日志
4. 各个节点的状态机可能 apply 了不同的日志序列，出现了不一致的情况

因此我们需要对 选主+日志复制 这套机制加上一些额外的限制，来保证 状态机的安全性，也就是 Raft 算法的正确性

8.1 对选举的限制

committed 日志被覆盖的场景，根本问题其实发生在第2步

Candidate 必须有足够的资格才能当选集群 Leader，否则它就会给集群带来不可预料的错误
Candidate 是否具备这个资格可以在选举时添加一个小小的条件来判断，即：

每个 Candidate 必须在 RequestVote RPC 中携带自己本地日志的最新 (term, index)
如果 Follower 发现这个 Candidate 的日志还没有自己的新，则拒绝投票给该 Candidate

这种情况可以解决 Leader 将日志复制到少数 Follower 之后就宕机了的情况
为了能让该日志不会丢失且能保持最终一致，只有这些少数的 Follower 才能成为 Leader

Candidate 想要赢得选举成为 Leader，必须得到集群大多数节点的投票
那么 它的日志就一定至少不落后于大多数节点
又因为一条日志只有复制到了大多数节点才能被 commit
因此 能赢得选举的 Candidate 一定拥有所有 committed 日志

因此前边才会断定地说：Follower 不可能比 Leader 多出一些 committed 日志q

比较两个 (term, index) 的逻辑非常简单：如果 term 不同 term 更大的日志更新，否则 index 大的日志更新

8.2 对提交的限制

• 图示

  

• 场景解读

  1. 阶段 a ：S1 是 Leader，收到请求后将 (term2, index2) 只复制给了 S2，尚未复制给 S3 ~ S5

  2. 阶段 b ：S1 宕机，S5 当选 term3 的 Leader（得到 S3、S4、S5 三票过半，即使 S2 拒绝给票）
     收到请求后保存了 (term3, index2)，尚未复制给任何节点

  3. 阶段 c ：S5 宕机，S1 恢复，S1 重新当选 term4 的 Leader（可以拿到 S1 S2 S3 S4 的票）
     继续将 (term2, index2) 复制给了 S3，此时该日志已经满足大多数节点，可以将其 commit

  4. 阶段 d ：S1 又宕机，S5 恢复，S5 重新当选 Leader（S2、S3、S4 三票）
     将 (term3, inde2) 复制给了所有节点并 commit
     注意，此时发生了致命错误，已经 committed 的 (term2, index2) 被 (term3, index2) 覆盖了

     为了避免这种错误，我们需要添加一个额外的限制：Leader 只允许 commit 包含当前 term 的日志

     针对上述场景，问题发生在阶段 c，即使作为 term4 Leader 的 S1 将 (term2, index2) 复制给了大多数节点
     它也不能直接将其 commit，而是必须等待 term4 的日志到来并成功复制后，一并进行 commit

  5. 阶段 e ：在添加了这个上边的限制后
     要么 (term2, index2) 始终没有被 commit，这样 S5 在阶段d将其覆盖就是安全的
     要么 (term2, index2) 同 (term4, index3) 一起被 commit，这样 S5 根本就无法当选 Leader
     因为大多数节点的日志都比它新，也就不存在前边的问题了

9. 集群成员更变

主要解决的是：安全地改变集群的节点成员

在实践中有时会需要替换宕机机器或者改变复制级别（即增减节点）
一种最简单暴力达成目的的方式就是：停止集群、改变成员、启动集群
这种方式在执行时会导致集群整体不可用，此外还存在手工操作带来的风险

为了避免这样的问题，Raft 论文中给出了一种无需停机的、自动化的改变集群成员的方式
其实本质上还是利用了 Raft 的核心算法，将集群成员配置作为一个特殊日志从 leader 节点同步到其它节点去

9.1 直接切换集群的后果

如果直接将新配置作为日志同步给居群并 apply，那么将是不安全的
因为不能保证集群中的全部节点能在同一时刻原子地切换自己的成员配置
所以在切换期间，不同的节点看到的集群视图可能不同（配置不同），最终导致集群存在多个 Leader

• 场景（初始节点为 S1 S2 S3，简写为 1 2 3）

  1. 假设原集群中有 1 2 3 三个节点，其中节点 3 是 Leader

  2. 某一时刻新来了两个节点 4 5，这个更变从 3 号节点 Leader 写入

     这时集群中各节点的配置如下（每个节点认为集群中有哪些节点）
     1：1 2 3
     2：1 2 3
     3：1 2 3 4 5
     4：1 2 3 4 5
     5：1 2 3 4 5

  3. 假设这是节点 3 短暂宕机了，触发了 1 和 5 的超时选主（然后 3 又醒过来了，所以下面 3 是参与的）

     节点 1 向 2 和 3 拉票，由于 2 的配置没有比 1 新，所以 2 把票给了 1
     此时 1 获得了 2 票，多于集群总数 3 的一般（它认为集群只有 3 各节点）
     所以节点 1 成为集群的 Leader

     节点 5 肯定会得到 3 和 4 的选票，因为 1 感知不到 4 所以不会发选票请求，只收到了 5 的请求
     而 1 的日志落后于 3，所以 3 不会投票给 1 而是将票给了 5
     此时节点 5 拿到了 3 票，多于集群总数 5 的一半，所以节点 5 又成为了集群的 Leader

     这最后就导致了，集群中出现了多个 Leader 的指明错误，产生了所谓的脑裂

9.2 两阶段切换集群成员配置

Raft 论文将该方法称之为 共同一致（Joint Consensus）

使用的是一种两阶段方法，来平滑切换集群成员配置，避免遇到前一节描述的问题，具体流程如下：

9.2.1 阶段一

1. 客户端将 C-new 发送给 Leader，Leader 将 C-old 与 C-new 取 并集 并立即apply，我们表示为 C-old,new
2. Leader 将 C-old,new 包装为日志同步给其它节点
3. Follower 收到 C-old,new 后立即 apply
   当 C-old,new 的大多数节点（即 C-old 的大多数节点和 C-new 的大多数节点）都切换后，Leader 将该日志 commit

9.2.2 阶段二

1. Leader 接着将 C-new 包装为日志同步给其它节点
2. Follower 收到 C-new 后立即 apply，如果此时发现自己不在 C-new 列表，则主动退出集群
3. Leader 确认 C-new 的大多数节点都切换成功后，给客户端发送执行成功的响应

9.2.3 论证不会出现多个 Leader

1. 阶段1：C-old,new 尚未 commit

   该阶段所有节点的配置要么是 C-old，要么是 C-old,new
   但无论是二者哪种，只要原 Leader 发生宕机
   新 Leader 都 必须得到大多数 C-old 集合内节点的投票

   以 9.1 场景为例，S5 在阶段 d 根本没有机会成为 Leader，因为 C-old 中只有 S3 给它投票了，不满足大多数

2. 阶段2：C-old,new 已经 commit，C-new 尚未下发

   该阶段可以确保已经被 C-old,new 的大多数节点（C-old 的大多数节点和 C-new 的大多数节点）复制
   因此当 Leader 宕机时，新选出的 Leader 一定是已经拥有 C-old,new 的节点，不可能出现两个 Leader

3. 阶段3：C-new 已经下发但尚未 commit

   该阶段集群中可能有三种节点 C-old、C-old,new、C-new
   但由于已经经历了阶段2，因此 C-old 节点不可能再成为 Leader
   而无论是 C-old,new 还是 C-new 节点发起选举，都需要经过大多数 C-new 节点的同意，因此也不可能出现两个 leader

4. 阶段4：C-new 已经 commit

   该阶段 C-new 已经被 commit，因此只有 C-new 节点可以得到大多数选票成为 Leader
   此时集群已经安全地完成了这轮变更，可以继续开启下一轮变更了

10. 日志压缩

主要解决的是：日志集合无限制增长带来的问题

Raft 提供了一种机制去清除日志里积累的陈旧信息，叫做 日志压缩

**快照（ Snapshot ）**是一种常用的、简单的日志压缩方式，ZooKeeper、Chubby 等系统都在用
简单来说，就是将某一时刻系统的状态 dump 下来并落地存储，这样该时刻之前的所有日志就都可以丢弃了
所以“压缩”并没有办法将状态机快照“解压缩”回日志序列

在 Raft 中我们只能为 committed 日志做 snapshot，因为只有 committed 日志才是确保最终会应用到状态机的

快照一般包含以下内容：

1. 日志的元数据 ：最后一条被该快照 apply 的日志 term 及 index
2. 状态机 ：前边全部日志 apply 后最终得到的状态机

• 快照图示

  

  上图展示了一个节点用快照替换了 (term1, index1) ~ (term3, index5) 的日志。

当 Leader 需要给某个 Follower同步一些旧日志，但这些日志已经被 Leader 做了快照并删除掉了时
Leader 就需要把该快照发送给 Follower

同样，当集群中有新节点加入，或者某个节点宕机太久落后了太多日志时
Leader 也可以直接发送快照，大量节约日志传输和回放时间。

同步快照使用一个新的 RPC 方法，叫做 InstallSnapshot RPC

11. Raft 的一致性问题

11.1 为什么 Raft 不能与线性一致划等号

假设读操作直接简单地向 Follower 发起，那么由于 Raft 的 Quorum 机制（大部分节点成功即可）
针对某个提案在某一时间段内，集群可能会有以下两种状态：

• 某次写操作的日志尚未被复制到一少部分 Follower，但 Leader 已经将其 commit
• 某次写操作的日志已经被同步到所有 Follower，但 Leader 将其 commit 后，心跳包尚未通知到一部分 Follower

以上每个场景客户端都可能读到 过时的数据，整个系统显然是不满足线性一致的
因为：已经告诉客户端更新完成了，但客户端读取到的还可能是旧值，但过一段时间又读到新值了，值在来回跳动

11.2 Raft 写主读主缺陷分析

问题一：状态机落后于 committed log 导致脏读

一个提案只要被 Leader commit 就可以响应客户端了
Raft 并没有限定提案结果在返回给客户端前必须先应用到状态机
所以从客户端视角当我们的某个写操作执行成功后，下一次读操作可能还是会读到旧值（因为还没被 apply）

这个问题的解决方式很简单，在 leader 收到读命令时我们只需记录下当前的 commit index
当 apply index 追上该 commit index 时，即可将状态机中的内容响应给客户端

问题二：网络分区导致脏读

假设集群发生网络分区，旧 leader 位于少数派分区中，而且此刻旧 leader 刚好还未发现自己已经失去了领导权，当多数派分区选出了新的 leader 并开始进行后续写操作时，连接到旧 leader 的客户端可能就会读到旧值了。

因此，仅仅是直接读 leader 状态机的话，系统仍然不满足线性一致性。

11.2 如何基于 Raft 实现线性一致

使用 Raft Log Read 可以实现线性一致

为了确保 Leader 处理读操作时仍拥有领导权，我们可以将读请求同样作为一个提案走一遍 Raft 流程
当这次读请求对应的日志可以被应用到状态机时，Leader 就可以读状态机并返回给用户了

这种读方案称为 Raft Log Read，也可以直观叫做 Read as Proposal

为什么这种方案满足线性一致？
因为该方案根据 commit index 对所有读写请求都一起做了线性化
这样每个读请求都能感知到状态机在执行完前一写请求后的最新状态
将读写日志一条一条的应用到状态机，整个系统当然满足线性一致

但该方案的缺点也非常明显，那就是 性能差
读操作的开销与写操作几乎完全一致
而且由于所有操作都线性化了，我们无法并发读状态机

11.3 如何在保证线性一致的前提下进行读性能优化

在 Raft Log Read 下，可以进行优化，形成了三种方案：Read Index、Lease Read 和 Follower Read

11.3.1 Read Index

与 Raft Log Read 相比，Read Index 省掉了同步 log 的开销
能够大幅提升读的吞吐 ，一定程度上降低读的时延，其大致流程为：

1. Leader 在收到客户端读请求时，记录下当前的 commit index，称之为 read index。
2. Leader 向 followers 发起一次心跳包，这一步是为了确保领导权，避免网络分区时少数派 leader 仍处理请求。
3. 等待状态机 至少 应用到 read index（即 apply index 大于等于 read index）
4. 执行读请求，将状态机中的结果返回给客户端

这里第三步的 apply index 大于等于 read index 是一个关键点
因为在该读请求发起时，我们将当时的 commit index 记录了下来
只要使客户端读到的内容在该 commit index 之后，那么结果 一定都满足线性一致

11.3.2 Lease Read

与 Read Index 相比，Lease Read 进一步省去了网络交互开销，因此更能显著降低读的时延

基本思路是：Leader 设置一个 比选举超时（Election Timeout）更短的时间作为租期
在租期内我们可以相信其它节点一定没有发起选举，集群也就一定不会存在脑裂
所以在这个时间段内我们直接读主即可，而非该时间段内可以继续走 Read Index 流程
Read Index 的心跳包也可以为租期带来更新

Lease Read 可以认为是 Read Index 的时间戳版本
额外依赖时间戳会为算法带来一些不确定性，如果时钟发生漂移会引发一系列问题，因此需要谨慎的进行配置

11.3.3 Follower Read

在前边两种优化方案中，无论我们怎么折腾，核心思想其实只有两点：

• 保证在读取时的最新 commit index 已经被 apply。
• 保证在读取时 Leader 仍拥有领导权

其实无论是 Read Index 还是 Lease Read，最终目的都是为了解决第二个问题
换句话说，读请求最终一定都是由 Leader 来承载的

那么读 Follower 真的就不能满足线性一致吗？
其实不然，这里我们给出一个可行的读 Follower 方案：
Follower 在收到客户端的读请求时，向 Leader 询问当前最新的 commit index
反正所有日志条目最终一定会被同步到自己身上，Follower 只需等待该日志被自己 commit 并 apply 到状态机后
返回给客户端本地状态机的结果即可，这个方案叫做 Follower Read

注意：Follower Read 并不意味着我们在读过程中完全不依赖 Leader 了
在保证线性一致性的前提下完全不依赖 Leader 理论上是不可能做到的