Chapter 03
数据分区：把状态切开
上一章扩的是无状态层——把 session 外移之后，副本可以随便克隆，加机器加负载均衡器就够了。从本章起进入有状态的硬骨头：当一份数据本身大到单台机器装不下、或写入快到单台机器追不上时，第一刀就是把这份状态切开，分散到多台机器上。切开本身有它自己的代价，这一章就是讲这把刀怎么落、落在哪会出血。
本章建立的 schema
- 分区（partition / shard）通过把数据集切成子集分散到多节点，同时突破单机的存储上限和写吞吐上限；代价是跨分区查询和热点。
- 范围分区与哈希分区是一对此消彼长的取舍：用范围扫描的局部性，去换均匀的负载。
- 一致性哈希 + 虚拟节点（virtual node）把成员变更时的数据搬动量从“几乎全部”降到约 1/N，再把负载摊匀。
- 再平衡（rebalancing）的成本由分区方案决定；热点（hot shard）是分区天生救不了的那一类问题。
3.1第一刀：为什么要切，切完得到什么、付出什么
一份数据放在单台机器上，会同时撞两堵墙。一堵是容量墙：磁盘装不下，或者索引大到内存放不进、查询退化成磁盘随机读。另一堵是写吞吐墙：所有写都落在同一台机器的同一套日志和锁上，CPU、磁盘带宽、行锁竞争任意一个先到顶，写入就排队。
第 04 章的复制（replication）解不了这两堵墙——复制是把同一份数据多拷几份，每个副本仍要装下全量数据、主副本仍要扛下全部写。复制扩的是读和可用性，不是写和容量。要突破容量和写吞吐，唯一的办法是把数据集切成互不重叠的子集，每个子集只放在一部分节点上。这就是分区（partition），在 MySQL/Redis 圈子里更常叫分片（sharding）——同一件事的不同名字。
切完，存储和写吞吐都随节点数近似线性增长——这是分区的全部收益。但切开状态会立刻引入两笔新账，它们贯穿本章后面所有的设计：
- 跨分区查询变成 scatter-gather：一次查询若涉及多个分区，请求要发散到所有相关分区（scatter）、再把结果汇聚回来（gather）。延迟由最慢的那个分区决定，节点越多，撞上一个慢节点的概率越高。单分区能做的事（一次范围扫描、一个聚合），跨分区都要付这笔散射-汇聚的税。
- 分区不均会产生热点：如果某个分区的数据被访问得格外频繁，它会先于其他分区到顶——这个过热的分区叫 hot shard（热分片）。其余节点闲着，整个集群的吞吐被这一个分区卡死。复制救不了热分片：再多副本，写仍然要全部落到持有这片数据的主副本上。
无状态层在第 02 章靠“克隆 + 负载均衡”就扩起来了，因为副本之间没有差别、任意副本服务任意请求。有状态层不行：数据切开后，每个节点持有不同的数据，节点不再可互换。分区的全部难度——路由到哪一片、不均怎么办、加节点怎么搬——都来自这个“节点不可互换”。
从这里开始，所有分区方案要回答的核心问题只有一个：给定一个 key，怎么决定它落在哪个分区？ 这个映射函数的选择，决定了你拿到的是均匀负载还是热点、是高效范围扫描还是 scatter-gather、是加节点只搬 1% 还是搬 99%。
3.2范围 vs 哈希：用扫描效率换均匀负载
把 key 映射到分区，最朴素的两条路是：按 key 的取值区间切，或按 key 的哈希值切。两者是一对几乎对立的取舍。
范围分区（range partitioning）
给每个分区分配一段连续的 key 区间，比如分区 A 放 a–h、分区 B 放 i–p、分区 C 放 q–z。key 在分区内保持有序。
这样做的好处是范围扫描局部化：查“用户名以 m 开头到 p 结尾”的所有记录，只命中分区 B 一个节点，一次有序顺序读就拿完，不用 scatter-gather。时间范围、ID 区间这类查询都受益。
它的失效模式很尖锐：当 key 单调递增时，所有新写入都落在最后一个分区上。最典型的是用时间戳或自增 ID 当分区 key——“现在”这一刻的写永远落在持有最大区间的那个节点，它成了写热点，其余分区只读不写。范围分区把顺序这件好事，变成了写倾斜这件坏事。
哈希分区（hash partitioning）
先对 key 求一个哈希值（要选分布均匀的哈希函数，如 MD5、MurmurHash；不要用语言内置的对象 hash，它常按进程随机加盐、不同节点算出的值不一致），再用哈希值决定分区。哈希把相邻的 key 打散到不同分区，于是写入和数据量都摊得很匀，消灭了单调 key 的写热点。
代价同样尖锐：哈希毁掉了范围扫描的局部性。原本相邻的 key 被均匀撒到所有分区，一次范围查询变成对每个分区都来一刀的 scatter-gather——这正是 Cassandra 等系统里默认主键无法做高效范围查询、必须靠 clustering key 在分区内部排序来补救的原因。
范围保留了 key 的顺序，所以扫描快、但热点风险高；哈希打散了顺序，所以负载匀、但扫描退化。一句话：用扫描效率换均匀负载。 没有第三种免费选项——任何想同时要两者的方案（见本章挑战），都是在更高层把这两种分区组合起来用。
一个日志系统按 (timestamp) 做范围分区，写入 QPS 很高但读得很少。它会先撞哪堵墙？如果把分区 key 改成 (hash(source_id), timestamp)，写热点缓解了，又会丢掉什么能力？
展开答案
原方案先撞写热点：所有当前时刻的写都落在持有最新时间区间的那一个分区，其余分区闲置，集群写吞吐被一个节点封顶。改成按 source_id 哈希后，写被多个来源摊到各分区，写热点缓解。丢掉的是纯按时间的全局范围扫描——“查过去一小时所有日志”现在要扫所有分区（scatter-gather）。补救办法是用复合 key：哈希定分区、时间在分区内排序，于是“某个来源过去一小时”仍然局部化，只有“跨所有来源按时间”才付散射税。这就是范围与哈希被组合使用的典型形态。
3.3一致性哈希 + 虚拟节点：少搬，和摊匀，是两件事
选了哈希分区，下一个问题立刻冒出来：哈希值怎么映射到具体的节点？ 最直觉的做法是取模——node = hash(key) % N，N 是节点数。这在节点数不变时工作得很好，但它有一个致命的失效模式，要到 3.4 再平衡 才完整展开。这里先给出业界的标准答案：一致性哈希（consistent hashing）。
哈希环：key 顺时针找下一个节点
一致性哈希的核心动作只有一个：把 key 和节点映射到同一个环上（取哈希值后对一个很大的空间取模，比如 2³²，首尾相接成环）。一个 key 的归属，是从它在环上的位置顺时针走，遇到的第一个节点。
这个安排的全部价值，在于成员变更时的影响是局部的。取模方案里 N 一变，几乎每个 key 的目标都变了；一致性哈希里，加入一个节点，只会“截走”原本属于它顺时针后继节点的那一段弧上的 key，其余 key 的归属纹丝不动。删除一个节点，只把它那段弧的 key 交给后继。搬动量从“几乎全部”降到约 1/N。
很多人混淆的地方：少搬 ≠ 摊匀
这是本章最容易被讲错的一点，也是面试里区分“背过名词”和“真懂”的分水岭：把“一致性哈希”和“负载均衡”划等号是错的。一致性哈希只保证“成员变更时少搬”，它对“平时负载匀不匀”不作任何承诺。
原因在裸版本里很直接：每个物理节点在环上只占一个点，节点之间的弧段长度是随机的，长弧段拿到的 key 多、短弧段拿到的少——负载天生不均，N 越小越严重。更糟的是故障放大：某个节点挂掉，裸版本会把它整段弧的 key 全砸给唯一的后继节点。后继本就有自己的负载，骤然接收双份流量便跟着过载，再把负载传给它的后继——级联过载（cascading overload）。
虚拟节点：摊匀，靠的是它
解决“不匀”和“故障放大”的，是虚拟节点（virtual node，简称 vnode）：让每个物理节点在环上占 v 个虚拟位置（比如 v=128 或 256），而不是 1 个。
- 平时摊匀：一个物理节点的负载是它 v 个虚拟点弧段长度之和。v 越大，大数定律越起作用，各物理节点的总弧长越接近相等——负载就匀了。
- 故障也摊匀：一个物理节点挂掉，它的 v 个虚拟点散落在环的各处，每个虚拟点的后继是不同的物理节点。于是它的负载被分摊给多个后继，而不是全压给一个——级联过载被消解。加节点时同理，新节点从多个现有节点各匀走一小段，而不是只从一个邻居身上撕一大块。
一致性哈希负责“少搬”（成员变更只动相邻弧段）；虚拟节点负责“摊匀”（平时负载均衡 + 故障/扩容时把变化分散到多个节点）。两者解决的是不同的问题，生产系统两者都要。只上一致性哈希、不配虚拟节点，会得到一个“少搬但不匀、还会级联过载”的系统。
3.4再平衡：朴素取模为什么会打爆网络、冷掉缓存
再平衡（rebalancing）指节点数量变化（扩容、缩容、故障替换）时，把数据重新分配到节点上的过程。判断一个分区方案好不好，最硬的指标就是：加一个节点，要搬动多少 key？ 搬得越少，再平衡期间占用的网络带宽越少、对在线请求的干扰越小、新节点上线越快。
失效模式：hash-mod-N
回到 node = hash(key) % N。它的问题在 N 一变就暴露：把 N 从 3 改成 4，hash(key) % 3 和 hash(key) % 4 对几乎每个 key 都给出不同的结果——约 (N-1)/N 比例的 key 都要换节点。100 个节点加到 101，约 99% 的 key 要搬家。后果是连锁的：
- 打爆网络：几乎全量数据在节点间迁移，再平衡期间网络被搬运流量占满，在线读写被挤到一边。
- 冷掉所有缓存：key 到节点的映射全变了，每一层缓存（本地缓存、就近副本）原来缓存的内容全部失效，缓存命中率瞬间归零，大量请求穿透到底层存储——这一波缓存击穿叠在再平衡的网络压力上，常常直接把集群打趴。（缓存击穿/雪崩的完整机制见第 07 章。）
静态 hash-mod-N 分片在需要弹性伸缩的系统里已被一致性哈希取代，不应再用于新设计。它唯一还能成立的场景是节点数永久固定、永不扩缩容——而这在“需要分区”的系统里几乎不存在。
更省的方案：固定分区数
一致性哈希之外，另一类常见做法是固定分区数（fixed number of partitions）：预先建好远多于节点数的分区（比如 256 个分区分给 8 个节点），分区数从此不变，再平衡时只改变分区到节点的归属，而不重新计算 key 到分区的映射。Riak、Elasticsearch、以及 Cassandra 早期的设计都用这个思路。
它的优势：加一个节点时，从现有每个节点各匀几个整分区过来给新节点；key 到分区的映射完全不动，被搬的只是少数几个分区的数据，搬动量接近最优。代价是分区数要在建库时就估对——分区太少会限制最大扩容上限（节点数不能超过分区数），分区太多则每个分区的元数据和管理开销摊薄了收益。
| 方案 | 加节点的搬动量 | 负载是否均匀 | 范围扫描 | 为什么选 / 何时选 |
|---|---|---|---|---|
| hash-mod-N | 约 (N-1)/N（≈全量） | 均匀 | 不支持 | 已被取代。仅节点数永久固定时勉强可用。 |
| 范围分区 | 分裂/合并区间，搬动可控 | 不均（单调 key 写热点） | 高效（局部化） | 需要按 key 顺序做范围扫描时选；要额外防写热点。 |
| 一致性哈希 + 虚拟节点 | 约 1/N（只动相邻弧段） | 均匀（靠 vnode） | 不支持（哈希打散顺序） | 需要弹性伸缩、负载均匀、无范围扫描需求时的默认选择。 |
表里把“固定分区数”归在一致性哈希这一类的精神里——两者都把“成员变更”和“key 映射”解耦，让搬动量与节点变化成正比而非与全量成正比；区别只是前者用“固定数量的整分区”做调度单元，后者用“环上的弧段”。两条路都把 hash-mod-N 的全量重排，降到了只动需要变的那一小部分。
3.5热 key：分区天生救不了的那一类
前面所有方案都假设：负载不均是因为 key 分布不均，所以把 key 摊匀就好了。但有一种不均，摊 key 解决不了——单个 key 本身太热。
一个明星用户的主页、一件爆款商品的库存行、一条刷屏微博的计数器：这都是同一个 key 被海量请求集中访问。无论范围、哈希还是一致性哈希，一个 key 在任何方案里都只能落在一个分区上——分区的粒度是 key，比 key 更细它切不动。于是这个分区被一个 key 打到过载，其余分区闲着。这是分区的能力边界：分区能摊匀很多 key，但摊不开一个 key。
读侧的热 key 还能靠多复制几份、读分散到多个副本来缓解（第 04 章）。但写侧的热 key——比如爆款的库存递减——所有写仍要落到持有这片数据的主副本上串行执行，再多副本也没用。这一类必须在分区/复制之外另想办法。
三种工程手段
- key 加盐（salting）/ 拆分：人为给热 key 拼上一个随机后缀（如
counter#0…counter#15），把一个逻辑 key 拆成 m 个物理子 key 摊到不同分区，写时随机选一个子 key、读时把 m 个子 key 聚合。代价是读变成 scatter-gather（要聚合 m 份），且 m 要预估——是用读放大换写均匀。爆款库存常用这招把一行拆成多行库存桶。 - 前置缓存：把热 key 放进读缓存（甚至本地进程内缓存），让绝大多数读根本到不了存储层。读多写少的热 key（明星主页、爆款详情）这招最有效——它不改分区，而是在分区之前挡住流量。
- shuffle sharding（洗牌分片）：AWS 的做法，给每个“租户/热源”分配一个随机的节点子集，于是任意两个热源的子集很难完全重叠（重叠的概率随子集随机性下降）。这样一个热源把它的那个小子集打爆，也只波及与它共享节点的少数其他租户，而不是拖垮整个集群——它隔离的是故障爆炸半径，而不是消除热点本身。
很多人下意识地认为“数据不均，加机器/换分区策略就行”。热 key 是反例：它的不均集中在一个不可再分的 key 上，再换多少种分区方案都无效。识别出“这是热 key 问题，不是分区策略问题”，是这一章最值钱的判断——开错药方（一直调分区）会浪费大量时间。
100 个节点的集群加 1 个节点。用 hash-mod-N，大约要搬多少比例的 key？换成一致性哈希呢？
展开答案
hash-mod-N ≈ 99%：N 从 100 变 101，hash%100 与 hash%101 对几乎每个 key 都不同，只有极少数恰好同余的 key 不动，整体约 (N-1)/N ≈ 99% 要搬。一致性哈希 ≈ 1%：新节点只截走它相邻弧段上的 key，约占全环的 1/N ≈ 1/101 ≈ 1%（配虚拟节点后，这 1% 是从多个原节点各匀一点凑出来的，更均匀也更平滑）。两个数量级的差距，就是 hash-mod-N 被淘汰、一致性哈希成为默认的全部原因。
自测
先合上教程，把答案写下来，再展开对照——能完整说出“机制 + 代价”才算过。
- 范围分区和哈希分区，各自牺牲了什么、换来了什么？给一个会让范围分区翻车的具体 key 选择。
- 一致性哈希的“少搬”保证，和虚拟节点的“摊匀”作用，分别解决的是哪个问题？只用一致性哈希、不配虚拟节点，会留下哪两个隐患？
- 热 key 为什么换任何分区策略都救不了？读侧和写侧的缓解手段各是什么？
展开参考答案
1. 范围分区保留 key 顺序，换来高效的范围扫描（查询局部化、不用 scatter-gather），牺牲的是负载均匀——单调递增的 key 会让所有新写落在最后一个分区，形成写热点。哈希分区把 key 打散，换来均匀负载、消灭单调 key 写热点，牺牲的是范围扫描局部性（范围查询退化为对所有分区的 scatter-gather）。会让范围分区翻车的 key：时间戳或自增 ID——“现在”的写永远落在持有最大区间的那一个分区。
2. “少搬”解决的是成员变更时的搬动量：加/删节点只动相邻弧段的 key（约 1/N），而不是像 hash-mod-N 那样几乎全量重排。“摊匀”解决的是平时的负载均衡以及故障/扩容时把变化分散到多个节点。只上一致性哈希不配虚拟节点的两个隐患：① 平时负载不均（每个物理节点在环上只占一点，弧段长短随机）；② 节点故障时它整段弧砸给唯一后继，引发级联过载。
3. 因为分区的最小粒度是 key，一个 key 在任何方案里都只能落在一个分区上——分区切不动“比一个 key 更细”的东西，所以单个热 key 必然把它所在的那一个分区打满。读侧缓解：前置缓存（把读挡在存储之前）、多副本读分散（第 04 章）。写侧缓解：key 加盐/拆分（把一个逻辑 key 拆成多个物理子 key 摊到多分区，代价是读要聚合）；配合 shuffle sharding 限制热源的故障爆炸半径。
既要按用户范围扫描、又要避免热点，分区方案怎么设计？
需求：一个多租户系统，既要支持“查某个租户下、ID 在某区间内的所有记录”（范围扫描），又不能让某个超大租户或单调 ID 形成热点。范围分区满足扫描但有热点，哈希分区没热点但毁掉扫描——单一策略都不行。给出一个能同时满足两者的复合 key 设计，并说明它在什么查询上仍要付 scatter-gather 的代价。
展开思路（不是唯一解）
用复合分区 key：(hash(tenant_id), id)——先按 tenant_id 的哈希定分区（把不同租户摊到各分区，避免单租户/单调 ID 的全局热点），再让 id 在分区内部有序（保留同一租户内的范围扫描局部性）。这正是 Cassandra 的 partition key + clustering key 模型：partition key 决定落哪个分区（哈希、摊匀），clustering key 决定分区内的物理排序（有序、可范围扫描）。
仍要付 scatter-gather 的查询：跨租户的范围扫描（如“所有租户中 ID 在某区间的记录”）——因为不同租户被哈希撒到了不同分区，这种查询要打所有分区再汇聚。代价是有意为之的：用“跨租户扫描慢”换“单租户扫描快 + 无热点”。还剩一个边角：若单个租户本身超大（数据量超过一个分区的容量上限），需要进一步在 partition key 里掺入 id 的分桶（如 (hash(tenant_id), id / BUCKET)）把这个大租户再切开——这又会让该租户的全范围扫描退回 scatter-gather，是同一把取舍的再一次出现。