「分布式一致性协议」从2PC、3PC、Paxos到 ZAB

作者 Starfish 日期 2022-06-09
zk 分布式
「分布式一致性协议」从2PC、3PC、Paxos到 ZAB

CAP

设计一个分布式系统必定会遇到一个问题—— 因为分区容忍性（partition tolerance）的存在，就必定要求我们需要在系统可用性（availability）和数据一致性（consistency）中做出权衡 。这就是著名的 CAP 定理。

大多数分布式系统都分布在多个子网络。每个子网络就叫做一个区（partition）。分区容错的意思是，区间通信可能失败。比如，一台服务器放在中国，另一台服务器放在美国，这就是两个区，它们之间可能无法通信。

一般来说，分区容错无法避免，因此可以认为 CAP 的 P 总是成立。(因为我们前提分布式系统，分布的服务都没法通信了，还玩个啥）

img

一致性和可用性，为什么不可能同时成立？答案很简单，因为可能通信失败（即出现分区容错）。

如果保证 G2 的一致性，那么 G1 必须在写操作时，锁定 G2 的读操作和写操作。只有数据同步后，才能重新开放读写。锁定期间，G2 不能读写，没有可用性不。

如果保证 G2 的可用性，那么势必不能锁定 G2，所以一致性不成立。

与 BASE 的关系

BASE 是 Basically Available（基本可用）、Soft state（软状态）和 Eventually consistent（最终一致性）三个短语的简写。

BASE是对CAP中一致性和可用性权衡的结果，其来源于对大规模互联网系统分布式实践的结论，是基于CAP定理逐步演化而来的，其核心思想是即使无法做到强一致性（Strong consistency），但每个应用都可以根据自身的业务特点，采用适当的方式来使系统达到最终一致性（Eventual consistency）。

一致性模型

一致性（Consistency）是指多副本（Replications）问题中的数据一致性。关于分布式系统的一致性模型有以下几种：

  • 强一致性：当更新操作完成之后，任何多个后续进程或者线程的访问都会返回最新的更新过的值，直到这个数据被其他数据更新为止。但是这种实现对性能影响较大，因为这意味着，只要上次的操作没有处理完，就不能让用户读取数据。
  • 弱一致性：系统并不保证进程或者线程的访问都会返回最新更新过的值。系统在数据写入成功之后，不承诺立即可以读到最新写入的值，也不会具体的承诺多久之后可以读到。甚至不能保证可以访问到。
  • 最终一致性：最终一致性也是弱一致性的一种，它无法保证数据更新后，所有后续的访问都能看到最新数值，而是需要一个时间，在这个时间之后可以保证这一点（就是在一段时间后，节点间的数据会最终达到一致状态），而在这个时间内，数据也许是不一致的，这个系统无法保证强一致性的时间片段被称为「不一致窗口」。不一致窗口的时间长短取决于很多因素，比如备份数据的个数、网络传输延迟速度、系统负载等。

一致性协议

为了解决分布式系统的一致性问题，在长期的研究探索过程中，业内涌现出了一大批经典的一致性协议和算法，其中比较著名的有二阶段提交协议（2PC），三阶段提交协议（3PC）和 Paxos 算法。

分布式事务

分布式事务是指会涉及到操作多个数据库的事务。其实就是将对同一库事务的概念扩大到了对多个库的事务。

目的是为了保证分布式系统中的数据一致性。

分布式事务处理的关键是必须有一种方法可以知道事务在任何地方所做的所有动作，提交或回滚事务的决定必须产生统一的结果（全部提交或全部回滚）

在分布式系统中，各个节点之间在物理上相互独立，通过网络进行沟通和协调。由于存在事务机制，可以保证每个独立节点上的数据操作可以满足 ACID。但是，相互独立的节点之间无法准确的知道其他节点中的事务执行情况。所以从理论上讲，两台机器理论上无法达到一致的状态。如果想让分布式部署的多台机器中的数据保持一致性，那么就要保证在所有节点的数据写操作，要不全部都执行，要么全部的都不执行。但是，一台机器在执行本地事务的时候无法知道其他机器中的本地事务的执行结果。所以他也就不知道本次事务到底应该 commit 还是 roolback。所以，常规的解决办法就是引入一个“协调者”的组件来统一调度所有分布式节点的执行。

XA规范

X/Open 组织（即现在的 Open Group ）定义了分布式事务处理模型。

X/Open DTP 模型（ 1994 ）包括应用程序（ AP ）、事务管理器（ TM ）、资源管理器（ RM ）、通信资源管理器（ CRM ）四部分。一般，常见的事务管理器（ TM ）是交易中间件，常见的资源管理器（ RM ）是数据库，常见的通信资源管理器（ CRM ）是消息中间件。

通常把一个数据库内部的事务处理，如对多个表的操作，作为本地事务看待。数据库的事务处理对象是本地事务，而分布式事务处理的对象是全局事务。所谓全局事务，是指分布式事务处理环境中，多个数据库可能需要共同完成一个工作，这个工作即是一个全局事务，例如，一个事务中可能更新几个不同的数据库。对数据库的操作发生在系统的各处但必须全部被提交或回滚。此时一个数据库对自己内部所做操作的提交不仅依赖本身操作是否成功，还要依赖与全局事务相关的其它数据库的操作是否成功，如果任一数据库的任一操作失败，则参与此事务的所有数据库所做的所有操作都必须回滚。

一般情况下，某一数据库无法知道其它数据库在做什么，因此，在一个 DTP 环境中，交易中间件是必需的，由它通知和协调相关数据库的提交或回滚。而一个数据库只将其自己所做的操作（可恢复）影射到全局事务中。

XA 就是 X/Open DTP 定义的交易中间件与数据库之间的接口规范（即接口函数），交易中间件用它来通知数据库事务的开始、结束以及提交、回滚等。 XA 接口函数由数据库厂商提供。

二阶提交协议和三阶提交协议就是根据这一思想衍生出来的。可以说二阶段提交其实就是实现XA分布式事务的关键(确切地说：两阶段提交主要保证了分布式事务的原子性：即所有结点要么全做要么全不做)

2PC

2PC，是 Two-Phase-Comimit 的缩写，即「二阶段提交」，是计算机网络尤其是数据库领域内，为了使基于分布式系统架构的所有节点在进行事务处理过程中能够保持原子性和一致性而设计的一种协议。

现在很多数据库都是采用的二阶段提交协议来完成分布式事务的处理。

二阶段，顾名思义就是分两个阶段处理事务，流程如下：

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

当要执行一个分布式事务的时候，事务发起者首先向协调者发起事务请求，然后协调者会给所有参与者发送 prepare 请求（其中包括事务内容）告诉参与者你们需要执行事务了，如果能执行我发的事务内容那么就先执行但不提交，执行后请给我回复。然后参与者收到 prepare 消息后，他们会开始执行事务（但不提交），并将 Undo 和 Redo 信息记入事务日志中，之后参与者就向协调者反馈是否准备好了

阶段二：执行事务提交

协调者根据各参与者的反馈情况决定最终是否可以提交事务，如果反馈都是Yes，发送提交 commit 请求，参与者提交成功后返回 Ack 消息，协调者接收后就完成了。如果反馈是 No 或者超时未反馈，发送 Rollback 请求，利用阶段一记录表的 Undo 信息执行回滚，并反馈给协调者 Ack ，中断消息

2PC

优缺点

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

缺点：

  • 单点故障问题，如果协调者挂了那么整个系统都处于不可用的状态了
  • 阻塞问题，即当协调者发送 prepare 请求，参与者收到之后如果能处理那么它将会进行事务的处理但并不提交，这个时候会一直占用着资源不释放，如果此时协调者挂了，那么这些资源都不会再释放了，这会极大影响性能
  • 数据不一致问题，比如当第二阶段，协调者只发送了一部分的 commit 请求就挂了，那么也就意味着，收到消息的参与者会进行事务的提交，而后面没收到的则不会进行事务提交，那么这时候就会产生数据不一致性问题

3PC

3PC，是 Three-Phase-Comimit 的缩写，即「三阶段提交」，是二阶段的改进版，将二阶段提交协议的“提交事务请求”过程一分为二。

阶段一：CanCommit

协调者向所有参与者发送 CanCommit 请求，参与者收到请求后会根据自身情况查看是否能执行事务，如果可以则返回 YES 响应并进入预备状态，否则返回 NO

阶段二：PreCommit

协调者根据参与者返回的响应来决定是否可以进行下面的 PreCommit 操作。如果上面参与者返回的都是 YES，那么协调者将向所有参与者发送 PreCommit 预提交请求，参与者收到预提交请求后，会进行事务的执行操作，并将 Undo 和 Redo 信息写入事务日志中 ，最后如果参与者顺利执行了事务则给协调者返回成功的 Ack 响应。如果在第一阶段协调者收到了 任何一个 NO 的信息，或者 在一定时间内 并没有收到全部的参与者的响应，那么就会中断事务，它会向所有参与者发送中断请求 abort，参与者收到中断请求之后会立即中断事务，或者在一定时间内没有收到协调者的请求，它也会中断事务

阶段三：DoCommit

这个阶段其实和 2PC 的第二阶段差不多，如果协调者收到了所有参与者在 PreCommit 阶段的 YES 响应，那么协调者将会给所有参与者发送 DoCommit 请求，参与者收到 DoCommit 请求后则会进行事务的提交工作，完成后则会给协调者返回响应，协调者收到所有参与者返回的事务提交成功的响应之后则完成事务。若协调者在 PreCommit 阶段 收到了任何一个 NO 或者在一定时间内没有收到所有参与者的响应 ，那么就会进行中断请求的发送，参与者收到中断请求后则会 通过上面记录的回滚日志 来进行事务的回滚操作，并向协调者反馈回滚状况，协调者收到参与者返回的消息后，中断事务。

3PC

优缺点

降低了参与者的阻塞范围，且能在单点故障后继续达成一致。

但是最重要的一致性并没有得到根本的解决，比如在 PreCommit 阶段，当一个参与者收到了请求之后其他参与者和协调者挂了或者出现了网络分区，这个时候收到消息的参与者都会进行事务提交，这就会出现数据不一致性问题。

Paxos 算法

从「拜占庭将军问题」到「Paxos小岛的故事」诞生了 Paxos 算法。

Paxos 算法是基于消息传递且具有高度容错特性的一致性算法，是目前公认的解决分布式一致性问题最有效的算法之一，其解决的问题就是在分布式系统中如何就某个值（决议）达成一致 。

在 Paxos 中主要有三个角色，分别为 Proposer提案者、Acceptor表决者、Learner学习者。Paxos 算法和 2PC 一样，也有两个阶段，分别为 Prepare 和 accept 阶段。

在具体的实现中，一个进程可能同时充当多种角色。比如一个进程可能既是 Proposer 又是 Acceptor 又是Learner。Proposer 负责提出提案，Acceptor 负责对提案作出裁决（accept与否），learner 负责学习提案结果。

还有一个很重要的概念叫「提案」（Proposal）。最终要达成一致的 value 就在提案里。只要 Proposer 发的提案被半数以上的 Acceptor 接受，Proposer 就认为该提案里的 value 被选定了。Acceptor 告诉 Learner 哪个 value 被选定，Learner 就认为那个 value 被选定。

阶段一：prepare 阶段

  1. Proposer 负责提出 proposal，每个提案者在提出提案时都会首先获取到一个 具有全局唯一性的、递增的提案编号N，即在整个集群中是唯一的编号 N，然后将该编号赋予其要提出的提案，在第一阶段是只将提案编号发送给所有的表决者。

  2. 如果一个 Acceptor 收到一个编号为 N 的 Prepare 请求，如果小于它已经响应过的请求，则拒绝，不回应或回复error。若 N 大于该 Acceptor 已经响应过的所有 Prepare 请求的编号（maxN），那么它就会将它已经批准过的编号最大的提案（如果有的话，如果还没有的accept提案的话返回{pok，null，null}）作为响应反馈给 Proposer，同时该 Acceptor 承诺不再接受任何编号小于 N 的提案

    eg：假定一个 Acceptor 已经响应过的所有 Prepare 请求对应的提案编号分别是1、2、…5和7，那么该 Acceptor 在接收到一个编号为8的 Prepare 请求后，就会将 7 的提案作为响应反馈给 Proposer。

阶段二：accept 阶段

  1. 如果一个 Proposer 收到半数以上 Acceptor 对其发出的编号为 N 的 Prepare 请求的响应，那么它就会发送一个针对 [N,V] 提案的 Accept 请求半数以上的 Acceptor。注意：V 就是收到的响应中编号最大的提案的 value，如果响应中不包含任何提案，那么 V 就由 Proposer 自己决定
  2. 如果 Acceptor 收到一个针对编号为N的提案的Accept请求，只要该 Acceptor 没有对编号大于 N 的 Prepare 请求做出过响应，它就通过该提案。如果N小于 Acceptor 以及响应的 prepare 请求，则拒绝，不回应或回复error（当proposer没有收到过半的回应，那么他会重新进入第一阶段，递增提案号，重新提出prepare请求）
  3. 最后是 Learner 获取通过的提案（有多种方式）

Paxos

paxos 算法的死循环问题

其实就有点类似于两个人吵架，小明说我是对的，小红说我才是对的，两个人据理力争的谁也不让谁🤬🤬。

比如说，此时提案者 P1 提出一个方案 M1，完成了 Prepare 阶段的工作，这个时候 acceptor 则批准了 M1，但是此时提案者 P2 同时也提出了一个方案 M2，它也完成了 Prepare 阶段的工作。然后 P1 的方案已经不能在第二阶段被批准了（因为 acceptor 已经批准了比 M1 更大的 M2），所以 P1 自增方案变为 M3 重新进入 Prepare 阶段，然后 acceptor ，又批准了新的 M3 方案，它又不能批准 M2 了，这个时候 M2 又自增进入 Prepare 阶段。。。

就这样无休无止的永远提案下去，这就是 paxos 算法的死循环问题。

ZAB

ZAB（Zookeeper Atomic Broadcast） 协议是为分布式协调服务 Zookeeper 专门设计的一种支持崩溃恢复的原子广播协议。

在 Zookeeper 中，主要依赖 ZAB 协议来实现分布式数据一致性，基于该协议，ZooKeeper 实现了一种主备模式的系统架构来保持集群中各副本之间数据的一致性。

尽管 ZAB 不是 Paxos 的实现，但是 ZAB 也参考了一些 Paxos 的一些设计思想，比如：

  • leader 向 follows 提出提案(proposal)
  • leader 需要在达到法定数量(半数以上)的 follows 确认之后才会进行 commit
  • 每一个 proposal 都有一个纪元(epoch)号，类似于 Paxos 中的选票(ballot)

ZAB 中的三个角色

ZAB 中有三个主要的角色，Leader 领导者、Follower跟随者、Observer观察者 。

  • Leader ：集群中 唯一的写请求处理者 ，能够发起投票（投票也是为了进行写请求）。

  • Follower：能够接收客户端的请求，如果是读请求则可以自己处理，如果是写请求则要转发给 Leader 。在选举过程中会参与投票，有选举权和被选举权 。

  • Observer ：就是没有选举权和被选举权的 Follower 。

    在 ZAB 协议中对 zkServer(即上面我们说的三个角色的总称) 还有两种模式的定义，分别是消息广播和崩溃恢复

消息广播模式

ZAB

  1. Leader从客户端收到一个事务请求（如果是集群中其他机器接收到客户端的事务请求，会直接转发给 Leader 服务器）
  2. Leader 服务器生成一个对应的事务 Proposal，并为这个事务生成一个全局递增的唯一的ZXID（通过其 ZXID 来进行排序保证顺序性）
  3. Leader 将这个事务发送给所有的 Follows 节点
  4. Follower 节点将收到的事务请求加入到历史队列（Leader 会为每个 Follower 分配一个单独的队列先进先出，顺序保证消息的因果关系）中，并发送 ack 给 Leader
  5. 当 Leader 收到超过半数 Follower 的 ack 消息，Leader 会广播一个 commit 消息
  6. 当 Follower 收到 commit 请求时，会判断该事务的 ZXID 是不是比历史队列中的任何事务的 ZXID 都小，如果是则提交，如果不是则等待比它更小的事务的 commit

zab-commit

崩溃恢复模式

ZAB 的原子广播协议在正常情况下运行良好，但天有不测风云，一旦 Leader 服务器挂掉或者由于网络原因导致与半数的 Follower 的服务器失去联系，那么就会进入崩溃恢复模式。整个恢复过程结束后需要选举出一个新的 Leader 服务器。

恢复模式大致可以分为四个阶段：选举、发现、同步、广播

  1. 当 leader 崩溃后，集群进入选举阶段，开始选举出潜在的新 leader(一般为集群中拥有最大 ZXID 的节点)
  2. 进入发现阶段，follower 与潜在的新 leader 进行沟通，如果发现超过法定人数的 follower 同意，则潜在的新leader 将 epoc h加1，进入新的纪元。新的 leader 产生
  3. 集群间进行数据同步，保证集群中各个节点的事务一致
  4. 集群恢复到广播模式，开始接受客户端的写请求
两个特性

根据 ZAB 消息广播的过程可知，如果一个事务 Proposal 在一台机器上被处理成功，那么就应该在所有的机器上处理成功，哪怕机器出现故障。所以在崩溃恢复过程结束后，为了保证新选举出来的 Leader 服务器能正常工作，需要保证 2 个基本特性：

  • 确保那些已经在 Leader 服务器上提交的事务最终被所有的服务器都提交
  • 确保丢弃那些只在 Leader 服务上被提出的事务

首先看第一个特性：确保那些已经在 Leader 服务器上提交的事务最终被所有的服务器都提交。试想这么个场景：Leader 服务器在收到超半数的 ACK 返回响应后，本应该广播 commit 消息，但这时候 Leader 服务器挂掉了（Leader 服务器已经提交了事务），这时候就会导致 Follower 服务器和 Leader 服务器数据不一致的情况。ZAB 协议就须确保这种况下，所有的 Follower 服务器也都成功提交该事物。

第二个特性：确保丢弃那些只在 Leader 服务上被提出的事务。试想这么个场景：Leader 服务器在生成 Proposal 后就挂掉了，其他的服务器都没收到该 Proposal。于是，当该机器再次加入集群中的时候，需要确保丢弃该事物 Proposal。

所以上面两个特性总结就是下面两句话：

  • 提交已经被 Leader 提交的事务
  • 丢弃已经被跳过的事务

基于这两个特性，如果让新选举出来的 Leader 具有最大的 ZXID 的事务 Proposal，那么就可以保证该 Leader 一定具有所有已提交的提案。更为重要的是，如果让具有最高 ZXID 的事务 Proposal 的机器来成为 Leader，就可以省去 Leader 服务器检查 Proposal 的提交和丢弃工作这一步操作了。

数据同步

在完成 Leader 选举之后，在正式开始工作（即接收客户端的事务请求，然后提出新的提案）之前，Leader 服务器首先会确保事务日志中的所有 Proposal 是否都已经被集群中过半的机器提交了，即是否完成数据同步。

对于那些没有被 Follower 服务器提交的事务，Leader 会为每个 Follower 服务器准备一个队列，并将那些没有被各 Follower 服务器同步的事务已 Proposal 消息的形式逐个发送给 Follower 服务器，并在每一个 Proposal 消息后面紧接着再发送一个 commit 消息，以表示该事务已被提交。等到 Follower 服务器将所有未同步的事务 Proposal 都从 Leader 服务器上同步过来并应用到本地数据库，Leader 服务器就将该 Follower 服务器加入到真正可用的 Follower 列表中。

那 ZAB 是如何处理那些需要被丢弃的事务 Proposal 呢？

ZXID 是一个 64 位的数字，其中低 32 位可看作是计数器，Leader 服务器每产生一个新的事务 Proposal 的时候，都会该计数器进行加 1 操作。而高 32 位表示 Leader 周期 epoch 的编号，每当选举一个新的 Leader 服务器，就会从该服务器本地的事务日志中最大 Proposal 的 ZXID 中解析出对应的 epoch 值，然后对其加 1 操作，这个值就作为新的 epoch 值，并将低 32 位初始化为 0 来开始生成新的 ZXID。

基于这样的策略，当一个包含上一个 Leader 周期中尚未提交的事务 Proposal 的服务器启动时，以 Follower 角色加入集群中之后，Leader 服务器会根据自己服务器上最后被提交的 Proposal 来和 Follower 服务器的 Proposal 进行比对，比对结果就是 Leader 会要求 Follower 进行一个回退操作——回退到一个确实已经被集群中过半机器提交的最新的事务 Proposal。

Master 选举实现细节

上文说过，新选举出来的 Leader 具有最大的 ZXID 的事务 Proposal，那这是怎么实现的呢？

ZAB 默认采用 TCP 版本的 FastLeaderElection 选举算法。在选举投票消息中包含了两个最基本的信息：所推举的服务器 SID 和 ZXID，分别表示被推举服务器的唯一标识（每台机器不一样）和事务 ID。假如投票信息为 （SID, ZXID）的形式。在第一次投票的时候，由于还无法检测集群其他机器的状态信息，因此每台机器都将自己作为被推举的对象来进行投票。每次对收到的投票，都是一个对投票信息（SID, ZXID）对比的过程，规则如下：

  • 如果接收到的投票 ZXID 大于自己的 ZXID，就认可当前收到的投票，并再次将该投票发送出去。
  • 如果 ZXID 小于自己的 ZXID，那么就坚持的投票，不做任何变更。
  • 如果 ZXID 等于自己的 ZXID，再对比 SID，比自己大，就认可当前收到的投票，再将该投票发送出去；如果比自己小，那就坚持自己的投票，不做变更。

经过第二次投票后，集群中每台机器都会再次收到其他机器的投票，然后开始统计，如果一台机器收到超过了半数的相同投票，那么这个投票对应的 SID 机器即为 Leader。

简单来说，通常哪台服务器上的数据越新，那么越有可能成为 Leader。原因很简答，数据越新，也就越能够保证数据的恢复。当然，如果集群中有几个服务器具有相同的 ZXID，那么 SID 较大的那台服务器成为 Leader。

参考

《从Paxos到ZooKeeper 分布式一致性原理与实践》

《聊聊zookeeper的ZAB算法》

《基础Paxos算法》

https://blog.csdn.net/demon7552003/article/details/86657767