题干与适用场景
实现把字符串 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。
回答前需要澄清的问题
- node ID 是否稳定且唯一？移除必须能精确找到该物理节点的 token。
- weight 是否为正整数？本文假设是；小数容量需另做 token 预算归一化。
- 更新是否与查找并发？若并发，应发布不可变快照；示例假设更新串行。
- 是否要求副本？基础 API 只返回一个 owner，多副本是后续约束。
- 哈希函数是否给定？练习中假设确定且近似均匀，生产仍需评估碰撞和对抗输入。
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 更短；成员经常变化且重映射成本重要时才值得一致性哈希的复杂度。