ai-infra-interview-305

第 283 题：分布式consistent hashing的实现？virtual node？

题目

分布式consistent hashing的实现？virtual node？

---

完整讲解

一、一致性哈希目的

分布式缓存/存储中，节点增删时希望只影响少量 key 的映射，避免全量 rehash。一致性哈希：将 hash 空间视为环，节点与 key 都映射到环上；key 归属「顺时针方向第一个节点」。增删节点只影响相邻一段 key。

二、Virtual node（虚拟节点）

若节点数少，在环上分布可能不均，导致负载倾斜。虚拟节点：每个物理节点对应多个虚拟节点（如 100～200 个），每个虚拟节点在环上占一点；key 先映射到虚拟节点再落到物理节点。虚拟节点数多则分布更均匀，负载更平衡；实现时虚拟节点名可用 node#v1、node#v2 等 hash 到环上。

三、实现要点

环用有序结构（如 TreeMap）存「hash 值 → 节点」；查找 key 时算 key 的 hash，在环上找第一个 >= 该 hash 的节点（没有则取环首）。虚拟节点插入/删除时维护同一物理节点的多个映射即可。

---

面试要点

• 一致性哈希：hash 环、key 归属顺时针第一节点；增删节点只影响相邻 key。
• 虚拟节点：一物理节点对应多虚拟点，打散到环上，减轻负载倾斜。
• 环用有序结构存 hash→节点；查找 key 找 >= hash(key) 的第一个节点。
• 用于分布式缓存、存储的 sharding 与扩缩容。

---

记忆要点

1. 环上 key 归属顺时针第一节点；增删节点影响局部。
2. 虚拟节点 = 一物理多虚拟、均匀分布；减少倾斜。
3. 实现：有序结构 + 查找 >= hash(key) 的节点。

返回模块

返回总览