Raft

标签

分布式/共识算法

字数

6780 字

阅读时间

27 分钟

Raft 的设计目标写在标题里：可理解性（understandability）。Raft 的设计者对 Paxos 的判断是，它能用一页伪码给出，但工程落地时"在许多方面都能有可接受的替代实现"，而这种自由度本身构成了理解与实现的负担。Raft 的做法是主动削减自由度 —— 强制 leader 制、强制日志单向流动、把算法切成选举 / 复制 / 安全三块可独立讲清的部分。

代价是 Raft 不覆盖 Paxos 的全部场景（它只处理崩溃故障，不处理拜占庭故障，见 01-不可能性结果：FLP 与部分同步里故障模型那一层），换来的是一份能被完整讲清的安全性论证。

它承诺的五条性质

要保证的东西被列成五条：

性质	内容	章节
Election Safety	一个任期内最多选出一个 leader	5.2
Leader Append-Only	leader 从不覆盖或删除自己日志里的条目，只追加	5.3
Log Matching	两份日志若在同一下标与同一任期有条目，则该下标及其之前的所有条目完全相同	5.3
Leader Completeness	某个条目在某任期被提交，则该条目会出现在所有更高任期的 leader 的日志里	5.4
State Machine Safety	若某服务器已把某下标的条目应用到状态机，则没有任何其他服务器会对同一下标应用不同的条目	5.4.3

最后一条是我们要的最终结果 —— 它保证所有状态机按相同顺序执行相同命令。前四条是达到它的路径。

三种状态与任期

集群通常有 5 台服务器，可容忍 2 台故障。任一时刻每台服务器处于三种状态之一：

follower：被动的，自己不发起请求，只响应 leader 与 candidate 的请求；
leader：处理所有客户端请求（客户端若连到 follower，follower 把请求重定向给 leader）；
candidate：选举新 leader 时的中间状态。

时间被切成任意长度、连续编号的任期（term）。每个任期以一次选举开始；若选举失败（分裂投票），这个任期没有 leader 就结束了，随后开始新的任期与新的选举。

任期号在 Raft 里起逻辑时钟的作用，用途是检测过时信息（例如失效的 leader）：

每台服务器存一个 current term，单调递增；
通信时交换任期号，若自己的当前任期比对方小，就更新为对方的值；
candidate 或 leader 一旦发现自己的任期过时，立即退回 follower；
服务器收到任期号过时的请求会拒绝它。

同一任期内至多一个 leader 靠多数派保证：一个 candidate 需要获得整个集群多数派对同一任期的投票才能当选，而每台服务器在一个任期内至多投一票（先到先得）。两个 candidate 各拿多数派票是不可能的。

Raft 只用两种 RPC：

RequestVote：candidate 在选举中发起；
AppendEntries：leader 用来复制日志条目，同时兼任心跳。

服务器在没及时收到响应时会重试 RPC，并且并行发出以求性能。

三种状态与它们之间的转换：

一个任期一票、先到先得，加上「当选要整个集群的多数派」，合起来就是 Election Safety 的全部依据。

选举

启动时所有服务器都是 follower。只要持续收到合法的 RPC（来自 leader 或 candidate），follower 就一直待在 follower 状态。

leader 定期向所有 follower 发心跳（不带日志条目的 AppendEntries）维持权威。若某台 follower 在**选举超时（election timeout）**内没有收到任何通信，它就认为没有可用 leader，开始选举：

自增 current term；
转为 candidate；
投自己一票；
并行向集群中其他每台服务器发 RequestVote。

candidate 会一直待在这个状态，直到三件事之一发生：

它赢得选举：收到整个集群多数派对同一任期的投票 → 成为 leader，随即向其他所有服务器发心跳以确立权威、阻止新的选举；
别的服务器成为 leader：若收到的 AppendEntries 里带的任期号不小于自己的，就承认对方是 leader 并退回 follower；若小于，则拒绝并保持 candidate；
一段时间过去仍无胜者（分裂投票）：自增任期、开始新一轮选举。

竞选超时是随机化的，这是打散分裂投票的手段。建议是把超时从固定区间里随机取，使各服务器错开。

一次当选要走完的往返：

日志复制

leader 收到客户端命令后，把它作为新条目追加到本地日志，然后并行向所有 follower 发 AppendEntries 请求（携带条目）。条目在多数派上落盘后即视为已提交（committed），leader 把它应用到本地状态机并向客户端返回结果。若 follower 崩溃或响应慢，leader 会反复重试；follower 一旦恢复就会收到。

Log Matching 的两条与那条归纳

两条子性质：

若两份日志中同一下标、同一任期的两个条目存在，则它们存的是同一条命令。 依据是 leader 在一个任期内对同一日志下标至多创建一条条目，且日志条目的位置永不改变。
若两份日志中同一下标、同一任期的两个条目存在，则两份日志在该下标及其之前的所有条目完全相同。

第二条靠 AppendEntries 的一个一致性检查保证，这一步是证明的关键：

leader 在发 AppendEntries 时，同时带上紧邻新条目之前那条条目的下标与任期。若 follower 在自己日志的该位置找不到下标与任期都相同的条目，就拒绝新条目。

这个检查就是归纳步：日志的空初始状态满足 Log Matching，而每次扩展日志时一致性检查保持这条性质。 因此，每当 AppendEntries 成功返回，leader 就知道该 follower 的日志与自己的日志在新条目处完全一致。

日志会怎么不一致

正常运行时一致性检查从不失败。但 leader 崩溃会留下不一致（旧 leader 可能没有把自己的全部条目复制出去），而一连串的 leader 与 follower 崩溃会把不一致叠加起来。follower 的日志相对新 leader 可能有三种偏差：

缺少 leader 有的条目；
多出 leader 没有的条目；
两者兼有。

而且缺失与多余的部分可以跨多个任期。六种情形的组合（a–f）画在下面。

Raft 的处理方式是让 leader 强制覆盖 follower 的日志：找两份日志最近的一致点，删掉 follower 在该点之后的条目，再把 leader 在该点之后的条目全部发过去。实现上靠 nextIndex：

leader 为每个 follower 维护一个 nextIndex，表示下一条要发给它的条目的下标；
新 leader 上任时，把所有 nextIndex 初始化为自己日志最后一条的下标 + 1；
若不一致，下一次 AppendEntries 的一致性检查会失败；被拒后 leader 把 nextIndex 减一重试，直到找到一致点；
一旦 AppendEntries 成功，follower 里的冲突条目就被移除，leader 的条目被追加进去；此后在整个任期内保持一致。

leader 上台时不需要做任何特殊动作来修复一致性 —— 它只开始正常工作，日志会在 AppendEntries 一致性检查失败时自动收敛。

把三种偏差画在一起，编号沿用出处的分法（a–b 缺、c–d 多、e–f 兼有）：

leader 的日志：  1  1  1  2  2  2  2  3  3  3
                 └────── 每个数字是该条目的任期 ──────┘

a–b：follower 少了尾部的条目
      1  1  1  2  2
                └─ 从这个下标往后的都没有

c–d：follower 多出未提交的尾部条目
      1  1  1  2  2  2  2  3  4  4
                             └─ 多出来的部分可以来自别的任期

e–f：既缺又多，两种偏差各自都可以跨多个任期
      1  1  1  2  4  4
                   └─ 缺了 leader 的 2 2 3 3，尾巴上是自己的 4 4

nextIndex 找到一致点的过程：

安全性

前面两节还不足以保证所有状态机执行相同的命令序列。一个具体的失效场景：一台 follower 在 leader 提交若干条目时不可用，随后它当选 leader，用自己的新条目覆盖掉那些已提交的条目。 补上这个缺口需要一条对"谁可以当选 leader"的额外限制。

选举限制

任何基于 leader 的共识算法，leader 最终都必须持有全部已提交条目。 Viewstamped Replication 允许 leader 当选时不持有全部已提交条目，靠额外机制识别缺失条目并传给新 leader（在选举过程中或稍后）—— 评价是这带来可观的额外机制与复杂度。

Raft 走更简单的路：保证新 leader 从当选那一刻起就持有此前所有任期的已提交条目，不需要传输。这带来一个强性质：日志条目只从 leader 流向 follower（单向），leader 永不覆盖自己日志里的既有条目。

怎么保证？用投票过程本身：

candidate 必须联系多数派才能当选，因此每个已提交条目必然存在于这个多数派中的至少一台服务器上；
若 candidate 的日志至少与该多数派中任何一份日志一样新（up-to-date），它就必然持有全部已提交条目。

RequestVote 实现这条限制：RPC 里带上 candidate 日志的信息，投票者若发现自己的日志比 candidate 的更新，就拒绝投票。

"更新"的判定只有两条，按顺序比：

比较两份日志最后一条条目的任期 —— 任期更大的更 up-to-date；
任期相同时，日志更长（下标更大）的更 up-to-date。

提交规则：为什么不能数副本提交旧任期的条目

leader 可以断定自己当前任期的条目在多数派上落盘后已提交。但不能因为一个此前任期的条目在多数派上就断定它已提交。一张四格时序图说明了原因：

步骤	发生了什么
(a)	S1 是 leader，部分复制了下标 2 的条目（还没到多数派）
(b)	S1 崩溃；S5 靠 S3、S4 和自己的票在任期 3 当选，并在下标 2 接受了另一个条目
(c)	S5 崩溃；S1 重启并当选，继续复制 —— 此时任期 2 的条目已经复制到了多数派，但仍未提交
(d)	若 S1 此时崩溃，S5 可以靠 S2、S3、S4 的票当选，用自己的任期 3 条目覆盖掉它

而 (e) 给出了正确做法：若 S1 在崩溃前把一条自己当前任期的条目复制到多数派，这条就被提交了（S5 无法当选），此时它之前的所有条目也随之提交。

于是 Raft 的规则是：

从不通过计数副本的方式来提交此前任期的条目。只有 leader 当前任期的条目才通过计数副本提交；一旦当前任期的某条被这样提交，此前所有条目都因 Log Matching Property 而间接提交。

有些情况下 leader 可以安全断定更早的条目已提交（例如它存在于每一台服务器上），但为了简洁取了更保守的做法。

代价与收益：Raft 让条目保留原本的任期号（其他算法会让新 leader 用自己的新任期号重新复制旧条目）。由此换来两点 —— 条目更容易推理（任期号跨时间、跨日志保持不变），且新 leader 要发的旧条目更少（其他算法必须冗余发送以便重新编号）。

把那张时序图铺成状态（每个格子是该下标的条目任期）：

(a) S1 是任期 2 的 leader，把下标 2 的条目复制出去一部分 —— 只到 S1、S2
    S1 [1][2]   S2 [1][2]   S3 [1]   S4 [1]   S5 [1]

(b) S1 崩溃。S5 靠 S3、S4 与自己的票在任期 3 当选，在下标 2 写入另一个条目
    S1 [1][2]   S2 [1][2]   S3 [1][3]   S4 [1][3]   S5 [1][3]（leader）

(c) S5 崩溃；S1 重启并当选，继续复制。此时任期 2 的下标 2 条目已落到多数派，但「未提交」
    S1 [1][2]   S2 [1][2]   S3 [1][2]   S4 [1][3]   S5 [1][3]
                     └── 三个副本持有它 ⇒ 多数派，仍不算提交 ──┘

(d) 若 S1 此时崩溃：S5 靠 S2、S3、S4 的票当选，用自己任期 3 的条目覆盖下标 2
    ⇒ 那条「已在多数派上」的任期 2 条目被抹掉 —— 这就是不能数副本提交旧任期条目的原因

(e) 换一种做法：S1 在崩溃前先把一条「自己当前任期」的条目复制到多数派
    S1 [1][2][4]   S2 [1][2][4]   S3 [1][2][4]   S4 [1][3]   S5 [1][3]
    ⇒ 任期 4 这条被提交，它之前的条目随之全部提交；
      而 S5 再也选不上 —— S1、S2、S3 的日志都比它 up-to-date

Leader Completeness 的九步反证

反设该性质不成立：任期 $T$ 的 leader（ $l e a d e r_{T}$ ）提交了一条自己任期的条目，但某个更晚任期 leader 的日志里没有它。取最小的 $U > T$ ，使 $l e a d e r_{U}$ 没有存这条。

该条目在 $l e a d e r_{U}$ 当选时就不在它的日志里 —— 依据是 leader 从不删除或覆盖条目。
$l e a d e r_{T}$ 把条目复制到了多数派， $l e a d e r_{U}$ 也从多数派拿到了票 → 至少有一台服务器（记作 voter）既接受了 $l e a d e r_{T}$ 的这条条目，又投给了 $l e a d e r_{U}$ 。这台服务器就是矛盾的支点。
voter 必然是在投票给 $l e a d e r_{U}$ 之前接受了这条条目的 —— 否则它会拒绝 $l e a d e r_{T}$ 的 AppendEntries（它的当前任期已经更高）。
voter 在投票给 $l e a d e r_{U}$ 时仍然存着这条条目，理由是中间每一个 leader 都包含它（这一步用的是 $U$ 的最小性）、leader 从不删除条目、而 follower 只在与 leader 冲突时才删除。
voter 投了 $l e a d e r_{U}$ ，所以 $l e a d e r_{U}$ 的日志必须至少和 voter 的一样 up-to-date。这一步引出两种情形，两种都矛盾：
若二者最后一条条目的任期相同，则 $l e a d e r_{U}$ 的日志必须不短于 voter 的日志，于是它含有 voter 日志里的每一条 —— 矛盾（voter 含有那条已提交条目，而 $l e a d e r_{U}$ 被假设为不含）。
否则， $l e a d e r_{U}$ 最后一条的任期必须大于 voter 的，而且大于 $T$ （因为 voter 的最后一条任期至少是 $T$ —— 它含任期 $T$ 的那条已提交条目）。创建 $l e a d e r_{U}$ 最后那条条目的更早那个 leader 必然含有该已提交条目（由最小性假设），于是由 Log Matching Property， $l e a d e r_{U}$ 的日志必然也含它 —— 矛盾。
矛盾成立，故所有任期大于 $T$ 的 leader 都含任期 $T$ 内提交的全部条目。
Log Matching Property 进一步保证未来的 leader 也含有间接提交的条目（例如上面那张时序图 (d) 里的下标 2）。

有了 Leader Completeness，State Machine Safety 就容易证了：所有状态机会按相同顺序应用相同的条目。

follower / candidate 崩溃

比 leader 崩溃好处理得多，两者用同一套办法：无限重试。若 follower 或 candidate 崩溃，发给它的 RequestVote 与 AppendEntries 会失败，重试即可；服务器重启后 RPC 会成功。

有一个边界情况：服务器在完成 RPC 但还没响应时崩溃，重启后会再收到同一个 RPC。这不构成问题，因为 Raft 的 RPC 是幂等的 —— 例如 follower 收到一个 AppendEntries，其中包含它日志里已有的条目时，忽略这些条目即可。

时序与可用性

这条边界划得很清楚：

安全性绝不能依赖时序 —— 不能因为某个事件比预期发生得更快或更慢就产生错误结果。可用性必然依赖时序。

时序最关键的地方是 leader 选举。系统需要满足：

broadcastTime ≪ electionTimeout ≪ MTBF

broadcastTime：一台服务器并行向集群内所有服务器发 RPC 并收到响应的平均时间；
electionTimeout：选举超时；
MTBF：单台服务器的平均故障间隔。

两段不等号的用途不同：

broadcastTime 应比 electionTimeout 小一个数量级 —— 这样 leader 能可靠地发出阻止 follower 发起选举所需的心跳；配合随机化的选举超时，这也让分裂投票不太可能；
electionTimeout 应比 MTBF 小几个数量级 —— 这样系统才能稳定推进。leader 崩溃时系统会不可用大约一个 electionTimeout 的时间，希望这只是总时间里的很小一部分。

其中 broadcastTime 与 MTBF 是底层系统的属性，electionTimeout 是可以选的。具体量级：

Raft 的 RPC 通常要求接收方把信息持久化到稳定存储，因此 broadcastTime 约在 0.5 ms 到 20 ms 之间（取决于存储技术）；
于是 electionTimeout 通常取在 10 ms 到 500 ms；
典型服务器的 MTBF 是几个月或更长，容易满足第二段不等号。

成员变更：joint consensus

实践中需要换服务器（替换故障机器、改复制度）。停机改配置再重启会让集群在切换期间不可用，而且任何手工步骤都引入运维误操作的风险，所以 Raft 把配置变更自动化并纳入共识算法。

安全要求是：过渡期间任何时刻都不能出现同一任期两个 leader。

直接从旧配置切到新配置是不安全的 —— 无法原子地同时切换所有服务器，于是集群可能在过渡期分裂成两个互相独立的多数派（例如 3 台扩到 5 台时，可能一个 leader 拿到旧配置 $C_{o l d}$ 的多数派、另一个拿到新配置 $C_{n e w}$ 的多数派）。所以配置变更必须是两阶段的。

Raft 用**联合共识（joint consensus）**作为中间态，它同时包含新旧两个配置：

日志条目复制到新旧两个配置的所有服务器；
任一配置里的任何服务器都可以当 leader；
达成一致（选举与条目提交）需要同时取得旧配置与新配置各自的多数派。

joint consensus 允许各服务器在不同时刻切换配置而不损害安全，并且整个变更过程中集群可以继续服务客户端请求。

流程（配置本身以特殊日志条目的形式存储与传播）：

leader 收到从 $C_{o l d}$ 变到 $C_{n e w}$ 的请求，把联合配置 $C_{o l d, n e w}$ 作为日志条目存下并复制；
一旦某台服务器把这个条目加入自己的日志，它就用该配置做后续所有决策 —— 规则是"总是使用日志里最新的配置，不管它是否已提交"。因此 leader 会用 $C_{o l d, n e w}$ 的规则判定 $C_{o l d, n e w}$ 何时提交；
若 leader 崩溃，新 leader 可能在 $C_{o l d}$ 或 $C_{o l d, n e w}$ 下选出（取决于当选者是否已收到 $C_{o l d, n e w}$ ）。无论哪种， $C_{n e w}$ 在此期间都不能单方面做决定；
$C_{o l d, n e w}$ 提交后， $C_{o l d}$ 与 $C_{n e w}$ 都不能在没有对方批准的情况下做决定，且 Leader Completeness 保证只有持有 $C_{o l d, n e w}$ 日志条目的服务器能当选 leader。此时 leader 才能创建描述 $C_{n e w}$ 的条目并复制 —— 它同样被看到时即刻生效；
当 $C_{n e w}$ 在 $C_{n e w}$ 的规则下提交后，旧配置不再相关，不在新配置里的服务器可以关停。

两阶段切换的状态（配置本身以日志条目传播，所以每一步都是「看到即生效」）：

C_old
  │ ① leader 把联合配置 C_old,new 作为日志条目存下并复制
  ▼
C_old,new    出现该条目的服务器立刻用它做后续所有决策，不等它提交
  │            选举与提交都要同时取得 C_old 与 C_new 各自的多数派
  │ ② C_old,new 提交后，leader 才能创建描述 C_new 的条目并复制 —— 同样看到即生效
  ▼
C_new        ③ C_new 在 C_new 的规则下提交 ⇒ 旧配置不再相关，不在新配置里的服务器可以关停

任一步骤中 leader 崩溃：新 leader 可能在 C_old 下选出，也可能在 C_old,new 下选出，
但 C_new 在这期间无法单方面做决定；Leader Completeness 保证只有持有 C_old,new
条目的服务器能当选，所以「两个独立多数派」不会同时做决定。

实现与评估

Raft 的参考实现约 2000 行 C++（不含测试、注释、空行），跑在 RAMCloud 的配置信息复制与协调器故障切换上。
一个可理解性实验：43 名参与者（Stanford 与 U.C. Berkeley 的本科高年级与研究生），看 Raft 与 Paxos 的录播课并做对应测验；为抵消个体差异与学习效应，约一半人先看 Paxos、一半先看 Raft。结果 33 人的 Raft 得分高于 Paxos。

判据速查

问题	答案
一个任期能选出几个 leader	至多一个（多数派 + 一任期一票）
为什么需要任期号	起逻辑时钟作用，检测过时 leader 与过时请求
candidate 凭什么当选	拿到整个集群多数派对同一任期的票
日志怎么定"谁更新"	先比最后一条的任期，任期相同再比长度
为什么不能数副本提交旧任期的条目	旧条目在多数派上仍可能被未来的 leader 覆盖（见那张时序图）
AppendEntries 带前一条的下标与任期做什么	一致性检查 —— 它是 Log Matching 的归纳步
`nextIndex` 怎么用	新 leader 初始化为自己日志末尾 +1；被拒就减一重试，直到找到一致点
RPC 重试安全吗	安全 —— Raft 的 RPC 是幂等的
安全性依赖超时吗	不依赖。可用性才依赖，条件是 $broadcastTime ≪ electionTimeout ≪ MTBF$
配置变更为什么要两阶段	直接切换会让集群在过渡期分裂出两个独立多数派
joint consensus 的多数派怎么算	选举与提交都要同时满足旧配置与新配置的多数派
服务器什么时候用新配置	日志里出现该配置条目的那一刻，不等它提交

参考

D. Ongaro, J. Ousterhout. In Search of an Understandable Consensus Algorithm. USENIX Annual Technical Conference (ATC) 2014, pp. 305–319.
本篇依据正式版；客户端交互与日志压缩的快照方案在正式版里因篇幅省略，扩展版见下。
D. Ongaro. Consensus: Bridging Theory and Practice. PhD thesis, Stanford University, 2014.

贡献者

文件历史

最后编辑于大约 23 小时前查看完整历史

语法基础

gpu

cuda

train

infer

Raft

它承诺的五条性质

三种状态与任期

选举

日志复制

Log Matching 的两条与那条归纳

日志会怎么不一致

安全性

选举限制

提交规则：为什么不能数副本提交旧任期的条目

Leader Completeness 的九步反证

follower / candidate 崩溃

时序与可用性

成员变更：joint consensus

实现与评估

判据速查

相关

参考

贡献者

文件历史

Raft ​

它承诺的五条性质 ​

三种状态与任期 ​

选举 ​

日志复制 ​

Log Matching 的两条与那条归纳 ​

日志会怎么不一致 ​

安全性 ​

选举限制 ​

提交规则：为什么不能数副本提交旧任期的条目 ​

Leader Completeness 的九步反证 ​

follower / candidate 崩溃 ​

时序与可用性 ​

成员变更：joint consensus ​

实现与评估 ​

判据速查 ​

相关 ​

参考 ​

贡献者 ​

文件历史 ​

Raft

它承诺的五条性质

三种状态与任期

选举

日志复制

Log Matching 的两条与那条归纳

日志会怎么不一致

安全性

选举限制

提交规则：为什么不能数副本提交旧任期的条目

Leader Completeness 的九步反证

follower / candidate 崩溃

时序与可用性

成员变更：joint consensus

实现与评估

判据速查

相关

参考

贡献者

文件历史