Design a rate limiter for an HTTP API that averages 1,000 requests per second with bursts up to 5,000 per second while running across multiple service instances.
Before you code
Before choosing an algorithm, commit to a state placement strategy (in-process, shared store like Redis, or hybrid) that accounts for cross-instance enforcement and latency cost.
Hints
- Token bucket is strong for bursts and steady rate; fixed window is simpler but boundary-skewed.
- In Redis, use an atomic Lua compare-and-swap to read, refill, and decrement safely across instances.
- Clock drift matters — use a monotonic clock and do not trust client timestamps.
Production & complexity notes
When solving Design a Rate Limiter on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Cache-Conscious Data Structures: Alignment, False Sharing, and Structure of Arrays to reinforce the underlying pattern.
What it practices
Rate-limiting algorithm tradeoffs and distributed coordination (atomicity, clock drift) under latency constraints, from Queues and ring buffers.