Design a Rate Limiter

Clarify requirements

The prompt: "Design a rate limiter for our public API." Worth pinning down first:

• Limiting key — per user, per API key, per IP address, or some combination? A logged-out client typically gets limited by IP; an authenticated one by user or API key.
• Limit shape — a flat "100 requests per minute", or does it need to allow short bursts above the steady-state rate (a common real-world requirement — a client batching 20 requests in one second should not necessarily be throttled if their per-minute average is fine)?
• Behavior when limited — reject with an HTTP 429 and a `Retry-After` header, or queue and delay? Rejecting is by far the more common expectation and the simpler system; assume that unless told otherwise.
• Scope — is this a single limiter for one service, or shared infrastructure sitting in front of many services (an API-gateway-level concern)? This materially changes where the component lives architecturally.

For this walkthrough: per-user limiting, burst tolerance matters, limited requests are rejected with a 429, and the limiter is shared infrastructure in front of multiple backend services — the more interesting and more commonly asked version of this problem.

Estimate scale

Assume 10 million active users and a typical per-user limit of 100 requests/minute. The limiter itself does not need to store request bodies or history beyond what its algorithm requires — a handful of bytes per user (a counter and a timestamp, or a small rolling window) — so even at 10 million concurrent trackable users, total state is on the order of a few hundred MB, comfortably held in an in-memory store. The real scale concern is not storage volume; it is throughput and latency — every single API request, across the whole platform, has to pass through a rate-limit check, so that check needs to add single-digit milliseconds of latency at whatever the platform's aggregate request rate is.

High-level design

A request flows: client → API gateway → rate-limit check (allow/reject) → on allow, forward to the backend service; on reject, return 429 immediately without touching the backend at all. The rate-limit check itself needs a shared counter store that every gateway instance reads and writes against — this is the crux of the design, covered in the deep dive below, because the wrong choice here silently breaks correctness under concurrent load rather than producing an obviously broken system.

Deep dive: the algorithm and where state lives

Three algorithms are worth being able to compare on the spot:

• Fixed window counter. Count requests in discrete windows (e.g., 00:00-00:59, 01:00-01:59). Simplest to implement, but has a real edge-case flaw worth naming unprompted: a user can send the full limit at 00:59 and again at 01:00 — technically two separate windows, but functionally a burst of 2x the intended limit in under two seconds.
• Sliding window log. Store the timestamp of every request in the last window and count them on each check. Exactly correct, no boundary flaw — but memory cost scales with request volume per user, which is expensive at real traffic levels.
• Token bucket. Each user has a bucket that refills at a fixed rate up to a max capacity; each request consumes a token, and a request is rejected if the bucket is empty. This naturally allows controlled bursts (up to the bucket's capacity) while enforcing a steady-state rate over time, and needs only two numbers of state per user (current token count, last refill time) — the best fit for this problem's burst-tolerance requirement from phase one, at low memory cost.

Where the state lives is the part that actually decides correctness. If each gateway instance keeps its own local token bucket per user, a user routed across three gateway instances effectively gets three times the intended limit — the limiter looks like it works in a single-instance demo and silently fails the moment there is more than one instance, which in production there always is. The fix is centralizing the bucket state in a shared, low-latency store — Redis is the standard choice — with the check-and-decrement implemented as a single atomic operation (a Lua script or `INCR`-based pattern in Redis) so two concurrent requests from the same user cannot both read "1 token left", both decrement, and both get allowed when only one token actually existed. Getting this atomicity right, and being able to explain why a naive read-then-write is broken under concurrency, is the single highest-signal moment in this entire problem.

Trade-offs and follow-ups

• "What happens if Redis goes down?" A rate limiter is a shared-fate component sitting in front of every request — if it is unreachable, the safer default for most products is fail open (allow requests through, accepting some risk of abuse) rather than fail closed (reject everything, turning a rate-limiter outage into a total outage). State this choice explicitly and note it is a product decision, not a purely technical one — a payments API might reasonably choose the opposite default.
• "How would you avoid Redis becoming a bottleneck at very high request rates?" Shard the counter store by user ID (consistent hashing across multiple Redis instances) so no single node holds all the state or takes all the traffic, and consider a local, short-lived approximate cache at the gateway layer to absorb the very hottest keys — accepting a small amount of temporary over-limit as the cost of not hitting the shared store on every single request.

How the bar changes by level

At SDE 2, correctly identifying that per-instance local state is broken and proposing a shared store is already a solid answer. At Senior, the atomicity argument (why check-then-write races, what an atomic Redis operation fixes) is expected as a first-pass answer, not something the interviewer has to extract with follow-ups. At Staff, the conversation typically extends past this one service: how this rate limiter composes with per-endpoint limits, tiered limits by subscription plan, and the organizational question of whether every team builds its own limiter or a shared platform team owns this as infrastructure other services depend on — the technical algorithm is almost a formality by that point, and the conversation is really about system boundaries and ownership.

See Design a URL Shortener for a first worked problem where scale and an encoding trade-off, rather than concurrency, are the central decision.