Raft (Resilience And Fault Tolerance) 于 2014 年由斯坦福大学的 Diego Ongaro 和 John Ousterhout 首次提出, 旨在用一种更简单易懂的算法来代替艰涩的 Paxos 算法;
本文将详细记录一下 Raft 的原理及各种细节;
基本概念
角色及状态机
raft 有三种角色:
- Leader: 负责发起心跳，响应客户端，创建日志，同步日志;
- Candidate: Leader 选举过程中的临时角色，由 Follower 转化而来，发起投票参与竞选;
- Follower: 接受 Leader 的心跳和日志同步数据，投票给 Candidate;
超时机制
raft 有两种超时时间:
- HeartBeat Timeout: 心跳超时, 用于 Leader 定期向 Follower 发送心跳, 维持自己的 Leader 地位; 心跳的作用是告诉 Follower: 我仍然是 Leader, 不要发起选举;
- 实现方式: Leader 会定期 (默认 50 ms) 向所有 Follower 发送心跳请求 (
AppendEntriesRPC，即使没有日志条目也会发送);
- 实现方式: Leader 会定期 (默认 50 ms) 向所有 Follower 发送心跳请求 (
- Election Timeout: 选举超时, 集群中的 Follower 节点在 electionTimeout 时间内没有收到 Leader 的心跳信息就会晋升为 Candidate, 触发新一轮的选主流程 (
RequestVoteRPC), 选举超时时间为随机值 150 ~ 300 ms;- Minimum Election Timeout: 最小选举超时, 为了防止 Follower 可能会在 Leader 仍然正常工作的情况下误判 Leader 失效从而发起不必要的选举, 通常至少要设为为 HeartBeat Timeout 的 3 ~ 5 倍, 默认 150 ms;
流程详解
状态同步
Leader 发起日志同步的 AppendEntries RPC 请求数据结构如下:1
2
3
4
5
6
7
8prevLogIndex: long # 上一个 entry 的 index
prevLogTerm: long # 上一个 entry 的 leader 任期
entries:
- index: long
- term: long
- cmd: Command
leaderId: long # 用于 Follower 识别发送 RPC 的 Leader
leaderCommit: long # leader 已提交的 index, 用于通知 Follower 可以提交到哪个日志 index
日志复制
- 当 Leader 收到客户端请求后, 会生成一个 entry, 包含 < index, term, cmd >, 在将这个 entry 添加到自己的日志末尾后, 会向所有的节点发送 AppendEntries RPC 广播该 entry, 要求其他 Followers 复制这条 entry;
- 如果 Follower 接受该 entry, 则会将其添加到自己的日志后面, 同时返回给 Leader 已成功接受;
- 如果 Leader 收到了多数 Follower 的成功响应, Leader 会将这个 entry 应用到自己的状态机中, 随后将该 entry 置为 committed, 向客户端返回结果, 并将日志被 committed 的结果广播到整个集群, 以让各个 Follower 也将其应用到状态机;
状态快照
领导者选举
Candidate 发起选举的 RequestVote RPC 请求数据结构如下:1
2
3
4term: long
candidateId: long
lastLogIndex: long
lastLogTerm: long
随机 election timeout
每一个 Follower 会计算一个随机的 electionTimeout, 为了减少多个 Follower 同时成为 Candidate 的可能性, 从而提升 raft 选举的效率:
Leader 宕机重选
如下图所示, 当原 Leader B 宕机, A 率先触发 election timeout 变成 Candidate, 将任期 term 自增为 2, 并获得了 A 和 C 的多数派投票, 成功变为新的 Leader;
即使后续 B 重新上线, 当其检测到 A 的 term 大于自己时, 也会自动退变为 Follower;
选举资格限制
如 数据结构 所示, 每个 Candidate 发送 RequestVote RPC 时都会携带上一个 entry 的 < term, index > 信息, 当 Follower 收到投票信息时, 会比较自己与 Candidate 谁的日志更完整:
- 如果两个日志的 term 不同: 认为 term 大的更完整;
- 如果两个日志的 term 相同: 认为 index 大的更完整;
如果 Follower 发现自己的日志更加完整, 则拒绝投票给该 Candidate;
一般来说, 我们不保证旧 Leader 尚未 commit 的日志能顺利保留到下一任期中, 但要保证已经 commit 的日志不能丢失, 必须在下一任期中得到保留; 可惜, 仅仅依靠上述选举资格的限制规则并不能保证这一承诺;
Leader 交接的安全保证
在上述选举资格限制规则下, 如果我们允许新选举出的 Leader 直接提交上一任期的 entry, 就可能触发漏洞, 我们用一个例子来详细描述该问题;
假设一个 Raft 集群有 3 个节点:
- term = 1: R1 是 Leader, 产生 entry < term=1, index=1 >, 尚未开始复制, 接着 R1 崩溃了;
- term = 2: R3 当选新 Leader (由 R2、R3 投票产生), 产生 entry < term=2, index=1 >, 尚未开始复制, 也崩溃了;
- term = 3: R1 恢复, 并重新当选新 Leader, 假设此刻 R1 复制了其 term = 1 任期的 entry < term=1, index=1 > 到 R2, 从而完成了多数派的复制, 于是直接提交该 entry, 然后 R1 再一次崩溃;
- term = 4: R3 恢复, 并再次当选新 Leader (因为它 RequestVote 请求携带的 lastLogTerm = 2, 根据选举限制规则, R1 和 R2 均会认为 R3 比自己更完整), 假设此刻 R3 广播了其 term = 2 任期的 entry < term=2, index=1 >, 则 R1 和 R2 之前已经 commit 的 entry < term=1, index=1 > 将会被强制覆盖 (在 后续小节 将详细描述相关机制), 至此发生了已提交日志的丢失;
造成上述问题的根本原因是: 选举资格判定只能比较日志的新旧 (term 和 index), 而不关心日志是否已提交, 因此 Raft 必须禁止新 Leader 直接提交之前任期的日志;
为了解决该问题, Raft 要求新 Leader 必须先在当前任期开始时写入一条空命令日志 (no-op) 并提交它, 从而实现间接提交可能存在的之前任期的日志; 加上这个限制后, 我们再来推演一遍刚才的 case:
- term = 1: R1 是 Leader, 产生 entry < term=1, index=1 >, 尚未开始复制, 接着 R1 崩溃了;
- term = 2: R3 当选新 Leader (由 R2、R3 投票产生), 产生 entry < term=2, index=1, cmd=no-op >, 尚未开始复制, 也崩溃了;
- term = 3: R1 恢复, 并重新当选新 Leader, R1 立即写入 entry < term=3, index=2, cmd=no-op > 并发送到 R2, Raft 的日志一致性机制 可以保证 R2 最终能接收到 < term=1, index=1 > 和 < term=3, index=2 > 两条日志, R1 完成多数派的复制后提交该 entry, 然后 R1 再一次崩溃;
- term = 4: R3 恢复, 并尝试再次竞选 Leader, 可是它 RequestVote 请求携带的 lastLogTerm = 2, R1 和 R2 均认为其进度落后于自己, 不会投票给 R3, R3 将无法成为 Leader;
可见, 当任期开始立即写入一条 no-op 日志, 可以为新 Leader 建立起当前任期的权威, 向所有 Follower 宣告新王登基的事实; 在此之上 Raft 得以确保了已经 commit 的日志一定不会丢失: 当一个 Candidate 自身缺少已经在集群中 commit 的 entry 时, 一定不可能获得大多数选票, 从而不可能成为 Leader;
Leader 选举失败
当 raft 节点数为偶数时, 选举失败的可能性远大于奇数:
- 节点数为偶数: 只要有两个 Candidate 同时发起投票, 就有可能造成无人获得多数派, 导致本轮选举失败;
- 节点数为奇数: 至少要有三个 Candidate 同时发起投票才可能造成无人获得多数派;
但是 raft 随机 election timeout 的机制保证了 leader 选举的活性, 最终一定能通过有限的轮次选出 Leader;
强一致性保证
日志序列的强一致性
raft 的日志有两个基本性质:
1. 在两份日志里的两个 entry: 如果拥有相同的 index 和 term, 那么它们一定有相同的 cmd (即存储的命令是相同的);
- 第一个基本性质由 Leader 对 index 的唯一性保证: 在一个 term 内, 给定一个 index 最多创建一个 entry;
2. 在两份日志里的两个 entry: 如果拥有相同的 index 和 term, 那么它们各自前一个 entry 也一定相同;
第二个基本性质由 Leader AppendEntries RPC 请求的 数据结构 保证: Leader 会将新 entry 的前一条 entry 的 < prevLogIndex, prevLogTerm > 捎带进 AppendEntries RPC 中, 随后 Follower 的处理流程如下:
- 检查 term: 如果 Leader 的任期小于自己的当前任期, 则拒绝该 RPC (并返回 Follower 自己的 term);
- 检查 prevLogIndex 和 prevLogTerm: 如果 index - 1 != prevLogIndex || term - 1 != prevLogTerm, 则拒绝该 RPC;
- 上两个检查通过: 将 entries 中的条目追加到自己的日志中;
- 根据 leaderCommit 决定提交自己日志的 index, 并应用到状态机;
Leader 强制对 Follower 作日志回退的场景:
- Leader 给每一个 Follower 都维护了一个
nextIndex, 它表示 Leader 将要发送给该追随者的下一个 entry 的索引; - 当一个 Leader 刚开始自己的任期时, 它会将每个 Follower 的 nextIndex 初始化为它的最新的 entry index + 1;
- Leader 根据 Follower 的 nextIndex 决定发送给目标 Follower 的 AppendEntries 请求内容;
- 当 Follower 收到 Leader 的 AppendEntries 请求, 但检查 prevLogIndex 和 prevLogTerm 不通过而拒绝时:
- Leader 会将 nextIndex 递减然后重试 AppendEntries RPC;
- 最终 nextIndex 会达到一个 Leader 和 Follower 日志一致的地方, AppendEntries 将会返回成功, Follower 中冲突的 entries 会被移除, 并且补全所缺少的 Leader 的 entries;
- Leader 给每一个 Follower 都维护了一个
注意: 被 Leader 强制回退的 Follower 日志一定是旧 Leader 尚未提交的 entry: 因为 Leader 选举限制规则已经强保证了被选出来的新 Leader 一定拥有完整的已提交日志, 如果某个 entry 在新 Leader 没有记录, 它一定是没提交的 entry;
网络分区下的强一致性
当 raft 节点数为奇数时, 可以保证当集群内出现两个分区时, 有大多数节点的分区可以正常运行 (另一个分区因无法形成多数派共识而不能提交日志);
- 当原 Leader 就在大多数节点的分区:
- 大多数节点的分区继续运行, Leader 任期也不用变;
- 另一个分区的节点将一直处于 Candidate 的状态, 无法选举出自己的 Leader;
- 当原 Leader 不在大多数节点的分区:
- 大多数节点的分区将选出自己的 Leader, 任期 + 1, 并且能正常响应请求, 提交日志;
- 另一个分区将无法提交日志;
- 当网络分区消失后, 另一个分区的 Leader 将退变为 Follower, 分区内所有的节点将回退自己未提交的日志, 重新复制新 Leader 的日志;
