第二阶段（Accept）：Proposer收到的答复中，如果过半数的Acceptor已经接受，Proposer把第一阶段的Proposal广播给所有Acceptor。而大多Acceptor已经接受了其他编号更大的Proposal时，Proposer把这个Proposal作为自己的Proposal提交。Acceptor接到请求后，如果Proposal编号最大则确认并返回结果给所有Proposer，如果Proposer得到多数派回复，则认为最终一致的值已经确定（Chosen）。Learner不参与提议，完成后学习这个最终Proposal。

　　严格证明是通过数学归纳法，本文只做了直观判断。Paxos确认这个值利用的是“抽屉原理”，固定数量的节点选取任意两次过半数的节点集合，两次集合交集必定有节点是重复的。所以第一阶段任何已经接受的提议，在第二阶段任意节点宕机或失联，都有某节点已经接受提议，而编号最大的提议和确定的值是一致的。递增的编号还能减少消息交互次数，允许消息乱序的情况下正常运行。就一个值达成一致的方式（Basic Paxos）已经明确了，但实际环境中并不是达成一次一致，而是持续寻求一致，读者可以自己思考和推导，想深入研究建议阅读Leslie Lamport的三篇论文《Paxos made simple》、《The Part-Time Parliament》、《Fast Paxos》。实现多值方式（原文为Multi Paxos），通过增加Leader角色统一发起提议Proposal，还能节约多次网络交互的消耗。Paxos协议本身不复杂，难点在如何将Paxos协议工程化。

　　我们实现Paxos存储做了一些改进，使用了无租约版Paxos分布式协议，参考Google MegaStore做了写优化，并通过限制单次Paxos写触发Prepare的次数避免活锁问题。虽然Paxos算法下只要多数派存在，就可以在分布式环境下达到严格的一致性。但是牺牲的性能代价可观，在大部分应用场景中，对一致性的要求并不是那么严格，这个时候有不少简化的一致性算法，比如Quorum。

　　简化的Quorum（NWR）算法

　　Quorum借鉴了Paxos的思想，实现上更加简洁，同样解决了在多个节点并发写入时的数据一致性问题。比如Amazon的Dynamo云存储系统中，就应用NWR来控制一致性。微信也有大量分布式存储使用这个协议保证一致性。Quorum最初的思路来自“鸽巢原理”，同一份数据虽然在多个节点拥有多份副本，但是同一时刻这些副本只能用于读或者只能用于写。

　　图3 Quorum模型：微信改进的版本、数据分离结构

Quorum控制同一份数据不会同时读写，写请求需要的副本数要求超过半数，写操作时就没有足够的副本给读操作；

Quorum控制同一份数据的串行化修改，因为副本数要求，同一份数据不会被两个写请求同时修改。

　　Quorum又被称为NWR协议：R表示读取副本的数量；W表示写入副本的数量；N表示总的节点数量。

假设N=2，R=1，W=1，R+W=N=2，在节点1写入，节点2读取，无法得到一致性的数据；

假设N=2，R=2，W=1，R+W>N，任意写入某个节点，则必须同时读取所有节点；

假设N=2，W=2，R=1，R+W>N，同时写入所有节点，则读取任意节点就可以得到结果。

　　要满足一致性，必须满足R+W>N。NWR值的不同组合有不同效果，当W+R>N时能实现强一致性。所以工程实现上需要N>=3，因为冗余数据是保证可靠性的手段，如果N=2，损失一个节点就退化为单节点。写操作必须更新所有副本数据才能操作完成，对于写频繁的系统，少数节点被写入的数据副本可以异步同步，但是只更新部分节点，读取则需要访问多个节点，读写总和超过总节点数才能保证读到最新数据。可以根据请求类型调整BWR，需要可靠性则加大NR，需要平衡读写性能则调整RW。

　　微信有大量分布式存储（QuorumKV）使用这个算法保证一致性，我们对这个算法做了改进，创造性地把数据副本分离出版本编号和数据存到不同设备，其中N=3（数据只有2份，版本编号有3份），在R=W=2时仍然可以保证强一致性。因为版本编号存放3份，对版本编号使用Quorum方式，通过版本编号协商，只有版本序号达成一致的情况下读写单机数据，从而在保证强一致性的同时实现高读写性能。实际数据只写入一台数据节点，使用流水日志的方式进行同步，并更新版本编号。但是我们的分布式存储（QuorumKV）仍存在数据可靠性比Paxos低的问题，因为数据只写一份副本，依靠异步同步。如果数据节点故障，故障节点上没有同步到另一个节点，数据将无法访问。版本节点故障时，如果Quorum协议没有设置W=3，也可能无法访问正确的数据节点副本。

　　后记