2PC

即Two-phase Commit，参与者将操作成败通知协调者，再由协调者根据所有参与者的反馈情报决定各参与者是否要提交操作还是中止操作。

第一阶段(提交请求阶段)

1. 协调者节点向所有参与者节点询问是否可以执行提交操作，并开始等待各参与者节点的响应。
2. 参与者将锁定资源，节点执行询问发起为止的所有事务操作，并将Undo信息和Redo信息写入日志。
3. 各参与者节点响应协调者节点发起的询问。如果参与者节点的事务操作实际执行成功，则它返回一个"同意"消息；如果参与者节点的事务操作实际执行失败，则它返回一个"中止"消息。

第二阶段(提交执行阶段)

成功

当协调者节点从所有参与者节点获得的相应消息都为"同意"时：

1. 协调者节点向所有参与者节点发出"正式提交"的请求。
2. 参与者节点正式完成操作，并释放在整个事务期间内占用的资源。
3. 参与者节点向协调者节点发送"完成"消息。
4. 协调者节点收到所有参与者节点反馈的"完成"消息后，完成事务。

失败

如果任一参与者节点在第一阶段返回的响应消息为"终止"，或者 协调者节点在第一阶段的询问超时之前无法获取所有参与者节点的响应消息时：

1. 协调者节点向所有参与者节点发出"回滚操作"的请求。
2. 参与者节点利用之前写入的Undo信息执行回滚，并释放在整个事务期间内占用的资源。
3. 参与者节点向协调者节点发送"回滚完成"消息。
4. 协调者节点收到所有参与者节点反馈的"回滚完成"消息后，取消事务。

存在的问题

1. 阻塞问题。当有部分参与者宕机或者与协调者网络通信故障，那么正常回应的参与者将进入阻塞状态，无法对锁定的资源进行任何操作，只有等待超时中断事务，极大的限制了系统的性能。
2. 单点问题。2PC完全依赖协调者的正常工作，一旦协调者出现问题，那么整个协议将瘫痪，如果协调者在阶段二中出现问题的话，那么其他参与者将会一直处于锁定事务资源的状态中。
3. 参与者直到接受到doCommit请求才知道协调者决定。假设在阶段2协调者与第一个参与者A在通信后双双宕机，那么剩下的机器即使重新选择协调者后，新的协调者无论是允许还是拒绝执行，那么都有可能与A机器的数据不一致。

3PC

      3PC是2PC的改进版本，将2PC的第一阶段：提交事务阶段一分为二，形成CanCommit、PreCommit和doCommit三个阶段组成的事务处理协议。

      3PC为了解决问题3参与者直到接受到doCommit请求才知道协调者决定而加入了canCommit阶段。这样即使出现了3问题，剩下的参与者也知道此次事务要提交，因为经过前两阶段的询问，无论是参与者还是协调者都已知道此次事物是要提交的。

     为了解决单点问题和阻塞问题，3PC在参与者这边也引入了超时机制。在阶段一和阶段二无论协调者还是参与者故障，那么在等待超时后，将拒绝此次事务，故障机器在恢复后，也会拒绝此次事务。在阶段三一旦参与者无法及时收到来自协调者的信息之后，他会默认执行commit，而不会一直持有事务资源并处于阻塞状态，而等到故障机器恢复，也会对事务进行提交从而达到数据的一致性。

     很多博客说3PC为了解决阻塞问题加入了canCommit阶段，说canCommit阶段没有锁定资源，降低了持有资源的时间。我认为canCommit阶段还是持有了资源的，因为阶段二只是告知各参与者协调者所做的决定，而且阶段三的超时自动提交依赖的是一阶段参与者对事务的保证。

存在的问题

1. 虽然3PC解决了大多数场景的一致性问题，但是少数场景还是会出现数据不一致的情况。比如在发送preCommit中协调者故障，那么收到参与者在收到请求后将进入阶段三，而剩下的参与者还在阶段二，根据超时机制将产生数据的不一致。
2. 3PC在要进行3轮通信，可想而知一轮事务的决策将是漫长的，对系统的负载也要求极高。

paxos

      了解了2PC和3PC之后，我们可以发现，无论是二阶段提交还是三阶段提交都无法彻底解决分布式的一致性问题。Google Chubby的作者Mike Burrows说过， there is only one consensus protocol, and that’s Paxos” – all other approaches are just broken versions of Paxos. 意即世上只有一种一致性算法，那就是Paxos。

     首先将一次决议角色分为proposers，acceptors，和learners（允许身兼数职）。proposers提出提案，提案信息包括提案编号和提议的value；acceptor收到提案后可以接受（accept）提案，若提案获得多数acceptors的接受，则称该提案被批准（chosen）；learners只能“学习”被批准的提案。

      然后一致性要满足安全性和活性 ：

• 安全性：只有被提出的提案才能被选定；只能有一个值被选定；如果某个proposer认为提案被选定 ，那么这个提案必须是真的被选定
• 活性：一次决议总有提案被选定 

      那现在我们有P1,P2,P3三个进程，要通过一个关于V的决议，显而易见我们得到一个约束：

      P1 acceptor必须接受它第一个收到的提案 

     那么我们就有这样一个场景，P1决定令V=1，P2决定令V=2，P3决定令V=3，这种场景下acceptors无法形成多数派，所以我们需要新的约束。因为进程都是平等的，所以不能对进程进行约束，比如说拒绝某个进程的提案，不让某个进程提出提案，所以我们转而提案进行增强。考虑维护一个全局的递增序列对提案进行编号(P_ID)，这样P1,P2,P3就有足够的凭证进行裁决，不妨假设接受大的P_ID。假设P3的P_ID最大，那么一定时间后，三个进程中V的值将等于3,但是在这一定时间中的某段时间，V的值将被决定为2（P2的提案提前于P3的提案到达P1),这违反了一致性的安全性。那么怎么让P1拒绝P2或者P3的提案呢，P1在接受到P2的提案之前并没有接受到任何消息，P2的提案到达时也只知道自己接受了P2的提案。对acceptor已经没有更强的约束了，所以我们转而对proposer进行约束。既然只能选定一个值，那么我们要求proposer提出提案选值的时候必须是存活acceptors中的批准的P_ID最大的提案值。

      P2 proposer提出提案选值的时候必须是回复acceptors中的接受的P_ID最大的提案值

     当然我们来看看完全体的算法是怎么描述的

阶段一

1. Proposer选择一个提案编号M，然后向超过半数的Acceptor发送编号为M的prepare请求。
2. 如果一个Acceptor收到一个编号为M的prepare请求，且编号M大于该Acceptor已经响应过的所有prepare请求的编号，那么他会将他已经批准过的最大编号的提案作为响应反馈给Proposer，同时承诺不会再批准任何编号小于M的提案。

阶段二

1. 如果Proposer收到半数以上的Acceptor对于其发出的编号为M的prepare请求的响应，那么他会发送一个编号为M值为V的Accept请求给Acceptor。V的值就是收到的响应中最大的提案的值，如果响应不包含任何提案，那么V可以是任意值。
2. 如果Acceptor收到编号为M的提案的Accept请求，只要改Acceptor尚未对编号大于M的prepare请求做出响应，他就可以通过这个提案。 

     那么如同2PC/3PC 中的协调者和部分参与者doCommit而导致的数据一致性问题解决了吗？

     我们假设有五个进程ABCDE，某时刻A提出提案P1令V=1，并对BC发送了prepare请求，BC收到prepare请求回复给了A，A对B发送的V=1的accept请求后终止，B在接受到Accept请求后也终止了。此时E深感自己责任重大，提出V=2的提案P2并发送prepare请求给CD，当C在接受到P2的preapre后，将回复P1{V=1}给E，E在收到C的响应后根据协议只能含泪把值改为1在发送Accept请求。

     这样看来好像是只要先有提案提出，那么以后提案的值都是第一次提案的值，这样好像也满足了安全性和活性。但是根据Paxos算法，也没有明确要求提案的值不能变。那么被决定之前提案的值能不能变呢？有这样一个场景，还是有五个进程ABCDE，某时刻A提出提案P1令V=1，并对BC发送了prepare请求，但是可怜的C在还未收到prepare请求时挂掉了，当然A也没收到多数派的响应，自然不会发送accept请求。而后C又成功上线，E命运使然的提出V=2的提案P2并发送prepare请求给CD，然后得到了CD的接受形成了自己的多数派使得P2被批准，但是如果E发送prepare请求给含有A或B的多数派那结果将完全不同。而无论哪种情况度没有违反活性和安全性的要求，paxos的作用也仅仅是确定一个值且在分布式系统保持一致性，至于你想说的是我的值可以进行多次改写啊，那就要将paxos和状态机联系起来。

ZAB

      paxos通过多数派和限制提案的值完美的解决了我们的问题，但是理论到实际是个艰难的过程。比如怎样在分布式环境下维持一个全局唯一递增的序列，如果是靠数据库的自增主键，那么整个系统的稳定和性能的瓶颈全都集中于这个单点。paxos算法也没有限制Proposer的个数，Proposer个数越多，那么达成一致所造成的碰撞将越多，甚至产生活锁，如果限制Proposer的个数为一个，那么就要考虑唯一的Proposer崩溃要怎么处理。paxos只是确定了一个值，离我们实际运用想要多次读写还有距离，上文也说过想要多次读写，要将paxos和状态机联系起来。

     ZAB协议分为2个部分，让我们来看看ZAB协议是怎么解决这些问题的:

     (以下内容来源于http://www.jianshu.com/p/fb527a64deee）

• 广播（boardcast）：Zab 协议中，所有的写请求都由 leader 来处理。正常工作状态下，leader 接收请求并通过广播协议来处理。

• 恢复（recovery）：当服务初次启动，或者 leader 节点挂了，系统就会进入恢复模式，直到选出了有合法数量 follower 的新 leader，然后新 leader 负责将整个系统同步到最新状态

广播（boardcast）

广播的过程实际上是一个简化的二阶段提交过程：

1. Leader 接收到消息请求后，将消息赋予一个全局唯一的 64 位自增 id，叫做：zxid，通过 zxid 的大小比较即可实现因果有序这一特性。
2. Leader 通过先进先出队列（通过 TCP 协议来实现，以此实现了全局有序这一特性）将带有 zxid 的消息作为一个提案（proposal）分发给所有 follower。
3. 当 follower 接收到 proposal，先将 proposal 写到硬盘，写硬盘成功后再向 leader 回一个 ACK。
4. 当 leader 接收到合法数量的 ACKs 后，leader 就向所有 follower 发送 COMMIT 命令，同事会在本地执行该消息。
5. 当 follower 收到消息的 COMMIT 命令时，就会执行该消息 

      相比于完整的二阶段提交，Zab 协议最大的区别就是不能终止事务，follower 要么回 ACK 给 leader，要么抛弃 leader，在某一时刻，leader 的状态与 follower 的状态很可能不一致，因此它不能处理 leader 挂掉的情况，所以 Zab 协议引入了恢复模式来处理这一问题。从另一角度看，正因为 Zab 的广播过程不需要终止事务，也就是说不需要所有 follower 都返回 ACK 才能进行 COMMIT，而是只需要合法数量（2f+1 台服务器中的 f+1 台） 的follower，也提升了整体的性能。

恢复（recovery）

     由于之前讲的 Zab 协议的广播部分不能处理 leader 挂掉的情况，Zab 协议引入了恢复模式来处理这一问题。为了使 leader 挂了后系统能正常工作，需要解决以下两个问题：

• 已经被处理的消息不能丢
• 被丢弃的消息不能再次出现

已经被处理的消息不能丢

      这一情况会出现在以下场景：当 leader 收到合法数量 follower 的 ACKs 后，就向各个 follower 广播 COMMIT 命令，同时也会在本地执行 COMMIT 并向连接的客户端返回「成功」。但是如果在各个 follower 在收到 COMMIT 命令前 leader 就挂了，导致剩下的服务器并没有执行都这条消息。

      为了实现已经被处理的消息不能丢这个目的，Zab 的恢复模式使用了以下的策略：

1. 选举拥有 proposal 最大值（即 zxid 最大） 的节点作为新的 leader：由于所有提案被 COMMIT 之前必须有合法数量的 follower ACK，即必须有合法数量的服务器的事务日志上有该提案的 proposal，因此，只要有合法数量的节点正常工作，就必然有一个节点保存了所有被 COMMIT 消息的 proposal 状态。
2. 新的 leader 将自己事务日志中 proposal 但未 COMMIT 的消息处理。
3. 新的 leader 与 follower 建立先进先出的队列， 先将自身有而 follower 没有的 proposal 发送给 follower，再将这些 proposal 的 COMMIT 命令发送给 follower，以保证所有的 follower 都保存了所有的 proposal、所有的 follower 都处理了所有的消息。
   通过以上策略，能保证已经被处理的消息不会丢

被丢弃的消息不能再次出现

       这一情况会出现在以下场景：当 leader 接收到消息请求生成 proposal 后就挂了，其他 follower 并没有收到此 proposal，因此经过恢复模式重新选了 leader 后，这条消息是被跳过的。 此时，之前挂了的 leader 重新启动并注册成了 follower，他保留了被跳过消息的 proposal 状态，与整个系统的状态是不一致的，需要将其删除。
       Zab 通过巧妙的设计 zxid 来实现这一目的。一个 zxid 是64位，高 32 是纪元（epoch）编号，每经过一次 leader 选举产生一个新的 leader，新 leader 会将 epoch 号 +1。低 32 位是消息计数器，每接收到一条消息这个值 +1，新 leader 选举后这个值重置为 0。这样设计的好处是旧的 leader 挂了后重启，它不会被选举为 leader，因为此时它的 zxid 肯定小于当前的新 leader。当旧的 leader 作为 follower 接入新的 leader 后，新的 leader 会让它将所有的拥有旧的 epoch 号的未被 COMMIT 的 proposal 清除。