Coding 面试：如何用虚拟节点实现一致性哈希环？

题干与适用场景

实现把字符串 key 路由到物理节点的哈希环。API 为 addNode(nodeId, weight)、removeNode(nodeId) 和 getNode(key)。节点生成 weight × V 个虚拟 token，使用确定性的 64 位哈希；查找 key 顺时针遇到的第一个存活 token。空环返回空节点。假设更新由调用方串行化，题目重点是可执行数据结构而非完整成员服务。

面试官考察点

PracHub 将该题记录为 DoorDash Software Engineer 技术面试，要求实现三个 API、虚拟节点、碰撞处理和复杂度；Glassdoor 的近期公开面试记录也提到修复 round-robin 负载均衡器并用一致性哈希实现。MIT 原论文把 balance 与 monotonicity 作为核心性质：负载应大致均衡，增加桶时不应移动本可保留的 key。

回答前需要澄清的问题

1. node ID 是否稳定且唯一？移除必须能精确找到该物理节点的 token。
2. weight 是否为正整数？本文假设是；小数容量需另做 token 预算归一化。
3. 更新是否与查找并发？若并发，应发布不可变快照；示例假设更新串行。
4. 是否要求副本？基础 API 只返回一个 owner，多副本是后续约束。
5. 哈希函数是否给定？练习中假设确定且近似均匀，生产仍需评估碰撞和对抗输入。

30 秒回答框架

“我保存按 (tokenHash, virtualTokenId, nodeId) 排序的记录。新增节点插入 weight × V 个确定 token，删除节点只删除它拥有的 token。查找时二分找到第一个不小于 key hash 的 token，越过末尾就回到零。核心不变量是每个 token 只属于一个存活节点、每个 key 归属顺时针第一个 token。查找 O(log M)，更新取决于容器；我会测试碰撞、环回、重复更新、删除、空环和重映射。”

分步骤深入解答

1. 表示和不变量

用排序数组保存 (hash, tokenId, nodeId)，再用 nodeId → tokens 的反向索引精确删除。维护四个不变量：token 按 (hash, tokenId) 排序；每个 token 指向一个注册节点；key 归属顺时针第一个 token；token 由稳定 node ID、索引和 token 数生成。第二排序键让哈希碰撞仍确定。

2. 确定生成虚拟节点

对节点 n 和索引 i 哈希 n + "#" + i，生成 weight × V 个索引。weight 越大，期望拥有的区间越多。V 和权重策略应随环快照保存；修改它们会产生预期之外的重映射。

3. 实现 API

from bisect import bisect_left

class ConsistentHashRing:
    def __init__(self, virtuals_per_weight, hash64):
        self.v = virtuals_per_weight
        self.hash64 = hash64
        self.tokens = []  # (hash, token_id, node_id)
        self.by_node = {}

    def add_node(self, node_id, weight=1):
        if weight <= 0 or node_id in self.by_node:
            raise ValueError("invalid or duplicate node")
        owned = []
        for i in range(weight * self.v):
            token_id = f"{node_id}#{i}"
            owned.append((self.hash64(token_id), token_id, node_id))
        self.by_node[node_id] = owned
        self.tokens.extend(owned)
        self.tokens.sort()

    def remove_node(self, node_id):
        owned = self.by_node.pop(node_id, None)
        if owned is None:
            return False
        owned_ids = {token_id for _, token_id, _ in owned}
        self.tokens = [t for t in self.tokens if t[1] not in owned_ids]
        return True

    def get_node(self, key):
        if not self.tokens:
            return None
        h = self.hash64(key)
        i = bisect_left(self.tokens, (h, "", ""))
        return self.tokens[i if i < len(self.tokens) else 0][2]

重复节点视为调用错误，删除不存在节点返回 false。生产实现可先构建新快照再原子发布，避免读者看到半更新状态。

4. 复杂度和重映射

令 M = V × sum(weight)。查找 O(log M)，每次额外空间 O(1)，数组实现更新为 O(M + K log M)，其中 K 是变更节点 token 数；平衡树可降为 O(K log M)，总空间 O(M)。节点加入只影响其虚拟 token 前方的区间，移除后这些区间转移到下一个顺时针 owner；这正是相比 hash % N 的优势。虚拟节点不能解决单一热点 key。

高质量示范回答

“我用排序的 (hash, tokenId, nodeId) 记录和反向索引实现。新增节点生成稳定的 weight × V 个虚拟 token，删除时精确删除它们，查找用 lower-bound 并处理环回。碰撞以 tokenId 决定顺序。排序数组查找 O(log M)，更新 O(M + K log M)；平衡树可让更新 O(K log M)。我会测试空环、单节点、环回、重复 ID、碰撞、权重分布、删除和节点变更后的 key 重映射比例。”

常见错误

• 使用 hash(key) % N → 节点数变化会大规模重映射 → 查找顺时针 token。
• 假设不会碰撞 → 相同 hash 的 owner 不稳定 → 用确定 tokenId 打破平局。
• 每次重启随机生成 token → 所有 key 意外迁移 → 从稳定 node ID 和索引生成。
• 只按名称前缀删除 → 相似 ID 可能误删 → 维护反向索引。
• 声称虚拟节点消除热点 → 单一热门 key 仍只有一个 owner → 把副本或热点处理作为独立需求。
• 忽略空环和重复 → 边界不变量失效 → 先定义返回值和错误行为。

追问及应对

如何返回三个副本？

从 owner 顺时针扫描，收集不同物理 node ID；跳过同一节点的其他虚拟 token。存活节点不足时返回可用集合并明确短缺。

如何测试分布？

生成固定 key 集合，统计各节点占比及最大最小比，加入和移除节点后重复测试；固定哈希种子保证回归可复现。

节点容量变化怎么办？

先删旧 token，再按新 weight 增加 token，并一次发布快照；监控变更期间负载。

什么时候 modulo 更简单？

成员固定或可接受全量重平衡时，modulo 更短；成员经常变化且重映射成本重要时才值得一致性哈希的复杂度。