raft: 分布式一致性算法笔记

2022 年 7 月 11 日
本文字数：12162 字
阅读完需：约 40 分钟

作者： eshin_ye 原文来源：https://tidb.net/blog/8e5aef8d

https://blog.csdn.net/qq_22351805/article/details/113568597

创作时间： 2021.01.27 17:22:15

本文主要记录 leader 选举与 log 复制过程的学习与思考。内容可能过于啰嗦，力求尽量对细节能有完整的描述，能对代码实现有所脾益。
首先我们先对 raft 要有一个大概的认知：raft 是一种基于日志复制的分布式一致性算法，用于解决分布式环境下多节点数据的一致性问题。多节点通过投票机制选举 leader 节点（超半数投票），客户端请求只能通过 leader 节点访问，当 leader 节点向 follower 节点复制日志时，超半数节点（包括 leader）复制完成即可向客户端返回已提交状态。这里需要注意的是，超半数节点复制完成不等于已提交，提交动作是 leader 节点完成，然后告知 follower 节点更新状态。
下面的说明，均以经典的 5 节点为背景。

一、主要概念：（可先大致了解，后面图文解析更方便理解）

1、leader，follower，candidate
leader 节点：接收客户端请求，客户端发起请求后，先在 leader 记录日志，然后 leader 复制到 follower 节点，当 leader 接受到超半数 follower 响应完成复制时，标识已提交并向客户端响应，告知 follower 已提交状态。
Follower 节点：接收 leader 的日志并持久化，接收 leader 的已提交通知并修改状态。
Candidate：Leader 选举过程中的临时角色。当 follower 等待一段时间（选举超时时间）后进入该状态，并开始发起投票。
2、选举超时时间与任期
选举超时时间：每个 follower 在启动后都会随机赋予一个超时时间，follower 启动后开始等待，在这个超时时间内，如果没有收到其他的投票请求，心跳请求或者日志复制请求，follower 进入 candidate 状态，并开始发起投票，如果这段时间有收到上述请求，则复位等待时间，重新开始等待。
任期：每一次 Leader 选举就开始新的任期。在成功选举 Leader 之后，Leader 会在整个 term 内管理整个集群。若当前任期没有选举出 leader，则开始下一个任期选举。
3、日志复制
每个节点上都会有个 log 数组，，记录每次的日志消息（logentry），每个 logentry 对应 log 数组的一个下标，logentry 记录有发送改 logEntry 的 leader 的任期和具体的 log 内容。
logEntry 在每个节点复制完成后告知 leader。leader 节点收到大多数回复后向客户端响应已提交并记为 commited（实际的已提交），而后告知 follower 已提交状态，follower 标识 commited（实际上没有告知的请求，而是通过下一次心跳检测请求（日志内容为空）或者日志复制请求，后面会讲到）,leader 标记 commited 之后同步执行当前日志的命令结果写入状态机（Replicated state machines）状态机可以理解为磁盘存储或者内存存储等能够保存数据状态的设备。

在开始下一部分内容之前，可以先玩下raft 演示，不过后面第三章的图文解析将用更详细的演示图。

二、raft 算法规则设计

这部分内容对理解 raft 和代码实现都是很有意义的。当然也可先大致了解一下，后面看完图文解析之后再回过头来细细品味，或者一边对照着一点看图文解析，或者直接跳过这章看第三章图文解析。
1、节点需要记录的信息
currentTerm：当前最新期次号，当前节点所处任期（初始为 0，不断递增）
voteFor：当前任期，该节点投票给了哪个节点，标识 candidateID。（没有则为空）
log[]：消息日志数组，每条日志对应一个下标，每条日志包含指令本身内容和所属任期
commitIndex：最后一条确认提交日志的下标。（初始为 0，不断递增），leader 节点接收到大多数节点确认后更新该值，也就是说，log[]的长度可能大于 commitIndex。
lastApplied：最后确认的已提交执行的日志下标（初始为 0，不断递增，leader 更替可能导致该值小于 commitIndex）
以下是主节点才有的属性
nextIndex[]：主节点为每一个节点保存的下一条将要同步的日志的下标（初始为 leader 日志长度 +1，可根据 follower 节点日志情况调整）
matchIndex[]：主节点为每一个节点保存的已经匹配上的最后一条日志下标。（leader 更替可能导致改制远小于 nextIndex，因此 leader 会逐渐将 nextIndex-1 检测，直至两者相差 1。）
2、选举请求与响应（RequestVote RPC）
follower 经过选举超时时间等待之后，转为 candidate 发起投票。
请求参数：
term：candidate 要竞选成为 leader 的任期号，值为转 candidate 前的 follower 的 currentTerm+1；
candidateID：候选人 ID；
lastLogIndex：candidate 节点最后一条日志记录的下标；
lastLogTerm：candidate 节点最后一条日志记录的所属任期（由于某些任期没有选举出 leader，或者选举出 leader 后没有发生过日志复制，该值可能小于转 candidate 前的 follower 的当前任期（currentTerm）。）
返回结果：
term：follower 当前任期号，该值如果大于 candidate 的 currentTerm，那么 candidate 的 currentTerm 复制为该值。
voteGranted：投赞成票值为 true，反对票值为 false；
请求端规则：（这个论文没有写，我在这里加上便于理解）
follower 转为 candidate 之后，当前任期增加 1，即 currentTerm=currentTerm+1；
接收端规则：
1、如果接收到的请求的 term<= 本 follower 节点的 currentTerm，返回 false，原论文这里只有小于，实际应该小于或者等于，因为相等的情况下，说明 follower 早就投过同任期的票了。
2、如果 candidate 的日志跟自己的一样或者比自己的新，则投出赞成票
那么怎样才算是更新呢，论文里提到：比较两个节点日志中的最新的日志记录，然后比较这两条日志记录的下标和所属任期号，所属任期号比较大的日志记录，那么它就是较新的，如果所属任期号相同，再比较下标值，下标值较大的则是较新的那一条。
3、若请求参数里的 term 大于自己的 currentTerm，follower 投票后，将自己的 currentTerm 赋值为请求参数 term；（这条也是自己加的，论文体现在后面的节点规则中，）
3、AppendEntries RPC
由 leader 发起，用于日志记录备份请求，或者心跳检测请求
请求参数：
term：leader 节点的当前任期号 currentTerm。
leaderID：主节点 ID，follower 更新到 votedFor 字段；当 follower 接收到客户端请求，follower 告诉客户端主节点是哪个，并将请求转发过去。
prevLogIndex：即将要复制的日志记录的上一条日志记录的下标
prevLogTerm；即将要复制的日志记录的上一条日志记录的所在任期号；
entries[]：需要复制的日志数组；（心跳检测只是 entries 没有内容而已)
leaderCommit：leader 节点要提交的日志记录下标；
返回：
term：follower 的任期号，leader 用于对该节点的状态更新
success：follower 包含 prevLogIndex，prevLogTerm 对应的日志，则备份成功返回 true，否则返回 false；
接收端处理规则：
1、如果传送过来的 term 小于 follower 节点的当前任期号 currentTerm，返回 false；
2、如果 follower 节点对应 prevLogIndex，prevLogTerm 的位置没有日志记录，返回 false；
3、如果 follower 已经存在一条日志与新传输的日志冲突（下标相同，但是任期号不同），则删除该日志及其 index 大于这条记录的日志。
4、追加所有不存在的日志；
5、如果 leaderCommit 大于 follower 节点的 commitIndex，将 commit 设置为（leaderCommit 和最新日志记录下标的最小值），体现在 leader 节点的日志比 follower 多，follower 追加日志的场景。
4、各个节点逻辑规则
所有节点规则：
如果 commitIndex>lastApplied，则将 lastApplied 逐次加 1，执行 lastApplied 下标对应日志的内容。
RPC 请求或者响应里的任期号 term T 大于自己的当前任期号 currentTerm，则将自己的当前任期号设置为 T；（确保所有节点的 currentTerm 都是最新的）
follower 节点的规则：
对来自 leader 和 candidate 的 RPC 请求应答；
如果选举超时时间内没有收到 leader 节点的 AppendEntries RPC 请求，或者没有收到其他候选人的投票请求，则自己变为候选人。
如果 follower 收到 leader 节点的 AppendEntries RPC 请求，或者收到 candidate 节点的 vote 请求后投了赞成票后，该 follower 节点复位超时等待时间，重新计时（比如，原先分配的超时时间为 1s，在等待了 500ms 后接收到以上的两种情况请求，重新分配一个超时时间 1.1s, 重新开始等待计时。）保证 leader 节点任期稳定。（这条是自己加的。论文没有）
candidate 节点：
成为候选人后，开始选举过程：
将自身的当期任期号 +1，即 currentTerm= currentTerm+1；
投自己一票；
重新开始选举超时计时
发送 requestvote RPC 请求到其他节点；
如果获得大部分节点的赞成票，则成为 leader；
如果接收到新 leader 的 appendEntries RPC，则回退到 follower；
如果该任期没有结果，重新等待所有节点中的其中一个（包括自己）成为 candidate，重新开始选举过程；
leader 节点：
成为 leader 后，马上发送一轮空内容的 appendEntriesRPC 请求（即心跳请求），且重复发送，避免其他的节点等待计时到达超时等待时间发起新的选举操作。
接收到客户端命令后，将其封装为日志追加到日志数组，执行该命令后，返回结果给客户端；
如果 leader 的最后一条日志记录的下标大于或者等于某个 follower 节点的 nextIndex，则发送 appendEntriesRPC 请求，entries 数组中包含 leader 节点 log 数组该 follower 的 nextIndex 及大于 nextIndex 的所有日志。
如果成功：更新 leader 中该 follower 的 nextIndex 和、matchIndex；
如因为一致性问题，追加失败（即 appendEntries RPC 接收端处理规则的第 2 条）。则将 nextIndex-1，再次发起 appendEntries RPC。
如果存在一个满足 N > commitIndex 和大部分节点的 matchIndex >= N 并且 log[N].term == currentTerm 的 N，则将 commitIndex 赋值为 N。这条规则隐藏两层意思，一是存在多条日志已经被多数 follower 节点复制，也就是先更新 matchindex，当多数节点的 matchIndex 都更新后才更新 commitIndex。二是 leader 只能提交当前任期的日志，如果有往期的日志有多数复制了，不能由当前任期的 leader 提交，二是在当期 leader 提交当期日志时，间接提交。这也表明有可能有些日志没有执行到状态机，那么就需要检测 lastApplied 是否小于 commitIndex，从而执行往期的指令。
安全约束：
election safety：对于任意一个任期，最多只有一个 leader；
leader append-only：leader 节点从不删除或者覆盖自身的日志，只追加；
log matching：如果两个日志在相同下标位置的日志所属任期号相同，则表明这两条日志及更早的日志都相同
leader completeness：如果某个日志在某个任期被提交了，那个这条日志一定会出现更高任期的 leader 节点日志里。
state machine satety：如果 leader 已经在给定下标位置的日志应用到状态机，那么其他任何节点都不能再同一个下标提交不同的日志
日志匹配特性（Log Matching Property）：
如果在不同节点日志数组里的两条日志记录拥有相同的下标和任期号，那么它们包含的命令肯定是一样的。
如果在不同节点日志数组里的两条日志记录拥有相同的下标和任期号，那么这些日志在这个下标以前的日志记录都是完全相同的。
解释：** 一、**leader 的日志只能追加不能删除或者覆盖，因此所有 follower 的日志里，如果下标和任期号与 leader 的相同，那么他们的日志内容肯定一样。** 二、** 由于 leader 发送一个 AppendEntries RPC 时，请求中包含请一个日志记录的下标和所属任期号，follower 找不到对应下标和任期的日志时，拒绝更新该日志，leader 会继续往前检测下标和任期在 follower 对应的日志存不存在。

三、选举与日志复制图文解析

在开始之前，先介绍一个模拟 raft 的工具, 如下图：

场景模拟演示与解析

这部分内容，会根据不同场景解释第二章中的规则；

1、选举

场景 1：所有节点都正常

刚启动，所有节点开始选举超时时间计时

（1） s4 最先到达选举超时时间成为 candidate，节点当前任期 currentTerm 从 1 设置为 2, 向其他节点发起 RequestVote RPC 请求，并投了自己一票。（请求参数 term=2，candidateID=s4）
（2） s1、s3、s5 接收到 s4 的 vote 请求后，voteFor 设置为 vote 请求参数的 candidateID：s4,currentTerm 设置 vote 请求参数的任期号 2，投出赞同票；
s2 在还没接收到 s4 发起的 RequestVote RPC 的时候，也到达了选举超时时间，也成为了 candidate，currentTerm 从 1 设置为 2, 向其他节点发起 RequestVote RPC 请求。在接收到 s2 的 vote 请求后，发现自己的 currentTerm 跟 s4 的一样，投了反对票。（follower 的当前任期号大于或者等于 candidate 的任期号，follower 都会投反对票）
（3） s4 接收到三个赞同票加上自身一票，一共 4 票，超过半数，成为 leader，并开始发送心跳请求。
s1,s3,s4,s5 收到 s2 的 vote 请求后，节点任期号均与 s2 相等，投出反对票。
（4） s2 无法获得多数赞同票，并在接收到 leader 节点的心跳请求后，回退为 follower。leader 节点 s4 在收到心跳请求响应后，为每个节点设置 nextIndex（初始值：1）和 matchIndex（初始值：0）（这两个值 leader 节点维护）。
follower 节点每收到一次请求（AppendEntries RPC）均重置等待时间，重新计时，保证 leader 节点稳定，这也要求 AppendEntries RPC 请求发送间隔要远远小于选举超时时间。

场景 2：leader 节点宕机，剩下 4 个节点参与选举

四节点选举时，存在两种情况（1、一个候选者获取多数选票，2、两个候选者各获得一半选票），不过这里合并一起讲。

（1） s4 宕机后，所有的 follower 节点继续选举超时计时。
（2） s1、s5 同时到达选举超时时间，均称为 candidate，任期号均 +1，各自给自己投一票，发起 vote 请求。并重新开始选举超时计时。
（3） s2 节点 currentTerm 为 2，接收到 s1 的请求后，发现自己的 currentTerm 小于 s1 的 currentTerm，s2 的 currentTerm 设置为 s1 的 currentTerm，并投出赞同票，紧接着又收到 s5 的 vote 请求，此时 s2、s5 的 currentTerm 相同（即 s2 已经投过任期号为 3 的票了），s2 投出反对票。s3 则是先接收到 s5 的 vote 请求，对 s5 投了赞同票，对 s1 投了反对票。
（4） 此时，s1、s5 均只获得两个选票，无法成为 leader，继续向挂掉的节点发起 vote 请求，试图获得选票，当然是不会获得回应的。
（5） 在 s1、s5 继续向 s4 发送 vote 请求的同时，四个节点继续选举超时计时
（6） s5 首先结束等待，转为 candidate，currentTerm+1 设置为 4，发送 vote 请求。
（7） s1、s2、s3currentTerm 设置为 4，均投出赞同票，voteFor 设为 s5；
（8） s5 成为 leader，发送心跳请求，为每个 follower 节点设置 nextIndex 和 matchIndex。

** 场景 3：宕机节点重启，并很快到达选举超时计时 ** 这种情况实际包含了 s4 正常重新加入集群的情况，只不过前面多了一点插曲 >![](https://img-blog.csdnimg.cn/img_convert/17b874f90798da497901f2bd5f15011e.png) >（2）s4 重启，并很快选举超时计时结束，成为 candidate，currentTerm+1 设置为 3，发起 vote 请求。（3）其与四个节点当前任期均为 4，均投反对票，在响应中反馈 term 为 4；（4）s4 收到响应后，将 currentTerm 设置为 4。leader 节点 s5 发送心跳请求（带参数 leaderID:s5）,s4 接收心跳请求后，更新 voteFor 字段值为 s5 并向 s5 响应成功，leader s5 收到响应后设置 s4 节点的 nextIndex 和 matchIndex。

** 场景 4：某个 follower 节点在某段时间因为网络问题无法收到 leader 的心跳请求，在这段时间内成为 candidate，在发送 vote 请求时，网络又恢复正常 ** >![](https://img-blog.csdnimg.cn/img_convert/2e3f2830a8bd39a1ffe81576d4789dec.png) （1）follower 节点 s1，因网络问题无法收到 leader 节点 s5 的心跳请求，到达选举超时计时，成为 candidate，currentTerm+1 设置为 5，在发送 vote 请求时，网络恢复正常。此时 leader 也在持续发送心跳包。（2）此时 s1 的任期号大于其余所有节点的任期号（包括 leader，目前先不考虑存在日志情况），其余所有节点均投了赞同票（图中小箭头“-”为 false，“+”为 true）并各自将 currentTerm 设置为 5。s5 停止发送心跳请求，s2/s3/s4 对原先 leader 的心跳请求响应 false；（3）s1 获得大多数选票，成为 leader，开始发送心跳请求，维护所有 follower 节点的 nextIndex 和 matchIndex。这种场景会导致 leader 节点频繁变更造成动荡，当然这种场景发生的几率很小，这就是为何论文中要求，心跳检测间隔时间 << 选举超时时间 << 故障发生时间间隔。这么看来，似乎没有什么优化的必要。

以上均是不含日志情况下的选举（日志条数一样的情况类似），下面将分析日志条数不一样的场景

首先先模拟场景（这个模拟也是模拟脑裂的场景，只不过这个模拟工具无法实现网络阻隔，但是这难不倒我们，我们可以分步来）

（1）leader s5 在在任期 3 完成日志复制
（2）s5 掉线后，重新选举了 s3 为 leader，此时（假设）出现网络阻隔，s1/s2/s5 可以相互访问，s3/s4 可以相互访问，阻断后，leader s3 继续接收客户端请求完成日志复制，并同步到 s4;
（3）阻隔后，s5 重新启动，并由 s1/s2/s5 三个节点重新选举出 leader s1(五个节点三个赞同票)，这里虽然停掉了 s3/s4，但通过想象我们可以当做这两个节点还在运行，这样就模拟出了脑裂的场景，s1 和 s3 两个 leader 同时存在
（4）如果此时网络恢复正常。此时如果 s3 发送心跳请求，则会被 s1/s2/s5 拒绝该请求响应 false（s3 任期较小）；或者 s1 发送心跳请求，s3/s4 接收请求并响应 true。这两种情况都会让 s3/s4 纳入 s1 的管辖。s1 记录 s3/s4 的 matchIndex 为 2、nextIndex 为 3；如下图：

下面两个场景（所有节点在到达选举超时时间之前任期号相同，但日志长度不一样的两种场景）的分析，则从这个图开始，这里先将 s1 resume 一下，重新开始计时。

（1）leader 节点 s1 resume 之后，重新开始计时
（2）假设此时 s1 最先计时完成结束等待成为 candidate，currentTerm+1 设置为 6，发起投票，投票请求中 lastLogIndex 为 2，lastLogTerm 为 3。
（3）s2/s5 最后的 log entry 的 index 为 2 等于 vote 请求的 lastLogIndex，log[lastIndex].term 为 3 等于 vote 请求的 lastLogTerm。这两个节点投出赞同票；s3/s4 log[lastIndex].term 为 4，日志更新，投反对票。
（4）但 s1 依旧获取多数票，成为 leader；leader s1 维护 matchIndex 表和 nextIndex 表，此时所有 follower 节点 matchIndex 均为 2，nextIndex 均为 3；s3/s4 的多余日志后续会删除（后面的日志复制小节解析）
（5）假设在（1）之后，不是 s1 先结束超时等待，而是 s3，那么 s3 成为 candidate，currentTerm 设为 6，投票请求中 lastLogIndex 为 5，lastLogTerm 为 4。此时所有的 follower 收到请求都响应 true。
（6）s3 成为 leader，维护 matchIndex 表和 nextIndex 表，此时所有 follower 节点 nextIndex 均为 6（leader 初始化给所有的 follower 的 nextIndex 设置为 lastIndex+1），后续 s3 发送心跳包，逐个 index（nextIndex–）检查 matchIndex（后面的日志复制小节解析）

继续上面的场景
（1）关闭 s4/s3, 重新选举 s1 为 leader（s1 发起投票，获得 s2/s5 的赞同票）
（2）leader 收到客户端请求，添加新日志。
（3）重启 s3/s4, 让 s3 到达超时发起 vote 请求，明显只有 s4 会将 currentTerm 从 6 变为 7 ，响应 true；其他 follower 节点的 currentTerm 本来就是 7，响应 false；当然这里只是为了演示需要做了个中间状态。现在 resume s1。
（4）s3 到达超时计时发起 vote 请求，可以看到，由于 s1 的最后一个 log entry 的任期号为 7，大于 vote 请求的 lastLogTerm，该节点投了反对票。
（5）反过来，如果是 s1 发起 vote 请求，s1 的最后一个 log entry 的任期号是大于其与所有 follower 的最后一个 log entry 的任期号，s1 将获得所有赞同票。

当 candidate 和 follower 日志不同的时候，选举情况看似复杂，其实是归结起来就两句话：日志里最后一个 log entry 的 term 更大的日志更加新，如果这个 term 相等，那么最后个 log entry 的 index 更大的日志更新。

2、日志复制

场景 1、leader 固定一个，新增日志顺序复制

（1）集群初始化选举完成之后，s5 当选为 leader（currentTerm：2），leader 中记录所有 follower 节点 matchIndex 为 0；nextIndex 为 1；commitIndex 为 0；lastApplied 为 0；
（2）leader 节点 s5 接收到客户端请求, 将命令包装成日志，s5 节点 log[]添加日志记录。
（3）leader 节点向其他节点复制日志，请求内容（leaderID：s5,prevLogIndex:0,prevLogTerm:2，leaderCommit：0）, 所有 follower 接收日志请求完成复制。leader 节点为响应已被收到的 follower 设置 matchIndex 和 NextIndex，如 s1,matchIndex 设置为 1，nextIndex 设置为 2；leader 节点接收到多数 follower 响应，commitIndex 设置为 1，同时将命令执行到状态机 lastApplied+1；（由于 lastApplied 不那么重要，后续忽略它）
（4）leader 确认提交后需要告知 follower，论文里没有使用专门的请求来告知通知状态，那么就是复用 AppendEntries RPC（要么心跳请求，要么日志复制请求）。请求内容 prevLogIndex:1,prevLogTerm:2，leaderCommit：1；follower 收到请求后，设置自身节点 commitIndex=leaderCommit;
(5) 全部 follower 节点均文成 commitIndex 修改，表明已提交状态；

场景 2、在 leader 复制完日志收到大多数确认之后，发生网络问题，leader 切到其他节点。

（1）s5 继续接受客户端请求，添加日志记录
（2）s5 向 follower 发送日志复制请求，follower 接收到请求，检测 index== prevLogIndex== 1 的位置包含 log[prevLogIndex].term == prevLogTerm == 2 的日志，发现存在对应 log entry，则完成日志复制返回 true（如不存在 logentry 则返回 false，若存在 log entry , 但 logentry.term 不等于 prevLogTerm，删除掉并返回 false，这样就保障了 follower 节点跟 leader 节点的顺序一致）并收到大多数成功恢复，为每个响应 true 的 follower 设置 matchIndex+1，nextIndex+1, 并设置自身 commitIndex+1；
（3）s5 收到全部响应后提交日志，但还没来得急向 follower 发送下一次心跳请求告知已提交状态（即 commitIndex+1）就发生网络震荡，然后 s1 当选为 leader，任期号为 3，为所有节点初始化 matchIndex 为 0，nextIndex 为 3。并继续通过心跳请求中的 prevLogIndex（值为 nextIndex-1）开始往前检测最后 match 的 index。follower 中 prevLogIndex 对应位置若不存在日志或者存在日志但所属 term 不等于 prevLogTerm 则返回 false，leader 将对应的 follower 的 nextIndex-1，并继续发送心跳请求检测 matchIndex;
（4）此时 s1.commitIndex 比 s5.commitIndex 小 1, 不更新 commitIndex，其余的 follower.commitIndex== s1.commitIndex, 也不更新。按规则，当前任期 leader 不提交往期日志的规则，index 为 2 的 log entry，即便完成了大多数复制，依然无法提交
（5）此时再发生网络震荡 s5 重新当选，任期号为 4；
（6）由于 s5 的 commitIndex 本就是已提交后 +1 过的，因此发送心跳包时，心跳请求中的 leaderCommit== s5.commitIndex == 2 大于其余 follower.commitIndex == 1。所有的 follower 节点修改 commitIndex 为 2。也就是所有 follower 提交 index 为 2 的 log entry。这看起来是不是像当期 leader 提交往期日志，然而并不是，index 为 2 的 logentry，在任期 2 的时候就已经提交了，并执行到状态机，但是只有 s5 知道，因此 s5 重新当选后，只不过是同步状态。
那么如果在发生网络问题，切换 leader 之前，leader 节点还没有收到大多数确认呢：

这种情况下，leader 从 s5 切到 s1 再切回 s5，都不会提交 index 为 2 的 log entry。因为此时所有的节点 commitIndex 都是 1。

那么往期的多数复制的日志什么时候提交呢？请看下图：

（1）在集群任期 2 时，发生网络震荡，经过几次选举，在任期 5 选举 s1 为 leader，发送心跳请求后，并没有提交 index 为 2 的 log entry。
（2）此时 leader 节点 s1 接收到客户端请求，写入日志。向 follower 节点发起日志复制请求。
（3）follower 节点复制完成后，响应 true，leader 节点 s1 为成功响应的 follower 节点设置 matchIndex+1，nextIndex+1；leader 节点 s1 接收到大多数成功响应后，提交日志，commitIndex 设置为 3，这里隐式将 index 为 2 的 log entry 提交了；此时 lastApplied== 1 小于 commitIndex，log[]中的 log entry 将从 index2 开始逐条执行到状态机，知道 lastApplied== commitIndex。
（4）leader 节点 s1 向其他节点发起心跳请求，此时请求中的参数 leaderCommit 为 3；follower 接受到请求后，修改 commitIndex 为 3，表示已提交相应 log entry。
为什么采取这样的方式？：既然讲到这里，那就一起吧各节点日志长度不一样的场景一起在这里解析：

（1）假设此时 s3/s4/s5 与 s1/s2 发生网络隔离，此时 leader 节点 s1 陆续收到客户端请求，但此时只有 s2 一个 follower 存活并完成日志复制，matchIndex 为 6，nextIndex 为 7。
（2）（3）因此同时，s3/s4/s5 选举了 s5 为 leader，任期号为 6、并接收到了客户端请求。
（4）此时网络恢复，同时 s5 宕机。重新选举了 s1 为 leader，初始化所有 follower 对应的 matchIndex 为 0；nextIndex 为 7。并发起心跳请求，以对 s3 发起的心跳请求为例，对其发送的心跳请求参数（prevLogIndex:6,prevLogTerm：5）
（5）follower 接收到心跳请求，如 s3, 开始检测 prevLogIndex 对应位置的日志，发现不含日志，返回 false，其他 follower 也同样。
（6）leader 节点收到 s3 的 false 响应，将 nextIndex-1，设置为 6，重新对其发起心跳请求（prevLogIndex:5,prevLogTerm：5（leader 中 index== 5 对应的 log entry 所属的 term））以此类推
（7）（8）最终通过 prevLogIndex== 3 在 follower s3 中找到存在 log entry 的对应 index，s3 向 leader 响应 true，leader s1 收到响应后修改其 matchIndex 为 3，nextIndex 为 4，其余 follower 也同样。s5 由于宕机无法响应，不修改，但 leader 继续向其发送心跳请求。然后 leader 根据所有 follower 的 matchIndex 情况追加 log entry。
论文中在这种情况说到一种优化，就是请求响应 false 时，直接将 follower 节点的 commitIndex 一同响应回 leader，但论文又提到，由于宕机的情况很少，该优化不太必要。个人以为这个优化还是很有必要的，尤其可以大大缩短故障恢复时间。
（9）问题还没完。此时 s5 重启，而且还发起 vote 请求，并收到多数赞同票成为了 leader（因为其最后一条日志的所属 term 大于其他任何节点最后一条日志的所属 term）
（10）leader s5 为所有的节点设置 matchIndex 为 0，nextIndex 为 5，并开始检测 follower 的 matchIndex。
（11）（12）检测的方式跟步骤（6）（7）（8）类似，但此时是 prevLogIndex 对应位置有 log entry，但是所属任期不相等，这种也是返回 false。最终确定 matchIndex 和 NextIndex，如 s3:matchIndex 为 3，nextIndex 为 4。然后开始发起日志复制请求（prevLogIndex:3,prevLogTerm：5，entry[]中包含 matchIndex 之后的所有 log entry）；
（13）follower 节点接收到日志复制请求后，发现 prevLogIndex+1 的位置有日志（matchIndex 不是这个位置，说明这个位置的 logentry 肯定是冲突的，即所属的任期不一样）则删除该位置及后面的所有 log entry，然后在该位置追加请求中带过来的 entry[]内容。

这里就演示了，即便大多数复制的内容也可能被覆盖。如果在步骤（9）中 s1 在完成多数节点复制后提交了往期的日志并执行到状态机，但是还没将提交状态同步到其他节点，或者已经同步了状态。此时 S5 发起的 vote 请求依然能成为 leader，顺利完成（9）之后的流程，这样就覆盖了已提交的 log, 与状态机的状态不一致了。

那为什么当期提交就没问题呢？

当期的 leader 能保证提交当期的日志时最新的，往期的日志 leader 不能保证是最新的（比如 s5 的第四个 log entry 才是整个集群最新的日志记录）。

那么只有在多数复制后，又有新的当期日志（肯定是所有节点中最新的）提交，才能顺带往往期的一起提交：

这个图就不再解析了，上面的流程都讲到过相关的内容

很明确的一点：已经提交应用到状态机的日志，不能被覆盖修改，这是数据一致性安全的要求。

3、leader 的完整性（Leader Completeness Properties）验证

论文中对 leader 的完整性（Leader Completeness Properties）用了一个很啰嗦的反证。其实就是只要是 leader 能确认提交的日志肯定是多数复制了，且当前任期号的日志肯定是最新的日志，那么下一任期选举，一定会有包含该条最新日志的节点参与选举才能有节点得到多数选票，且一定是包含最新日志的节点得到多数选票。

可以想象存不存在 s2 中 index 为 3，任期为 5 的日志。答案是肯定不存在的，任意一个任期的某条日志（如任期 4 时，s1 在 index3 的日志），这条日志肯定是当前最新的，如果该条日志被提交那么肯定这条日志被复制到大多数节点，那么在下一次选举中，剩下的少数节点中的任意一个肯定不会被选举为 leader（能得到的票数最多为 n/2 -1, 此例中肯定不会超过 2 票，如上图在任期 5 的选举，s4 或者 s2 如果成为 candidate 发起 vote 请求，最多只能得到两票），由此保证了下一任期的 leader 的日志完整性。

后面的成员配置边和日志压缩等就先不玩了。。。

参考：

http://thesecretlivesofdata.com/raft/

https://raft.github.io/raftscope/index.html

https://github.com/maemual/raft-zh_cn/blob/master/raft-zh_cn.md#51-raft- 基础