功能说明
ConsistentHashRing 把每个物理节点映射为多个虚拟副本,计算哈希后放入有序环。查找键时计算键的哈希,用二分查找找到环上第一个大于等于该哈希的点,其所属节点就是目标。节点增删只影响环上相邻的一段,因此大部分键仍然映射到原节点,适合分布式缓存、分片存储和无状态服务的会话路由。
每个节点默认创建 64 个虚拟副本,副本数量越多,键分布越均匀,但环的存储和查找开销也越大。add_node 和 remove_node 都是幂等的,重复添加或删除不存在的节点不会报错。nodes 属性返回排序后的节点名,get_node 在空环上抛出 RuntimeError。
关键代码
查找使用 bisect_left,越过环末尾时回到起点:
point = self._hash(key)
index = bisect.bisect_left(self._ring, point)
if index == len(self._ring):
index = 0
return self._owners[self._ring[index]]
add_node 对每个副本计算 节点名#序号 的哈希,遇到已占用的点则跳过,保证一个环点只属于一个节点。
使用注意
哈希使用 SHA-256 的前 8 字节,碰撞概率很低但并非为零;实现遇到碰撞会跳过该副本,而不是覆盖已有节点。删除节点时只移除确实属于它的环点,避免误删碰撞情况下其他节点的点。节点名必须是非空字符串,键也必须非空。
虚拟副本数量需要在均匀性和内存之间权衡;节点数量很少时,即使 64 个副本也可能出现分布不均。该实现把所有状态保存在进程内,多个客户端必须使用相同的节点列表和副本数才能得到一致映射。节点权重不同(例如容量更大的机器)需要按权重调整副本数,本实现未内置。删除最后一个节点后环为空,继续查询会抛错。
验证方式
示例用三个缓存节点和 12 个用户键统计分布,删除 cache-b、加入 cache-d 后再次统计,并计算映射发生变化的键数量。由于只移除一个节点并加入一个节点,变化数量应明显小于全部键,体现一致性哈希的稳定性。最后在空环上查询,应输出 hash ring is empty。可以调整 replicas 观察分布均匀度的变化。