一致性协议算法

2PC - 二阶段提交算法

---

节点分为协调者和参与者，执行分为提交事务请求阶段、提交事务执行阶段（投票、执行）。

1. 阶段1：
协调者发送一个事务询问给参与者，询问参与者是否接受。参与者执行事务操作，将undo和redo信息写入事务日志，然后向协调者回复yes或者no响应。

2. 阶段2：
   协调者根据参与者反馈，提交或者中止当前事务，如果参与者全都yes，那么就提交执行该事务。但是只要有一个参与者回复no或者等待超时，那么参与者中断当前事务。然后向所有参与者节点发送rollback请求，利用undo信息来执行事务回滚操作，然后释放资源，向协调者发送ACK请求。

2PC缺陷：

• 同步阻塞：参与该事务的逻辑，在事务处理期间都将是阻塞的。
• 太过保守：一个节点出现一点问题，那么整个所有的节点都需要回滚（缺乏容错机制）。
• 单点问题：2PC的整个流程过于依赖协调者，如果协调者第二阶段发生了问题，那么当前事务相关的所有参与者都将处于阻塞状态，无法完成事务操作。
• 脑裂问题：可能由于网络原因，网络不好的节点没有进行事务处理，而网络正常的节点进行了事务处理，造成了数据不一致。

3PC - 三阶段提交算法

---

3PC是2PC的改进版，将请求提交的过程一分为二。

1. 阶段1：CanCommit
   事务询问：协调者向参与者发送一个CanCommit事务请求，询问是否可以执行事务提交操作，开始等待参与者的响应。
   参与者向协调者反馈事务询问响应：参与者根据自身情况，反馈YES响应，进入预备状态，否则返回NO响应。
2. 阶段2：PreCommit
   返回yes情况：
   协调者向所有参与者发送PreCommit请求，进入准备阶段。
   参与者收到PreCommit请求后，执行事务操作，将undo和redo信息记录到日志中。
   各参与者向协调者反馈事务执行响应：成功响应ACK，同时等待最终指令：提交还是终止。
   返回no情况（中断事务）：
   任一参与者向协调者反馈了NO响应或者等待超时之后，协调者无法接收到所有参与者反馈响应，那么中断事务。
   发送中断请求（abort请求）。
   参与者收到协调者abort请求或者等待协调者请求超时，参与者中断事务。
3. 阶段3：DoCommit
   同步处理：
   发送提交请求：协调者正常工作状态，接收到来自所有参与者的ACK响应，那么它将从预提交状态转换为提交状态，向所有参与者发送DoCommit请求。
   事务提交：参与者收到DoCommit请求后，会正式执行事务提交操作，完成提交后，释放事务资源。
   反馈事务提交结果：参与者完成事务提交之后，向协调者发送ACK消息。
   完成事务：协调者收到所有参与者反馈的ACK消息后，完成事务。
   回滚处理：
   发送中断请求：协调者向所有参与者发送abort请求。
   事务回滚：参与者收到abort请求后，利用 阶段2中的undo日志来执行事务回滚操作，完成回滚，释放资源。
   反馈事务回滚结果：参与者完成了事务回滚后，向协调者发送ACK消息。
   协调者收到所有参与者反馈的ACK消息后，中断事务。

3PC优缺点：

• 优点：减小了阶段阻塞的范围。
• 缺点：当第二阶段PreCommit成功之后，第三阶段协调者向参与者发送DoCommit之后，然后参与者同步，但是如果同步之后，参与者与协调者断开了。那么协调者一直收不到参与者回复，那么就超时。协调者开始发送Abort回滚操作，其他参与者都回滚了，而断开的参与者没有回滚，造成了服务器节点之间数据不一致。

Paxos算法

---

• Proposer：提案者，可能有多个，它门负责提出提案。
• Acceptor：接受者，一定要有多个，它们对指定提案进行表决，同意则接受提案，不同意则拒绝。
• Learner：学习者，收集每位Acceptor接受的提案，并根据少数服从多数的原则，形成最终提案。
  

  算法描述：

1. 阶段1 - prepare阶段：

• Proposer提案者：
  选取提案编号M，向某个超过半数的子集成员的Acceptor发送编号为M的Prepare请求。
• Acceptor接受者：
  如果Acceptor收到的编号M的Prepare请求并且编号M比Acceptor已经接收的编号都大，则向Proposer承诺不再接收小于M的编号提案了。
  如果之前也接收了一些提案，那么会将已接受的提案中编号最大的提案及编号N发给Proposer（N < M，当前M编号还没接收，不算已接收的编号）。
  如果收到的提案编号M小于Acceptor之前已经接收的提案编号的最大值，那么拒绝接收。

2. 阶段2 - accept阶段：

• Proposer提案者：
  如果发送的反馈结果为拒绝接收，那么就不处理了。
  如果返送的反馈结果为同意接收，那么记录提案和编号。
  如果超过半数的Acceptor同意，Acceptor已经接受的提案中选取提案编号N最大的提案作为自己的提案，没有的话就是任意值，发送Propose请求，提案为[N，S]。
  注意S的值就是收到的响应中最大编号提案值，如果响应中不包含任何提案，S就是任意值。
• Acceptor接受者：
  Acceptor针对收到[N，S]提案Propose请求，Prepare阶段收到的M大于Acceptor自己当前最大提案编号N，通过该提案，返回Proposer一个Aceept请求，双方都更新了当前最大编号的提案，达成共识。

3. 阶段3 - learn阶段：
   Proposer收到超过半数Acceptors的Accept之后，标志本地Accept阶段已成功，形成决议，将形成的决议发给所有的Learners。

参考

---

《从Paxos到Zookeeper分布式一致性原理与实践》
https://zhuanlan.zhihu.com/p/31780743