一致性哈希：让数据分布更均匀的神器
【720】一致性哈希：让数据分布更均匀的神器
你开了个快递站，最初只有3个员工。
分配包裹很简单：按编号除以3取余，0号员工、1号员工、2号员工。
后来员工离职了，只剩2个员工。你得重新分配所有包裹，工作量巨大。
再后来招聘新员工，你又得重新分配一遍。
这就像传统哈希的问题：扩容和缩容时，所有数据都要重新分配。
一致性哈希就是来解决这个痛点的：节点变动时，只需要移动少量数据。
一、一致性哈希的原理
环形空间
想象一个圆环，上面有2^32个位置（或者更多）：
0 /\ 2^32/ \0 / \ / 环 \ /________\ 65536 4294967295节点映射
把服务器节点映射到环上：
节点A：Hash("服务器A") = 1000000 节点B：Hash("服务器B") = 4000000 节点C：Hash("服务器C") = 7000000数据映射
把数据Key也映射到环上：
数据X：Hash("数据X") = 3500000 数据Y：Hash("数据Y") = 6000000 数据Z：Hash("数据Z") = 9000000顺时针查找
数据X顺时针走，遇到的第一个节点是节点B，所以数据X存在节点B上。
二、一致性哈希的优势
场景1：节点扩容
新增节点D，Hash(“服务器D”) = 5500000
原来：
- 数据Y（6000000）在节点C
- 数据Z（9000000）在节点C
现在：
- 只有落在4000000~5500000之间的数据会移动到节点D
- 其他数据不受影响！
场景2：节点缩容
节点B突然宕机，只有它上面的数据需要重新分配到节点C。
对比传统哈希：
- 传统：N个数据全部重新分配
- 一致性哈希：只有部分数据重新分配
三、虚拟节点：解决数据倾斜
问题来了：如果三个节点分布不均匀怎么办？
节点A：1000000 节点B：4000000 节点C：4000001 ← 几乎在一起！大部分数据都会落在节点C上，数据严重倾斜。
解决方案：虚拟节点
每个真实节点映射多个虚拟节点：
节点A-1：Hash("服务器A#1") = 1000000 节点A-2：Hash("服务器A#2") = 2000000 节点A-3：Hash("服务器A#3") = 3000000 节点B-1：Hash("服务器B#1") = 4000000 节点B-2：Hash("服务器B#2") = 5000000 节点B-3：Hash("服务器B#3") = 6000000 ...这样节点在环上分布更均匀，数据也会更均衡。
四、实战应用
Redis集群
Redis Cluster使用一致性哈希（16384个槽位）：
# 计算key应该落在哪个槽slot=crc16(key)%16384# 槽映射到节点node=slots[slot]数据库分库分表
defget_shard(key):hash_key=hash(key)%(真实节点数*虚拟节点数)foriinrange(虚拟节点数):node_idx=(hash_key+i)%(真实节点数*虚拟节点数)if是真实节点(node_idx):return节点[node_idx]CDN内容分发
用户请求图片时，通过一致性哈希选择最近的缓存节点。
五、代码实现
importhashlibclassConsistentHash:def__init__(self,nodes=None,virtual_nodes=150):self.virtual_nodes=virtual_nodes self.ring={}self.sorted_keys=[]ifnodes:fornodeinnodes:self.add_node(node)def_get_hash(self,key):"""计算哈希值"""returnint(hashlib.md5(str(key).encode()).hexdigest(),16)defadd_node(self,node):"""添加节点"""foriinrange(self.virtual_nodes):key=self._get_hash(f"{node}#vn{i}")self.ring[key]=node self.sorted_keys=sorted(self.ring.keys())defremove_node(self,node):"""移除节点"""foriinrange(self.virtual_nodes):key=self._get_hash(f"{node}#vn{i}")delself.ring[key]self.sorted_keys=sorted(self.ring.keys())defget_node(self,key):"""获取key对应的节点"""ifnotself.ring:returnNonehash_key=self._get_hash(key)forkinself.sorted_keys:ifk>=hash_key:returnself.ring[k]# 环的起点returnself.ring[self.sorted_keys[0]]六、一句话总结
一致性哈希让系统扩缩容时，只需要移动少量数据，而不是全部重新分配。
配合虚拟节点，还能解决数据倾斜问题，是分布式系统的必备技能。