选举算法Fencing

本文目录导读：

1. 核心问题：为什么需要 Fencing？
2. Fencing 的核心原理：单调递增的 Fencing Token
3. 常见的 Fencing 实现方式
4. Fencing 与 选举算法的关系
5. 典型的 Fencing 工作流程图

在分布式系统和共识算法中，Fencing（隔离/ fencing） 并不是一个独立的选举算法，而是一个防御机制或安全策略，它通常与 Leader Election（领导者选举） 算法配合使用，用来解决脑裂（Split-Brain） 或幽灵领导者（Zombie Leader） 的问题。

下面我来详细解释它的原理、实现方式以及它与选举算法的关系。

核心问题：为什么需要 Fencing？

在分布式系统中，我们通常使用选举算法（如 Paxos、Raft、ZAB）来选出一个 Leader，Leader 负责处理写操作或分发任务。

存在一种危险情况：

1. 旧 Leader 与集群断开连接（例如网络分区）。
2. 集群其他节点认为旧 Leader 挂了，于是选举出一个新的 Leader。
3. 旧 Leader 恢复连接（网络恢复），但它仍然认为自己是 Leader。
4. 系统中存在两个 Leader，它们同时尝试写入数据或操作共享资源，导致数据不一致，这就是脑裂。

Fencing 的目的就是：确保在旧 Leader 被隔离后，它无法再对共享资源进行任何写操作。

Fencing 的核心原理：单调递增的 Fencing Token

Fencing 通常通过一个 单调递增的全局令牌（Token） 来实现，这个 Token 是一个整数，每次发生 Leader 切换时,令牌值都会增加。

具体流程如下：

1. 选举产生新 Leader：新的 Leader 从协调服务（如 ZooKeeper， etcd）或一致性算法中获取一个 Fencing Token，这个 Token 的值必须比之前所有 Leader 的 Token 都大。
2. 写入资源时携带 Token：新 Leader 在向共享资源（如数据库、分布式文件系统）执行任何写操作时，必须附带自己的 Fencing Token。
3. 资源层验证 Token：共享资源层（例如一个分布式锁或存储服务）会记录最近一次成功写操作的最高 Token 值，当收到一个写请求时，它会比较请求中的 Token 与记录的 Token：
   • 如果请求的 Token 小于或等于 记录的 Token → 拒绝写入（说明这个 Leader 是旧的或已被隔离的）。
   • 如果请求的 Token 大于 记录的 Token → 接受写入，并更新记录的 Token。

关键点：由于旧 Leader 的 Token 值小，即使它恢复并尝试写资源,也会被资源层拒绝。

常见的 Fencing 实现方式

根据不同的技术栈，Fencing 有几种具体的实现方式：

租约（Lease） + 分布式锁

• 原理：Leader 通过分布式锁（如 ZooKeeper 的临时节点）获得租约,租约有过期时间。
• Fencing 机制：
  • 锁本身携带一个版本号或 epoch number。
  • 每次锁的拥有者（Leader）发生变化,版本号递增。
  • 资源服务器在执行写操作前，需要检查当前持有锁的版本号是否与请求中的一致，如果版本号过时,就拒绝操作。

ZooKeeper 的 Epoch (ZAB 协议)

• 原理：ZooKeeper 的 Zab 协议本身就实现了 Fencing。
• 机制：每个 Leader 都有一个唯一的 Epoch（纪元） 编号，当新 Leader 被选举出来时，Epoch 加 1，所有写请求（事务）都必须包含当前的 Epoch，ZooKeeper 只接受 Epoch 最高的 Leader 发来的提案。

数据库中的乐观锁或版本号

• 原理：在资源表中增加一个 version 或 lock_version 字段。
• 机制：每个 Leader 写操作时，要求 WHERE version = X SET version = X+1，如果旧 Leader 尝试写入，它持有的旧版本号 X-1 会与数据库中的 X 冲突,导致更新失败。

Fencing 与 选举算法的关系

Fencing 本身不是一个选举算法，但它极大地增强了选举算法的健壮性,它们的关系如下表所示：

一句话总结：

选举算法决定了“谁可以说话”，而 Fencing 确保了“已经不是 Leader 的人不能再说任何有效的话”。

典型的 Fencing 工作流程图

时间线 -->
1. [节点A] 当选 Leader (Token = 1)
2. [节点A] 写入数据 (Token=1) -> 资源层接受 (记录Token=1)
--- 网络分区发生 ---
3. [节点A] 与集群断开，成为旧Leader
4. [节点B, C] 选举 [节点B] 为新 Leader (Token = 2)
5. [节点B] 写入数据 (Token=2) -> 资源层接受 (记录Token=2)
--- 网络恢复，节点A 恢复连接 ---
6. [节点A] 认为自己还是 Leader，尝试写入数据 (Token=1)
7. 资源层收到请求，发现 Token=1 <= 记录的 Token=2
8. 资源层 **拒绝** 节点A的写入请求 (Fencing 生效)
9. [节点A] 从数据中发现 Token=2，意识到自己被隔离，自愿降级

• Fencing 不是选举算法，而是选举算法的安全网。
• 它通过单调递增的 Token 来标记每个 Leader 的“任期”。
• 共享资源通过检查 Token 来决定是否接受写请求,从而避免脑裂。
• 在实践中，ZooKeeper、etcd 等协调服务本身就内置了 Fencing 能力，而 Raft 协议中的 Term 和 Paxos 协议中的 Ballot Number 也是一种 Fencing 机制。

如果你正在设计一个需要 Leader 选举的系统，请一定将 Fencing 机制纳入设计，否则在高可用和网络不稳定的情况下,数据一致性很难保证。