什么是Paxos？
Paxos算法是莱斯利·兰伯特（英语：Leslie Lamport，LaTeX中的“La”）于1990年提出的一种基于消息传递且具有高度容错特性的共识（consensus）算法，是一种去中心化共识算法（注意，非一致性算法），用于使一组计算机就单个值达成一致，例如通常使用两阶段或三阶段提交做出的提交或回滚决定，最终促成共同认可的一个结果值，即对多个节点产生的值，该算法能保证只选出唯一一个值。
在分布式系统中，要使各个机器对某个选举达成共识是比较麻烦的，因为机器之间的消息可能会丢失或无限延迟，或者机器本身可能会出现故障。而Paxos算法可以保证的是节点最终只会选择一个值，但不保证在大多数节点不可用时能选出一个值。
Paxos 主要分为三类节点：
- 提议者（Proposer）：提议一个它所支持的值，并发送给每个Acceptor；
- 接受者（Acceptor）：决定是否接受Proposer的提议，并将自己决定值发给Leaner；
- 告知者（Learner）：被告知投票的结果，不参与投票过程。
PS：实际上单节点可能扮演多个不同的类型的节点角色（甚至全部角色），而为了容易理解，下面示例图是假设一个节点只扮演一个角色。
几个概念：
1、消息类型
标准的Paxos算法中Proposer会分为两种不同消息类型发送给Acceptor：
- prepare request：提案
- accept request
在下面的流程描述中会详述这两种消息类型的格式与其作用。
2、提议编号
对于每个Proposer节点都会有一个唯一、正值、递增的提议编号，每个Acceptor只认prepare消息中这个编号的大小，大的优先被采纳，并且在接受某个提议后，Acceptor可以保证不会接受小于该提议编号的提议。
流程（两阶段提交）：
阶段一：prepare请求（Proposer → Acceptor）
1、Proposer会发送prepare消息给所有Acceptor，其格式为[n, v]，n表示当前Proposer持有的提议编号。
2、在上面示例中，有两个Proposer（A、B），三个Acceptor（X、Y、Z），假设A发出的prepare消息先于B到达X、Y，而B发出的prepare先于A到达Z。
3、接下来X、Y、Z会如何处理A、B先到的消息？
对于先到达的A的提议，X、Y由于在A的提议之前没有接受过其他消息，X、Y会设置收到的提议为[n=2, v=8]，然后回应A一个prepare response[no previous]表示先前没有收到其他提议，并承诺不会接受编号比2更小的提议；Z同理，对于先到达的B的提议，也会接受、存储、响应，并承诺不会接受编号比4更小的提议。
4、那么X、Y如何处理后到的B的提议，Z又如何处理后到的A的提议？
由于B的提议编号n=4比先前A的n=2更大，X、Y会接受B的提议，将当前提议设置为[n=4, v=5]，并响应之前[n=2, v=8]给B；而对于后到的A的提议，Z判断A的提议编号n=2小于目前持有的提议编号n=4，于是忽略掉A的提议。
阶段二：accept请求（Proposer → Acceptor）
每个Proposer收到超过Acceptor数量半数的响应后，就可以发出accept请求（真正提交议案）
1、对于A而言，收到X、Y两个响应后，会向所有Acceptor发出accept请求[n=2, v=8]，然而由于X、Y、Z持有的提议编号为4，且承诺不会接受提议编号低于4的提议，所以不会接受A的提议。
2、对于B而言收到超过半数响应后，也会向每个Acceptor发送一个接受请求，其中包含它之前使用的提议编号 (n=4) 以及与它收到的prepare响应消息中最高提议编号相关联的值 (v=8)[3]，最终发出accept请求为[n=4, v=8]。
阶段三（准确地说不属于一个阶段）：Learn阶段（Acceptor → Learner）
对于每个Acceptor而言，如果收到的accept请求提议编号大于或等于它持有的提议编号，则会接受该提案并发送accepted请求给所有Learner节点。当Learner发现大多数Acceptor已经接受一个值时，Paxos算法最终就会选择这一个值，一旦 Paxos 选择了一个值，此时如果还有其他Proposer（假如为C）再提出不同的提议，即使C提议编号更高（假设[n=6, v=7]），也不会被接受，Acceptor仍然只接受之前提议编号最大的[n=4, v=8]，但需要C发送一个包含 [n=6, v=8] 的接受请求，它只确认、同步已经选择出来的值（此外，如果此时还有少数Acceptor还没有选择一个值，这个过程可以确保他们最终就相同的值v=8达成共识）。
Paxos的应用场景
一个典型的场景是，在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点都执行相同的操作序列，那么他们最后能得到一个一致的状态。那么为了保证每个节点执行相同的命令序列，就需要在每一条指令上执行一个“共识算法”以保证每个节点看到的指令一致。
Paxos的优化方案：
Multi-Paxos、Fast-Paxos，对于这两种优化方案，本文暂不深入探究。
参考文献：
https://medium.com/@angusmacdonald/paxos-by-example-66d934e18522
