Jace Ding
0%

一致性协议

发表于 分类于

CAP 定理

一个分布式系统最多只能同时满足一致性（Consistency）、可用性（Availability）和分区容错性（Partition tolerance）这三项中的两项。

一致性

一致性是指多个数据副本之间能够保持一致的特性（强一致性）。

从客户端角度，多进程并发访问时，更新过的数据在不同进程如何获取的不同策略，分为不同的一致性。

  1. 强一致性：要求更新过的数据能被后续的访问都能看到，则是强一致性。
  2. 弱一致性：能容忍后续的部分或者全部访问不到，则是弱一致性。
  3. 最终一致性：经过一段时间后要求能访问到更新后的数据，则是最终一致性。

可用性

可用性是指系统提供的服务一直处于可用状态，每次请求都能获取到非错的响应。

分区容错性

分区容错性是指分布式系统在遇到某节点或网络分区故障的时候，仍然能够对外提供满足一致性或可用性的服务。

论证

假设存在有一个分布式系统：有两个节点N1、N2，N1 和 N2 分别连接数据库D1 和 D2。

如果客户端向节点 N1 请求更新数据，N1 更新完数据后需要向 N2 进行同步操作，如果此时正好发生网络分区，也就是说 N1 和 N2 网络不通。在满足分区容错性的前提下，是否能满足一致性和可用性呢？这里有两种选择：

  1. 牺牲数据一致性，保证系统可用性，响应更新成功给客户端。
  2. 牺牲系统可用性，保证数据一致性，阻塞等待网络连通或返回错误信息给客户端。

在分布式系统中，通常分区容错性必须得保证，只能在一致性和可用性做出权衡。

权衡

CA

如果不要求分区容错性，则强一致性和可用性是可以保证的。

但其实分区不是你想不想的问题，而是始终会存在，因此CA的系统更多的是允许分区后各子系统依然保持CA。

CP

如果不要求可用性，相当于每个请求都需要在Server之间强一致，而P（分区）会导致同步时间无限延长，如此CP也是可以保证的。很多传统的数据库分布式事务都属于这种模式。

AP

如果要求高可用并允许分区，则需放弃一致性。一旦分区发生，节点之间可能会失去联系，为了高可用，每个节点只能用本地数据提供服务，而这样会导致全局数据的不一致性。

WARO 机制

WARO（Write All Read one）是一种简单的副本控制协议，当 Client 请求向某副本写数据时（更新数据），只有当所有的副本都更新成功之后，这次写操作才算成功，否则视为失败。

假设有 N 个副本，N-1 个都宕机了，剩下的那个副本仍能提供读服务；但是只要有一个副本宕机了，写服务就不会成功。

WARO 机制牺牲了更新服务的可用性，最大程度地增强了读服务的可用性。

Quorum 机制

Quorum机制是 “抽屉原理” 的一个应用。

假设有 N 个副本。为了能够执行写请求，必须要确保写操作被 W（W 小于 N）个副本确认。所以你需要将写请求发送到这 W 个副本。如果要执行读请求，那么至少需要从 R 个副本得到所读取的信息。这里的 W 对应的数字称为 Write Quorum，R 对应的数字称为 Read Quorum。这是一个典型的 Quorum 配置。

这里的关键点在于，W、R、N之间的关联。Quorum 系统要求，任意你要发送写请求的 W 个服务器，必须与任意接收读请求的 R 个服务器有重叠。这意味着，W+R > N ，这样任意 W 个服务器至少与任意 R个服务器有一个重合。

N个9

系统的可靠性中有个衡量标准：N个9，表示一年中，系统可以正常使用的时间与总时间之比。

  • 3个9：( 1 - 99.9% ) * 365 * 24 = 8.76小时，表示系统一年内最多不可用时间为 8.76 小时。
  • 4个9：( 1 - 99.99% ) * 365 * 24 = 0.876小时 = 52.6分钟，表示系统一年内最多不可用时间为 52.6 分钟。
  • 5个9：( 1 - 99.999% ) * 365 * 24 * 60 = 5.26分钟，表示系统一年内最多不可用时间为 5.26 分钟。

Base 理论

BASE 理论是基本可用（Basically Available），软状态（Soft State）和最终一致性（Eventually Consistent）三个短语的缩写。

BASE 理论是对 CAP 中 AP 的一个扩展，其核心思想是：即使无法做到强一致性，但每个应用都可以根据自身的业务特点，采用适当的方式来使系统达到最终一致性。

基本可用

基本可用是指分布式系统在出现不可预知故障的时候，允许损失部分可用性。例如：

  • 响应时间上的损失：正常情况下的搜索引擎0.5秒即返回给用户结果，但由于出现故障，查询结果的响应时间增加到 1 ~ 2 秒。
  • 功能上的损失：在一个电商网站上，正常情况下，用户可以顺利完成每一笔订单。但是到了大促期间，为了保护购物系统的稳定性，部分消费者可能会被引导到一个降级页面。

软状态

软状态是指允许系统中的数据存在中间状态，并认为该状态不影响系统的整体可用性，即允许系统在多个不同节点的数据副本存在数据延时。

最终一致性

最终一致性强调的是系统中所有的数据副本，在经过一段时间的同步后，最终能够达成一致的状态。因此，最终一致性的本质是需要系统保证最终数据能够达成一致，而不需要实时保证数据的强一致性。

最终一致性是一种特殊的弱一致性，经过一段时间后达成一致，这个时间期限取决于网络延时、系统负载、数据复制方案设计等等因素。

在实际工程实践中，最终一致性大致分为5种：

  1. 因果一致性（Causal consistency）：

    如果节点 A 在更新完某个数据后通知了节点 B，那么节点 B 之后对该数据的访问和修改都是基于 A 更新后的值，即不能发生丢失更新情况。而与节点 A 无因果关系的节点 C 的数据访问则没有这样的限制。

  2. 读己之所写（Read your writes）

    节点 A 更新一个数据后，它自身总是能访问到自身更新过的最新值，而不是旧值。这也算一种因果一致性。

  3. 会话一致性（Session consistency）

    将对系统数据的访问过程框定在了一个会话当中：系统能保证在同一个有效的会话中实现 “读己之所写” 的一致性，也就是说，执行更新操作之后，客户端能够在同一个会话中始终读取到该数据项的最新值。

  4. 单调读一致性（Monotonic read consistency）

    如果一个节点从系统中读取出一个数据项的某个值后，那么系统对于该节点后续的任何数据访问都不应该返回更旧的值。

  5. 单调写一致性（Monotonic write consistency）

    一个系统要能够保证来自同一个节点的写操作被顺序的执行。

在实际的实践中，这5种系统往往会结合使用，以构建一个具有最终一致性的分布式系统。

小结

总体来说 BASE 理论面向的是大型高可用、可扩展的分布式系统。不同于传统 ACID 的强一致性模型，BASE 理论提出通过牺牲强一致性来获得可用性，并允许数据段时间内的不一致，但是最终达到一致状态。同时，在实际分布式场景中，不同业务对数据的一致性要求不一样。因此在设计中，ACID 和 BASE 理论往往又会结合使用。

FLP

FLP 不可能定理是分布式系统领域中最重要的定理之一，它给出了一个非常重要的结论：

在网络可靠并且存在节点失效的异步模型系统中，不存在一个可以解决一致性问题的确定性算法。

这个定理告诉我们不要浪费时间去为异步分布式系统设计在任意场景上都能够实现共识的算法，异步系统完全没有办法保证能在有限时间内达成一致。

2PC 和 3PC

前言

在分布式系统中，每个节点虽然知道自己进行事务操作的结果，却无法获取其他节点的操作结果。因此，当一个事务操作需要跨域多个分布式节点的时候，为了保持事务处理的 ACID 特性，引入了一个称为 “协调者” 的组件来调度所有分布式节点的执行逻辑（比如：半数节点执行成功则提交），这些被调度的分布式节点被称为 “参与者”。

协调者负责调度参与者的行为，并最终决定这些参与者是否要把事务进行提交。基于这个思想，衍生出了二阶段提交协议（2 Phase Commitment Protocol，2PC）和三阶段提交协议（3 Phase Commitment Protocol，3PC）。

2PC

为了使分布式系统的所有节点在进行事务过程中能够保持原子性和一致性而设计的算法。通常，2PC也被认为是一种一致性协议，用来保证分布式系统中的数据一致性。

大概思路：每个参与者将操作成败通知协调者，再由协调者根据所有参与者的反馈情报，决定各参与者是否要提交操作还是中止操作。

二阶段提交的两个阶段：

  • 第一阶段：提交事务请求（也叫投票阶段，各参与者投票表明是否要继续执行接下来的事务提交操作）
  • 第二阶段：执行事务提交（也叫提交阶段，根据参与者的反馈情况决定最终是否可以进行事务提交操作）

投票阶段

投票阶段流程如下：

  1. 事务询问

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

  2. 执行事务

    各参与者节点执行事务操作，并将 undo 和 redo 信息记入事务日志中。

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

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

提交阶段

根据参与者的反馈情况决定最终是否可以进行事务提交操作，有两种可能：

执行事务提交

如果所有参与者的反馈都是Yes，那么就会执行事务提交。执行事务提交流程如下：

  1. 发送提交请求

    协调者向所有参与者发送 commit 请求。

  2. 事务提交

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

  3. 反馈事务提交结果

    参与者完成提交事务之后，向协调者发送 Ack 消息。

  4. 完成事务

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

中断事务

如果任何一个参与者的反馈是No，或者在等待超时之后，协调者没有收到所有参与者的响应，那么就会中断事务。中断事务流程如下：

  1. 发送回滚请求

    协调者向所有参与者发送 Rollback 请求。

  2. 事务回滚

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

  3. 反馈事务回滚结果

    参与者完成事务回滚之后，向协调者发送 Ack 消息。

  4. 完成中断事务

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

优缺点

优点：

  1. 原理简单，实现方便。

缺点：

  1. 同步阻塞

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

  2. 单点问题

    一旦协调者出现问题，整个二阶段提交流程将无法运转，更为严重的是，参与者将会一直处在锁定事务资源的状态中，而无法继续完成事务操作。所有参与者必须等待协调者重新上线后才能工作。

  3. 数据不一致

    在提交阶段中，当协调者向参与者发送 commit 请求之后，发生了局部网络异常或者在发送 commit 请求过程中协调者发生了故障，这会导致只有部分参与者接受到了commit 请求。这样整个分布式系统便出现了数据不一致性的现象。

  4. 容错性不好

    如果在二阶段提交的提交阶段，参与者出现故障，导致协调者始终无法获取到所有参与者的确认信息，这时协调者只能依靠其自身的超时机制，判断是否需要中断事务。显然，这种策略过于保守。换句话说，二阶段提交协议没有设计较为完善的容错机制，任意一个节点是失败都会导致整个事务的失败。

3PC

二阶段提交存在诸多缺点，因此研究者在二阶段提交协议的基础上进行了改进，提出了三阶段提交协议。

与两阶段提交不同的是，三阶段提交有两个改动点：

  1. 引入超时机制（2PC只有协调者有超时机制）
  2. 将 2PC 的投票阶段一分为二，这样 3PC 就有 CanCommit、PreCommit、DoCommit 阶段

引入 CanCommit 阶段，主要是进一步降低阻塞范围，因为在执行事务后，就会占用事务资源。2PC 没有CanCommit 阶段，那么就一定会占用事务资源（占用事务资源意味着可能导致阻塞）。换句话说，如果在占用事务资源之前，就能先判断事务是否执行成功，那么这样可以避免一些不必要的阻塞，这个和 Java 中的双重锁定有着异曲同工之妙。

CanCommit

CanCommit 流程如下：

  1. 事务询问

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

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

    参与者在接收到协调者的 CanCommit 请求后，如果认为自身能够顺利执行事务，则响应 Yes 并进入预备状态，否则响应 No。

PreCommit

根据参与者的反馈情况决定最终是否可以进行 PreCommit 操作，有两种可能：

执行事务预提交

如果阶段一所有参与者的反馈都是 Yes，那么就会执行事务预提交。执行事务预提交流程如下：

  1. 发送预提交请求

    协调者向所有参与者发送 PreCommit 请求，并进入 Prepared 阶段。

  2. 事务预提交

    各参与者接收到 PreCommit 请求后，执行事务操作，并将 undo 和 redo 信息记入事务日志中。

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

    如果参与者成功执行了事务操作，那么就会反馈给协调者 Ack 响应，同时等待最终的指令：提交（commit）或中止（abort）。

中断事务

如果阶段一任何一个参与者的反馈是 No，或者在等待超时之后，协调者没有收到所有参与者的响应，就会执行中断事务。中断事务流程如下：

  1. 发送中断请求

    协调者向所有参与者发送 Abort 请求。

  2. 中断事务

    参与者收到协调者的 Abort 请求，或者在等待超时之后，参与者没有收到所有协调者的响应，就会执行中断操作。

DoCommit

执行提交

如果协调者处于正常状态，并且它接收到了所有参与者的 Ack 响应，那么就会执行提交。执行提交流程如下：

  1. 发送提交请求

    协调者会从 “预提交” 状态转换为 “提交” 状态，并向所有参与者发送 doCommit 请求。

  2. 事务提交

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

  3. 反馈事务提交结果

    参与者完成事务提交之后，会向协调者发送 Ack 消息。

  4. 完成事务

    协调者在收到所有参与者的 Ack 后，完成事务。

中断事务

如果协调者处于正常状态，有任意一个参与者向协调者反馈了 No 响应，或者在等待超时之后，参与者没有收到所有协调者的响应，就会中断事务。中断事务流程如下：

  1. 发送中断请求

    协调者向所有参与者发送 Abort 请求。

  2. 事务回滚

    参与者在收到协调者的 Abort 请求后，会利用其阶段二中记录的 undo 信息来执行事务回滚操作，并在完成回滚后释放整个事务执行期间占用的事务资源。

  3. 反馈事务回滚结果

    参与者在完成回滚后，向协调者发送 Ack 消息。

  4. 中断事务

    协调者在收到所有参与者反馈的 Ack 消息后，中断事务。

协议补充

一旦进入阶段三，参与者等待协调者最终的指令，协调者发生了故障或者发生了网络故障，参与者在等待超时后最终会提交事务。

优缺点

优点：

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

    进入阶段三后，即使没有收到协调者最终的指令，参与者最终也会提交事务。

缺点：

  1. 可能会数据不一致

    参与者在接收到PreCommit消息后，如果出现网络分区， 某个参与者无法和协调者进行通信，这个参与者最终会进行事务的提交（其他参与者可能会回滚）。

Paxos

Paxos 算法是 Leslie Lamport 1990年提出的一种基于消息传递且具有高度容错特性的共识算法。

需要注意的是，一致性和共识并不是一个概念，一致性往往指分布式系统中多个副本对外呈现的数据的状态，共识则描述了分布式系统中多个节点之间，彼此对某个提案达成一致结果的过程。因此，一致性描述的是结果，共识则是一种手段。从某种程度上来说，共识算法可以看作是实现强一致性的一种方法。

算法角色

Paxos 有三种角色：提议者（Proposer），决策者（Acceptor），和学习者（Learner）：

  • Proposer：
    • 提案发起者
    • 处理客户端的请求
  • Acceptor：
    • 参与决策，回应 Proposer 的提案
    • 对 Accept 的提案，进程状态进行持久化
  • Learner：
    • 不参与决策，从 Proposer / Acceptor 学习最新达成一致的提案（Value）。

在具体的实现中，一个进程可能不止充当一种角色。

安全性和活性

一个分布式算法有两个最重要的属性：安全性（Safety）和活性（Liveness）。

  • 安全性
    1. 只有被提出的提案才能被选定
    2. 只能一个值被选定
    3. 如果某个进程认为某个提案被选定了，那么这个提案必须是真的被选定的那个
  • 活性
    1. 最终有一个提案会被选定

Basic Paxos

Proposer 生成提案

  • Proposer 选择一个新的提案编号 N，然后向某个 Acceptor 集合（该集合数量必须大于半数）的成员发送请求，要求该集合中的 Acceptor 做出如下回应：
    • 保证不再批准任何编号小于 N 的提案。
    • 如果 Acceptor 已经批准过任何提案，那么其就向 Proposer 反馈当前该 Acceptor 批准过的编号小于 N 但为最大编号的那个提案。
  • 如果 Proposer 收到了半数以上的 Acceptor 的响应结果，那么它就可以产生编号为 N，Value 为 W 的提案，这里的 W 是 Prepare 请求中所有响应中编号最大的提案的值。或者如果半数以上的 Acceptor 没有批准过任何提案，即 Prepare 请求中不包含任何提案，那么此时 W 值就可以由 Proposer 任意选择。

Acceptor 批准提案

Acceptor可能会收到来自Propose的两种请求：Prepare 请求和 Accept 请求，对这两种请求做出响应的条件如下：

  • Prepare 请求：Acceptor 可以在任何时候响应一个 Prepare 请求（前提是这个 Prepare 中的提案编号大于他批准过的所有提案编号）。
  • Accept请求： Acceptor 只要尚未响应过任何编号大于M的 Prepare 请求，那么它就可以响应这个编号为 M 的Accept 请求。

算法流程

Basic Paxos 算法伪代码如下：

Basic Paxos 将决议分为两个阶段：Prepare 阶段、Accept 阶段：

Prepare 阶段
  1. Proposer 生成一个全局唯一且递增的提案编号M，然后向所有 Acceptor 发送编号为M的 Prepare 请求。（这里只携带提案编号即可）
  2. 如果一个 Acceptor 收到提案编号为 M 的 Prepare 请求，且 M 大于已批准过的最大编号的提案，那么它就会将已批准过的最大编号的提案 [M1，V1] 作为响应反馈给 Proposer，同时承诺不会再批准任何编号小于M的提案。
Accept 阶段
  1. 如果 Proposer 收到半数以上 Acceptor 对其发出的 Prepare 请求的响应，那么它会发送一个针对 [M，V] 提案的 Accept 请求给 Acceptor。（这个提案的值 V 就是收到的响应中编号最大的提案的值V1，如果响应中不包含任何提案，那么 V 就是任意值）
  2. 如果一个 Acceptor 收到针对 [M，V] 提案的Accept请求，只要该 Acceptor 尚未对编号大于 M 的 Prepare 请求做出响应，它就可以接收并持久化这个提案 [M，V]。

算法优化

对于不会批准的请求，直接忽略，减少RPC次数。

提案的获取

  • 方案一：一旦一个 Acceptor 批准了一个提案，就将该提案发送给所有的 Leaner。
    • 优点：实现简单
    • 缺点：通讯次数太多。这样的做法虽然可以让 Learner 尽快获取被选定的提案，但是却需要让每个Acceptor跟所有的Learner逐个进行通信，通信的次数至少为二者数量的乘积。
  • 方案二：让所有的 Acceptor 将它们对提案的批准情况，统一发送给一个特定的Learner（称为“主Learner”），在不考虑拜占庭将军问题的前提下，假定Learner之间可以通过消息通讯来感知提案的选定情况。所以，当主Learner被通知一个提案已经被选定时，它会负责通知其他Learner。
    • 优点：通讯次数减少（通常为Accepter和Learner数量的总和）
    • 缺点：主Learner存在单点问题，并且延迟更高。
  • 方案三：因为方案二主 Learner 存在单点问题，所以让 Acceptor 发送给一个特定的 Learner 集合，该集合中的每个 Learner 都可以在一个提案被选定后通知其他 Learner。集合中 Learner 数量越多，就越可靠，但通讯也更复杂。
    • 优点：通讯次数相对方案一少，相对方案二也更可靠。
    • 缺点：通讯次数相对方案二多了，实现复杂。

活锁

存在一种极端情况，有两个 Proposer 依次提出一系列编号递增的提案，但是最终都无法被选定，陷入死循环。

Multi-Paxos

Basic Paxos 只能对一个值形成决议，决议的形成至少需要两次网络来回，在高并发情况下可能需要更多的网络来回，极端情况下甚至可能形成活锁。如果想连续确定多个值，Basic Paxos搞不定了。因此Basic Paxos几乎只是用来做理论研究，并不直接应用在实际工程中。

Multi-Paxos 基于 Basic Paxos 做了两点改进：

  1. 针对每一个要确定的值，运行一次 Basic Paxos 算法实例（Instance），形成决议。每一个 Paxos 实例使用唯一的Instance ID标识。
  2. 在所有 Proposers 中选举一个 Leader，由 Leader 唯一地提交 Proposal 给 Acceptors 进行表决。这样没有Proposer 竞争，解决了活锁问题。在系统中仅有一个 Leader 进行 Value 提交的情况下，Prepare 阶段就可以跳过，从而将两阶段变为一阶段，提高效率。

Multi-Paxos 首先需要选举Leader，Leader的确定也是一次决议的形成，所以可执行一次Basic Paxos实例来选举出一个Leader。选出Leader之后只能由Leader提交Proposal，在Leader宕机之后服务临时不可用，需要重新选举Leader继续服务。在系统中仅有一个Leader进行Proposal提交的情况下，Prepare阶段可以跳过。

Multi-Paxos通过改变Prepare阶段的作用范围至后面Leader提交的所有实例，从而使得Leader的连续提交只需要执行一次Prepare阶段，后续只需要执行Accept阶段，将两阶段变为一阶段，提高了效率。为了区分连续提交的多个实例，每个实例使用一个Instance ID标识，Instance ID由Leader本地递增生成即可。

Multi-Paxos允许有多个自认为是Leader的节点并发提交Proposal而不影响其安全性，这样的场景即退化为Basic Paxos。

总结

  • 二阶段提交主要解决了分布式事务的原子性问题，但是存在一些难以解决的例如同步阻塞，单点问题导致无期限等待，数据不一致等问题。
  • 三阶段提交在二阶段提交的基础上，引入CanCommit，并给参与者加上超时机制，减小阻塞的范围，避免无期限等待，但仍然没解决数据不一致问题。
  • Paxos 算法引入“过半”理念，并支持分布式节点角色之间的转换，避免了分布式节点的单点问题，既解决了无期限等待，也解决了“脑裂”问题。
  1. 如果 Proposer 收到半数以上 Acceptor 对其发出的 Accept 请求的响应，标志着本次 Accept 成功，决议形成。
  2. 将形成的决议发送给所有 Learner。

相关资料

  1. Paxos made simple

ZAB

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

基于 ZAB 协议，Zookeeper 实现了一种主备模式的系统架构来保持集群中各副本之间数据的一致性。这里的主备模型是指：Zookeeper 使用一个单一的主进程来接收并处理客户端的所有事务请求，并采用 ZAB 的原子广播协议，将服务器的状态变更以事务 Proposal 的形式广播到所有的副本进程上去。

ZAB 的核心是定义那些会改变 Zookeeper 服务器数据状态的事务请求的处理方式，即：

所有事务请求必须由一个全局唯一的服务器来协调处理，这样的服务器被称为 Leader 服务器，而余下的服务器被称为 Follower 服务器。Leader 服务器负责将一个客户端事务请求转换成一个事务 Proposal，并将该 Proposal 分发给集群中所有的 Follower 服务器。之后 Leader 会等待所有 Follower 服务器的反馈，一旦超过半数 Follower 服务器进行了正确的反馈后，那么 Leader 会再次向所有的 Follower 服务器分发 commit 消息，要求其将前一个 Proposal 进行提交。

角色、节点状态

ZAB 协议中有三种角色：Leader 领导者、Follower 跟随者、Observer 观察者：

  • Leader：集群中唯一的写请求处理者，能够发起投票（投票也是为了进行写请求）
  • Follower：能够接收客户端的读请求，如果是写请求则要转发给 Leader 。在选举过程中会参与投票，有选举权和被选举权 。
  • Observer：就是没有选举权和被选举权的 Follower，可以忽略。

ZAB 协议中节点有三种状态：Following、Looking、Leading：

  • Following：当前节点是跟随者，服从 Leader 节点的命令。
  • Looking：当前节点是 Leader，负责协调事务。
  • Leading：节点处于选举状态，正在寻找 Leader。

协议介绍

ZAB 协议中有两种模式：

  • 崩溃恢复模式

    当整个服务启动过程中，或者当 Leader 服务器出现网络中断、崩溃退出或重启等异常情况时，ZAB 协议就会进入崩溃恢复模式并通过选举产生新的 Leader 服务器。

    当选举产生新的 Leader 服务器，同时集群中已有过半的节点和该 Leader 服务器完成数据同步后，ZAB 协议就会退出崩溃恢复模式。

  • 消息广播模式

    当集群中已有过半的节点和 Leader 服务器完成数据同步后，就可以进入消息广播模式。

消息广播

当集群中已有过半的节点和 Leader 服务器完成数据同步后，就可以进入消息广播模式。

ZAB 协议的消息广播过程使用的是一个原子广播协议，类似于一个二阶段提交的过程。不同之处在于：

  • 移除了中断逻辑

    在 ZAB 协议的二阶段提交过程中，移除了中断逻辑，所有的 Follower 服务器要么正常反馈要么抛弃 Leader 服务器。崩溃或网络超时的 Follower 可以直接抛弃 Leader，并在数据同步阶段与集群达成一致，这种做法提高了集群的性能。

  • 过半的 Follower 服务器反馈 Ack 之后就可以提交事务

    二阶段提交的要求协调者必须等到所有的参与者全部反馈 Ack 确认消息后，再发送 Commit 消息。但 ZAB 协议中只需要过半的 Follower 服务器反馈 Ack 之后就可以提交事务。

消息广播模式具体的步骤如下：

  1. 客户端发起一个写操作请求。
  2. Leader 服务器将客户端的请求转化为事务 Proposal，同时为每个 Proposal 分配一个全局的ID，即 zxid。
  3. Leader 服务器为每个 Follower 服务器分配一个单独的队列，然后将需要广播的 Proposal 依次放到队列中取，并且根据 FIFO 策略进行消息发送。
  4. Follower 接收到 Proposal 后，会首先将其以事务日志的方式写入本地磁盘中，写入成功后向 Leader 反馈一个 Ack 响应消息。
  5. Leader 接收到超过半数以上 Follower 的 Ack 响应消息后，即认为消息发送成功，可以发送 commit 消息。
  6. Leader 向所有 Follower 广播 commit 消息，同时自身也会完成事务提交。Follower 接收到 commit 消息后，会将上一条事务提交。

只要有一台服务器提交了 Proposal，就要确保所有的服务器最终都能正确提交 Proposal。这也是 CAP/ BASE 实现最终一致性的一个体现。

Leader 服务器与每一个 Follower 服务器之间都维护了一个单独的 FIFO 消息队列进行收发消息，使用队列消息可以做到异步解耦。 Leader 和 Follower 之间只需要往队列中发消息即可。如果使用同步的方式会引起阻塞，性能要下降很多。由于协议是 *通过 TCP *来进行网络通信的，保证了消息的发送顺序性，接受顺序性也得到了保证。

ZAB 协议中定义了一个全局单调递增的事务ID：zxid ，用于避免不同的 Leader 错误的使用了相同的 zxid 编号提出了不一样的 Proposal 的异常情况。它是一个 64 位 long 型，其中高32位表示 epoch 年代，低32位表示事务 id。epoch 可以理解为当前集群所处的年代，每次 Leader 变更之后都会在 epoch 的基础上加1。而低32位可以简单理解为递增的事务 id，Leader 在产生新的 Proposal 事务时，都会对其加1。

崩溃恢复

当整个服务启动过程中，或者当 Leader 服务器出现网络中断、崩溃退出或重启等异常情况时，ZAB 协议就会进入崩溃恢复模式并通过选举产生新的 Leader 服务器。

ZAB 协议崩溃恢复需要满足以下两个条件：

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

选举规则

为了实现上面这两个条件，需要选举算法能够保证新选举出来的 Leader 服务器拥有集群中所有机器最高编号（即 zxid 最大）的事务，这样就可以保证这个新选举出来的 Leader 一定具有所有已经提交的提案。同时也避免了 Leader 服务器检查 Proposal 的提交和丢弃工作。

数据同步

当选举产生新的 Leader 服务器之后，在正式开始工作之前（接收事务请求，然后提出新的 Proposal），Leader 服务器会首先确认事务日志中的所有的 Proposal 是否已经被集群中过半的服务器 Commit。

Leader 服务器需要确保所有的 Follower 服务器能够接收到每一条事务的 Proposal ，并且能将所有已经提交的事务 Proposal 应用到内存数据中。等到 Follower 将所有尚未同步的事务 Proposal 都从 Leader 服务器上同步过啦并且应用到内存数据中以后，Leader 才会把该 Follower 加入到真正可用的 Follower 列表中。

状态流转

  • 选举（Leader Election）：选出 Leader。
  • 发现（Descovery）：Leader 会维护一个 Follower 的可用列表，将来客户端可以和其中的 Follower 节点进行通信。
  • 同步（Synchronization）：Leader 要负责将本身的数据与 Follower 完成同步，做到多副本存储。
  • 广播（Broadcast）：Leader 可以接受客户端新的 Proposal 请求，将新的 Proposal 请求广播给所有的 Follower。

Raft

协议介绍

由于论文非常详细，直接查看论文即可。

优缺点

优点

  1. 相比Paxos更容易理解和工程化实现

缺点

  1. Raft有一个很强的假设是主（leader）和备（follower）都按顺序投票，存在并发瓶颈，可参考 OceanBase 的一致性协议为什么选择 paxos 而不是 raft?，不过也可以参考 TiDB 使用 multi raft，或者是 PolarFS 使用的ParallelRaft。
    1. Elasticell-Multi-Raft实现
  2. 网络分区会导致脑裂，可能会导致stale read，可以通过ReadIndex Read和Lease Read的方法来解决。
    1. TiDB如何确认 leader 在处理这次 read 的时候一定是 leader

相关资料

  1. 中文论文翻译
  2. 动画演示
坚持原创技术分享，您的支持将鼓励我继续创作！