Paxos 和 ZAB

Paxos

多个Acceptor，多个Proposer。

提案

[M, V] 由编号M 和值 V 组成

Acceptor 规则

1. 接受收到的第一个提案
2. 如果收到的提案的编号比已接受的提案编号大，则接受新的提案

算法描述

Prepare阶段

1. Proposer 生成提案编号 Mn, 向Quorum 广播该编号。
2. Acceptor 收到Prepare Mn 之后
   1. 如果比已接受提案编号大，则接受Mn, 并承诺不再接受小于Mn 的提案，将已接收的编号最大提案通过返回ACK 给Proposer。
   2. 否则忽略Prepare Mn
3. Proposer 收到Quorum 数量的ACK 之后，则进入提交阶段。否则重新开始Prepare 阶段。

Accept阶段

1. Proposer 选取ACK 中编号最大的提案的Value 作为Vn, 向Quorum 广播 Accept [Mn, Vn]。
2. Acceptor 收到Accept [Mn, Vn] 之后
   1. 若提案不违背承诺，则接受该提案，并返回ACK
   2. 否则忽略

Multi-Paxos

由于多个Proposer 同时提交提提案会竞争编号导致效率太低。

所以可以把提交提案的工作交给一个Leader Proposer。

由于Paxos并不限制Proposer 数量，该Leader 也不需要严格保证单一。所以可以由简单的心跳/租约机制来产生Leader。

ZAB

多个Follower。单个Leader，所有Proposal由leader发起，保证事务提交的顺序。

提交

类似二阶提交

1. Leader 向多个Follower 提交提案
2. Follower 收到后，如果可以执行则返回ACK
3. Leader 收到超过半数的ACk, 则发送 COMMIT 消息给follower, follower 执行提案。本次提交成功。

Leader选举

1. 每个参与者广播自己的选票 vote[zxid, sid, electionEpoch]。
2. 收到其他参与者的选票 vote[zxid', sid', electionEpoch']
   1. 如果 electionEpoch' < electionEpoch, 忽略
   2. electionEpoch' > electionEpoch, 更新electionEpoch 进入下一轮选举
   3. zxid' > zxid, 则更新 sid := sid', zxid相等比较 sid' > sid, 则更新sid := sid'。投出更新的选票
3. 某个参与者发现自己获得了超过半数的选票，且经过短暂等待，没有其他Leader 产生，则自己变成Leader

Leader同步

由于上述选举过程保证了 Leader 必然拥有最大zxid, Leader 只需要向Follower 同步自己的历史提案即可。

1. 若Follower 拥有 Leader 没有的提案，则 truncat掉。
2. 若落后则根据log, reply 历史transcation
3. 若落后太多，则直接同步 snapshot，再replay transaction log.

附2PC 与 3PC

2PC

1. 发起者向所有参与者提交事务。参与者执行并记录Undo log，返回ACK
2. 发起者收到所有的ACK后，发送COMMIT, 参与者释放资源。
   2.1 否则发送ABORT, 参与者undo 事务。

缺点

1. 同步阻塞，收到事务后需要阻塞直到事务完成或取消
2. 单点，发起者单点
3. 脑裂，部分节点可能没收到部分请求导致数据不一致。

3PC

1. 先发送 canCommit 询问是否能执行事务。
2. 可以则发出 preCommit，参与者执行事务，记录Undo log, 返回ACK
3. 发起者收到所有ACK，发送COMMIT, 参与者释放资源。
   3.1 否则发送ABORT，参与者undo 事务。

如果参与者收到preCommit 后，超时未收到COMMIT 或 ABORT, 则继续执行事务。

优于2PC

1. 阻塞范围变小。
2. 在某些故障下，可以继续执行。