2PC（两阶段提交）
- 角色
- 协调者
- 参与者
- 过程
- 事务准备请求
- 协调者发送prepare消息给所有参与者，参与者执行事务（但不提交），写入undo/redo日志，并且投票反馈yes/no。
- 事务提交/回滚
- 若所有参与者反馈yes，协调者会发送commit消息，参与者收到后提交事务，并且向协调者反馈Ack消息。
- 若有参与者反馈no或者由于超时协调未收到响应时，协调者会发送abort消息，参与者收到后会执行回滚，并释放事务期间持有的资源和锁。
- 完成事务
- 协调者接收到所有参与者反馈的Ack消息后，完成事务。
- 缺点 两阶段提交协议的最大缺点是它是一种阻塞协议。在参与者向协调者反馈消息后，它将一直阻塞，占用相关资源和锁，直到收到提交或回滚。如果协调者永久失败，参与者可能会一致被阻塞。
无法解决这样的场景：协调者在发出commit消息之后宕机，而唯一接收到这条消息（并提交了事务）的参与者同时也宕机了（没有参与者或两个以上参与者接收到commit消息，不存在该问题）。那么即使协调者通过选举协议产生了新的协调者，这条事务的状态也是不确定的，新的协调者决定事务是否可以提交时必须要询问所有参与者（在宕机的参与者恢复前无法确定）有没有接收到commit消息，只要有一个参与者接收到commit消息，即可认为事务可以提交。
3PC（三阶段提交）
- 过程
- canCommit
- 协调者询问是否可以提交，并且投票反馈yes/no，该阶段相当于2PC的第一阶段。
- preCommit 预提交
- 若所有参与者针对canCommit询问反馈yes，协调者发送preCommit消息。参与者收到preCommit消息后后执行事务（但不提交），写入undo/redo日志，并向协调者反馈Ack消息。
- 若有参与者针对canCommit反馈no或者由于超时协调者未收到响应时，协调者会发送abort消息。
- 该阶段相对于2PC为新增阶段，目的是为了消除参与者已经反馈Ack消息并且等待协调者的commit/abort消息时所处的“不确定状态”（参与者无法知晓到底要提交或中止）所产生的长期等待的问题。
- 若参与者收到preCommit消息，可以确定所有参与者都在canCommit阶段都投票反馈可以提交，也可以在很大程度上确认后续可以执行真正的提交（不排除其他参与者收到preCommit后反馈no的情况），所以即使收不到协调者的commit消息，参与者也可以自主提交。
- doCommit 真正提交
- 协调者收到所有参与者ack后发送commit消息，参与者收到commit消息或者等待commit/abort消息超时后提交事务。
- 任何一个参与者针对preCommit消息反馈了no，或者协调者等待超时无法获取所有参与者响应即发送abort消息，参与者收到abort后会进行事务中断。
- 优点
- 非阻塞
- 参与者也引入超时机制，doCommit阶段由于协调者宕机参与者未及时接受到请求时，仍会进行事务提交。
- 处理协调者故障
- 如果协调器在发送preCommit后但在doCommit前发生故障： 参与者超时后并自行决定提交，他们可以安全地假定所有其他参与者也收到了preCommit 。
- 如果协调器在发送 preCommit前发生故障： 参与者超时后并安全地中止事务。
- 解决上述2PC缺点2
- 选举出新的协调者后，查询所有存活的参与者，如果得知某些节点处于preCommit状态（曾收到过preCommit消息），那么可认为协调者在崩溃之前已经做出了提交的决定。因此它可以带领参与者进行事务提交。类似地，如果参与者说它没有到达preCommit状态（未收到preCommit消息），那么新的协调者甚至可以假设前一个协调者在完成preCommit阶段之前就已经失败了。因此，它可以安全地假设没有参与者提交更改，从而安全地中止事务。
- 缺点
- 数据不一致问题
- doCommit阶段部分参与者针对preCommit消息反馈了no（属于小概率事件，因为canCommit阶段所有参与者都反馈了yes），协调者向所有参与者发送abort消息，但是此时若出现网络分区，某个参与者由于接受不到协调者的abort消息仍然会进行提交，其他参与者接收到了abort消息进行了回滚，，从而导致发生分区的参与者与其他参与者状态的不一致，并且无法恢复。
- 需要至少三次网络往返，即至少3次RTT，对于完成事务是个比较长的延迟。
PAXOS
- 角色
- Proposer：提案的发起者
- Acceptor：参与对提案的投票
- Learner：不参与提案和投票，只被动接收提案结果
- 阶段
- Prepare阶段
- Proposer选择一个提案编号N，然后向半数以上的Acceptor发送编号为N的Prepare请求。
- Acceptor收到编号为N的Prepare请求后
- 若N大于该Acceptor已经响应过的所有Prepare请求的编号，那么它就会将它已经接受过的编号最大的提案（如果有的话） 作为响应反馈给Proposer，同时该Acceptor承诺不再接受任何编号小于N的提案。
- 否则，拒绝这个Prepare请求。
- Accept阶段
- 如果Proposer收到半数以上Acceptor对其发出的编号为N的Prepare请求的响应，那么它就会发送一个针对[N,V]提案的Accept请求给半数以上的Acceptor（和之前的半数以上Acceptor集合不一定相同）。注意：V就是收到的响应中编号最大的提案的value，如果响应中不包含任何提案，那么V就由Proposer自己决定。
- Acceptor收到编号为N的提案的Accept请求后
- 若该Acceptor没有承诺过不接收编号小于M（N < M ) 的提案，它就接受该提案。
- 否则，就拒绝该提案。
- Learn阶段
- 一旦大多数Acceptor都接受了提案[N,V]（即使在Accept阶段存在拒绝），那么就认为该提案被选定，同时同步Learner所选的提案。
- 要求
- 活性：值最终被选中
- 安全性：只有一个值被选中
- 优化
- 选择主proposer解决活性问题
- 选择主learner（若干）使通信简单化
ZAB
- 角色
- leader
- follower
- observer
- 阶段
- discovery：准leader与quorum通信发现其中的最大epoch，然后epoch+1，发送消息给这些follower，follower更新自己的处理过的的最大事务epoch，follower反馈历史事务集合和当前最大epoch。
- synchronization：发现阶段获取的最大epoch和最新提议历史去同步quorum，若follower发现自己处理过的最大epoch不等于最大epoch则不执行事务操作，若过半follower正确反馈后，leader向follower发送commit请求broadcast：leader对外提供服务，简化版的二阶段提交，遵循过半原则，收到过半ack后，发送commit消息。
- java实现
- Fast Leader Election：选取半数以上同意的(zxid,sid)最大的
- Recovery Phase：包括discovery和synchronization阶段
- Broadcast Phase
FAQ
- zab 与 paxos的区别？
- zab为分布式主备系统而设计、paxos为分布式一致性状态机系统而设计
- 关于状态更新的协议（对于主备系统）需要比客户端请求（针对状态机复制系统）的协议更严格的顺序保证
- zab leader/follower接受到proposal直接写入事务日志，等待过半follower反馈ack后发送commit消息；paxos master（即proposer）接收到大多数accept反
- ack选定提案后才写入事务日志，并广播commit消息，acceptor接受commit后才写入事务日志
- zab存在一个崩溃恢复阶段
- zab为什么同步阶段只需同步quorum就够了？
事务操作都是类似二阶段提交的过程，遵循多数派原则
- zab顺序性如何保证？
客户端和zk服务器之间采用tcp长连接，利用其FIFO的特性，对于客户端请求先到先执行，leader和follower之间也采用TCP长连接，保证follower接收事务顺序性。
- paxos为什么无法保证顺序性？
proposer提出的第一个提案prepare阶段完成还未被选定（没有commit），接着提出第二个提案覆盖了第一个提案的prepare，被选定进而广播commit消息给acceptor,后面proposer可能还再次提出未达成一致的第一个提案，及时被选中，也无法与提出提案的顺序相一致。要想保证顺序性proposer必须等上一个提议commit后才能发出，但是这样性能极低。
- zxid设计的作用
- Fast Leader Election 比较zxid
- learner与leader数据同步时会进行zxid对比
- zab同步阶段部分follower由于一些原因未正常处理commit请求，如何保证同步结果？
在leader对外提供服务之前会检查事务日志是否完成数据同步，即是否所有proposal已被过半机器提交