Raft 算法相关笔记。
1. 概述
一致性算法是在状态机复制的背景下提出，而状态机复制通常通过复制日志实现，保证复制日志在每个服务器上相同就是一致性算法的目的。Raft 通过使用强领导人的方式，将一致性问题分解为以下三个相对独立的子模块：
-
领导选举 (Leader election)：领导人处理所有的客户端请求，所以当现存领导人宕机之时，必须选举一个新的领导人，否则服务不可用。
-
日志复制 (Log replication)：领导人需要将从客户端接受到的日志条目(log entires，其实也就是请求)复制至集群中的其他节点，并且需保证其他节点的日志和自己相同
-
安全性 (Safety)：Raft 算法需要保证以下几点，才能满足一致性要求
Election safety：对于一个给定的任期号 (term)，最多只会有一个领导人选举成功Leader Append-Only: 领导人从不覆写或删除自己的日志条目，只会附加新的日志条目Log Matching: 如果两个日志在某一相同索引位置日志条目的任期号相同，那么我们就认为这两个日志从头到该索引位置之间的内容完全一致Leader Completeness: 如果某个日志条目在某个任期号中已经被提交 (commit)，那么这个条目必然出现在更大任期号的所有领导人中State Machine Safety: 如一服务器已将给定索引位置的日志条目应用至其状态机中，则其他任何服务器在该索引位置不会应用不同的日志条目
Safety: what a system must not do; Liveness: something does happen.
可以看出安全性是对领导选举和日志复制的额外约束，因此在后续介绍中，会将安全性相关的点穿插在领导选举和日志复制之中。
2. 相关术语
2.1. 状态
所有服务器上的持久性状态 (在响应 RPCs 之前已更新至可靠的存储设备中)
| 参数 | 说明 |
|---|---|
| currentTerm | 服务器已探知的最大任期号 (服务器首次启动时初始化为 0，单调递增) |
| votedFor | 当前任期内所投选票的候选者 ID (若无则为 null) |
| log[] | 日志条目；每个日志条目中包含了应用于状态机的命令，以及领导人收到该命令时的任期号 |
所有服务器上的易失性状态
| 参数 | 说明 |
|---|---|
| commitIndex | 已知已提交 (committed) 的最新日志条目的索引值 (初始为 0，单调递增) |
| lastApplied | 已被应用于 (applied) 状态机的最新日志条目的索引值 (初始为 0，单调递增) |
领导人的易失性状态
| 参数 | 说明 |
|---|---|
| nextIndex[] | 发送至其他节点的下一条日志的索引值 (初始值为领导人最新日志条目的索引值 $+1$) |
| matchIndex[] | 已知已复制至该节点的最新日志条目的索引值 (初始为 0，单调递增) |
2.2. RPC
AppendEntries RPC：领导人调用，用于日志复制和心跳检测
| 参数 | 说明 |
|---|---|
| Sends | |
| term | 领导人的任期号 |
| leaderId | 领导人 ID，因此跟随者可以据此将客户端请求重定向至领导人 |
| prevLogIndex | 紧邻新日志条目之前的日志条目的索引 |
| prevLogTerm | 紧邻新日志条目之前的日志条目的任期 |
| entries | 需要被保存的日志条目 (为了提高效率可能一次性发送复数条日志；用于心跳检测时，该项为空) |
| leaderCommit | 领导人的 commitIndex，用于更新跟随者的 commitIndex = min(leaderCommit, index of last new entry) |
| ————– | —————————————————————– |
| Results | |
| term | 供领导人判断自己的任期号是否已过期，按需更新 currentTerm |
| success | 值为 true 时表示跟随者所含日志条目可以和 prevLogIndex 以及 prevLogTerm 匹配 |
RequestVote RPC：候选人调用，用于征集选票
| 参数 | 说明 |
|---|---|
| Sends | |
| term | 候选人的任期号 |
| candidateId | 候选人 ID |
| lastLogIndex | 候选人最新日志条目的索引值 |
| lastLogTerm | 候选人最新日志条目的任期号 |
| ————– | —————————————————————– |
| Results | |
| term | 供候选人按需更新自己的 currentTerm |
| voteGranted | 值为 true 时表示候选人赢得此张选票 |
InstallSnapshot RPC: 领导人调用，用于将日志快照发送给跟随者，通常是将快照分为多个 chunks 后按序发送
| 参数 | 说明 |
|---|---|
| Sends | |
| term | 领导人的任期号 |
| leaderId | 领导人 ID，因此跟随者可以据此将客户端请求重定向至领导人 |
| lastIncludedIndex | 快照中包含的最后日志条目的索引值 |
| lastIncludedTerm | 快照中包含的最后日志条目的任期号 |
| offset | 该 chunk 在快照中的字节偏移量 |
| data[] | 该 chunk 的内容 |
| done | 如果这是快照的最后一个 chunk 时为真 |
| —————— | ————————————————————– |
| Results | |
| term | 供领导人判断自己的任期号是否已过期，按需更新 currentTerm |
3. 领导人选举
在 Raft 中，每个服务器节点都处于以下三种状态之一：领导人(leader)、跟随者(follower)或候选人(candidate)。其状态转移图如下所示：
3.1. 选举流程
Raft 使用心跳检测机制触发领导人选举。具体而言，领导人会周期性地向所有跟随者发送心跳包 (AppendEntries RPCs that carry no log entries) 来让跟随者知道自己的存活状态，如果一个跟随者在一段时间 (election timeout，选举超时) 内未收到领导人的心跳包，那么他就会认为当前系统中领导人不可用，从而发起选举以选出新的领导人。
跟随者转变成候选人开始选举后：
- Increment
currentTerm - Vote for self
- Reset election timer
- Send RequestVote RPCs to all other servers
候选人的结果可能为以下三种：
- 赢得选举，成为领导人: 当候选人从整个集群的大多数节点处获得了针对同一任期号的选票时赢得选举
- 其他服务器成为领导人: 候选人在等待选票时，若从其他节点接收到
AppendEntries RPC- 如该 RPC 中的
term不小于候选人的currentTerm，那么候选人会承认领导人合法，并切换至跟随者状态 - 如该 RPC 中的
term小于候选人的currentTerm，那么候选人会拒绝这次 RPC 并保持候选人状态
- 如该 RPC 中的
- 本次选举超时: 如果有多个跟随者同时成为候选人，那么选票可能会被瓜分以至于没有候选人可以赢得大多数节点的支持。当这种情况发生的时候，每一个候选人都会超时，然后通过增加当前任期号来开始一轮新的选举
- Raft 算法使用随机选举超时时间的方法来减少发生选票瓜分的情况
3.2. 选举原则
Raft 应用以下选举原则以确保 election safety(安全性第一条)：
-
每一个服务器按照先来先服务的原则，最多会对一个任期号投出一张选票
-
只有从整个集群的大多数节点处获得了针对同一任期号的选票时赢得选举
此处可以不要求 majority, 只要求 quorum 即可，详见后分布式时代: 多数派读写的"少数派"实现
-
在收到
RequestVote RPC时，除了检测 RPC 中的term，还会根据lastLogIndex和LastLogTerm判断候选人的日志是否比自己新，投票人会拒绝那些日志没有自己新的投票 RPC- 如果两份日志最后的条目的任期号不同，那么任期号大的日志更新
- 如果两份日志最后的条目任期号相同，那么日志比较长(index 大)的那个就更新
- 通过这条限制保证了能当选的候选人包含了所有已经提交的日志条目
-
Raft 在系统满足以下时间要求时可以选举并维持一个稳定的领导人：
$$broadcastTime \ll electionTimeout \ll MTBF$$
其中，广播时间(broadcastTime)指的是从一个服务器并行地发送 RPCs 给集群中的其他服务器并接收响应的平均时间；平均故障间隔时间(MTBF)就是对于一台服务器而言，两次故障之间的平均时间。
3.3. 选举相关问题思考
-
Q: 选举时为何要先投给自己？
A: 考虑 3 个节点的系统，当领导人宕机后，如果选举时不先投给自己，那么如何选举出新的 leader..
-
Q: 假设某个跟随者节点因网络分区成为孤立节点，由于接收不到来自领导人的心跳检测包，因此会不断发起选举 -> 选举超时，导致 term 一直增加。网络分区结束后回到原集群会将原领导人降级为跟随者，导致重新选举，造成服务中断，如何解决？
A: 将选举拆成两阶段提交的方式：
- 首先进行一轮 prevote，在 prevote 阶段并不会自增
currentTerm，仅在RequestVote RPC中令term = currentTerm + 1 - prevote 收到多数派的选票时，发起真正的选举
- 首先进行一轮 prevote，在 prevote 阶段并不会自增
4. 日志复制
在 Raft 中，领导人处理所有的客户端请求，因此领导人需要将从客户端接受到的日志条目(其实也就是请求)复制至集群中的其他节点，并且需保证其他节点的日志和自己相同。日志的组织方式大致如下图所示：
4.1. 日志特性
Raft 通过维护以下日志特性，而保证 Log Matching(安全性第三条)：
-
如果在不同日志中的两个条目拥有相同的索引和任期号，那么他们存储了相同的指令 (唯一性)
- 领导人在给定任期和索引值下，最多仅创建一条日志
- 日志条目的位置保证不会发生改变
-
如果在不同的日志中的两个条目拥有相同的索引和任期号，那么他们之前的所有日志条目也全部相同 (无空洞)
AppendEntries RPC一致性检查：领导人在发送AppendEntries RPC时会包含prevLogIndex和prevLogTerm信息，跟随者发现这两者不匹配时会拒绝该 RPC- 只有当一致性检查成功时，跟随者才会接受该 RPC 中的日志条目
AppendEntries RPC 一致性检查失败时的处理
- 当一个节点刚成为领导人时，他会将所有跟随者的
nextIndex值初始化为自己最新日志条目的index + 1 - 当
AppendEntries RPC一致性检查失败时，领导人会减小nextIndex值并进行重试，直至找到两者日志一致之处
通过这种机制，新的领导人不需要任何特殊的操作来恢复日志的一致性。他只需要进行正常的 AppendEntries RPC 操作，然后领导人和其他节点日志就能自动地趋于一致。
4.2. 提交日志 (commited)
- 当领导人将创建的日志条目复制到大多数的节点上时，日志条目就会被提交
- 与此同时，领导人日志中之前所有日志条目也会被间接提交，包括由其他领导人创建的日志条目
- 领导人不会通过判断多数派是否已复制的方式去提交之前任期的日志条目
- 一旦跟随者知道一条日志已被提交，那么他也会将该日志条目应用到本地的状态机中 (按照日志顺序)
- Raft 算法保证所有已提交的日志条目都已持久化并且最终会被所有可用的状态机执行
5. 成员变更
服务器直接从旧配置转换至新配置是不安全的，如下图所示，当集群节点数从 $3$ 增加至 $5$ 时，存在一个时间点，如在此时发生选举，同一任期内两个不同的候选人都可以选举成功，成为领导人：
- server 1 和 server 2 通过旧配置(3 节点)选举 server 1 为领导人
- server 3、server 4 和 server 5 通过新配置( 5 节点)选举 server 3 为领导人
5.1. 问题原因
引用 后分布式时代: 多数派读写的"少数派"实现 中对 majority 和 quorum 的解释：
majority：多数派；多于半数；$\ge \lfloor \frac{n}{2} \rfloor + 1$quorum: 法定人数，不一定是多数派，但需满足任意 $2$ 个 quorum 之间必须有交集(该条件保证了按照 quorum 集合选举出的领导人是唯一的)majority 显然满足 quorum 的约束条件，因此 quorum 是 majority 概念的一个推广
一般我们提到的 quorum (或 majority)，其实可以用节点集合 $Q$ 代表，我们把系统中所有的 quorum 集合记为 $\mathbb{Q} = \{Q_1, Q_2, \dots\}$，例如对于一个三节点系统 $\{a, b, c\}$，$\mathbb{Q} = \{ \{a, b\}, \{a, c\}, \{b, c\}, \{a, b, c\} \}$。
因此在上述成员变更问题中，是因为那个时刻 $\mathbb{Q} = \{ \{s1, s2\}, \{s3, s4, s5\} \}$，不满足 quorum 之间必须有交集的条件，所以会选举出两个不同的领导人出来。
5.2. 解决办法：Joint consensus
解决问题的关键点就是让 $\mathbb{Q}$ 满足集合中任意 $2$ 个 quorum 之间必须有交集这一约束条件。作者在论文中提出一个两阶段变更方案：
- 首先将集群切换至一个旧配置和新配置结合的过渡配置，称为
Joint consensus - 当
Joint consensus被提交后(复制到了多数派)，再将集群切换至新配置
在变更的过程中：
- 日志条目会被复制给集群中所有的节点，不论是该节点是使用新配置还是旧配置
- 使用新、旧配置的节点都可以被选举成为领导人
- 节点间达成一致 (针对选举和提交) 需要分别在两种配置上都获得大多数的支持
配置切换的具体流程如下图所示：
-
当领导人接收到一个配置变更请求时，其会将
Joint consensus: $C_{old, new}$ 作为日志条目应用并复制至其他节点- 此时 $\mathbb{Q} = \mathbb{Q}_{old}$，即达成一致只需旧配置上的 quorum 之间达成一致即可
集群配置信息作为特殊的日志条目存储和通信，所有服务器在将配置日志条目添加进其日志存储中时，其会立刻使用该配置进行之后的决策，而不论该配置日志条目是否已被提交
-
领导人使用 $C_{old, new}$ 配置的规则决定 $C_{old, new}$ 日志条目是否可以被提交，一旦 $C_{old, new}$ 被提交，则仅靠 $C_{old}$ 或 $C_{new}$ 配置无法在节点间达成一致，且
Leader Completeness保证了只有含有 $C_{old, new}$ 日志条目的节点才有可能被选举为领导人- $C_{old, new}$ 提交后，$\mathbb{Q} = \mathbb{Q}_{old, new} = \mathbb{Q}_{old} \times \mathbb{Q}_{new}$
-
在 $C_{old, new}$ 被提交后，领导人可以创建、应用一条关于 $C_{new}$ 配置的日志条目，随后将其复制至其他节点
- $\mathbb{Q} = \mathbb{Q}_{new}$
-
当领导人发现日志条目 $C_{new}$ 可以在新配置的规则下被提交，则变更结束，不在新配置中的节点可以安全从集群中移除
依然以往 $\{s1, s2, s3\}$ 中添加 $\{s4, s5\}$ 为例，如下所示，容易知道任意时刻 quorum 集合中任意两个 quorum 之间都有交集，因此可以被选举出的领导人是唯一的。
| 当前状态 | quorum 集合 $\mathbb{Q}$ |
|---|---|
| $C_{old, new}$ 已应用，未提交 | $\mathbb{Q}_{old} = \{ \{s1, s2\}, \{s2, s3\}, \{s1, s3\} \}$ |
| $C_{old, new}$ 已提交， $C_{new}$ 未应用 | $\mathbb{Q}_{old, new} = \{ \{s1, s2, s3\}, \{s1, s2, s4\}, \{s1, s2, s3, s4\}$, $\{s1, s2, s5\}, \{s1, s2, s3, s5\}, \{s1, s3, s5\}, \{s1, s2, s4, s5\}$, $\{s1, s2 ,s3, s4, s5\}, \{s1, s3, s4 , s5\}, \{s2 ,s3, s4\}$, $\{s2, s3 ,s5\}, \{s2 ,s3, s4, s5\} \}$ |
| $C_{new}$ 已提交 | $\mathbb{Q}_{new} = \{ \{s1 ,s2, s3\},\{s1 ,s2, s4\}, \{s1 ,s2, s5\}$, $\{s1 ,s3, s4\}, \{s1 ,s3, s5\}, \{s1 ,s4, s5\}$, $\{s2 ,s3, s4\}, \{s2 ,s3, s5\}, \{s2 ,s4, s5\}, \{s3 ,s4, s5\} \}$ |
Joint consensus 通过令配置变更中间状态的
$$\mathbb{Q}_{old,new} = \mathbb{Q}_{old} \times \mathbb{Q}_{new}$$
而非 $\mathbb{Q}_{old}$ 和 $\mathbb{Q}_{new}$ 简单求并集，从而满足了 quorum 集合的约束条件，避免了同一时刻可能有多个领导人被选举出来的情况。
5.3. 成员变更相关问题
-
Q: 当一个全新的服务节点加入集群时，因为其未存储任何日志条目，需要一段时间来追赶最新的日志，在追赶期间很可能集群无法提交新的日志条目 (3 节点集群加入 2 个新节点，且有个旧节点宕机时，此时集群不可用)，怎么办？
A: 新节点加入集群时以
non-voting的身份加入，也即其不参与决策过程，但是领导人会复制日志给新节点，待新节点追赶上最新的日志时，再给予其投票权。具体而言，在追赶日志阶段可以配置固定的 Rounds 数，新节点尝试在 Rounds 内追赶日志，一旦最后一轮追赶日志耗时小于
election timeout时，则认为新节点已追赶上最新的日志，给予其投票权，开始成员变更。 -
Q: 配置变更的时候，当服务器收到配置相关的日志条目时，会立即应用新配置，如果当前领导人不在新配置中，怎么办？
A: 对于这种情况，我们可以规定领导人在 $C_{new}$ 提交后再退位，进行选举。这意味着，存在这样的一段时间，领导人管理者集群，但是其自身无投票权，因此计算 $C_{new}$ 是否可提交时需将自身排除在外。
-
Q: 如果新配置需要移除部分节点，直接移除该节点可能会造成集群不可用：被移除的服务器由于没接收到来自领导人的心跳检测，因此会发起选举，这可能会导致领导人回退至跟随者状态 (领导人当前任期小于选举 RPC 中的
term)，即使选举出了新的领导人，被移除节点仍会因为选举超时而发起选举干扰集群运行。A: 跟随者在收到
RequestVote RPC时，可以判断在election timeout期间是否有收到当前领导人的心跳检测包，如有，则跟随者认为领导人可用，跟随者便不会更新currentTerm值，也不会投票。使用该策略，领导人如能够发送心跳检测给集群中的多数节点，那么他就不会被更大的任期号罢黜，从而避免被移除的服务器扰乱集群的正常运行。
5.4. 单步变更
Joint consensus 较为复杂，在实际的实现中大多会采用单步变更算法，也即每次仅从集群中添加/删除一个节点。
详细介绍可参考 TiDB 在 Raft 成员变更上踩的坑。
6. 日志压缩
在 Raft 中，每个节点独立地创建快照，其仅包括已被提交的日志条目。如下图所示，在快照中主要包含以下信息：
last included index: 被快照取代的最后一条日志的索引值last included term: 被快照取代的最后一条日志的任期号state machine state: 状态机状态
虽然快照由每个节点独立创建，但有时还是需要领导人发送快照至跟随者（如新加节点等）。此时，领导人可以使用 InstallSnapshot RPC 将快照分块发送至跟随者，跟随者在接收到快照后，依据 RPC 中的 lastIncludedIndex 和 lastIncludedTerm 信息，删除被快照包含的日志条目，保留未被快照包含的日志条目。
7. 客户端交互
-
Raft 中由领导人处理所有的客户端请求
- 客户端随机挑选集群中的一个节点进行通信，当该节点不是领导人时，那么该节点会拒绝客户端请求，并提供他最近接收到的领导人信息(
AppendEntries RPCorInstallSnapshot RPC中的leaderId)
- 客户端随机挑选集群中的一个节点进行通信，当该节点不是领导人时，那么该节点会拒绝客户端请求，并提供他最近接收到的领导人信息(
-
为了避免客户端请求因为重试而被执行多次，可以为每一个请求赋予一个唯一的序列号
-
虽然只读的请求不需要记录日志，但领导人直接返回结果至客户端时，可能因为该领导人被罢黜而导致返回脏数据。在不使用新增日志条目的情况下，如要保证读请求返回的正确性，需要做到以下两点：
- 领导人必须拥有关于被提交日志的最新信息
Leader Completeness保证了领导人拥有所有已被提交的日志- 但在领导人任期刚开始时，他可能不知道哪些日志已经被之前的领导人提交，为了知道这些信息，领导人可以在任期刚开始时提交一个空的日志条目
在单步变更时也是通过在任期开始提交一条 NoOp 的日志，避免已提交变更日志的丢失
- 领导人在处理只读请求之前必须依赖心跳机制检查自己的领导人身份
- 领导人必须拥有关于被提交日志的最新信息
8. 参考资料
-
In search of an understandable consensus algorithm (extended version)