Design a Rate Limiter

You're asked to design a rate limiter: a component that decides whether a given request is allowed through or rejected, based on how many requests that caller has already made in some recent window. It should enforce limits consistently across a fleet of servers rather than per machine, add almost no latency to the requests it allows, and keep working when the machinery behind it fails.

The single-server version is a few lines of code. What makes this an interview question is that your API runs on hundreds of servers, and a user hitting a different server on each request must still be held to one shared limit.

Clarifying the requirements

• What's the limit keyed on? Per user, per API key, per IP, per endpoint, or a combination. Multiple simultaneous limits are common: 100 requests per minute per user and 10,000 per minute per organization.
• What happens when a request is denied? Return HTTP 429 with a Retry-After header is the standard. Ask whether denied requests should be queued instead, which is a different design.
• How strict does the limit need to be? Allowing 105 requests when the limit is 100 is usually fine. If it isn't, the design gets much more expensive, and it's worth knowing that before you start.
• Where does it run? At the API gateway, as a middleware in each service, or as a standalone service. The gateway is the common answer.

Back-of-envelope numbers

• 10k requests/sec across the fleet, each requiring a counter check → 10k counter operations/sec
• 10M distinct users, but only a fraction active in any window → ~1M live counter keys
• At ~100 bytes per key, that's roughly $1\text{M keys} \times 100\text{ B} \approx 100\text{ MB}$

The counter state is small enough to hold in memory, which is what makes a shared in-memory store the natural home for it.

High-level architecture

Deep dive 1: choosing the algorithm

Four algorithms come up, and the interviewer wants you to compare rather than pick blindly.

• Fixed window. Count requests per clock-aligned interval, resetting at each boundary. Trivial to implement with one counter and a TTL. Its flaw is the boundary burst: a user can send their full limit at 11:59:59 and again at 12:00:00, briefly getting double the intended rate.
• Sliding window log. Store a timestamp per request and count those falling inside the window. Perfectly accurate, and expensive, since memory grows with request volume rather than with user count.
• Sliding window counter. Keep the current and previous fixed windows, and weight the previous one by how much of it still overlaps the sliding window. Approximate, but it removes the boundary burst at almost no extra cost. This is usually the right answer.
• Token bucket. A bucket holds tokens up to a maximum, refills at a fixed rate, and each request consumes one. Requests are allowed when a token is available. This deliberately permits short bursts up to the bucket size while enforcing a long-run average, which matches how most APIs actually want to behave.

Deep dive 2: making the check atomic

Every server checking the same counter creates a classic race condition. Two requests read a count of 99, both conclude they're under the limit of 100, and both proceed. It's the same read-check-write race described in transactional workflows.

The check and the increment have to happen as one indivisible operation. In practice that means executing the logic where the data lives rather than in your application:

• Atomic increment with expiry. For a fixed window, Redis INCR returns the new value atomically, and you set a TTL on first creation. One round trip, no race.
• A Lua script for anything more complex. Token bucket refill requires reading the current token count and last-refill timestamp, computing the new balance, and conditionally decrementing. Running that as a script on the store makes the whole sequence atomic.

Deep dive 3: keeping latency low

A rate limiter sits in front of every request, so its own latency is added to every request your API serves. A 5 ms check on a 20 ms endpoint is a 25% latency tax.

Three techniques, worth presenting as a progression:

• Co-locate the counter store with the gateway fleet, so the check is a sub-millisecond round trip within one datacenter rather than across regions.
• Batch and pipeline where a request needs multiple checks against per-user, per-organization, and per-endpoint limits, so three checks cost one round trip rather than three.
• Approximate locally. Each gateway keeps a small local counter and synchronizes with the shared store periodically rather than per request. This trades exactness for speed, and at high volume it's often the right trade: allowing 103 requests instead of 100 costs nothing, while adding latency to every request costs a great deal.

Deep dive 4: hot keys and failure

Hot keys are the dominant scaling problem. Limits are keyed by user or API key, and one enormous customer can send a large share of all traffic, concentrating on a single counter and therefore a single store node. The escalating responses are the same as in distributed storage: shard that key's counter into N sub-counters that each accept 1/N of the limit and are checked round-robin, or move the largest customers onto dedicated capacity.

When the counter store is unavailable, you have to choose in advance:

• Fail open and allow every request. Your API stays up, but it's unprotected exactly when infrastructure is already unhealthy.
• Fail closed and deny every request. Your API is protected and also effectively down.

Fail open is the usual answer for a public API where availability matters most, and fail closed is right where the limiter is a security control rather than a fairness one. What matters in the interview is naming the choice rather than leaving it undefined.

Deep dive 5: communicating limits to callers

Rate limiting is a developer-experience feature as much as a protection mechanism, and mentioning this separates candidates who have operated an API from those who haven't.

Return X-RateLimit-Limit, X-RateLimit-Remaining, and X-RateLimit-Reset headers on every response, not only on rejections, so a well-behaved client can slow itself down before being denied. On a 429, include Retry-After so clients back off by the right amount rather than retrying immediately and making the problem worse.

Common pitfalls

• Per-server counters. With N servers, the effective limit is N times what you intended.
• A non-atomic check-then-increment. Concurrent requests race past the limit.
• Fixed windows with no discussion of the boundary burst. It allows double the rate across a window boundary.
• No hot-key plan. One large customer's counter becomes a single-node bottleneck.
• No decision about store failure. Fail open and fail closed are both defensible; silence is not.

Leveling the answer

Related lessons