Multi-Paxos共识协议原理

可视化演示

展示Multi-Paxos共识协议核心机制：三阶段共识流程（Prepare→Accept→Commit）中Leader与Follower的消息交互，以及日志复制模式下条目提交进度与多数派确认。

Basic痛点：会议室里人人抢话筒

回到小组协作的场景。Basic Paxos 相当于一个“没有主编”的规则：任何人要改文档，都得先喊一声“我要改这里”（Prepare），等超过一半同学回一句“行，不改了”（Promise），他才能正式把修改写上去（Accept）。这套规则能保证单次的修改不会冲突，但它有三个很别扭的地方。

第一，每一次修改都要完整跑一遍“举手→表决→落笔”，不能偷懒。你改个错别字要两轮消息，改个标题也要两轮消息，无论改动多小，消息量都一样大。第二，如果两个人同时举手，你举 1 号牌，我举 2 号牌，你的 Prepare 会被我的盖过去，然后你举 3 号牌反超我……两个人就这么互相抬编号，谁也写不成一个字，这就是著名的“活锁”。第三，Basic Paxos 的设计焦点是“单个值”，而不是“一串值”。真实系统里要写入成千上万个值，每个值都重新投票，代价高到无法接受。

在分布式系统术语里，这种“多台机器凑成多数”的概念叫 Quorum。三个节点的集群，至少两个节点确认才有效；五个节点，至少三个节点确认。这个“过半”条件是一切共识协议安全的基石。

所以 Basic Paxos 就像班里人人抢话筒，规则本身没错，可每个人都举着越来越大的编号牌，会场上除了“我要改”“我不同意”之外，什么都没有发生。真正要把系统跑起来，必须改变思路：先安定下来，选一个主编。

核心优化：选出一位主编，一次准备终身受用

同学们最终发现，与其每次修改都重新争取多数，不如先花一轮功夫选出一位“主编”，让他在任期内负责所有的修改。这个朴素的改进，正是 Multi-Paxos 的灵魂。

Multi-Paxos 的优化思路可以概括为两点。第一，集群先通过一轮 Prepare/Accept 选出一个稳定领袖（Leader）。选出之后，除非 Leader 崩溃或网络分区，否则大家不再轻易换人。第二，Leader 在任期内提交第一个值时才需要 Prepare，后续提交值直接进入 Accept 阶段。因为在选主那一轮，接受者已经把承诺给了这位 Leader，只要它的编号不降，就不必重复询问“我要改这里”。

假设系统要提交 m 条日志条目，Basic Paxos 每一条都要经历 Prepare 和 Accept 两个阶段，而 Multi-Paxos 只需要在任期开始时做一次 Prepare，之后 m 条全是 Accept。消息量立刻从“2m 轮”降为“m 轮加一”，性能差距随 m 增大越来越明显。

主编一旦确定，剩下的就是流水线作业：他把修改一条条编号，大家按顺序确认。会议室从“菜市场”变成了“编辑部”，效率自然天差地别。

选主机制：编号牌决定话语权

主编可不是终身制。万一主编请假、宕机，或者网络把主编和其他人隔开了，就需要重新选一个人来主持。问题来了：谁来当新主编？怎么判断一个候选人的资格？

Multi-Paxos 的选主机制像发编号牌。每个候选人手里都有一个单调递增的编号（Ballot Number / 任期号），想要竞选时，他带上自己的编号向其他节点广播 Prepare：“我要当主编，我的编号是 5。” 各节点只认编号更 大 的候选人：如果它们之前已经答应过编号 4，那么编号 5 会得到许可；如果它们已经答应过编号 6，编号 5 就会被拒绝。一旦多数节点承诺只接受编号 5，这个候选人就成了新 Leader。

编号牌机制还附带一个安全效果：陈旧消息自动失效。当选主完成、新主编上任后，旧主编的“落笔”请求因为编号较小，会被所有节点视为过期文件直接丢弃，绝不会覆盖新主编已经推进的内容。

选主就像一场“号牌拍卖会”，最新最大的号牌获胜，旧号牌的记录一律作废。这样一来，无论主编换多少任，同一个时刻都只有一个“最高编号”说了算。

日志复制：主编把稿件按顺序编号分发

新主编走马上任后，他要把所有修改整理成一条条“日志条目”。日志条目是分布式系统里的核心载体，每一条都包含三个信息：它排在第几号（索引）、它属于哪个任期（编号）、它的内容是什么（值）。主编在自己的日志末尾追加新条目，然后把条目复制给所有节点。

日志复制的关键在“按序”。主编只会往日志尾部追加，索引严格递增，不会跳过、不会原地修改。每个副本收到条目后，也把它追加到自己的本地日志尾部。如果某个副本反应慢，或者网络分区，主编会不断重试；日志缺口较大的副本，则通过追赶机制补齐。

假设主编的日志目前最长索引是 i，那么下一条新条目的索引就是 i+1。这里的“索引”就是团队里修改记录的流水号，编号 7 永远在编号 6 之后，不会插队。

主编不用等所有同学回复。他只要把稿件按编号发出去，大家收到后各存一份，多收集几张“收到”的回执，就足以确定这条修改能否转正。

推进规则：多数人点头才算定稿

日志复制只是把条目送到了各副本手里，真正重要的是“定稿”——也就是提交（Commit）。一条日志条目被提交的含义是：这条修改已经被整个集群认可，可以永久生效，并且任何新主编都不能推翻它。

提交的判定条件非常简单：一个条目只要被超过半数的节点写入并确认，就算提交。为什么“多数”就够了？因为任意两个多数派必然有交集。旧主编提交过的条目一定出现在某个多数派里，新主编无论如何都绕不开这个多数派，所以它要么保留该条目，要么能从中恢复出它的内容。

当某条日志达成多数确认后，Leader 把自己的“提交指针”（commit index）前移到该位置，并把提交信息广播给所有副本。各副本收到提交通知后，把日志中已提交的部分逐条“回放”到状态机——也就是真正执行 set key=1、转账 100 元 这类命令。状态机按照相同顺序执行相同命令，最终各节点状态完全一致。

“多数人点头”让定稿既安全又高效：不要求全员到场，只要过半就能推进。就像开会时不必等所有人都签字，只要超过半数人签名，决议就能生效。

Raft异同：把会议室规则写成傻瓜版手册

Multi-Paxos 非常强大，但它更像一篇论文里的“设计思路”，留下很多灰色地带：什么情况下允许空洞？新 Leader 上任时怎么补齐日志？这些细节在工程实现时相当容易踩坑。Raft 的成功正在于它把 Multi-Paxos 的松散规则改写成了严格、可逐条执行的操作手册。

Raft 与 Multi-Paxos 的第一个区别是角色划分。Multi-Paxos 里“提议者、接受者、学习者”三种角色是叠加在同一批节点上的，身份切换很灵活；而 Raft 把每个节点硬性分成 Leader、Follower、Candidate 三种状态，并用状态机限定转换条件。第二个区别是日志匹配（Log Matching）。Raft 强制要求：如果两个节点在同一个索引处有相同任期号，那么之前的日志必须完全一样；Leader 在追加日志前还要检查 Follower 与自己的最近一条日志是否匹配。这条规则在 Multi-Paxos 中并不显式，但 Raft 直接写进了算法。第三个区别是提交规则的收紧：Raft 规定 Leader 不能通过“旧任期日志已经被复制到多数派”来提前提交它，而必须等当前任期的一条新日志也提交成功，才允许一并提交旧日志，避免日志覆盖把已提交的内容回滚。

从这个角度看，可以写出一句便于记忆的公式：Raft = Multi-Paxos + 工程约束。Multi-Paxos 是思想，Raft 是带着安全护栏的落地实现。

把 Multi-Paxos 理解成“会议室治理哲学”，Raft 就是一份写清楚“谁负责签到、谁负责记录、争议如何裁决”的员工手册。现在很多数据库（比如 etcd、TiKV）都选择直接实现 Raft，但它们的血脉里始终流淌着 Multi-Paxos 的思想。

AI 应用场景

Python 演示

class Replica:    def __init__(self, name):        self.name = name        self.promised = 0   # 已应允的最大提案轮数        self.accepted = []  # 已接受条目的 (轮数, 索引, 值)        self.commit = 0     # 已提交索引  class MultiPaxosLog:    def __init__(self):        self.replicas = [Replica(name) for name in ["A", "B", "C"]]        self.leader = self.replicas[0]        self.ballot = 1        self.log = []     def prepare_once(self):        # 领导者刚上任，只需要做一次Prepare        for r in self.replicas:            r.promised = self.ballot        return sum(1 for r in self.replicas) > len(self.replicas) / 2     def propose(self, value):        idx = len(self.log)        for r in self.replicas:            if r.promised >= self.ballot:                r.accepted.append((self.ballot, idx, value))        acks = sum(1 for r in self.replicas                   if r.accepted and r.accepted[-1][1] == idx)        if acks > len(self.replicas) / 2:            self.log.append(value)            for r in self.replicas:                r.commit = len(self.log)            return True        return False  def main():    paxos = MultiPaxosLog()    if not paxos.prepare_once():        print("prepare failed")        return    for cmd in ["set key=1", "set key=2", "del key"]:        ok = paxos.propose(cmd)        print(cmd, "committed" if ok else "rejected")    print("final log:", paxos.log)  if __name__ == "__main__":    main()

1. r.promised = self.ballot各副本把本轮编号记入账簿，相当于接受者承诺“只认这个编号的 Leader”。
2. r.accepted.append((self.ballot, idx, value))副本把收到的日志条目记录进本地日志。
3. acks > len(self.replicas) / 2只有确认数量超过半数，条目才算提交成功。
4. self.log.append(value)Leader 将日志推进到新索引，代表提交状态前移。
5. r.commit = len(self.log)所有副本同步更新自己的提交指针，之后可以安全执行已提交命令。

常见误区

面试题