一致性哈希算法详解（Python实现分布式系统中的高效负载均衡）

什么是传统哈希的问题？

假设我们有3台缓存服务器（Node A、B、C），使用普通哈希算法：对 key 做哈希后对服务器数量取模，即 hash(key) % 3。这样可以将 key 分配到某一台服务器上。

但当新增一台服务器（变为4台）时，几乎所有 key 的映射结果都会改变，导致缓存失效，需要重新加载数据——这在高并发系统中是灾难性的。

一致性哈希如何解决这个问题？

一致性哈希算法的核心思想是将哈希值空间组织成一个虚拟的圆环（称为“哈希环”），通常范围是 0 到 2³² - 1。所有服务器节点和数据 key 都通过哈希函数映射到这个环上的某个位置。

当需要查找某个 key 应该落在哪个节点时，我们顺时针沿着环找到第一个大于等于该 key 哈希值的节点，即为该 key 所属的服务器。

这样，当增加或删除节点时，只有相邻的一小部分 key 需要重新映射，大大减少了数据迁移量，提升了系统的稳定性——这是实现高效负载均衡的关键。

Python 实现一致性哈希

下面我们将用 Python 编写一个简单的一致性哈希类。为了提高均匀性，我们还会引入“虚拟节点”（Virtual Nodes）技术——每个物理节点对应多个虚拟节点，避免数据倾斜。

import hashlibimport bisectclass ConsistentHashing:    """    一致性哈希算法的Python实现    支持添加/移除节点、获取key对应的节点    """    def __init__(self, nodes=None, replicas=3):        """        :param nodes: 初始节点列表        :param replicas: 每个节点的虚拟副本数（虚拟节点数）        """        self.replicas = replicas        self.ring = dict()  # 哈希环：{hash_value: node}        self.sorted_keys = []  # 排序后的哈希值列表，用于二分查找        if nodes:            for node in nodes:                self.add_node(node)    def _hash(self, key):        """使用MD5生成32位哈希值，并转换为整数"""        m = hashlib.md5()        m.update(key.encode('utf-8'))        return int(m.hexdigest(), 16)    def add_node(self, node):        """添加一个物理节点及其虚拟节点到哈希环"""        for i in range(self.replicas):            virtual_node_key = f"{node}#{i}"            hash_val = self._hash(virtual_node_key)            self.ring[hash_val] = node            self.sorted_keys.append(hash_val)        self.sorted_keys.sort()    def remove_node(self, node):        """从哈希环中移除一个物理节点及其所有虚拟节点"""        for i in range(self.replicas):            virtual_node_key = f"{node}#{i}"            hash_val = self._hash(virtual_node_key)            if hash_val in self.ring:                del self.ring[hash_val]                self.sorted_keys.remove(hash_val)    def get_node(self, key):        """根据key获取对应的节点"""        if not self.ring:            return None        hash_val = self._hash(key)        # 使用二分查找找到第一个 >= hash_val 的位置        idx = bisect.bisect_left(self.sorted_keys, hash_val)        # 如果超出范围，回到环的起点（顺时针）        if idx == len(self.sorted_keys):            idx = 0        return self.ring[self.sorted_keys[idx]]

使用示例

现在我们来测试一下这个一致性哈希类：

# 初始化一致性哈希环nodes = ['cache-server-1', 'cache-server-2', 'cache-server-3']ch = ConsistentHashing(nodes=nodes, replicas=10)# 测试 key 分配keys = ['user:1001', 'product:205', 'order:789']for key in keys:    node = ch.get_node(key)    print(f"Key '{key}' => {node}")# 添加新节点ch.add_node('cache-server-4')print("\n添加 cache-server-4 后：")for key in keys:    node = ch.get_node(key)    print(f"Key '{key}' => {node}")

运行上述代码，你会发现大多数 key 在新增节点后仍然映射到原来的服务器，只有少数 key 被重新分配——这正是一致性哈希算法的优势所在。

总结

通过本文，我们深入理解了一致性哈希算法的工作原理，并用Python实现了支持虚拟节点的完整版本。这项技术广泛应用于 Redis 集群、Memcached、分布式数据库等系统中，是构建高可用、可扩展的分布式缓存和实现智能负载均衡的基石。

对于初学者来说，掌握一致性哈希不仅能提升对分布式系统的理解，还能在面试和实际项目中展现扎实的工程能力。建议读者动手运行代码，尝试修改节点数量和虚拟副本数，观察 key 分布的变化，加深理解。