Paxos算法原理与变种

约 1932 字大约 6 分钟

distributedpaxos

2025-05-24

概述

Paxos是Leslie Lamport于1990年提出的分布式共识算法，是所有分布式共识算法的理论基石。尽管以"难以理解"著称，但深入理解Paxos对于掌握分布式系统的核心原理至关重要。本文从Basic Paxos出发，逐步展开Multi-Paxos及其他变种。

历史背景

Lamport最初以一个虚构的希腊城邦"Paxos"的议会投票故事来描述这个算法（1990年论文《The Part-Time Parliament》），但过于晦涩导致被拒稿。直到1998年才正式发表，2001年又写了一篇更直白的《Paxos Made Simple》。此后，Google Chubby、Apache ZooKeeper等系统将Paxos付诸实践。

Basic Paxos

角色定义

Proposer：接收客户端请求，发起提案（Proposal），包含一个提案编号（Proposal Number）和一个值（Value）
Acceptor：对Proposer的提案进行投票，多数Acceptor接受后，提案被选定（Chosen）
Learner：学习被选定的提案值，不参与投票

两阶段协议

Basic Paxos分为Prepare阶段和Accept阶段。

核心约束

public class Acceptor {
    private long promisedN = 0;     // 承诺不再接受小于此编号的提案
    private long acceptedN = 0;     // 已接受的提案编号
    private Object acceptedValue = null; // 已接受的值

    /**
     * 阶段一：处理Prepare请求
     * 承诺(Promise)：如果n > promisedN，承诺不再接受编号小于n的提案
     */
    public PrepareResponse handlePrepare(long n) {
        if (n > promisedN) {
            promisedN = n;
            return new PrepareResponse(true, acceptedN, acceptedValue);
        }
        return new PrepareResponse(false, 0, null);
    }

    /**
     * 阶段二：处理Accept请求
     * 如果n >= promisedN，接受此提案
     */
    public AcceptResponse handleAccept(long n, Object value) {
        if (n >= promisedN) {
            promisedN = n;
            acceptedN = n;
            acceptedValue = value;
            return new AcceptResponse(true);
        }
        return new AcceptResponse(false);
    }
}

public class Proposer {
    /**
     * 关键规则：如果Prepare阶段发现Acceptor已经接受过提案，
     * Proposer必须使用编号最大的已接受提案的值，而不是自己的值。
     * 这保证了已选定的值不会被覆盖。
     */
    public Object chooseValue(List<PrepareResponse> responses, Object myValue) {
        Object highestAcceptedValue = null;
        long highestAcceptedN = 0;
        for (PrepareResponse resp : responses) {
            if (resp.acceptedN > highestAcceptedN) {
                highestAcceptedN = resp.acceptedN;
                highestAcceptedValue = resp.acceptedValue;
            }
        }
        // 如果有已接受的值，使用该值；否则使用自己的值
        return highestAcceptedValue != null ? highestAcceptedValue : myValue;
    }
}

活锁问题

当两个Proposer交替发起更高编号的Prepare，导致谁也无法完成Accept阶段：

解决方案： 引入Leader（Distinguished Proposer），同一时刻只有一个Proposer发起提案，这就是Multi-Paxos的核心思想。

Multi-Paxos

Multi-Paxos是对Basic Paxos的实际工程优化，通过选举一个稳定的Leader来减少消息轮次。

优化要点

在Multi-Paxos中：

首先运行一轮Basic Paxos选举Leader
Leader在其任期内直接进入Accept阶段（跳过Prepare），因为没有竞争者
显著减少了消息数量和延迟

public class MultiPaxosLeader {
    private long currentN;
    private boolean isLeader;

    /**
     * 成为Leader后，对每个新的日志槽位：
     * 跳过Prepare，直接发送Accept
     */
    public void proposeValue(int slot, Object value) {
        if (!isLeader) {
            // 需要先运行Basic Paxos获取领导权
            runPreparePhase();
        }

        // 直接进入Accept阶段
        AcceptRequest req = new AcceptRequest(currentN, slot, value);
        int accepted = 0;
        for (Acceptor acceptor : acceptors) {
            if (acceptor.handleAccept(req).isAccepted()) {
                accepted++;
            }
        }
        if (accepted > acceptors.size() / 2) {
            // 值被选定
            commit(slot, value);
        }
    }
}

Fast Paxos

Fast Paxos由Lamport在2006年提出，允许客户端直接向Acceptor发送提案，在无冲突时只需一轮消息延迟。

代价： 需要更大的法定人数（Quorum）。对于n个Acceptor，Classic Paxos需要 n/2 + 1，Fast Paxos需要 2n/3 + 1。

Flexible Paxos

Flexible Paxos（FPaxos, 2016年）放松了Paxos的法定人数要求：

经典Paxos要求： Prepare Quorum = Accept Quorum = n/2 + 1

Flexible Paxos： 只要求 Prepare Quorum + Accept Quorum > n

例如 5个Acceptor:
经典Paxos: Prepare需要3, Accept需要3
FPaxos选项1: Prepare需要4, Accept需要2 (写优化)
FPaxos选项2: Prepare需要2, Accept需要4 (读优化)

这意味着可以根据读写比例来优化法定人数大小，在正常运行时（Accept阶段）使用更小的Quorum，提高性能。

Paxos与Raft对比

特性	Paxos	Raft
理论完备性	极高（数学证明）	高（等价于Multi-Paxos）
可理解性	低（抽象，多变种）	高（设计目标就是易理解）
Leader	Multi-Paxos有，Basic无	始终有Leader
日志连续性	不要求（可有空洞）	要求连续
实现难度	极高	中等
工程实践	Chubby, ZooKeeper(变种)	etcd, Consul, TiKV

Paxos在实际系统中的应用

Google Chubby

Google内部的分布式锁服务，底层使用Multi-Paxos实现一致性复制。Chubby是GFS和Bigtable的基础组件。

Apache ZooKeeper（ZAB协议）

ZooKeeper使用的ZAB（ZooKeeper Atomic Broadcast）协议不是严格的Paxos，但受Paxos启发：

与Multi-Paxos类似，有一个稳定的Leader
保证消息的因果顺序（Paxos不保证）
使用epoch（类似Raft的term）标识Leader

Google Spanner

使用Multi-Paxos进行跨数据中心的一致性复制，结合TrueTime实现全球范围的外部一致性。

提案编号的生成

提案编号必须全局唯一且递增，常见做法：

public class ProposalNumberGenerator {
    private final int serverId;    // 服务器唯一标识
    private final int totalServers; // 服务器总数
    private long round = 0;

    // 提案编号 = round * totalServers + serverId
    // 保证全局唯一且递增
    public long nextProposalNumber() {
        round++;
        return round * totalServers + serverId;
    }

    // 例: 3台服务器(id=0,1,2)
    // Server0: 3, 6, 9, 12...
    // Server1: 4, 7, 10, 13...
    // Server2: 5, 8, 11, 14...
}

9f6c2-feat: organize wiki content and refresh site setup于 2026/3/14