---
title: 分片算法 + 全局 ID 生成
type: concept
domain: sharding
tags: [sharding, algorithm, consistent-hash, gene-method, global-id, snowflake, segment]
status: learning
created: 2026-09-23
last_reviewed: 2026-09-23
method: feynman
related_questions:
  - "分表算法都有哪些？"
  - "分表后全局ID如何生成？"
related_knowledge:
  - ./sharding-fundamentals.md
  - ./sharding-join-pagination.md
  - ./sharding-migration.md
  - ../mysql/mysql-transaction-core.md
anki_cards: 8
interview_rounds:
  - "2026-09-23-round-1-Q5"
  - "2026-09-23-round-1-Q7"
---

# 分片算法 + 全局 ID 生成

> 分片算法决定数据"怎么落到分片"，全局 ID 决定"分片后主键如何唯一有序"。两者是配套设计：分片算法常要求 ID 内嵌分片位（基因法），ID 方案影响分片键选择。

## TL;DR（30 秒扫完）

- **分片算法 6 种**：Range / Mod / 一致性哈希 / 基因法 / List / Key，各对应不同扩容代价
- **扩容代价对比**：Mod N→N+1 迁 80%+；一致性哈希/基因法只迁 1/N 或接近 0；翻倍扩容恒 50%
- **全局 ID 6 种**：数据库自增 / UUIDv4 / UUIDv7 / 雪花 / 号段 / 基因法，按性能+有序+分布式+防猜测四维选
- **雪花 64 位**：1 符号 + 41 毫秒时间戳 + 10 机器 ID + 12 序列号 = 单机每秒 4096
- **雪花的三个坑**：时钟回拨 / workerId 冲突 / 单机 TPS 上限
- **基因法**：ID 低 4 位嵌 `hash(buyer_id) % 16`，查单时截取低 4 位直接路由，电商必备

## 关键结论

- **结论 A**：分片算法没有最好的，只有最适合业务生命周期的**组合**
- **结论 B**：一致性哈希用**虚拟节点**（100-200 个/物理节点）解决负载不均
- **结论 C**：全局 ID 的核心权衡是 **有序 vs 高性能 vs 分布式 vs 防猜测**
- **结论 D**：雪花是**通用默认**，号段/基因法是对特定痛点的加强版

## 完整讲解（费曼四步）

### STEP 1 · 概念

**分片算法**决定"分片键 → 分片号"的映射规则；**全局 ID** 解决"分片后主键跨片唯一有序"的问题。

### STEP 2 · 大白话

**快递分拣类比**：
- **Mod**：按地址末位 mod N 分到 N 个快递柜（均匀但柜子数改了全都要重新分）
- **一致性哈希**：环上排队，柜子加了只影响附近一段
- **基因法**：包裹编号本身就写着"去几号柜"，扫码直达

**雪花算法类比**：
- 时间戳 = 年号
- 机器 ID = 工厂编号
- 序列号 = 流水线次品重制号
- 合起来 = "2026 年 3 月 22 号，北京 5 号工厂，第 7 号工人，第 400 个产品"

### STEP 3 · 底层

#### 六种分片算法

| 算法 | 分片方式 | 适用场景 | 扩容代价 | 典型代表 |
|------|---------|---------|---------|---------|
| **Range** | 按区间切 | 时序数据、按月归档 | 高（旧数据要迁） | 按月分表 |
| **Mod** | `hash(key) % N` | 均匀分布要求高 | 极高（几乎全表迁） | ShardingSphere 默认 |
| **一致性哈希** | 环形 + 虚拟节点 | 频繁扩容场景 | 低（1/N） | 分布式缓存路由 |
| **基因法** | ID 内嵌分片位 | 主键即路由键 | 极低（新片新数据） | 电商订单 |
| **List** | 枚举映射 | 少量离散值 | 中 | 多租户 SaaS |
| **Key** | MySQL 内置哈希 | 分区场景 | — | 分区引擎层 |

**扩容代价对比（关键）**：

| 场景 | 迁移比例 | 说明 |
|------|---------|------|
| Mod 8 → 9 | **~88.9%** | `hash(x) % 8` vs `hash(x) % 9` 几乎独立 |
| Mod 8 → 16 | **~50%** | 翻倍扩容恒定 50% |
| 一致性哈希 8 → 9 | **~11.1%** | 1/(N+1) |
| 基因法 | **~0%** | 新数据自动落新片 |

**组合方案（工程实践关键）**：
- **分库按一致性哈希 + 分表按 Range**：库层解决扩容均衡，表层解决时序归档
- **分库按 Gene + 分表按 Mod**：基因法保证路由一致，库内取模保证均匀
- **两级 Hash**：分库 = hash(user_id) % 8，分表 = hash(order_id) % 16 → 8 库 × 16 表 = 128 分片

#### 一致性哈希的虚拟节点

**问题**：物理节点少时（如 3 个），环上映射分布不均，某节点可能承担 60% 数据。

**解决**：每个物理节点在环上映射 **100-200 个虚拟点**。

```
物理节点 A → 虚拟点 A1, A2, ..., A100
物理节点 B → 虚拟点 B1, B2, ..., B100
物理节点 C → 虚拟点 C1, C2, ..., C100
```

数据落在虚拟点，虚拟点映射到物理节点。这样哈希分布均匀得多。

#### 六种全局 ID 方案

| 方案 | 有序 | 高性能 | 分布式 | 防猜测 | 典型场景 |
|------|------|--------|--------|--------|---------|
| 数据库自增 | ✅ | ❌ | ❌ | ❌ | 单库单表 |
| UUIDv4 | ❌ | ✅ | ✅ | ✅ | 无要求场景 |
| UUIDv7 | ✅ | ✅ | ✅ | 部分 | 新型替代 |
| 雪花 | ✅ | ✅ | ✅ | ❌ | 电商/订单 |
| 号段 | ✅ | ✅ | ✅ | ❌ | 高 QPS 场景 |
| 基因法 | ✅ | ✅ | ✅ | ❌ | 分片路由 |

#### 雪花算法的 64 位组成

```
┌──┬──────────────────────────┬─────────────┬──────────────────┐
│ 1 │        41 位             │   10 位     │     12 位        │
│符号│      毫秒时间戳           │   机器 ID   │     序列号       │
│   │    (约 69 年)            │  (1024 台)  │  (单机 4096/秒)  │
└──┴──────────────────────────┴─────────────┴──────────────────┘
```

**Java 伪代码**：
```java
long id = timestamp << 22
       | (datacenterId << 17)
       | (workerId << 12)
       | sequence;
```

#### 雪花的三个经典坑

**1. 时钟回拨**：NTP 校时可能回拨几秒，导致同一毫秒生成重复 ID。

处理方案：
- **拒绝生成**：检测到回拨直接抛异常，等追上
- **备用时间戳**：用上次成功时间戳的下一个毫秒
- **暂停等待**：sleep 几毫秒直到追上（推荐）

**2. workerId 分配冲突**：多实例部署时谁发 workerId？

方案：
- ZK 临时节点抢占（美团 Leaf-Snowflake）
- DB 唯一约束（INSERT 冲突重试）
- 配置文件预分配（简单但有冲突风险）

**3. 单机 TPS 上限**：12 位序列号一毫秒只有 4096 个位置。

超过 4096/秒要拆到多台 worker。

#### 号段模式（Segment）

```sql
-- ID_SEQ 表
CREATE TABLE id_seq (
  name VARCHAR(64) PRIMARY KEY,
  max_id BIGINT NOT NULL,
  step INT NOT NULL DEFAULT 1000
);
```

- 应用本地缓存 1000 个 ID，用完再去 DB 取下一段
- **1000 应用请求换 1 次 DB 请求**，DB 压力极低
- 双 Buffer 预热减少重启浪费

#### 基因法（Gene Method）

**思路**：ID 低 4 位嵌 `hash(buyer_id) % 16`。

```
64 位雪花 ID：
[1][41 位时间戳][10 位机器 ID][12 位序列号]

基因法改造：
[1][41 位时间戳][10 位机器 ID][8 位序列号][4 位分片位]
                                                    ↑
                                          hash(buyer_id) % 16
```

查询时截取低 4 位 → 直接路由到对应分片，**不需要额外查用户表**。

代价：主键必须能改（不能用自增 ID），要占用位数。

### STEP 4 · 简化

**一句话总结**：分片算法选**扩容代价最小的组合**；全局 ID 选**能覆盖主查询路径**的方案；两者常常配合（基因法 = 分片算法 + 全局 ID 二合一）。

**记忆口诀**：
- 扩容频繁 → **一致性哈希 / 基因法**
- 归档频繁 → **Range**
- 极致均匀 → **Mod + 2 的幂**
- 多租户 → **List**
- 主键即路由 → **基因法**
- 雪花三坑 → **回拨 / workerId / TPS 上限**

## 常见误区

- **误区 1**：说"一致性哈希永远比 Mod 好" → 正确：分片数固定且很少扩时，Mod 完全够用；一致性哈希需要虚拟节点调优
- **误区 2**：说"雪花保证不重复" → 正确：雪花**理论上**保证，但**时钟回拨**会导致同毫秒重复 ID
- **误区 3**：说"UUIDv4 就是 UUID" → 正确：UUIDv4 完全随机，导致 B+ 树随机插入，**写入性能差 3-10 倍**；UUIDv7 用时间戳前缀修复了
- **误区 4**：说"基因法就是雪花" → 正确：基因法是**分片算法**，雪花是**ID 生成算法**；基因法可以在雪花 ID 上叠加分片位
- **误区 5**：说"号段模式不浪费 ID" → 正确：应用重启会丢掉未用完的号段，**不连续但保证唯一**
- **误区 6**：说"雪花单机能撑很高 QPS" → 正确：12 位序列号上限是 **4096 个/秒/worker**

## 延伸追问

1. **N=8 扩到 N=12 要迁多少数据？**
   - `hash(x) % 8` 和 `hash(x) % 12` 的理论最小公约数是 `hash(x) % 24`。只有 `hash(x) % 24 == 0` 才不迁，约 **8.3%** 不迁，**91.7%** 要迁。
2. **`hash(x) & (N-1)` 什么时候等价于 `hash(x) % N`？**
   - 仅当 N 是 2 的幂时。否则不等价（如 `11 & 3 = 3`，`11 % 4 = 3` 巧合；`6 & 3 = 2`，`6 % 4 = 2` 巧合；`5 & 5 = 5`，`5 % 8 = 5` 巧合，但换个数字就崩了）。
3. **雪花遇到时钟回拨怎么办？**
   - 三种：①拒绝生成抛异常 ②备用时间戳 ③sleep 等待追上（推荐）。严重回拨要告警人工介入。
4. **号段模式如何减少重启浪费？**
   - 双 Buffer：本地两个 buffer，一个在用，一个预热。用完了无缝切换到预热的，同时启动预热下一个。
5. **为什么 UUIDv4 会导致 B+ 树写入性能差 3-10 倍？**
   - 随机 ID 导致 B+ 树页随机插入，频繁 page split、页内移动大量数据、破坏页的局部性。UUIDv7 用时间戳前缀（48 位）修复了这个问题。
6. **Leaf-Snowflake 的 workerId 分配怎么保证不冲突？**
   - ZK 临时节点抢占：每个 worker 启动时向 ZK 的 `/leaf-snowflake/workers/` 下注册一个临时节点，ZK 保证同名节点唯一。ZK 会话断开会清理临时节点。

## 速查表

```
分片算法 6 种: Range / Mod / 一致性哈希 / 基因法 / List / Key
扩容代价:     Mod 8→9=89% / 一致性哈希=1/N / 基因法≈0%
雪花 64 位:   1+41+10+12（符号/时间戳/机器/序列）
雪花 TPS:     单机 4096/秒
雪花三坑:     时钟回拨 / workerId 冲突 / TPS 上限
号段:         1000 应用请求换 1 次 DB 请求
基因法:       低 4 位嵌 hash(user_id) % 16
UUIDv4 坑:    随机导致 B+ 树随机插入，写入慢 3-10 倍
UUIDv7 修复:  前 48 位时间戳前缀
组合方案:     分库一致性哈希 + 分表 Range
```

## 关联题目（题库）

- ⚠️ 《分表算法都有哪些？》— 2026-09-23 Round 1, ⭐⭐（只答 2 种，缺基因法/扩容代价）
- ⚠️ 《分表后全局 ID 如何生成？》— 2026-09-23 Round 1, ⭐⭐⭐（只答雪花，缺号段/基因法/时钟回拨）

## 关联知识

- [分库分表基础概念 + 分片规模设计](./sharding-fundamentals.md)
- [跨分片 JOIN 与分页方案](./sharding-join-pagination.md)
- [5 亿订单分库分表迁移](./sharding-migration.md)
- [MySQL MVCC](../mysql/mvcc.md)
- [主题地图](./_moc.md)

## Anki 候选卡片

1. **正**：分片算法六种分别是什么？**反**：Range / Mod / 一致性哈希 / 基因法 / List / Key
2. **正**：Mod N→N+1 扩容迁移多少数据？**反**：约 N/(N+1)，8→9 迁 88.9%；翻倍扩容恒 50%
3. **正**：雪花算法 64 位组成？**反**：1 符号 + 41 毫秒时间戳 + 10 机器 ID + 12 序列号（4096/秒）
4. **正**：雪花算法的三个经典坑？**反**：时钟回拨 / workerId 冲突 / 单机 TPS 上限
5. **正**：号段模式如何降低 DB 压力？**反**：本地缓存 1000 ID，1000 应用请求换 1 次 DB 请求
6. **正**：基因法核心思想？**反**：ID 低 4 位嵌 `hash(user_id) % N`，查单时截取低 4 位直接路由
7. **正**：UUIDv4 为什么写入性能差 3-10 倍？**反**：随机 ID 导致 B+ 树随机插入，频繁 page split
8. **正**：一致性哈希虚拟节点作用？**反**：每物理节点映射 100-200 虚拟点，解决物理节点少时负载不均

---

*最后更新：2026-09-23*