rgoussu.dev
rgoussu@goussu: ~/library/system-design/exercises
❯ ~/library/system-design/exercises cat load-balancer-and-rate-limiter-subject.md

Build a load balancer & rate limiter — subject

# The full work statement for the API-edge build — the L7 load balancer spec, the rate-limiter algorithms and response contract, their composition, and the load-test protocol with a measured p99.

Subjectsaved 2026-08-08source #exercise#load-balancing#rate-limiting#networking#http#resilience#subject

Brief

Your API runs on several identical backend instances, and clients — some polite, some not — hit them directly. You are building the edge tier that goes in front: an L7 load balancer that spreads traffic across healthy backends only, and a rate limiter that keeps any one client from starving the rest. Built as two separate projects, then composed into a single edge process whose own overhead you must measure and report.

Instructions

1. The load balancer (L7)

An HTTP reverse proxy in front of a configurable set of backends.

  • Backend registry — backends come from configuration (file or flags): a list of url + optional weight (default 1). No hardcoded addresses. For testing, any trivial HTTP server that returns its own identity (port or name) in the body works as a backend.
  • Proxying — for each inbound request, pick a backend, forward the request (method, path, query, headers, body), and relay the response — status, headers, body — unmodified except for hop-by-hop headers (Connection, Keep-Alive, Transfer-Encoding, TE, Upgrade, Proxy-*), which are stripped, and standard forwarding headers (X-Forwarded-For, X-Forwarded-Proto, X-Forwarded-Host), which are appended. A backend connection failure or timeout yields 502 Bad Gateway; the balancer process itself never crashes on a dead backend.
  • Health-check loop — a background loop probes every backend's health endpoint (path configurable, default GET /health; 2xx = pass) every interval seconds (configurable, default 10). After unhealthy-threshold consecutive failures (default 2) a backend leaves the rotation; after healthy-threshold consecutive passes (default 2) it re-enters. Thresholds prevent flapping on one lost probe. State transitions are logged. If every backend is out, answer 503.
  • Strategies — round-robin first: rotate through healthy backends in order, correct under concurrent requests (the shared cursor is synchronized). Then weighted round-robin: a backend with weight 3 receives 3× the requests of a weight-1 backend over any window, interleaved (smooth), not in runs of 3.
  • Connection reuse — maintain keep-alive connections to backends (a pool or your HTTP library's pooling, deliberately configured: max idle per backend, idle timeout). Demonstrate the win: measure request latency with pooling on vs. a new TCP connection per request, and record both numbers.

2. The rate limiter

A limiting layer with pluggable algorithms behind one interface — allow(client, now) → (allowed, retry_after_hint) — so algorithms swap without touching the transport.

  • Keying — the client identity is the X-Api-Key header when present, else the client IP. Every counter/bucket is per-key; one client exhausting its quota must not affect another's.
  • Token bucket — per key: capacity tokens, refilled at rate tokens/second (lazily computed from elapsed time — no timer per bucket). A request consumes one token; empty bucket → rejected. Allows bursts up to capacity while capping the sustained rate at rate.
  • Fixed window — per key: a counter per clock-aligned window of window seconds, rejecting past limit. Keep it — and unit-test its known flaw: up to 2×limit requests can pass inside one window-straddling burst.
  • Sliding window log — per key: a timestamp log of accepted requests; a request is allowed if fewer than limit timestamps fall within the trailing window; prune as you go. Exact behavior, O(limit) memory per key — the reference the others are judged against.
  • Sliding window counter — the compromise: current and previous fixed-window counters, the previous one weighted by its overlap with the trailing window (prev × overlap_fraction + current). Near-exact at O(1) memory.
  • Rejection contract — a rejected request gets 429 Too Many Requests with a Retry-After header (whole seconds until a request could next succeed). Every response — allowed or not — carries X-RateLimit-Limit, X-RateLimit-Remaining, and X-RateLimit-Reset so a well-behaved client can pace itself without ever seeing a 429.
  • Comparison harness — one bursty client profile (e.g. 3× the sustained limit for 2 s, silence, repeat) replayed against all four algorithms; output a per-second admitted-requests series per algorithm (table or chart) showing the double-burst leak of fixed window and the smoothing of the others.

3. Composition — one edge

Mount the rate limiter inside the balancer, in front of backend selection: a rejected request costs no backend capacity. Per-key limits come from configuration (a default plus optional per-key overrides). The full rejection contract of §2 applies at the edge.

4. Distributed counters

Run two edge instances behind any entry point (round-robin DNS, a TCP proxy, or just a client alternating between them). Local buckets now let a client reach ~2× its quota. Fix it by backing the counters with a shared store (Redis or your own build-your-own-Redis server): the check-and-consume must be atomic — a Lua script (or equivalent single server-side operation), never a read-modify-write from the edge. Measure both configurations: enforcement accuracy (admitted rate vs. configured limit) and added per-request latency, and present the trade-off in a short table.

5. Load-test protocol

Drive the system with wrk2 (constant-throughput mode, which avoids coordinated omission) on an otherwise idle machine:

  1. Baseline: wrk2 straight at one backend — record p50/p99/p999.
  2. Through the edge (limiter keyed so the test client is never limited) — same rates, same duration; report the p99 delta as "what the edge costs".
  3. Limiter enforcement: set a per-key limit, drive wrk2 at 2× that limit, and verify the admitted (non-429) throughput sits within 2% of the configured limit.

Report the exact wrk2 invocations with the numbers.

Constraints

  • Standard library plus, at most, an HTTP toolkit — no proxy frameworks, no rate-limiting libraries; the algorithms and the balancing logic are the exercise. (Redis as milestone 7's shared store is allowed and expected.)
  • The balancer is L7 and transparent: apart from the header rules above, a client must not be able to tell (from status, headers, or body) whether it hit the backend directly or through the edge.
  • All tunables — backends, weights, health-check interval and thresholds, algorithm, limits, window sizes — are configuration, not code edits.
  • Time-based logic must be testable: inject the clock so window and refill arithmetic is unit-testable without sleeping.

Acceptance

Mapped one-to-one onto the exercise's milestones:

  1. Reverse proxy — for GET and POST (with body), curl -i direct vs. proxied differs only in the specified hop-by-hop/forwarding headers; diff on the bodies is empty.
  2. Round robin — 90 requests across 3 backends land exactly 30/30/30; killing one backend yields 502 on its turns and no balancer crash.
  3. Health checks — kill a backend under continuous traffic: after the configured threshold×interval it stops receiving requests and clients stop seeing 502s; restart it and it rejoins within threshold×interval; both transitions appear in the log.
  4. Rate limiter, in process — unit tests (injected clock) pass for token bucket and fixed window, including: burst of capacity allowed then denial; and the window-straddling 2×limit burst that fixed window admits but token bucket doesn't.
  5. Sliding window — log and counter variants pass the same suite (counter within ~1% of log's decisions); the comparison harness outputs the per-algorithm admitted series for the shared bursty profile.
  6. Composed edge — a scripted client exceeding its key's limit receives 429 with Retry-After and the three X-RateLimit-* headers; a client that obeys them never receives a 429; backends receive no rejected requests.
  7. Distributed counters — with two edges and local buckets, a client demonstrably exceeds its quota (~2×); switching to the shared atomic store brings admitted rate within 2% of the limit; the accuracy-vs-latency table for both setups is filled in.
  8. Load test — the wrk2 report shows baseline vs. through-edge p99 and the enforcement run's admitted throughput within 2% of the configured limit, with exact invocations reproducible from the README.

Related