Paxos 协议从零实现：Basic Paxos 到 Multi-Paxos 完整工程

Lamport 的 Paxos 被誉为「分布式共识的圣经」，也是公认最难理解的算法之一。但它的核心其实只有两条不变量：接受者只接受编号更大的提案，且一旦某值被多数派接受，之后的提案必须带着这个值。本文不画图讲希腊议会，而是给出完整可运行的 Go 实现：三角色状态机、两阶段协议的每一条消息处理、双提议者互掐的活锁演示，以及在 Basic Paxos 之上构建的 Multi-Paxos 日志复制状态机。

一、Paxos 要解决什么问题

在异步网络中，多个节点需要就一个值达成一致，且满足：只有被提出的值才可能被选定（有效性）、所有节点选定的值相同（一致性）、只要多数派存活就能持续做出决定（活性）。FLP 定理告诉我们完美的确定性方案不存在，Paxos 的取舍是：永远保证安全性（不选错），多数派存活时大概率保证活性（能选定）。

三个角色

提议者（Proposer）：接收客户端请求，发起两阶段提案。
接受者（Acceptor）：对提案投票，是共识的真正裁决者。其状态必须持久化（宕机重启后不能违背承诺）。
学习者（Learner）：被动接收被选定的值，驱动状态机前进。

两阶段协议（精确描述）

阶段一 Prepare：提议者选编号 n，向多数派发送 Prepare(n)。接受者收到后：若 n 大于它承诺过的所有编号，则承诺不再接受编号小于 n 的提案，并回复它已接受过的最大编号提案 (n_accepted, v_accepted)。
阶段二 Accept：提议者集齐多数派承诺后，从回复中挑选编号最大的 v_accepted 作为自己的提案值（若都为空则用自己的值），向多数派发送 Accept(n, v)。接受者收到后：若未承诺过更大编号，则接受该提案。值一旦被多数派接受即被「选定」（Chosen）。

二、完整实现：Basic Paxos

2.1 消息与接受者状态机

接受者是 Paxos 安全性的基石。它只需记住三个值：promisedN（已承诺的最大编号）、acceptedN、acceptedV（已接受的最大编号提案）：

package main

import (
    "fmt"
    "sync"
)

// ---- 消息定义 ----
type Prepare struct{ N int }
type Promise struct {
    N         int
    AcceptedN int
    AcceptedV string
    HasAccepted bool
}
type Accept struct {
    N int
    V string
}
type Accepted struct {
    N int
    V string
}

// Acceptor 接受者：共识的裁决者
type Acceptor struct {
    mu        sync.Mutex
    id        int
    promisedN int    // 已承诺的最大提案编号，0 表示无
    acceptedN int    // 已接受的最大提案编号
    acceptedV string // 已接受的提案值
    hasAccepted bool
}

func NewAcceptor(id int) *Acceptor {
    return &Acceptor{id: id}
}

// OnPrepare 处理 Prepare 请求：Paxos 安全性的第一道闸
func (a *Acceptor) OnPrepare(p Prepare) (Promise, bool) {
    a.mu.Lock()
    defer a.mu.Unlock()
    if p.N <= a.promisedN {
        return Promise{}, false // 拒绝：已承诺过更大或相等的编号
    }
    a.promisedN = p.N
    // 承诺的同时，如实汇报自己接受过的最大提案
    return Promise{
        N: p.N,
        AcceptedN: a.acceptedN,
        AcceptedV: a.acceptedV,
        HasAccepted: a.hasAccepted,
    }, true
}

// OnAccept 处理 Accept 请求：第二道闸
func (a *Acceptor) OnAccept(acc Accept) (Accepted, bool) {
    a.mu.Lock()
    defer a.mu.Unlock()
    if acc.N < a.promisedN {
        return Accepted{}, false // 拒绝：期间已承诺了更大编号
    }
    a.promisedN = acc.N
    a.acceptedN = acc.N
    a.acceptedV = acc.V
    a.hasAccepted = true
    return Accepted{N: acc.N, V: acc.V}, true
}

注意两道闸的对称性：Prepare 用 <= 拒绝（编号必须严格递增），Accept 用 < 拒绝（同编号的 Accept 是该提议者的合法推进）。这两行比较运算就是 Paxos 全部安全性的代码化身。

2.2 提议者：两阶段完整流程

// Proposer 提议者
type Proposer struct {
    id        int
    acceptors []*Acceptor
}

func NewProposer(id int, acceptors []*Acceptor) *Proposer {
    return &Proposer{id: id, acceptors: acceptors}
}

// proposalNumber 生成全局唯一且递增的提案编号：
// 高位是轮次，低位是提议者 ID，保证不同提议者编号可比较
func (p *Proposer) proposalNumber(round int) int {
    return round*1000 + p.id
}

// Propose 执行一次完整的两阶段提案，返回选定值与是否成功
func (p *Proposer) Propose(round int, myValue string) (string, bool) {
    n := p.proposalNumber(round)
    quorum := len(p.acceptors)/2 + 1

    // ===== 阶段一：Prepare =====
    promises := []Promise{}
    for _, a := range p.acceptors {
        if pr, ok := a.OnPrepare(Prepare{N: n}); ok {
            promises = append(promises, pr)
        }
    }
    if len(promises) < quorum {
        fmt.Printf("[P%d] 轮次 %d: Prepare 仅获 %d/%d 承诺，提案失败\n",
            p.id, round, len(promises), len(p.acceptors))
        return "", false
    }

    // ===== 选择提案值：采纳已接受提案中编号最大的值 =====
    value := myValue
    maxAcceptedN := -1
    for _, pr := range promises {
        if pr.HasAccepted && pr.AcceptedN > maxAcceptedN {
            maxAcceptedN = pr.AcceptedN
            value = pr.AcceptedV // 关键不变量：沿用可能已被选定的值
        }
    }
    if maxAcceptedN >= 0 {
        fmt.Printf("[P%d] 轮次 %d: 发现已接受值 '%s' (n=%d)，放弃自己的 '%s'\n",
            p.id, round, value, maxAcceptedN, myValue)
    }

    // ===== 阶段二：Accept =====
    acceptedCount := 0
    for _, a := range p.acceptors {
        if _, ok := a.OnAccept(Accept{N: n, V: value}); ok {
            acceptedCount++
        }
    }
    if acceptedCount >= quorum {
        fmt.Printf("[P%d] 轮次 %d: 值 '%s' 被多数派接受 (n=%d)，选定!\n",
            p.id, round, value, n)
        return value, true
    }
    fmt.Printf("[P%d] 轮次 %d: Accept 仅获 %d/%d，被更高编号抢占\n",
        p.id, round, acceptedCount, len(p.acceptors))
    return "", false
}

「采纳已接受提案中编号最大的值」这一步是 Paxos 的灵魂。它保证了一旦某值被多数派接受过，任何后续提议者都会在阶段一发现它并继续传播它，而不是另起炉灶——这条不变量数学上保证了一致性，代码上就是这六行循环。

2.3 演示一：正常共识与值继承

func demoNormal() {
    fmt.Println("===== 演示一: 5 接受者，提议者完成共识 =====")
    acceptors := make([]*Acceptor, 5)
    for i := range acceptors {
        acceptors[i] = NewAcceptor(i)
    }
    p1 := NewProposer(1, acceptors)
    p1.Propose(1, "SET x = 42")

    // 另一个提议者稍后发起：它会发现并沿用已选定的值
    p2 := NewProposer(2, acceptors)
    p2.Propose(2, "SET x = 99") // 自己的值将被放弃
}

// 输出:
// [P1] 轮次 1: 值 'SET x = 42' 被多数派接受 (n=1001)，选定!
// [P2] 轮次 2: 发现已接受值 'SET x = 42' (n=1001)，放弃自己的 'SET x = 99'
// [P2] 轮次 2: 值 'SET x = 42' 被多数派接受 (n=2002)，选定!

P2 虽然带着不同的值来，但在阶段一发现了已选定的值，主动放弃自己的提议——这就是「一致性」在运行时的样子。

2.4 演示二：提议者互掐与随机退避

Paxos 不保证活性：两个提议者交替用更大编号抢占，可能谁都到不了阶段二（活锁）。工程解法是随机退避，让双方错开重试时机：

import (
    "math/rand"
    "time"
)

// ProposeWithBackoff 带随机退避的提案，直到成功
func (p *Proposer) ProposeWithBackoff(value string) string {
    for round := 1; ; round++ {
        if v, ok := p.Propose(round, value); ok {
            return v
        }
        // 随机退避：打破两个提议者的同步抢占
        d := time.Duration(rand.Intn(50*(1<<min(round, 6)))) * time.Millisecond
        fmt.Printf("[P%d] 退避 %v 后重试\n", p.id, d)
        time.Sleep(d)
    }
}

// 两个提议者并发运行时的典型输出:
// [P1] 轮次 1: Prepare 仅获 2/5 承诺，提案失败   ← 被 P2 抢占
// [P2] 轮次 1: 值 'B' 被多数派接受 (n=1002)，选定!
// [P1] 退避 37ms 后重试
// [P1] 轮次 2: 发现已接受值 'B' (n=1002)，放弃自己的 'A'
// [P1] 轮次 2: 值 'B' 被多数派接受 (n=2001)，选定!

2.5 演示三：接受者宕机与多数派容错

// 5 个接受者中 2 个宕机，剩余 3 个仍构成多数派，共识正常完成。
// 宕机的接受者重启后，凭持久化的 (promisedN, acceptedN, acceptedV)
// 继续参与协议且绝不违背承诺——这就是接受者状态必须落盘的原因。
// 若 3 个及以上宕机: Prepare 永远集不齐多数派，系统安全地"卡住"，
// 绝不做出矛盾的决定（安全性优先于活性）。

三、从 Basic Paxos 到 Multi-Paxos

Basic Paxos 一次只能确定一个值，真实系统需要连续确定一串日志项。Multi-Paxos 的思路：先选出稳定的 Leader，由 Leader 为后续所有日志项跳过阶段一（因为阶段一的本质是为一批提案锁定编号空间），直接对每个日志槽位发 Accept：

// MultiPaxos 日志复制状态机
type LogEntry struct {
    Index   int
    Term    int    // Leader 任期（复用提案编号的高位）
    Command string
    Chosen  bool
}

type MultiPaxos struct {
    mu       sync.Mutex
    id       int
    isLeader bool
    term     int
    log      []LogEntry
    commitIdx int
    applyCh  chan LogEntry // 已提交日志送往状态机执行
}

// ReplicateLeader Leader 侧：为日志项直接发起 Accept（跳过 Prepare）
func (m *MultiPaxos) ReplicateLeader(cmd string, acceptors []*Acceptor) bool {
    m.mu.Lock()
    idx := len(m.log)
    entry := LogEntry{Index: idx, Term: m.term, Command: cmd}
    m.log = append(m.log, entry)
    m.mu.Unlock()

    quorum := len(acceptors)/2 + 1
    okCount := 0
    // 槽位 idx 的提案编号由 (term, idx) 唯一确定
    n := m.term*100000 + idx
    for _, a := range acceptors {
        if _, ok := a.OnAccept(Accept{N: n, V: cmd}); ok {
            okCount++
        }
    }
    if okCount >= quorum {
        m.mu.Lock()
        m.log[idx].Chosen = true
        m.commitIdx = idx
        m.mu.Unlock()
        m.applyCh <- entry // 提交给上层状态机
        fmt.Printf("[Leader] 日志 #%d '%s' 已提交\n", idx, cmd)
        return true
    }
    return false
}

// 跟随者侧收到 Commit 通知后按序 apply，保证所有节点状态机一致

Leader 选举本身用一次 Basic Paxos 完成（提案值就是「谁是 Leader」）。这形成了一个自举结构：用 Paxos 选出 Leader，再用 Leader 高效运行 Multi-Paxos。Raft 可以看作把这个结构显式化、工程化的产物。

四、Paxos 家族对照

变体	核心优化	典型应用
Basic Paxos	单值共识的完整两阶段	成员变更、Leader 选举
Multi-Paxos	稳定 Leader 跳过阶段一，批量日志复制	Chubby、ZooKeeper(Zab)、Spanner
Fast Paxos	客户端直发接受者，冲突少时省一轮 RTT	低延迟研究系统，冲突时回退 Classic
EPaxos	无 Leader，利用命令交换性并发提交	广域网多主数据库
Cheap Paxos	正常时只用多数派，故障才唤醒辅助节点	降本场景
Raft（精神继承者）	把选举/复制/安全性拆成显式子问题	Etcd、Consul、TiKV

五、工程落地要点

接受者状态必须落盘：promisedN/acceptedN/acceptedV 要在响应前 fsync，否则重启后违背承诺，多数派交叠论证直接失效。
提案编号设计：常用 (round << 20) | nodeID，或时间戳+节点 ID 的组合，保证全局唯一且近似递增。
活锁治理：随机退避是底线；生产系统直接选主（Paxos Lease）让 99% 的请求走单提议者路径。
日志压缩：Multi-Paxos 的日志无限增长，需要快照 + 日志截断，落后太多的跟随者直接传快照。
成员变更：集群节点增减本身也要通过一次 Paxos 共识来切换配置（Joint Consensus 的 Paxos 版本）。

六、常见误区

误区一：Paxos 需要全局时钟。提案编号只需偏序可比，与物理时间无关。
误区二：多数派 = 所有节点的大多数副本都要写成功。正确理解是「任意两个多数派必有交集」，这是安全性证明的全部支点。
误区三：Prepare 阶段可以省略。没有阶段一，提议者无从得知某值是否已被选定，会写出互相矛盾的值。
误区四：Paxos 太慢不实用。Multi-Paxos 稳定期只需一次 Accept RTT，与主从复制同量级——Spanner 在全球范围都这么跑。

七、总结

本文把 Paxos 从纸面公式变成了可运行代码：接受者的两道编号闸、提议者的值继承循环、随机退避治活锁、Multi-Paxos 的选主自举。回看 Lamport 那句「Paxos 很简单」，它的真意是：一旦你把「多数派交叠」和「编号单调」这两条不变量刻进代码，正确性就会自然涌现，剩下的一切都是工程优化。

参考文献

L. Lamport. The Part-Time Parliament. ACM TOCS, 1998.
L. Lamport. Paxos Made Simple. ACM SIGACT News, 2001.
T. Chandra et al. Paxos Made Live: An Engineering Perspective. PODC, 2007.
D. Ongaro, J. Ousterhout. In Search of an Understandable Consensus Algorithm (Raft). USENIX ATC, 2014.

← 返回文章列表