一看就懂，一学就会的 Raft 解析

说明：本文节选自清华大学出版社出版的《深入理解分布式共识算法》，略有修改。

粉丝福利，京东 5 折购买链接：https://item.jd.com/13677957.html，2023 年 4 月 5 日前有效。点击原文立即参与

全文导读

Raft 是一个强 Leader 的算法，我们可以根据 Leader 的状态来划分 Raft 的执行阶段。本文从以下三个方面行文。

• Leader 选举，集群中没有 Leader，该阶段将选举出日志最完整的成员晋升为 Leader

• 日志复制，集群正常运行，在该阶段处理事务请求

• 日志对齐，使得集群中所有成员的数据保持一致

Leader 选举

存在 A、B、C 三个成员组成的 Raft 集群，刚启动时，每个成员都处于 Follower 状态，其中，成员 A 心跳超时为 110ms，成员 B 心跳超时为 150ms，成员 C 心跳超时为 130ms，其他相关信息如图 1 所示。

图 1 Raft 模拟初始状态

由于集群中不存在 Leader，A、B、C 三个成员都不会收到来自 Leader 的心跳信息。其中，成员 A 的超时最短，最先进入选举状态，修改自己的状态为 Candidate，并增加自己的任期编号为 1，发起请求投票消息，如图 2 所示。

图 2  请求投票

成员 A 通过 RequestVote 广播自己的选票给成员 B、C，选票描述了成员 A 所拥有的数据，其包含成员 A 所处的 term 及最新的日志索引。成员 B、C 根据投票规则处理 RequestVote 消息。

• term 大的成员拒绝投票给 term 小的成员。

• 日志索引大的成员拒绝投票给日志索引小的成员。

• 一个 term 内只投出一张选票，采用先来先获得投票的原则。

很明显，成员 B、C 的 term 小于成员 A 的 term，也不存在比成员 A 日志索引更大的日志索引，并且 term 为 1 的选票还没有投给其他成员，因此成员 B、C 将 term 为 1 的选票投给成员 A 并更新自己的 term 为 1。

成员 A 获得包括自己在内的 3 张选票，赢得大多数选票，成员 A 晋升为 Leader，并向其他成员发送心跳信息，维护自己的领导地位，如图 3 所示。

图 3  Leader 晋升示意

如果成员 A 在等待投票超过约定的时间内没有收到多数派的选票，则会重置自己的超时，并结束本次选举进程。接着会有其他成员在等待心跳超时后发起 Leader 选举，在当前案例中，发起 Leader 选举的顺序为 A→C→B。

可能因为网络问题，使集群中的所有成员又发起了一轮选举，但是都没有获得多数派的选票，因此会随机产生新的超时，开始下一个循环的选举。

日志复制

在之前的文章中提过，日志复制是一个一阶段协商的过程，其中，日志项的提交操作由下一轮协商或者心跳消息来代替完成。因此处理事务请求，Raft 只需要发送一轮 AppendEntries 消息即可。

AppendEntries 消息除了会包含需要复制日志项的相关信息外，通常会携带 Leader 的 committedIndex 参数，标示着最后一个已提交的日志索引。每个 Follower 的本地都维护了 committedIndex，Follower 可以对比 Leader 的 committedIndex 来推进自己的提交操作。

接着如图 3 所示的示例，一个三个成员组成的集群，成员 A 为 Leader，成员 B 和 C 为 Follower，并且在集群中未提交任何日志项。Leader 收到客户端发送的 Add 请求后，Leader 和 Follower 依次执行以下步骤，如图 4 所示。

图 4  日志复制-复制

（1）Leader 将其封装成日志项追加到本地的日志中，日志索引为 1。

（2）Leader 通过 AppendEntries(0, <1, Add>)消息时将日志项广播给所有的 Follower。其中：

• 第一个参数为 committedIndex，即 Leader 最后提交的日志索引。

• 第二个参数为 Leader 所处的日志索引，即 Add 日志项的索引。

• 第三个参数为事务操作指令，即客户端的指令。

（3）Follower 收到消息，将日志项追加到本地的日志中。

此时，成员 A、B、C 都拥有日志项 Add 且都已在索引为 1 上完成了持久化。Follower 在处理完 AppendEntries 消息后需要回复 ACK 消息给 Leader，代表接受该日志项。Leader 收到多数派的 ACK 消息后，可以在本地提交该日志项并执行状态转移，之后将执行结果返回给客户端，如图 5 所示。

图 5  日志复制-回复

在当前场景中，成员 A 提交了索引为 1 的日志项，成员 B、C 仅仅拥有索引为 1 的日志项的所有信息但并未提交。成员 B、C 需要等待下一次 AppendEntries 消息，根据其 committedIndex 推进索引为 1 的日志项的提交操作。以心跳的 AppendEntries 消息为例，该 AppendEntries 消息仅携带了 committedIndex，此时 Leader 已经提交了索引为 1 的日志项，因此 committedIndex 为 1。Follower 则可以提交索引为 1 及其之前的所有日志项，如图 6 所示。

图 6  日志复制-心跳

日志对齐

我们使用<term, index>表示一个日志项，如表 1 所示为 Follower E 的日志索引 3 和 Follower D 的日志索引 4，与当前 Leader 处理不一致的情况。出现这种情况可能是 Follower E 和 Follower D 曾经当选过 Leader，并且在自己的 term 上提出了日志索引为 3 和 4 的日志项后立即宕机造成的。

表 1  日志对齐

要使 Follower E 和 Follower D 与 Leader 数据保持一致，大致步骤分为两步：寻找 nextIndex，复制 nextIndex 及其之后的日志项。在 Raft 中，这个步骤均可由 AppendEntries 消息来完成。这里以 Follower E 成员为例，交互细节如下：

（1）Leader 为 Follower E 初始化 nextIndex，nextIndex=lastLogIndex+1，即 nextIndex=6+1=7。

（2）Leader 通过 AppendEntries 发送探测消息，携带 preLogIndex（nextIndex-1）及 preLogTerm，其中，preLogIndex=6，preLogTerm=3。

（3）Follower 收到探测消息，对比索引为 6 的日志项，返回失败的响应给 Leader 并携带 lastLogIndex=3。

（4）Leader 收到失败的响应，更新 nextIndex=$lastLogInde{x}_{msg}$+1，即 nextIndex=4。

（5）Leader 发送下一轮的探测消息，其中，preLogIndex=3，preLogTerm=2。

（6）Follower 收到探测消息，对比索引为 3 的日志项，返回失败的响应给 Leader 并携带 lastLogIndex=3。

（7）Leader 收到失败的响应，此时$lastLogInde{x}_{msg}$+1 ≤ nextIndex，则 nextIndex 单调递减为 3。

（8）Leader 发送下一轮的探测消息，其中，preLogIndex=2，preLogTerm=1。

（9）Follower 收到探测消息，对比索引为 2 的日志项，返回探测成功的响应给 Leader。

（10）Leader 在成功探测到 nextIndex 之后，通过 AppendEntries 消息从 nextIndex 开始发送索引为 3 的日志项给 Follower。

（11）Follower 将以 Leader 的数据为准，覆盖本地的日志项并返回处理成功的响应给 Leader。

（12）Leader 收到成功响应后，单调递增 nextIndex，继续发送下一个日志项。直到 nextIndex 等于 Leader 的 lastLogIndex，意味着该 Follower 拥有 Leader 所有的数据，本次日志对齐即完成。