《深入理解分布式共识算法》记录

从 ACID 和 BASE 到 CAP

BASE 理论

BASE 包含；

  • BA（Basically Available）：基本可用，当分布式系统出现故障的时候，允许损失部分可用性。这里损失指响应时间的损失和功能上降级，前者是在增加响应时间上来提供服务，后者是在高峰期不请求后端而直接返回降级数据、以保证系统的稳定性。
  • S（Soft State）：软状态，允许系统中的数据存在中间状态，并认为该状态不会影响系统的整体可用性，即允许节点之间的数据同步存在延迟。
  • E（Eventually Consistent）：最终一致性。

为应用 BASE 理论，可以采用异步补偿机制。如果用这个机制，需要明确哪些操作属于非关键操作，如果非关键操作失败，应允许业务流程继续执行，然后在异步补偿非关键操作。

补偿指事务补偿：在分布式事务中，由于各个服务可能分布在不同的节点上，无法像单机事务那样简单地通过“回滚”来撤销操作。因此，事务补偿通过执行与原始操作相反的操作来达到类似的效果。

补偿操作需要注意两点：

  • 幂等性：补偿操作可能需要多次执行，因此需要保证其幂等性，即多次执行的效果与一次执行相同。
  • 最终一致性：补偿机制通常用于实现最终一致性，而不是强一致性，因此需要权衡一致性和性能。

CAP 理论

CAP 包含：

  • C（Consistency）一致性：分布式系统的全序线性一致性。
  • A（Availability）可用性：任何情况都能够处理客户端的每个请求。
  • P（Partition Tolerance）分区容错性：发生网络分区时，系统仍能提供服务。

任何分布式系统都可分为三类架构：

  • CP（锁定事务资源）：所有节点的数据需要实时保持一致性，这需要锁定各分支事务的资源。当发生分区时，此期间为确保返回客户端数据的准确性且不破坏一致性，可能会因为无法响应最新数据而拒绝响应，即放弃 A 。
  • AP（尽力提供服务）：要求每个节点拥有集群的所有能力或数据，能独立处理客户端的每个请求。发生分区时，可以通过缓存后本地副本来处理请求，以达到可用性，但会出现各节点不一致性，即放弃 C 。
  • CA（本地一致性）：在不发生分区时，C、A 正常满足。一旦发生分区，会保证各子分区满足 CA 。

但是网络分区不可避免，CAP 理论就变成了在 C 和 A 中的权衡问题。

2PC、3PC，分布式事务的解决方案

2PC

2PC 中的字母含义是 P（Participant，参与者），C（Coordinator，协调者）。

2PC 即两阶段提交协议，用于解决分布式事务问题。第一阶段用于各个分支事务的资源锁定，第二阶段用于全局事务的提交或回滚：

  • 第一阶段，准备：

    1. 开启全局事务。当协调者收到客户端的请求后，它将各个分支事务需要处理的内容通过 Prepare 请求发送给所有参与者，并询问能否正常处理自己的分支事务，然后等待各个参与者的响应。
    2. 处理分支事务。当参与者收到 Prepare 请求后便锁定事务资源，然后尝试执行，记录 Undo 和 Redo 信息，但不提交分支事务。
    3. 汇报分支事务状态。参与者根据第 2 步执行的结果，向协调者汇报各自的分支事务状态，Yes 表示可以提交，No 表示不能提交。

  • 第二阶段，提交/回滚：

    1. 协调者如果收到所有的响应及所有响应都为 Yes ，就发起全局事务提交；如果没有收到全部分响应或响应中有 No，就发起全局事务回滚。
    2. 汇报分支事务状态。参与者处理完成后向协调者汇报分支事务的状态。
    3. 关闭全局事务。协调者收集到全部的反馈后，向客户端返回结果并关闭本次事务。

从 2PC 的特点能看出，它适用于追求强一致性的场景。但是也能发现，2PC 并没有什么容错。以下是其存在的几个缺陷：

  • 同步阻塞：当第一阶段完成后，第二阶段需要协调者存在且正常才能进行下去。否则协调者出现故障，就会导致各个参与者锁定的事务资源无法被释放。
  • 数据不一致：发生网络分区后，可能导致只有部分参与者接收到了提交请求，结果就是导致各个节点的数据不一致。
  • 单点问题和脑裂：单点问题就是单一协调者一旦故障就会导致 2PC 无法进行。脑裂问题就是出现多协调者（多主）时，无法解决共识问题。

3PC

3PC 即三阶段提交协议，分为询问、锁定事务资源、提交事务三阶段，并引入了超时机制。但这里的超时机制是为解决同步阻塞问题，当参与者等待协调者的请求超时后，将会执行默认的提交/中断指令。

  • 阶段一，询问：
    1. 协调者收到客户端开启事务的请求后，会向所有的参与者发送包含事务内容的询问请求，询问是否可以执行本次事务。
    2. 参与者收到请求后，先检查自身健康（与协调者的连接、自身处理事务能力等）并判断能否执行以及是否会与其他事务冲突。
    3. 根据检查情况，返回 Yes 或 No。
  • 阶段二，预提交：
    1. 根据参与者的响应，在一定时间内响应不全（超时等）或是有 No 就终止全局事务，反之向所有参与者发起预提交。
    2. 参与者收到请求后，锁定事务资源，然后尝试执行，记录 Undo 和 Redo 信息，但不提交分支事务。
    3. 汇报分支事务状态。
  • 阶段三，提交/回滚：
    1. 根据参与者的响应，在一定时间内响应不全（超时等）或是有 No 就终止全局事务，反之向所有参与者发起全局提交。
    2. 参与者处理完成后向协调者汇报分支事务的状态。
    3. 向客户端返回结果并关闭本次事务。

3PC 增加了一个询问阶段，就降低了事务资源锁定的范围，不会一上来就锁定。同时超时机制也解决了同步阻塞问题。

Seata

Seata 是解决微服务架构下分布式事务的框架。

Paxos

Paxos 算法分为基础的 Basic Paxos 和 经过 Lamport 优化后提出的 Multi Paxos 。下面的算法讲解基于 Basic Paxos 。

基本概念

  • 状态机（State Machine）：是一种计算机程序或系统的行为模型，它通过描述一系列状态以及在不同状态下的转移条件和动作来描述系统的行为。
  • 容错：在系统运行时对故障的容忍程度。
  • 共识：在对等的成员集合中，让每个成员都认可某一个值。
  • 多数派（Quorum）：在一个集群中超过一半以上的成员组成的集合，即成员个数大于 $N/2+1$ 。多数派的设定可以在保证安全的情况下有效地提高容错性，少数派就是允许出现故障的数量。
  • 提案编号：指一个单调递增的整数，它标识着一轮协商，提案协商之前需要生成一个全局唯一的提案编号。
  • 提案：由提案编号和提案指令组成的实体。

角色分类

  • 提议者（Proposer）：是算法的发起者，它驱动协商的进程，相当于会议的主持人。
  • 接受者（Accepter）：是提案的决策者，相当于会议的参会人员。
  • 学习者（Learning）：不参与提案的发送和决策，只是被动的接受提案选定的结果，相当于普通民众。

算法流程

Basic Paxos 算法可分为三个阶段：

  • 准备阶段，协商过程的开始：
    • 提议者生成一个提案编号，并向所有接受者发送包含提案编号的准备请求。当接受者收到提案后，会根据约定的规则决定是否需要响应准备请求：
      • 如果提案编号大于该接受者已经通过的提案中的最大提案编号，则通过准备请求，并承诺在当前准备请求的响应中，加上已经批准的接受请求的最大编号的提案指令。如果接受者没有批准过任何接受请求，返回空。
      • 如果提案编号小于等于该接受者已经通过的提案中的最大提案编号，则拒绝本次准备请求，不响应请求。
    • 如果接受者通过了准备请求，则对提议者做出以下承诺：
      • 不再通过编号小于等于本次提案的提案编号的准备请求。
      • 不再批准编号小于该提案编号的接受请求。
      • 如果接受者已经批准过编号小于该提案编号的接受请求，则承诺在本次准备请求的响应中加入已经批准过的接受请求的最大编号的提案指令。如果接受者没有批准过任何接受请求，返回空。
  • 接受阶段：
    • 提议者收到多数派的响应后，向接受者发送接受请求，此时的接受请求包含提案编号和提案指令。接受者收到接受请求后，做出以下反馈：
      • 如果接受者没有通过编号比接受请求的编号还大的准备请求，则批准该接受请求，并返回已通过的最大编号。
      • 如果接受者已通过编号更大的准备请求，则拒绝本次接受请求，并返回已通过的最大编号。
    • 如果多数派的接受者批准了该接受请求，说明提案已达成共识。反之，需要回到准备阶段重新开始协商。
  • 学习阶段，不属于协商阶段，主要作用是将已达成共识的提案交给学习者进行处理，然后执行状态转移操作。如何让学习者知道提案是否已达成共识，这里只介绍这一种最简单的方案，就是进行提议者同步：
    • 协商过程中，只有提案对应的提议者才知道提案是否已达成共识和最终达成共识的真正提案，所以只要有提案达成共识，那么由提议者立即将该提案发送给学习者。

Multi Paxos，对 Basic Paxos 的优化

Basic Paxos 需要多轮才能对一个提案达成共识，所以协商效率很低。Lamport 提出了运行一轮就可以使多个值、多个指令达成共识的 Multi Paxos：

  • 引入领导者（Leader）角色，只能由领导者发起提案，减少了活锁的概率。
  • 在没有提案冲突的情况下，省略准备阶段，由此优化为一阶段。

Multi Paxos 在执行一次准备阶段的任务，获得了多数派接受者的承诺之后，后续连续的提案只需要执行接受阶段的任务即可。因为领导者认为接受者一定会批准自己后续提出的提案。

Multi Paxos 也允许多主的存在，并允许它们同时发起提案，只要每个领导者按照算法约定运行，便不会影响其算法安全性。为什么？

  • 在一个接受者承诺了新领导者的提案编号之后，意味着之前对其他领导者承诺的提案编号将失效，之前领导者发起的接受请求自然会被拒绝。

在 Multi-Paxos 中，领导者的选举过程并非通过显式的投票机制完成，而是通过算法本身的特性隐式产生：

  • Multi-Paxos 并未设计独立的领导者选举流程，而是通过提案竞争和全局承诺机制自然形成。当某个提议者连续成功提交提案时，其他节点会默认接受其领导地位，暂停自身提案以避免冲突。这一过程类似于“抢占式协调”，而非传统的主节点投票。
  • 具体解释就是：若提议者的提案编号持续被多数派接受（未被更高编号打断），则该提议者实质上成为领导者，后续提案可跳过准备阶段直接提交。

Raft

基本概念

  • 任期（term）：Raft 将时间分割为不同长度的任期，任期使用连续单调递增的整数，并随着 RPC 消息在成员之间交换。Raft 使用任期作为领导者的任期号：

  • 每个 Raft 成员在本地维护自己的任期。

  • 在每轮领导者选举之前递增自己的任期。

  • 每个 RPC 消息都携带自己本地的任期。

  • 每个 Raft 成员都拒绝处理小于自己本地任期的 RPC 消息。

  • 成员状态：

    • 跟随者（Follower）：只会处理和响应来自领导者和候选人的请求。如果客户端与其通信，跟随者只会将请求重定向到领导者。
    • 候选人（Candidate）：如果领导者故障或跟随者等待心跳超时，跟随者会变成候选人，新的领导者只能从候选人中产生。
    • 领导者（Leader）：当一个候选人获得来自多数派的选票后就变成领导者，负责处理客户端请求、日志复制管理、心跳消息管理。
    • 无投票权成员：新成员上线时，先以学习者身份加入，快速和领导者完成数据对齐。
    • 见证者（Witness）：只投票但不存储数据的成员，对存储资源的需求小。

    Raft 是强领导者模式的算法，日志项只能由领导者复制给其他成员，所有日志以领导者为基准。

  • 运行阶段：

    • 领导者选举：集群启动之初或领导者出现故障就需要启动选举进程。
    • 日志复制：领导者可以接收客户端请求并正常进行处理，由领导者向跟随者同步日志项。

  • RPC 消息分类：

    • 请求投票消息：用于选举领导者。
    • 追加条目消息，用于以下场景：领导者与跟随者的日志复制、心跳检测、日志对齐。
    • 快照传输消息。
    • 快递超时消息：用于领导者切换，可立即发起选举。

领导者选举

领导者选举会在以下情况触发：

  • 心跳超时：跟随者在预先规定的时间内没收到领导者的心跳，转换为候选人。
  • 任期自增：候选人将当前任期+1，发起投票请求。
  • 投票规则：每个成员每任期只能投一票（先到先得），需满足日志最新性检查。

在新的领导者被选举出来之后会面临一个日志对齐问题，如果用一些额外的机制来确保日志同步，就违背了 Raft 追求简单的理念，故而通过在选举阶段设置投票规则，来自然的让新领导者一定拥有所有最新的已提交日志：

  • 任期长的成员拒绝投票给任期短的请求投票消息。
  • 最后一条日志项编号大的成员拒绝投票给最后一条日志项编号小的成员。
  • 每个成员每任期只能投一票（先到先得）。

候选人为了获得选举的胜利，必须要与多数派通信，因此在多数派中一定存在一个成员拥有最完整的已提交的日志项。

当一个候选人获得多数派的选票后，就进入领导者状态，然后周期性向所有跟随者发送心跳消息（追加条目消息）来维持自己的领导地位。当候选人收到了追加条目消息，并且消息中的任期大于自己的任期，那么就会退出候选人状态变为跟随者。若没有成员获得多数派选票，选举就有可能会无限循环，这种现象称为分割选举（Split Vote）。

每位成员都有一个自己的随机等待心跳超时，如果心跳超过约定时间，就会进入候选人状态并发起选举。这个设定降低了多个成员同时发起选举概率，降低分割选举的可能性。极端情况下，有多个候选人同时发起选举，此时每个候选人都为每次选举设置了随机等待选票的超时，所以即使选票被瓜分，超时机制也控制了下一次发起选举的成员数量。所以，在选举过程中的超时有两层含义：随机等待心跳超时、堆积等待选票超时。

为了保证领导者的稳定，心跳间隔时间非常重要。以下是一个时间设置的参考：

  • 消息交互时间 « 心跳间隔时间 « 平均故障时间

消息交互时间远小于心跳间隔时间是为了避免在消息传输过程中出现延迟、阻塞而引发领导者选举。而平均故障时间不由人为控制。

日志复制

在 Raft 中数据都以日志项形式保存，日志中每个元素都有固定编号，具体的结构如下：

  • 每条日志包含Term（写入时的领导者任期）、Index（全局递增索引）、Command（客户端请求）。
  • 所有已提交的日志必须被所有节点最终应用。

Raft 规定日志索引必须是连续的，不允许出现空洞。

日志复制的流程：

  1. 客户端请求：领导者将命令追加到本地日志（未提交）。

  2. 并行推送：向所有跟随者发送追加条目消息，包含前一条日志的任期和索引。

  3. 跟随者验证前一条日志的任期和索引是否匹配：

    • 若匹配则追加新日志，返回成功。

    • 若不匹配返回失败，触发日志对齐。

  4. 当新日志被多数派持久化后，领导者将其标记为已提交。

  5. 领导者和跟随者按顺序将已提交索引前的日志应用到状态机。

日志对齐

日志对齐通常发生在跟随者追随领导者之初或者跟随者落后于领导者数据时，下面是检测冲突的方法：

  • 领导者为每个跟随者维护一个 nextIndex 字段，即预计发送的下一条日志索引。
  • 当追加条目消息因日志不一致失败时：
    1. 领导者将 nextIndex 递减。
    2. 重新发送 nextIndex 开始的日志 。
    3. 重复以上直到找到跟随者日志中最后匹配上的条目。

当检测到冲突后，会采取两种强制覆盖措施：

  • 删除冲突：跟随者在收到有效的追加条目消息后，删除所有与领导者发送的日志相冲突的条目。
  • 幂等写入：即使重复发送相同日志，跟随者也不会产生重复条目。

幽灵日志

幽灵日志指未提交的旧日志，即前任领导者已复制到部分跟随者但未提交的日志项。新的领导者有更大的任期，所以就有可能覆盖掉旧日志，导致其无法提交。

Raft 通过两个限制解决了幽灵日志问题：

  • 选举限制：新的领导者必须包含所有已提交日志。
  • 提交限制：领导者只能显式提交当前任期的日志，旧任期的日志只能通过提交新任期日志间接提交。

安全性

Raft 必须时刻保证以下安全要求：

  • 选举安全性：一个任期内只能选出一个领导者。
  • 领导者只追加日志项：不能以任何形式删除或覆盖领导者的日志项，领导者只会追加日志项。
  • 日志匹配：对于索引、任期一致的日志项，它们一定有相同的内容，且在该日志项之前的所有日志项也完全一致。
  • 领导者完整性：如果一个日志项被提交了，那么其必然存在于后续任期较高的领导者中。
  • 状态机安全性：所有成员按日志索引顺序应用日志项，不允许跳跃或重复。