一致性哈希：让数据分布更均匀的神器

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