罗罗编程学习记录
本页内容 展开查看

02.10.3 一致性哈希与分片

所属:全栈开发面试题库 / 02 数据结构与算法 / 02.10 设计类与手写题

覆盖范围

  • 一致性哈希环原理与虚拟节点
  • 数据倾斜与扩缩容迁移量
  • Jump Consistent Hash
  • 普通取模与一致性哈希对比

高频题速览

编号 题目 难度 频率
02.10.3-001 一致性哈希环原理 基础 ★★★★★
02.10.3-002 虚拟节点解决数据倾斜 基础 ★★★★★
02.10.3-003 扩缩容时迁移量计算 进阶 ★★★★
02.10.3-004 普通取模 vs 一致性哈希 基础 ★★★★
02.10.3-005 Jump Consistent Hash 原理 高级 ★★★
02.10.3-006 一致性哈希缓存预热 进阶 ★★★
02.10.3-007 数据倾斜与负载均衡 进阶 ★★★★
02.10.3-008 分片策略怎么选 进阶 ★★★★

02.10.3-001 一致性哈希环原理

频率 ★★★★★ | 难度 基础

一句话结论

把哈希值空间(如 0~2^32-1)组织成首尾相接的环;节点和 key 都哈希到环上,key 顺时针找到第一个节点即为归属;扩缩容只影响相邻区间的 key。

概念解释

  • 环:哈希值空间首尾相接。
  • 节点哈希:服务器节点也哈希到环上。
  • key 归属:顺时针找第一个节点。
  • 扩缩容:新增/删除节点只影响该节点与前一个节点之间的 key。

原理流程

  1. 把节点 A、B、C 哈希到环上。
  2. key k 哈希到环上某位置。
  3. 从 k 顺时针走,遇到的第一个节点就是 k 的归属。
  4. 新增节点 D,只迁移 D 与前一节点之间的 key。

代码 / 示例

class ConsistentHash {
    private final TreeMap<Integer, String> ring = new TreeMap<>();
    private final List<String> nodes;

    ConsistentHash(List<String> nodes) {
        this.nodes = nodes;
        for (String n : nodes) ring.put(n.hashCode(), n);
    }
    String getNode(String key) {
        int h = key.hashCode();
        Map.Entry<Integer, String> e = ring.ceilingEntry(h);
        return e == null ? ring.firstEntry().getValue() : e.getValue();
    }
}

常见误区

  • 误区:key 和节点用不同哈希函数;正解:同一哈希函数才能在环上比较位置。
  • 误区:ceilingEntry 找不到返回 null 时返回 null;正解:环是循环的,找不到则回绕到 firstEntry。

追问 / 延伸

  • Q:环大小多少合适? A:通常 2^32 或 2^160,越大分布越均匀。
  • Q:为什么不用数组排序? A:TreeMap/有序集合支持 O(log n) 查找,数组二分也行但插入删除慢。

02.10.3-002 虚拟节点解决数据倾斜

频率 ★★★★★ | 难度 基础

一句话结论

一个物理节点对应环上多个虚拟节点(如 150 个),key 哈希到虚拟节点再映射到物理节点;虚拟节点越多,各物理节点在环上的分布越均匀,数据倾斜越小。

概念解释

  • 真实节点:物理服务器。
  • 虚拟节点:真实节点的副本,哈希到环上多个位置。
  • 映射:key -> 虚拟节点 -> 真实节点。
  • 倾斜:节点少时环上位置不均匀,某些节点区间大。

原理流程

  1. 每个真实节点拆成 N 个虚拟节点,如 node#0、node#1、...、node#N。
  2. 所有虚拟节点哈希到环上。
  3. key 顺时针找虚拟节点,再映射回真实节点。
  4. 虚拟节点越多,分布越均匀。

代码 / 示例

class ConsistentHashWithVNodes {
    private final TreeMap<Integer, String> ring = new TreeMap<>();
    private final int vnodes;
    private final Map<String, List<String>> realToV = new HashMap<>();

    ConsistentHashWithVNodes(List<String> realNodes, int vnodes) {
        this.vnodes = vnodes;
        for (String rn : realNodes) addNode(rn);
    }
    void addNode(String rn) {
        List<String> vs = new ArrayList<>();
        for (int i = 0; i < vnodes; i++) {
            String vn = rn + "#" + i;
            ring.put(vn.hashCode(), vn);
            vs.add(vn);
        }
        realToV.put(rn, vs);
    }
    String getRealNode(String key) {
        Map.Entry<Integer, String> e = ring.ceilingEntry(key.hashCode());
        String vn = e == null ? ring.firstEntry().getValue() : e.getValue();
        return vn.substring(0, vn.lastIndexOf('#'));
    }
}

常见误区

  • 误区:虚拟节点越多越好;正解:虚拟节点多内存开销大(每个虚拟节点一个 TreeMap 条目),通常 150~200 足够。
  • 误区:虚拟节点哈希用相同字符串;正解:必须带后缀(#0、#1)才能哈希到不同位置。

追问 / 延伸

  • Q:虚拟节点数怎么定? A:经验值 100~200,节点少时可更多。
  • Q:删除真实节点怎么迁移? A:删除其所有虚拟节点,受影响的 key 重新顺时针找下一节点。

02.10.3-003 扩缩容时迁移量计算

频率 ★★★★ | 难度 进阶

一句话结论

普通取模 hash(key) % N,N 变化时几乎所有 key 都要重新映射(迁移 ~100%);一致性哈希 N 变化时只迁移 1/N 的 key(新增节点从下一节点抢 1/N,删除节点其全部 key 迁到下一节点)。

概念解释

  • 取模:N 变了,hash(key) % N 几乎全变。
  • 一致性哈希:新增节点 D,只从下一节点 B 抢 D 与 B 之间的 key,约 1/N。
  • 删除节点:该节点所有 key 迁到下一节点,约 1/N。

原理流程

  1. 取模:N 台服务器,key 映射到 hash(key) % N。
  2. 从 N 加到 N+1:约 N/(N+1) 的 key 迁移。
  3. 一致性哈希:新增一台,只迁移 1/(N+1) 的 key。
  4. 删除一台:1/N 的 key 迁移。

代码 / 图示

取模:N=4 -> N=5
迁移量 ≈ 1 - 4/5 = 80%

一致性哈希:N=4 -> N=5
迁移量 ≈ 1/5 = 20%

常见误区

  • 误区:一致性哈希扩缩容零迁移;正解:只迁移 1/N,不是零。
  • 误区:删除节点迁移量和新增一样;正解:删除节点时该节点所有 key 都迁到下一节点,也是 1/N。

追问 / 延伸

  • Q:为什么取模迁移量大? A:因为 hash % N 和 hash % (N+1) 之间没有连续关系。
  • Q:数据库分库分表怎么迁移? A:一致性哈希减少迁移量,但实际分库常用范围分片或哈希取模后双写迁移。

02.10.3-004 普通取模 vs 一致性哈希

频率 ★★★★ | 难度 基础

一句话结论

普通取模 hash(key) % N 实现简单但扩缩容迁移量大;一致性哈希扩缩容迁移量小(1/N),但实现复杂且有虚拟节点开销;静态场景用取模,动态扩缩容场景用一致性哈希。

概念解释

  • 取模:数组下标,O(1) 查找。
  • 一致性哈希:环 + 有序集合,O(log n) 查找。
  • 迁移量:取模 1~N/(N+1),一致性哈希 1/N。

原理流程

  1. 节点数固定不变:取模足够,简单高效。
  2. 节点数会变化:一致性哈希减少迁移。
  3. 中间场景:取模 + 预分片(先分 1024 片,再映射到节点),兼顾两者。

代码 / 图示

方案           查找   迁移量    实现复杂度
取模           O(1)   高(100%)  简单
预分片         O(1)   低(1/N片) 中
一致性哈希     O(log n) 低(1/N)  复杂

常见误区

  • 误区:一致性哈希一定比取模好;正解:静态场景取模 O(1) 更简单。
  • 误区:预分片不是一致性哈希;正解:预分片是取模的变体,先分固定数量片,片到节点映射可变。

追问 / 延伸

  • Q:Redis Cluster 用什么? A:16384 个哈希槽,类似预分片,片到节点映射在 cluster 配置中维护。
  • Q:一致性哈希查找复杂度? A:TreeMap O(log n),虚拟节点多时 log n 略大。

02.10.3-005 Jump Consistent Hash 原理

频率 ★★★ | 难度 高级

一句话结论

Jump Consistent Hash 是 Google 提出的极简算法:给定 key 和节点数 n,返回 [0, n) 中的节点号;只需 O(log n) 时间,零内存,分布均匀;适合节点数已知且递增的场景。

概念解释

  • 输入:key(整数)和节点数 n。
  • 输出:bucket ∈ [0, n)。
  • 递推:从 bucket=0 开始,不断用随机数生成新 bucket,直到 bucket >= n。
  • 无内存:不需要维护环,纯函数计算。

原理流程

  1. 初始化 bucket = -1,j = 0。
  2. 当 j < n:用哈希函数生成下一个 j = floor((j+1) * (random ^ ...)),bucket = j。
  3. 返回 bucket。

代码 / 示例

static int jumpConsistentHash(long key, int n) {
    long b = -1;
    long j = 0;
    while (j < n) {
        b = j;
        key = key * 2862933555777941757L + 1; // LCG
        j = (long) ((b + 1) * (double)(1L << 31) / ((key >>> 33) + 1));
    }
    return (int) b;
}

常见误区

  • 误区:Jump Hash 是一致性哈希;正解:Jump Hash 是哈希函数,不需要环,但节点数必须已知且递增。
  • 误区:Jump Hash 支持删除节点;正解:Jump Hash 只支持节点数递增,删除节点会导致分布不均。

追问 / 延伸

  • Q:Jump Hash 适合什么场景? A:节点数可预测递增的场景,如消息队列分区到消费者。
  • Q:分布均匀性? A:数学上证明均匀,且扩缩容迁移量约 1/n。

02.10.3-006 一致性哈希缓存预热

频率 ★★★ | 难度 进阶

一句话结论

新节点加入后,从下一节点迁移 1/N 的 key;迁移期间这部分 key 仍在旧节点,可双写或异步迁移,迁移完成后切流量;预热是把热点 key 主动推到新节点。

概念解释

  • 迁移:key 从旧节点到新节点。
  • 双写:迁移期间新旧节点都写。
  • 预热:主动把热点 key 加载到新节点,避免迁移后冷启动。

原理流程

  1. 新节点加入环,计算受影响的 key 集合。
  2. 异步把这些 key 从旧节点复制到新节点。
  3. 复制期间双写,保证一致性。
  4. 复制完成后,切流量到新节点。

代码 / 图示

新节点 D 加入
受影响区间:B -> D 之间的 key
异步迁移:从 B 复制 key 到 D
双写:迁移期间 B、D 都写
切流:迁移完成,key 归属 D

常见误区

  • 误区:迁移完再切流;正解:迁移期间双写,迁移完成后切流,避免请求打到不存在的 key。
  • 误区:预热就是迁移;正解:预热是主动加载热点,迁移是被动数据搬移。

追问 / 延伸

  • Q:迁移期间旧节点还在吗? A:在,只是不再是这些 key 的归属,切流后旧节点这些 key 可删除。
  • Q:迁移失败怎么办? A:双写保证数据不丢,失败可重试或回滚。

02.10.3-007 数据倾斜与负载均衡

频率 ★★★★ | 难度 进阶

一句话结论

节点少时环上位置不均匀,某些节点区间大导致数据倾斜;虚拟节点把一个节点拆成多个,均匀分布到环上;倾斜还可能由 key 分布不均引起(如热点 key),需额外处理。

概念解释

  • 环倾斜:节点在环上位置集中,区间大小不均。
  • key 倾斜:某些 key 访问量远高于平均。
  • 虚拟节点:打散环倾斜。
  • 热点 key:需要额外拆分或缓存。

原理流程

  1. 节点少(如 3 台):环上位置集中,区间大小差异大。
  2. 加虚拟节点:每个节点 150 个副本,环上位置均匀。
  3. key 倾斜:热点 key 单独处理(拆分 key 或本地缓存)。

代码 / 图示

3 个真实节点:
环上位置:A ----- B --- C ---- A
区间不均

加虚拟节点(每个 150 个):
环上位置均匀分布
各真实节点负责区间 ≈ 1/N

常见误区

  • 误区:虚拟节点解决 key 倾斜;正解:虚拟节点解决环倾斜(节点间负载不均),不解决热点 key。
  • 误区:虚拟节点越多越好;正解:通常 150~200 足够,过多增加内存和查找时间。

追问 / 延伸

  • Q:热点 key 怎么处理? A:拆分 key(如 key_1、key_2)分散到不同节点,或本地缓存。
  • Q:Redis Cluster 怎么处理倾斜? A:16384 个槽位均匀分布,key 按 slot 归属。

02.10.3-008 分片策略怎么选

频率 ★★★★ | 难度 进阶

一句话结论

范围分片适合顺序访问(如按时间范围查),哈希分片适合均匀分布(如用户数据),一致性哈希适合动态扩缩容;选分片策略要考虑查询模式、扩缩容频率、数据倾斜。

概念解释

  • 范围分片:按 key 范围划分,适合范围查询,但可能倾斜。
  • 哈希分片:按 hash(key) 划分,均匀,但范围查询要扫所有分片。
  • 一致性哈希:动态扩缩容迁移量小。

原理流程

  1. 主要按范围查询(如按时间):范围分片。
  2. 主要按点查询(如用户 ID):哈希分片。
  3. 需要动态扩缩容:一致性哈希或预分片。
  4. 数据有热点:额外拆分热点 key。

代码 / 图示

策略       查询模式    扩缩容    倾斜风险
范围分片   范围友好    迁移大     高(热点区间)
哈希分片   点查友好    迁移大     低
一致性哈希 点查友好    迁移小     低(需虚拟节点)

常见误区

  • 误区:范围分片一定倾斜;正解:只要 key 分布均匀,范围分片也可以均衡。
  • 误区:哈希分片不能范围查询;正解:可以,但要扫所有分片,性能差。

追问 / 延伸

  • Q:MySQL 分库分表用什么? A:范围分片(按时间)或哈希分片(按用户 ID),常见预分片。
  • Q:MongoDB 用什么? A:范围分片(range sharding)或哈希分片(hashed sharding),由用户选择。

待整理清单

  • [ ] Redis Cluster 16384 槽位设计
  • [ ] 分库分表双写迁移方案
  • [ ] 一致性哈希 + 虚拟节点完整代码