# 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，获得真题。
联系方式
Email: [email protected] Telegram: @OAVOProxy