Standford 大学的 Diego 提出的 Raft 算法正是为可理解性、易实现而诞生的；

它通过问题分解，将复杂的共识问题拆分成三个子问题，分别是：
1）Leader 选举：当 Leader 故障后集群能快速选出新 Leader；
2）日志复制：集群只有 Leader 能写入日志，Leader 负责复制日志到 Follower，并强制 Follower 与自己保持相同；
3）安全性：一个任期内集群只能产生一个 Leader、已提交的日志条目在发生 Leader 选举时，一定会存在更高任期的新 Leader 日志中、各个节点的状态机应用的任意位置的日志条目内容应一样等；

Leader 选举

在 Raft 中，集群 Leader 才能处理写提案，该部分将记录：Leader 是如何产生的，以及 Leader 崩溃后其他节点如何竞选；

节点状态

Follower，跟随者， 同步从 Leader 收到的日志，etcd 启动的时候默认为此状态；

Candidate，竞选者，可以发起 Leader 选举；

Leader，集群领导者， 唯一性，拥有同步日志的特权，需定时广播心跳给 Follower 节点，以维持领导者身份；

任期与任期号（Term）

Raft 将时间划分成一个个任期，任期用连续的整数表示，每个任期从一次选举开始，赢得选举的节点在该任期内充当 Leader 的职责；

随着时间的消逝，集群可能会发生新的选举，任期号也会单调递增；
通过任期号，可以比较各个节点的数据新旧、识别过期的 Leader 等，它在 Raft 算法中充当逻辑时钟，发挥着重要作用；

状态变迁

Follower => Candidate
1）当 Follower 接收 Leader 心跳消息超时后，它会转变成 Candidate 状态；

Candidate => Leader
1）Candidate 可发起竞选 Leader 投票，若获得集群多数节点的支持后，它就可转变成 Leader 节点；

Leader => Follower
1）现有 Leader 发现新的 Leader 任期号，那么它就需要转换到 Follower 节点；
2）当 Leader 崩溃恢复后，再次启动将成为 Follower 状态；

场景：after Leader Crash

假设：Leader A；Follower B；Follower C；

当 Leader 正常时：
1）Leader 将周期（心跳间隔时间）广播 MsgHeartbeat 消息给 Follower，以维持 Leader 身份；
2）Follower 收到 MsgHeartbeat 后，回复 MsgHeartbeatResp 消息给 Leader；

当 Leader 异常后：
1）Follower 超时未接收到 Leader 的 MsgHeartbeat 消息，并且当 heartbeat-interval(100ms) > election-timeout(1000ms) 后，Follower 将进入 Candidate 状态；
2）Follower 进入 Candidate 状态会立即发起选举流程，自增任期号，投票给自己，并向其他节点发送竞选 Leader 投票消息（MsgVote）；

现在，我们假设 Follower B 先进入 Candidate 状态，并向 Follower C 发送投票消息：

现在，我们假设 Follower B 与 Follower C 同时进入 Candidate 状态：

场景：when Leader Recovery

Leader A 崩溃后，再次启动成为 Follower A

假设因为网络问题无法连通 B、C 节点，根据状态图，Follower A 将不停自增任期号，发起选举。等 Follower A 网络异常恢复后，那么现有 Leader 收到新的任期号，就会触发新一轮 Leader 选举；

然而 Follower A 的数据落后于 B、C 节点，是无法获得集群 Leader 地位的，其发起的选举是无效的，但却对集群的稳定性造成影响；

在网络故障恢复后，某个故障节点将发起选举。然而，鉴于故障节点数据落后，注定其无法成为 Leader 角色。其发起的选举是无效的，但却对集群的稳定性造成影响；

在 etcd 3.4 中，etcd 引入 PreVote 参数（默认 false），可以用来启用 PreCandidate 状态解决此问题；

Follower 在转换成 Candidate 状态前，先进入 PreCandidate 状态，不自增任期号，发起预投票；
若 Follower 获得集群多数节点认可，确定有概率成为 Leader 才能进入 Candidate 状态，发起选举流程；
但是，鉴于节点数据落后较多，预投票请求无法获得多数节点认可，所以它就不会进入 Candidate 状态；

以此解决无效选择影响集群稳定性的问题；

日志传递

当 Leader 选择结束后，Leader 负责数据写入，该部分将记录：Leader 将日志同步给 Follower 节点的过程；它是如何确定一个日志条目为已提交，并应用日志条目指令到状态机；

日志内容（Log）

每个日志条目内容包含： Leader 任期号和提案内容；

最上方的是日志条目索引（Log Index），

日志，则由有序号标识的一个个条目组成，
1）最开始的时候（蓝色），A 节点是 Leader，任期号为 1；
2）A 节点 crash 后，B 节点通过选举成为新的 Leader（绿色），任期号为 2；

我们假设上图描述的是 (2 hello<-world) 日志条目未提交前的各节点 Raft 日志状态；

Leader 会维护两个核心字段来追踪各个 Follower 的进度信息：
1）NextIndex，表示 Leader 发送给 Follower 节点的下一个日志条目索引；
2）MatchIndex，表示 Follower 已复制的最大日志条目的索引，比如上图 Follower C 的已复制最大日志条目索引为 5，而 A 为 4；

日志存储

Raft 模块设计实现上抽象网络、存储、日志等模块，它本身并不会进行网络、存储相关的操作，上层应用需结合自己业务场景选择内置的模块或自定义实现网络、存储、日志等模块 —— 即：日志并没有持久化，需要上层应用自己处理；日志发送也未实现，需要上层应用自己实现；

上层应用通过 Raft 模块的输出接口（如 Ready 结构），获取到待持久化的日志条目和待发送给 Peer 节点的消息后（如上面的 MsgApp 日志消息），需持久化日志条目到自定义的 WAL 模块，然后通过自定义的网络模块将消息发送给 Peer 节点；

当日志条目持久化到稳定存储中后，便可将日志条目追加到稳定的 Raft 日志（即便这个日志是内存存储，节点重启时也不会丢失任何日志条目，因为 WAL 模块已持久化此日志条目，可通过它重建 Raft 日志）；

Raft 模块提供一个内置的内存存储（MemoryStorage）模块实现，etcd 使用的就是它，Raft 日志条目保存在内存中；

网络模块并未提供内置的实现，etcd 基于 HTTP 协议实现 peer 节点间的网络通信，并根据消息类型，支持选择 pipeline、stream 等模式发送，显著提高网络吞吐量、降低延时；

details in etcd

当收到 Client 的请求后，Leader 会向其 Raft Module 提交一个 put hello 为 world 提案消息（②），它的消息类型是 MsgProp；

Leader 的 Raft Module 获取到 MsgProp 消息后：

etcdserver 模块通过 channel 从 Raft 模块获取到 Ready 结构后，因 B 节点是 Leader，它首先会通过基于 HTTP 协议的网络模块将追加日志条目消息（MsgApp）广播给 Follower，并同时将待持久化的日志条目持久化到 WAL 文件中，最后将日志条目追加到稳定的 Raft 日志存储中；

各个 Follower 收到追加日志条目（MsgApp）消息，并通过安全检查后，它会持久化消息到 WAL 中，并将消息追加到 Raft 日志存储，随后会向 Leader 回复一个 MsgAppResp（应答追加日志条目）的消息，告知 Leader 当前已复制的日志最大索引（流程图中的序号 6 流程）

当 Leader 收到 MsgAppResp 消息后，会将 Follower 回复的已复制日志最大索引更新到 MatchIndex 字段，如下图 Follower C 的 MatchIndex 为 6，Follower A 为 5；

所示如图，其描述的是 hello 日志条目提交后的各节点 Raft 日志状态：

最后 Leader 根据 Follower 的 MatchIndex 信息，计算出一个位置，如果这个位置已经被一半以上节点持久化，那么这个位置之前的日志条目都可以被标记为已提交；

在该案例中，LogIndex = 6 其前的日志条目已被多数节点复制，那么他们状态都可被设置为已提交。Leader 可通过在发送 MsgHeartbeat 给 Follower 节点时，告知 Follower 已经提交的日志索引位置；

最后，各个节点的 etcdserver 模块，可通过 channel 从 Raft 模块获取到已提交的日志条目（流程图中的序号 7 流程），应用日志条目内容到存储状态机（⑧），返回结果给 Client（Leader 是先应用状态机，成功之后再返回 Client。Follower 收到 Msg 后先放入不稳定存储，然后回复 Leader，在异步应用状态机）；

通过以上流程，Leader 就完成同步日志条目给 Follower 的任务，一个日志条目被确定为已提交的前提是，它需要被 Leader 同步到一半以上节点上；

安全性

选举规则

Leader B 在应用日志指令 put hello 为 world 到状态机，并返回给 Client 成功后，突然崩溃，如果 A 成为 Leader 那么就会导致数据丢失（因为它并未含有刚刚 Client 已经写入成功的 put hello 为 world 指令）；

当节点收到选举投票的时候：
1）需检查候选者的最后一条日志中的任期号，若小于自己则拒绝投票；
2）如果任期号相同，日志却比自己短，也拒绝为其投票；

Folllower A 和 C 任期号相同，但是 Follower C 的数据比 Follower A 要长，那么在选举的时候，Follower C 将拒绝投票给 A， 因为它的数据不是最新的；

同时，对于一个给定的任期号，最多只会有一个 leader 被选举出来，leader 的诞生需获得集群一半以上的节点支持。每个节点在同一个任期内只能为一个节点投票，节点需要将投票信息持久化，防止异常重启后再投票给其他节点；

通过以上规则就可防止日志图 2 中的 Follower A 节点成为 Leader；

日志复制规则

在日志图 2 中，Leader B 返回给 Client 成功后若突然 crash ，此时可能还并未将 6 号日志条目已提交的消息通知到 Follower A 和 C，那么如何确保 6 号日志条目不被新 Leader 删除呢？ 同时在 etcd 集群运行过程中，Leader 节点若频繁发生 crash 后，可能会导致 Follower 节点与 Leader 节点日志条目冲突，如何保证各个节点的同 Raft 日志位置含有同样的日志条目？

Leader 完全特性是指如果某个日志条目在某个任期号中已经被提交，那么这个条目必然出现在更大任期号的所有 Leader 中。Leader 只能追加日志条目，不能删除已持久化的日志条目（只附加原则），因此 Follower C 成为新 Leader 后，会将前任 Leader 的 6 号日志条目复制到 A 节点；

为保证各个节点日志一致性，Raft 算法在追加日志的时候，引入一致性检查。Leader 在发送追加日志 RPC 消息时，会把新的日志条目紧接着之前的条目的索引位置和任期号包含在里面。Follower 节点会检查相同索引位置的任期号是否与 Leader 一致，一致才能追加，这就是日志匹配特性。它本质上是一种归纳法，一开始日志空满足匹配特性，随后每增加一个日志条目时，都要求上一个日志条目信息与 Leader 一致，那么最终整个日志集肯定是一致的；

常见问题

哪些场景会出现 Follower 日志与 Leader 冲突？

leader 崩溃的情况下可能 (如老的 leader 可能还没有完全复制所有的日志条目)，如果 leader 和 follower 出现持续崩溃会加剧这个现象。follower 可能会丢失一些在新的 leader 中有的日志条目，他也可能拥有一些 leader 没有的日志条目，或者两者都发生。

follower 如何删除无效日志？

leader 处理不一致是通过强制 follower 直接复制自己的日志来解决。因此在 follower 中的冲突的日志条目会被 leader 的日志覆盖。leader 会记录 follower 的日志复制进度 nextIndex，如果 follower 在追加日志时一致性检查失败，就会拒绝请求，此时 leader 就会减小 nextIndex 值并进行重试，最终在某个位置让 follower 跟 leader 一致。

为什么 WAL 日志模块只通过追加，也能删除已持久化冲突的日志条目呢？ 其实这里 etcd 在实现上采用了一些比较有技巧的方法，在 WAL 日志中的确没删除废弃的日志条目，你可以在其中搜索到冲突的日志条目。只是 etcd 加载 WAL 日志时，发现一个 raft log index 位置上有多个日志条目的时候，会通过覆盖的方式，将最后写入的日志条目追加到 raft log 中，实现了删除冲突日志条目效果

Does etcd RAFT guarantees durability ? · Issue #12589 · etcd-io/etcd · GitHub

参考文献

etcd 实战课（唐聪，腾讯云资深工程师，etcd 活跃贡献者）_极客时间