4.1 共识的定义与 FLP 不可能性
共识(consensus)是分布式系统所有一致性的地基。etcd 选主是共识,日志复制顺序是共识,K8s 里多个 apiserver 对「某个对象当前是什么」的认同也是共识——只不过大多数时候由 etcd 代劳。在动手拆 Raft 之前,必须先回答两个更根本的问题:共识到底要求什么?它为什么这么难?
本节先给出共识的形式化定义(安全 + 活性),再讲分布式理论最著名的一堵墙——FLP 不可能性,然后用「协调者的两难」建立直觉,最后说明现实系统(包括 Raft/etcd)是怎么绕过它的。这节的结论会贯穿整个卷一:共识的安全性可以在异步模型下保证,活性只能在部分同步假设下、以概率方式争取。
共识问题的形式化:安全 + 活性
先定义问题。有 N 个进程,每个进程可以提出(propose)一个值;共识协议要求每个非故障进程最终决定(decide)一个值,且满足以下性质:
| 类别 | 性质 | 含义 |
|---|---|---|
| 安全 | 一致(Agreement) | 任何两个进程决定的值必须相同 |
| 安全 | 合法(Validity) | 被决定的值必须是某个进程提出的值(不能无中生有) |
| 安全 | 可学习(Learnability/Integrity) | 每个非故障进程最终都学得到这个决定,且只决定一次 |
| 活性 | 终止(Termination) | 每个非故障进程在有限时间内必须做出决定 |
注意「安全」与「活性」的哲学差别:安全性是「永远不能违反」——一旦违反,历史已不可挽回(两个副本各执一词);活性是「终将得到」——暂时没达成可以等,但不能永远等下去。分布式系统理论里大量不可能结果,本质都是「安全 + 活性同时要,在某些模型下做不到」。
形式化地写,共识要满足:
一致: ∀p,q 若 p 决定 v、q 决定 w,则 v = w
合法: ∀p 若 p 决定 v,则 v ∈ {某个进程提出的值}
终止: ∀非故障 p,p 最终决定
这套定义下,「共识」这个抽象可以实例化成无数具体问题:谁当 leader(值 = 节点 id)、日志第 i 条是什么(值 = 命令)、etcd 的成员变更(值 = 新成员列表)。Raft 解决的正是「在一个 log index 上就同一个值达成共识」,然后靠状态机复制把整条日志的一致性推到存储上。etcd 的键值对写入,最终也归结为「对第 i 条日志命令达成共识」这一件小事——大事全由这一件小事累加而来。
值得注意「合法」这条性质的范围:决定必须是某个进程提出过的值,而不是任何值。这排除了「大家都选预先固定的默认值」这类作弊解法,也意味着共识协议不能凭空发明值——这个约束在后面理解 etcd 的写入语义(客户端提议、Leader 广播、多数确认)时很关键。
把抽象落到实例,看三组共识问题的「值」分别是什么:
| 共识实例 | 参与进程 | 提议的值 | 决定的意义 |
|---|---|---|---|
| Raft 选举 | 集群节点 | 节点 id | 谁是唯一的 Leader |
| 日志复制 | 集群节点 | 一条客户端命令 | 第 i 条日志是什么 |
| etcd 成员变更 | 集群节点 | 新成员列表 | 集群配置变为什么 |
| K8s 对象写入 | 多数派 etcd | 对象的最新状态 | 对象当前是什么 |
同一个「达成唯一决定」的抽象,被这些实例复用了无数次——理解这一点,后面读 Raft 的每个阶段就能随时对应回「这是在解决哪一次共识」。
FLP 不可能性:异步模型下的一致与终止不可兼得
FLP 是三位作者姓氏的首字母:Fischer、Lynch、Paterson,1985 年发表在 JACM 上的论文《Impossibility of distributed consensus with one faulty process》。它说的是:
在异步(asynchronous)分布式系统里,只要允许哪怕一个进程可能崩溃,就不存在任何共识协议能同时保证「一致」与「终止」。
定理的三条模型假设必须记清楚,否则容易误解:
- 异步:消息延迟没有上界,进程执行速度没有上界(可能慢到「看起来死了」)。
- 故障模型:进程可能崩溃(fail-stop),崩溃后不再参与;崩溃是「可能发生」,不是「必然发生」。
- 网络:消息可能丢失、乱序,但通道是「最终可靠」的(重传总能送到)——FLP 甚至不需要假设永久丢消息。
在这个模型下,任何确定性协议(不用随机数、不靠真实时钟)都可能永远不终止。定理的证明是构造性的:任选一个协议,构造一个「无限拖延」的执行——每一步都让某些进程在「是否决定」之间摇摆,让任何决定都不被所有进程同时观察到,于是永远无法同时满足一致与终止。
FLP 的结论常被外行误读成「分布式共识不可能」,必须纠正:它说的是「在异步模型 + 确定性 + 可能故障下,无法保证终止」。它没说异步系统里共识从没成功过——只说不能保证。Raft 在真实世界天天成功,但那是概率上的成功,不是绝对保证。
顺着这个纠正再挖一层:FLP 甚至没削弱「安全」——在异步模型下设计一个「永远保持一致、只是可能不终止」的协议是可行的,Paxos 与 Raft 的安全性部分都走在这条路上。真正被 FLP 判死刑的,是「在不确定世界里做出确定决定且永不落空」这个组合。
直觉:协调者的「等 vs 决定」两难
FLP 的证明很难,但直觉可以用一个「协调者」故事概括。假设有一个中心协调者(coordinator)负责收集所有提议,再广播最终决定。协调者必须决定一个值并让所有人都知道。它的困境在于:
- 决定太快:如果它没等到所有响应就宣布结果,万一两个分区各自按不同子集做了决定,一致(Agreement)就被违反——这是安全错误,无法挽回。
- 决定太慢:如果它坚持等到「所有可能影响结果的响应」,那么任何一条消息丢失(或某个进程崩溃)都会让它永远等下去——这是活性错误,系统僵死。
问题在于:在一个没有时间上界的异步系统里,协调者从原理上无法区分「这个进程只是慢」与「这个进程已经死了」。慢和死,在观察者看来是同一种现象。于是「等待 vs 决定」成为不可解的两难:多等一会儿是安全的,但可能等到永远;快做决定是快的,但可能做错。
这还不是全部困难。即使协调者自己做出了决定,它还要把决定传给所有人;而任意一个学习者可能恰好在广播到达前崩溃,恢复后它必须能重新学到决定。FLP 的构造性证明正是把这种「总有一个进程还没学到」的状态一直延续下去。
用一个 3 进程的例子把「等 vs 决定」具体化。三个进程都提议值,协调者收到前两个进程的提议后面临选择:现在就决定「v1」,还是等第三个?若第三个永远不来(消息丢或进程死),等 = 活性违约;若现在决定,而第三个恰好已私下同意另一个值,一旦两个分区各宣布一个结果,一致被破坏。FLP 的证明把这种「无论怎么选都有无限执行」的结构推广到任意确定性协议——这正是它叫「不可能」而不是「很难」的原因。
安全与活性的不对称:为什么一个保得住、一个保不住
FLP 还有一个常被忽略的侧面:安全与活性在异步模型下待遇完全不同。
- 安全可以无条件保证。 任何「不能违反」的性质,都可以靠「宁可多等、绝不乱来」的策略保住——在不确定时选择不提交、不覆盖、不选主,最多是系统停滞,绝不会出现两个决定冲突。Raft 的 term、日志匹配、选举限制等机制就是这类「宁可保守」的规则。
- 活性无法无条件保证。 任何「终将发生」的性质都依赖时间假设:要么假设消息延迟有界(同步),要么假设延迟最终有界(部分同步),要么靠随机性打破对称——在纯异步 + 确定性的组合里,总存在一个「让你永远等下去」的执行。
这个不对称解释了为什么所有真实共识协议的安全论证都干净利落,活性论证却要么带概率、要么带「假设网络最终恢复」。读 Raft 源码时会反复遇到这种气质:安全相关逻辑极其严谨,活性相关逻辑全是超时、重试与随机数。
现实回应:从「不可能」到「高概率」
既然在纯异步模型下保证终止不可能,现实系统只能选择放松某个假设。三条主流路径:
| 路径 | 放松什么 | 代表 |
|---|---|---|
| 随机化 | 协议允许用随机数 | Ben-Or 随机共识、Raft 的随机选举超时 |
| 部分同步(partial synchrony) | 假设存在某个「全球稳定时刻 GST」之后消息延迟有界 | DLS 1988 的三种模型 |
| 故障转移/中心化 | 放弃多副本对等,引入权威 | 数据库单主、etcd 单写入路径 |
其中与 Raft 关系最直接的是 DLS 模型(Dwork、Lynch、Stockmeyer,1988)。DLS 按时间假设把系统分成三档,把 FLP 的结论精确化:
| 模型 | 时间假设 | 共识能否保证终止 |
|---|---|---|
| 同步(synchronous) | 消息延迟有已知上界 | 能 |
| 部分同步(partial synchrony) | 存在未知的 GST,此后延迟有界 | 能(何时终止取决于 GST) |
| 异步(asynchronous) | 延迟无上界 | 不能(FLP) |
DLS 的结论是:在部分同步模型下,共识的一致性与终止可以同时保证,只是「何时终止」取决于 GST。真实网络(有超时重传、有 TCP、有现实物理上限)几乎总满足这种假设——只要分区最终会愈合、迟到最终会送到。这给了工程界一条体面的出路:你不需要在「不可能」面前认输,只需要承认「GST 之前可能要等」。Raft 正是这条路径的工程化身:它不假设网络完美,只假设「网络终将恢复正常一段足够长的时间」,在这段窗口里完成选举与日志提交。
超时在这里不是「笨办法」,而是部分同步模型在工程上的最小实现:每个超时都在试探「GST 是否已过」。超时太短会频繁误判(把慢进程当死的,触发不必要的选举);超时太长会拖慢故障恢复(分区愈合后迟迟不选主)。Raft 把「超时」交给随机化,既避免全局同步的超时引发分裂投票,又把期望恢复时间控制在可接受范围——下一节与 5.1 节的选举协议会给出具体数字。
Raft 如何绕过:随机化活性
Raft 从两个方向绕开 FLP:
第一,活性靠随机化 + 重试。 Raft 的每个 Follower 持有一个随机的选举超时(lab 仿真里是 5–10 个 tick,真实 etcd 默认约 1 秒量级)。没有任何消息时,超时先到的节点发起选举。由于超时是随机且各节点独立,两个节点同时超时的概率被压得很低,一个节点大概率独自触发选举,凑齐多数票当选。即便发生分裂投票(两个 Candidate 各拿一半票),下一轮随机超时再次打破对称,最终以概率 1 收敛出唯一 Leader。这就是 FLP 所说「随机化可恢复活性」的实例。
第二,正确性靠部分同步假设。 Raft 的安全性(单一 Leader、日志不会回退)不依赖任何时间假设——它靠 term 与选举限制等规则保证,即使网络乱成一团也不违反。但终止(最终选出 Leader)依赖部分同步:只有当选举消息最终能在多数节点间送达时,选举才会完成。分区持续期间没有 Leader,正是系统诚实地承认「活性暂不可得」。
一句话总结 Raft 的立场:在部分同步窗口内,用随机超时 + 重试,以高概率快速选出唯一 Leader;安全永不妥协,活性概率保证。
K8s 场景:etcd 在不可靠网络上的选主
把 FLP 拉回 K8s。etcd 生产部署通常 3 或 5 个节点,跑在不可靠的物理网络、容器网络、甚至跨机房链路上。真实世界里发生过无数次:一次网络抖动丢了几秒心跳,Follower 超时发起选举,新 Leader 在多数节点间产生,旧 Leader 发现自己的 term 已过时、主动退位——集群毫秒级恢复。这套行为正是「部分同步 + 随机化」的日常演出。etcd 的默认参数也印证了设计:heartbeat 间隔约 100ms,选举超时是它的若干倍(约 1s 量级),超时远大于心跳,就是为了让「正常心跳压制选举」与「故障时快速触发选举」共存。
可以用 lab 仿真把「不可能」与「可能」的边界看得更清楚:
- 完全隔离时(FLP 场景):3 个节点彼此不可达,任何人凑不齐 2 票。Raft 不会假装选主,集群进入无 Leader 状态,写请求失败(etcd 返回 leader 丢失或超时错误)。这正是 FLP 的正确姿势——一致性保持,活性让位。
- 多数派存活时(日常场景):3 节点里 2 个互通,它们凑齐 2 票选出 Leader,第 3 个节点分区后靠 pre-vote 机制(5.3 节详述)不扰乱主集群,恢复后重新跟上日志。活性在部分同步窗口内恢复。
用法定票数把两种结果算清楚:3 节点集群的多数派是 2(n/2+1),5 节点集群是 3。一次分区后,只要存活的一侧人数 ≥ 多数派,那一侧就能选出 Leader 继续服务;两侧都不足多数派时(如 3 节点拆成 1+2 的孤点,或 5 节点拆成 2+2),谁都无法合法选主,集群进入只读的降级状态。这个「存活侧是否凑够多数派」的判断,是运维排障时最先要看的一步——它直接决定 etcd 是能继续服务还是只能等分区愈合。
把两种集群规模的分区场景摆开,多数派与容错数的关系一目了然:
| 集群规模 | 多数派 | 可容忍故障数 | 分区后仍可服务的一侧 |
|---|---|---|---|
| 3 | 2 | 1 | 存活侧 ≥ 2 |
| 5 | 3 | 2 | 存活侧 ≥ 3 |
这张表是 4.3 节多数派算术的前奏:etcd 扩到 5 节点不是为了性能,而是为了把「可容忍故障」从 1 提到 2。
etcd 在不可靠网络上仍能选主,靠的不是「更聪明的算法」,而是放弃无条件活性保证,换取大概率快速收敛:它不保证网络一直坏着时还能选主(谁也做不到),但它保证网络一旦好转,选举在有限且期望很小的时间内完成。K8s 控制面对 etcd 的可用性判断(lease 续约、健康检查的短超时)全部建立在这条交换之上。
本节 lab
TestFLPSingleFaultNoTermination(private/labs/k8s-etcd-lab/raft/)是 FLP 结论的直观演示。它构造一个 3 节点集群,分区函数把网络切碎:节点 0 完全隔离(单点故障 + 不可达),节点 1 与节点 2 也相互隔离——于是任何节点都只能与「自己」通信,谁也凑不齐 2 票的法定多数:
s.SetPartition(func(a, b int) bool {
if a == 0 || b == 0 { return true } // 节点 0 完全隔离
return (a == 1 && b == 2) || (a == 2 && b == 1) // 节点 1、2 相互隔离
})
for i := 0; i < 200; i++ { s.Step() } // 200 个 tick 后仍无 Leader
测试跑满 200 个 tick 并断言全程无 Leader——协议在完全隔离的异步网络里不终止,这正是 FLP 的工程侧写:一致性可以保持,终止无法保证。对照 5.1 节 TestElectionReachesAgreement:同样的仿真器、同样的 3~5 节点,网络一旦互通(部分同步),随机超时下集群以高概率快速选出 Leader。
两个用例放在一起读就是本节的完整结论:同一套选举协议,网络隔离时永不终止(FLP),网络部分同步时快速收敛(Raft)。区别不在协议,在时间假设——这正是 DLS「部分同步」模型的工程注脚。仿真细节也值得注意:每个 tick 只投递上一轮积压的消息,消息固定延迟 1 个 tick,所以这里的「隔离」是彻底的——被分区函数过滤掉的消息永远不会进入 inflight 队列,节点也永远不会收到任何响应,这正是异步模型「消息可能永远不到」的最强版本。
运行:
cd private/labs/k8s-etcd-lab
go test ./raft -run TestFLPSingleFaultNoTermination -v
这个用例与下一节的「多数派仲裁」一起,构成 Raft 在 FLP 阴影下取回的活性边界:FLP 告诉我们活性在异步模型里理论上不可保证,Raft 告诉我们把网络假设放松到部分同步、把活性交给随机化之后,工程上可以做得非常好。下一节进入 Paxos 简述与 Raft 的动机:为什么最终是 Raft 而不是 Paxos 成了 etcd 的选择。
继续阅读
探索更多技术文章
浏览归档,发现更多关于系统设计、工具链和工程实践的内容。