19.2 哈希分区
一句话
哈希分区用
hash(key) % N把每条数据钉到一个分片，读写都只打一片；它用「顺序」换「均匀」，代价是范围查询退化为全分片扫描，扩容时取模会搬走几乎全部数据。
原理：一行公式，两个陷阱
shard = hash(key) % N // N 个分片
shard = hash(key) & (N - 1) // 仅当 N 是 2 的幂，位运算更快
两个陷阱：
% N的 N 一变，映射几乎全变（下一节算给你看）；- 哈希均匀的是 key 数量，不是负载（19.1 已量化：key 数量最大/平均 1.00，请求负载 3.02）。
扩容：取模的迁移代价
N → N+1 时，key 留在原分片的条件是 k % N == k % (N+1)。对随机 key，稳定比例是 1/(N+1)，所以迁移比例是 N/(N+1)：
| N → N+1 | 理论迁移 | 实测（100 万 key） |
|---|---|---|
| 8 → 9 | 88.9% | 88.9% |
| 16 → 17 | 94.1% | 94.1% |
| 64 → 65 | 98.5% | 98.5% |
| 100 → 101 | 99.0% | 99.0% |
| 1000 → 1001 | 99.9% | 99.9% |
算这段的程序：
package main
import "fmt"
func moved(n, keys int) float64 {
m := 0
for i := 0; i < keys; i++ {
if i%n != i%(n+1) {
m++
}
}
return float64(m) * 100 / float64(keys)
}
func main() {
fmt.Println("取模分片：N 个分片扩到 N+1 个，重新映射的 key 比例")
fmt.Printf("%-6s %-12s %-12s\n", "N", "理论 N/(N+1)", "实测")
for _, n := range []int{8, 16, 64, 100, 1000} {
fmt.Printf("%-6d %-12s %-12s\n", n,
fmt.Sprintf("%.1f%%", float64(n)*100/float64(n+1)),
fmt.Sprintf("%.1f%%", moved(n, 1000000)))
}
}
运行输出与上表一致（N=8 时 88.9%，N=1000 时 99.9%）。
🔑 结论：取模扩容本质上是全量重分布。分片数越多、扩一个分片的相对代价越大（1000 片扩 1 片要搬 99.9%）。这就是一致性哈希（19.4）要解决的问题。
三种缓解手段
| 手段 | 做法 | 迁移比例 | 代价 |
|---|---|---|---|
| 预分桶/固定槽位 | 桶数远大于分片数，桶 → 分片的映射表可改 | 约 1/(N+1)，按桶粒度 | 多一层元数据；桶数决定倾斜粒度 |
| 2 的幂 + 翻倍 | N 翻倍时，只有「新增那一位为 1」的 key 迁移 | 50% | 仍不是最小迁移；容量只能翻倍 |
| 一致性哈希 | 环 + 顺时针，增删只影响相邻区间 | 约 1/(N+1) | 元数据与实现复杂度（19.4） |
预分桶的粒度可以算出来（1024 个桶、9 个分片）：
| 桶数 | 每分片桶数 | 最大分片偏离理想值 |
|---|---|---|
| 16 | 1–2 | 12.5% |
| 64 | 7–8 | 12.5% |
| 256 | 28–29 | 2.0% |
| 1024 | 113–114 | 0.2% |
| 4096 | 455–456 | 0.2% |
桶越多越均匀，但元数据越大；Redis Cluster 选的是固定的 16384 个槽，在「粒度」与「槽位表大小」之间取平衡。
哈希函数怎么选
本机基准（Go 1.27，Apple M1，16 字节 key，go test -bench）：
| 函数 | ns/op | 吞吐 | 适用 |
|---|---|---|---|
| CRC32（IEEE） | 5.3 | 2.8 GB/s | 最快；但可预测，不适合不可信输入 |
| FNV-1a | 6.0 | 2.4–2.5 GB/s | 简单；雪崩性一般，需加 finalizer |
hash/maphash | 7.0 | 2.1 GB/s | 带随机种子的抗碰撞哈希；进程重启后种子变 |
| SHA-1 | 47 | 320 MB/s | 能用，但比 FNV 慢约 8 倍 |
| MD5 | 97 | 153 MB/s | 别用：慢，且早已不适合做安全哈希 |
fmt.Sprintf 拼 key | 28.6 | 524 MB/s | 额外分配，热点路径上是纯开销 |
三条选型规则：
- 默认用 xxHash/MurmurHash/CityHash 这类非加密哈希（Go 标准库没有，需引入），或
maphash；它们比 MD5 快一个数量级，分布足够好； - 不可信输入用带密钥的哈希（
maphash/SipHash）：CRC32、FNV 是可预测的，攻击者能构造大量 key 落到同一分片，制造热点； - 别在热路径上拼字符串再哈希：
fmt.Sprintf一次分配就是几十纳秒，直接WriteString/预分配 buffer 更快。
⚠️ FNV-1a 还有一个坑：对「只差后缀」的字符串（比如
node-1#0、node-1#1）雪崩不足，哈希值会聚簇。做虚拟节点时这会让同一节点的 token 挤在一段弧上，虚拟节点直接失效（19.5 有实测）。要么换好哈希，要么在末尾加一个 splitmix64/murmur 的 finalizer。
哈希分区失去了什么
| 能力 | 哈希分区 | 影响 |
|---|---|---|
范围扫描（BETWEEN、时间区间） | ❌ 要扫所有分片 | 分析型查询、分页、导出变慢 |
| 有序遍历 / 前缀查询 | ❌ 无全局顺序 | 「最近 10 条」需要额外索引 |
| 跨 key 的局部性（同一用户的多条数据） | ✅ 若按该 key 分区 | 单用户查询收敛 |
| 分片内二级索引 | ✅ | 仅限该分片 |
| 全局唯一约束 | ❌ | 需要额外协调 |
所以哈希分区适合「点查为主、写吞吐优先」的业务；范围/排序需求要用范围分区（19.3）或额外索引。
工程细节
| 问题 | 做法 |
|---|---|
| 多 key 操作要落同一分片 | Redis 用 hash tag：user:{42}:name、user:{42}:age 只哈希 {} 里的内容 |
| 热点 key | 加盐拆子键（19.1），或做本地/分布式缓存副本 |
| 分片数变化 | 预分桶/一致性哈希；不要直接改 % N |
| 客户端还是服务端路由 | 客户端路由省一跳但要同步元数据；服务端路由简单但多一跳（48.2 服务发现） |
| 分片键与主键不同 | 需要二级索引表；写入要走两张表（见 19.9 二级索引与分区） |
反模式
| 反模式 | 后果 |
|---|---|
| 用 MD5/SHA 做分区哈希 | 每次写入多几百纳秒到微秒，吞吐白白损失 |
直接用 % N 然后在线扩分片 | 一次扩容搬走 90%+ 数据，集群雪崩 |
| 用可预测哈希处理用户可控 key | 攻击者构造同分片 key，制造热点 |
| 分片数不是 2 的幂却用位掩码 | 映射严重不均 |
| 忽略 hash tag，多 key 命令跨槽 | Redis 直接报 CROSSSLOT 错误 |
| 热点 key 只加机器 | 同一个 key 永远在同一片，加机器无效 |
| 用哈希分区还要全局有序分页 | 每次查询 fan-out + 归并，尾延迟不可控 |
自检
Q1 10 个分片扩到 11 个，为什么会有约 90.9% 的 key 需要迁移？如果改成扩到 20 个呢？
▸ 答案：取模 k%10 与 k%11 对随机 key 相等的比例是 1/11，所以 10/11 ≈ 90.9% 的 key 会换分片。扩到 20 时，k%10 == k%20 只对「除以 20 的余数小于 10」的一半 key 成立，迁移约 50%；但分片数翻倍意味着容量翻倍，不能只加 1 台。结论：取模扩分片的迁移量由「新旧分片数的公倍数」决定，不是「加一台就只搬 1/N」。
Q2 预分桶为什么能降低迁移量？桶数是不是越多越好？
▸ 答案：预分桶把「key → 分片」拆成「key → 桶（固定）」和「桶 → 分片（可改）」两层；扩容只改第二层，迁移量按桶计，约 1/(N+1)。桶越多，单桶越小，迁移粒度越细、分布越均匀（1024 桶/9 片偏离 0.2%，16 桶偏离 12.5%）；但桶 → 分片的映射表要存、要同步，桶太多会让元数据与变更传播变重。经验是桶数比预期最大分片数大 1–2 个数量级。
Q3 为什么说 CRC32 不适合对「用户可控的 key」做分区？
▸ 答案：CRC32/FNV 都是确定性、无密钥的哈希，攻击者可以离线构造大量落在同一分片的 key（甚至不需要知道分片数，只要能探测延迟/错误），制造热点或让某片过载。对不可信输入要用带密钥的哈希（maphash、SipHash），让攻击者无法预测映射；代价是哈希种子变化会影响跨进程一致性——maphash 的种子无法跨进程固定，需要跨进程一致时改用固定密钥的 SipHash，或把路由收到服务端。
Q4 哈希分区下，如何实现「查询某用户最近 10 条订单」？
▸ 答案：如果按 user_id 分区，直接单分片查询 + 分片内按时间索引即可。如果按 order_id 分区，则必须 fan-out 或建二级索引：① 建 (user_id, created_at) → order_id 的索引表（按 user_id 分区），先查索引再取详情；② 用 CQRS 维护一份按 user_id 组织的读模型（见 32.1 CQRS）；③ 接受全分片扫描，但设超时与降级。选哪种看查询 QPS、延迟要求与一致性要求。
Q5 一个系统用 hash(user_id) % 16 分片，现在要扩到 32 片。有哪些方案，各自迁移多少？
▸ 答案：① 直接 % 32：k%16 == k%32 只对一半 key 成立，迁移 50%（因为 32 是 16 的倍数，旧分片正好一分为二，代价可控）；② 预分桶：桶数不变，改桶 → 分片映射，迁移约 1/2 的桶；③ 一致性哈希/虚拟节点：迁移约 1/2（新增 16 个节点接管一半弧），但粒度更细、可逐步扩；④ 双写迁移：新老映射并行写，后台搬迁，校验后切读。方案 ① 在「翻倍」场景其实可接受，方案 ③④ 适合不能停机、要逐步扩容的场景。
跨篇相关：分区键的四条判据与负载实测见 19.1 分区键设计；按范围切分与热点见 19.3 范围分区；取模扩容的替代方案见 19.4 一致性哈希、19.5 虚拟节点；再平衡与迁移流程见 19.7 再平衡与数据迁移；分库分表的工程实践见 44.14 分库分表；缓存分片与一致性哈希见 41.2 本地缓存与分布式缓存；会话粘性路由的实测见 37.2 无状态化；客户端路由与元数据同步见 48.2 服务发现；NoSQL 的分区实现见 44.19 分布式数据库（待补）。