数据分片与一致性哈希：Slot、虚拟节点、Rendezvous与再平衡

分片把一份超出单节点容量或吞吐的数据拆到多个节点。一致性哈希只是路由算法之一，它能减少成员变化时的映射变动，却不负责复制、事务、迁移校验和强一致。要做生产分片，必须同时设计逻辑分区、物理节点、路由版本、副本、热点和迁移状态机。

一、学习目标

学完后应能：

1. 区分 Partition、Shard、Slot、Replica 和物理节点。
2. 比较 Range、取模、目录、固定 Slot、一致性哈希、Rendezvous 与 Jump Hash。
3. 解释一致性哈希扩缩容时哪些 Key 移动，以及虚拟节点为何改善倾斜。
4. 解释 Redis Slot、Kafka Partition 和数据库分片的不同语义。
5. 设计路由版本、双读、CDC、校验、切换和回滚流程。
6. 定位热点 Key、热点分片、容量倾斜和错误路由。

二、先分清几个对象

对象	含义	示例
Logical Partition/Slot	稳定的逻辑桶	Redis 16384 Slot、Kafka Partition
Physical Node	真正承载数据或请求的实例	Redis Master、Broker、分库实例
Replica	同一逻辑分区的冗余副本	Leader/Follower、Master/Replica
Routing Table	逻辑分区到物理节点的映射	Slot 0-5000 属于节点 A
Routing Version	当前映射的版本/Epoch	防止旧客户端按过期拓扑写入

flowchart TD
    A["业务Key"] --> B["分片函数得到逻辑Partition"]
    B --> C["路由表和版本"]
    C --> D["选择当前Leader或Master"]
    D --> E["副本协议复制到Replica"]

分片回答“数据放在哪里”，复制回答“同一份数据有几份以及如何一致”，两者不能混为一谈。

三、Range Sharding

按照连续范围分片，例如用户 ID 1~100万 在 A、100万~200万 在 B，或者按日期按月建表。

优点：范围查询和批量扫描容易裁剪分片，数据位置直观。风险：递增 ID 的新写全部落到最后范围，形成尾部热点；不同范围数据量不均，需要 Split/Merge。

时间分区还要处理迟到数据、跨月查询、历史归档和新分区预创建。只按创建时间分片可能让“今天”成为热点，必须结合业务访问模式。

四、取模分片为什么扩容代价大

最简单规则：

partition = hash(key) % N

当节点数从 4 变成 5，大量 Key 的余数都会变化，不只是迁移约五分之一数据。缓存场景会造成集中 Miss 和回源风暴；数据库场景会造成大规模搬迁。

取模并非不能用。若 N 是稳定逻辑分区数，而逻辑分区再映射物理节点，扩容只调整少量映射，这就是固定 Slot/Partition 层的价值。

五、固定逻辑 Slot 解耦节点数量

flowchart TD
    A["hash(key)得到固定Slot"] --> B["查询Slot到节点映射"]
    B --> C["节点A负责一组Slot"]
    B --> D["节点B负责一组Slot"]
    B --> E["节点C负责一组Slot"]
    C --> F["扩容时只迁移选中的Slot"]

Redis Cluster 使用 16384 个 Hash Slot，Key 通过 CRC16 后对 16384 取模；节点扩容是迁移 Slot，而不是把节点数直接放进 Key 取模。客户端访问错误节点时，MOVED 表示稳定归属变化，ASK 表示 Slot 正在迁移中的临时访问指引。

Kafka 的 Partition 是持久化日志和顺序边界，不是 Redis Slot。Partition 有 Leader、副本和 Offset；增加 Broker 不会自动增加 Partition 数，增加 Partition 还可能改变按 hash(key) % partitionCount 的 Key 映射和局部顺序。

六、目录路由

目录服务显式保存 tenantId -> shard、deviceId -> unit。优点是可按租户容量、地域、合规和大客户独立迁移；缺点是目录本身要高可用、缓存和版本化。

目录缓存过期会把请求发到旧分片。服务端应校验路由版本或数据归属，返回可识别重定向，而不是在错误库静默创建一份重复数据。

七、一致性哈希环

将哈希空间首尾相连成环。物理节点和 Key 都映射到环上，Key 顺时针找到第一个节点作为所有者。

flowchart TD
    A["节点地址和虚拟节点计算Hash"] --> B["按Hash排序形成环"]
    B --> C["业务Key计算Hash"]
    C --> D["顺时针找到第一个节点"]
    D --> E["路由到对应物理节点"]

新增节点 X 时，理想均匀条件下主要接管它在环上前驱到 X 的区间，预期约移动 1/(N+1) Key；删除节点时主要把该节点区间交给后继。这里的比例是均匀哈希期望，不是每次扩容的绝对保证。

一致性哈希只改变映射。数据是否已经搬到 X、迁移期间从哪里读、并发写怎样处理，必须由迁移协议完成。

八、虚拟节点为什么重要

物理节点很少时，单个哈希点容易把环切得极不均匀。为每个物理节点创建多个虚拟节点，可把区间打散，降低容量方差，也可用不同虚拟节点数量近似权重。

虚拟节点不是越多越好：路由表内存、构建时间、状态传播和迁移碎片都会增加。权重变更也会移动 Key，必须纳入容量和迁移预算。

故障域同样重要。三个副本若都落在同一机架，即使节点 ID 不同，也无法承受机架故障；副本选择要按地域、机房、机架做拓扑约束。

九、Rendezvous/HRW Hash

对一个 Key 和每个候选节点计算分数：

score = hash(key, node)

选择最高分节点。新增节点时，只有新节点得分超过旧赢家的 Key 会迁移；理想均匀条件下约 1/(N+1)。删除节点时，原本由它获胜的 Key 自动选择第二高分节点。

优点是不需要维护环和虚拟节点，Top-K 还能选副本；代价是朴素实现每次路由要计算全部节点，节点非常多时需优化。加权 Rendezvous 不能简单把哈希分数乘权重，可靠实现应使用经过证明的加权公式。

十、Jump Consistent Hash

Jump Hash 将 Key 映射到编号为 0..bucketCount-1 的桶，时间复杂度约 O(log N)、状态少，并具有较小重映射。它适合桶编号连续且权重一致的场景；任意节点身份、加权和多副本选择需要额外映射层。

算法选型不是只比单次计算速度，还要看节点变化频率、权重、副本拓扑、路由表传播和迁移协议。

十一、JDK 8 Demo：带虚拟节点的一致性哈希环

import java.nio.ByteBuffer;
import java.nio.charset.StandardCharsets;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.SortedMap;
import java.util.TreeMap;

public final class ConsistentHashRing {
    private final TreeMap<Long, String> ring = new TreeMap<Long, String>();

    public void addNode(String node, int virtualNodes) {
        if (virtualNodes <= 0) throw new IllegalArgumentException("virtualNodes必须大于0");
        for (int i = 0; i < virtualNodes; i++) {
            ring.put(hash(node + "#" + i), node);
        }
    }

    public String route(String key) {
        if (ring.isEmpty()) throw new IllegalStateException("哈希环为空");
        long value = hash(key);
        SortedMap<Long, String> tail = ring.tailMap(value);
        Long position = tail.isEmpty() ? ring.firstKey() : tail.firstKey();
        return ring.get(position);
    }

    private static long hash(String text) {
        try {
            MessageDigest digest = MessageDigest.getInstance("SHA-256");
            byte[] bytes = digest.digest(text.getBytes(StandardCharsets.UTF_8));
            return ByteBuffer.wrap(bytes).getLong() & Long.MAX_VALUE;
        } catch (NoSuchAlgorithmException ex) {
            throw new IllegalStateException(ex);
        }
    }

    public static void main(String[] args) {
        ConsistentHashRing ring = new ConsistentHashRing();
        ring.addNode("node-a", 64);
        ring.addNode("node-b", 64);
        ring.addNode("node-c", 64);
        System.out.println(ring.route("tenant-1001"));
        System.out.println(ring.route("tenant-1002"));
    }
}

Demo 只负责确定目标节点，不包含数据复制和迁移。生产实现还要处理哈希碰撞、节点移除、权重、拓扑副本、路由快照原子替换和观测指标。

十二、热点与倾斜

哈希均匀只针对 Key 数量，不保证流量和数据大小均匀。一个超热 Key、超大租户或单个超大对象仍会压垮所在分片。

治理手段：

• Hot Key：本地/多级缓存、请求合并、拆 Key、只读副本、限流。
• 大租户：目录路由单独分片、独立容量和迁移。
• 数据倾斜：增加虚拟节点、重新加权、拆逻辑 Partition。
• 顺序写热点：Salting 后并行写，查询时聚合；但会增加读放大。
• Kafka 热 Partition：改 Key、拆业务 Topic/Partition，并保持所需顺序边界。

不能仅靠“增加节点”解决单 Key 热点，因为同一个 Key 通常仍映射同一主分片。

十三、扩缩容迁移状态机

flowchart TD
    A["PLANNED生成迁移计划和版本"] --> B["COPYING复制历史数据"]
    B --> C["CATCHING_UP消费增量变更"]
    C --> D["VERIFYING校验数量、版本和摘要"]
    D --> E["DUAL_READ或影子读比较"]
    E --> F["CUTOVER原子发布新路由"]
    F --> G["DRAINING等待旧请求和连接排空"]
    G --> H["CLEANUP过回滚窗口后清理源数据"]

迁移期间应保持单一写入事实源，或使用明确的版本化双写协议。无事务双写源和目标，一边成功一边失败会制造分叉；更常见做法是源端提交后通过 WAL/CDC/日志复制增量，目标按版本幂等应用。

切换必须发布新的 Routing Version。旧客户端写源分片时，源端应拒绝、转发或返回新位置；不能在旧分片静默接受导致数据重新长回去。

十四、迁移失败窗口

窗口	风险	处理
历史复制中	源仍有新写	CDC/WAL 追增量并记录水位
双写一边失败	源目标分叉	单一事实源、Outbox/日志重放、版本幂等
校验只比行数	内容错误未发现	主键范围、版本、摘要和业务抽样
路由发布中	新旧客户端并存	Routing Version、重定向和兼容窗口
切换后回滚	目标产生新写	反向同步或冻结写，不能直接改路由
清理过早	无法回滚	观察期、备份和删除审批
多迁移并发	磁盘/网络饱和	迁移限速、并发预算和业务优先级

十五、商业场景：医疗采集租户扩容

医院租户按目录路由到采集分片。某大型医院增长后单独迁移：

1. 目录服务创建迁移记录 version=28，源 A、目标 D。
2. 按设备 ID 范围复制历史数据并记录断点。
3. 通过数据库日志/Outbox 将新采集事件同步到 D，按事件版本幂等。
4. 影子读取 A、D 对比最新版本、数量和业务摘要。
5. 网关原子发布目录版本 29，把该租户新请求路由到 D。
6. A 收到版本 29 的旧路由写时返回重定向，不继续落旧库。
7. 完成连接排空和观察期后再归档 A 的租户数据。

迁移记录本身必须可恢复，任务重启后从水位继续，而不是从头复制或跳过失败区间。

十六、分片错误与再平衡 Runbook

1. 确认业务 Key、逻辑 Partition、Routing Version、目标节点和实际命中节点。
2. 检查路由函数、Hash Tag、字符编码和不同语言哈希实现是否一致。
3. 检查成员列表/路由表传播、客户端缓存和旧长连接。
4. 检查分片数据量、QPS、P99、磁盘、网络和 Key/租户 TopN。
5. 迁移中检查历史复制水位、CDC Lag、失败重试和版本冲突。
6. 用主键范围、版本和摘要校验，不能只看总行数。
7. 切换异常时先冻结清理，根据目标新写决定正向完成还是反向同步回滚。
8. 控制迁移并发和带宽，避免再平衡压垮正常业务。
9. 修复后演练节点新增、删除、路由旧版本、CDC 中断和大租户迁移。

十七、常见错误

错误	正确理解
一致性哈希保证数据一致	它只减少映射变化，不负责复制和事务
节点从4变5只移动20%取模数据	普通 %N 会重映射大量Key
虚拟节点越多越好	路由内存和迁移碎片也会增加
Key数量均匀就不会热点	流量、大小和租户可能高度倾斜
增加Kafka Partition只提高并发	可能改变Key映射和局部顺序
Redis加节点能解决单热Key	单Key仍在一个Slot和Master
双写即可安全迁移	部分失败会分叉，需事实源和重放协议
发布新路由后旧请求自然消失	缓存、连接和在途请求仍需版本与排空

十八、关联知识点

• MySQL 分库分表
• Redis Cluster Slot
• Dubbo 一致性哈希
• Kafka 原理
• 多副本一致性
• API 与事件契约
• 分片与一致性哈希面试题