分布式一致性：Paxos推导过程

可视化演示

展示系统处理流水线、实时性能指标曲线及多方案对比分析，包含数据流转、吞吐延迟监控与方案评估。

问题根源

同一场年夜饭，大家消息不对称：张三收到了小张的通知，李四只看到老李的传单，王五干脆没信号。结果不是两桌同时开席，就是全村饿肚子。分布式系统面临的正是这个困局：每个节点对“当前该做什么”都有自己的局部视图，而系统整体又必须给大家一个统一答案。如果这个答案还能被随便推翻，那比没有答案更糟——刚把火锅店的定金付了，转头又被告知改去农家乐。

把村民换成服务器，把饭店换成需要一致提交的数据值（Value），把传话换成网络消息，问题就清晰了：一群节点在没有中央调度者、存在消息延迟和随机故障的环境里，必须就同一个值达成一致，并且一旦选定，这个值就不能被后续操作改写。这不是“尽量同步一下”的软需求，而是一条硬性安全规范，在 Paxos 里被称为一致性（Agreement）。

正式一点：Paxos 要保证的是，任意时刻都不可能有两个不同的值被系统确定为最终结果。这个目标可以写成一条不变量：

这个不变量就是整座大厦的地基。接下来要推导的每一个规则——角色、编号、两阶段——都在为守卫这一个公式服务。过年的一桌饭，看似简单，但放进“有人迟到、有人缺席”的世界里，就逼着我们发明一套精密的政治程序。

角色与多数派

年夜饭总不能全村几千人一起坐在谈判桌上。有人负责出主意，比如小张提出“去火锅店”；有人负责记录和表态，比如几个热心肠的村委会成员；大多数人只关心最后通知我去哪吃。于是 Paxos 把节点分成三个角色：Proposer（提案者，出主意的人）、Acceptor（接受者，负责记录和投票的人）、Learner（学习者，等待最终结果的人）。

这里有个关键的推导转折：如果要求“所有 Acceptor 都同意”才能定案，那么只要有一个 Acceptor 宕机，年夜饭就永远定不下来。所以 Paxos 把“全体一致”降级为“多数派一致”——只要超过半数的 Acceptor 点头，结果就是定局。这个“超过半数”的集合叫 Quorum（法定人数）。

为什么“多数”就够了？因为这带来一个漂亮的数学性质：任意两个多数派必然有至少一个公共成员。就像三户人家中任意两家一起吃饭，总有一户会同时认识两拨人。这个性质写下来是：

多数派交集就是 Paxos 安全的秘密武器。它保证：无论历史如何分岔，总有一个“知情人”站在两条路交汇处，能把上一轮的决议带给下一轮。年夜饭的秩序，就靠这个公共村民来维护。

编号与承诺规则

小张的方案是 5 号，老李的方案是 6 号。如果两人同时拉票，村民们可能上午答应小张、下午又答应老李，最后谁说了都不算。关键推导来了：要给每个提案一个全局全序的编号 \(n\)（编号越大代表越“新”），并且要求 Acceptor 做出一个刻骨铭心的承诺——一旦答应支持编号 \(n\) 的方案，就绝不再接受任何编号小于 \(n\) 的方案。

这个承诺在 Paxos 里叫 Promise（承诺）。为什么必须这样做？因为编号 5 和 6 之间可能存在竞争窗口：老李的 6 号提案正在路上，如果 Acceptor 还接受小张的 5 号，两个不同的值就可能都被多数派接受，安全地基瞬间崩塌。承诺的本质是“选边站”，用编号的序关系强行消除并发窗口。

还有一个更深的推导：Acceptor 光记住“我承诺过 6 号”还不够，还必须记住“我是否已经在某个编号上接受了某个值”。否则当未来某位 Proposer 来摸底时，这位 Acceptor 无法把自己见证过的历史告诉对方。承诺规则的形式化表达为：

有了编号和承诺，村里就不会有人两面讨好。但承诺只是“防守”，真正要确定一个值，还需要主动出击的流程——这就是下一节的两阶段推导。

两阶段流程推导

既然决定了要投票，又不能乱投，自然导出了两阶段流程。第一阶段叫 Prepare（准备），可以理解为“摸底”：小张拿着 5 号方案挨家挨户问“你们最多支持到几号？如果已经有人定过老地点，告诉我”。每个 Acceptor 的回答是 Promise：好的，5 号以内我不再答应别人；顺便告诉你，我曾经接受过 3 号方案的“农家乐”。

第二阶段叫 Accept（接受），是“正式定案”：小张收集到多数派的承诺后，如果摸底中发现有人报告了已接受的值，就必须采用其中编号最高的那个值；如果没有人报告过任何旧值，他才能提自己的“火锅店”。然后把这个最终值连同 5 号编号发给 Acceptor，让它们记录并确认。

为什么必须“沿用旧值”？这是整个推导中最精妙的一步。因为那个旧值很可能已经在一个较早的轮次里被某个多数派接受了，只是小张当时不知道。如果他不沿用旧值而是坚持自己的值，两个值都可能形成多数派，违反 Agreement。值选取规则写成分段函数：

两阶段流程就此闭环：先摸底收集承诺，再带着旧值或新值正式投票。村民小张发现：只要有人记录过“农家乐”，他就必须改口提议农家乐，哪怕他更爱吃火锅。这不是妥协，而是数学上的必然——那桌旧饭可能已经订好，他不能掀桌。

正确性证明

现在到了最激动人心的一步：证明这套规则真的不会出现“两桌同时开席”。回顾多数派交集定理：任意两个多数派必然共享至少一个 Acceptor。这个共同村民就是证明的钥匙。

先定义“选定”。一个值 \(v\) 被选定（Chosen），意味着存在一个多数派集合 \(Q\)，其中每个 Acceptor 都已经接受过 \((n, v)\)。形式化定义：

接下来用反证法证明安全性不变量。假设第一轮在编号 \(n_1\) 选定了值 \(v_1\)，而后来第二轮编号 \(n_2 > n_1\) 却接受了不同的值 \(w \neq v_1\)。由于第二轮也凑到了多数派，它与第一轮构成多数派必有公共 Acceptor \(a\)。在第二轮 Prepare 时，\(a\) 必须如实告诉新 Proposer：“我曾在 \(n_1\) 号方案中接受了 \(v_1\)。”于是按上一节的取值规则，新 Proposer 只能提出 \(v_1\)，不可能提出 \(w\)，矛盾！

这个反证可以归纳到任意编号更大的后续轮次，因此得到核心不变量：

这个证明的本质是：多数派交集传播记忆。公共村民把过去的决议带向未来，任何试图颠覆历史的提案都会被承诺和取值规则挡回去。年夜饭一旦定了火锅店，后续再多人来拉票，最终结果也只会是火锅店。

算法特性

最后，我们来审视这套协议能撑起多大的风雨。年夜饭的组织者问：最多能容忍几个人失联还能把饭定下来？答案是“小于一半”。假设共有 \(N\) 个 Acceptor，多数派至少需要 \(\lfloor N/2 \rfloor + 1\) 个节点，因此最多可以容忍 \(\lfloor (N-1)/2 \rfloor\) 个节点同时失效：

Paxos 还有一个反直觉的优雅之处：它没有固定的主节点。任何节点都可以在任意时刻扮演 Proposer 发起一轮提案，只要编号够新、能凑齐多数派。这种去中心化让系统在领导人选举上也天然容错。但也因此带来工程上的复杂性：多轮竞争可能活锁（大家互相打断，谁也定不下来）。于是工程界演化出 Multi-Paxos 和 Raft 等变体：前者用长期 Leader 稳定提案通道，后者把“选主+日志复制”整体重构成更易理解的协议。Raft 不是 Paxos 的对立面，而是 Paxos 思想最著名的工程化特化。

年夜饭的故事到此收尾：过半村民在线，饭局就能定；新人提出新编号，也必须沿着旧记忆走；没有村长，谁都能当牵头人。这套由数学逼出来的协议，至今仍是谷歌 Spanner、etcd、ZooKeeper 等系统的心脏——只因为现实中每一场“年夜饭”，都输不起。

AI 应用场景

Python 演示

class Acceptor:    def __init__(self, name):        self.name = name        self.promised_id = -1        self.accepted_id = -1        self.accepted_value = None     def recv_prepare(self, n):        if n > self.promised_id:            self.promised_id = n            return True, self.accepted_id, self.accepted_value, self.name        return False, -1, None, self.name     def recv_accept(self, n, v):        if n >= self.promised_id:            self.promised_id = n            self.accepted_id = n            self.accepted_value = v            return True        return False  class Proposer:    def __init__(self, name, acceptors):        self.name = name        self.acceptors = acceptors     def propose(self, n, v):        promises = []        for a in self.acceptors:            ok, max_aid, max_val, aname = a.recv_prepare(n)            if ok:                promises.append((max_aid, max_val, aname))        quorum = len(self.acceptors) // 2 + 1        if len(promises) < quorum:            print(self.name + ": prepare 未获多数派")            return False        promises.sort(reverse=True)        if promises[0][0] != -1:            v = promises[0][1]        count = 0        for a in self.acceptors:            if a.recv_accept(n, v):                count += 1        if count >= quorum:            print(self.name + ": 选定值为 " + str(v))            return True        print(self.name + ": accept 未获多数派")        return False  if __name__ == "__main__":    acceptors = [Acceptor("A1"), Acceptor("A2"), Acceptor("A3")]    p1 = Proposer("P1", acceptors)    p2 = Proposer("P2", acceptors)    p1.propose(1, "火锅店")    p2.propose(2, "农家乐")

1. class Acceptor:每个 Acceptor 保存最大承诺编号和已接受的值，对应村民的记忆。
2. self.promised_id = -1初始承诺编号为 -1，表示还没有承诺过任何提案。
3. def recv_prepare(self, n):处理 Prepare 请求，只有编号更大才回复 Promise，并捎带自己记住的旧值。
4. (True, self.accepted_id, self.accepted_value, self.name)返回四元组，包括承诺结果、已知最高编号的旧值、值本身和节点名。
5. if n >= self.promised_id:Accept 阶段的条件：只有编号不小于已承诺编号才接受，防止旧方案插队。
6. promises.sort(reverse=True)按编号降序排序，最高编号的已接受值排在最前面。
7. if promises[0][0] != -1:如果响应里有旧值，就把本轮提案值改成旧值，体现“沿用旧值”规则。
8. quorum = len(self.acceptors) // 2 + 1计算多数派大小，3 个节点时是 2。
9. p2.propose(2, "农家乐")高编号提案发起时，会因为看到火锅店而放弃自己的农家乐提议。

常见误区

面试题