DoorDash VO: Load Balancer Debug + Consistent Hashing

oavoservice Original Review: DoorDash loves the combination of "first debug a broken implementation, then discuss scalable design".

Part 1: Round Robin Load Balancer Debug (Restated)

You are given pseudocode (or incomplete implementation) for a load balancer. Requirements:

• Round Robin distribution.
• Skip unavailable backends (UNAVAILABLE).
• Dynamically added backends should also work.

Common Bug Profiles

• index resets to 0 every time (always hits the first backend).
• Typo in state string (e.g., AVAILABLE spelled wrong).
• "Skip unavailable" not implemented.
• Adding a backend overwrites the original list.

A Correct Minimal Implementation (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

What Interviewers Look For

• Can you deduce correct behavior from unit tests?
• Do you consider the "all unavailable" edge case?
• Can you write skip logic that doesn't cause infinite loops?

Part 2: Why isn't Round Robin Enough? (State/Sticky Sessions)

If backends are stateful (session, cache, shopping cart), Round Robin causes:

• User requests landing on different instances, losing state.
• Reduced cache hit rate.

This leads to Consistent Hashing.

Part 3: Consistent Hashing Design (Core Points)

Goals

• Minimize key migration when adding/removing nodes.
• Even distribution of keys.

Basic Approach

• Treat hash space as a ring (0..2^32-1).
• Hash each backend to a position.
• Hash request key (e.g., user_id) to a position.
• Find the first backend clockwise on the ring.

Virtual Nodes

To improve uniformity, assign multiple vnodes to each backend:

• hash(backend_id + "#" + i)
• More vnodes = more even distribution.

Reference Implementation (Simplified)

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]

Interview Extensions

• How to handle health checks and draining?
• How to support weighted consistent hashing?
• How to handle region-aware routing?

If you are preparing for backend VOs at DoorDash / Uber / Stripe, oavoservice trains your expression to: Fix correctness first, then discuss scalability and engineering trade-offs.

Need real interview questions? Contact WeChat Coding0201 immediately to get real questions.