DoorDash VO：負載均衡 Debug + 一致性雜湊

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，獲得真題。