分布式 ID 与哈希
两个基础组件：全局唯一 ID 生成（数据分片前提）和一致性哈希（节点路由）。面试常考。
分布式 ID 要求
| 要求 | 说明 |
|---|---|
| 全局唯一 | 跨实例不重复 |
| 趋势递增 | 索引友好（B+树顺序写） |
| 高可用 | 生成不能断 |
| 高性能 | 不能成为瓶颈 |
方案对比
| 方案 | 机制 | 优点 | 缺点 |
|---|---|---|---|
| UUID | 随机 | 简单、本地生成 | 无序（索引差）、太长 |
| 数据库自增 | 单点序列 | 简单 | 单点瓶颈、跨库难 |
| 号段模式 | 一次取一批号 | 高性能（本地分发） | 号段浪费、重启丢失区间 |
| 雪花算法 | 时间戳+机器+序列 | 趋势递增、无中心 | 依赖时钟 |
| Redis INCR | 原子自增 | 简单 | 依赖 Redis（见高级应用篇） |
雪花算法（Snowflake）
64 位: 1 bit 符号 | 41 bit 时间戳(毫秒) | 10 bit 机器 ID | 12 bit 序列号- 趋势递增：时间戳高位 → 近似单调
- 单机每毫秒 4096 个（序列号 12 bit），够用
- 唯一性三要素：时间 + 机器 + 序列
- 时钟回拨问题（必考）：机器时钟回拨 → 可能生成重复 ID。解法：拒绝生成等待、记录上次时间戳、备用序列
变体：美团的 Leaf（号段 + 雪花混合）、百度的 UidGenerator。
一致性哈希
哈希环: 增减节点只影响相邻段
- 普通取模（hash % N）：节点增减 → 全部 key 重映射（缓存全失效）
- 一致性哈希：hash 到环上，顺时针找最近节点。增减节点只影响环上相邻段（少量 key 迁移）
- 虚拟节点：每个物理节点多个虚拟节点，解决分布不均（数据倾斜）
- 应用：缓存分片、负载均衡（见系统设计水平扩展篇）、分库分表路由
面试追问
- 分布式 ID 要求？ 唯一、趋势递增（索引友好）、高可用高性能
- 雪花算法结构？ 时间戳 + 机器 ID + 序列号。单机毫秒级 4096 个，趋势递增
- 时钟回拨怎么办？ 拒绝生成/等时钟恢复/记录上次时间戳。回拨会重复
- 一致性哈希解决什么？ 节点增减只影响少量 key（普通取模全量重映射）。虚拟节点防倾斜
- 号段模式？ 一次取一批号本地分发，数据库压力小。重启丢区间（可接受）