一致性哈希是一种特殊的哈希算法：当集群中增加或减少节点时，它能保证大部分数据不需要重新分配，只有少部分数据受影响。
类比：你有 3 个书架放书，普通哈希像「打乱重排」，一致性哈希像「只挪动几本书」。
假设你有 3 台缓存服务器，需要把数据均匀分布到它们上面。最直觉的做法：
server = hash(key) % N （N = 服务器数量）
N 从 3 变成 2，几乎所有 key 的 hash % N 结果都变了！
~66% 的数据需要重新分配
N 从 3 变成 4，同样几乎所有 key 的映射都变了。
~75% 的数据需要重新分配
hash % N 的方式，N 一旦变化，所有数据的归属都会打乱重来。这在大规模系统中会导致：
一致性哈希的巧妙之处：它把哈希值空间组织成一个环（Hash Ring）。
哈希环上的每个位置对应一个哈希值（0 到 232-1）。
hash(IP/名称) 放到环上的某个位置hash(key) 也放到环上的某个位置hash(IP) 映射到环上的一个点。
hash(key)，在环上找到对应位置，然后沿顺时针方向找到第一台服务器，该数据就存在这台服务器上。
D 落在 A 和 B 之间：
只迁移 ~25% 的数据
B 下线后：
只迁移 ~33% 的数据
hash % N 增减节点时，几乎所有数据（~75%~100%）都要迁移。一致性哈希只影响 1/N 的数据量。
如果只有 3 台服务器，它们在环上的位置可能分布不均匀，导致某台服务器承担过多数据。
为每台服务器创建多个「分身」，每个分身映射到环上的不同位置：
虚拟节点越多，数据分布越均匀（大数定律）。实际生产中通常用 100~200 个虚拟节点。
import hashlib
from bisect import bisect_right
class ConsistentHash:
def __init__(self, nodes=None, replicas=150):
# replicas: 每个真实节点的虚拟节点数量
self.replicas = replicas
self.ring = {} # hash值 -> 真实节点名
self.sorted_keys = [] # 排序后的hash值列表
for node in (nodes or []):
self.add_node(node)
def _hash(self, key):
# 用 MD5 生成 32 位整数哈希值
return int(hashlib.md5(key.encode()).hexdigest(), 16)
def add_node(self, node):
# 为一个真实节点创建多个虚拟节点
for i in range(self.replicas):
vnode_key = f"{node}:v{i}"
h = self._hash(vnode_key)
self.ring[h] = node
self.sorted_keys.append(h)
self.sorted_keys.sort()
def remove_node(self, node):
# 移除一个节点及其所有虚拟节点
for i in range(self.replicas):
vnode_key = f"{node}:v{i}"
h = self._hash(vnode_key)
del self.ring[h]
self.sorted_keys.remove(h)
def get_node(self, key):
# 查找 key 应该存储在哪个节点
if not self.ring:
return None
h = self._hash(key)
# 二分查找：找到顺时针方向第一个 >= h 的位置
idx = bisect_right(self.sorted_keys, h)
# 如果超出列表末尾，绕回环的起点
if idx == len(self.sorted_keys):
idx = 0
return self.ring[self.sorted_keys[idx]]
# ---- 使用示例 ----
ch = ConsistentHash(["Server-A", "Server-B", "Server-C"])
# 查找数据归属
keys = ["user:1001", "user:1002", "order:500", "product:88"]
for k in keys:
print(f"{k} -> {ch.get_node(k)}")
# 新增节点后，大部分 key 不变
ch.add_node("Server-D")
print("--- 新增 Server-D 后 ---")
for k in keys:
print(f"{k} -> {ch.get_node(k)}")| 对比维度 | 传统 hash % N | 一致性哈希 |
|---|---|---|
| 节点增减影响 | 几乎所有数据重新分配 | 仅 1/N 数据受影响 |
| 缓存命中率 | 节点变动时急剧下降 | 基本保持稳定 |
| 数据分布均匀性 | 天然均匀 | 需要虚拟节点保证 |
| 实现复杂度 | 极简（一行代码） | 中等（需要维护环和二分查找） |
| 适用场景 | 固定节点数、无扩缩容 | 分布式缓存、弹性伸缩 |
ketama 一致性哈希负载均衡