DoorDash VO：负载均衡 Debug + 一致性哈希（Consistent Hashing）系统设计

# DoorDash VO：负载均衡 Debug + 一致性哈希（Consistent Hashing）系统设计

oavoservice 原创复盘：DoorDash 很爱用“先 debug 一个坏实现，再让你讲可扩展设计”的组合题。

Part 1：Round Robin 负载均衡器 Debug（改写版）

你拿到一个负载均衡器的伪代码（或不完整实现），单测要求：

轮询（Round Robin）分发请求
跳过不可用后端（UNAVAILABLE）
动态新增后端也要生效

常见 bug 画像

index 每次都从 0 开始（永远打到第一个后端）
状态字符串拼写错误（AVAILABLE 写错）
未实现“跳过不可用”
新增后端时覆盖了原列表

一个正确的最小实现（Python）

class Backend:
    def __init__(self, name, state='AVAILABLE'):
        self.name = name
        self.state = state


class TrafficRouter:
    def __init__(self, backends):
        self.backends = list(backends)
        self._idx = 0

    def add_backend(self, backend):
        self.backends.append(backend)

    def get_backend(self):
        n = len(self.backends)
        if n == 0:
            return None

        tried = 0
        while tried < n:
            b = self.backends[self._idx]
            self._idx = (self._idx + 1) % n
            tried += 1
            if b.state == 'AVAILABLE':
                return b
        return None

面试官听什么

你是否能从单测推导正确行为
你是否考虑“全不可用”的边界
你是否写出不会死循环的跳过逻辑

Part 2：为什么 Round Robin 不够？（状态/粘性会话）

如果后端是有状态的（session、cache、shopping cart），Round Robin 会导致：

同一用户请求落到不同实例，状态丢失
cache 命中率降低

于是引出 一致性哈希。

Part 3：一致性哈希设计（核心要点）

目标

节点增删时，尽量少迁移 key
key 分布尽量均匀

基本做法

把 hash 空间看作一个环（0..2^32-1）
对每个 backend 做 hash 得到位置
对请求 key（如 user_id）hash 得到位置
在环上顺时针找到第一个 backend

虚拟节点（Virtual Nodes）

为了更均匀，给每个 backend 放多个 vnode：

hash(backend_id + "#" + i)
vnode 越多，分布越均匀

参考实现（简化）

import bisect
import hashlib


def h32(s: str) -> int:
    return int(hashlib.md5(s.encode('utf-8')).hexdigest()[:8], 16)


class ConsistentHashRing:
    def __init__(self, replicas=100):
        self.replicas = replicas
        self.ring = []          # sorted hashes
        self.nodes = []         # parallel array of node ids
        self.live = set()

    def add_node(self, node_id: str):
        self.live.add(node_id)
        for i in range(self.replicas):
            key = f"{node_id}#{i}"
            hv = h32(key)
            idx = bisect.bisect_left(self.ring, hv)
            self.ring.insert(idx, hv)
            self.nodes.insert(idx, node_id)

    def remove_node(self, node_id: str):
        if node_id not in self.live:
            return
        self.live.remove(node_id)
        i = 0
        while i < len(self.nodes):
            if self.nodes[i] == node_id:
                self.nodes.pop(i)
                self.ring.pop(i)
            else:
                i += 1

    def route(self, request_key: str) -> str | None:
        if not self.ring:
            return None
        hv = h32(request_key)
        idx = bisect.bisect_left(self.ring, hv)
        if idx == len(self.ring):
            idx = 0
        return self.nodes[idx]

面试扩展点

如何做健康检查（health check）与摘流（drain）？
如何支持权重（weighted consistent hashing）？
如何做跨机房路由（region-aware）？

如果你要准备 DoorDash / Uber / Stripe 这类后端 VO，oavoservice 会用这类“debug + 系统设计升级”的题把你的表达训练成：先修正确性，再谈可扩展与工程权衡。

需要面试真题？立刻联系微信 Coding0201，获得真题。