数据分片与一致性哈希

本文是分布式系统系统学习系列的 L2 核心篇。前置：30. distributed-transactions-all-solutions。 面试题汇总参考：04-consistent-hashing

为什么需要数据分片

单机数据库的容量和吞吐量是有上限的。当数据量超过一台机器的磁盘、计算能力，或者单个请求的延迟已经无法满足 SLA，就必须把数据拆开，分散到多台机器上——这就是分片（sharding）。

分片不是新鲜事，分布式数据库、缓存集群、消息队列都依赖它来做水平扩展。但"怎么拆"这件事，直接影响扩容时的迁移成本和查询效率。

三种分片维度

哈希分片

对 key 取哈希值，然后对分片数取模，决定数据去哪个节点。实现简单，路由快，但扩容时几乎全量搬迁——节点数变了，相同的 key 取模结果大变样。

范围分片

按 key 的字典序或者数值范围切分，比如 [a-g) 在节点 1，[g-p) 在节点 2。范围查询友好，但容易产生热点——如果 key 是自增 ID，新数据全往最后一个节点写。

查表分片

维护一张路由表，显式记录每个 key 范围对应哪个节点。灵活，但路由表本身是单点，查表也需要一次额外网络开销。

三种方案没有绝对优劣，取决于访问模式。哈希分片在工程上用得最广，它的缺陷也最值深入研究。

简单哈希取模的致命伤

假设 3 个节点，key 的哈希值 hash(key) % 3 决定归属。扩容到 4 个节点后，变成 % 4，绝大多数 key 的归属都变了。对于一个 1000 万 key 的缓存集群，这意味着几乎 1000 万次重新映射——数据搬迁量 ≈ 节点增量比例，而不是只影响新节点。

这也是为什么"加机器就能解决一切"是个错觉：加机器带来的迁移成本，往往比加机器本身更大。

一致性哈希：环与虚拟节点

一致性哈希把哈希空间组织成一个闭环（0 到 2^32-1），节点和 key 都哈希到环上。key 顺时针找到的第一个节点就是它的归属。

扩容时，只有相邻区间的数据受影响。假设环上原有节点 A、B、C，新增节点 D 落在 B 和 C 之间，只需要把 B→D 之间那部分数据从 C 迁到 D，其他节点不动。搬迁比例 = 1/N，而不是接近 100%。

但"节点少"时有个问题：节点在环上分布不均匀，导致数据倾斜。一种极端情况——两个节点落在环上非常靠近的位置，一个节点几乎扛全部流量，另一个几乎空着。

虚拟节点解决这个问题：一个物理节点在环上放多个虚拟位置，比如 150 个虚拟节点。物理节点的路由能力 = 它在环上的虚拟节点数量比例。当节点数量少时，虚拟节点越多，分布越均匀。

虚拟节点还有另一个好处：不同物理节点的虚拟节点可以配置权重，比如机器 A 是 64G 内存，机器 B 是 32G，A 的虚拟节点数可以设成 B 的两倍，实现"按容量分配"。

受控再平衡：固定槽数方案

一致性哈希不是唯一方案。Redis Cluster 和 DynamoDB 用了另一种思路：固定槽数。

Redis Cluster 有 16384 个槽，每个 key 通过 CRC16(key) % 16384 确定归属槽。槽到节点的映射关系是显式维护的，增删节点时只需要迁移槽。DynamoDB 的 partition 也是类似——固定 partition 数，扩容时只分裂部分 partition。

对比一致性哈希，固定槽数方案的好处是：

• 迁移粒度可控（按槽迁移，不是按节点区间）
• 槽->节点映射可以人为干预，支持手动调节
• 不需要虚拟节点，均匀分布天然有保障

代价是路由表更大（16384 条），但现代机器内存完全不是问题。

跨分片查询的代价

分片解决了"单机放不下"的问题，但带来了"跨分片查询"的代价。

Scatter-Gather：查询发给所有分片，各分片并行执行，结果汇总后返回。简单，但延迟受最慢分片限制，且如果有二级索引，每个分片都得维护自己的索引副本。

全局二级索引 vs 本地二级索引：本地索引在每个分片内部维护，跨分片查询时要做 scatter-gather；全局索引单独维护一个索引表，写入时多一次开销，但按索引查询时不需要扫所有分片。

工程上常见的选择是：业务按主键维度访问为主（比如按 userId 分片，查 userId 的单条记录），那就用本地索引；如果按非分片键维度查询很多（比如按 email 查用户），要么加全局索引，要么用 ES 做旁路。

动手实操

下面是一个一致性哈希的 Java 实现，用 TreeMap 模拟哈希环，支持虚拟节点：

import java.util.*;

public class ConsistentHashRing {
    private final TreeMap<Integer, String> ring = new TreeMap<>();
    private final int virtualNodes;
    private final List<String> nodes = new ArrayList<>();

    public ConsistentHashRing(int virtualNodes) {
        this.virtualNodes = virtualNodes;
    }

    public void addNode(String nodeId) {
        nodes.add(nodeId);
        for (int i = 0; i < virtualNodes; i++) {
            int hash = (nodeId + "#" + i).hashCode() & 0x7fffffff;
            ring.put(hash, nodeId);
        }
    }

    public void removeNode(String nodeId) {
        nodes.remove(nodeId);
        for (int i = 0; i < virtualNodes; i++) {
            int hash = (nodeId + "#" + i).hashCode() & 0x7fffffff;
            ring.remove(hash);
        }
    }

    public String getNode(String key) {
        if (ring.isEmpty()) return null;
        int hash = key.hashCode() & 0x7fffffff;
        Map.Entry<Integer, String> entry = ring.ceilingEntry(hash);
        if (entry == null) {
            entry = ring.firstEntry(); // 环绕
        }
        return entry.getValue();
    }

    // 扩容搬迁比例实验：从 N 节点扩到 N+1 节点
    public static double migrationRatio(ConsistentHashRing ring, int keyCount) {
        // 先用 N 个节点分配 key
        // 加一个节点后统计多少 key 换了节点
        Set<String> before = new HashSet<>();
        for (int i = 0; i < keyCount; i++) {
            before.add(ring.getNode("key-" + i));
        }
        // 模拟... 简化起见直接返回理论值
        return 1.0 / ring.nodes.size(); // 理论值
    }

    public static void main(String[] args) {
        ConsistentHashRing ring = new ConsistentHashRing(150);
        ring.addNode("node-A");
        ring.addNode("node-B");
        ring.addNode("node-C");

        System.out.println("key1 -> " + ring.getNode("key1"));
        System.out.println("key2 -> " + ring.getNode("key2"));
        System.out.println("key3 -> " + ring.getNode("key3"));

        // 观察扩容影响
        ring.addNode("node-D");

        // 只影响相邻区间，大部分 key 归属不变
        // 理论搬迁比例 ≈ 1/4 = 25%
        System.out.println("搬迁比例 ≈ 1/N = " + migrationRatio(ring, 10000));
    }
}

关键行解释：

• hashCode() & 0x7fffffff：确保哈希值为非负整数
• ceilingEntry(keyHash)：找顺时针第一个节点
• firstEntry()：环尾绕回开头
• (nodeId + "#" + i)：虚拟节点命名，i 从 0 到 virtualNodes-1

理论搬迁比例：从 N 个节点扩到 N+1 个，搬迁比例 = 1/(N+1)。一致性哈希下，只有新增节点在环上的邻居区间被影响，其他节点完全不动。

常见误区与小结

• "一致性哈希就不用迁移数据"——错。迁移只发生在相邻区间，减少了量，不是零。
• "虚拟节点越多越好"——不是。虚拟节点过多导致路由表变大、查找变慢，工程上 100-200 个虚拟节点/物理节点已经足够。
• "哈希分片最均匀"——不一定。哈希分片只对均匀分布的 key 有效，如果 key 有聚类特征（比如同一用户的 UUID 前缀相同），哈希取模后仍然可能倾斜。
• "一致性哈希解决了一切分片问题"——不是。跨分片查询、事务、排序这些问题，无论用什么分片方式都绕不开。
• "固定槽数方案比一致性哈希好"——不绝对。固定槽数需要额外维护槽映射表，一致性哈希适合"节点即槽位"的自治场景（如 Cassandra），各有取舍。

小结：分片是水平扩展的基础，核心矛盾是"扩容时的迁移成本"。一致性哈希用环+虚拟节点把迁移范围从"几乎全量"降到"1/N"，固定槽数方案则用预分配槽让迁移粒度更可控。跨分片查询是另一个维度的代价，选择分片策略时必须一起考虑。

下一篇进入分布式设计模式：选举、租约、故障检测与 Gossip。

参考

参考：Karger et al. "Consistent Hashing and Random Trees" (1997) — 原始论文，至今仍是分布式缓存和路由表的理论基础。 参考：Redis Cluster Spec — 16384 个槽的设计与迁移协议，是固定槽数方案的工程范本。 参考：DynamoDB 分区文档 — 理解 partition 分裂与扩容的新思路。