Chapter 05
分区与路由：把不同数据切到不同节点
第 04 章建立了复制——同一份数据存在多个副本，代价是要协调写顺序和副本漂移。这一章转向数据分布的另一个轴：分区（partitioning / sharding），把不同数据切到不同节点，以突破单机容量和吞吐上限。复制与分区通常叠加使用：先分区，每个分区再复制。
本章你将建立的 schema
- 范围分区与哈希分区各牺牲了什么——有序扫描 vs 均匀分布，鱼与熊掌
- 一致性哈希为何把再平衡的搬迁量从全量降到 K/N——环上只动相邻段
- 虚拟节点（vnode）解决了朴素一致性哈希的负载不均与异构机器问题
- 哈希消不掉的热点——单 key 内在热度，以及随机后缀的写扩散代价
5.1范围分区 vs 哈希分区
分区的根本选择：保留 key 的顺序（范围分区），还是打乱顺序换来均匀分布（哈希分区）。
单机的存储容量、内存、I/O 带宽都有上限。当数据量或请求量超出单机极限，唯一的出路是把数据水平切割，分散到多台机器——这正是分区要解决的问题。没有分区，工程师只能靠垂直扩容（更贵的机器）或手动在应用层按业务逻辑拆库，两者都难以自动扩展。
范围分区（key-range）
范围分区把 key 空间切成若干有序连续区间，每个区间分配给一个节点。类比百科全书分卷：A–D 卷、E–H 卷……路由表只需记录每个区间的边界，节点收到请求后，按边界做二分查找即可定位分区。
优势：key 在磁盘上有序存储，范围扫描（range scan）高效——SELECT * WHERE ts BETWEEN t1 AND t2 只需访问一个或少量相邻分区。
以 sensor_id:timestamp 作 key 时，所有"现在"的写请求哈希落在同一时间段对应的分区，形成写热点。修复方案之一：反转时间戳（sensor_id:(MAX_TS - ts)），让最新数据散布到多个分区；或在 key 前加随机桶前缀，把写流量打散。
哈希分区（hash）
对 key 计算哈希值（Cassandra 用 Murmur3，MongoDB 用 MD5），将哈希值均匀映射到哈希空间，再按哈希区间分配分区。哈希函数的均匀性保证：即使原始 key 分布极度倾斜，哈希后落点接近均匀。
代价：相邻 key 哈希后不再相邻，范围查询退化为 scatter-gather——必须广播到所有分区并合并结果，延迟和 CPU 均上升。
| 维度 | 范围分区 | 哈希分区 |
|---|---|---|
| 路由信息 | 区间边界表，O(log N) 查找 | 哈希区间映射表 |
| 范围查询 | 高效，单分区顺序扫描 | scatter-gather，全分区广播 |
| 写分布 | 可能倾斜（时间 key 等） | 均匀（取决于哈希质量） |
| 热点根因 | key 分布本身倾斜 | 单 key 内在热度（哈希消不掉） |
| 典型系统 | HBase、BigTable、TiKV | Cassandra、Dynamo、MongoDB |
电商订单表按 order_id 做哈希分区，产品经理要求"查询某用户最近 30 天的所有订单"。这个查询在哈希分区下会遇到什么问题？有哪些解法？
展开答案（先停 10 秒）
同一用户的订单 order_id 哈希后散落在所有分区，查询变成全分区 scatter-gather，延迟线性增长。解法：①按 user_id 而非 order_id 做分区 key（同一用户的订单聚集）；②引入二级索引（本地索引或全局索引）；③双写一张以 user_id 为前缀的辅助表。这指向一个设计洞察：分区 key 的选择必须与最常见的查询模式对齐。
5.2一致性哈希
把节点和 key 都映射到同一个环，每个 key 归顺时针方向最近的节点——节点变动时只搬环上相邻一段，而非全量。
用 hash(key) mod N 分区时，节点数 N 一旦变化（加节点 N→N+1，或节点故障 N→N-1），绝大多数 key 的 hash % N 都变，几乎所有数据需要搬迁，形成"再平衡风暴"（rebalancing storm），在搬迁期间磁盘和网络被打满。一致性哈希把搬迁量的理论下界降到 K/N（K = key 总数，N = 节点数），这是它存在的根本理由。
机制：哈希环
将哈希空间定义为一个闭合环 [0, 232)。每个节点的标识符（IP + 端口）也经过同一哈希函数映射到环上某个位置。每个 key 顺时针找到的第一个节点，即为其归属节点。
加节点时：新节点 P 插入环上位置 X。X 到 X 的前驱节点 Q 之间的那段 key，从 Q 迁移到 P；环上其他位置的 key 不动。平均搬迁量 ≈ K/N。
对比 hash mod N：N→N+1 后，对于大多数 key，hash(key) % (N+1) ≠ hash(key) % N，要读取旧节点的数据写入新节点，几乎全量搬迁，是一次性能瓦解事件。
一致性哈希像时钟表盘：节点是刻度，key 是指针，指针顺时针转到下一个刻度即停。加一个刻度，只有"上一个刻度到新刻度"这段指针需要重新停靠。类比的边界在于：真实的哈希环上节点位置不是等间距的，一个邻居节点会承接过大的弧段。
虚拟节点（vnode）
朴素一致性哈希的缺陷：节点在环上只有一个位置，新节点加入仅从一个邻居抢走一段 key，该邻居承载减轻，其他节点毫无变化——负载不均。强机器和弱机器分配权重相同——无法异构。节点故障时，其负载全压给一个后继节点——足以压垮单点。
vnode 方案：每个物理节点在环上映射到多个位置（Cassandra 和 Dynamo 默认 100–1000 个 token）。
- 负载均衡：新节点的 vnode 分散在环的多处，从许多现有节点各抢一小段，汇总后负载均衡。
- 异构支持：性能强的机器分配更多 vnode，承担更多数据和流量。
- 故障容忍：节点故障时，其 vnode 分散到所有其他节点，而不是全部压给单一后继节点。
hash mod N 的全量搬迁形成本质区别。Karger 等人在提出一致性哈希时证明了四条性质：balance（key 均衡分布到各节点）、monotonicity（加节点时，key 只往新节点迁移，不在旧节点之间乱动）、spread（client 视角不一致时 key 仍稳定）、load（节点负载有上界）。monotonicity 是最关键的——它保证加节点不触发旧节点间的数据洗牌，只做增量搬迁。
用 hash mod N 分区，当前 N=4，某 key 的 hash(key)=17，归属节点 3。现在加一个节点 N=5，17 % 5 = 2，归属节点变为 2。哈希环下同样的 key 会发生什么？
展开答案（先停 10 秒）
在哈希环上，key 的哈希值 17 落在环的固定位置，归属节点取决于"顺时针方向最近的节点"。新节点 P 若其哈希值在 hash(key)=17 和其前驱节点之间，则 key 从前驱迁往 P；否则 key 完全不动。无论如何，不会触发其他任意节点间的数据移动，这正是 monotonicity 性质。
5.3再平衡策略
节点加入或离开时，如何把分区在节点间重新分配——三种策略各有固定代价与灵活性取舍。
生产集群中节点会扩容（容量不足）、缩容（成本优化）、或故障下线（硬件/网络）。每次拓扑变化后，若不重新平衡分区，部分节点承载过多，其余节点闲置，系统整体资源利用率低下，热节点成为瓶颈。
| 策略 | 原理 | 优势 | 缺陷 | 典型系统 |
|---|---|---|---|---|
| 固定分区数 | 建库时创建远多于节点的分区（如 10 节点配 1000 个分区），加节点时从每个现有节点各抢几个分区，分区总数不变 | 路由逻辑简单；分区大小随数据量自动稳定 | 初始分区数选大了浪费元数据，选小了后期扩展受限；分区数不能动态增长 | Riak、Elasticsearch |
| 动态分区 | 分区超过阈值（如 10 GB）自动分裂为两个；过小时与邻居合并 | 分区数随数据量自适应，适合数据量差异大的场景 | 新建数据库只有一个分区，所有写请求打到单节点直到第一次分裂（单点瓶颈）；HBase 用预分裂（pre-split）缓解 | HBase、MongoDB |
| 比例分区 | 每节点维持固定数量的分区，加节点时按比例增加总分区数 | 节点数与分区数线性增长，分区大小稳定 | 分区分裂逻辑略复杂；分裂时目标节点需随机选取以避免偏斜 | Cassandra（vnode 变体） |
hash mod N 不是再平衡策略——它是一个路由公式。每次节点数 N 变化，公式的结果对几乎所有 key 都变，触发全量数据搬迁。生产系统的再平衡必须建立在稳定的分区映射表（partition map）之上，通过移动分区而非重算映射来完成。
5.4请求路由与热点
客户端请求如何找到正确分区，以及哈希分区消不掉的热点如何处理。
分区方案确定后，每个请求必须被路由到持有目标分区的节点。路由信息（分区→节点映射）在集群拓扑变化时会更新，不同节点的视图会短暂不一致。路由层的设计决定了：谁存储分区表、谁负责更新、客户端是否需要感知拓扑。
三种路由架构
三种架构在"谁知道分区表"这个问题上给出不同答案，并因此在延迟、复杂度、一致性上取得不同取舍。
热点与"明星问题"
哈希分区消除了 key 分布倾斜导致的热点——但无法消除单 key 内在热度。一个被百万用户同时访问的明星用户 ID，哈希后落在唯一一个分区，该分区的节点成为瓶颈，任何分区策略都无法自动分散这类热点。
缓解手段：
- 随机后缀（写扩散）：给热 key 加 0–99 的随机后缀，把同一逻辑 key 的写请求分散到 100 个物理 key（分散到多个分区）。代价：读请求必须查询所有 100 个子 key 再合并（scatter-gather），读代价线性上升。
- 应用层缓存：热数据在 Redis/本地内存缓存，降低对存储层分区的压力。
- CDN 与预聚合：内容类热 key（视频、图片）走 CDN；计数类热 key（点赞数）在内存聚合后批量写入。
写时加随机后缀后，读请求必须知道哪些后缀存在并行并发查询，否则会漏读。工程上通常的做法是：维护一个"热 key 列表"（配置下发或自动检测），只对热 key 启用后缀扩散，冷 key 保持原样，避免给所有 key 引入不必要的读放大。
微博上某明星发了一条微博（热 key = 微博 ID），未来 10 分钟会有数百万次读请求。用哈希分区存储微博内容，这条微博所在的分区节点会遇到什么问题？随机后缀方案是否适用于这种场景？
展开答案（先停 10 秒）
微博 ID 哈希到固定分区节点，数百万次读请求打到单台机器，CPU 和网络带宽被打满，其他分区的正常请求延迟也受影响（共享节点资源）。随机后缀方案不适用于纯读场景——该方案针对写扩散，读时需 scatter-gather 合并，对纯读的热 key 反而增加延迟。此场景的正确方案是：分层缓存（Redis/CDN），让热内容在缓存命中而不落到存储层；或者存储层支持分区内副本分读（复制 + 读负载均衡，第 04 章的内容）。
自测题
- 用
hash mod N分区，为什么加一个节点会引发几乎全量数据搬迁？一致性哈希怎么把搬迁量降到约 K/N？ - 虚拟节点（vnode）解决了朴素一致性哈希的哪两个核心问题？
- 哈希分区消除了所有热点吗？它消不掉哪一种热点，为什么？
- 范围分区和哈希分区各自牺牲了什么能力？分别举一个场景说明这个代价何时不可接受。
展开参考答案（先独立作答）
1. hash mod N 中，N 变为 N+1 后，对绝大多数 key 有 hash(key) % N ≠ hash(key) % (N+1)，导致它们被分配到不同节点，几乎所有数据需要搬迁。一致性哈希把 key 和节点都映射到同一个环，新节点 P 插入位置 X，只有 X 与其前驱节点之间的那段 key（占整体的 1/N）需要从前驱迁往 P；其余位置的 key 归属节点不变，搬迁量平均 ≈ K/N。
2. ①负载均衡：vnode 让新节点从环上多处各抢一小段，汇总负载均衡，而非只从一个邻居抢一大段。②异构支持：性能强的机器分配更多 vnode，按比例承担更多数据和流量。
3. 哈希分区消除了 key 分布倾斜（统计热点），但消不掉单 key 内在热度（明星问题）。单个热 key（如明星用户 ID）哈希到唯一分区，该分区节点收到全部请求，哈希函数无论多均匀都无法把同一 key 的请求分到多个节点。
4. 范围分区牺牲了均匀写分布——时间前缀 key 让"当前"分区成为写热点，在时序写入场景（IoT 传感器、日志）中代价不可接受。哈希分区牺牲了有序范围查询——相邻 key 哈希后不相邻，范围扫描退化为全分区 scatter-gather，在需要时间范围查询或地理范围查询的场景中代价不可接受。
一致性哈希 × 副本放置：vnode 的拓扑陷阱
一致性哈希决定 key 归属哪个节点（主分区），但第 04 章指出每个分区还需要 N 个副本。环上某个 key 的 N 个副本应该放在哪几个节点？naïve 方案是顺时针取随后 N−1 个 vnode 对应的节点——但 vnode 带来了什么拓扑陷阱？如何避免？
提示（卡住再展开）
vnode 让同一个物理节点在环上有多个位置。顺时针取 N−1 个 vnode 时，这些 vnode 可能属于同一台物理机器——甚至同一个机架。副本全部落在同一机器/机架，物理故障（断电、交换机失联）会导致所有副本同时不可用，副本的容错意义消失。Cassandra 的 NetworkTopologyStrategy 在选副本节点时跳过同一物理节点和同一机架的 vnode，确保 N 个副本跨机器/跨机架，这需要节点在注册时上报自己的 rack 和 datacenter 标签（snitch）。