深入解读Raft算法与etcd工程实现

作者：jettchen，腾讯 IEG 后台开发工程师

本文不对 raft 算法从头到尾细细讲解，而是以 raft 算法论文为起点，逐步解读 raft 算法的理论，帮助读者理解 raft 算法的正确性。然后，etcd 不仅是 raft 算法最为热门的工程实现，同时也是云原生 kubernetes 的核心存储，本文也对 etcd 的底层实现进行剖析，让读者在使用 etcd 组件的过程中能够做到心中有数。对 raft 算法足够熟悉的同学，也可以直接阅读 etcd 工程实现那块内容。

在 raft 算法中，每个机器节点的状态包含三种：leader、follower、candidate。系统在时间上被划分为一系列连续的任期 term，每个 term 的 leader 可以产生连续的 log，如下图所示。每个任期 term 可以选举出一个 leader，该 term 的 leader 选举出来后可以产生日志。异常情况下，一些任期 term 可能选举 leader 会失败而直接进入下一个 term，或者 leader 没有产生任何日志就超时从而进入下一个选举周期。

leader 节点需要将其产生的 log 复制给其他节点，当多数派节点收到 log 则表明该 log 可提交。对于集群机器更换或者扩缩容，leader 节点生成配置变更日志并且复制给其他节点来达成一致。

从上面对 raft 算法的介绍中，可以得出 raft 需要解决以下三个问题。后续章节将围绕这三个问题剖析 raft 算法的实现。

raft 如何安全地选举出一个 leader？

leader 如何将 log 安全地复制到其他节点？

集群如何安全地变更机器节点？

下图是 leader 选举的流程图。节点初始化的时候，首先进入到 follower 状态，一段时间内没有收到 leader 节点的心跳就会切换到 candidate 状态去竞选 leader。节点进入到 candidate 状态后，首先将自身任期 term 加一，然后给自己投票，并且向其他节点广播 RequestVote 投票请求。candidate 竞选 leader 的结果有三种：

拿到多数派投票，切换为 leader。

发现其他节点已经是 leader（其任期 term 不小于自身 term），则切换为 follower。

选举超时后重来一遍选举流程（比如多个 candidate 同时参与竞选 leader 导致每个 candidate 都拿不到多数派投票）。

candidate 每次选举时都会设置随机的选举超时时间，避免一直有多个 candidate 同时参与竞选。candidate 竞选成为 leader 后，就不停地向其他节点广播心跳请求，以维持自己的 leader 状态同时也为了阻止其他节点切换为 candidate 去竞选 leader。

另外有一种异常情况，比如某个机器网络故障导致它一直收不到 leader 的心跳消息，那它就会切换到 candidate 状态，并且会一直选举超时，那它就会一直增加自身的任期 term，当网络恢复正常的时候，原有 leader 就会收到较高任期 term 的请求从而被迫切换到 follower 状态，这样就会影响到整个集群的稳定性。因此在工程实现的时候，candidate 都会增加一个 preVote 预投票阶段。在预投票阶段，candidate 不增加自身 term 而只会广播投票请求，只有拿到多数派投票后才进入正式投票阶段，这样就可以避免由于网络分区导致集群的 term 不断增大进而影响集群的稳定性。

最后，因为日志复制只会从 leader 复制到其他节点，所以在选举的时候，必须确保新 leader 包含之前任期所有提交的日志。接下来我们来看 raft 是如何保证新 leader 一定包含之前任期所有提交的日志。

下图描述的是 leader 选举过程中，候选者 candidate 发出的投票请求协议。投票请求会带上候选者自身的任期 term、memberId、最新日志的任期 term 和 index，其他节点收到请求后如果发现候选者的任期 >= 自身任期 并且 候选者的最新日志 >= 自身的最新日志，则回复同意。

每条日志的元数据包括任期 term 以及一个自增的日志索引。日志大小的比较规则是：先比较日志的任期 term，term 相同则再比较日志的 logIndex。

下面用个例子来证明 leader 选举的安全性。比如有 5 台机器，多数派机器拥有最新提交的日志，如果此时有 1 台机器拿到了多数派投票成为 leader，因为两个多数派必然存在交集，所以被选出来的 leader，其日志必然 >= 最新提交的日志。因此可以得出 1 个结论：新 leader 节点一定包含最新提交的日志。

下图描述的是 leader 处理写请求过程中，向其他节点发出的日志复制请求协议。请求会带上 leader 自己的任期 term、memberId、本次待复制的日志列表、上一条日志的 prevLogIndex 和 prevLogTerm、已达到多数派一致而提交的最大日志索引 commitIndex。其他节点收到请求后，如果发现 leader 的任期 >= 自身任期 并且 日志一致性检查通过，则用请求中待复制的日志列表直接覆盖本地的日志，并且更新本地的 commitIndex。日志一致性检查的逻辑是：自身节点已存在的日志列表中如果包含请求中指定 prevLogIndex、prevLogTerm 的日志，则检查通过。

接下来用下图这个例子来讲解日志复制的过程。机器节点 d 作为 term 7 的 leader 节点，产生两条日志后发生异常，之后其中一台机器在 term 8 成功竞选成为 leader 并生成了一条新日志，这条新日志的 logTerm 为 8，logIndex 为 11。这个新任 leader 在将这条新日志复制给其他节点的时候，会带上前一条日志的元数据，也就是 prevLogTerm 为 6，prevLogIndex 为 10。刚开始由于只有节点 c 和 d 包含这个前一条日志而复制成功，其他节点则会拒绝复制。leader 节点收到复制失败的回包后，需要往前移动待复制的日志列表然后重新发送日志复制请求。例如 leader 节点能够成功向节点 b 复制日志的请求，该请求体的内容为：前一条日志的 prevLogTerm 为 4，prevLogIndex 为 4，而待复制的日志列表则包含从 logIndex 为 5 开始的所有日志。

日志复制到其他节点后，不同节点上的日志会满足一个匹配性质。不同节点上的两个日志条目，如果 logTerm 、logIndex 都相同，则有：

由于 leader 节点对于给定的任期 term、给定的 logIndex 至多创建 1 个日志条目，那么这两条日志必然包含相同的状态机输入。

因为存在日志复制请求的一致性检查，所以这两个节点上，位于这条相同日志之前的所有日志条目必然也会相同。

通过这个日志匹配性质，就可以总结出：所有节点都会拥有一致的状态机输入序列。这样，各个节点就可以通过一致的初始状态 + 一致的状态机输入序列 从而 得到一致的最终状态。

日志成功复制给多数派节点，就可以提交，进而 apply 到业务状态机。但日志提交的时候存在一个限制：不能直接提交之前任期 term 的日志，只能提交当前任期下的日志。

以下面这个图为例子，在集群处于状态 c 的时候，节点 S1 在 term 4 成为 leader，并且已经将 term 2 的日志复制给多数派，此时节点 S1 将 term 2 的日志 commit 后宕机。之后集群进入到状态 d，此时节点 S5 成为 leader 并且将 term 3 的日志复制给其他节点，这样就会导致之前已 commit 的 term 2 日志被回滚覆盖。

因此为了避免这个问题，之前节点 S1 在任期 term 4 的时候，不能直接 commit 之前任期 term 的日志，只能通过将自己任期 term 4 的日志复制给多数派从而 commit 自己任期内的日志，如图中状态 e 所示。而一旦自己任期 term 内的日志得到 commit，那么由于日志一致性检查的存在，那么之前任期 term 下的日志必然也达到了多数派一致，因此之前任期 term 的日志此时也可以安全地 commit。

集群在扩缩容或者机器节点发生故障的时候，我们需要对集群的成员进行变更。以下图为例，如果我们直接将集群的节点配置切换到新配置，由于无法将所有节点的配置同时切换到新配置，因此存在某一个时刻，server 1 和 server 2 可以形成老配置的多数派，server 3、server 4 和 server 5 可以形成新配置的多数派，这样在同一个任期 term 内就可以选举出两个 leader，使得集群产生脑裂。

那么如何解决这种成员变更的问题呢？有两种方式：1. 联合共识。2. 单成员变更。

如下图所示的联合共识中，集群分为三个阶段。

集群还在采用 Cold 配置，此时 Cold 配置中的多数派达成一致就可以做出决议。

向集群写入一个 Cold,new 的配置后，集群进入联合共识状态，此时需要 Cold 配置中的多数派与 Cnew 配置中的多数派同时达成一致才可以做出决议。