文章目录

• 2PC
• 3PC
• Paxos
• • 基础流程
  • • 优化
• Raft
• ZAB
• • 消息广播
  • 崩溃恢复

2PC

2PC是Two-Phase Commit的缩写，二阶段提交。目前大多数SQL数据库都是采用的二阶段提交的策略完成事务，利用该协议可以非常方便的完成所有分布式事务参与者的协调，统一决定事务的提交和回滚。设计思路主要是保证在最后一个瞬间的网络是正常的就可以，尽可能将麻烦的过程前置。

• 阶段一：协调者让全部的参与者都完成准备，万事俱备，只欠东风。

1. 事务询问：协调者向所有的参与者发送事务内容，询问各个从节点是否可以执行事务的提交，并等到参与者的相应。
2. 执行事务：各参与者节点执行事务，并且将undo和Redo写入事务日志。
3. 反馈：如果参与者成功执行了事务，反馈给协调者yes，否则返回no。

• 阶段二：提交事务。东风，发令枪

提交事务：如果收到了全部参与者的反馈都是yes，执行事务的提交。协调者向全部的参与者节点发送Commit请求。参与者收到Commit以后提交事务，完成提交以后释放整个事务执行期间占用的事务资源，并且向协调者发送Ack消息。协调者收到全部的参与者的Ack以后，完成事务。

中断事务：收到了任何一个参与者的No，或者在等待超时以后没有收到全部参与者的yes，进行中断流程。 协调者向全部的参与节点发送Rollback请求，参与者收到rollback以后，利用Undo信息执行回滚，并释放资源，向协调者发送Ack。协调者收到全部的参与者的Ack以后，完成事务。

满足了强一致性，优点：原理简单，容易实现；缺点：存在同步阻塞，所有的参与者都被阻塞等待统一行动。存在单点问题，一旦协调者挂了，在阶段二中被卡死。脑裂问题，在发送了Commit以后如果因为局部网络异常崩溃，导致只有部分参与者收到了Commit，就会导致数据不一致。

3PC

三阶段提交，主要是对阶段二进行了拆分，形成了CanCommit，PreCommit，DoCommit三个阶段。

• CanCommit：协调者询问参与者是否可以执行事务提交操作，参与者予以反馈，并进入准备准备状态。
• PreCommit：如果全是yes，协调者发送PreCommit请求，进入Prepared阶段，参与者收到以后，执行事务，并且将Undo和Redo写入事务日志，返回Ack操作。如果收到了No或者等待超时，协调者发送abort指令，参与者结束事务。
• do Commit：协调者收到了全部的ack，进入Commit状态，发送do commit请求，参与者收到Commit以后提交事务，完成提交以后释放整个事务执行期间占用的事务资源，并且向协调者发送Ack消息。否则，发送abort指令，参与者执行回滚，返回ack。

需要注意的是，在进入阶段三以后，如果协调者出现问题或者网络出现问题，参与者在等待超期以后会继续事务的提交。

优点：降低了参与者的阻塞范围，且能够在单点故障以后达成一致。但是依然存在脑裂问题。

Paxos

具有高容错特性的一致性算法。分为接收者(Accepter)和提出者(Proposer)。一个接收者必须接受收到的第一个提案，接收者只认可接收到的最新的议案（即议案编号最新），当某个提案被一半以上接收者认可后，那么该议案成功。有一篇讲的还不错的文章，paxos详解

对于这个算法核心是提案的特点，如果编号为M，value值为V的提案 [M, V]被选定，那么所有比M0编号高，且被选中的提案必须也是V0。因此得到核心环节，提案生成。

基础流程

提案生成

1. prepare请求：Proposer选择一个新的提案编号Mn，然后向超过一半acceptor的acceptor集合发送请求，要求该集合中的acceptor做出如下回应：
   • 不能再批准任何编号小于Mn的提案
   • 若果acceptor已经批准过任何提案，那向proposer反馈已批准过得提案中编号小于Mn但是最大编号的提案的值V
2. 如果proposer收到了半数以上的acceptor的响应结果，则它可以产生编号为Mn，值为Vn的提案，这里的Vn是指的所有响应中编号最大的提案的值。若半数以上的acceptor未批准过任何的提案，则Vn的值由Proposer任意选择

在提案确定之后，proposer会向acceptor集合再次发送该提案，称此请求为accept请求

批准阶段

Acceptor会收到来自proposer的两种请求：

• Prepare请求：Acceptor可以在任何时候响应一个prepare请求;
• Accept请求： 若acceptor为响应过任何编号大于Mn的请求，那么它就可以接受这个编号为Mn的请求。

每个proposer可以任意时刻抛弃提案，因此accepter最好可以进行回应，以便及时丢弃。同时考虑到系统的活性问题，比如proposer不断地提出一系列单增提案，会导致死循环。因此一般选择一个主Proposer提出提案。

优点：解决了无限等待和脑裂问题。

优化

当某个副本节点被升级为Master以后，使用新的N编号广播一个prepare消息，每个未达成一致地Instance将各自最后接受的提案值打包，并且作为promise返回。master对这些未决的Instance执行propose和accept。除非master发现了一个更大的reject，说明集群中由另一个master在进行prepare，需要重新prepare->promise。

Raft

这个算法在redis的集群策略中被使用了。我觉着是一个很有意思的算法。

主要是集群选择master的过程，正常情况下，master和slave之间存在心跳机制。如果slave在一定的时间内无法收到心跳，进入主观下线判断，这时候给其他的slave发送咨询，如果收到过半的主管下线反馈，认为客观下线自己会成为candidate，然后发送投票。这时其他节点需要对这个请求进行反馈，对于每一个纪元，每个节点只会给收到的第一个请求进行投票，其余的都静默。当一个节点收到半数以上投票时候，升级为主节点。和其余的节点重新建立心跳机制。

ZAB

主要是被ZooKeeper使用，成为ZAB原子消息广播协议。ZooKeeper只允许唯一的一个Leader进行事务请求的处理。ZAB协议包括两个部分，崩溃回复和消息广播，前者用于选择leader服务器，后者用于leader服务器的消息同步。

消息广播

消息广播的过程类似于二阶段提交的过程，但是删除了中断逻辑。所有的follower服务器要不正常反馈leader提出事务，要不抛弃leader。因此，我们可以在leader收到过半ack响应以后就开始提交事务。但是这会导致leader崩溃退出引发的不一致性，这就需要崩溃恢复模式来解决这个问题。并且广播是基于FIFO特性的TCP协议进行网络通信的，很容易保证消息接收与发送的顺序性。在事务广播前，leader会为事务指派一个全局单调递增唯一ID，称为事务ID。因为ZAB协议保证每一个消息严格的因果关系，因此需要按照ZXID进行排序和处理。具体的就是，leader和每个follower直接分配了一个单独的队列，保证顺序的正确性。follower在接受到事务以后，先以事务日志的形式落盘，然后返回ack。

崩溃恢复

ZAB协议需要保证在leader服务器上提交的事务最终要被所有的服务器执行提交；保证丢弃那些旨在leader服务器上被提出的事务。

如果从集群中选举出来的机器具有最大的ZXID编号的话，可以保证这个新选举出来的leader具有所有已经提交的提案（因为这个任务一定是被提交的，且不会是master的一厢情愿），并且省去了检查提交和丢弃的工作。在完成选举以后，leader服务会首先确认事务日志中所有的proposal是不是都已经被集群中过半的机器提交了。leader每一个follower都准备一个队列，将没有被这些follower提交的事务进行同步。

具体的，这里巧妙使用了64位的ZXID，高32位是epoch编号，低32位是递增的事务。当新的leader产生时候，解析出epoch并加一，后32位置为0。保证不发生混乱。