Paxos算法

Paxos算法是一族用于在不可靠分布式系统中达成共识的协议,其目标是让一组进程即使部分发生故障,也能就某个提案值达成唯一且一致的决定。它被誉为分布式一致性问题的理论基石。

概述

Paxos由图灵奖得主莱斯利·兰伯特（Leslie Lamport）于1990年提出,并在1998年论文中以虚构的古希腊议会为背景正式发表。它以推导严谨著称,但也因表述晦涩而以难懂闻名,后来的Raft算法正是为了更易理解而设计。Paxos在只要多数节点存活的前提下,保证系统的安全性(不会决定出冲突的值)。

核心原理

• 三种角色:提议者(Proposer)发起提案,接受者(Acceptor)投票表决,学习者(Learner)获知最终结果,一个进程可同时承担多个角色。
• 两阶段:准备阶段中提议者用递增编号请求多数接受者承诺;接受阶段中若获多数承诺,则提交带值的提案供表决。
• 多数派原则:任意两个多数派必有交集,该交集保证不会有两个不同的值同时被选定。
• 编号约束:接受者一旦承诺更高编号,就拒绝较小编号的提案,从而避免冲突。

应用场景

谷歌的Chubby锁服务、分布式数据库Spanner的副本一致性,均以Paxos为核心。ZooKeeper的ZAB协议、etcd背后的思想也与之一脉相承。工程实践中多采用其变体Multi-Paxos,以连续决定一系列值,构建高可用的复制状态机。

常见问题

问:Paxos和Raft是什么关系?答:两者都解决分布式共识,安全性等价。Raft把问题拆成领导选举、日志复制、安全性三个清晰子模块,更易理解和实现,可视为Paxos思想的一种工程化重述。

问:为什么说Paxos只保证多数存活即可工作?答:因为它依赖多数派表决,只要超过半数节点正常,就能形成有交集的多数派完成决议;少数节点故障不影响整体达成一致。