用 Python bisect 实现带虚拟节点的一致性哈希环

问题场景

分片缓存常用 hash(key) % N 决定 key 落在哪个节点。这个做法在 N 不变时很省事，但只要节点数变化就会出问题：hash(key) % 4 和 hash(key) % 5 的结果几乎对不上，绝大多数 key 的归属都会改变。对缓存来说，归属改变意味着新节点上大概率没有这条数据，请求会穿透到后端数据库；如果扩容时一次性切换，很容易把回源压力放大成雪崩。

我们希望的是：增减一个节点时，只让“本该属于新节点”的那部分 key 迁移，其余 key 保持不动。一致性哈希环就是为此设计的。

一致性哈希与虚拟节点的关系

把哈希值空间首尾相接看成一个环，每个缓存节点用哈希映射到环上的若干位置，key 也映射到环上，然后顺时针找到第一个节点，就是它的归属。增加一个节点，只有落在“新节点与其前驱之间”那段弧上的 key 会改归属；删除一个节点，只有该节点负责的那段弧会交给后继节点。

只用一个哈希点表示一个物理节点会导致分布很不均匀，所以实践中会给每个物理节点生成多个虚拟节点（形如 node#0、node#1……），让每个物理节点在环上占据多段小弧。虚拟节点越多，负载越均衡，代价是环上的点数和内存占用随之上升。

环上的点需要保持有序并支持快速查找，Python 标准库的 bisect 正好提供了有序插入与二分定位，不用自己写排序。

最小可运行实现

import bisect
import collections
import hashlib


def h(key: str) -> int:
    """稳定哈希：保证不同进程、不同机器上结果一致。"""
    return int.from_bytes(hashlib.md5(key.encode("utf-8")).digest()[:8], "big")


class ConsistentHashRing:
    def __init__(self, nodes=(), vnodes=150):
        self.vnodes = vnodes
        self._hashes = []   # 升序排列的虚拟节点哈希值
        self._ring = []     # 与 _hashes 一一对应的 (hash, node)
        self._nodes = set()
        for n in nodes:
            self.add_node(n)

    def _points(self, node):
        """同一节点每次生成的虚拟节点哈希是确定的，删除时可由此还原。"""
        for i in range(self.vnodes):
            yield h("{}#{}".format(node, i))

    def add_node(self, node):
        if node in self._nodes:
            return
        for hv in self._points(node):
            idx = bisect.bisect_left(self._hashes, hv)
            self._hashes.insert(idx, hv)
            self._ring.insert(idx, (hv, node))
        self._nodes.add(node)

    def remove_node(self, node):
        if node not in self._nodes:
            return
        for hv in self._points(node):
            idx = bisect.bisect_left(self._hashes, hv)
            if idx < len(self._hashes) and self._hashes[idx] == hv:
                self._hashes.pop(idx)
                self._ring.pop(idx)
        self._nodes.discard(node)

    def get_node(self, key):
        if not self._ring:
            raise ValueError("hash ring is empty")
        idx = bisect.bisect_left(self._hashes, h(key))
        if idx == len(self._ring):   # 越过环尾则回到环首
            idx = 0
        return self._ring[idx][1]

节点增删都是对有序列表的插入或删除，单次操作代价与该节点的虚拟节点数相关；查找是一次二分，复杂度为 O(log(N·V))，N 为物理节点数，V 为每节点虚拟节点数。

验证迁移率

下面把一致性哈希和取模哈希放在同一批 key 上对比，统计 4 节点扩到 5 节点后有多少 key 换了归属：

def migration_rate(old, new):
    moved = sum(1 for k in old if old[k] != new[k])
    return moved / len(old)


if __name__ == "__main__":
    keys = ["user:{}".format(i) for i in range(20000)]

    ring = ConsistentHashRing(
        ["cache-0", "cache-1", "cache-2", "cache-3"], vnodes=150
    )
    before = {k: ring.get_node(k) for k in keys}

    ring.add_node("cache-4")
    after = {k: ring.get_node(k) for k in keys}

    mod_before = {k: h(k) % 4 for k in keys}
    mod_after = {k: h(k) % 5 for k in keys}

    print("一致性哈希 4->5 迁移率: {:.2%}".format(migration_rate(before, after)))
    print("取模哈希   4->5 迁移率: {:.2%}".format(migration_rate(mod_before, mod_after)))

    dist = collections.Counter(after.values())
    print("扩容后各节点键数量:", dict(sorted(dist.items())))

运行方法：把两段代码保存为 ring.py，执行 python ring.py。脚本只依赖标准库，不需要额外安装包。

结果解读：一致性哈希的迁移率应当接近新增节点占总节点数的比例，4 扩 5 时理论值约为 1/5，实际数值会因哈希分布略有浮动；取模哈希的迁移率则远高于这个量级，因为节点数一变，几乎所有 key 的取模结果都会被重排。dist 的输出可以用来观察虚拟节点数量对均衡性的影响：把 vnodes 调小（例如 1 或 5），各节点键数量往往相差明显；调到 150 以上通常会平缓很多。

边界与限制

• 不要用 Python 内置的 hash() 对字符串求哈希值，它带有进程级随机盐，不同进程结果不一致，环的成员会各自算出不同的归属。示例使用 MD5 前 8 字节，只取确定性和分布性，不用于安全场景。
• 哈希碰撞概率极低但并非为零。示例中 remove_node 依赖哈希值定位虚拟节点，若发生碰撞可能导致误删，工程实现可改为按 (hash, node) 排序或存储节点名做二次校验。
• 虚拟节点数不是越多越好。它直接决定环上点数与内存占用，也会放大节点上下线的计算量，需要按节点规模做权衡。
• 节点规格不同时，可以给大规格节点分配更多虚拟节点来实现加权，而不是所有节点用同一个 vnodes。
• 环只解决“key 该找哪个节点”，不解决数据本身的问题。新节点加入后是冷的，仍需缓存预热、限流和回源保护，避免切换瞬间把压力打到数据库。
• 节点故障时，它负责的那段弧会全部交给后继节点，可能出现单点热点，通常配合副本或多次哈希来缓解。
• 环视图必须在客户端与服务端保持一致，实际系统中一般由配置中心统一下发并带版本号，环变更需要灰度生效。
• 示例为单线程使用；多线程增删节点时需自行加锁，或采用“构建新环再原子替换”的写法。