Java 学习知识库

主题

分布式 ID 与一致性哈希 ​

S6-015选修高级约 60 分钟JDK 21Java 高级与架构 · 分布式

1. 本节定位 ​

分布式系统有两件「分配」的老问题：ID 怎么发才不重号、数据怎么分才少搬家。本节把两个问题都做成可运行实验：

★ 四组一手实测 ✓✓：

text
雪花实测：单线程 359 万个/秒（逼近每毫秒 4096 的上限）✓✓
时钟回拨：THROW 直接拒绝 / WAIT 等 50ms / BORROW 用未来时间 ⚠️
迁移对比：取模 3→4 台要搬 74.8% ✗✗ ｜ 一致性哈希只搬 27.3% ✓✓
虚拟节点：不加 node-1 独占 99.1% ✗✗ → 加 150 个后 30.2/33.7/36.1% ✓✓

2. 学习目标 ​

  • 说清主键用 UUID 的代价与雪花的优势 ★★★；
  • 能实现雪花算法并解释 41/10/12 位结构 ★★★；
  • 知道时钟回拨的三种策略与选择标准 ★★★；
  • 能解释一致性哈希为什么比取模少搬数据、虚拟节点为什么必要 ★★★。

3. 前置知识检查 ​

4. 为什么需要这个知识 ​

★ 两个「看不见的地基」，出事就是大事 ✗✗：

问题出事的后果
ID 重复 / 主键乱序 ✗✗✗数据覆盖、索引页分裂、插入变慢（《索引》）
扩容导致缓存全量重分布 ✗✗✗「加机器把系统加挂了」—— 缓存瞬间击穿（《缓存穿透、击穿与雪崩》）

5. 核心概念 ​

5.1 ID 方案谱系 ★★ ​

方案有序性性能缺点
数据库自增有序 ✓受单库限制 ✗分库分表后冲突、扩展难
UUID无序 ✗✗本地生成 ✓✓36 字符、索引页分裂、不可读
雪花（Snowflake）趋势递增 ✓✓本地生成，实测 359 万/秒 ✓✓✓依赖时钟（回拨风险 ⚠️）
号段模式有序 ✓批量取号，性能高 ✓依赖中心存储（DB/Redis）
Redis INCR有序 ✓高 ✓多一次网络往返、Redis 成依赖 ⚠️

★ 结论 ✓✓：互联网业务的主流默认是雪花（或号段） —— 本地生成 + 趋势递增 + 8 字节 ✓✓。

5.2 雪花的结构与容量（实测）★★★ ​

text
生成的 ID  : 228375873370222592
二进制形式 : 1100101011010110101010010110010111100000000111000000000000
结构拆解   : 时间戳（相对纪元）=54449051230 | 机器 ID=7 | 序列=0
位段位数容量换算
时间戳（相对自定义纪元）41 位2^41 ms≈ 69 年 ✓
机器 ID10 位1024最多 1024 台发号机 ✓
序列号12 位4096每毫秒 4096 个 ✓

★ 吞吐实测 ✓✓✓：单线程生成 100 万个 ID 用时 278ms → 约 359 万个/秒 —— 逼近理论上限（4096 × 1000 ≈ 409 万/秒），序列用尽会自动等下一毫秒 ✓。

★★ 两条工程约定 ✓✓：workerId 必须全局规划（K8s 里用 StatefulSet 序号 / 注册中心分配，重复 = 撞号 ✗✗✗）； 自定义纪元（epoch）不是必须从 1970 开始（早用早得，能延长可用年限）✓。

5.3 时钟回拨：必须提前设计（实测）★★★ ​

text
策略 A（THROW）：抛错 → 时钟回拨 50ms，拒绝生成 ✗✗（直接拒绝服务）
策略 B（WAIT）：检测到回拨 50ms，等时钟追平后继续 ✓（多等约 50ms，换来不重复）
策略 C（BORROW）：借用 lastTimestamp 继续 → 仍生成 15099494404097 ⚠️
策略行为代价
THROW拒绝发号服务短暂不可用 ✗
WAIT等到追平调用方多等（小回拨可接受）✓
BORROW沿用旧时间戳继续发「未来 ID」→ 重启后可能撞号 ⚠️✗✗

★★ 生产建议 ✓✓✓：小回拨（< 阈值，如几百 ms）等待或借用；大回拨直接拒绝 + 告警 —— 宁可短暂不可用，不可发出重号 ✓✓（回拨来源：NTP 校时、虚拟机暂停/迁移、闰秒）✓。

5.4 取模 vs 一致性哈希（实测）★★★ ​

text
取模哈希：3 台 → 4 台，需要迁移 **74.8%** 的键 ✗✗（几乎全量重分布，缓存瞬间击穿）
一致性哈希：3 台 → 4 台，需要迁移 **27.3%** 的键 ✓✓（≈ 1/4：只有新节点顺时针覆盖的那段区间）

★★ 原理一句话 ✓✓✓：取模的映射依赖「总节点数」，节点数一变、所有键的落点全乱 ✗✗； 一致性哈希把「键与节点」都映射到同一个环上，键顺时针找到的第一个节点就是归属 —— 加一个节点只影响「它与前一个节点之间的区间」 ✓✓✓。

★ 为什么是 1/4 ✓：新节点在环上随机落点，抢走的区间期望大小 = 环长的 1/新节点数 = 25% ✓。

5.5 虚拟节点：必须加，而且要多（实测）★★★ ​

text
无虚拟节点（3 个物理节点）：node-0=0.3%  node-1=99.1%  node-2=0.6%   ← 严重倾斜 ✗✗
每节点 150 个虚拟节点：    node-0=30.2%  node-1=33.7%  node-2=36.1%  ← 趋于均匀 ✓✓

★★ 倾斜的原因 ✓✓：哈希值在环上不是等距的（CRC32/MD5 也是伪随机）—— 3 个点把环切成 3 段，段的长度是随机的，运气不好就出现「一台扛 99%」✗✗。

★★ 虚拟节点的作用 ✓✓✓：把 1 台物理机「伪装」成 150 个环上成员 —— 区间被充分细分后，大数定律让份额趋于均匀，也让节点故障/扩容时的负载转移更平滑 ✓✓。

★ 工程落点 ✓：Redis Cluster 用 16384 个哈希槽（一种固定分片方案）； 分库分表（ShardingSphere）与 CDN 调度普遍用「一致性哈希 + 虚拟节点」✓✓。

6. 递进示例 ​

6.1 雪花核心代码 ​

java
synchronized long nextId() {
    long now = clock.getAsLong();
    if (now < lastTimestamp) { /* 回拨处理：THROW / WAIT / BORROW */ }
    if (now == lastTimestamp) {
        sequence = (sequence + 1) & 0xFFF;
        if (sequence == 0) { while (now <= lastTimestamp) now = clock.getAsLong(); }
    } else { sequence = 0; }
    lastTimestamp = now;
    return ((now - EPOCH) << 22) | (workerId << 12) | sequence;
}

6.2 一致性哈希的最小实现 ​

java
String route(String key) {
    Map.Entry<Long, String> entry = circle.ceilingEntry(hash(key));   // 顺时针找第一个节点
    return (entry == null ? circle.firstEntry() : entry).getValue();  // 绕回环首
}

6.3 反例：把 hash(key) % 节点数 用在缓存分片 ​

text
3 台 → 4 台：74.8% 的键换机器 → 缓存集体未命中 → 全量穿透到数据库 ✗✗✗（[S4-008]）

7. 完整可运行代码与实测 ​

代码：labs/java-deep/src/main/java/cn/kb/learn/deep/distributed/DistributedIdLesson.java

实测输出（节选）：

text
===== 2. 雪花算法：结构与吞吐实测 =====
  结构拆解   : 时间戳（相对纪元）=54449051230 | 机器 ID=7 | 序列=0
  单线程生成 1000000 个 ID：用时 278.2ms → 约 3595028 个/秒 ✓✓

===== 3. 时钟回拨：三种应对策略 =====
  策略 A（THROW）：抛错 → 时钟回拨 50ms，拒绝生成 ✗✗（直接拒绝服务）
  策略 B（WAIT）：检测到回拨 50ms，等时钟追平后继续 ✓（多等约 50ms，换来不重复）
  策略 C（BORROW）：借用 lastTimestamp 继续 → 仍生成 15099494404097 ⚠️

===== 4. 取模 vs 一致性哈希：节点扩容的数据迁移 =====
  取模哈希：3 台 → 4 台，需要迁移 **74.8%** 的键 ✗✗
  一致性哈希：3 台 → 4 台，需要迁移 **27.3%** 的键 ✓✓

===== 5. 虚拟节点：把「倾斜」压平 =====
  无虚拟节点（3 个物理节点）：node-0=0.3%  node-1=99.1%  node-2=0.6%
  每节点 150 个虚拟节点：node-0=30.2%  node-1=33.7%  node-2=36.1%

8. Debug 观察点 ​

  1. 把 workerId 改成两台机器相同：观察同一毫秒内可能撞号 ✗✗✗；
  2. 统计 100 万个 ID 的「每毫秒个数」分布：看序列如何被用尽 ✓✓；
  3. 把虚拟节点数从 1 调到 10 / 150：观察分布极差收敛的过程 ✓✓✓；
  4. 给一致性哈希加「节点下线」实验：观察它的键如何被顺时针「继承」✓✓。

9. 常见错误 ​

#错误说明
1UUID 当聚簇主键 ✗✗✗无序插入 → 页分裂 → 插入变慢 ✓✓
2workerId 不规划、靠随机 ✗✗✗撞号是概率事件，上线越久越危险 ✓✓
3时钟回拨不处理 ✗✗✗回拨窗口内必定发重号 ✓✓
4缓存分片用取模 ✗✗✗扩容即雪崩 ✓✓
5一致性哈希不加虚拟节点 ✗✗一台扛 99%，等于没分片 ✓✓
6数据迁移不预热 ⚠️搬迁期间未命中率上升（配合缓存预热/双读）✓

10. 动手实验 ​

  1. 跑 DistributedIdLesson 四段实验 ✓✓✓；
  2. 把雪花 ID 存进 PostgreSQL 并观察主键插入（对比 UUID 主键的插入耗时）✓✓✓；
  3. 用 100 万个键统计「加节点后迁移比例」，反复 5 次看波动范围 ✓✓；
  4. 实现「节点下线」场景：验证下线节点的键被顺时针后继接管、且只影响一段区间 ✓✓。

验收方式：给定「分库分表 / 缓存分片 / 全局 ID」三类需求，能各选一套方案并说清迁移与容错行为。

扩展任务：给项目 B 写一份《ID 与分片方案说明》：雪花 workerId 分配方式、回拨策略、分片算法与扩容演练 ✓✓

11. 练习题 ​

  1. 为什么 UUID 不适合做主键？雪花为什么适合？
  2. 雪花的 41/10/12 位各能撑多久 / 多少台 / 多快？
  3. 时钟回拨的三种策略各自代价？生产怎么选？
  4. 为什么取模哈希扩一次容要搬 3/4 的数据？
  5. 虚拟节点解决什么问题？不加会怎样（给实测数字）？
参考答案（要点）
  1. UUID 无序 → 索引页分裂、36 字符；雪花趋势递增 → 8 字节、可排序 ✓✓★
  2. ≈ 69 年 / 1024 台 / 每毫秒 4096 个（实测 359 万/秒） ✓✓★
  3. THROW（拒绝）/ WAIT（多等）/ BORROW（未来 ID 有撞号风险）；小回拨等待、大回拨拒绝 + 告警 ✓✓★
  4. 因为落点依赖「总节点数」：hash % 3 与 hash % 4 几乎全不同（实测 74.8%）✓✓★
  5. 环上区间切分随机导致倾斜（实测一台 99.1%）；虚拟节点细分区间后趋于均匀（30/34/36）✓✓★

12. 掌握标准 ​

  • [ ] 能对比五种 ID 方案 ★★★；
  • [ ] 会实现雪花并解释位段 ★★★；
  • [ ] 知道三种回拨策略的取舍 ★★★；
  • [ ] 能解释一致性哈希的迁移收益 ★★★；
  • [ ] 知道虚拟节点为什么必须加 ★★★。

13. 扩展资源 ​

14. 下一步学习 ​

《高并发系统设计》 —— 把并发、缓存、消息、ID 与分片的能力组合成系统级方案。 分布式模块到此收尾（《CAP 与 BASE 理论》 理论 → 《分布式事务》 事务 → 本节 ID 与分片）。

前置知识

后续知识

暂无

进度只保存在本机浏览器，可随时清除

个人学习项目：AI 生成内容均经人工复核，第三方资源仅作索引

仅作个人学习使用