约 14 分钟7 张卡

一致性哈希

一致性哈希是一类在节点集合变化时，尽量保留已有键归属的映射方法。它适用于需要按键选择缓存节点、存储节点或服务实例的场景，可以减少扩缩容造成的重新分配。

面试中，画出哈希环只是第一步。还要能说明哪些键会移动、虚拟节点改善了什么，以及为什么“算出了新节点”不代表数据已经迁移完成，也不代表各节点负载相同。本文用顺时针寻找后继节点的环实现讲解。

1. 面试核心

先记住这几条，再读正文

键和节点位置映射到同一哈希空间，查询选择顺时针遇到的第一个位置，再找到它所属的物理节点。环空间固定，不随物理节点数量重新取模。卡 · 节点数量取模的问题
保留旧节点位置时，新增节点只接走自己的区间，删除节点只重新分配它原来负责的键。使用虚拟节点后，一个物理节点涉及多个区间，可能与多台机器交换数据。卡 · 节点增删与映射变化
虚拟节点让一台机器承担多个分散区间，改善有限节点下的分布并表达容量权重；数量比例不等于实际键数、字节数或请求量的精确比例。卡 · 虚拟节点与权重
同一个键仍选中同一个所有者，增加虚拟节点不能拆开单键热点。需要按读取、可合并写入或严格顺序写入的语义处理。卡 · 为什么单键热点仍然存在
映射变化不负责复制历史数据、接住增量或协调写权，存储迁移需要单独保证数据完整和旧路由隔离。卡 · 负载均衡和存储迁移有什么不同
虚拟节点不是数据副本，“一致性”也不表示强一致读写；副本放置、复制和共识是另外的职责。卡 · 虚拟节点不是副本，一致性哈希不是共识
各参与方必须使用相同的节点身份、编码、哈希规则、权重和成员版本。规则不一致时，即使输入业务键相同，也可能得到不同归属。卡 · 环上的位置不是数据本身

2. 节点数量取模的问题

卡 · 一致性哈希怎样定位节点，与直接按节点数量取模有什么区别？

一种直接的分配方式是 hash(key) % N，把余数当作节点编号。问题在于，节点数量从 N 变成 N+1 时，所有键都改用新的除数，许多原本属于健康节点的键也会改变归属。

例如用哈希值 0 到 11 分别对 3 和 4 取模，只保留编号 0、1、2 对应的原节点，再新增编号 3：

哈希值	`% 3`	`% 4`	归属是否变化
0、1、2	0、1、2	0、1、2	不变
3、4、5	0、1、2	3、0、1	改变
6、7、8	0、1、2	2、3、0	改变
9、10、11	0、1、2	1、2、3	改变

这个小例子中，12 个键有 9 个换了节点。用于缓存时，大量旧缓存可能暂时用不上；用于存储时，需要重新定位数据。实际系统也可以使用固定逻辑分片再映射到机器，避免直接按机器数量取模，见数据拆分中的分片方式。一致性哈希是另一种控制变化范围的办法。

3. 哈希环与后继节点

卡 · 一致性哈希怎样定位节点，与直接按节点数量取模有什么区别？卡 · 相同业务键在两个客户端得到不同节点，应检查哪些映射条件？

哈希环把一个固定整数空间首尾相接。节点位置和键位置都落在这个空间内；超过最大位置后，继续从最小位置寻找。

先假设每个物理节点只有一个位置。为了方便推导，用 0 到 99 的空间，三个节点分别位于 A=10、B=50、C=80。查询从键位置出发，按数值增大的方向，选择第一个不小于它的节点位置；没有找到时回到最小节点位置。

键位置	负责节点	原因
5	A	第一个不小于 5 的位置是 10
10	A	恰好命中 A 的位置
30、50	B	第一个后继位置是 50
70	C	第一个后继位置是 80
90	A	超过 80 后绕回 10

因此，B 负责 (10, 50]，C 负责 (50, 80]，A 负责跨过环尾的 (80, 99] 与 [0, 10]。这里采用左开右闭的边界约定；实现可以采用其他约定，但构建、查询和迁移必须一致。

3.1 环上的位置不是数据本身

路由只决定请求交给哪台机器，机器内部仍需根据完整键存取记录。两个业务键哈希到同一位置，会去同一个节点，但不应因此被当成同一条记录；精确区分键仍遵守哈希表的相等关系。

节点位置碰撞则影响环的构建。不能用 位置 → 节点 的字典静默覆盖另一个节点。可以在构建时拒绝碰撞，也可以约定稳定的重新取点或排序规则；所有参与方必须得到同一结果。后面的示例选择检测并拒绝，避免用随机重试悄悄改变其他进程的环。

4. 节点增删与映射变化

卡 · 增加或删除一个节点，会影响哪些键，迁移比例是否固定？

4.1 新增节点

在刚才的环上增加 D=40，已有 A、B、C 的位置不动。D 接管 (10, 40]，这些键原本由 B 负责；B 继续负责 (40, 50]，其他区间不变。

由此可以推出一个检查条件：只新增 D 的位置时，改变归属的键，新所有者一定是 D。如果发现一个键从 A 变到 C，就要检查是否同时移动了旧节点、改变了哈希规则或调整了其他权重。

4.2 删除节点

回到只有 A、B、C 的原环，删除 B。B 原来的 (10, 50] 被顺时针下一个节点 C 接管；原来属于 A 或 C 的键不需要改变归属。

对应检查条件是：只删除 B 的位置时，改变归属的键，旧所有者一定是 B。如果 B 已经宕机且数据没有副本，算法只能算出新的归属，无法凭空恢复 B 上的数据。

4.3 迁移比例的条件

当各节点等权、位置分布合适，且大量键近似均匀分布时，从 N 台增加到 N+1 台，新增节点预期承担约 1/(N+1) 的键；从 N 台删除一台，原来约 1/N 的键需要重新分配。

这不是每次操作必然满足的百分比。一台节点只占一个随机位置时，它前面的区间可能很大，也可能很小；键数量有限、记录大小不同或访问集中时，实际迁移键数、迁移字节数和转移请求量更不能混为一谈。上述变化范围还假设旧位置、哈希规则和其他节点权重保持不变，不包括副本集合的额外调整。

5. 虚拟节点与权重

卡 · 虚拟节点解决什么问题，权重为 1:2 是否意味着负载严格为 1:2？

虚拟节点是物理节点在环上的一个位置及其所属关系。一台机器可以对应 A:0、A:1 等多个位置，查询先找到某个虚拟节点，再回到所属机器 A。它不必对应独立进程，也不表示多保存了一份数据。

多个分散的小区间，可以降低单个大区间偶然落在某台机器上的影响。一台机器退出时，它的多个区间也有机会交给不同机器，避免全部交给一个物理邻居。这个效果依赖位置分布，不能保证每台机器获得完全相同的负载。

5.1 用位置数量表达容量权重

节点性能不同时，可以让容量更大的节点拥有更多位置。例如 A、B、C 权重为 1:2:1，每份权重对应 32 个位置，则分别生成 32、64、32 个位置。位置分布合适时，B 预期承担更多键。

位置数量是配置量，实际负责的环区间长度才直接影响均匀键的分配。两个位置可能非常接近，所以 32:64:32 不意味着实际请求严格按 1:2:1 分配。Envoy 1.31.0 的 ring hash 文档也明确说明，少量位置不足以表达目标权重，需要观察实际环分布。

调整权重同样会触发迁移。如果只给 B 增加稳定编号的新位置，改变归属的键只会转给 B；如果整个实现重新计算所有节点的位置数量或身份，就不能继续套用这个局部变化条件。

5.2 虚拟节点的代价

更多虚拟节点需要保存更多路由条目，增加构建、发布和迁移管理的成本。若环上有 V 个位置，排序数组需要 O(V) 空间，构建排序为 O(V log V)，一次后继查找为 O(log V)，另加键本身的哈希成本。

虚拟节点数量没有脱离规模和负载的万能值。需要同时观察键数、字节数、请求量、队列与延迟，并考虑迁移时的带宽和磁盘压力。单靠增加位置数量，不能修复错误的分片键或消除大对象带来的容量倾斜。

6. 热点、迁移与一致性边界

卡 · 虚拟节点很多、键数分布均匀，为什么仍可能有一台机器过载？卡 · 扩容后发布新哈希环，为什么可能读不到数据或出现双写？卡 · 一致性哈希、虚拟节点、副本复制与 Raft 分别负责什么？

6.1 为什么单键热点仍然存在

同一个键采用同一份环配置，总是找到同一个首选所有者。即使其他键分配得很均匀，一个热门键的请求也可能压满这台机器。增加虚拟节点最多改变它由谁负责，不会把这个键自动拆成多个独立键。

读取热点可以结合缓存副本和请求合并；可合并的计数可以拆成子计数；严格顺序写入则需要保留所有者并限制入口。这些方案改变了存储或访问语义，不能仅修改路由就假定正确，具体取舍见数据拆分中的热点。

6.2 负载均衡和存储迁移有什么不同

一致性哈希用于请求分发时，计算结果是本次请求的候选后端。按用户或资源键保持亲和性有利于利用本地缓存；但这不等于根据实时忙闲选择后端，也不会把已经建立的连接自动搬到新机器。健康检查和重试策略可能改变最终处理节点，应由具体负载均衡实现说明。

用于持久化存储时，目标节点必须有正确的数据，或者能够按迁移协议找到旧数据。修改路由以后再慢慢复制，会让部分读请求找不到记录，也可能让新旧节点同时接受写入。

因此需要在切换前后处理历史数据、并发增量、校验、路由版本和旧端写入隔离。完整流程由数据拆分的扩容迁移解释。缓存有时可以回源重建，但仍需评估集中失效造成的回源压力，不能把缓存的恢复办法直接用于唯一的数据副本。

6.3 虚拟节点不是副本，一致性哈希不是共识

分片回答“这个键由谁负责”，副本回答“还在哪些节点保存副本”。如果沿环选择多个位置作为副本候选，必须跳过同一物理节点的其他位置，否则选中三个虚拟节点，可能实际只有一台机器；故障域隔离还要进一步考虑机架或可用区。

确定副本集合以后，仍要设计数据传输、成功确认、冲突和故障恢复。Dynamo 2007 论文分别讨论了分区、复制、版本管理和成员发现，不能把它们都归结为一个哈希算法。

一致性哈希也不会让两个持有不同成员列表的客户端立即达成一致。它控制的是映射变化的范围；Raft等协议负责的日志共识，以及一致性模型描述的读写结果，是其他问题。

6.4 固定哈希槽与哈希环是不是一回事

不是。Redis 6、7 的 Cluster 先把键映射到固定的 16384 个槽，再维护槽到节点的归属。扩缩容主要改变槽的所有者，不把机器位置放入本文的后继环重新查找。两者都能通过一层映射减少不必要的重新分配，但路由与迁移机制不同，见Cluster 与哈希槽。

7. 可复现的环实现

卡 · 相同业务键在两个客户端得到不同节点，应检查哪些映射条件？

下面使用 Python 3 的排序数组和 bisect_left 构建环快照，节点变化时创建新环，不原地修改旧环。节点 ID 和虚拟节点编号共同生成位置，键使用另一种固定前缀；SHA-256 的前 8 个字节按大端转换为 64 位整数。代码只负责映射，不包含发现服务、网络请求、副本或数据迁移。

from bisect import bisect_left
from hashlib import sha256


def position(text: str) -> int:
    return int.from_bytes(sha256(text.encode("utf-8")).digest()[:8], "big")


class Ring:
    def __init__(self, weights: dict[str, int], vnodes: int = 32):
        if not weights or type(vnodes) is not int or vnodes <= 0:
            raise ValueError("nonempty nodes and positive vnodes required")
        entries = []
        for node, weight in weights.items():
            if not isinstance(node, str) or not node:
                raise ValueError("node ID must be a nonempty string")
            if type(weight) is not int or weight <= 0:
                raise ValueError("weight must be a positive integer")
            for i in range(vnodes * weight):
                entries.append((position(f"node:{node}:{i}"), node))
        entries.sort()
        points = tuple(point for point, _ in entries)
        if len(set(points)) != len(points):
            raise ValueError("token collision; ring was not installed")
        self.points = points
        self.nodes = tuple(node for _, node in entries)

    def owner_at(self, point: int) -> str:
        if not 0 <= point < 2**64:
            raise ValueError("point is outside the ring")
        i = bisect_left(self.points, point)
        return self.nodes[i % len(self.points)]

    def owner(self, key: str) -> str:
        return self.owner_at(position("key:" + key))


old = Ring({"A": 1, "B": 1, "C": 1})
added = Ring({"A": 1, "B": 1, "C": 1, "D": 1})
removed = Ring({"A": 1, "C": 1})
keys = [f"key:{i}" for i in range(1000)]

moved_add = [key for key in keys if old.owner(key) != added.owner(key)]
moved_remove = [key for key in keys if old.owner(key) != removed.owner(key)]
assert all(added.owner(key) == "D" for key in moved_add)
assert all(old.owner(key) == "B" for key in moved_remove)
assert all(removed.owner(key) != "B" for key in keys)
print("add D:", len(moved_add))
print("remove B:", len(moved_remove))