系统设计面试题

一致性哈希:为什么和怎么做

一致性哈希是什么?Cassandra和DynamoDB为什么用它?

为什么面试官会问这道题

系统设计和分布式都考。追问"为什么要虚拟节点"能筛出真懂和背书的。

如何回答

  1. 1

    问题:hash(key)%N在加减节点时几乎所有key都重新映射——缓存雪崩、数据大迁移。

  2. 2

    一致性哈希:key和节点都哈希到同一圈(2^32哈希空间)。每个key属于顺时针第一个节点。加节点只动它和前驱之间的key。

  3. 3

    不均衡:节点哈希聚堆时负载不均。虚拟节点修正——每个物理节点注册K个随机位置。

  4. 4

    副本:RF=R时key顺时针找R个不同物理节点。

  5. 5

    用在Cassandra、DynamoDB、memcached客户端(ketama)、部分CDN源站路由。

参考回答示例

hash(key)%N加一个节点要重新映射大部分key。一致性哈希把key和节点放同一圈(2^32);每个key归顺时针最近的节点。加节点X只动X和前驱之间的弧。但朴素放置会让圈不均——热节点过载。虚拟节点解决:每个物理节点发布K个(如100-200)位置,负载铺开。副本:从key位置顺时针走,找到R个不同物理节点(跳过同一物理的多个vnode)。Dynamo、Cassandra、ketama式memcached客户端都这样做。vs Rendezvous哈希:一致性哈希排序vnode列表查找O(log N),rendezvous O(N)但无状态。

实用技巧

  • 每物理节点K个vnode凭实证选——太少不均、太多费内存。100-256典型。

  • 读多的缓存场景,一致性哈希+少量副本能覆盖大部分故障模式。

  • 即答侠给了图和圈的数学——白板画得出。

常见问题

Rendezvous哈希 vs 一致性哈希?

Rendezvous(HRW)无需节点表——每个客户端独立取哈希最大的节点。更简单但查询开销大。多客户端要达成一致时一致性哈希更合适。

Redis Cluster用一致性哈希吗?

不是——Redis Cluster用16384个固定哈希槽映射到节点。槽重平衡是显式的。比一致性哈希简单但灵活度差。

面试时担心忘词?即答侠实时助你

即答侠 AI 实时监听面试对话,自动识别问题并即时生成回答建议——无感辅助,让你从容应对每一道题。

免费试用即答侠