一致性问题是分布式系统中的核心问题，目前经典的一致性算法包括2PC、3PC、Basic-Paxos、ZAB、Multi-Paxos、Raft、Dynamo等等，本文将对梳理和对比这些算法。

CAP理论

　　CAP理论是Eric Brewer在1999年提出，指分布式系统中强一致性（C）、高可用性（A）和分区容错性（P）三者不可能同时满足，该理论于2002年被证明。在目前的网络设施下，分布式系统中的网络分区错误难以避免，因此分区容错性（P）一般必须保证，只能在强一致性（C）和高可用性（A）中进行权衡。
　　然而三选二的理论存在误导性，CAP理论作者本人在2012年重新梳理的CAP理论。其实CAP理论只是说完美的强一致和高可用不能同时和分区容错并存，但是不完美的呢？首先分区不发生的情况下，CA可以共存，而且P发生的概率一般不高，所以没有必要在设计之初直接放弃C或者A。其次，假设分区发生了，C和A的选择一定完全水火不容吗？这也不一定，因为C包括了很多数据，A也包括了很多服务，要具体情况具体分析，而非一刀切。有些数据放弃C是没什么问题的，但有些数据一旦不一致就会造成重大影响。A也一样，有些服务并不会影响C，那完全可以继续提供，有些服务直接影响不能放弃C的数据，这类服务就必须暂时不可用。那放弃了C的部分数据一定就不一致了吗？放弃了A的服务一定就会让客户很不开心吗？这也不一定，例如分区期间暂时放弃了C的数据可以在分区恢复之后进行合并，合并方法又有很多种。放弃了A的服务虽然不能立即给出应答，但可以记录下客户的操作意向，给出进行中的提示。
　　总结来说，CAP理论并非三选二那么简单，因为该理论只是不允许分区错误发生的情况下所有数据都是强一致，所有服务都立即给出正确应答这种完美的系统。所以，即使不能达到完美，但可以努力趋近完美。

2PC与3PC

2PC

　　两阶段提交时分布式关系型数据库中实现事务的经典方法，都是基于协调者（leader）的事务提交方法。顾名思义，数据的提交分为两个阶段：

1. 第一阶段是prepare阶段，也叫投票阶段。
   协调者向参与者发起事务准备请求，参与者执行事务并记录日志，然后向协调者发送Ack消息。如果参与者不能执行事务，则向协调者发送No消息。

2. 第二阶段是commit阶段，也叫执行阶段，这个阶段分为两种情况。
   2.1 如果协调者收到所有参与者的ack消息，则协调者向所有参与者发送事务提交请求，参与者提交事务，然后向协调者发送ack消息。
   2.2 如果任意一个参与者向协调者发送了No消息，则协调者向所有参与者发送事务回滚请求，协调者根据日志回滚事务，然后向协调者发送ack消息。

　　两阶段提交的优点是原理简单，实现方便，但有个很明显的缺点就是同步阻塞问题，如果任意一个参与者挂掉，则事务会阻塞，其他参与者拿到的事务资源也无法释放。另外，2阶段提交还有明显的单点问题、网络异常时的数据不一致问题。

3PC

　　三阶段提交是为了解决两阶段提交的同步阻塞问题而提出的，同时改良了（而非解决）两阶段提交的数据不一致问题。三阶段提交分为三个阶段：

1. 第一阶段是CanCommit阶段
   协调者向参与者发起PreCommit请求，询问参与者能否执行事务，如果参与者可以执行事务，则恢复yes消息，否则恢复no消息。

2. 第二阶段是PreCommit阶段
   2.1 如果协调者收到所有参与者的yes消息，则协调者向参与者发送PreCommit请求，参与者执行事务并记录日志，然后向协调者发送ack消息，如果参与者未能执行事务，则向协调者发送no消息。
   2.2 如果协调者收到任意一个参与者的no消息或者超时没能收到部分参与者的应答，则协调者向参与者发送abort请求，参与者中断事务。
   2.3 如果参与者超时没能收到协调者的PreCommit请求，则参与者中断事务。

3. 第三阶段是DoCommit阶段
   3.1 如果协调者收到所有参与者第二阶段的ack消息，则协调者向参与者发出DoCommit请求，参与者执行事务提交并释放事务资源，然后向协调者发送ack消息
   3.2 如果协调者收到任意一个参与者的no消息或者超时没能收到部分参与者的应答，则协调者向参与者发送abort请求，参与者根据日志回滚事务并释放事务资源，然后向协调者发送ack消息。
   3.3 如果参与者超时没能收到协调者的DoCommit请求，则参与者执行事务提交并释放事务资源。

　　三阶段提交通过设置超时解决了两阶段提交中的同步阻塞问题，通过增加事务询问阶段，提高了某个节点故障之后的数据仍然保持一致的概率，但仍存在某些情况下数据不一致的可能。

Basic-Paxos

原理

Paxos是一个算法簇，最早由Lamport于1990年提出，其核心原理是多数投票原则，即一项议案如果想要获得通过，则必须获得超过半数人的同意，因为任意两个多数派之间必然有重叠，所以其他人针对这项议案想要提交一个不同的值的时候是无法获得另一个多数派同意的，也就无法通过，从而保证了一个议案有且仅有一个一致的值。Lamport提出的Paxos算法的最初版本称为Basic-Paxos。

角色划分

该算法将议员的角色分为proposer, acceptor, learner三种，proposer提出议案，议案信息包括议案编号和提议值；acceptor接收议案，acceptor收到议案后可以接受（accept）议案，如果一个议案获得多数acceptor接受，则该议案被批准（chosen）；learner学习被批准的议案。每个议员可以身兼多职。

问题定义

1. 必须能形成决议（value）。决议只有在被proposer提出后才能被批准；未经批准的决议称为议案（proposal）
2. 在一次Paxos算法的执行实例中，只能批准（chosen）一个value；（但可以接受多个proposal，只要这些proposal具有同样的value)

算法-版本1

算法的执行分为两个阶段：

1. 准备阶段
   1.1 proposer创建一个议案，此时只包括议案编号n，然后向acceptors中的一个多数派发送prepare请求；
   1.2 acceptor收到prepare消息后，如果该议案的编号n大于它已经回复的所有prepare消息中的议案编号，则acceptor回复proposer可以接受，并承诺不再回复议案编号小于n的prepare请求；
2. 批准阶段
   2.1 当一个proposer收到了acceptors中一个多数派可以接受的回复后，就进入批准阶段。它要向回复可以接受的acceptors发送accept请求，包括编号n和提议值v。
   2.2 在不违背自己向其他proposer的承诺的前提下，acceptor收到accept请求后即接受这个请求，然后向proposer回复已接受应答。
   2.3 当proposer收到了acceptors中一个多数派已接受的回复后，该议案获得批准。

有没有问题

上面的算法有没有问题？
当然有问题，按照上面的算法，问题定义中的第2条无法得到满足，因为随着不断有人提出编号更大的议案，已经批准的议案的值在不断变化。
那么怎样保证已经批准（chosen）的议案值不会发生变化呢？
显然有两条路，要么我们约束acceptor，要求acceptor只能接受（accept）一个议案，不能多次接受编号不同的议案；要么我们约束proposer，如果没有已批准（chosen）的决议值（value），那么proposer可以提出任意值的议案；如果决议值（value）已批准（chosen），那么proposer只能提出值为已批准的决议值的议案。
先考察方案一，如果acceptor只能接受一个议案，那么可能无法形成任意一个多数派，因为每个议案的提出者都可能找到几个支持者，但这些支持者都不构成多数派，这样就违反了问题定义中的第1条。
再考察方案二，如果约束proposer提出议案的值，那proposer需要知道当前有没有已经批准的决议值，而这可以在收集prepare请求的应答后，判断有没有形成一个多数派来确定，即由acceptor应答prepare请求时告知proposer已接受（accept）的编号最大的议案的值，如果没有接受过任何议案，则回复null，这样proposer就知道回复应答的所有acceptor中有没有一个多数派已经接受了同一个议案值，如果有，那么proposer必须提出具有同样值的议案（proposal），如果没有，那么proposer可以提出具有任意值的议案（proposal）

算法-版本2

1. 准备阶段
   1.1 proposer创建一个议案，此时只包括议案编号n，然后向acceptors中的一个多数派发送prepare请求；
   1.2 acceptor收到prepare消息后，如果该议案的编号n大于它已经回复的所有prepare消息中的议案编号，则acceptor回复proposer自己已经接受（accept）的议案的值，并承诺不再回复议案编号小于等于n的prepare请求和议案编号小于n的accept请求；
2. 批准阶段
   2.1 当一个proposer收到了acceptors中一个多数派对prepare请求的回复后，就进入批准阶段。它要向回复prepare请求的acceptors发送accept请求，包括编号n和提议值v，如果proposer没有在acceptors的回复中发现具有同一个议案值得多数派，即没有已经批准（chosen）的决议值（value）时，proposer自行指定value；如果发现了已批准的决议值，则proposer的提议值必须等于决议值。
   2.2 在不违背自己向其他proposer的承诺的前提下，acceptor收到accept请求后即接受这个请求，然后向proposer回复已接受应答。
   2.3 当proposer收到了acceptors中一个多数派已接受的回复后，该议案获得批准。

场景分析

• 场景1：假设5副本ABCDE，3个副本ABC都accept了编号为1的提案，值为10，DE现在没有同步，这时D以编号2向CDE发请求，CDE应该回复D，其中C回复D已经accept过10这个值，DE应该回复NULL，这时D没有看到一个关于值10的一个多数派，因此D发起第二阶段请求，请问D能设置值为20吗？当然不能。
• 场景2：A向ABC发prepare请求，编号为1，ABC回复A，值为NULL，在A发起第二阶段请求之前，C向CDE发起prepare请求，编号为2，CDE也回复NULL，这时A发起第二阶段请求，值为10，AB都accept了，C没有，D这时候向CDE发起第二阶段请求，值为20，这时C挂了，D只收到了DE两个accept，这时连个议案都没有通过，过了一段时间C恢复了，以编号3发起向BCD发起prepare请求，B回复10，C回复NULL，D回复20，那C以哪个值作为第二阶段的提议值呢？实际上应该选择议案编号最大的值。
• 现在我们可以深入理解一下prepare阶段的意义了，prepare阶段不但是约束proposer不能乱取值，而且保证较旧的proposal无法被chosen。Paxos算法的阶段一和阶段二相辅相成，缺一不可。

算法-版本3（最终版）

1. 准备阶段
   1.1 proposer创建一个议案，此时只包括议案编号n，然后向acceptors中的一个多数派发送prepare请求；
   1.2 acceptor收到prepare消息后，如果该议案的编号n大于它已经回复的所有prepare消息中的议案编号，则acceptor回复proposer自己已经接受（accept）的id最大议案的id和值，并承诺不再回复议案编号小于等于n的prepare请求和议案编号小于n的accept请求；
2. 批准阶段
   2.1 当一个proposer收到了acceptors中一个多数派对prepare请求的回复后，就进入批准阶段。它要向回复prepare请求的acceptors发送accept请求，包括编号n和提议值v，如果proposer没有在acceptors的回复均为NULL，则proposer自行指定value；否则proposer的提议值必须等于id最大提案的值。
   2.2 在不违背自己向其他proposer的承诺的前提下，acceptor收到accept请求后即接受这个请求，然后向proposer回复已接受应答。
   2.3 当proposer收到了acceptors中一个多数派已接受的回复后，该议案获得批准。

优化

如果一个proposer发现已经有其他proposer提出了编号更高的议案，那这个proposer有必要中断这个过程，因此，在prepare过程中，如果一个acceptor发现了一个编号更高的议案，那这个acceptor在收到编号较小的prepare请求后，需要通知这个proposer中断这个议案。

有没有其他问题

上面的算法看起来可以满足问题定义，那还有没有其他问题？不幸的是，还有。Basic-Paxos在极端情况下会形成活锁，导致无法形成决议。具体来说，就是多个proposer交替提出编号递增的议案（proposal），每个议案在阶段2都不能批准，因为有新的编号更大的proposal刚好完成了阶段1。

Multi-Paxos, Raft, ZAB

Dynamo