当前位置： 首页 > news >正文

分布式选举算法：Bully、Raft、ZAB

news 2025/8/6 15:17:51

分布式选举算法：Bully、Raft、ZAB

  • Bully算法
    • 示例流程
      • 1. 主节点故障检测
      • 2. N1 发起选举
      • 3. N2、N3 回复 Alive
      • 4. N2 发起新一轮选举
      • 5. N3 最终当选
  • Raft 算法
    • 节点角色
    • 选举流程
    • 日志复制流程
    • 脑裂（网络分区）场景
      • 简单脑裂场景
      • 复杂脑裂场景
  • ZAB 算法
    • 节点角色
    • 四种状态
    • 选举过程
    • 示例：3 个服务器集群的初始化选举
    • 三个阶段
  • 总结

Bully算法

Bully 算法是一种用于分布式系统的主节点（Leader）选举算法，其核心原则是在存活的节点中，选取节点 ID 最大的节点为主节点。算法中定义了三种消息类型：

  1. Election 消息：用于发起选举。
  2. Alive 消息：对 Election 消息的回复，表明“我还活着，且 ID 比你大”。
  3. Victory 消息：当某节点成为主节点后，向其他节点广播自己的胜利。

每个节点都知道集群中其他节点的 ID，选举过程如下：

  1. 自检主节点

    • 每个节点判断自己是否是当前存活节点中 ID 最大的。
    • 如果是，则直接向所有其他节点发送 Victory 消息，宣告自己为主节点。

  2. 发起选举

    • 否则，向所有 ID 比自己大的节点发送 Election 消息，并启动计时器，等待 Alive 回复。

  3. 等待结果

    • 如果在超时时间内未收到任何 Alive 消息，则认为自己是最高 ID 节点，向全网发送 Victory 消息，成为主节点。
    • 若收到比自己 ID 大节点的 Alive 回复，则停止选举，等待其后续的 Victory 消息。

  4. 响应他人选举

    • 若节点接收到来自 ID 较小节点的 Election 消息，应立即回复 Alive 消息，告知对方“我的 ID 更大，你应让我来发起选举”。

示例流程

假设集群中有 4 个节点，ID 从小到大分别为 N1、N2、N3、N4。初始化时 N4 为主节点。
在这里插入图片描述

1. 主节点故障检测

  • N4 突然故障，集群中最先发现的是 N1。

2. N1 发起选举

N1 向所有比自己 ID 大的节点（N2、N3、N4）发送 Election 消息：
在这里插入图片描述

3. N2、N3 回复 Alive

  • N4 已故障，不会回复。
  • N2、N3 收到后，分别向 N1 发送 Alive，告知其 ID 更大，需要重新选举。

在这里插入图片描述

4. N2 发起新一轮选举

  • N2 向比自己 ID 大的 N3、N4 发送 Election 消息。

在这里插入图片描述

  • N4 无响应，N3 回复 Alive。

在这里插入图片描述

5. N3 最终当选

  • N3 向比自己 ID 大的 N4 发送 Election，因 N4 无响应，N3 自认最高并成为主节点。

在这里插入图片描述

  • 成为新主节点后，N3 向集群内所有节点广播 Victory 消息：
    在这里插入图片描述

通过上述步骤，集群实现了在主节点故障后快速、可靠的重新选举，并确保具有最高节点 ID 的结点接管领导角色。这样既简单又高效，适合节点数量有限且节点 ID 唯一且可比较的场景。

Raft 算法

Raft 算法是一种投票选举算法，遵从少数服从多数的原则，规定在一个周期内获得票数最多的节点为主节点。该算法将集群节点划分为三种角色。

节点角色

  • Leader：领导者，也就是主节点，在一个集群中同一时刻只能有一个领导者，负责协调和管理其他从节点。
  • Candidate：候选者，集群中的每个节点都有可能成为候选者，只有先成为候选者才有机会被选为领导者。
  • Follower：跟随者，它会跟随领导者，不可以发起选举。
    在这里插入图片描述

如上图 所示，集群初始化时，所有节点都是跟随者，在没有领导者的情况下，这些跟随者自然接收不到领导者的消息，经过一定时间后就会转换为候选者。候选者通过投票参与选举，如果接收到半数以上的投票就会转换为领导者。如果由于网络分区，网络中出现了更大任期（Term）领导者，那么旧的领导者会退为跟随者。候选者如果发现了新的领导者或者新的任期，会转换为跟随者。

选举流程

  1. 集群初始化
    在集群初始化阶段，各节点加入集群中，此时所有节点均为跟随者，也就是说在最初是没有领导者的。

  2. 心跳检测
    集群中如果存在领导者，就会给每个跟随者发送心跳包表示自己存在，但此时集群中并没有领导者，因此需要进行选举。

  3. 发起选举

    • 集群中所有节点都从跟随者转换为候选者，同时向其他节点发送选举请求。
    • 这里有一个选举超时控制机制（Election Timeout），用来控制节点从跟随者转换为候选者的时间，一般选取 150ms 和 300ms 之间的随机值。设置这个值的目的是避免多个跟随者同时转换为候选者。
    • 如果跟随者在选举超时控制指定的时间范围内没有接收到来自领导者的心跳包，就转换为候选者发起选举。

  4. 投票机制

    • 由于选举超时控制的时间是一定范围内的随机数，因此其他节点接收到的选举请求是有先后顺序的，接收请求的节点回复请求发起者，是否同意其成为领导者。
    • 需要注意，在每轮选举中，一个节点只能投出一张票。

  5. 当选与任期

    • 如果有候选者获得超过一半节点的投票，那么这个候选者就会成为领导者并且宣布自己的任期。任期可以理解为一个累加的数字，例如集群中第一次选举出来的领导者，其任期为 1。
    • 领导者宣布任期以后，其他节点会转变为跟随者。领导者节点会向跟随者节点定期发送心跳包，检测对方是否存活。通常来说心跳包会按照一定时间间隔发送，跟随者接收到来自领导者的心跳包以后，会回复一个消息表示已经接收到。

  6. 领导者失效与再选举

    • 当领导者出现网络延迟或者死机时，无法发送心跳包，跟随者如果在选举超时控制容忍的时间内没有接收到心跳包就会发起选举。
    • 这表明之前领导者节点的任期到了，如果之前的任期为 1，那么再选举出来的领导者的任期就是 2。
    • 当跟随者发起新选举时，当前的领导者节点会降级为跟随者，和其他跟随者一样参与新一轮选举。

注意
在 Raft 算法中，如果某一次选举时出现了平票的现象，也就是两个节点获得了一样多的票数，就将任期加 1 并重新发起一次选举，直到某个节点获得更多的票数。一旦集群中选举出了领导者，客户端的写入操作就会针对领导者展开，领导者再与跟随者同步信息完成最终值的修改。

日志复制流程

在这里插入图片描述

如上图所示，客户端通过领导者对集群中其他节点上的信息进行更新的过程：

  1. 客户端请求
    客户端将更新信息发送给领导者，此时领导者会在本地的日志中建立一个 Entry，记录这次修改。注意这个 Entry 是未提交（Uncommitted）的，即还没有进行提交操作。

  2. 日志同步
    领导者将客户端的更新信息分别提交到两个跟随者中，说白了就是将这次修改的日志副本发送给两个跟随者。

  3. 确认提交

    • 跟随者接收到更新信息后，会给领导者发送确认信息。
    • 直到接收到半数以上的确认信息后，领导者才会将客户端更新的 Entry 提交到本地的日志中保存，意思是这次更改已经发送给跟随者，并且得到半数以上的确认。
    • 与此同时，领导者还会向集群内的所有跟随者发送广播，声明这次更改已经提交了。上述整个将更新信息通知全网跟随者，并且得到确认的过程称为日志复制。

  4. 提交反馈
    最后，领导者告知客户端 Entry 已经提交。

补充
上面介绍的日志复制过程不仅在更新信息时会发生，在集群初始化、选举新领导者时也会进行。领导者会将自身保存的状态信息复制到集群的其他跟随者中，这个状态信息叫作 AppendEntries。通常是在领导者向跟随者发送心跳包的时候发送 AppendEntries。

脑裂（网络分区）场景

简单脑裂场景

在这里插入图片描述
如上图所示，由于网络问题导致集群分成了两个独立的网络，上面一个网络由领导者 1、跟随者 2、跟随者 3 组成，下面一个网络由领导者 4、跟随者 5 组成。这两个网络中的节点由于都感知不到对方的存在，因此分别在自己的网络中选举出领导者 1 和领导者 4。

在这里插入图片描述

一个集群出现两个领导者，会破坏数据的一致性。比如：

  • 客户端 1 向领导者 1 更新 Value=5 以后，领导者 1 通过日志复制的方式通知其他跟随者，并获得了超过半数的确认，因此信息为 Committed 状态，Value=5 更新成功。
  • 然后客户端 2 向领导者 4 发起 Value=8 的更新信息，由于其无法获得网络中超过半数的节点的支持，因此此次更新一直都处于 Uncommitted 状态，如上图所示。

如上图所示，此时网络恢复正常，节点之间均可以互相感知到对方。

  1. 在做心跳检测的时候，领导者 4 发现另外一个领导者 1 的任期比自己的大，因此转换为跟随者 4，然后跟随者 4 和跟随者 5 同时回滚之前的更新信息 Value=8。
  2. 当领导者 1 发送心跳给跟随者 4 和跟随者 5 时，会将 Value=5 的日志复制信息一并发送，在得到确认以后，跟随者 4 和跟随者 5 的信息都修改为 Value=5。

通过这种方式解决了脑裂问题。

复杂脑裂场景

当网络故障将集群分割成多个子网络，且每个分区中的节点数都不足以构成半数（即没有任何一个分区拥有超过 ⌈N/2⌉ 的节点），集群将进入一种特殊的“停滞”状态：

  1. 无法选举出 Leader

    • 每个分区的节点都会在各自的选举超时后升级为 Candidate，并向本地分区内的节点请求投票。
    • 由于分区内节点数 ≤ ⌊N/2⌋，任何 Candidate 最多只能获得分区内的全部票数，也就是 ≤ ⌊N/2⌋ 票，永远达不到 “超过半数” 的门槛。
    • 因此，在任意一轮选举中都不会产生 Leader，集群始终处于无 Leader 的状态。

  2. 持续重试与选举超时

    • 各节点在每轮随机选举超时（150–300 ms）到期后，会不断重新发起选举。
    • 每次都因票数不足而失败，整个集群就像“原地踏步”，直到网络拓扑或延迟模式发生变化。

  3. 服务可用性中断

    • 没有 Leader，就无法接受客户端的写请求，也无法提交任何新的日志条目。
    • 集群对外表现为读取可能仍可（读旧数据），但写操作会一直等待超时或直接失败。

  4. 恢复机制

    • 自动恢复：一旦网络分区有所整合，某个分区突然拥有了超过半数的节点，就能在接下来的选举中选出 Leader，恢复正常服务。
    • 运维介入：在生产环境中，通常会结合监控和报警，若出现“长时间无 Leader”告警，运维可手动修复网络或调整节点配置，使某个分区临时达到半数以上。

  5. 最佳实践建议

    • 优化选举超时范围：缩小 150–300 ms 的随机范围，可以减少重试间隔，尽快发现网络状态变化。
    • 网络拓扑设计：避免出现孤立小分区，如将节点分布在多个可用区（AZ）时，保证每个 AZ 内至少有 ⌈N/2⌉ 个节点。
    • 监控与告警：对“无 Leader 状态”和“连续选举失败次数”进行指标监控，配合自动化运维工具，提升恢复速度。

ZAB 算法

ZAB（ZooKeeper Atomic Broadcast）是 ZooKeeper 原子消息广播协议，其设计目的是保证集群中数据的一致性。ZooKeeper 使用一个主进程处理客户端的请求，这个主进程和 Raft 算法中的领导者很像；同时还采用 ZAB 的原子广播协议，将数据的状态变化广播给集群中的其他节点，这点和 Raft 算法中的日志复制相类似。

节点角色

  • 领导者（Leader）
    领导者负责将客户端的事务请求转换成一个提议（Proposal），并将该提议分发给集群中的所有跟随者，之后领导者需要等待所有跟随者的反馈信息，得到超过半数跟随者的反馈以后，领导者会再次向所有跟随者发布消息，告知提议已经半数通过了，并提交和提议对应的事务请求。

  • 跟随者（Follower）
    集群中的其他服务器，接收并执行领导者发布的提议，保持数据同步。

  • 观察者（Observer）
    保持观望并且没有投票权和选举权，只用于扩展读取能力，不参与事务处理。

四种状态

  1. Looking 状态
    选举状态，此时集群中不存在领导者，所有节点进入选举状态。

  2. Leading 状态
    领导状态，此时集群中已经选出领导者，它可向其他节点广播和同步信息。

  3. Following 状态
    跟随状态，此时集群中已经选出领导者，其他节点进入跟随状态并且跟随领导者。

  4. Observing 状态
    观察状态，当前节点为观察者，保持观望并且没有投票权和选举权。

选举过程

  • 在选举投票的过程中，每个节点都会记录三元组信息 (ServerID, ZXID, epoch)。

    • ServerID：节点 ID
    • ZXID：处理的事务 ID，它越大表示处理的事务越新
    • epoch：选举轮数，一般用逻辑时钟表示，选举的轮数越多这个数字越大

  • 每个节点通过二元组 (vote_serverID, vote_zxid) 来表明投票给哪个节点：

    • vote_serverID：被投票节点的 ServerID
    • vote_zxid：投票节点的事务 ID

  • 选举的原则：

    1. ZXID 最大的节点成为领导者；
    2. 若 ZXID 相同，则 ServerID 大的节点成为领导者。

示例：3 个服务器集群的初始化选举

  1. 第一步

    • 集群初始化时，由于所有节点都没有感知到领导者的存在，因此发起选举，进行第一轮投票，即 epoch=1。
    • 由于此时还没有处理任何事务，因此 3 个节点的 ZXID 都为 0。
    • 此时每个节点都会推选自己作为领导者，并向集群中的其他 2 个节点广播投票信息。
      在这里插入图片描述

  2. 第二步

    • 三个节点交换信息以后发现，ZXID 都是 0，难分伯仲。
    • 于是比较 ServerID，将 ServerID 较大的节点推选为领导者，
    • 节点 1 和节点 2 会更改投票信息为 (3,0)，然后发送给集群中的其他节点，也就是选举节点 3 作为领导者。
    • 此时节点 3 的 ID 是最大的，因此没有参与投票。在这里插入图片描述

  3. 第三步

    • 集群中所有服务器都把票投给了节点 3，因此节点 3 当选为集群的领导者。
    • 节点 3 进入 Leading 状态，节点 1 和节点 2 作为跟随者进入 Following 状态。
    • 完成第三步以后，领导者会向其他服务器同步信息，如果有客户端的事务请求要处理，还会发送提议信息。

三个阶段

  1. 发现阶段（Discovery）
    该阶段要求集群必须选举出一个领导者，这个领导者要维护集群中的可用跟随者的列表，从而保证与跟随者节点之间通信的顺利进行。

  2. 同步阶段（Sync）
    既然发现阶段已经能够保证领导者与跟随者之间的通信，那么在这个阶段，领导者就需要同步自身保存的数据与跟随者节点中的数据，这个和 Raft 算法中的日志复制是一个意思。这个过程会用到 CAP 理论。

  3. 广播阶段（Broadcast）
    领导者可以接收客户端需要处理的事务请求，并以提议的形式广播给所有跟随者。

总结

至此，我们介绍了三种选举算法的机制和原理。实际上，选举算法的初衷是解决集群中如何选择领导者的问题。由于在分布式互斥和分布式事务中都会引入事务协调者，来协调分布式进程或者节点之间的关系，在解决协调问题的同时又对事务协调者的可用性提出了要求，因此通过集群的方式提高协调者的可用性。在集群中谁是领导者、谁是跟随者，以及如何选举领导者都是选举算法要解决的问题。这里我们把上面介绍的三种算法做一个总结和比较，如下表所示。
在这里插入图片描述

http://www.lryc.cn/news/611348.html

相关文章：

  • 【深度学习新浪潮】TripoAI是一款什么样的产品？
  • ORACLE多表查询
  • GaussDB 常见问题-集中式
  • 【带root权限】中兴ZXV10 B863AV3.2-M_S905L3A处理器刷当贝纯净版固件教程_ROM包_刷机包_线刷包
  • Java set集合讲解
  • 最长连续序列(每天刷力扣hot100系列)
  • python学智能算法（三十三）|SVM-构建软边界拉格朗日方程
  • 利用 Radius Resource Types 扩展平台工程能力
  • avue---upload 图片上传
  • Vue3核心语法进阶（Props）
  • 从汇编角度揭秘C++构造函数（1）
  • 【Lua】题目小练8
  • 超越注意力机制
  • Augmodo AI：零售门店智能货架管理平台
  • 8月5号打卡
  • Java: jwt 入门介绍（Introduction to JSON Web Tokens）
  • ENS-317 Modbus TCP / 通用模式网关
  • Shader开发（七）创建第一个Shader项目
  • 完整设计 之2： 变形金刚机器人Transformer
  • 最优化中常见的优化理论
  • Guava 与 Caffeine 本地缓存系统详解
  • Windows 11 使用Windows Hello使用人脸识别登录失败，重新录入人脸识别输入PIN后报Windows Hello安装程序白屏无响应的问题解决
  • nodejs 编码初体验
  • 艺术性与真实感并存：FLUX.1 Krea [dev] 开源模型速览
  • muc中的电压调节和电源控制回路？
  • 网络相关(AI回答)
  • Linux的NFS与Autofs配置指南
  • linux定时器管理 timer_*系统调用及示例
  • table行内--图片预览--image
  • 并发编程的三要素是什么