Design: Load Balancer¶

Difficulty: Foundation | Time: 45–60 minutes

1. Problem Statement¶

Design a load balancer service that sits in front of a fleet of backend servers and distributes incoming traffic across them. It must pick a healthy backend per request/connection, detect and remove dead backends without dropping in-flight work, and let operators add or remove capacity without a config-and-restart cycle. Assume this is a product you build and run — not a vendor black box — because an interviewer will ask what happens inside it.

2. Clarifying Questions¶

Practice asking these before designing:

3. Functional Requirements¶

• Distribute incoming requests/connections across a pool of healthy backends
• Support multiple algorithms: round robin, weighted round robin, least connections, least latency, consistent hashing
• Detect unhealthy backends and remove them from rotation
• Detect recovered backends and add them back
• Support adding/removing backends dynamically (no restart)
• Drain connections from a backend being taken out of service (deploys, scale-down) without dropping in-flight requests

4. Non-Functional Requirements¶

5. Capacity Estimation¶

Traffic:
  100K requests/second sustained, 10x burst → 1M rps peak
  Avg connection duration: 200ms (HTTP), some WebSocket at minutes

Connections:
  100K rps x 200ms avg duration ≈ 20,000 concurrent connections (Little's Law)
  Peak: 200,000 concurrent connections

LB instance capacity:
  L4 (Maglev/IPVS-style): ~1-2M packets/sec per core, connection-table bound
  L7 (Envoy/nginx-style): ~20-50K rps per core (TLS termination + HTTP parsing)
  100K rps / 30K rps-per-core ≈ 4 cores minimum, provision 3x for headroom = 12 cores

Backend pool:
  Assume 50 backend instances, each handling ~2K rps
  Health check interval: 5s, every backend probed each interval
  50 backends × (1 probe / 5s) = 10 probes/sec per LB — trivial

Config propagation:
  Backend registry: 50-500 entries x 200 bytes ≈ 100KB, fits in memory on every LB
  Push to N LB instances on every membership change: N x 100KB, sub-second on a control plane

6. API Design¶

The load balancer's "API" is mostly the data plane (proxying), plus a small control plane for operators and orchestration to register backends.

# Data plane — this is what clients actually call
ANY  https://api.shop.com/*        → proxied to a backend per algorithm + health

# Control plane (internal, authenticated)
POST /internal/backends
     { "id": "n42", "address": "10.0.4.12:8080", "weight": 100, "zone": "us-east-1a" }
     → 201 Created

DELETE /internal/backends/{id}
     → 202 Accepted (initiates connection drain, not immediate removal)

PUT /internal/backends/{id}/weight
     { "weight": 50 }

GET /internal/backends
     Response: [{ "id": "n42", "state": "healthy|draining|dead", "active_conns": 12, ... }]

PUT /internal/pool/algorithm
     { "algorithm": "least_conn" }

7. Algorithm Choice and Trade-offs¶

The concept page (Load Balancing) covers mechanics; here's how to choose one for this exercise.

Recommended default: least connections for a general HTTP fleet; consistent hashing when cache hit rate or session affinity matters more than perfect load evenness.

8. L4 vs L7 — Which Do You Build?¶

In this exercise: build an L7 gateway tier for the public API (routing, health-aware retries, header injection) sitting behind an L4 tier (cheap, high-PPS, absorbs volumetric load and TLS-agnostic traffic) — this two-tier pattern is what most large-scale deployments actually run, not a single layer doing everything.

Global vs regional:

• Regional LB — one VIP per region. Cheap, low RTT, simple. A full regional outage takes the VIP with it.
• Global (GSLB / anycast) — DNS-based (api.shop.com resolves to the nearest healthy region's IP, TTL-bounded failover of seconds-to-minutes) or anycast (same IP announced from multiple POPs, BGP converges faster but you now debug routing instead of HTTP). Use GSLB for multi-region DR; anycast when failover speed matters more than operational simplicity.

9. Health Checking — How a Dead Node Leaves the Pool¶

This is the load balancer's entire control plane for "who is alive," and it's the part interviewers probe hardest.

Active vs passive:

• Active: LB independently probes each backend (GET /healthz, TCP connect, gRPC health check) on an interval, independent of real traffic. Detects dead nodes even with zero traffic to them. Detection lag = interval × consecutive_failure_threshold (e.g. 5s × 3 = 15s of possible bad routing).
• Passive: LB observes real request outcomes — connection resets, timeouts, 5xx — and ejects a backend after N failures in a window (outlier ejection). Faster than active probing (reacts on the very next real request) but requires traffic to already be flowing to that backend, and a backend that returns fast 200s with garbage bodies looks healthy.

Removing a node without dropping in-flight requests:

1. Health check fails 3 consecutive times → backend marked unhealthy, removed from the selection pool immediately.
2. Requests already in flight to that backend are not migrated — the LB cannot move an established TCP connection. They fail (timeout/reset) and, if idempotent, get retried against a different healthy backend by the L7 tier.
3. New requests never route to the unhealthy backend once it's out of rotation — that's the win. The gap is only the detection window (step 1), during which some fraction of new requests still land there.

Timeline, 3 backends, N0 crashes at t=0:
t=0        N0 process dies. In-flight requests to N0: reset/timeout.
t=0-15s    LB still considers N0 healthy (probes haven't failed 3x yet).
           ~1/3 of NEW requests route to N0 and fail.
t=15s      3rd consecutive probe failure -> N0 marked dead, pulled from pool.
t=15s+     100% of new traffic goes to N1, N2. Capacity -33% until scale-out.

10. Basic Architecture (V1)¶

graph LR
    Client -->|HTTP| LB[Single LB instance]
    LB -->|health check every 5s| N0[Backend N0]
    LB -->|health check every 5s| N1[Backend N1]
    LB -->|health check every 5s| N2[Backend N2]
    LB -->|round robin, healthy only| N0
    LB --> N1
    LB --> N2

One LB process, in-memory backend list, active health checks on a timer, round robin over the healthy subset. Good enough to demonstrate the core loop — but the LB itself is now a single point of failure, and every backend add/remove requires touching that one process's memory.

11. Identify Bottlenecks¶

12. Scaled Architecture (V2)¶

graph TD
    subgraph Clients
        C[Clients]
    end
    subgraph Global["Global tier (GSLB / anycast)"]
        DNS[DNS / Anycast]
    end
    subgraph L4Tier["L4 tier (per region)"]
        L4a[L4 LB 1]
        L4b[L4 LB 2]
    end
    subgraph L7Tier["L7 gateway tier (stateless, autoscaled)"]
        L7a[L7 LB 1]
        L7b[L7 LB 2]
        L7c[L7 LB 3]
    end
    subgraph Discovery["Service discovery / control plane"]
        SD[Registry\nConsul / K8s Endpoints / etcd]
        HCd[Health checker\ncan be centralized or per-LB]
    end
    subgraph Backends["Backend fleet (autoscaled)"]
        N0[N0]
        N1[N1]
        N2[N2]
        N3[N3 draining]
    end

    C --> DNS
    DNS --> L4a
    DNS --> L4b
    L4a --> L7a
    L4a --> L7b
    L4b --> L7c
    L7a -->|least_conn| N0
    L7b --> N1
    L7c --> N2
    SD -->|push backend list + health| L7a
    SD -->|push backend list + health| L7b
    SD -->|push backend list + health| L7c
    N0 -->|register on start| SD
    N3 -.->|deregistering, draining| SD
    HCd --> N0
    HCd --> N1
    HCd --> N2

Key additions over V1: the LB tier itself is now a horizontally scaled, stateless fleet behind an L4 layer (so the LB isn't a SPOF); a shared service discovery / control plane is the single source of truth for backend membership and health, pushed to every LB instance instead of each LB independently guessing.

13. Config Propagation — the LB's Own Distributed Systems Problem¶

Every LB instance needs the same view of "which backends exist and are healthy" — this is a small consensus/propagation problem in its own right, and it's easy to hand-wave past in an interview.

Recommended: push model via a registry with a streaming API (xDS-style) — this is what Envoy, and most production service meshes, actually do. Give every LB instance a local health check as a second signal even when using centralized discovery — don't route to a backend the registry says is "up" if this LB's own probes disagree; treat centralized state as advisory, local observation as authoritative for the final decision.

14. Connection Draining During Deploys¶

Taking a backend out of rotation for a planned reason (deploy, scale-down) should never look like a crash to the client.

Drain sequence for backend N3:
1. Orchestrator sends SIGTERM to N3 (or control plane marks it "draining")
2. N3 (or the LB, depending on design) immediately fails readiness
   -> LB stops routing NEW requests/connections to N3 within one health-check tick
3. N3's IN-FLIGHT requests continue to completion (grace period, e.g. 30-60s)
4. LB removes N3 from its active set entirely once grace period elapses
   or in-flight count hits zero, whichever comes first
5. N3 process exits

The two failure modes to avoid: (a) killing the process before step 2-3 complete, which resets in-flight connections exactly like an unplanned crash; (b) never timing out the drain, which means one stuck long-lived connection (WebSocket that never closes) blocks a deploy indefinitely — always cap the grace period and force-close after it.

Try: Run, then Kill N0 — watch new requests skip it while in-flight work to it just errors. Switch to consistent hash and add a node — only a slice of keys should move, unlike round robin which reshuffles everyone. Full mechanics of each algorithm are in the Load Balancing concept page.

15. Failure Modes¶

16. Consistency Considerations¶

• Backend membership is AP, not CP. Every LB instance briefly disagreeing about whether N5 exists yet is fine — routing a request to a backend that's 2 seconds stale-dead is a transient error, not data corruption.
• Health state is inherently eventually consistent across a distributed LB tier — there is no practical way to make every instance agree instantaneously without adding latency to every request. Design for convergence within a bounded window, not for immediate agreement.
• Connection-count state for least-connections is naturally per-instance unless you centralize it (expensive, adds a hop to every routing decision). Accept per-LB-instance approximate counts; it self-corrects because each instance is still internally consistent.

17. Observability¶

Key metrics:
- healthy_backend_count / total_backend_count (per LB instance and aggregate)
- lb_5xx_rate vs backend_5xx_rate (distinguish LB-originated from backend-originated errors)
- request_latency_p50/p95/p99 added by the LB hop
- config_propagation_lag (time from registry change to all LB instances converging)
- active_connections per backend (skew across the pool = algorithm working or not)
- drain_duration and in_flight_at_forced_close (deploy health)

Alerts:
- healthy_backend_count == 0 (page immediately)
- healthy_backend_count < N+1 headroom threshold
- lb_5xx_rate > 1%
- config_propagation_lag p99 > 10s
- any single backend receiving > 2x its expected share (algorithm or weight bug)

18. Cost Analysis¶

L7 gateway tier (12 vCPU total, autoscaled 3-10 instances): ~$600/month
L4 tier (managed NLB or self-run IPVS, 2 instances):         ~$300/month
Service discovery cluster (Consul/etcd, 3 nodes):            ~$300/month
Health check traffic (negligible bandwidth):                 ~$10/month
GSLB / DNS (Route 53 style, health-checked routing):         ~$50/month
Total:                                                        ~$1,260/month

Cost per million requests:
  Monthly request volume: 100K rps x 2.6M sec/month = 260 billion requests/month
  $1,260 / 260,000,000,000 requests ≈ $0.0000000048 per request (4.8 x 10^-9)
  ≈ $0.0048 per million requests
  Dominant cost is the L7 CPU tier (TLS termination) — using a managed
  cloud LB (ALB/NLB) trades this line item for a per-request/per-LCU fee,
  often cheaper below ~50K sustained rps, more expensive above it.

19. Alternative Architectures¶

20. Staff Engineer Extensions¶

21. Interview Follow-ups¶

1. "How would you avoid the LB itself becoming a bottleneck?" — Scale the LB tier horizontally behind a cheaper L4/anycast layer; keep it stateless so any instance can serve any request; push connection/health state to a shared control plane rather than per-instance memory.
2. "What's the difference between service discovery and health checking?" — Discovery answers "what backends exist and where," health checking answers "which of them can currently serve traffic." A backend can be discovered but unhealthy (starting up) or healthy but undiscovered (misconfigured registration) — they're separate signals that must both be true before routing.
3. "How do you avoid retry storms when a backend gets slow, not dead?" — Outlier ejection based on latency/error-rate thresholds (not just binary health), circuit breaking at the caller, and bounded retry budgets so failures don't amplify onto the remaining healthy backends.
4. "Why is L4 'dangerous' for retries?" — At L4 the LB doesn't know if bytes were already partially written to the dead backend; retrying blindly at the connection level can replay a non-idempotent operation. L7 can inspect the HTTP method/idempotency key before deciding to retry.

Self-Assessment¶

• [ ] Can I explain the exact sequence of events, with timing, when a backend crashes?
• [ ] Can I justify least connections vs consistent hashing for a specific workload?
• [ ] Can I describe how a second LB instance learns about a new backend?
• [ ] Can I design a connection-drain sequence that survives a stuck WebSocket?
• [ ] Can I explain why the LB tier itself needs the same HA thinking as the backends it protects?