分布式缓存用一致性 Hash，把节点和键都映射到一个首尾相接的哈希环上，键沿顺时针找最近节点。相比普通取模 Hash，加减节点时只迁移约 1/N 的键，缓存命中率几乎不受影响。配合虚拟节点，负载还能均匀分布。下文给出原理、对比与可直接运行的实现。
一、普通 Hash 在扩容时崩了
最朴素的路由是 hash(key) % N，N 是节点数。4 个节点时一切正常；一旦加一个节点变成 5，取模基数变了，几乎每个键都映射到不同节点，缓存命中率瞬间跌到接近零，所有请求击穿到数据库。节点少时取模的代价最明显——从 4 扩到 5，约 80% 的键要挪窝。
二、一致性 Hash 解决什么
| 维度 | 普通取模 Hash | 一致性 Hash |
|---|---|---|
| 扩容迁移量 | 近乎全部重映射 | 约 1/N 的键 |
| 节点下线影响 | 全量失效 | 仅其负责的键 |
| 负载均衡 | 依赖 N 固定 | 需虚拟节点辅助 |
| 典型查找 | O(1) | O(log N) |
一致性 Hash 把哈希空间看作一个 [0, 2^32) 的环。节点和键都经同一哈希函数落到环上，键从自己位置顺时针走，碰到的第一个节点就是归属。增减节点时，只有落在新增/移除节点与其上游之间的键需要迁移，其余原地不动。
三、为什么必须加虚拟节点
节点少时，几个物理节点在环上分布很不均匀，某节点可能独占 60% 的键空间。解决办法是给每个物理节点分配多个虚拟节点（vnode）：一台机器在环上散落几十到几百个点，键被均摊到各机器。生产上每物理节点配 100~200 个虚拟节点即可把负载偏差压到 10% 以内；Apache Cassandra 默认 256 个，Amazon DynamoDB 也采用类似方案。没有虚拟节点时，3 台机器在环上可能分布成 10%/30%/60%，热点机器扛大部分请求。加虚拟节点后，每台机器的多个点分散在环各处，它负责的弧段被切成很多小段平均分给邻居；单点失效时负载也平摊到所有存活机器，不会”一棵树倒一片”。
四、Python 实现（含虚拟节点）
用 MD5 做哈希，靠 bisect 做二分查找。增删节点只动对应虚拟节点的环位置。get_node 里 bisect_right 找第一个大于等于键哈希的位置；走到环尾则回绕环首，保证任何键都有归属。
把缓存接入一致性 Hash，按四步推进：
- 选均匀哈希函数（MurmurHash3 或 MD5），确定环空间大小 2^32；
- 给每台物理节点生成 V 个虚拟节点位置，写入有序结构并排序；
- 查键时算哈希，二分找顺时针第一个虚拟节点，映射到物理节点；
- 增删节点只动其虚拟节点位置，并触发相邻节点的数据再平衡。
import hashlib
import bisect
from typing import List
class ConsistentHash:
def __init__(self, nodes: List[str], vnodes: int = 150):
self.vnodes = vnodes
self.ring = {} # 哈希值 -> 物理节点
self.sorted_keys = []
for node in nodes:
self.add_node(node)
def _hash(self, key: str) -> int:
return int(hashlib.md5(key.encode).hexdigest, 16)
def add_node(self, node: str) -> None:
for i in range(self.vnodes):
pos = self._hash(f"{node}#{i}")
self.ring[pos] = node
self.sorted_keys.append(pos)
self.sorted_keys.sort
def remove_node(self, node: str) -> None:
for i in range(self.vnodes):
pos = self._hash(f"{node}#{i}")
self.ring.pop(pos, None)
self.sorted_keys.remove(pos)
def get_node(self, key: str) -> str:
if not self.ring:
raise KeyError("ring is empty")
pos = self._hash(key)
idx = bisect.bisect_right(self.sorted_keys, pos)
if idx == len(self.sorted_keys):
idx = 0 # 环尾回绕到环首
return self.ring[self.sorted_keys[idx]]4.1 验证迁移量
ring = ConsistentHash(["nodeA", "nodeB", "nodeC"], vnodes=150)
before = {k: ring.get_node(k) for k in map(str, range(10000))}
ring.add_node("nodeD")
moved = sum(1 for k in map(str, range(10000))
if ring.get_node(k) != before[k])
print(f"迁移比例 ≈ {moved / 100:.1f}%") # 约 25%，即 1/44.2 另两种思路
Jump Consistent Hashing（Google，2014）用确定性跳跃函数把键映射到桶，O(1) 查找、均衡极佳，但只支持整数桶编号、不便带权。Rendezvous（HRW）哈希对每个键算”键+节点”的最高分，无需建环，节点少时更简单。
五、落地要注意的坑
哈希函数要均匀，优先 MurmurHash3、xxHash，MD5/SHA 也可用但偏慢，别用简单字符串哈希。虚拟节点别少于 100，否则仍有热点。节点故障时靠成员协议（如 gossip）及时更新环，否则请求还会持续发到死节点；并向下游 N 个节点复制数据防丢失。虚拟节点数也不是越多越好——每多一个就多占一条环记录，内存与查找成本线性涨，150~200 是平衡点。Memcached 客户端 ketama、Redis Cluster、NGINX 上游模块都在用这套思路。
六、虚拟节点为什么能均摊负载
靠的是大数定律：每台物理节点有 150 个随机点散布在环上，它拥有的弧段总和趋近均等。虚拟节点少于 100 仍能看到明显倾斜，生产建议 150 起步。Cassandra 默认 256 个，Amazon DynamoDB 也采用类似虚拟节点方案。
七、真实系统的落地位置
Memcached 客户端 ketama、Redis Cluster、NGINX 上游一致性 Hash 模块都用这套思路。CDN 用它对 URL 选边缘节点，某边缘下线只重路由它负责的 URL，其余内容不受影响。负载均衡用它做会话保持，同一用户的请求稳定落到同一后端，增删节点也不丢亲和。
八、别忘了复制
一致性 Hash 只决定主副本归属。节点宕机时它的键若无副本就会丢失，应把键复制到顺时针后续 N 个节点，主节点失效由副本接管。这也解释了为什么移除节点后还要做数据再平衡，把迁出键同步到新 owner。
九、复杂度与内存开销
环用有序数组存虚拟节点，查找走二分 O(log N)，N 为虚拟节点总数。200 虚拟节点 × 100 台机器约 2 万条目，二分约 15 次比较，开销可忽略；增删节点是 O(log N) 的插入删除。跳数一致性 Hash 把查找降到 O(1)，但只支持整数桶编号，不便带权。
常见问题（FAQ）
Q1：虚拟节点设多少合适？
每物理节点 100~200 个，Cassandra 默认 256，偏差可压到 10% 内。
Q2：查找复杂度怎么算？
环上二分查找 O(log N)，N 为虚拟节点总数。
Q3：节点宕机数据会丢吗？
会，需向下游 N 个节点复制副本，单点故障不丢数据。
