Design a Rate Limiter
MediumAsked at: Amazon, Stripe, Google, Cloudflare
A standalone service/library that throttles the number of requests a client can make in a given time window, used to protect APIs from abuse and overload. A great 'systems building block' question that tests algorithmic + distributed-systems depth without requiring huge architecture diagrams.
Request flow
Functional Requirements
- Limit requests per client (by API key, user ID, or IP) to N requests per time window.
- Reject (HTTP 429) requests over the limit, ideally telling the client when they can retry.
- Support different limits per client tier (free vs. paid) and per endpoint.
Non-Functional Requirements
- The rate limiter itself must add negligible latency (it sits on the hot path of every request).
- Must work correctly across a fleet of many API servers (not just per-instance).
- Should be resilient — if the rate-limiter's datastore has a hiccup, prefer to fail open (allow traffic) or fail gracefully rather than take down the whole API.
Capacity Estimation
- If the API sees 1M requests/sec across all clients, the rate limiter must make an allow/deny decision at that same throughput with sub-millisecond overhead per check.
- State needed is small per client (a counter or small timestamp list) but multiplied by potentially millions of distinct clients — favors an in-memory store like Redis over a full relational DB.
Design Walkthrough
1. Choosing the algorithm
Token Bucket (most common default): each client has a bucket with capacity C, refilled at rate R tokens/sec; each request consumes a token, rejected if the bucket is empty. Allows short bursts up to C while enforcing a long-run average rate of R — matches how real client traffic behaves (bursty, not perfectly smooth).
Sliding Window Counter: approximates a true sliding window using the current and previous fixed windows' counts, weighted by how far into the current window we are — much cheaper than storing a full timestamp log, and avoids the fixed-window boundary-burst problem.
For most interviews, presenting Token Bucket as the primary answer (simple, well-understood, industry standard) with Sliding Window Counter as the 'more accurate alternative' shows good breadth.
2. Architecture — where does the limiter live?
At the edge/API Gateway/load balancer, so abusive requests are rejected before consuming any backend capacity — this is almost always the right placement, not deep inside a downstream service.
Implemented as a shared library called by each API server, backed by a centralized fast store (Redis) holding the per-client counters/bucket state — using `INCR`+`EXPIRE` (fixed window) or a Lua script (atomic token-bucket check-and-decrement) to avoid race conditions from concurrent servers reading/writing the same key.
3. Handling the distributed nature
Because many API server instances check the same client's limit concurrently, the check-and-decrement operation on the shared counter must be atomic — a Lua script executed by Redis (single-threaded per key) is the standard way to make 'check remaining tokens, then decrement' atomic without a separate distributed lock.
For extreme scale, consider a hybrid: each API server keeps a small local approximate counter and only syncs with the central store periodically, trading some precision for far less network chatter — acceptable because rate limiting doesn't need to be perfectly exact, just approximately enforced.
4. Client experience
Return `429 Too Many Requests` with a `Retry-After` header (and often `X-RateLimit-Limit` / `X-RateLimit-Remaining` / `X-RateLimit-Reset` headers) so well-behaved clients can back off automatically instead of hammering the API in a retry loop.
Bottlenecks & Mitigations
- The centralized Redis store becomes a critical dependency for every request — mitigate with a highly-available Redis cluster and a 'fail open' policy (allow requests through, perhaps logging a warning) if Redis is unreachable, rather than failing the whole API.
- Extremely high cardinality of distinct clients (millions of API keys) means the counter store's memory footprint matters — use short TTLs so inactive clients' counters expire naturally instead of accumulating forever.
Likely Follow-Up Questions
- How would you rate limit by multiple dimensions simultaneously (per-IP AND per-API-key)? (Run independent checks against independent keys/buckets for each dimension; reject if any one is exceeded.)
- How do you avoid the rate limiter itself becoming a bottleneck at 1M+ req/sec? (Shard the Redis layer by client key hash, and/or use the local-approximate-counter hybrid mentioned above.)
- How would you rate limit a distributed system with no single shared datastore at all (fully offline/edge scenario)? (Accept approximate enforcement: each node enforces limit/N independently, trading precision for zero shared-state dependency.)