分布式理论系列（二）一致性算法：2PC 到 3PC 到 Paxos 到 Raft 到 Zab

本文介绍一致性算法: 2PC 到 3PC 到 Paxos 到 Raft 到 Zab

两类一致性算法(操作原子性与副本一致性)

• 2PC 3PC 协议用于保证属于多个数据分片上的操作的原子性。这些数据分片可能分布在不同的服务器上，2PC 协议保证多台服务器上的操作要么全部成功，要么全部失败。

• Paxos Raft Zab 协议用于保证同一个数据分片的多个副本之间的数据一致性。当这些副本分布到不同的数据中心时，这个需求尤其强烈。

一、2PC（阻塞、数据不一致问题、单点问题）

Two-Phase Commit(两阶段提交) 是计算机网络尤其是在数据库领域内，为了使基于分布式系统架构下的所有节点在进行事务处理过程中能够保持原子性和致性而设计的一种算法。通常，二阶段提交协议也被认为是一种一致性协议，用来保证分布式系统数据的一致性。绝大部分的关系型数据库都是采用二阶段提交协议来完成分布式事务处理。

1.1 协议介绍

第一阶段：提交事务请求（投票阶段）

1. 事务询问

   协调者向所有的参与者发送事务内容，询问是否可以执行事务提交操作，并开始等待各参与者的响应。

2. 执行事务

   各参与者节点执行事务操作，并将 Undo 和 Redo 信息计入事务日志中。

3. 各参与者向协调者反馈事务询问的响应

   如果参与者成功执行了事务操作，那么就反馈给协调者 Yes 响应，表示事务可以执行；如果参与者没有成功执行事务，那么就反馈给协调者 No 响应，表示事务不可以执行。

第二阶段：执行事务提交（执行阶段）

（1）执行事务提交

如果所有参与者的反馈都是 Yes 响应，那么

1. 发送提交请求

   协调者向所有参与者节点发出Commit请求

2. 事务提交

   参与者接收到Commit请求后，会正式执行事务提交操作，并在完成提交之后释放在整个事务执行期间占用的事务资源

3. 反馈事务提交结果

   参与者在完成事务提交之后，向协调者发送ACK信息

4. 完成事务

   协调者接收到所有参与者反馈的ACK消息后，完成事务

（2）中断事务

任何一个参与者反馈了 No 响应，或者在等待超时之后，协调者尚无法接收到所有参与者的反馈响应，那么就会中断事务。

1. 发送回滚请求

   协调者向所有参与者节点发出Rollback请求

2. 事务回滚

   参与者接收到rollback请求后，会利用其在阶段一中记录的Undo信息来执行事务回滚操作，并在完成回滚之后释放整个事务执行期间占用的资源

3. 反馈事务回滚结果

   参与者在完成事务回滚之后，向协调者发送ACK信息

4. 中断事务

   协调者接收到所有参与者反馈的ACK信息后，完成事务中断

1.2 优缺点

优点：原理简单、实现方便

缺点：同步阻塞、单点问题、数据不一致、太过保守

（1）同步阻塞

同步阻塞会极大地限制分布式系统的性能。在二阶段提交的执行过程中，所有参与该事务操作的逻辑都处于阻塞状态，各个参与者在等待其他参与者响应的过程中，将无法进行其他任何操作。

（2）单点问题

一旦协调者出现问题，那么整个二阶段提交流程将无法运转，更为严重的是，如果是在阶段二中出现问题，那么其他参与者将会一直处于锁定事务资源的状态中，无法继续完成事务操作。

（3）数据不一致

在阶段二，当协调者向所有参与者发送commit请求之后，发生了局部网络异常或协调者在尚未发完commit请求之前自身发生了崩溃，导致最终只有部分参与者接收到了commit请求，于是这部分参与者执行事务提交，而没收到commit请求的参与者则无法进行事务提交，于是整个分布式系统出现了数据不一致性现象。

（4）太过保守

如果参与者在与协调者通信期间出现故障，协调者只能靠超时机制来判断是否需要中断事务，这个策略比较保守，需要更为完善的容错机制，任意一个节点的失败都会导致整个事务的失败。

二、3PC（解决2PC的阻塞，但还是可能造成数据不一致）

Three-Phase Commit，三阶段提交，分为 CanCommit、PreCommit、doCommit 三个阶段。

2.1 协议介绍

为了避免在通知所有参与者提交事务时，其中一个参与者 crash 不一致时，就出现了三阶段提交的方式。三阶段提交在两阶段提交的基础上增加了一个 preCommit 的过程，当所有参与者收到 preCommit 后，并不执行动作，直到收到 commit 或超过一定时间后才完成操作。

第一阶段： CanCommit

1. 事务询问
   协调者向各参与者发送 CanCommit 的请求，询问是否可以执行事务提交操作，并开始等待各参与者的响应

2. 参与者向协调者反馈询问的响应
   参与者收到 CanCommit 请求后，正常情况下，如果自身认为可以顺利执行事务，那么会反馈 Yes 响应，并进入预备状态，否则反馈 No。

第二阶段： PreCommit

（1）执行事务预提交

如果协调者接收到各参与者反馈都是 Yes，那么执行事务预提交

1. 发送预提交请求
   协调者向各参与者发送 preCommit 请求，并进入 prepared 阶段

2. 事务预提交
   参与者接收到 preCommit 请求后，会执行事务操作，并将Undo和Redo信息记录到事务日记中

3. 各参与者向协调者反馈事务执行的响应
   如果各参与者都成功执行了事务操作，那么反馈给协调者 Ack 响应，同时等待最终指令，提交 commit 或者终止 abort

（2）中断事务

如果任何一个参与者向协调者反馈了No响应，或者在等待超时后，协调者无法接收到所有参与者的反馈，那么就会中断事务。

1. 发送中断请求
   协调者向所有参与者发送 abort 请求

2. 中断事务
   无论是收到来自协调者的 abort 请求，还是等待超时，参与者都中断事务

第三阶段： doCommit

（1）执行提交

1. 发送提交请求
   假设协调者正常工作，接收到了所有参与者的ack响应，那么它将从预提交阶段进入提交状态，并向所有参与者发送doCommit请求

2. 事务提交
   参与者收到doCommit请求后，正式提交事务，并在完成事务提交后释放占用的资源

3. 反馈事务提交结果
   参与者完成事务提交后，向协调者发送ACK信息

4. 完成事务
   协调者接收到所有参与者ack信息，完成事务

（2）中断事务

假设协调者正常工作，并且有任一参与者反馈No，或者在等待超时后无法接收所有参与者的反馈，都会中断事务

1. 发送中断请求
   协调者向所有参与者节点发送abort请求

2. 事务回滚
   参与者接收到 abort 请求后，利用 undo 日志执行事务回滚，并在完成事务回滚后释放占用的资源

3. 反馈事务回滚结果
   参与者在完成事务回滚之后，向协调者发送 ack 信息

4. 中断事务
   协调者接收到所有参与者反馈的 ack 信息后，中断事务。

阶段三可能出现的问题：

协调者出现问题、协调者与参与者之间网络出现故障。不论出现哪种情况，最终都会导致参与者无法及时接收到来自协调者的 doCommit 或是 abort 请求，针对这种情况，参与者都会在等待超时后，继续进行事务提交（timeout 后中断事务）。

2.2 优缺点

优点：降低参与者阻塞范围，并能够在出现单点故障后继续达成一致
缺点：引入 preCommit 阶段，在这个阶段如果出现网络分区，协调者无法与参与者正常通信，参与者依然会进行事务提交，造成数据不一致。

三、Paxos（解决单点问题）

Paxos 算法目的是让整个集群的结点对某个值的变更达成一致。Paxos 算法(强一致性算法)属于多数派——大多数的决定会成个整个集群的统一决定。任何一个点都可以提出要修改某个数据的提案，是否通过这个提案取决于这个集群中是否有超过半数的结点同意（所以 Paxos 算法需要集群中的结点是单数）

这个算法有两个大阶段，四个小阶段（Paxos 有 Proposer 和 Acceptor 两个角色）

1. Prepare proposer 提出一个提案，编号为 N ，此 N 大于这个 proposer 之前提出提案编号。请求 acceptors 的 quorum 接受。
2. Promise 如果 N 大于此 acceptor 之前接受的任何提案编号则接受，否则拒绝
3. Accept 如果达到了多数派， Proposer 会发出 accept 请求，此请求包含提案编号 N，以及提案内容
4. Accepted 如果此 acceptor 在此期间没有收到任何编号大于 N 的提案，则接受此提案内容，否则忽略

下面详细解释一下这四个阶段（A 为 Proposer， A、B、C 均为 Acceptor）

第一阶段：Prepare 阶段

A 把申请修改的请求 Prepare Request 发给所有的结点 A，B，C。注意，Paxos 算法会有一个 Sequence Number（你可以认为是一个提案号，这个数不断递增，而且是唯一的，也就是说 A 和 B 不可能有相同的提案号），这个提案号会和修改请求一同发出，任何结点在 “Prepare 阶段” 时都会拒绝其值小于当前提案号的请求。所以，结点 A 在向所有结点申请修改请求的时候，需要带一个提案号，越新的提案，这个提案号就越是是最大的。

如果接收结点收到的提案号 n 大于其它结点发过来的提案号，这个结点会回应 Yes（本结点上最新的被批准提案号），并保证不接收其它 <n 的提案。这样一来，结点上在 Prepare 阶段里总是会对最新的提案做承诺。

优化：在上述 prepare 过程中，如果任何一个结点发现存在一个更高编号的提案，则需要通知提案人，提醒其中断这次提案。

第二阶段：Accept 阶段

如果提案者 A 收到了超过半数的结点返回的 Yes，然后他就会向所有的结点发布 Accept Request（同样，需要带上提案号 n），如果没有超过半数的话，那就返回失败。

当结点们收到了 Accept Request 后，如果对于接收的结点来说，n 是最大的了，那么，它就会通过 request（修改这个值），如果发现自己有一个更大的提案号，那么，结点就会拒绝 request（拒绝修改）。

我们可以看以，这似乎就是一个“两段提交”的优化。其实，2PC/3PC 都是分布式一致性算法的残次版本，Google Chubby 的作者 Mike Burrows 说过这个世界上只有一种一致性算法，那就是 Paxos，其它的算法都是残次品。

我们还可以看到：对于同一个值的在不同结点的修改提案就算是在接收方被乱序收到也是没有问题的。

四、Raft(解决 Paxos 的实现难度)

Raft 是简化版的 Paxos。Raft 划分成三个子问题：一是Leader Election；二是 Log Replication；三是 Safety。Raft 定义了三种角色 Leader、Follower、Candidate，最开始大家都是 Follower，当 Follower 监听不到 Leader，就可以自己成为 Candidate，发起投票。

4.1 Leader 选举：timeout 限制

每个 Follower 都在 150ms and 300ms 之间随机超时，之后看谁先 timeout，谁就先成为 Candidate，然后它会先投自己一票，再向其他节点发起投票邀请。如果其他节点在这轮选举还没有投过票，那么就给 Candidate 投票，然后重置自己的选举 timeout。如果得到大多数的投票就成为 Leader，之后定期开始向 Follower 发送心跳。

如果两个 Follower 同时成为 Candidate 的话，如果最后得到的票数相同，则等待其他 Follower 的选择 timeout 之后成为 Candidate，继续开始新一轮的选举。

4.2 log复制

Leader 把变动的 log 借助心跳同步给 Follower，过半回复之后才成功提交，之后再下一次心跳之后，Follower 也 commit 变动，在自己的 node 上生效。

分裂之后，另一个分区的 Follower 接受不到 Leader 的 timeout，然后会有一个先 timeout，成为 Candidate，最后成为 Leader。于是两个分区就有了两个 Leader。

当客户端有变动时，其中的 Leader 由于无法收到过半的提交，则保持未提交状态。有的 Leader 的修改，可以得到过半的提交，则可以修改生效。

当分裂恢复之后，Leader 开始对比选举的 term，发现有更高的 term 存在时，他们会撤销未提交的修改，然后以最新的为准。

五、ZAB

基本与 raft 相同。在一些名词的叫法上有些区别，如 ZAB 将某一个 Leader 的周期称为 epoch，而 raft 则称之为 term。实现上也有些许不同，如 raft 保证日志连续性，心跳方向为 Leader 至 Follower，ZAB 则相反。

参考：

1. 《分布式理论系列》：https://segmentfault.com/a/1190000004474543
2. 从 Paxos 到 Zookeeper : 分布式一致性原理与实践
3. 《一致性算法（Paxos、Raft、ZAB）视频》：https://www.bilibili.com/video/av21667358/
4. 《分布式事务中2PC与3PC的区别》：https://blog.csdn.net/yyd19921214/article/details/68953629

每天用心记录一点点。内容也许不重要，但习惯很重要！