从协议到算法:解读分布式一致性的核心机制

引言

在现代计算领域,分布式系统已成为众多应用的标准架构,通过将数据和计算任务分散到多个独立节点上,极大地提升了系统的可扩展性和容错能力。然而,随着系统规模的增长和分布特性的增强,如何确保数据一致性成为一项重要而复杂的挑战。事务一致性是数据库系统中维护数据准确性和可靠性的关键因素,但在分布式环境中,由于节点独立性和网络通信的不确定性,实现事务一致性变得尤为困难。

为应对这一挑战,分布式一致性协议和算法应运而生。它们在分布式系统中起着至关重要的作用,旨在保证多个节点在执行某项操作后能够保持一致的状态,从而确保集群中数据的一致性和系统的稳定性。通过这些协议和算法,分布式系统可以在面对网络延迟、节点故障甚至网络分区时,依然实现数据的一致性和高可用性。

两阶段提交协议 (2PC)

概念

两阶段提交协议(Two-Phase Commit,2PC)是一种用于确保分布式系统中事务一致性的协议。它的基本思想是在提交事务之前,通过协调者(Coordinator)向所有参与者(Participator)确认是否能够提交,然后根据所有参与者的响应决定提交还是回滚事务。2PC通常用于需要强一致性的分布式数据库系统中。

流程

投票阶段(Vote)

  • 协调者向所有参与者发起投票请求。
  • 参与者执行事务并写入Undo和Redo日志,但不提交。
  • 参与者回应准备就绪(YES)或失败(NO)。

Pasted image 20240802100143.png

写入Undo和Redo日志与提交的关系
  • 写入Undo和Redo日志是事务处理过程中重要的步骤,它们用于支持事务的持久性和原子性。但是,仅仅写入这些日志并不等同于提交事务
  • 提交事务的操作除了可能包括写入Undo和Redo日志外,还包括确保这些更改被永久性地写入数据库的存储介质中(如硬盘),并且使这些更改对其他事务可见。
  • 在许多数据库系统中,提交事务的操作还包括一个“提交点”(Commit Point),在这一点上,数据库会确保所有相关的日志条目都已被安全地写入磁盘,并且事务的更改也被持久化。一旦达到提交点,事务就被认为是“已提交”的,其更改成为永久性的。

提交阶段(Commit)

协调者根据参与者的响应决定提交或中断事务。

  • 提交事务(所有参与者均反馈YES时):
    1. 协调者向所有参与者发送 commit 请求。
    2. 参与者提交事务。
    3. 参与者释放事务期间占用的资源。
    4. 参与者回应 ACK 确认。
    5. 协调者收到所有参与者反馈的 ACK 消息后,完成事务提交。
  • 中断事务(任何一个参与者反馈NO,或者协调者等待所有参与者的反馈超时时):
    1. 协调者向所有参与者发送 rollback 请求。
    2. 参与者回滚事务。
    3. 参与者释放事务期间占用的资源。
    4. 参与者回应 ACK 确认。
    5. 协调者收到所有参与者反馈的 ACK 消息后,完成事务中断。

Pasted image 20240802100118.png

优点

  • 实现简单:2PC 的协议流程比较简单,易于实现和理解。目前,绝大多数关系型数据库都采用 2PC 来完成分布式事务处理。
  • 保证一致性:在没有网络分区的情况下,2PC 能够确保数据一致性,即所有参与者要么全部提交,要么全部回滚。

缺点

  • 同步阻塞:在提交阶段,所有参与者必须等待协调者的最终决策,这可能导致长时间的资源锁定,牺牲了可用性。
  • 单点故障:协调者的故障会导致参与者一直处于锁定状态,整个事务将无法完成,甚至可能导致数据不一致。
  • 分区敏感:2PC协议为了保证数据的强一致,实际上选择的是 CAP 理论中的 CA 部分,不能容忍网络分区异常。网络分区会导致参与者无法收到协调者的指令,可能出现只有部分参与者接收并执行了 commit 请求,从而导致节点数据的不一致。

三阶段提交协议 (3PC)

概念

三阶段提交协议(Three-Phase Commit,3PC)是对 2PC 的改进,旨在解决 2PC 中的同步阻塞和单点故障问题。3PC 将 2PC 的 Vote 阶段拆分为 CanCommitPreCommit 阶段,进一步细化了事务的提交过程,从而提高了系统的性能和网络延迟的容忍性。

流程

准备阶段(CanCommit)

  • 协调者向所有参与者发出包含事务内容的 canCommit 请求
  • 参与者回应准备就绪(YES)或失败(NO)。

预提交阶段(PreCommit)

协调者根据参与者的响应决定预提交或中断事务。

  • 提交事务(所有参与者均反馈YES时):
    1. 协调者向所有参与者发送 preCommit 请求。
    2. 参与者执行事务并写入Undo和Redo日志,但不提交。
    3. 参与者回应 ACK 或 NO。
  • 中断事务(任何一个参与者反馈NO,或者协调者等待所有参与者的反馈超时时):
    1. 协调者向所有参与者发送 abort 请求。
    2. 参与者中断事务。
Note

在等待协调者请求过程中出现超时,参与者会中断事务

Pasted image 20240802110926.png

提交阶段(DoCommit)

协调者根据参与者的响应决定提交或中断事务。

  • 提交事务(所有参与者均反馈 ACK 时):
    1. 协调者向所有参与者发送 doCommit 请求。
    2. 参与者提交事务。
    3. 参与者释放事务期间占用的资源。
    4. 参与者回应 ACK 确认。
    5. 协调者收到所有参与者反馈的 ACK 消息后,完成事务提交。
  • 中断事务(任何一个参与者反馈NO,或者协调者等待所有参与者的反馈超时时):
    1. 协调者向所有参与者发送 abort 请求。
    2. 参与者回滚事务。
    3. 参与者释放事务期间占用的资源。
    4. 参与者回应 ACK 确认。
    5. 协调者收到所有参与者反馈的 ACK 消息后,完成事务中断。
Note

在等待协调者请求过程中出现超时,参与者会直接提交事务

Pasted image 20240802111014.png

优点

  • 减少同步阻塞:3PC 协议在 CanCommit 不占用资源,只进行校验,减少了不必要的资源浪费。
  • 降低单点故障影响:在 PreCommit 阶段,参与者在等待协调者请求超时时会中断事务;在 DoCommit 阶段,参与者在等待协调者请求超时时将继续提交事务

缺点

  • 实现复杂:相比于2PC,3PC的实现更加复杂,需要处理更多的状态和消息。
  • 数据不一致问题依然存在:DoCommit 阶段中,如果协调者请求中断事务,但因故障或网络分区无法同部分参与者正常通信,这部分参与者会继续提交事务,从而导致节点数据的不一致。

Paxos

介绍

无论是 2PC 或 3PC,均无法彻底解决分布式的一致性问题。

Quote

There is only one consensus protocol, and that’s “Paxos” — all other approaches are just broken versions of Paxos

世界上只有一种共识协议,就是 Paxos,其他所有共识算法都是 Paxos 的退化版本。

—— Mike Burrows,Inventor of Google Chubby

Paxos 算法是一个解决分布式系统中一致性问题的一种共识算法(Consensus Algorithm),由莱斯利·兰伯特(Leslie Lamport)于1990年提出。在 Paxos 算法中,每次运行以达成一致选择一个值的过程称为一个实例(instance)。Paxos 是少数在工程实践中被证实的强一致性、高可用、去中心的分布式协议。

什么是共识算法

所谓共识,就是达成一致性的方法与过程。共识算法能够让分布式系统内部暂时容忍存在不同的状态,但最终能够保证大多数节点的状态达成一致;同时,能够让分布式系统在外部看来始终表现出整体一致的结果。这个让系统各节点不受局部的网络分区、宕机、执行性能或者其他因素影响,都能最终表现出整体一致的过程,就被称为各个节点的协商共识(Consensus)。

共识算法建立在状态机复制(State Machine Replication)模型的基础上。状态机复制模型的核心在于状态机的一个关键特性:当所有状态机起始于相同状态,并接收并执行完全相同的命令序列时,它们最终会达到相同的状态。这一特性被巧妙地应用于多参与者系统的共识机制中,意味着系统中的每个参与者(即状态机实例)需从相同的基础状态出发,遵循完全一致的指令序列进行状态更新。

根据状态机的特性,要让多台机器的最终状态一致,只要确保它们的初始状态是一致的,并且接收到的操作指令序列也是一致的即可,无论这个操作指令是新增、修改、删除抑或是其他任何可能的程序行为,都可以理解为要将一连串的操作日志正确地广播给各个分布式节点。广播指令与指令执行期间,允许系统内部状态存在不一致的情况,即并不要求所有节点的每一条指令都是同时开始、同步完成的,只要求在此期间的内部状态不能被外部观察到,且当操作指令序列执行完毕时,所有节点的最终的状态是一致的,这种模型就被称为状态机复制。

Paxos 协议用于在多个副本之间在有限时间内对某个决议达成共识。Paxos 协议运行在允许消息重复、丢失、延迟或乱序,但没有拜占庭错误的网络环境中,它利用“多数派 (Majority)”机制保证了 2F+1 的容错能力,即 2F+1 个节点的系统最多允许 F 个节点同时出现故障。

在本小节中 Paxos 均特指最早的 Basic-Paxos 算法。

概念

核心概念

  • 提案(Proposal):提案包括提案编号和提案值。
  • 提议者(Proposer):提出提案的角色。Proposer 生成提案编号,并向 Acceptor 发送提案请求。Paxos 是一种合作协议,类似于无锁无等待算法。Proposer 的职责并非确保其提案值被选中,而是辅助推进流程
  • 接受者(Acceptor):接受提案的角色。Acceptor 会根据提案编号决定是否接受提案。
  • 学习者(Learner):不参与提案,也不参与决策,只了解已经达成共识的提案的角色。Learner 通过观察多数派 Acceptor 的接受情况来确定提案值是否被最终批准(chosen)
  • 约束:在一次 Paxos 算法的执行实例中,只批准一个提案值(只要提案值是一样的,批准多个提案不会违背约束)。

使用 Paxos 算法的分布式系统里的,所有的节点都是平等的,它们都可以承担以上某一种或者多种的角色,不过为了便于确保有明确的多数派,Acceptor 的数量应该被设定为奇数个,且在系统初始化时,网络中每个节点都知道整个网络所有 Acceptor 的数量、地址等信息。

基础逻辑

Paxos 算法分为两个主要阶段:准备阶段(Prepare Phase)和接受阶段(Accept Phase)。

准备阶段(Prepare Phase)

  • Proposer 生成提案编号
    • Proposer 生成一个全局唯一且递增的提案编号 n
  • 发送 Prepare 请求
    • Proposer 向集群中的 Acceptor 广播发送 Prepare 请求,该请求包含提案编号 n
  • Acceptor 响应 Prepare 请求
    • 收到后 Prepare 请求后,Acceptor 将会给予 Proposer 两个承诺与一个应答:
      • 两个承诺是指:
        1. 承诺不会再接受提案编号小于等于 n 的 Prepare 请求。
        2. 承诺不会再接受提案编号小于 n 的 Accept 请求。
      • 一个应答是指:
        • 向 Proposer 发送响应数据 Promise,包含提案编号 n其之前接受(Accepted)的最大编号的提案值(如果有的话)。
    • 如果与承诺相悖,即收到的提案编号小于等于之前收到的提案编号,Acceptor 会忽略该请求。

Pasted image 20240802142340.png

关于提案编号

在 Paxos 算法中,提案编号并非由算法自身生成,而是由外部指定并传入。根据不同的应用场景和业务需求,我们可以自定义提案编号的生成规则,只需确保提案编号是递增的数值即可。具体实现方式如下:

  • 在单一 Proposer 的场景下,可采用自增ID或时间戳作为提案编号。
  • 在两个 Proposer 的场景中,可以分别采用奇数(如1、3、5、7…)和偶数(如2、4、6、8…)作为提案编号。
  • 在多 Proposer 的环境中,可以为每个节点分配一个唯一的 ServerId(例如1、2、3、4…),然后采用自增序号与 ServerId 的组合(如 自增序号 ‘.’ ServerId)或时间戳与ServerId的组合(如 timestamp ‘.’ ServerId)作为提案编号,例如:1.1、1.2、2.3、3.1、3.2或1693702932000.1、1693702932000.2、1693702932000.3。
  • 当 Proposer 在发起 Prepare 请求后未获得超过半数的响应时,需要更新自己的提案编号,并重新发起一轮 Prepare 请求。

接受阶段(Accept Phase)

Proposer 发送 Accept 请求

如果 Proposer 从超过半数的 Acceptor 处收到 Prepare 请求的响应,它将向集群中的 Acceptor 广播发送 Accept 请求,该请求包含提案编号 n 和提案值 v

Accept 请求的提案值是什么
  • 如果 Proposer 接收到的 Promise 响应中包含 Acceptor 之前已接收的提案,则选择最大提案编号对应的提案值作为当前 Accept 请求的提案值,这种设计的目的是为了能够更快的达成共识。
  • 如果所有 Promise 响应的提案值均为空,则 Proposer 可以自行决定一个提案值。
Acceptor 处理 Accept 请求
  • 如果 Acceptor 收到的 Accept 请求的编号 n 等于其承诺的提案编号,则 Acceptor 接受该提案并持久化提案编号和提案值
  • 如果与承诺相悖,Acceptor 会忽略该请求。
  • Acceptor 接受提案后发送包含提案编号和提案值的 Accepted 消息给 ProposerLearner
最终值的选择

每当 Acceptor 接受一个新的提案时,都会将提案值发送给 Learner。Learner 统计所有 Acceptor 的提案值,如果某个提案值被超过半数的 Acceptor 接受,则批准该提案,并将该值同步给集群中的所有需要了解最终决策的 Proposer 和 Acceptor,之后结束当前提案过程。

在实际业务场景中,Learner 可能由多个节点组成,每个 Learner 都需要“学习”到最新的投票结果。关于 Learner 的实现,Lamport 在其论文中给出了下面两种实现方式:

  1. 选择一个 Learner 作为主节点用于接收提案值,其他 Learner 节点作为备份节点。主节点接收到数据后再同步给其他 Learner 节点。该方案的缺点是存在单点故障风险,如果主节点宕机,则无法获取到投票结果。
  2. Acceptor 接受提案后,将提案值广播给所有 Learner,每个 Learner 再将提案值广播给其他 Learner 节点。这样可以避免单点故障问题,但缺点是涉及多次消息传递,效率要低于上一种方案。

示例

  • Acceptor 未接受过提案的时序图:

    Pasted image 20240802143717.png

  • Acceptor 接受过提案后的时序图:

    Pasted image 20240802144457.png

    Info

    > Acceptor1 和 Acceptor2 已经接受过提案,它们的 Promise 响应中包含了之前的提案 (1, ‘apple’)(2, ‘banana’),Proposer 选择之前最大提案编号的提案值作为 Accept 请求的提案值,即 banana

优点

  • 强一致性:Paxos 保证了在分布式系统中,即使部分节点发生故障,也能达成一致的决策。这种强一致性对于需要严格保证数据正确性的系统至关重要。
  • 容错性强:Paxos 能够在多数节点正常工作的情况下继续运行。它允许少数节点出现故障而不影响系统的整体功能。
  • 避免脑裂:Paxos 的核心在于“多数派”原则,即一个提案要在集群中被批准,必须得到超过半数的节点同意。这意味着即使集群被分割成多个部分,也只能有一个部分能够形成多数派,而其他部分由于节点数量不足,无法独立达成共识。

缺点

Paxos 的价值在于开拓了分布式共识算法的发展思路,但它因有如下缺陷,一般不会直接用于实践:

  • 实现复杂:Paxos 的实现较为复杂,涉及多个阶段和细节处理,特别是在处理失败和超时方面,并且只能对单个值形成决议。
  • 性能较低:决议的形成至少需要两次网络请求和应答(Prepare 和 Accept 阶段各一次),高并发情况下将产生较大的网络开销。
  • 活锁问题:在某些情况下,Proposer 之间可能会频繁地互相打断彼此的提案,导致没有提案能够成功提交。

总之,Paxos 是一种很学术化但对工业化并不友好的算法,现在几乎只用来做理论研究。实际的应用都是基于 Multi Paxos 和 Fast Paxos 算法的。

什么是活锁

活锁是指系统虽然没有陷入死锁,但由于各个进程频繁地相互干扰,导致没有进程能够取得进展的情况。
在 Paxos 中,活锁通常发生在多个 Proposer 同时提出提案,导致提案不断地被否决和重试,但始终无法达成一致。

Pasted image 20240802151232.png

活锁如何解决

活锁有可能自行解开,但该过程的持续时间可长可短并不确定,这与具体的业务场景实现逻辑、网络状况、提案重新发起时间间隔等多方面因素有关。
解决活锁问题,有以下常见的方法:

  1. 当 Proposer 接收到响应,发现支持它的 Acceptor 小于半数时,不立即更新编号发起重试,而是随机延迟一小段时间,来错开彼此的冲突。
  2. 可以设置一个 Proposer 的 Leader,集群全部由它来进行提案,等同于下文的 Multi-Paxos 算法。

Multi-Paxos

前文介绍了 Paxos 算法的基本流程,但存在两个主要问题:

  1. 集群内所有 Proposer 都可以发起提案,可能导致活锁问题;
  2. 每次发起提案都需要经过反复的 Prepare 和 Accept 流程,涉及多次网络交互,影响程序的执行效率。

考虑到以上两个问题,能不能在保障分布式一致性的前提下避免活锁情况的发生,以及尽可能减少达成共识过程中的网络交互,基于这种目的随即产生了 Multi-Paxos 算法。

理想的共识达成过程应是这样的:在多个 Proposer 的环境中,一个 Proposer 广播一次 Prepare 请求并获得多数响应,随后广播一次 Accept 请求,一旦获得多数同意,共识即告达成。然而,现实情况中,多个 Proposer 可能同时发送消息,导致冲突,且在网络不稳定时,消息可能延迟或丢失,迫使重新发起提案,降低效率。Multi-Paxos 算法旨在解决这些问题。

Multi-Paxos 算法在保持集群节点平等的同时,引入了主次节点的概念,以减少不必要的网络交互。该算法通过选举出一个主 Proposer 节点来避免上述问题。集群中的 Proposer 节点通过定期发送心跳包来监控主节点的存在。一旦检测到主节点失活,Proposer 节点会向Acceptor 节点发送申请,表明其希望成为新的主节点。当获得多数节点的同意后,该Proposer 便成为主节点。

在主节点存在的情况下,集群中的提案仅由主节点提出,其他 Proposer 不再提案,从而避免了活锁问题。由于只有一个节点负责提案,消除了冲突的可能性,因此无需发送 Prepare 请求,只需发送 Accept 请求,显著减少了网络协商的次数。

相关应用

Chubby 和 Boxwood 均使用 Multi-Paxos。

Zookeeper 使用的 ZAB(Zookeeper Atomic Broadcast)也是 Multi-Paxos 的变体。

应用场景示例

场景描述

在一个分布式数据库中,假设包含3个节点。客户端访问时通过负载均衡请求到某个节点,并通过 Paxos 算法保证分布式数据库3个节点中的数据一致性。为了方便阐述,我们对实际分布式数据一致性的流程进行了简化。

Pasted image 20240805090659.jpg

分布式数据库中的每个节点都存储三类数据:事务日志数据、数据库数据(DB数据)、事务日志执行位置。

  • 事务日志表:存储数据库的操作日志记录,包括写入 Put、修改 Update 和删除 Delete 等操作日志。事务日志表可以被看做是状态机的命令序列。
  • DB数据表:存储具体的业务数据。
  • 事务日志执行位置:记录当前节点执行到哪一条操作记录。

Pasted image 20240805090852.jpg

快照

随着数据不断写入,事务日志表的数据量不断增加。可以通过快照方式,将某个时间点之前的数据备份到磁盘。这样,宕机恢复时直接从快照点开始恢复,可以提高恢复效率。

整体设计思想

为了保证所有节点执行相同的事务日志,我们采用了 Paxos 共识算法的一系列单独实例,实例 i 确定的值是事务日志中的第 i 个操作。每个节点在算法的每个实例中扮演所有角色(Proposer、Acceptor 和 Learner)。

注意

Paxos 中的提案编号与事务日志索引没有直接关系,每个 Paxos 实例与特定的事务日志索引相关联;而提案编号的作用是作为共识达成过程中的一个重要机制,确保即使在多个提议者存在的情况下,所有节点也能对同一索引的操作达成一致。

初始状态

  • 系统启动后,所有节点的事务日志表和数据表均为空,且 OperateIndex 设置为0。
  • 客户端 C1、C2 有序向系统发起写请求:C1 请求 Put(a,'1'),C2 请求 Put(b,'1')

流程说明

  1. 请求接收

    • Server1 接收 C1 的 Put(a,'1') 请求,并不直接写入数据表,而是启动 Paxos 实例1以达成共识。
  2. Prepare 请求

    • Server1 作为 Proposer,对所有节点(包括自己)发起 Prepare(n) 请求,其中n是提案编号。
  3. Promise 响应

    • Server1 收到过半节点的 Promise 响应后,发出 Accept(n, '{"Op1": "Put(a,'1')"}') 请求。此时三个节点达成共识,实例1结束,事务日志表均为:{"Op1": "Put(a,'1')"}
  4. 写入操作

    • 达成共识后,Server1 执行写入操作,此时 Server1 的 OperateIndex 为1,其他节点仍为0。Server1 的数据表为:a = 1,另外两个节点的数据表为空,三个节点的事务日志表相同,当前写入流程结束。

Pasted image 20240805091108.png

继续处理后续请求

Paxos 实例1完成后,Server2 继续处理 C2 的请求。

  1. 检查事务日志表

    • Server2 检查事务日志表和 OperateIndex,按顺序执行遗漏的操作。
  2. Prepare 请求

    • Server2 的 OperateIndex 更新后,开始 Paxos 实例2,发起 Prepare(n) 请求。
  3. Promise 响应

    • 接收到过半数的 Promise 响应后,Server2 发送 Accept(n, '{"Op1": "Put(b,'2')"}') 请求,并得到 Accepted 响应。此时三个节点达成共识,实例2结束,事务日志表均更新为:{"Op1": "Put(a,'1')", "Op2": "Put(b,'1')"}
  4. 执行写入

    • 达成共识后,Server2 执行写入操作,此时 Server2 的 OperateIndex 为2,其他节点仍为1。Server2 的数据表为:a = 1, b = 1,其他节点的数据表仍为空,三个节点的事务日志表相同,当前写入流程结束。

读操作示例

当 Server3 接收到 Get(a) 请求时:

  1. 检查操作记录

    • Server3 比对 OperateIndex 与事务日志表,执行遗漏操作以确保数据一致性。
  2. 执行读取

    • 由于 Get 请求不涉及写入和修改数据,理论上不需要发起 Paxos 协商。

执行流程示意图如下:

Pasted image 20240805092807.png

提案的体现

在决定日志单个索引的值的过程中,可以有多个提案。

假设在 Paxos 实例1未完成时,即 C1 的请求还未写入事务日志前,客户端 C3 向 Server3 发起一个写请求,那么该请求也会参与到 Paxos 实例1中。

Server3 发送 Prepare(nh) 请求,其中 nh > n。得到多数响应,Acceptor 承诺不在接受提案编号小于 nh 的提案

  • 如果 Server1 还未发送 Accept 请求,那么当它尝试发送时,会因为提案编号小于 nh 而被多数节点拒绝。
  • 如果 Server1 已经发送了 Accept 请求,并且从至少一个 Acceptor 那里得到了 Accepted 响应,但在 Server3 发送 Prepare(nh) 请求之前还未完成 Accept 阶段;Server3 在 Prepare 阶段会发现至少有一个 Acceptor 已经接受了 Server1 的提案。在这种情况下,Server3 为了遵守 Paxos 算法规则,在 Accept 阶段必须发送 Accept(nh, 'Put(a,'1')') 请求,即采用与 Server1 相同的提案值

小结

Paxos 算法虽然概念简单,但在实际实现中由于需要处理各种故障情况,其复杂性较高。Paxos 的变种,如 Multi-Paxos 和 Raft,针对不同应用场景进行了优化和改进,广泛应用于现代分布式系统中。

Raft

介绍

鉴于 Paxos 算法因其高度复杂性及实现难度,显著限制了其在实际应用中的广泛推广,而分布式系统领域又亟需一种高效而易于实现的分布式一致性算法,在此背景下,Raft 算法应运而生。

Raft是一种共识算法。与 Paxos 不同,Raft 强调的是易懂性(Understandability)。为了达成这个目标,Raft 主要做了两方面的事情:

  1. 运用了分而治之的策略,将复杂的算法逻辑解构为三个清晰独立的子问题:领导者选举(Leader Election)、日志复制(Log Replication)以及安全性(Safety);
  2. 对算法做出一些限制,减少状态数量和可能产生的变动。

Raft 不是拜占庭容错(BFT)算法,节点信任当选的领导者。

Raft 还引入了联合共识(Joint Consensus)这一新机制,允许线上进行动态的集群扩容,利用有交集的大多数机制来保证安全性。

概念

先介绍两个非常优秀的网站:

  1. The Secret Lives of Data-CN 以图文方式介绍 Raft 算法,是非常好的入门材料。将其阅读完后您大概率已经了解了 Raft 算法,如果您仍有疑问可以回来继续阅读本文。
  2. Raft Scope 是 Raft 官方提供的互动式演示程序,它展示了 Raft 集群的工作状态。您可以用它模拟节点宕机、心跳超时等各种情况。有了 Raft Scope 我们可以亲自“动手”观察 Raft 集群是如何工作、如何处理各种故障的。

核心概念

Raft 算法通过选举出的领导者来在集群内达成共识。在 Raft 集群中,每个节点的角色明确分为领导者(Leader)、追随者(Follower),以及在特定选举情境下(当 Leader 不可用时)可能成为的候选者(Candidate)。Leader 的核心职责是将日志条目(log entry)复制给所有 Follower,以确保数据一致性。为实现这一点,Leader 定期向 Follower 发送心跳消息,以此宣示其存在和活动状态。

Raft 集群有且只有一位当选的 Leader,该 Leader 完全负责管理集群其他节点上的日志复制。这意味着 Leader 可以决定新条目的放置位置以及它与其他节点之间数据流的建立,而无需与其他节点协商。Leader 会一直在任,直到发生故障或断开连接,在这种情况下,幸存的节点会选出新的领导者。

每个 Follower 内部维护一个选举超时计时器,其时长随机设定在150~300毫秒之间,用于等待来自 Leader 的心跳信号。一旦接收到有效的心跳消息,该计时器会被重置。若超时时间内未接收到心跳,则 Follower 会认为当前 Leader 可能已失效或网络分区发生,随后自动转变为 Candidate 状态,并启动新一轮的领导者选举过程,以恢复集群的正常运作和共识机制。

节点之间通信方式

Raft 集群节点之间通过 RPC 交互,只需要两种 RPC 消息:RequestVoteAppendEntries。另外,RPC 都是幂等的,发起 RPC 是并行的。

RequestVote RPC

用于领导者选举。Candidate 会向其他节点发送 RequestVote 请求,征求选票。

请求体

1
2
3
4
5
6
{
"term": 5, // Candidate 的任期号
"candidateId": "A", // Candidate 的ID
"lastLogIndex": 10, // Candidate 最后日志条目的索引值
"lastLogTerm": 4 // Candidate 最后日志条目的任期号
}

响应体

1
2
3
4
{
"term": 5, // 当前节点的任期号
"voteGranted": true // 当前节点是否投票给 Candidate
}

AppendEntries RPC

用于日志复制和心跳检查。Leader 通过发送 AppendEntries 消息向 Follower 复制日志条目,同时也可以作为心跳消息,防止 Follower 超时。

请求体

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
{
"term": 5, // Leader 的任期号
"leaderId": "A", // Leader 的ID
"prevLogIndex": 10, // 紧邻新日志条目之前的那个日志条目的索引值
"prevLogTerm": 4, // 紧邻新日志条目之前的那个日志条目的任期号
"entries": [ // 需要存储的日志条目(可以为空,用于心跳)
{
"index": 11,
"term": 5,
"command": "set x=10"
},
{
"index": 12,
"term": 5,
"command": "set y=20"
}
],
"leaderCommit": 8 // Leader 已经提交的日志的索引值
}

响应体

1
2
3
4
5
{
"term": 5, // 当前节点的任期号
"success": true, // 如果 Follower 包含了匹配上 prevLogIndex 和 prevLogTerm 的日志条目时为真
"matchIndex": 12 // 成功追加的日志条目的索引值(只有在 success 为 true 时包含)
}

领导者选举

当现有 Leader 发生故障或算法初始化时,需要选举新的 Leader。这时,集群内将开启一个新的任期(term)。term 用于将时间划分为不同的逻辑周期,用一个单调递增的整数表示。每个 term 都以领导人选举开始。如果选举成功完成(即选举出单个 Leader),则该任期内将由新 Leader 负责正常运作(normal operation)。如果选举失败,该任期结束,新的任期开始,并进行新一轮的选举。

Pasted image 20240806144929.png

领导者选举由 Candidate 启动。在一段时间内如果 Follower 没有收到 Leader 的心跳,它会增加自己的任期号,再成为 Candidate,为自己投票,然后向集群中的所有节点发送请求投票消息(RequestVote)来开始选举。每个节点在一个任期只能投票一次,只能投给任期号大于等于自己任期号的 Candidate,并按先到先得的原则投票。

说明

每个节点都会维护一个当前任期号 (current term)。当一个节点收到任期号更大的 RequestVoteAppendEntries 时,它必须更新自己的任期号;如果该节点是 Candidate 或者 Leader ,它必须要“放下身段”变为 Follower。如果节点接收到一个任期号小于其维护的当前任期号的请求,它将拒绝该请求。

根据 Candidate 从集群中其他节点收到的响应,可以得出选举的三个结果:

  1. 收到超过半数的选票,则该节点成为 Leader,开始发送心跳消息。
  2. 收到来自 Leader 的心跳消息,如果 Leader 的任期号大于等于自己当前的任期号,则它会转变为 Follower,并承认该 Leader 的合法性。
  3. 如果以上两种情况都未发生(比如由于票数分散),每个 Candidate 会在选举超时后增加任期号,并启动新一轮选举
为什么选举超时时长是随机的

为了最大程度地减少票数分散的情况,这样 Follower 几乎不可能同时成为 Candidate。

Pasted image 20240806133321.jpg

日志复制

在Raft中, Leader 负责日志复制和接收客户端请求,每个请求包含一个将在集群中被复制状态机执行的命令(command)。

具体步骤

  1. Leader 将 command 作为一个新的日志条目(log entry)追加到自己的日志中,然后将该请求以 AppendEntries 消息的形式发送给所有 Follower。
  2. 如果 Follower 没有响应,Leader 会无限期地重试发送 AppendEntries 消息,直到日志条目被所有 Follower 存储为止。
  3. 一旦 Leader 收到超过半数的 Follower 确认日志条目已经被复制,它就会将该条目应用到本地状态机,并认为该请求已经提交(committed)。这一事件也会使得 Leader 日志中的所有之前的条目被间接提交。
  4. 当 Follower 得知一个日志条目已被提交后,它会将该条目应用到自己的本地状态机。这确保了集群中所有服务器日志的一致性,从而保证了日志匹配的安全规则。
关于提交

一个日志条目被“提交”,意味着这个条目已经被大多数节点复制,并且即使当前 Leader 故障,这个条目也不会被未来的 Leader 删除或覆盖。换句话说,一旦一个日志条目被提交,它就成为了系统状态的一部分,并且最终会被所有节点应用。

处理 Leader 故障

如果 Leader 故障,日志可能会出现不一致。旧 Leader 的一些日志条目可能已经复制到部分 Follower 但还未提交,而新 Leader 可能不具备这些日志条目。在这种情况下,新 Leader 会强制 Follower 覆盖它自己的日志(因为这些日志条目尚未提交,不违背外部一致性)。具体步骤如下:

  1. 日志比较:新 Leader 会与每个 Follower 比较日志,找到它们最后一致的条目
  2. 删除和替换:然后,新 Leader 会删除 Follower 中在这个关键条目之后的所有日志条目,并用自己的日志条目覆盖它们

安全性

Raft 确保了以下关键安全特性:

  • 选举安全:在任何给定的任期内,最多只能有一个 Leader 被选举出来。这是通过以下机制实现的:
    • 每个节点在一个任期只能投票一次;
    • 只有获得大多数投票才能当任 Leader。
  • Leader Append-Only:Leader 只能在其日志的末尾追加新的条目,而不能修改或删除已存在的条目。这保证了日志的顺序性和一致性。
  • 日志匹配:如果两份日志中的两个条目具有相同的索引和任期号,那么在这两个条目之前(包括这两个条目本身)的所有日志条目在这两份日志中都是相同的。
  • Leader 完整性:一旦一个日志条目在某个 Leader 的任期内被提交,那么从该任期开始,所有后续的 Leader(包括当前 Leader 和未来通过选举产生的 Leader)的日志中都将包含这个已提交的日志条目。这确保了即使发生 Leader 变更,已提交的日志条目也不会丢失。
  • 状态机安全:如果某个节点已经将某个特定的日志条目成功应用到了其状态机上,那么其他任何节点都不能在同一任期号和索引上为该日志条目应用不同的命令。这一特性确保了所有节点的状态机在执行相同日志序列后的状态是一致的。为了维持状态机安全:
    • Candidate 在选举过程中必须包含之前任期已提交的所有日志条目。如果 Follower 的日志比 Candidate 的日志更(即 Follower 的日志包含更新的任期号或更高的索引),Follower 将拒绝投票给该 Candidate。日志的新旧通过比较任期号和索引来确定,具体地,任期号大的更新,如果任期号相同,则索引大的更新
    • 值得注意的是,Leader 不会直接通过计算集群中日志条目的副本数来提交之前任期内的日志条目。然而,由于日志匹配特性,Leader 在自己任期内提交的日志条目会间接导致之前任期的日志条目也被提交,因为所有已提交的日志条目必须是连续的。
  • Follower 故障:如果 Follower 故障,其他节点发送的 AppendEntriesRequestVote 将失败。为了应对这种情况,集群中的其他节点会持续不断地尝试与已宕机的 Follower 建立联系,直到 Follower 恢复。如果某个请求在 Follower 故障之前已经被其接收并处理,当 Follower 重新启动并再次接收到这一请求时,它将忽略该请求(幂等)。
  • 时间和可用性:Raft 算法整体不依赖于客观时间,即使在面对网络延迟或 RPC 通信顺序混乱的情况下,其正确性依然不受影响。Raft 维持一个稳定 Leader 的关键在于系统需满足以下时间条件:broadcastTime(广播时间) << electionTimeout(选举超时时间) << MTBF(平均故障时间)。
    • 广播时间:即一次RPC请求从发送到接收完整响应的时间,这一时间跨度极大地受到存储技术的影响,通常范围在0.5毫秒至20毫秒之间。由于 Raft 的 RPC 机制要求接收方将信息持久化到磁盘,因此这一时间相对较长,但仍是可预测的。
    • 选举超时时间:是 Raft 算法中用于触发新选举的关键参数,它必须显著大于广播时间,以确保在 Leader 可能存在的情况下,足够的 RPC 请求能够完成而不会误触发新的选举。同时,选举超时时间也应远小于系统的平均故障时间,以避免在短暂的故障期间频繁进行不必要的选举。基于广播时间的范围,选举超时时间通常设定在10毫秒至500毫秒之间,以平衡响应速度和系统稳定性。
    • 平均故障时间:代表系统组件(如服务器)在两次故障之间平均无故障运行的时间,对于大多数服务器而言,这一时间通常以月或年为单位计算,远远超过了选举超时时间的设定范围。

相关应用

  • Etcd 使用 Raft 来管理其内部的高可用复制日志。
  • MongoDB 内部实现了一种称为“复制协议”的机制,该机制与 Raft 有许多相似之处,特别是用于维护多个数据副本之间的一致性和选主(选举Leader)的过程。这可以视为 Raft 的一个变体应用。
  • TiDB 采用了 HTAP(混合事务/分析处理)架构,其核心组件之一 TiKV 是一个基于 Raft 的分布式事务型键值数据库。TiKV 使用 Raft 来确保数据的强一致性和高可用性,即使在多个节点出现故障时也能保证数据不丢失且服务不中断。
  • ClickHouse 利用 Raft 来实现类似 Zookeeper 的服务,比如用于配置管理、服务发现或分布式锁等场景。
  • Apache Kafka 使用 Raft (KRaft)来管理元数据,从而减少对外部系统的依赖。

优点

  • 易于理解和实现:相比于其他共识算法如 Paxos,Raft 算法的设计更加直观和易于理解,使得开发人员能够更容易地实现和调试。
  • 安全性:Raft 算法通过领导者选举和日志复制等机制来确保数据的一致性和可靠性,提供了较高的安全性。
  • 高可用性:在 Leader 失效时,Raft 算法能够快速进行新的领导者选举,从而保证系统的高可用性。
  • 强一致性:Raft 算法通过多数投票机制来确保系统的安全性,任何一条已提交的日志条目都必须在多数节点上复制并最终应用到其状态机,这保证了数据的一致性。

缺点

  • 性能开销:对于每个写操作,Raft 算法都必须通过 Leader 进行处理和复制。因此,当 Leader 的负载过高时,可能会成为系统的瓶颈,影响性能和响应时间。
  • Leader 单点故障:在 Raft 算法中,Leader 扮演着关键角色,负责处理所有客户端请求并协调日志复制。一旦 Leader 失效,不仅会导致与客户端的直接连接中断,还可能引发一系列问题,如提交状态的不确定性增加,客户端难以确认提交的最终状态。这种不确定性进一步影响了系统的整体性能和可用性。
  • 选举期间的服务中断:当 Leader 发生变更时,系统可能会经历短暂的服务中断。这种中断可能会影响系统的可用性和性能,特别是在频繁发生选举的情况下。
  • 扩展性限制:Raft 的性能和延迟在大规模集群(如数百个节点)中可能会受到影响。Leader 的负载和日志复制的开销在大规模集群中会显著增加,影响系统的扩展性。

总结

分布式一致性协议和算法是保障现代分布式系统稳定性和数据一致性的核心组件。在本文中,我们探讨了两阶段提交(2PC)和三阶段提交(3PC)协议,以及 Paxos 和 Raft 这两种分布式一致性算法的原理与特点。2PC 和 3PC 通过分阶段协调节点操作,实现事务的一致性,但它们在应对网络分区和节点故障时存在不同的优缺点。相比之下,Paxos 和 Raft 等一致性算法旨在提供容错能力和稳定的领导者选举,能够在更复杂和动态的网络环境中保持集群一致性。

随着分布式系统的广泛应用,这些协议和算法不仅成功解决了事务一致性的关键问题,还奠定了系统高可用性、良好的扩展性以及稳定运行的基础。深入理解和掌握这些核心机制,对于架构师和开发人员在设计及优化分布式系统时至关重要,能够帮助他们做出更加明智、有根据的决策,从而确保系统能够有效应对现实中的各种挑战和复杂情况。

参考

分布式事务 | 2PC与3PC 详解_2pc和3pc-CSDN博客

分布式共识算法 | 凤凰架构 (icyfenix.cn)

Paxos (computer science) - Wikipedia

一篇文章让你弄懂分布式一致性协议Paxos_paxos 协议-CSDN博客

共识算法 — PBFT、Raft和Paxos_pbft raft-CSDN博客

分布式共识算法 Raft - 知乎