本文适合作为阅读 Paxos Made Simple 的开胃小菜。
从分布式系统谈起
分布式系统的出现是由于随着流量的迅速增长，单台服务器已经无法满足需求了。要么让单台服务器继续增强，要么把流量分散到多台服务器，事实证明后者成本更低。分布式系统也就是将多台服务器当作一台服务器来使用，此时一致性问题便凸显出来（例如银行系统中，不允许A节点说a账户余额为1000，而B节点说a账户余额500），因为网络延迟、节点故障等原因，使用普通的方法难以保证一致性（或者成本太高）。而Paxos算法允许在挂掉少于一半节点的情况下维持系统运转。
Paxos算法解决了一个什么问题？确定一个值，也就是多个节点达成了共识。等等，确定一个值（并且之后无法更改，若可以更改那就可能导致一致性失效）对我们实际生产有什么用？很明显，数据经常是要进行修改操作的，不变的数据有什么用？我们可以想到日志系统。日志是用来记录每个操作的，有了日志，我们就知道数据发生了什么变化，那么通过回放日志（这一步交给状态机处理），我们就知道此时数据什么样。mysql的主从同步就是利用binlog。
Paxos
Paxos算法里有三个角色，提议者(proposer)：负责提出提案（也就是提出一个值让大家达成共识）；接受者(acceptor)：收到议案后可以接受(accept)提案，若有个提案被超过一半的acceptor接受，则该提案被批准；学习者(learner)：学习被批准的议案。每个节点可身兼数职。
这里我们只讨论proposer与acceptor的关系。
Paxos算法规定：一次Paxos算法实例（Instance）只能批准一个值（value）
如何满足这个约束？之前已经规定：批准的提案必须经过超过一半acceptor接受，我们称为多数派，而任意两个多数派必然至少有一个公共acceptor，那么让每个acceptor只能接受一个value，该约束能满足。
因为有网络延迟等原因，acceptor不允许收到多个提案后再决定接受哪个提案（无法保证第二个提案什么时候到达，或者根本没有第二个提案），因此规定：
P1: 每个acceptor必须接受第一次收到的提案
但是如果恰好一半acceptor接受value A，另一半接受value B的话，就无法批准任何一个value。如何解决这个问题？让每个acceptor被允许接受多个提案（注意，多个提案的value可以是一样的，我们会为每个提案分配一个递增的数字作为编号），也允许批准多个提案，但被批准的所有提案的value必须相同。于是：
P2 ：如果一个具有value v的提案被批准，那么每个被批准的更高编号的提案具有value v
一个被批准的提案必须被至少一个acceptor接受，因此可以加强P2
P2a: 如果一个具有value v的提案被批准，那么任何acceptor接受的更高编号的提案必须有value v
由于通信是异步的，现在有个提案被批准了，其中acceptor c 没有accept这个提案（也就是说c没有收到这个提案）。假设有一个proposer“苏醒”过来（可能刚刚陷入了阻塞），提出一个具有新value的提案，此时：P1要求c接受这个新提案（新提案是c收到的第一个提案），但会违反P2a，因此继续加强P2a：
P2b：如果一个具有value v的提案被批准，那么之后任何proposer提出的提案（也就是编号更大的提案）必须有value v
从P2到P2a，再到P2b，为了避免批准错误的value（也就是与之前提案不同的value），干脆从源头（proposer）解决问题。
现在想一下如何实现P2b。假设编号为m，value为v的提案已经被批准了，那么什么情况下任何编号为n（n > m ）的提案都含有value v？
P2c： 如果一个提案具有value v 和编号n，那么存在一个多数派acceptor集合S：
(a) S中的acceptor都没有接受过任何编号比n小的提案
(b) S中的acceptor接受过的比n小的最大编号的提案的value就是v
简单分析一下：（a）：此时说明还没有任何提案被批准，因为提案被批准必须获得多数派的接受。（b）设这个被S中acceptor接受过的最大编号提案的编号为m，假设m被批准了，则：每个S中的acceptor都接受了一个编号在m…(n-1)中的提案（至少接受了m，当然也可能接受了其他的），每个编号在m…(n-1)中的被接受的提案都具有value v(否则违背P2c)。
算法的具体步骤
算法分为两个阶段，第一阶段为prepare阶段，一个proposer会选择一个新的编号为n的提案，发送一个请求给某些acceptor，让它们回复：
- 承诺不再接受编号比n小的提案
- 是否如果之前有编号比n小的提案已经被接受了，如果有，将该提案回复给这个proposer
第二阶段为accept阶段：这个proposer收到回复之后（回复的acceptor应占大多数），就可以提出一个编号为n，value为v的提案了。这个v的值是什么？有两种情况：1. 回复中都说没有接受过比n小的提案，则v可以是任意值。 2. 回复中有说已经接受过比n小的提案，则将该提案的value作为v的值。这个新提案发出后，如果获得多数acceptor的接受，则被批准。
上面主要从proposer的角度来看，那从acceptor角度呢？acceptor可能会收到两种来自proposer的请求：repare请求和accept请求，但acceptor可以忽略任何一个请求而不会破环算法的安全性。
我们来看一下什么时候acceptor能够回应proposer的请求：它始终能回应prepare的请求，但是如果它回应过编号为n的prepare请求，它就不能回应编号比n小的accept请求（因为承诺不再接受编号比n小的提案）。
此时我们可以获得P1的一个加强：
P1a： 当且仅当acceptor没有回应过编号大于n的prepare请求时，它可以接受编号为n的提案。
因此，acceptor必须记住：曾经接受过的编号最大的提案 和 回应过的编号最大的prepare请求的编号
总结一下：
阶段一:
(a) 一个proposer选择一个提案编号n，发送prepare请求给一半以上的acceptor
(b) 如果acceptor收到编号为n的prepare请求，且n大于之前任何回应过的prepare请求的编号，则承诺不再接受任何比n小的提案，如果之前它接受过提案，则把其中编号最大的提案回复给proposer
阶段二:
(a) 如果Proposer收到了超过一半的acceptor对prepare请求的回应，就把包含如下提案的accept请求发送给acceptor：编号为n，v为：1 若收到的回应中有已经接受过的提案，则把编号最大的提案的v作为新提案的value. 2 若没有，则v可以是任何值。
(b) 如果acceptor收到包含编号为n的提案的accept请求，除非它已经回应了编号比n大的提案的prepare请求，否则它接受这个编号为n的提案。
以上是Paxos算法的核心内容，强烈建议读一下Lamport大师的论文Paxos Made Simple
参考链接
Paxos Made Simple
Paxos lecture (Raft user study)
维基百科——Paxos算法
微信自研生产级paxos类库PhxPaxos实现原理介绍
