Paxos算法
Paxos算法
Paxos 算法是莱斯利·兰波特（Leslie Lamport）提出的一种基于消息传递的分布式共识算法。【维基百科说过：Paxos常被误称为“一致性算法”。但是“一致性（consistency）”和“共识（consensus）”并不是同一个概念。Paxos是一个共识（consensus）算法。】
分布式系统中的节点通信存在两种模型：共享内存（Shared memory）和消息传递（Messages passing）。
基于消息传递通信模型的分布式系统，不可避免的会发生以下错误：进程可能会慢、被杀死或者重启，消息可能会延迟、丢失、重复。
在最普通的 Paxos 场景中，先不考虑可能出现“消息篡改”。（即拜占庭错误的情况：允许军中可能有叛徒，又要保证战争胜利，引申到计算机领域，成为一种容错理论）Paxos 算法解决的问题是在一个可能发生消息延迟、丢失、重复的分布式系统中，如何对某个值的看法相同，保证无论发生以上任何异常，都不会破坏决议的共识机制。
为描述Paxos算法，Lamport虚拟了一个叫做Paxos的希腊城邦，这个岛按照议会民主制的政治模式制订法律，但是没有人愿意将自己的全部时间和精力放在这种事情上。所以无论是议员，议长或者传递纸条的服务员都不能承诺别人需要时一定会出现，也无法承诺批准决议或者传递消息的时间。但是这里假设没有拜占庭将军问题（即虽然有可能一个消息被传递了两次，但是绝对不会出现错误的消息）；只要等待足够的时间，消息就会被传到。另外，Paxos岛上的议员是不会反对其他议员提出的决议的。
对应于分布式系统，议员对应于各个节点，制定的法律对应于系统的状态。各个节点需要进入一个一致的状态。
Paxos算法中，有三种角色：
提议者（Proposer）、接收者（Acceptor）、学习者（Learners）
在具体的实现中，一个进程可以同时充当多种角色。还有一个概念叫提案（Proposal）。最终要达成一致的value就在提案里。
算法的基本逻辑为：
- 提议者向所有接受者发送消息prepare(n)。（假设他们都会响应，只发送给大多数接受者就足够了。）
- 每个接受者将 n 与它已响应准备且编号最高的消息的提议进行比较（编号会自增）。如果 n 更大，它以 ack(v, n) 响应，其中 v 是它已经接受的编号最高的提议，n 是该提议的编号。（如果 n 小，此时应该做出的优化是使接受者发回 nack消息，让提议者知道该提案已经被认定，应该撤回并重试。
- 提议者等待从大多数接受者那里收到已经确认的提案。如果任何 ack 包含一个值，它会将 v 设置为它收到的最新（按提案编号排序）值。然后它将 accept(n, v) 发送给所有接受者（或只是多数）。接收者负责学习接收到的提案。
- 在接收到accept(n, v) 后，accepter 接受v，除非它已经接收到过 prepare(n) 大于当前n的提案。
Apache ZooKeeper 就是使用一个类Multi-Paxos的共识算法作为底层存储协同的机制。
Google在其分布式锁服务中应用了Multi-Paxos算法。Chubby lock应用于大表（Bigtable），在谷歌所提供的各项服务中有广泛应用。
维基百科：https://zh.wikipedia.org/wiki/Paxos算法
Lamport于1998年第一次公开发表[PDF] ：https://lamport.azurewebsites.net/pubs/lamport-paxos.pdf
Lamport 觉得同行无法接受他的幽默感，于是用容易接受的方法重新表述了一遍[PDF] ：https://lamport.azurewebsites.net/pubs/paxos-simple.pdf
gabrielle's blog