Paxos 算法

概述

Paxos 是由图灵奖得主 Leslie Lamport 提出的分布式共识算法,最早见于其论文《The Part-Time Parliament》,后以更易读的《Paxos Made Simple》广为流传。它解决的核心问题是:在节点可能宕机、消息可能丢失或延迟的异步网络中,多个节点如何对一个值达成不可撤销的一致。

角色与流程

Paxos 将参与者分为 Proposer(提议者)、Acceptor(接受者)和 Learner(学习者)三种角色。协议分两个阶段:Prepare 阶段中 Proposer 携带全局递增的提案编号向 Acceptor 请求承诺;Accept 阶段中 Proposer 将值发送给 Acceptor,只要获得多数派(Quorum)接受,该值即被选定。多数派机制保证任意两个多数派必有交集,从而杜绝两个不同的值同时被选定。

变体与影响

实际系统通常使用 Multi-Paxos,通过选出稳定 Leader 省去重复的 Prepare 阶段。Google 的 Chubby 锁服务即基于 Paxos 实现。由于 Paxos 以难以理解和工程化著称,斯坦福的 Diego Ongaro 等人后来设计了以可理解性为目标的 Raft 算法,但 Paxos 仍是理解现代分布式一致性协议的理论基石。