Skip to content
Charles Shao
Go back

分布式共识(开篇)· Paxos 与 Raft 图解

views

一旦系统里有了多个副本,一个绕不开的问题就摆在面前:这几台机器,怎么就同一件事达成一致? 谁是主、日志写到第几条、这条命令到底提交了没有——只要涉及”多个节点要看到同一个真相”,你就撞上了分布式系统里最硬的一块骨头:共识(consensus)。它是 高可用 里主从选举、Redis 哨兵/集群故障转移Kafka 副本可靠性 这些机制底下共同的地基。

这篇作为分布式共识系列的开篇,不堆公式、不背协议条文,而是把为什么需要共识、共识到底难在哪、Paxos 与 Raft 各用什么招这几件事从原理到机制讲透,再落到工程里怎么选型、怎么踩坑。

本文是分布式共识系列的第 1 篇(开篇 · 图解)。 全系列 5 篇,循序渐进:

  1. 分布式共识(开篇)· Paxos 与 Raft 图解(本篇)
  2. ZooKeeper 与 etcd 深挖 · ZAB、Raft、Watch 与租约
  3. 分布式锁深挖 · Redis Redlock vs ZooKeeper/etcd
  4. 分布式事务深挖 · 2PC、TCC、Saga 与 Outbox
  5. 分布式 ID 深挖 · 雪花算法及其变体

一句话定位:共识就是让一组会宕机、会丢包、会延迟的节点,对”一系列操作的顺序”达成多数派认可的、不可推翻的一致意见——它是把”多副本”从”各说各话”变成”同一个状态机”的那把锁。

TL;DR

Table of contents

Open Table of contents

1. 为什么需要共识:复制状态机与多副本一致

单机服务最省心:所有状态在一个进程里,天然一致。可单机一挂就全挂,扛不住流量也扩不了。于是我们把服务做成多副本——但副本一多,“一致”立刻变成难题:10 台机器各自维护一份状态,凭什么保证它们看到的是同一个真相?

1.1 复制状态机:把”多副本一致”归约成”日志一致”

工业界的标准答案是复制状态机(Replicated State Machine, RSM)。它的洞察极其简单却深刻:

如果每个副本都是一个确定性状态机(相同输入 → 相同输出),那么只要让所有副本按同一顺序执行同一串命令,它们的最终状态就必然一致。

于是”多副本一致”这个模糊的目标,被精确地归约成一个更具体的问题:让所有副本拥有一份完全相同、顺序一致的操作日志(log)。状态机只要顺序回放这份日志,一致性就自动成立。

复制状态机与多数派提交示意图。顶部一条横向流水线展示一条命令从产生到应用的五个阶段:客户端发出有序请求(命令 x←3、y←7)→ Leader 把命令追加到本地日志并分配 index 与 term → 通过 AppendEntries 并行复制到各个 follower → 收集到多数派(⌈N/2⌉+1)的确认后把该条目标记为已提交 commit → 顺序应用到状态机执行。底部画三个副本节点并排(Follower 1、居中的 Leader、Follower 2),每个节点都持有完全相同、顺序一致的日志条目序列 [1:x←3][2:y←7][3:x←5],并各自把日志顺序回放到本地状态机得到完全相同的键值状态 x=5、y=7。Leader 用 AppendEntries 箭头把日志分别复制给两个 follower。底部说明:只要一条日志被复制到多数派节点(含 leader 自身,3 个里达到 2 个),它就永远不会丢失、也不会被推翻,因此可以安全提交;共识算法的全部工作,就是为这份日志中的每个槽位,让多数派对"这一格放哪条命令"达成不可推翻的一致。

复制状态机:把”多副本状态一致”归约成”多副本日志一致”,共识算法负责给日志的每个槽位定序、并让多数派认账;状态机顺序回放即得到相同结果。

所以本文后面讲的 Paxos、Raft,本质都在解同一个问题:怎么让一组不可靠的节点,对”日志第 i 格放哪条命令”达成一致,且这个一致一旦达成就不可推翻。

1.2 CAP 背景:共识站在 CP 这一边

绕不开 CAP:分区(P)不可避免时,你只能在一致性(C)和可用性(A)里二选一。共识算法明确站在 CP 一侧——网络分区时,它宁可让少数派侧停止服务(不可用),也绝不允许两侧各写各的(破坏一致性)。这也是后面 §7 脑裂的核心:共识的”安全”是用少数派侧的”可用性”换来的。

理解了这层归约,就能明白为什么共识是分布式系统的地基——几乎所有”需要一个权威真相”的场景(选主、配置下发、分布式锁、元数据管理)底下都是它

2. 问题定义、FLP 不可能与 quorum 多数派

2.1 共识问题的形式化

抛开状态机的包装,共识问题本身可以精确定义为:一组进程各自提议一个值,最终要**决定(decide)**出一个值,并满足三条性质:

前两条是安全性(safety)——“不做坏事,绝不出错值”;第三条是活性(liveness)——“最终会做好事,不会永远拖着”。共识之难,就在于要同时扛住这两类保证,而故障与异步网络专门跟它们作对。

2.2 FLP 不可能:为什么共识没有”完美解”

1985 年 Fischer、Lynch、Paterson 证明了分布式领域最著名的负面结论——FLP 不可能

在完全异步的网络模型下(消息延迟无上界、无法区分”节点崩了”还是”消息还在路上”),只要允许哪怕一个进程崩溃,就不存在一个确定性算法,能同时保证共识的安全性与终止性。

直觉是:异步系统里你永远无法确定一个没回消息的节点是死了还是只是慢。如果你为了”活性”设个超时就往下走,可能误判导致不一致;如果你为了”安全”死等它回消息,就可能永远等下去(活性没了)。

FLP 不是说”共识不可能实现”,而是说没有确定性算法能在纯异步模型下保证必然终止。工程上的破解办法就两招:

所以你会看到:真实的共识算法都是”几乎总能终止”,而不是”数学上保证必然终止”——这正是对 FLP 的妥协。记住这点,就不会对”为什么要设一堆超时参数”感到困惑了。

2.3 quorum:多数派相交是共识的机械核心

共识算法里反复出现的 ⌈N/2⌉+1(多数派 / quorum),背后是一个极其朴素却致命重要的性质:

任意两个多数派集合,必然至少有一个共同成员(交集非空)。

比如 5 个节点,任何两个”3 节点集合”至少共享 1 个节点——因为 3+3=6 > 5,鸽笼原理保证重叠。这个”必然相交”是共识安全性的机械基础

这就是为什么共识能容忍少数节点失联还不出错:只要多数派还活着且能互通,历史就不会丢、也不会分叉。而分区时被隔到少数派一侧的节点,永远凑不齐多数派,只能停下来——安全就是这么来的。quorum 也解释了 §7 为什么用奇数节点。

3. Paxos:正确但难懂的鼻祖

Paxos 是 Leslie Lamport 提出的第一个被严格证明正确的共识算法,也是后来一切共识算法的思想源头。它的名声一半来自”正确”,一半来自”难懂”——连 Lamport 自己都写了篇《Paxos Made Simple》来补救。

3.1 Basic Paxos:三角色 + 两阶段

Basic Paxos 只解决一个最小问题:让一组节点对”单个值”达成一致。三种角色(一个进程可同时扮演多个):

核心是两阶段 + 全局递增的提案编号 n(编号全局唯一且单调,通常由 轮次号 + 节点ID 拼成):

Phase 1 — Prepare(占坑 + 打探)

Phase 2 — Accept(提交值)

3.2 为什么 Paxos 难懂

Paxos 的正确性关键在 Phase 2 那句”proposer 必须沿用已被接受的最高编号的值”——正是它保证了”一旦有值被选定,后续任何提案都只会提同一个值”(因为新 proposer 的 prepare 一定会撞见那个多数派里见过旧值的 acceptor,被迫沿用)。这个论证优雅,但也是它反直觉的根源:

3.3 Multi-Paxos:从”一个值”到”一串值”

要用 Paxos 复制日志,就得为**日志的每一个槽位(slot)**跑一遍 Paxos。朴素做法是每条命令两阶段,太慢。Multi-Paxos 的优化是:

这基本就是”强 leader + 日志复制”的雏形。但 Multi-Paxos 的论文描述极其含糊,成员变更、日志压缩、快照、冲突恢复这些工程必需的细节全靠实现者自己填坑——这正是 Raft 要解决的痛点:Paxos 正确,但太难对着它写出一个正确的系统。

一句话对比:Paxos 是一套正确的”共识原语”,Raft 是一份可以照着实现的”共识工程蓝图”。 下面三节就是 Raft 的三大块。

4. Raft(一):Leader 选举

Raft 的设计目标写在标题里——可理解性(understandability)。它做的第一件事是强 leader 化:任何时刻集群最多一个 leader,所有客户端写都走 leader,日志只从 leader 流向 follower(单向)。这一刀就砍掉了 Paxos 里最绕的”谁都能提案、值互相覆盖”的复杂度。

4.1 三种角色与 term

每个节点在任意时刻处于三种状态之一:

贯穿始终的是 term(任期)——一个单调递增的逻辑时钟。每次选举开启一个新 term,term 内最多一个 leader。term 是 Raft 里的”版本号 / 逻辑钟”:每条消息都带 term,节点一旦发现比自己更大的 term,立刻更新自己的 term 并转为 follower。这条铁律是防止”旧 leader 复活捣乱”的关键(旧主的 term 小,一发言就被”你 out 了”打回 follower)。

Raft 选举状态机图。三个状态节点横向排列:左侧 Follower(跟随者)、中间 Candidate(候选人)、右侧 Leader(领导者)。状态间的转换箭头:Follower 到 Candidate 的箭头标注"选举超时(随机 150–300ms 未收到心跳):term+1、给自己投一票、广播 RequestVote";Candidate 到 Leader 的箭头标注"赢得多数派选票(⌈N/2⌉+1)当选";Candidate 顶部自环标注"选票被瓜分 split vote → 选举再次超时,term+1 开启新一轮选举";Follower 顶部自环标注"收到 leader 心跳 AppendEntries → 重置选举计时器,保持 follower";Leader 顶部自环标注"周期性发送心跳 AppendEntries 维持权威、压制新选举";Candidate 经底部回到 Follower 的箭头标注"收到合法 leader(term≥自己)的心跳 / 发现更高 term → 退回 follower";Leader 经底部回到 Follower 的箭头标注"发现更高 term(出现新 leader 或更高任期)→ 立即退位为 follower"。底部说明:term 是单调递增的逻辑时钟,每条 RPC 都带 term,任何节点看到更大的 term 都立即更新并转 follower;随机化的选举超时是打破对称、避免选票反复瓜分的关键设计。

Raft 选举状态机:follower 超时未收到心跳 → 变 candidate、term+1、拉票 → 拿到多数派选票即当选 leader;随机化超时打破对称避免 split vote,更大的 term 永远压倒一切。

4.2 选举流程:随机超时打破对称

选举的触发与推进:

  1. 触发:follower 在一个**选举超时(election timeout)**内没收到 leader 心跳,就认为 leader 挂了,转为 candidate。
  2. 拉票:candidate 把自己的 term += 1先给自己投一票,然后向所有节点广播 RequestVote(term, candidateId, lastLogIndex, lastLogTerm)
  3. 投票规则:每个节点在一个 term 内只能投一票(先到先得),且只投给”日志不比自己旧”的 candidate(见 §6 选举限制)。
  4. 当选:candidate 收到多数派选票即成为 leader,立刻广播心跳压制其他潜在 candidate。

关键设计是随机化选举超时:如果所有 follower 用同一个固定超时,它们会同时变 candidate、同时拉票,选票被均匀瓜分(split vote),谁都拿不到多数派,然后又同时超时……陷入活锁。Raft 让每个节点从一个区间(如 150–300ms)里随机取超时值——总有一个节点先超时、先拉票、先拿多数派,其他节点还没醒就收到新 leader 的心跳,选举一轮收敛。这正是 §2.2 说的”用随机化绕过 FLP 活锁”的具体落地。

4.3 心跳与任期切换

leader 通过周期性发送空的 AppendEntries(心跳)来维持权威、重置所有 follower 的选举计时器。一旦网络分区或 leader 宕机,某一侧的 follower 收不到心跳就会重新触发选举。而当旧 leader 从分区中恢复、发现集群已经有了更高的 term,它会立刻退位成 follower——简化版选主若漏掉这一步,就会留下双主隐患。

5. Raft(二):日志复制

选出 leader 后,真正的工作是把客户端命令可靠地复制成一致的日志

5.1 日志结构与 AppendEntries

Raft 的日志是一串条目(entry),每个条目记录:{term, index, command}index 是全局位置,term 是该条目被创建时 leader 的任期——(term, index) 唯一确定一条日志,也是一致性检查的依据。

leader 收到客户端命令后:

  1. 把命令作为新条目追加到自己的日志(此时未提交 uncommitted);
  2. 通过 AppendEntries(term, prevLogIndex, prevLogTerm, entries[], leaderCommit) 并行发给所有 follower;
  3. follower 做一致性检查:只有当自己在 prevLogIndex 处的条目 term 等于 prevLogTerm 时,才接受新条目(保证日志前缀完全一致);否则拒绝,leader 回退 nextIndex 重试直到对齐。

Raft 日志复制时序图。四个参与者纵向泳道:客户端 Client、Leader、Follower A、Follower B。时序步骤:1. 客户端向 Leader 发送写请求 set x=3;2. Leader 自身动作:把命令追加为日志条目 (term=2, index=5, x←3),状态为未提交 uncommitted;3. Leader 向 Follower A 发送 AppendEntries(term=2, prevLogIndex=4, prevLogTerm=2, entries=[x←3], leaderCommit=4);4. Leader 同时向 Follower B 发送同样的 AppendEntries;5. Follower A 一致性检查通过(prevLogIndex 处 term 匹配),追加条目并回复成功 ACK,Leader 据此更新 matchIndex[A]=5;6. 注释:Leader 自身 + Follower A 已达多数派(3 个节点里的 2 个)持有该条目;7. Leader 自身动作:推进 commitIndex=5,把条目应用到状态机执行 x=3;8. Leader 向客户端返回写入成功;9. Leader 在下一次 AppendEntries 中携带 leaderCommit=5,通知 Follower A(及随后的 B)该条目已提交,follower 也据此提交并应用到各自状态机;注释:matchIndex 记录每个 follower 已复制到的最高日志位置、nextIndex 记录下一个要发送的位置;只有当前 term 的日志被复制到多数派才能直接提交(选举安全性约束)。

日志复制:leader 追加条目 → 并行 AppendEntries → 多数派 ACK 后推进 commitIndex 并应用状态机 → 通过后续心跳的 leaderCommit 通知 follower 提交;matchIndex/nextIndex 跟踪每个 follower 的进度。

5.2 commitIndex:多数派才算提交

这是 Raft 最关键的一步,也是共识安全性的落点:

一条日志条目,只有当 leader 确认它已被复制到多数派节点时,才被标记为”已提交(committed)“,然后才能应用到状态机、才能对客户端返回成功。

leader 用两个数组跟踪进度:

leader 找到”存在于多数派上的最大 index”(即多数派的 matchIndex 都 ≥ 它),把 commitIndex 推进到那里,随后应用到状态机并回复客户端。follower 并不立刻知道自己刚追加的条目提交了——它们通过后续 AppendEntries 里携带的 leaderCommit 得知”到某某 index 都提交了”,再各自推进并应用。这解释了图里第 9 步:提交状态是搭下一趟心跳的顺风车扩散出去的。

5.3 一致性回退:日志怎么被强制对齐

当 follower 因为宕机/分区落后或有冲突条目时,leader 的 AppendEntries 一致性检查会失败。Raft 的修复策略是简单粗暴的**“以 leader 为准”:leader 递减该 follower 的 nextIndex 重试,直到找到双方日志一致的分叉点,然后用自己的日志覆盖 follower 从分叉点之后的所有冲突条目**。因为只有已提交的日志才会被应用,而已提交的日志一定在多数派上、绝不会被覆盖(见 §6),所以这种覆盖是安全的——被覆盖的一定是未提交的脏条目。

6. Raft(三):安全性

选举 + 复制还不够,必须再加两条安全性约束,否则会出现”已提交的日志被覆盖”这种灾难。这也是 Raft 论文里最需要细品的部分。

6.1 选举限制:日志不够新的不能当选

设想:一个日志落后的节点当选了 leader,然后用它残缺的日志去覆盖别人——已提交的数据就丢了。Raft 用选举限制堵死这条路:

candidate 的 RequestVote 里带上自己最后一条日志的 (lastLogTerm, lastLogIndex);投票者只有在”candidate 的日志至少和自己一样新”时才投票。“更新”的定义:先比 lastLogTerm,term 大的更新;term 相同则 index 大的更新。

因为当选要拿多数派选票,而任何已提交的条目都在多数派上——两个多数派必相交(§2.3)——所以能当选的 leader,其日志必然包含所有已提交的条目。这就保证了新 leader 不会”倒退”,永远不会覆盖已提交的历史。

6.2 只提交当前 term 的日志

这是 Raft 里最反直觉、也最容易被自研实现漏掉的一条。直觉上,一条日志只要”复制到了多数派”就该能提交。但 Raft 论文用一个经典反例证明:leader 不能仅凭”某条旧 term 的日志已复制到多数派”就提交它——因为这条旧日志可能在后续被另一个 leader 的更高 term 日志覆盖掉,导致”提交后又被推翻”。

Raft 的解法:

leader 只能通过”提交自己当前 term 的日志”来间接提交之前 term 的日志。 即:只有当前 term 产生的某条日志达成多数派提交后,它之前的所有日志才随之被安全提交(Log Matching + 提交传递)。

实践中新 leader 上任常会追加一条空的 no-op 条目并尽快提交它,以此”带出”并确认之前 term 的所有待定日志。这条规则和 §6.1 的选举限制配合,共同构成了 Raft 的 State Machine Safety:一旦某条日志在某 index 被应用到状态机,任何节点在同一 index 都不会应用一条不同的日志。

这两条安全性约束,正是”自己撸一个共识”最容易翻车的地方——§10 的生产事故本质就是”简化版选主”既没做选举限制、也没做 term 校验。

7. 脑裂与 quorum:为什么用奇数节点

7.1 共识天然防脑裂

脑裂(split-brain)指网络分区导致集群裂成两半、两边各自选主、各自写入,最终数据分叉。共识算法对此有天然免疫,机制就是 §2.3 的多数派:

所以正确实现的共识不会脑裂双主——最多是少数派侧短暂不可用。这也正反衬出 §10 那个自研组件的问题:它没有真正的多数派约束,两侧才会各自称王。

7.2 为什么是奇数节点

容错能力由 f = ⌊(N-1)/2⌋ 决定(能容忍 f 个节点故障还保持可用):

节点数 N多数派 quorum可容忍故障 f
321
431
532
642

看这张表就懂了:从 3 加到 4、从 5 加到 6,容错能力没涨,却多花一台机器、还多一个可能故障的点。偶数节点是”花钱不办事”。更糟的是偶数节点在 N/2 : N/2 均等分区时两侧都拿不到多数派,谁都不能写、集群整体不可用(而奇数节点分区必然一侧是多数派、能继续服务)。所以共识集群一律用奇数节点(3、5、7),在给定成本下把容错能力和抗分裂性都拉满。

8. 共识在工程里的落地

好消息是:你几乎永远不需要自己实现共识。成熟的共识系统和库已经把 Paxos/Raft 的所有魔鬼细节(成员变更、快照、日志压缩、网络重传)踩平了。

选型经验:要强一致的元数据/配置/选主/锁 → etcd 或 ZooKeeper;已经在用 Kafka 且是新集群 → 直接上 KRaft;自己写业务时绝不要手撸共识,把它下沉给这些组件。

9. 共识 vs 最终一致

共识给的是强一致,但强一致不是免费的。要清楚它和最终一致的边界,才不会用错地方:

维度共识(Raft/Paxos,强一致/CP)最终一致(Dynamo 风格,AP)
一致性线性一致:写完立即可读到、有全局唯一顺序最终一致:短时间可能读到旧值,最终收敛
写路径每次写要跨多数派确认,延迟更高写本地/少数副本即返回,延迟低
分区行为少数派侧不可写(牺牲可用性保一致)两侧都可写,事后靠版本向量/LWW 合并冲突
典型场景元数据、选主、锁、配置、账务购物车、点赞数、会话、缓存
代表etcd / ZooKeeper / SpannerCassandra / DynamoDB / Riak

一句话:共识把”顺序和唯一真相”做成了硬保证,代价是延迟和分区可用性;最终一致反过来,用”可能读到旧值”换低延迟和高可用。系统设计里常常两者并用——用共识管一小撮关键元数据,用最终一致扛海量数据面。更细的一致性模型、幂等与去重,见 幂等与一致性

参考


views
Share this post on:

Previous Post
Criteo CTR 特征工程实战:把理论串成一条能跑的广告管线
Next Post
广告多维报表与漏斗分析实战