一致性哈希解决什么问题？虚拟节点有什么用？

面试问 359 约 2 分钟读完

面试怎么回答

普通取模在节点数变化时几乎所有 key 都要重新分布。一致性哈希把节点和 key 都映射到一个哈希环上，key 顺时针找第一个节点，增删节点只影响相邻的一段区间，平均只迁移约 1/N 的数据。虚拟节点让每个物理节点在环上占很多个位置，解决节点少时分布不均、以及节点下线后负载集中到一个邻居的问题，还能按机器性能分配权重。Redis Cluster 的固定哈希槽是同样思路的另一种实现。

先把这段讲顺；面试官追问时，再展开下面的原理和细节。

详细讲解

分布式缓存、分库分表、Kafka 之外的很多路由场景都会被问到：节点数变化时，数据怎么尽量少迁移？

普通取模的问题

用 hash(key) % N 决定数据放在哪个节点，简单直接。但节点数从 N 变成 N+1 时，几乎所有 key 的取模结果都会变，意味着绝大部分数据要迁移，缓存会大面积失效。

一致性哈希怎么做

把哈希值空间想象成一个环（比如 0 到 2^32-1 首尾相接）：

每个节点按自己的标识计算哈希，落在环上的某个位置；
每个 key 也计算哈希，落在环上后顺时针找到的第一个节点，就是它的归属节点。

增加一个节点时，只有新节点和它逆时针方向前一个节点之间的那一段 key 需要迁移；删除节点时，也只影响它负责的那一段。平均下来，只有约 1/N 的数据需要移动。

虚拟节点解决什么

节点少的时候，它们在环上的位置可能分布不均，有的节点负责的区间很大，负载严重倾斜；某个节点下线后，它的全部数据都压到顺时针下一个节点上。

虚拟节点的做法是：每个物理节点在环上放很多个位置（比如 100 到 200 个），key 先找到虚拟节点，再映射回物理节点。这样每个物理节点负责的是很多个分散的小区间，负载更均匀；一个节点下线时，它的数据会分散到多个节点上。还可以按机器性能给不同节点分配不同数量的虚拟节点。

和大数据的关系

Cassandra、DynamoDB 一类系统用它做数据分布；Redis Cluster 用的是固定 16384 个哈希槽，思路类似：先把 key 映射到固定数量的槽，再把槽分配给节点，扩容时迁移的是槽。