DoorDash Round Robin 调试：持久游标与 Consistent Hashing 追问

题目重点：DoorDash Onsite Debugging 面经深挖：轮询可用 worker、游标与边界错误、测试不变量，并解释一致性哈希替代策略。

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

题目没有贴完整 Broken Round Robin starter，因此无法逐行定位真实 bug。示例代码是明确标注的训练契约：worker ID 固定且唯一，可用状态可变，assign 从持久游标向后循环，找不到可用 worker 返回 None。
每次成功分配后，游标指向被选 worker 的下一位置；所有 worker 不可用时保持游标不变。此行为并非题目明确输出规范。
示例是单线程。若生产环境多线程分配，读/更新游标及可用状态应在同一临界区或由原子状态机统一处理。

解题路线

一致性哈希练习附StableHashRing：SHA-256稳定摘要与固定虚拟节点配置，按顺时针第一个位置定位。同requestId在相同拓扑、编码和hash配置下跨进程映射一致；成员变化后不保证永远同server。Python内置hash不作为跨进程稳定协议。
保留碰撞虚拟节点，用serverId/replica稳定打破平局，不能遇碰撞就丢整台服务器。构环O(V log V)、空间O(V)，每次查O(log V)加请求键hash成本；虚拟节点数改善分布却不替代负载测量。
先用最小可复现用例识别游标是否在多次 assign 之间持久：3 个 worker 连续分配应轮转，而不是每次都从 0 开始。
每次最多检查 n 个位置，防止全不可用时死循环。检查 size=0、size=1、当前 worker 不可用、最后位置回卷、可用状态在调用间变化。
修复数据结构后再看测试断言是否本身写错、字段名 available 是否一致；题目只报告错误类别，具体行号不能反推。
Consistent Hashing 追问与 Round Robin 的目标不同：把订单 key 经稳定 hash 映到环上顺时针第一个节点，节点增删只迁移局部 key。用排序环/TreeMap、二分找 successor，虚拟节点平衡负载；故障剔除与热节点容量仍需独立处理。

手动走一遍

workers=[A,B,C]，B 暂不可用：连续 assign 应返回 A、C、A；B 恢复后，下一次从上次游标继续，返回 B。空列表或全不可用返回 None，不陷入无限循环。Consistent Hashing 则对同一 order key 优先稳定映到相同 backend，不能把每次请求 Round Robin 的结果当作其替代。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

"""Training model for a persistent-cursor Round Robin debugging prompt."""


class RoundRobinWorkers:
    def __init__(self, workers: list[str]) -> None:
        if len(workers) != len(set(workers)):
            raise ValueError("worker IDs must be unique")
        self.workers = workers[:]
        self.available = set(workers)
        self.next_index = 0

    def set_available(self, worker: str, is_available: bool) -> None:
        if worker not in self.workers:
            raise KeyError(worker)
        if is_available:
            self.available.add(worker)
        else:
            self.available.discard(worker)

    def assign(self) -> str | None:
        size = len(self.workers)
        for offset in range(size):
            index = (self.next_index + offset) % size
            worker = self.workers[index]
            if worker in self.available:
                self.next_index = (index + 1) % size
                return worker
        return None


class StableHashRing:
    """Fixed topology deterministic routing; membership changes may remap keys."""
    def __init__(self,servers,replicas=32):
        import hashlib
        if replicas<1 or len(servers)!=len(set(servers)):raise ValueError('configuration')
        self.digest=lambda key:int.from_bytes(hashlib.sha256(key.encode('utf-8')).digest(),'big')
        # Keep colliding virtual nodes: stable server/replica tie breakers.
        self.ring=sorted((self.digest(f'{len(server)}:{server}:{replica}'),server,replica)
                         for server in servers for replica in range(replicas))
        self.positions=[entry[0] for entry in self.ring]
    def assign(self,request_id):
        from bisect import bisect_left
        if not self.ring:return None
        return self.ring[bisect_left(self.positions,self.digest(request_id))%len(self.ring)][1]

复杂度

轮询一次最坏检查 n 个 worker，O(n) 时间、O(n) 可用集合空间；若所有 worker 都可用，每次 O(1)。一致性哈希环若有 V 个虚拟节点，建环 O(V log V)、路由 O(log V)，增删节点迁移的 key 比例取决于环区间与权重。

易错点与追问

容易失分的边界

AVAILABLE拼写错会把健康节点错误过滤；一台available一台unavailable应每次都返回健康者，而不是人为交替None。
把 index 声明为 assign 内的局部变量会导致每次调用从同一位置开始，破坏轮转；但共享游标在并发下还需同步。
while 一直找 available 却没有至多 n 次的停止条件，在全不可用时永不返回。
修改 bug 前应验证测试本身对跳过不可用 worker 与回卷的期望值；面经明确提到 test case 也有错误。
随机选骑手 q14 与 Round Robin 是两种不同调度语义，不能把其 swap-delete 索引 bug 套到本题的游标逻辑。

继续深挖

若 worker 集合动态增加/删除，要定义游标在拓扑变化后的指向；可按稳定 ID 找下一节点，或用版本化列表切换。
若 worker 容量不同，Round Robin 可改 weighted round robin；一致性哈希可调虚拟节点数/权重，但都要配健康检查与连接失败回退。