分布式系统 #03：分布式协调与选举

本文系统梳理分布式系统中的协调与选举技术：分布式锁的三种方案对比、分布式 ID 的生成策略、一致性哈希的原理与虚拟节点、服务注册与发现的选型，以及 Bully/ZAB 等 Leader 选举算法。读完能在工程中做出有依据的方案选择。

相关文章：分布式一致性 · 分布式事务 · 分布式系统设计模式 · 金融级分布式系统实践

目录

分布式锁

分布式锁是在分布式环境下，实现多进程对临界资源互斥访问的标记机制。

为什么需要分布式锁

单机的线程锁（synchronized、ReentrantLock）只能管控同一进程内的并发，无法管控跨机器的并发访问。

典型场景：电商库存扣减。用户 A 和用户 B 同时读到库存为 2，A 买走 1 个后库存变为 1，但 B 的请求基于旧的库存数据执行，导致超卖。

三种实现方案

方案一：基于数据库

原理：创建一张锁表，利用数据库唯一性约束实现互斥。获取锁 = 插入记录，释放锁 = 删除记录。

-- 锁表
CREATE TABLE distributed_lock (
    resource_name VARCHAR(64) NOT NULL UNIQUE,  -- 资源名（唯一约束）
    holder        VARCHAR(64) NOT NULL,          -- 锁持有者
    created_at    DATETIME    NOT NULL
);

-- 获取锁（成功则持有，失败则等待）
INSERT INTO distributed_lock(resource_name, holder, created_at)
VALUES ('inventory:sku001', 'server-1', NOW());

-- 释放锁
DELETE FROM distributed_lock WHERE resource_name = 'inventory:sku001';

问题：

• 单点故障：数据库宕机导致整个系统不可用
• 死锁：锁没有超时机制，持有锁的进程崩溃后锁永远不释放
• 性能差：频繁磁盘 IO，不适合高并发

方案二：基于 Redis（推荐高并发场景）

原理：利用 Redis 的 SET key value NX PX 命令实现原子性的加锁，value 为唯一标识（防止误删他人的锁）。

# 获取锁：key 不存在时设置，并设置过期时间（防死锁）
SET lock:inventory:sku001 {uuid} NX PX 30000

# 释放锁：Lua 脚本保证原子性（先验证是自己的锁，再删除）
if redis.call("GET", KEYS[1]) == ARGV[1] then
    return redis.call("DEL", KEYS[1])
else
    return 0
end

优点：

• 性能极高（内存操作）
• 支持自动过期，防死锁
• 可跨集群部署，避免单点故障

缺点：

• 超时时间难以精确设定（业务执行时间不确定）
• Redis 主从切换时可能出现锁丢失（Redlock 算法可缓解）

方案三：基于 ZooKeeper（推荐高可靠场景）

原理：利用 ZooKeeper 的临时顺序节点实现分布式锁。

/lock/
  ├── lock-0000000001  ← 编号最小，持有锁
  ├── lock-0000000002  ← 监听前一个节点
  └── lock-0000000003  ← 监听前一个节点

流程：

1. 在 /lock/ 下创建临时顺序节点
2. 获取所有子节点，判断自己的编号是否最小
3. 若最小 → 获得锁；若不最小 → 监听前一个节点的删除事件
4. 前一个节点删除（持有者释放锁或宕机）→ 收到通知 → 重新判断

优点：

• 可靠性最高，天然解决死锁（临时节点在会话断开后自动删除）
• 公平性好（按创建顺序获取锁）
• 支持读写锁

缺点：

• 性能不如 Redis（需要频繁创建/删除节点）
• 依赖 ZooKeeper 集群

羊群效应：若监听父节点（所有子节点），锁释放时所有等待者同时被唤醒，大量无效通知。解决方案：每个节点只监听前一个节点，而非所有节点。

三种方案对比

生产推荐：高并发场景选 Redis（注意 Redlock 或 Lua 脚本保证原子性）；对可靠性要求高的场景选 ZooKeeper（Curator 框架封装完善）。

分布式 ID

分布式系统中，多个节点同时生成 ID，需要保证全局唯一性，同时满足有序性、高性能等要求。

方案对比

雪花算法（Snowflake）详解

Twitter 开源的分布式 ID 生成算法，生成 64 位整数：

| 符号位（1bit） | 时间戳（41bit） | 机器ID（10bit） | 序列号（12bit） |
|      0        |  毫秒级时间戳   |  最多1024台机器 |  每毫秒4096个  |

• 时间戳（41bit）：相对于某个起始时间的毫秒数，可用约 69 年
• 机器 ID（10bit）：可部署 1024 台机器，通常拆分为 5bit 数据中心 + 5bit 机器编号
• 序列号（12bit）：同一毫秒内最多生成 4096 个 ID

时钟回拨问题：

• 服务器时钟被调整到过去的时间，可能生成重复 ID
• 解决方案：检测到时钟回拨时，等待时钟追上（小回拨）或抛出异常（大回拨）；或使用逻辑时钟代替物理时钟

号段模式详解

数据库记录：
| biz_tag | max_id | step | update_time |
| order   | 1000   | 1000 | ...         |

本地缓存号段：[1, 1000]，用完后再取 [1001, 2000]

• 每次从数据库取一批号段（如 1000 个），在内存中分配
• 减少数据库访问频率（1000 个 ID 只需 1 次数据库请求）
• 双 buffer 优化：当前号段用到 10% 时，异步加载下一个号段，避免取号段时的延迟

一致性哈希

一致性哈希解决了普通哈希在节点增减时大量数据迁移的问题，是分布式存储中数据路由的核心算法。

普通哈希的问题

hash(key) % N：当节点数 N 变化时，几乎所有 key 的映射都会改变。

3 节点 → 4 节点：需迁移约 75% 的数据
10 节点 → 11 节点：需迁移约 91% 的数据

一致性哈希原理

将整个哈希值空间（0 ~ 2^32-1）组织成一个虚拟圆环（哈希环）：

flowchart LR
    subgraph 哈希环
        direction TB
        A["节点A\n(hash=100)"] --> B["节点B\n(hash=200)"]
        B --> C["节点C\n(hash=300)"]
        C --> A
    end
    k1["key-01\n(hash=150)"] -->|顺时针找到第一个节点| B
    k2["key-02\n(hash=250)"] -->|顺时针找到第一个节点| C
    k3["key-03\n(hash=50)"] -->|顺时针找到第一个节点| A

寻址规则：对 key 计算哈希值，在哈希环上顺时针找到第一个节点，该节点负责存储此 key。

节点变化影响范围：

• 节点宕机：只影响该节点到前一节点之间的数据（重新映射到下一个节点）
• 新增节点：只影响新节点到前一节点之间的数据

3 节点 → 4 节点：只需迁移约 25% 的数据（理论上 1/N）
10 节点 → 11 节点：只需迁移约 9% 的数据

虚拟节点解决数据倾斜

当节点数量少时，节点在哈希环上分布不均匀，导致数据访问冷热不均（大部分请求集中在少数节点）。

解决方案：为每个物理节点创建多个虚拟节点，分散在哈希环上。

物理节点 A → 虚拟节点 A-01, A-02, A-03
物理节点 B → 虚拟节点 B-01, B-02, B-03
物理节点 C → 虚拟节点 C-01, C-02, C-03

虚拟节点数量越多，数据分布越均匀。实践中每个物理节点通常对应 100~200 个虚拟节点。

适用场景

• 分布式 KV 存储（Redis Cluster、Memcached）
• 分布式数据库的数据分片路由
• CDN 节点选择

注意：一致性哈希适合简单的路由寻址场景，不需要维护路由信息。但不适合需要范围查询的场景（哈希后数据无序）。

服务注册与发现

服务注册与发现解决微服务架构中"服务 A 如何找到服务 B 的 IP 和 Port"的问题。

核心问题

1. 统一的中介存储：调用方在唯一的地方获取被调用服务的所有实例信息
2. 状态更新与通知：服务实例的信息能够及时更新并通知到服务调用方

工作原理

sequenceDiagram
    participant S as 服务实例（被调用方）
    participant R as 注册中心
    participant C as 调用方
    Note over S,R: 服务注册（心跳续约）
    S->>R: 注册：IP=10.0.0.1, Port=8080, TTL=90s
    loop 每30秒
        S->>R: 心跳续约
    end
    Note over C,R: 服务发现（订阅变更）
    C->>R: 订阅服务B的实例列表
    R-->>C: 返回当前实例列表
    Note over R,C: 实例状态变更时通知
    R->>C: 推送变更（实例上线/下线）
    Note over S: 实例崩溃，停止心跳
    Note over R: 90秒后自动清除该实例
    R->>C: 推送变更（实例下线）

主流方案对比

AP vs CP 的选择

推荐选 AP（如 Eureka、Nacos AP 模式）：

服务发现是整个分布式系统的基石，可用性是最关键的设计目标。原因：

• 服务注册（心跳续约）本身就是最终一致性的
• 服务发现（订阅变更）也是最终一致性的
• 获取到稍旧的实例信息，最多导致一次请求失败（可重试）
• 完全不能获取实例信息，会导致整个调用链路不可用

类比：整个互联网的服务发现系统就是 DNS，它是一个典型的 AP 系统（DNS 记录更新有延迟，但保证高可用）。

Leader 选举

分布式集群需要一个主节点（Leader）来协调和管理其他节点，保证集群有序运行和数据一致性。

Bully 算法（霸道总裁）

原则："长者为大"，ID 最大的活跃节点成为 Leader。

流程：

1. 检测到 Leader 宕机，发起选举
2. 向所有 ID 比自己大的节点发送 Election 消息
3. 若在超时时间内未收到 Alive 响应 → 自己成为 Leader，广播 Victory 消息
4. 若收到 Alive 响应 → 等待对方发送 Victory 消息

典型应用：MongoDB 副本集故障转移（以最后操作时间戳作为 ID）。

Raft 选举（民主投票）

见 10 分布式一致性 - Raft 协议 章节。核心：随机超时 + 大多数票。

ZAB 选举（有优先级的民主投票）

ZooKeeper Atomic Broadcast 的选举算法，在 Raft 基础上增加了数据新鲜度的考量。

选举原则：server_zxID（数据 ID）最大者优先；相同则 server_id 最大者当选。

节点状态：Looking（选举中）→ Leading（主节点）/ Following（跟随者）/ Observing（观察者，无投票权）

三阶段流程：

sequenceDiagram
    participant S1 as Server-1
    participant S2 as Server-2
    participant S3 as Server-3
    Note over S1,S3: 初始状态，所有节点 Looking，各推选自己
    S1->>S2: 投票 <epoch=1, vote_id=1, zxID=0>
    S1->>S3: 投票 <epoch=1, vote_id=1, zxID=0>
    S2->>S1: 投票 <epoch=1, vote_id=2, zxID=0>
    S2->>S3: 投票 <epoch=1, vote_id=2, zxID=0>
    S3->>S1: 投票 <epoch=1, vote_id=3, zxID=0>
    S3->>S2: 投票 <epoch=1, vote_id=3, zxID=0>
    Note over S1,S3: 比较：zxID 相同，server_id 最大为 3
    S1->>S2: 更新投票 → vote_id=3
    S2->>S1: 更新投票 → vote_id=3
    Note over S3: 收到多数票，成为 Leader
    S3->>S1: Victory（我是 Leader）
    S3->>S2: Victory（我是 Leader）

三种选举算法对比

为什么选奇数节点：多数派算法需要超过半数节点投票。偶数节点时，两个候选人各获一半票会导致选举失败，需重新投票。奇数节点（3、5、7）避免了这种平票情况，且容错能力相同（3 节点和 4 节点都只能容忍 1 个节点故障）。

参考资料

• 《分布式技术原理与算法解析》— 聂鹏程（极客时间）
• 《分布式协议与算法实战》— 韩健（极客时间）
• 《深入浅出分布式技术原理》— 陈现麟（极客时间）
• Consistent Hashing and Random Trees — David Karger et al.
• ZooKeeper: Wait-free coordination for Internet-scale systems