Paxos算法是分布式系统中非常重要的一个算法。Paxos算法是莱斯利·兰伯特（英语：Leslie Lamport，LaTeX中的“La”）于1990年提出的一种基于消息传递且具有高度容错特性的一致性算法。

主要有两篇论文：

• The Part-Time Parliament：Lamport于1998年发表在ACM Transactions on Computer Systems。第一次公开发表
• Paxos Made Simple：2001年。Lamport觉得同行无法接受他的幽默感，于是用容易接受的方法重新表述了一遍。

Paxos算法其实理解起来有一些晦涩，本文试图通过一些图解和例子结合，尽量让它通俗易懂。

为什么需要分布式一致性算法？

分布式系统中的节点通信存在两种模型：共享内存（Shared memory）和消息传递（Messages passing）。

在分布式系统中，各结点是相对独立的，很难使用“共享内存”。

基于消息传递通信模型的分布式系统，不可避免的会发生以下错误：进程可能会慢、被杀死或者重启，消息可能会延迟、丢失、重复。

所以我们需要一个方法来保证基于“消息传递”通信模型的分布式系统能够达成一致的算法。一个典型的场景是，在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点都执行相同的操作序列，那么他们最后能得到一个一致的状态。

Paxos算法就是解决这个问题的。举个通俗的例子：

• 假如我们有5个游客，3个导游，他们要决定接下来去哪个城市旅游
• 如果可以拉一个微信群商量，那就相当于“共享内存”模型了，我们这里假定不能“拉群”
• 每个游客和导游之间互相可以通过“私聊”交流，这就相当于“消息传递”模型
• 每个导游想去的城市不一样
• 每个导游给游客发短信的时间是不固定的
• 游客可能会延迟收到每个导游的消息，也可能根本收不到
• 少数服从多数，如果大多数游客同意去一个城市，那就可以去那个城市

我们期望达到的目标是：最终所有人达成共识：去同一个城市旅游。

算法描述

我们先来看一下角色。在这个系统中，主要有两个角色：

• 提议者 Proposer：提出决议的人，在这里就是“导游”的角色。
• 批准者 Acceptor：批准决议的人，这这里就是“游客”的角色。

具体怎么操作呢？我们以一个导游和一个游客为例，Paxos算法分为两阶段，共4步。如图：

例子

下面我们以“游客”和“导游”为例，来讲述这个算法的原理。

第一阶段（占坑阶段）

导游发出占坑请求

导游1（给所有游客发送短信）：大家好，我是导游1，我想发出一个提议，我这个提议的编号是4，你同意吗？

可能发生以下几种情况：

游客1：我之前没有收到过其它短信，同意！（并记录下来当前最大编号是4）；

游客2：（看了看，之前收到过的最大编号是3）同意！（并记录下来当前最大编号是4）；

游客3：（看了看，之前收到过的最大编号是5，想了想，不理他）；

游客4：（看了看，之前已经接受了其它导游的提议了，已经进行到了第二阶段，编号是3，想去的城市是重庆）同意！我之前收到的最大编号是3，他想去的城市是重庆；（并记录下来当前最大编号是4）；

其他游客也根据自己的情况去回复。。。

第二阶段

P2a：导游根据收到的回复进行下一步私聊

经过一段时间后，导游收到了一些回复。有以下几种情况：

超过半数的人都回复了OK，且没人回复已经accepted的城市，则导游发出accept请求，并带上自己的N和V：

导游：很好，我的提议的编号还是4，我提议去成都！

超过半数的人都回复了OK，但有些人已经accepted了城市，其中最大的已经accept的编号是3，想去的城市是重庆，则导游发出accept请求，并带上自己的N和回复中N最大的V：

导游：很好，我的提议的编号还是4，我提议去重庆！

回复数量小于一半，尝试生成更大的N，再转到阶段一。

导游1（给所有游客发送短信）：大家好，我是导游1，我想发出一个提议，我这个提议的编号是7，你同意吗？

P2b：游客应答导游的accept请求

游客收到了导游的提议编号N和城市V。比较本地保存的最大编号MaxN：

导游：我的提议编号是4，我提议去成都！

游客1：（看了一下，本地最大编号是3）好啊，那就去成都！（并记下最大编号是3，想去的城市是成都）；

游客2：（看了一下，本地最大编号是5，不理他）；

其他游客也根据自己的情况去回复。。。

P2c：导游收集所有结果，进行下一步处理

超过半数的人回复提议成功，就广播给所有游客，通知他们这个提议：

导游1：行程已经确认了，去成都！大家记得保留在你们的记事本里面！

游客1：好的！

游客2：好的！

。。。

否则，生成更大的N，重复第一阶段：

导游1（给所有游客发送短信）：大家好，我是导游1，我想发出一个提议，我这个提议的编号是7，你同意吗？

相关问题

如何产生一个递增的唯一编号？

根据Lamport的论文，可以使用(n + i * m)来产生一个递增的唯一编号。

其中n为提议者的编号。比如导游1的n就是1，导游2的n就是2。

m是总共有多少个提议者，比如我们一个有三个导游，那m就是3。

i是轮次，可以从1开始递增。

所以导游1的编号就是：4，7，10，13…

为什么要“过半数”？

试想一下，如果没有这个要求。假如一共10个游客，其中五个达成协议去重庆，另外5个达成协议去成都，那怎么进行最终的商定？

所以我们在使用Paxos算法搭建分布式集群的时候，会尽量让Acceptor的数量为奇数。

陷入死循环了怎么办？

这是一种极端的情况，导游1进行完了第一阶段，编号为N1，准备发送accept请求。但与此同时，导游2发送了一个更大的编号N2，会让所有的游客替换本地的MaxN为N2，这样就会导致导游1发送的accept请求全部被拒绝，然后导游1会重新进入第一阶段，发送一个更大的编号，这又可能会导致所有游客拒绝导游2的accept请求，进入了一个死循环。

Lamport的第二篇论文提出了一种解决方案：制定一个特定的Proposer，是他作为唯一一个可以提案的Proposer。这样一来，只要这个Proposer能与过半的Acceptor进行通信，该提案终将会被批准。

Paxos算法到底有什么用？

Paxos算法是一个“分布式一致性状态”的理论算法。它有许多改进版本和具体的技术实现。比如做分布式锁、元数据存储、master选举等。

Chubby（分布式锁服务）是基于Paxos算法的，Hypertable（分布式存储）底层也用到了Paxos来保证元数据的分布式一致性。

Zookeeper是基于ZAB协议的，ZAB协议和Paxos算法有些不同，但是由Paxos算法发展而来。

我们可以把上面“导游”和“游客”的例子类比成数据库的结点。把“去某个城市旅游”的提议改为“我想成为主结点”，就成为了典型的“分布式主结点选举问题”。