一致性哈希：让数据分布更均匀的神器-尧图网络科技

【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]]