In Search of an Understandable Consensus Algorithm (Extended Version)

寻找可理解的共识算法 (扩展版) [Extended Paper] [Original Paper]
ATC’14 (Original)

摘要

Raft 是一个用于管理复制日志的共识算法.
Raft 更易于理解, 且为构建实际的系统提供了更好的基础.
Raft 分离了共识的关键要素, 如领导者选举、日志复制、安全性; 并通过更强的一致性来减少状态数量.
Raft 包括一个使用重叠多数(overlapping majorities)保证安全性的新机制来更改集群成员.

1 介绍

共识算法(consensus algorithms) 让一组机器作为一个协调的整体进行工作, 并在一些成员机器出现故障时也能继续运行.
Paxos 作为过去十年共识算法的主导十分难以理解, 且需复杂更改才能支持实际系统.
Raft 提高可理解性的技术: 分解(分离了领导者选举、日志复制和安全性)和状态空间缩减(降低了不确定性程度和服务器间不一致的方式).

Raft 新特性:

• 强领导者: 更强的领导形式. 如日志条目仅从领导者流向其他服务器. 简化了复制日志的管理并易于理解.
• 领导者选举: 使用随机计数器选举领导者. 基于心跳机制实现, 同时能简单快速解决冲突.
• 成员变更: 使用一种新的联合一致性(joint consensus)方法, 其中两种不同配置的大多数在转换期间重叠, 使得集群在配置更改期间可继续正常运行.

2 复制状态机

共识算法通常出现在复制状态机(replicated state machines)的上下文中.
复制状态机用于解决分布式系统中的各种容错问题, 通常使用复制日志(replicated log)实现.

保持复制日志的一致性是共识算法的工作.

实际系统的一致性算法的特性:

• 确保在所有非拜占庭条件下的安全性(从不返回错误结果), 包括网络延迟、分裂、数据包丢失、重复和重排. (一般把出现故障但不会伪造信息的情况称为"非拜占庭错误")
• 大多数服务器都可运行且通信, 共识算法就可用的.
• 不依赖时序来确保日志的一致性.
• 当集群大多数响应了一轮 RPC 时指令即可完成, 少数慢速服务器不影响系统整体性能.

3 Paxos 的问题

Paxos 第一个定义了一种能够就单个决策达成一致的协议, 例如单个复制的日志条目, 这一子集称为单决策(single-decree) Paxos. 然后通过组合多个 Paxos 实例来促进一系列决策的达成, 例如日志(多 Paxos, mutil-Paxos).

Paxos 的两个明显缺点:

• 非常难以理解
• 没有为构建实际的工程实现提供良好的基础

4 为了可理解性而设计

设计 Raft 的目标:

• 必须为系统构建提供完整且实用的基础
• 必须在所有条件下是安全的, 在典型操作条件下是可用的
• 对于常见操作必须是高效的
• 最重要, 最困难的挑战 —— 可理解性: 广大受众必须能够轻松理解; 必须能够形成对算法的直觉

使用的两种普遍适用的技术:

1. 问题分解: 尽可能将问题划分为可相对独立地解决、解释和理解的独立部分.
   Raft 中分离了领导者选举、日志复制、安全性和成员变更
2. 通过减少状态数量来简化状态空间: 尽可能使系统更加一致并消除不确定性.
   随机化方法虽然引入了不确定性, 但有利于减少状态空间.
   Raft 使用随机化来简化领导者选举.

5 Raft 共识算法

Raft 是一种用于管理(第 2 节描述的)复制日志的算法.


Raft 通过选举出一位领导者(leader), 让领导者全权负责管理复制日志来实现共识. 领导者接受来自客户端的日志条目, 在其他服务器上进行复制, 并告知服务器可以安全地将日志条目应用于其状态机的时机.
领导者可以简化复制日志的管理: 领导者可以自行决定日志中放置新条目的位置, 数据从领导者流向其他服务器.
领导者出现故障或者与其他服务器断开连接时, 将选出新的领导者.

Raft 将共识问题分解为三个相对独立的子问题:

• 领导者选举: 当现有领导者故障时, 必须选出新领导者
• 日志复制: 领导者接受来自客户端的日志条目并在集群中复制, 强制其他节点的日志与自己的日志一致
• 安全性: Raft 的关键安全特性为状态机安全特性(State Machine Safety Property)

5.1 Raft 基础

Raft 集群包含多个服务器(满足"2f+1 复制"原则). 任何给定时间, 服务器都处于三种状态之一:

• 领导者(leader): 只有一个领导者, 处理所有客户端请求.
• 跟随者(follower): 其他服务器都是. 不发送请求, 被动响应领导者和候选者的请求. 客户端联系跟随者, 则会将其重定向领导者.
• 候选者(candidate): 用于选举出新领导者.

任期:
Raft 把时间划分为任意长度的任期(term), 用连续整数编号. 每届任期开始于一次选举, 其中一名或多名候选者尝试成为领导者. 若一名候选者赢得选举, 则担任任期余下时间的领导者. 若选举导致分裂投票(split vote), 任期将以无领导者结束, 并开始新的任期(新的选举). Raft 确保在给定任期至多一名领导者.
任期在 Raft 中充当逻辑时钟, 以让服务器检测过时信息.
每个服务器存储一个当前任期(current term)编号, 该编号随时间单调递增.
服务器通信时都会交换当前任期编号: 若一个服务器的当前任期小于另一个, 则将其当前任期更新为较大值; 若候选者或领导者发现其任期已过时, 则恢复为跟随者状态; 若服务器收到带有过期任期编号的请求, 则会拒绝该请求.

Raft 服务器间通信使用远程过程调用(RPC), 基本的共识算法只需要两种(第 7 阶添加了第三种 RPC 用于服务器间传输快照):

• 请求投票(RequestVote) RPC: 由候选者在选举期间发起
• 追加条目(AppendEntries) RPC: 由领导者发起以复制日志条目并提供一种形式的心跳

5.2 领导者选举

Raft 使用心跳机制触发领导者选举.
服务器以跟随者状态启动, 只要收到来自领导者或候选者有效的 RPC 则保持跟随者状态.
领导者向所有跟随者发送周期性心跳(不携带日志条目的 AppendEntries RPC).
若跟随者在选举超时(election timeout)的时间内未收到任何通信, 其会假设没有可用的领导者并开始选举以选择新的领导者.

选举过程:

1. 跟随者递增当前任期编号并转换到候选者状态.
2. 候选者为自己投票, 并向集群中的其他每个服务器并行发出 RequestVote RPC.
3. 候选者持续这种状态直到发生以下三种情况之一:
   1. 该候选者赢得了选举
      候选者若在同一任期内从整个集群的大多数服务器上获得选票, 则赢得选举.
      每个服务器在给定任期内已先到先得的方式为至多一名候选者投票.
      多数原则确保在给定任期内至多有一名候选者能够赢得选举. 候选者一旦赢得选举, 就转换为领导者并向其他服务器发送心跳消息, 以建立权威并阻止新的选举.
   2. 另一个服务器确立自己为领导者
      候选者可能从另一个自称领导者的服务器上接收到 AppendEntries RPC, 若该领导者的任期至少与候选者的当前任期一样大, 则候选者承认该领导者, 并转换为跟随者; 反之则拒绝该 RPC 并继续处于候选者状态.
   3. 一段时间内无领导者当选
      若多个跟随者同时成为候选者, 可能发生分裂投票, 没有候选者会获得大多数选票. 该情况下每个候选者都会超时, 并发起新一轮选举.
      Raft 使用随机选举超时时间来确保很少发生分裂投票且能迅速解决. 选举超时时间从固定间隔(如 150~300ms)中随机选择. 每个候选者在选举开始时重置选举超时时间.

5.3 日志复制

一旦选出了领导者, Raft 服务器集群就开始为客户端请求提供服务.
响应客户端请求的过程:

1. 客户端请求包含由复制状态机执行的指令. 领导者将指令作为一个新的条目追加到其日志中.
2. 领导者并行地向其他每个服务器发送 AppendEntries RPC 以复制该(刚刚追加到自己日志的)条目.
3. 当日志条目被安全复制后(备注: 如下文所述, 即条目被大多数服务器复制后), 领导者将该条目应用于其状态机, 并将执行结果返回给客户端.
4. 若跟随者崩溃或运行缓慢, 或者网络数据包丢失, 则领导者会无限重试 AppendEntries RPC (即使在响应客户端之后)直到所有跟随者最终存储了所有的日志条目.

日志条目组成:
每个日志条目存储一个状态机指令, 以及领导者收到该条目时的任期编号. 日志条目中的任期编号用于检测日志间的不一致性, 并确保图 3 中的某些特性. 每个日志条目还有一个整数索引以表示其在日志中的位置.

已提交的日志条目:
领导者决定将日志条目安全应用于状态机的时机, 这样的条目被称为已提交的(committed)条目.
已提交的日志条目是持久化的, 且最终将有所有可用的状态机执行.
一旦创建日志条目的领导者在大多数服务器上复制了该日志条目, 该日志条目就会被提交. 这会同时提交领导者日志中的所有之前的条目, 包括由以前领导者创建的条目.
领导者会跟踪其已知已提交的日志条目的最高索引(commitIndex), 并将该索引包含到未来将发送的 AppendEntries RPC (包括心跳消息)中, 以便其他服务器发现. 一旦跟随者得知日志条目已提交, 它就会将日志条目(按日志顺序)应用于其本地状态机.

Raft 日志匹配特性(Log Matching Property)的组成:

• 若不同日志中的两个条目具有相同的索引和任期, 则它们存储着相同的指令.
  -> 领导者在给定任期创建至多一条具有给定索引的日志条目, 并且日志条目在日志中的位置永远不变.
• 若不同日志中的两个条目具有相同的索引和任期, 则(该条目)前面所有条目构成的日志是相同的.
  -> 由 AppendEntries RPC 执行的一致性检查保证: 在发送 AppendEntries RPC 时, 领导者会将紧邻新条目的上一个日志条目的索引(prevLogIndex)和任期(prevLogTerm)包含在 RPC 参数中; 若跟随者在日志中没有找到具有相同索引和任期的条目, 则拒绝新条目. 因此 AppendEntries RPC 返回成功时, 跟随者的日志与领导者的日志直到新条目都是相同的.

处理日志不一致:
在正常操作期间, 领导者和跟随者的日志保持一致. 但领导者崩溃可能日志不一致(旧领导者可能没有完全复制完其日志中的所有条目). 跟随者可能缺少领导者有的条目, 也可能有领导者没有的额外的条目, 或二者都有.

Raft 中, 领导者通过强制跟随者复制自己的日志来处理不一致行. 这意味着, 跟随者日志中的冲突条目会被来自领导者日志的条目所覆盖.
领导者为了使跟随者的日志与自己的日志保持一致, 必须找到二者日志一致的最新日志条目, 删除跟随者日志在该点之后的所有条目, 并将领导者在该点之后的所有条目发送给跟随者. 这些操作在 AppendEntries RPC 的一致性检查时完成.

1. 领导者为每个跟随者维护 nextIndex, 即领导者将发送给该跟随者的下一个日志条目的索引. 当领导者第一次掌权时, 他将所有的 nextIndex 初始化为其日志最后一个条目的下一个的索引.
2. 如果跟随者与领导者的日志不一致, 则在下个 AppendEntries RPC 中, 一致性检查将失败.
3. AppendEntries RPC 被拒绝后, 领导者将递减 nextIndex 并重试 AppendEntries RPC.
4. 最终 nextIndex 达到领导者和跟随者匹配的点. 此时 AppendEntries RPC 将成功, 这将删除跟随者日志中的冲突条目, 并从领导者日志中追加条目. 这样, 跟随者的日志将会与领导者的日志一致, 并在任期的剩余时间内保持.

减少拒绝的 AppendEntries RPC 数量的优化(加速日志回溯):
跟随者拒绝 AppendEntries RPC 请求时, 返回值中包含冲突条目的任期以及该任期存储的第一个索引.
领导者则可以减少 nextIndex 直接跳过该任期的所有冲突条目. $\to$ 具有冲突条目的每个任期需要一个 AppendEntries RPC, 而非每个冲突条目需要一个 AppendEntries RPC.
优化非必要.

领导者在掌权时无需额外操作即可恢复日志一致性. 领导者不会覆盖或删除其日志中的条目(领导者只追加特性).

5.4 安全性

通过添加对服务器可以被选为领导者的限制来保证每个状态机以相同的顺序执行完全相同的指令. 该限制确保给定任期的领导者包含之前任期所提交的所有条目(领导者完整性特性).

5.4.1 选举限制

Raft 使用投票过程来阻止候选者赢得选举, 除非其日志包含所有已提交的条目. 候选者必选联系集群中的大多数服务器才能当选, 这意味着每个已提交的条目必须至少存在于其中一个服务器上. 如果候选者的日志至少与其他大多数服务器的日志一样"新(up-to-date)", 那么它将保存所有已提交的条目.
RequestVote RPC 实现了这一限制: RPC 包含候选者日志的信息, 如果投票者自己的日志比候选者的日志更加新, 则投票者拒绝投票.

Raft 比较日志更加新(more up-to-date)的方法: 比较日志中最后条目的索引和任期

• 若日志的最后条目具有不同的任期, 则具有较后任期的日志更加新.
• 若日志以相同的任期结束, 则更长的日志更加新.

5.4.2 提交之前任期的条目

如果领导者在提交条目之前崩溃, 未来的领导者将尝试完成该条目的复制. 然而领导者不能断定存储在大多数服务器上的之前条目是否被提交.
图 8 说明了即使旧日志条目被存储到了大多数服务器也可能被未来领导者所覆盖的情景. (备注: © 中任期 2 的条目在大多数服务器复制但未提交, 若 S1 崩溃此时任期 2 的条目便不再满足多数原则, 因此 S5 当选后会用任期 3 的条目去覆盖, 产生 (d) 的结果; 而若任期 4 的条目已在大多数服务器上复制, 则能保证先前任期 2 的条目已被提交, 且此时 S5 不满足引得选举的条件.)

Raft 不通过统计复制数目(counting replicas)来提交之前任期的日志条目; 只有来自领导者当前任期的日志条目通过统计复制数目来提交, 而由于日志匹配特性(Log Matching Property), 所有之前的条目都被间接提交. Raft 在提交规则中增加了这种额外的复杂性, 因为当领导者从以前的任期复制条目时, 日志条目保留其原始任期编号.

5.4.3 安全性论证

反证法论证领导者为完整性特性(Leader Completeness Property)成立:

假设任期 $T$ 的领导者($leade{r}_T$)在该任期提交了一个日志条目(目标条目), 但该日志条目没有被未来某个任期的领导者存储, 考虑最小的任期 $U>T$ 的领导者 ($leade{r}_U$) 未存储该目标条目.

1. 已提交的目标条目必须在选举时不存在于 $leade{r}_U$ 的日志中(领导者从不删除或覆盖条目).
2. $leade{r}_T$ 集群的大多数服务器上复制了该目标条目, 并且 $leade{r}_U$ 接收到了集群大多数服务器的选票. 因此至少有一个服务器(“投票者”)既接受了来自 $leade{r}_T$ 的目标条目又投票给了 $leade{r}_U$.
3. 投票者必须在投票给 $leade{r}_U$ 之前接受了 $leade{r}_T$ 已提交的目标条目, 否则它将拒绝来自 $leade{r}_T$ 的 AppendEntries 请求(其当前任期将高于 $T$). (备注: 若先投票给 $leade{r}_U$, 再接收到来自 $leade{r}_T$ 的 AppendEntries RPC, 因为当前任期 $U>T$, 所以会拒绝该请求.)
4. 投票者在投票给 $leade{r}_U$ 时仍存储该目标条目, 因为每个介入的领导者都包含该条目(根据假设), 领导者从不删除条目, 跟随者只有在与领导者冲突时才会删除条目. (备注: 根据假设在任期 $U$ 之前, 目标条目是被存储的, 且只有 $leade{r}_U$ 当选后, 投票者通过接收 $leade{r}_U$ 的AppendEntries RPC 才知道目标条目是冲突条目, 进而删除该条目.)
5. 投票者向 $leade{r}_U$ 授予选票, 因此 $leade{r}_U$ 的日志必须和投票者的日志一样新. 这样导致两个矛盾中的一个产生.
6. 首先, 若投票者和 $leade{r}_U$ 共享相同的最后的日志任期, 则 $leade{r}_U$ 的日志至少与投票者的日志一样长, 因此其日志包含了投票者日志中的每个条目. 这是一个矛盾, 因为投票者包含了已提交的条目, 而假设 $leade{r}_U$ 不包含. (备注: 这是根据比较日志更加新的第 2 个判据, 即以相同的任期结束的日志, 更长的更加新.)
7. 否则, $leade{r}_U$ 的最后的日志任期必须比投票者的任期大, 此外它还需比 $T$ 大, 因为投票者的最后的日志任期至少为 $T$ (它包含来自任期 $T$ 的已提交条目). 创建 $leade{r}_U$ 最后一个日志条目的更早的领导者必须在其日志中包含已提交的目标条目(根据假设). 然后根据日志匹配特性, $leade{r}_U$ 的日志还必须包含已提交的目标条目, 这是一个矛盾. (备注: 这是根据比较日志更加新的第 1 个判据, 即具有较后任期的日志更加新. 假设 $leade{r}_U$ 最后的日志条目任期为 $K$ 由 $leade{r}_K$ 追加, 则 $T<K<U$. 而任期为 $T$ 的目标条目根据假设也会在 $leade{r}_K$ 中且在最后任期为 $K$ 的条目的前面. 再根据日志匹配特性, $leade{r}_U$ 和 $leade{r}_K$ 具有相同索引且都为任期 $K$ 的条目, 因此前面的条目都是相同的, 因此也应该具有任期为 $T$ 的目标条目.)
8. 出现矛盾. 因此所有大于 $T$ 的任期的领导者必须包含在任期 $T$ 被提交的来自任期 $T$ 的所有条目.
9. 日志匹配特性保证未来的领导者也将包含交接提交的条目.

给定领导者完整性特性, 可以证明状态机安全特性(State Machine Safety Property).
Raft 要求服务器按日志索引顺序应用条目. 结合状态机安全特性, 这意味着所有服务器将以相同顺序将完全相同的日志条目应用于其状态机.

5.5 跟随者和候选者崩溃

若跟随者或候选者崩溃, 则未来发送给它的 RequestVote 和 AppendEntries RPC 将失败. Raft 通过无限重试来处理这种失败. 当崩溃的服务器重启, 则 RPC 将成功完成.
若服务器在完成 RPC 但在响应之前崩溃, 则它将在重启后会再接收到相同的 RPC.

Raft RPC 是幂等的. 例如, 跟随者会忽略收到的 AppendEntries RPC 中在其日志中已存在的条目. (备注: 收到重复的 RequestVote RPC, 服务器也会确保对候选者的投票结果前后相同.)

5.6 时间和可用性

Raft 的安全性不依赖于时间.
Raft 能够选出并维持一个稳定的候选者只要系统满足一下时间要求:

$$broadcastTime<<electionTimeout<<MTBF$$

• 广播时间($broadcastTime$): 服务器向集群值每个服务器并行发送 RPC 并接收其响应所需的平均时间.
  应比选举超时时间小一个数量级, 以便领导者能够发送心跳阻止跟随者开启新一轮选举.
  可能在 0.5~20ms 之间, 取决于存储技术.
• 选举超时时间($electionTimeout$): #5.2 节描述的进行领导者选举所需的超时时间.
  应比 MTBF 小几个数量级, 以便系统能稳定运行.
  只有选举超时时间是我们需要选择的(其余二者是底层系统的属性).
  可能在 10~500ms 之间.
• 平均无故障间隔时间(Mean Time Between Failure, MTBF): 单个服务器的平均故障间隔时间.
  通常是几个月甚至更长.

6 集群成员变更

Raft 配置变更的两阶段方法:

1. 集群首先切换到一个过渡性配置，被称为联合共识(joint consensus)
2. 一旦联合共识被提交, 系统就会过渡到新的配置

联合共识结合了新旧配置:

• 日志条目被复制到所有同时处于新旧配置中的服务器
• 任何新旧配置的服务器都可以作为领导者
• 达成一致(选举和条目提交)需要分别在新旧配置的服务器中获得多数选票

联合共识允许单个服务器在不同时间转换配置而不影响安全性; 还允许集群在整个配置变化过程中继续为客户端请求提供服务.

集群配置过程:
集群配置是通过复制日志中的特殊条目进行存储和通信的.
当领导者收到将配置从 $C_{old}$改为 $C_{new}$ 的请求时, 它将联合共识的配置(图中的 $C_{old,new}$)存储为一个日志条目, 并使用上文描述的机制复制该条目.
一旦某个服务器将新的配置条目添加到其日志中, 它就会将该配置用于所有未来的决策(一个服务器总是使用其日志中的最新配置, 无论该条目是否被提交). 这意味着领导者将使用 $C_{old,new}$ 的规则来决定 $C_{old,new}$ 的日志条目何时被提交.
若领导者崩溃, 一个新的领导者可能会在 $C_{old}$ 或 $C_{old,new}$ 配置下被选举出. 此时 $C_{new}$ 不能在这期间做出单方面的决策. (备注: 此处笔者猜测, 若新领导者有 $C_{old,new}$ 则和崩溃前一样继续配置变更, 若新领导者只有 $C_{old}$ 则 $C_{old,new}$ 被丢失需要重试配置更新以产生 $C_{old,new}$ 配置条目.)
一旦 $C_{old,new}$ 被提交, $C_{old}$ 和 $C_{new}$ 都不能在没有对方批准的情况下做出决策, 而且只有拥有 $C_{old,new}$ 日志条目的服务器才能被选为领导者.
此时, 领导者创建 $C_{new}$ 日志条目并将其复制到集群中.

配置相关的三个问题:

1. 问题: 新服务器最初可能未存储任何日志条目.
   解决: 在配置变更前引入一个额外阶段, 该阶段新服务器作为非投票成员(领导者复制给其日志条目, 但其不被认为是大多数服务器)加入集群; 直至日志追赶上.
2. 问题: 集群领导者不是新配置的成员.
   解决: 领导者在提交了 $C_{new}$ 日志条目后就会下台(返回到跟随者状态). 有一段时间(在提交 $C_{new}$ 时), 领导者在管理一个不包括自己的集群; 它复制日志条目, 但不把自己算在多数中.
3. 问题: 被移除的服务器(不在 $C_{new}$ 中的服务器)会扰乱集群. 这些服务器不会收到心跳从而超时开始新的选举.
   解决: 当服务器认为存在一个当前的领导者时就会忽略 RequestVote RPC. 具体来说, 若一个服务器在最小选举超时内收到 RequestVote RPC 则不会更新其任期或授予投票.

7 日志压缩

实际的系统中, 日志不能无限制地增长.
快照是最简单的压缩方法. 在快照中, 当前系统的整个状态被写入稳定存储的快照中, 然后丢弃截至该点的所有日志.

每个服务器独立进行快照, 只覆盖其日志中已提交的条目. 大部分工作是由状态机将其当前状态写入快照中, 还包含有少量 Raft 元数据:

• last included index(最后包含索引): 快照取代的日志中最后一个条目的索引(状态机应用的最后一个条目).
• last included term(最后包含任期): last include index 条目的任期.

这些元数据是用于支持快照后第一个日志条目的 AppendEntries 的一致性检查.
为了实现集群成员变更, 快照还需将最新的配置作为日志中 last included index 处的条目被包含.
一旦服务器完成快照写入, 即可删除直到 last included index 处的所有的日志条目, 以及任何先前的快照.

领导者必须偶尔向落后的跟随者发送快照, 这会发生在领导者已经删除了下一个需发送给跟随者的日志条目时; 接收方一般是速度特别慢的跟随者或新加入集群的服务器.
领导者通过 InstallSnapshot RPC 向落后过多的跟随者发送快照.

跟随者接收到此 RPC 的快照时的处理方法:

• 通常快照包含接收者日志中不存在的新信息, 此时跟随者丢弃其整个日志而由快照取代, 且此时可能有与快照冲突的未提交的条目.
• 若快照是接收者日志的前面部分(由于重传或错误), 则快照所涵盖的日志条目会被删除, 但快照后面的条目仍有效并必须被保留.

影响快照性能的两个问题:

1. 问题: 服务器必须决定何时进行快照. 快照太频繁, 就会浪费磁盘带宽和资源; 快照频率太低, 则容易耗尽存储并会增加重启时重播日志用时.
   解决: 在日志达到固定大小(以字节为单位)时进行快照. 将此大小设置的显著大于预期的快照大小, 那么快照的磁盘带宽开销将很小.
2. 问题: 写入快照可能需要大量时间, 但不希望延迟正常操作.
   解决: 写时复制(copy-on-write)技术. 例如, 函数式数据结构构建的状态机自然支持该技术; 另外, 操作系统有对写时复制技术的支持(如 Linux 上的 fork).

8 客户端交互

客户端如何与 Raft 交互, 包括客户端如何找到集群领导者以及 Raft 如何支持线性化语义. Raft 的解决方案与其他系统类似.

Raft 客户端将所有请求都发送给领导者:
当客户端第一次启动时, 它连接一个随机选择的服务器.
若客户端的第一次选择的不是领导者, 选择的服务器将拒绝客户端的请求, 并提供给客户端最近收到的领导者的信息(AppendEntries 请求包括领导者的网络地址).
若领导者崩溃, 则客户端的请求将超时; 客户端之后会随机选择服务器进行重试.

Raft 的目标是实现线性化的语义(linearizable semantics): 每个操作立即执行, 在调用和响应之间只执行一次
Raft 可能执行一个指令多次: 如领导者在提交日志条目后但在响应客户端前崩溃, 客户端将向新领导者重试该指令.
解决方案: 客户端为每个指令分配唯一序列号, 状态机跟踪每个客户端的最新序列号及响应, 若收到的序列号已被执行的指令则立刻响应并不重新执行.

线性化读取必须不返回脏数据, Raft 的额外预防措施:

• 让每个领导者在其任期开始时提交一个空白的无操作(no-op)条目, 以确定最新的已提交条目的信息.
• 领导者在处理只读请求之前与集群中的大多数交换心跳消息来检查自己是否已退位(若有新领导者被选出, 则其信息可能已过时).
• 领导者可以依靠心跳机制提供一种租赁机制(来确保不会读取脏数据), 但需要依靠时间来保证安全性.

---

笔者总结

本文的核心在于提出了一种新的分布式共识算法 Raft. 该算法更易于理解, 且为系统构建提供了更好的基础, 解决了之前 Paxos 共识算法在这两方面的问题.
论文的主要篇幅都在阐述 Raft 算法的具体实现.