In Search of an Understandable Consensus Alg orithm (Extended Version)
寻找⼀种易于理解的⼀致性算法（扩展版）
这篇文章完全按照原 Raft 论文的结构做的笔记，没有遗漏论文中的任何细节，但是更简洁，有更清晰的分点划分，也加入了部分自己的理解。
文章目录- 1. 背景（Abstract & Introduction）
- 2. 复制状态机（Replicated state machines）
- 3. Paxos 算法的问题（What’s wrong with Paxos?）
- 4. 为了可理解性的设计（Designing for understandability）
- 5. Raft 共识算法（The Raft consensus algorithm）
- 两张图
- State （状态）
- AppendEntries RPC（追加待同步⽇志 RPC）
- RequestVote RPC（请求投票 RPC）
- Rules for Servers（服务器的规则）
- 5.1 Raft 基础（Raft basics）
- 5.2 Leader 选举（Leader election）
- 5.3 日志复制（Log replication）
- 5.3.1 **Leader 日志复制流程**：
- 5.3.2 **日志提交**：
- 5.3.3 日志一致性
- 5.3.4 日志不一致情况
- 5.3.5 不一致的恢复
- 5.4 安全性（Safety）
- 5.4.1 选举限制
- 5.4.2 之前任期已提交的日志条目
- 5.4.3 安全性证明
- 5.5 Follower 和 Candidate 崩溃（Follower and candidate crashes）
- 5.6 时间和可用性（ Timing and availability）
- 6. 集群成员变化（Cluster membership changes）
- 6.1 **两阶段提交：Joint Consensus**
- 6.2 实现细节
- 6.3 问题讨论
- 7. 日志压缩（Log Compaction）
- 7.1 **快照**基本思路
- 7.2 InstallSnapshot RPC
- 安装快照 RPC
- 7.3 问题讨论
- 8. 客户端交互（ Client interaction）
- 9. 算法实现和评估
- 10. 相关工作
⼀致性算法，或者说共识算法，让⼀组机器像⼀个整体⼀样⼯作，即使其中⼀些机器出现故障也能够继续⼯作。
Raft 是⼀种为了管理复制⽇志的⼀致性算法。
它将⼀致性算法分解成了⼏个关键模块：领导⼈选举、⽇志复制和安全性。同时它通过更强的⼀致性来减少状态机的数量。
总之，对比传统的一致性算法 Paxos，Raft 更清晰易懂，易于实现。
它有几个独特特性：
- 强领导者：例如⽇志条⽬只从领导者发送给其他的服务器，简化了对复制⽇志的管理并好理解。
- 领导选举：用随机计时器来选举领导者，基于心跳机制实现，用于解决冲突。
- 成员关系调整：使得集群在成员变换的时候依然可以继续⼯作。
一致性算法基于复制状态机。
⼤规模的系统中通常都有⼀个集群领导者（Primary，论文中用的 Leader），⼀个独⽴的的复制状态机管理领导选举和存储配置信息并且在领导⼈宕机的情况下存活下来。
在之前 VMware FT 中已经学过这个，复制状态机通常都是基于复制⽇志实现。
日志传递 Primary 所有操作记录，让所有 Backup 执行相同的指令序列，达到相同的状态。
图 1 ：复制状态机的架构
**保证复制⽇志相同就是⼀致性算法的⼯作。**一致性模块（图中 Consensus Module）接受客户指令，生成日志，和其他 Backup 通信传递日志。
实际使用的一致性算法有以下特征：
- 安全性：非拜占庭错误情况下，绝不会返回错误的结果
- 可用性：只要大多数机器正常就可保证可用。
- 不依赖时序保证一致性
- 一条指令大多数节点可一轮 RPC 完成，小部分慢节点不影响整体性能。
Paxos ⾸先定义 了⼀个能够达成单⼀决策⼀致的协议，⽐如单条的复制⽇志项。这⼀⼦集叫做单决策Paxos。然后通过组合多个 Paxos 协议的实例来促进⼀系列决策的达成。
Paxos 是大多数一致性算法的起点，理论上证明可行，但是有两个明显缺点：
- 特别难以理解。不直观、不透明。
- 理论可行，实际实现困难，不易于构建实践系统。
Raft 算法就是尝试克服以上缺点，替代 Paxos 的一致性算法。
4. 为了可理解性的设计（Designing for understandability）设计 Raft 的初衷：
- 提供⼀个完整的实际的系统实现基础：大大减少开发者的工作
- 任何情况下都是安全的
- ⼤多数的情况下都是可⽤的
- ⼤部分操作必须是⾼效的
- 可理解性：（最重要、最大挑战）保证普遍⼈都可以容易理解。
- 能够让⼈形成直观的认识：使系统的构建者能够在现实中进⾏必然的扩展。
为了可理解性做的工作：
-
问题分解：尽可能将问题分解成⼏个相对独⽴的、可被解决的、可解释的和可理解的⼦问题。
Raft 算法被分成领导⼈选举、⽇志复制、安全性和⻆⾊改变⼏个部分。
-
减少状态的数量来简化需要考虑的状态空间：使得系统更加连贯并且在可能的时候消除不确定性。
随机化⽅法增加了不确定性，但是有利于减少状态空间数量，通过处理所有可能选择时使⽤相似的⽅法。
使⽤随机化去简化 Raft 中领导⼈选举算法
Raft 是⼀种⽤来管理第 2 部分中描述的复制⽇志的算法。图2是这个算法的简略版，图3列举了这个算法的关键特性。
Raft 选举一个 Leader，给予管理所有复制日志的权限，由此实现一致性。
Leader 从客户接受指令，写入日志，复制到其他 Backup Server 上，在保证安全性时通知其他 Server 根据日志执行指令更新状态机。
Leader 大大简化了对复制日志的管理。leader 可以自行决定新日志写入位置，数据都从 Leader 流向其他 Server。当 Leader 宕机，其他 Server 中选举一个新 Leader。
由此 Raft 将一致性问题分解为三个子问题：
-
领导选举：旧 Leader 宕机选举新 Leader （5.2 节）
-
日志复制：Leader 接受日志，复制到其他节点并保证一致。
-
安全性：关键在于状态机安全（图 3）：某一节点应用某个日志条目到状态机，其他节点不能在此条目应用不同指令。（5.4 节）
此处还涉及一个额外的选举机制上的限制（5.2 节）
图2是 Raft 算法的简略版，图3列举了 Raft 算法的关键特性。
对这两张图片内容进行了全部翻译。
State （状态）图2：一个关于 Raft 一致性算法的浓缩总结（不包括成员变换和日志压缩）
所有服务器上持久存在的：
（在响应RPCs之前已在稳定的存储上进行更新）
| currentTerm | 服务器最后⼀次知道的任期号（初始化为 0，持续递增） |
| votedFor | 在当前获得选票的候选⼈的 Id（如果没有则为 null） |
| log[] | ⽇志条⽬集；每⼀个条⽬包含⼀个⽤户状态机执⾏的指令，和收到时的任期号 |
所有服务器上经常变的：
| commitIndex | 已知的最⼤的已经被提交的⽇志条⽬的索引值 |
| lastApplied | 最后被应⽤到状态机的⽇志条⽬索引值（初始化为 0，持续递增） |
在领导⼈⾥经常改变的：
（选举后重新初始化）
| nextIndex[] | 对于每⼀个服务器，需要发送给他的下⼀个⽇志条⽬的索引值（初始化为领导⼈最后索引值加⼀） |
| matchIndex[] | 对于每⼀个服务器，已经复制给他的⽇志的最⾼索引值 |
由 Leader 负责调⽤来复制⽇志（5.3）；也会⽤作心跳（5.2）
传入参数：
| term | 领导⼈的任期号 |
| leaderId | 领导⼈的 Id，以便于跟随者重定向请求 |
| prevLogIndex | 新的⽇志条⽬紧随之前的索引值 |
| prevLogTerm | prevLogIndex 条⽬的任期号 |
| entries[] | 准备存储的⽇志条⽬（表示⼼跳时为空；⼀次性发送多个是为了提⾼效率） |
| leaderCommit | 领导⼈已经提交的⽇志的索引值 |
返回值：
| term | 当前的任期号，⽤于领导⼈去更新⾃⼰ |
| success | 跟随者包含了匹配上 prevLogIndex 和 prevLogTerm 的⽇志时为真 |
接收者实现：
- 如果 term < currentTerm 就返回 false （5.1 节）
- 如果⽇志在 prevLogIndex 位置处的⽇志条⽬的任期号和 prevLogTerm 不匹配，则返回 false （5.3 节）
- 如果现有的⽇志条⽬和新的产⽣冲突（索引值相同但是任期号不同），删除现有的和之后所有的条目 （5.3 节）
- 追加⽇志中尚未存在的任何新条⽬
- 如果 leaderCommit > commitIndex ，令 commitIndex = min(leaderCommit, 新日志条目索引)
由候选⼈调⽤⽤来征集选票（5.2 节）
传入参数：
| term | 候选⼈的任期号 |
| candidateId | 请求选票的候选⼈的 Id |
| lastLogIndex | 候选⼈的最后⽇志条⽬的索引值 |
| lastLogTerm | 候选⼈最后⽇志条⽬的任期号 |
返回值：
| term | 当前任期号，以便于候选⼈去更新⾃⼰的任期号 |
| voteGranted | 候选⼈赢得了此张选票时为 true |
接收者实现：
- 如果term < currentTerm返回 false （5.2 节）
- 如果 votedFor 为 null 或者为 candidateId，并且候选人的日志至少和接受者一样新，那么就给它投票（5.2 节，5.4 节）
所有服务器：
- 如果commitIndex > lastApplied，那么就 lastApplied 加一，并把log[lastApplied]应用到状态机中（5.3 节）
- 如果接收到的 RPC 请求或响应中，任期号T > currentTerm，那么就令 currentTerm 等于 T，并切换状态为 Follower（5.1 节）
Followers（跟随者）（5.2 节）：
- 响应来自候选人和领导者的 RPC 请求
- 如果选举超时，都没有收到现任 Leader 的AppendEntries RPC，也没有给候选人投票：自己转变成候选人。
Candidates（候选人）（5.2 节）：
- 在转变成候选人后就立即开始选举过程
- 自增当前的任期号（currentTerm）
- 给自己投票
- 重置选举超时计时器
- 发送 RequestVote RPC 给其他所有服务器
- 如果接收到大多数服务器的选票，那么就变成 Leader
- 如果接收到来自新的 Leader 的 AppendEntries RPC，转变成 follower
- 如果选举过程超时，再次发起一轮选举
Leader（领导人）：
- 一旦成为领导人：发送初始的空 AppendEntries RPCs（心跳）给每个服务器；在空闲期间重复发送，防止选举超时（5.2 节）
- 如果接收到来自客户端的请求：附加条目到本地日志中，在条目被应用到状态机后响应客户端（5.3 节）
- 如果一个 follower 最后日志条目的索引值 index ≥ nextIndex，那么：使用 AppendEntries RPC 发送从 nextIndex 开始的所有日志条目：
- 如果成功：更新相应跟随者的 nextIndex 和 matchIndex
- 如果 AppendEntries 因为日志不一致而失败，减少 nextIndex 并重试
- 如果存在一个满足N > commitIndex的 N，并且大多数的matchIndex[i] ≥ N成立，并且log[N].term == currentTerm成立，那么令 commitIndex = N （5.3 和 5.4 节）
图 3：Raft 在任何时候都保证以上的各个特性
| 特性 | 解释 |
|---|---|
| 选举安全 | 对于一个给定的任期号，最多只会有一个领导人被选举出来（5.2 节） |
| Leader 只追加 | 领导人绝对不会删除或者覆盖自己的日志，只会增加（5.3 节） |
| 日志匹配特性 | 如果两个日志在相同的索引位置的日志条目的任期号相同，那么我们就认为这个日志从头到这个索引位置之间全部完全相同（5.3 节） |
| 领导人完全特性 | 如果某个日志条目在某个任期号中已经被提交，那么这个条目必然出现在更大任期号的所有领导人中（5.4 节） |
| 状态机安全特性 | 如果一个领导人已经在给定的索引值位置的日志条目应用到状态机中，那么其他任何的服务器在这个索引位置不会提交一个不同的日志（5.4.3 节） |
5.1 Raft 基础（Raft basics）
一个 Raft 集群通常包含 5 个节点，能容忍 2 个节点宕机。
Raft 集群的服务器都处于三个状态之一：
- Leader：只有一个，响应所有客户端请求
- Follower：其余都是，不发送只响应 Leader 或 Candidate 的请求。若客户向其请求，会重定向到 Leader。
- Candidate：选举新 Leader 时使用（5.2）
图 4：服务器状态。Follower 只响应来自其他服务器的请求。如果 Follower 接收不到消息，那么他就会变成 Candidate 并发起一次选举。获得集群中大多数选票的 Candidate 将成为 Leader。在一个任期内，Leader 保持身份直到自己宕机。
如图 5，Raft 把时间分割成任意长度的任期（term），用连续递增整数编号，任期开始即选举。Raft 保证一个任期只有一个 Leader。
图 5：时间被划分成一个个的任期（term），每个任期开始都是一次选举。在选举成功后，领导人会管理整个集群直到任期结束。有时候选举会失败，那么这个任期就会没有领导人而结束。任期之间的切换可以在不同的时间不同的服务器上观察到。
任期编号在 Raft 算法中充当逻辑时钟，每个节点都储存当前任期号，节点之间通信会交换任期号，当一个节点：
- 当前任期号比其他节点小，更新自己的任期号
- Leader 或 Candidate 发现自己任期号过期，立即转为 Follower
- 收到过期的任期号请求，拒绝请求。
节点之间通信使用远程过程调用（RPCs），包含两种（第7节还增加了第三种传送快照的）：
- **请求投票（RequestVote） RPCs：**Candidate 在选举期间发起（5.2）
- 追加条目（AppendEntries）RPCs：Leader 发起，用于复制日志和心跳（5.3）
节点未及时收到 RPC 响应会重试，能并行发起 RPCs。
5.2 Leader 选举（Leader election）- 刚开始所有节点都是 Follower。
- Follwer 一段时间没接收到消息即选举超时，发起新选举。
- Leader 周期性发送**心跳包（不含日志的 AE RPC）**给所有 Follower 来维持自己地位。
- Follwer 只要能收到 Leader 或 Candidate 的 RPC 就保持当前状态。
- 开始选举。Follower 自增 term（任期号）并转为 Candidate，并行向其他节点发送 RV RPC 等待给自己投票。
- 等待时收到 Leader 的心跳，且心跳中的任期不小于自己的当前任期，则自己变为 Follower。若小于自己的任期，则拒绝并保持 Candidate。
- 如果同时出现多个 Candidate，选票可能被瓜分，没有人得到多数选票。则等待超时后重新选举。
- Raft 使用随机选举超时时间（例如 150-300 毫秒）防止多次无人上任。每个节点开始选举时重制超时时间。可以让多数情况只有一个节点超时，进入下一轮赢得选举。
- 获得多数选票的 Candidate 变为 Leader。
- 每个节点在一个任期内，按先来先服务（5.4节还有额外限制）最多为一个 Candidate 投票。
- 成为 Leader 后向其他节点发送心跳建立权威。
- 把客户端请求指令追加到日志，然后并行发 AE RPC 给其他节点让其追加日志。
- 在日志被其他节点安全复制后（多数节点已复制），Leader 应用该指令到状态机并返回结果给客户端。
- 如果中途出现问题，Leader 会不断重复 AE RPC（甚至已回复客户端后）直到所有 Follower 都追加了该日志。
-
一条日志包含当前任期号和一条指令，也都有一个整数索引来表明它在日志中的位置。
-
Leader 决定什么时候能把日志安全应用到状态机，这样的日志条目为已提交（committed）。Raft 保证所有已提交日志都是持久化并最终被所有状态机执行。
Leader 把日志设为已提交后，还需要通知 Follower 应用日志到状态机，这个通知通过下一次 AE RPC（也许是心跳）附加 commitIndex。论文没有提到这里具体如何实现，6.824课程中讲了。
-
日志条目复制到大多数节点上时，就是已提交（例如图 6 的 7），且 Leader 中当前条目之前的日志也都已提交，包括其他 Leader 创建的条目（5.4）。Leader 记录最大已提交索引 leaderCommit，并放进所有 AE PRCs，其他节点由此得知 Leader 已提交位置，并按日志顺序应用到自己的状态机。
5.3.3 日志一致性图 6：日志由序号标记的条目组成。每个条目都包含创建时的任期号和一个状态机需要执行的指令。一个条目当可以安全的被应用到状态机中去的时候，就认为是可以提交了。
这样 Raft 能维持日志的一致性（也是图 3 中的日志匹配特性）：
-
在不同的日志中的两个条目拥有相同的索引和任期号，那么他们存储了相同的指令。
-
在不同的日志中的两个条目拥有相同的索引和任期号，那么他们之前的所有日志条目也全部相同。
追加日志的一致性检查：每次新条目 AE RPC 给 Follower，如果上一条索引任期不一致，则拒收新条目。所以一旦 AE RPC 返回成功，说明 Follower 所有日志和 Leader 相同。
正常情况下一致性检查不会失败，能一直保持一致。但是 Leader 在未完全复制日志时宕机会使日志不一致。例如 Follower 可能没有新Leader 有的条目，也可能有新 Leader 没有的条目，或者都有，如图 7。
5.3.5 不一致的恢复图 7：当一个领导人成功当选时，跟随者可能是任何情况（a-f）。每一个盒子表示是一个日志条目；里面的数字表示任期号。跟随者可能会缺少一些日志条目（a-b），可能会有一些未被提交的日志条目（c-d），或者两种情况都存在（e-f）。例如，场景 f 可能会这样发生，某服务器在任期 2 的时候是领导人，已附加了一些日志条目到自己的日志中，但在提交之前就崩溃了；很快这个机器就被重启了，在任期 3 重新被选为领导人，并且又增加了一些日志条目到自己的日志中；在任期 2 和任期 3 的日志被提交之前，这个服务器又宕机了，并且在接下来的几个任期里一直处于宕机状态。
Raft 中处理这种不一致方法是，Leader 强制 Follower 复制自己的日志，即覆盖 Follower 中所有冲突日志（安全性在5.4）。
Leader 找到最后和 Follower 一致的地方，删除 Follower 之后的冲突日志，发送自己的日志附加给 Follower。这些操作在 AE RPCs 一致性检查时完成：
-
Leader 对每个 Follower 维护下一个需发送的条目索引nextIndex，在刚上任时初始化为最新日志索引加一（图 7 中 11）。
-
Follower 日志不一致则拒绝 AE PRC，Leader 减小 nextIndex 重试直到成功，Follower 删除冲突日志并追加 Leader 日志。日志即保持一致。
这里可以优化，Follower 拒绝时返回冲突任期号的最早地址，Leader 下次就可以越过同任期号的冲突。但是此优化不一定有必要，因为实际很少发生。
所以 Leader 无需特殊操作就能恢复一致性，Leader 也从不会覆盖删除自己的日志（图3 Leader 只追加特性）。
日志复制机制展示了第 2 节的一致性特征：
- 只要大部分的机器是工作的就能正常复制日志和应用保证可用性；
- 一条指令大多数节点可一轮 RPC 完成，小部分慢节点不影响整体性能。
以上的讨论不能保证每个状态机按相同顺序执行相同指令。例如因故障缺少被提交日志的 Follower 可能被选为 Leader 并覆盖日志。
故需增加选举限制，保证图 3 中的领导人完整性，即领导人一定包含所有已提交日志条目。
5.4.1 选举限制某些一致性算法中需要额外复杂机制把缺少的日志传给 Leader。但是 Raft 保证 Leader 本来就有所有日志，所有日志都是单向从 Leader 传出去。
Raft 在等待投票时，RV PRC 包含 Candidate 的日志信息，投票人会拒绝日志没有自己新的投票请求。
投票人比较最后一条日志的索引值和任期号：
- 任期号不同，则任期号大的比较新
- 任期号相同，索引值大的（日志较长的）比较新
5.3 中介绍了，只要日志条目被存在多数节点，Leader 就知道此日志在自己任期已提交。
但 Leader 可能在提交之前崩溃，新 Leader 不知道保存在多数节点的的条目是否提交。例如图 8，存在多数节点的老日志仍可能被覆盖。
图 8：如图的时间序列展示了为什么领导人无法决定对老任期号的日志条目进行提交。在 (a) 中，S1 是领导者，部分的复制了索引位置 2 的日志条目。在 (b) 中，S1 崩溃了，然后 S5 在任期 3 里通过 S3、S4 和自己的选票赢得选举，然后从客户端接收了一条不一样的日志条目放在了索引 2 处。然后到 ©，S5 又崩溃了；S1 重新启动，选举成功，开始复制日志。在这时，来自任期 2 的那条日志已经被复制到了集群中的大多数机器上，但是还没有被提交。如果 S1 在 (d) 中又崩溃了，S5 可以重新被选举成功（通过来自 S2，S3 和 S4 的选票），然后覆盖了他们在索引 2 处的日志。反之，如果在崩溃之前，S1 把自己主导的新任期里产生的日志条目复制到了大多数机器上，就如 (e) 中那样，那么在后面任期里面这些新的日志条目就会被提交（因为S5 就不可能选举成功）。 这样在同一时刻就同时保证了，之前的所有老的日志条目就会被提交。
图 8 说明即使某日志被复制到多数节点也不代表它被提交。
所以 Raft 对日志提交条件增加一个额外限制：Leader 在当前任期至少有一条日志被提交（即超过半数节点复制），如图 8 中的（e）所示。而（c）中并没有提交 4 任期的日志。
所以新上任的 Leader 在接受客户写入命令前先提交一个 no-op（空命令），携带自己任期号的日志复制到多数节点，这样能保证选举限制成立。
5.4.3 安全性证明这里可以认为 2 和 4 日志的复制是原子的，不会如 © 一样单独提交 2，要么就 2 和 4 一起提交要么就都失败。
定义：上个任期 Leader 最后提交了日志 L，B为当前任期 Leader，某个拥有 L 的节点 C。
- 由于 L 已提交，所以多数节点复制了 L。
- 由于 B 当选，所以多数节点投票给 B。
- 由（1）和（2）可知，B 的选民中必然含有存在 L 的节点 C。
- 由于选举限制（投票人会拒绝日志没有自己新的投票请求），B 当选必须要日志比 C 新。
- 所以 B 的日志中必然含有日志 L。
- 由于日志匹配特性（一致性检查），B 包含 L 则 B 必定包含 L 之前的所有已提交日志。
- 由于 Raft 保证所有节点上已提交日志顺序一致，且当前应用日志小于等于提交日志（lastApplied ≤ commitIndex），状态机按序执行应用日志。
- 得证：所有节点上状态机必然最终一致。图 3 中状态机安全特性成立。
图 9：如果 S1 （任期 T 的领导者）提交了一条新的日志在它的任期里，然后 S5 在之后的任期 U 里被选举为领导人，然后至少会有一个机器，如 S3，既拥有来自 S1 的日志，也给 S5 投票了。
论文中使用了反证法。先假设 B 没有日志 L，推出矛盾得证假设不成立，过程差不多。
5.5 Follower 和 Candidate 崩溃（Follower and candidate crashes）前面都是讨论 Leader 崩溃，Follower和 Candidate 崩溃后的处理方式简单的多，Raft 只需要不断重试发送 RPCs 即可，崩溃重启后再执行 RPC。
Raft 的 RPCs 都是幂等的，重试不会产生问题。如果 Follower 发现 AE RPC 中的日志已经有了，它直接忽略这个请求。
5.6 时间和可用性（ Timing and availability）幂等操作的特点是其任意多次执行所产生的影响均与一次执行的影响相同。
Raft 的要求之一就是安全性不能依赖时间：整个系统不能因为某些事件运行的比预期快一点或者慢一点就产生了错误的结果。
但可用性不可避免要依赖时间，最关键在于 Leader 选举，需要满足如下时间要求：
b
r
o
a
d
c
a
s
t
T
i
m
e
<
<
e
l
e
c
t
i
o
n
T
i
m
e
o
u
t
<
<
M
T
B
F
broadcastTime << electionTimeout << MTBF
broadcastTime< 广播时间（broadcastTime） 一个节点并行发送 RPCs 给其他节点并接收响应的平均时间。 应比选举超时时间小一个数量级才能保证稳定的心跳。 广播时间大约是 0.5 毫秒到 20 毫秒，取决于存储的技术 选举超时时间（electionTimeout） 即 5.2 中选举超时时间限制。随机化使之难以瓜分选票。 只有选举超时时间是我们自己选择的。可能需要在 10 毫秒到 500 毫秒之间。 应比平均故障时间小几个数量级。Leader 崩溃后系统将在一个选举超时时间中不可用，此情况应很少出现。 平均故障间隔时间（MTBF） 一个节点两次故障之间的平均时间。 大多数服务器平均故障时间在几个月甚至更长，很容易满足时间的需求。 实践中会替换那些宕机的机器或者改变复制级别，手动暂停重启易出错且会有段时间不可用，所以需要自动化配置改变，并且将其纳入到 Raft 一致性算法中。 为了让配置修改机制安全，在转换的过程中同一个任期里不能够存在两个 Leader 同时当选。问题在于，一次性自动的转换所有服务器是不可能的，任何切换方法都是不安全的，所以在转换期间整个集群可能分裂成两个独立的多数（见图 10）。 图 10：直接从一种配置转到新的配置是十分不安全的，因为各个机器可能在不同时候进行转换。在这个例子中，集群配额从 3 台机器变成了 5 台。不幸的是，存在这样的一个时间点，两个不同的领导人在同一个任期里都可以被选举成功。一个是通过旧组合的多数（C_old），一个通过新组合的多数（C_new）。 为了保证安全性，配置更改必须使用两阶段方法。有些系统在第一阶段停掉旧的配置，集群就不能处理客户端请求；然后在第二阶段在启用新的配置。 在 Raft 中，集群先切换到一个过渡性配置，我们称之为 Joint Consensus（联合共识，共同一致）；一旦联合共识被提交，那么系统就切换到新的配置上。 Joint Consensus 是老配置和新配置的结合： Joint Consensus 允许独立的服务器在不影响安全性的前提下，在不同的时间进行配置转换，还可以让集群在配置转换的过程中依然响应客户端的请求。 集群配置在复制日志中以特殊的日志条目来存储和通信。图 11 展示了配置转换的过程： 在整个过程中没有哪个时候让 C-old 和 C-new 同时产生影响，保证了安全性。 图 11：一个配置切换的时间线。虚线表示已经被创建但是还没有被提交的条目，实线表示最后被提交的日志条目。领导人首先创建了 C-old,new 的配置条目在自己的日志中，并提交到 C-old,new 中（C-old 的大多数和 C-new 的大多数）。然后他创建 C-new 条目并提交到 C-new 中的大多数。这样就不存在 C-new 和 C-old 可以同时做出决定的时间点。 没有存储任何的日志条目新节点加入，复制日志条目需要时间，此时无法作为提交和选举决策的节点。 新节点设置保护期，此期间以没有投票权身份加入到集群中来，不参加选举投票和日志提交决策，直到日志同步完毕。 Leader 不是新配置成员。 Leader 在提交了 C-new 日志之后主动退位（回到 Follower 状态）。并且在复制提交 C-new 时自己不算半数之一。 被移除的服务器未关闭，可能会扰乱集群。因为它们不再收到心跳，就会一直超时发起带有新任期号的选举。 集群中节点在未达到选举超时时间前，不响应 RV RPC。即如果当前 Leader 能够在超时时间内发送心跳，Follwer 就能确认当前 Leader 存在而不响应新的投票请求。 日志不能无限增长，Snapshotting（快照）是最简单的压缩方法。在快照系统中，整个系统的状态都以快照的形式写入到稳定的持久化存储中，那个时间点之前的日志全部丢弃。 增量压缩，例如日志清理或者日志结构合并树也可行，这些方法每次只对一小部分数据进行操作，分散了负载压力。首先，选择一个已经积累的大量已经被删除或者被覆盖对象的区域，然后重写那个区域还活跃的对象，之后释放那个区域。 增量压缩需要增加复杂的机制来实现，而快照总是简单操作整个数据集合，简化了这个问题。日志清除方法需要修改 Raft，但是状态机可以使用和快照相同的接口实现 LSM tree（日志结构合并树）。 图 12：一个服务器用新的快照替换了从 1 到 5 的条目，快照值存储了当前的状态。快照中包含了最后的索引位置和任期号。 图 12 展示了 Raft 中快照的基本思路： 每个服务器独立的创建快照，只包括已经被提交的日志。大部分由状态机将当前状态写入到快照中，也包括少量元数据： 保留这些数据是为了支持快照后第一个 AE RPC 时的一致性检查，因为这个条目需要前一日志条目的索引值和任期号。 为了支持集群成员更新（第 6 节），快照中也将最后的集群配置作为最后一个状态条目存下来。一旦服务器完成一次快照，他就可以删除最后索引位置之前的所有日志和快照了。 Leader 必须偶尔通过 RPC 发送快照给一些落后的 Follower。一般发生于当 Leader 已经删除下一条需要发送给某 Follower 的日志条目的时候。例如一个运行非常缓慢的 Follower 或者新加入集群的服务器（第 6 节），这时让这个 Follower 更新到最新的状态的方式就是通过网络把快照发送给他们。 当 Follower 接收到 IS RPC 时，自己决定对于已经存在的日志该如何处理。 图 13：一个关于安装快照的简要概述。为了便于传输，快照都是被分成分块的；每个分块都给了跟随者生命的迹象，所以跟随者可以重置选举超时计时器。 由 Leader 调用，将快照的分块发送给 Follower。Leader 总是按顺序发送分块。 接收者实现： 这种快照的方式背离了 Raft 的强 Leader 原则，因为 Follower 可以在 Leader 不知情情况下创建快照，但是这是值得的。领导人的存在，是为了解决在达成一致性的时候的冲突，创建快照的时候一致性已经达成，不存在冲突了，所以没有领导人也是可以的。数据依然是从领导人传给跟随者，只是跟随者可以重新组织他们的数据。 而只有 Leader 创建快照，发送给所有的 Follower 的方案有三个问题： 还有两个问题影响快照性能： 什么时候应该创建快照？过于频繁会浪费大量的磁盘带宽和其他资源；频率太低要承受耗尽存储容量的风险，也增加了从日志重建的时间。 当日志大小达到一个固定大小的时候就创建一次快照。如果这个阈值设置的显著大于期望的快照的大小，那么快照对磁盘压力的影响就会很小了。 写入快照需要花费显著的一段时间，并且我们还不希望影响到正常操作，如何处理？ 写时复制的技术，这样新的更新就可以被接收而不影响到快照。具有函数式数据结构的状态机天然支持这样的功能。另外，操作系统的写时复制技术的支持（如 Linux 上的 fork）可以被用来创建完整的状态机的内存快照（我们的实现就是这样的）。 写时复制的技术在 GFS 论文中快照部分有提到，类似假创建、惰性创建。master 记录操作到磁盘后创建拷贝文件的元数据，其与原文件指向相同 chunk。即只创建了一个元数据指针。此时对原文件和副本的读实际都是同一个 chunk。一旦发生写操作，无论原文件还是拷贝文件的修改都会导致在本地机器创建一个新chunk，并修改变更文件的元数据信息。 这一节将介绍客户端是如何和 Raft 进行交互的，包括： 这些问题对于所有基于一致性的系统都存在，并且 Raft 的解决方案和其他的也差不多。 客户端发送所有请求都要给 Leader。 第一次通信会随机联系一个节点，如果不是 Leader ，会被拒绝并提供最近接收的 Leader 信息（AE RPC 包含 Leader 地址），即重定向。 如果 Leader 宕机，请求超时，客户重试即可。 Raft 的目标是要实现线性化语义（每次操作立即执行，在调用和收到回复之间只执行一次） 若 Leader 提交了客户端的操作日志，在回复客户端之前宕机，客户端重试。此时该指令可能执行两次。 解决方案是客户端对每条指令赋予唯一序列号，状态机接受的序列号被执行的指令直接返回结果。 只读操作可以不需要记录日志，但是旧 Leader 响应客户端时可能已经卸任，此时返回的是脏数据。需要两个额外机制保证不返回脏数据： 可选项：Leader 可以通过心跳机制实现租约机制，但是这种方法依赖时间来保证安全性（假设时间误差是有界的）。 参考下 GFS 中的租约机制 后面的部分不是论文重点了，不详细写了。 从三个方面来评估 Raft 算法： 可理解性：比 Paxos 好多了 正确性：前面已经证明过了 性能：和 Paxos 差不多 选举超时时间随机化能大大加快领导人选举过程收敛。 通过减少选举超时时间可以减少系统的宕机时间，但是继续减小会违反 Raft 的时间不等式需求。建议使用 150-300 毫秒。 介绍了一些其他一致性算法的工作。 Raft 和 Paxos 最大的不同之处就在于 Raft 的强 Leader 特性。 Raft 比 VR 和 ZooKeeper 拥有更少的机制因为 Raft 尽可能的减少了非领导人的功能。 Raft 的强领导人模型简化了整个算法，但是同时也排斥了一些性能优化的方法。例如，平等主义 Paxos （EPaxos）在某些没有领导人的情况下可以达到很高的性能。 结论 感谢 参考
6. 集群成员变化（Cluster membership changes）
6.3 问题讨论
7. 日志压缩（Log Compaction）
7.1 快照基本思路
7.2 InstallSnapshot RPC
安装快照 RPC
参数 解释 term 领导人的任期号 leaderId 领导人的 Id，以便于跟随者重定向请求 lastIncludedIndex 快照中包含的最后日志条目的索引值 lastIncludedTerm 快照中包含的最后日志条目的任期号 offset 分块在快照中的字节偏移量 data[] 原始数据 done 如果这是最后一个分块则为 true 返回结果 解释 term 当前任期号（currentTerm），便于领导人更新自己
7.3 问题讨论
8. 客户端交互（ Client interaction）
10. 相关工作
