Design a Rate Limiter

A rate limiter caps how many requests a client may make in a period. It is a favourite interview problem because the requirements fit on one line while the design touches algorithms, distributed state, atomicity, failure modes and API behaviour. A strong answer is precise about the algorithm and honest about what goes wrong when the limiter itself is distributed.

The chapter follows the usual shape: understand the problem, set up the interface, build the high-level design, then go deep on the places where interviewers push, each with a weak, a solid and an excellent answer.

1. Understanding the problem

We are building a component that decides, for each incoming request, whether it is allowed or must be rejected because the caller has exceeded a limit.

Why rate limit at all

• Protect the service from overload caused by bugs, retry storms or abuse.
• Share capacity fairly, so one noisy client cannot starve others.
• Control cost, especially when a request triggers paid downstream work.
• Enforce product tiers, such as a free plan limited to 100 calls a minute.
• Slow attacks, such as credential stuffing against a login endpoint.

Functional requirements

Core:

1. Limit requests by an identifier: user, API key, IP address, or a combination, optionally per endpoint.
2. When a client is over the limit, reject the request with a clear error and tell the client when to retry.
3. Support different limits for different clients and routes, changeable without a deploy.

Confirm in or out: whether limits are per second, minute or day; whether bursts are allowed; whether the limiter is a library inside each service or a separate layer; and what happens to excess requests (reject, queue or slow down).

Non-functional requirements

• Very low overhead. The limiter sits in front of every request, so it must add well under a few milliseconds.
• High availability. A broken limiter must not take down the product.
• Accuracy that is good enough. Slight over- or under-counting is usually acceptable, so say how much error you tolerate.
• Works across many servers. A limit of 100 a minute means 100 across the whole fleet, not 100 per server.
• Scale. Assume 1 million limit checks per second at peak and tens of millions of distinct clients.

Estimation

What the numbers say. The state is tiny and fits in memory on a handful of machines. The challenge is not storage but throughput on shared counters and doing a read-modify-write atomically, a million times a second.

2. The set up

Core entities

• Rule: which requests it applies to (key type, route), the limit, the window or refill rate, and the burst capacity.
• Counter or bucket: the state for one key under one rule.
• Client identity: what the limit is keyed on.

Interface

The limiter exposes one decision, whether it is embedded or a service:

allow(key, rule) -> { allowed: true|false, remaining: n, reset_after_ms: t }

When a request is rejected, the HTTP response should be 429 Too Many Requests, with headers that let well-behaved clients back off:

HTTP/1.1 429 Too Many Requests
Retry-After: 12
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 1735689600

The exact header names for limit and remaining vary by API, but a retry hint is the part that matters.

3. High-level design

Where does the limiter live?

Three options, each with a trade-off:

The common answer is the API gateway: every request passes through it, so it can reject bad traffic before it reaches any backend. Finer, business-aware limits, such as "5 password resets per hour per account", can still live in the service that owns the logic.

The flow

1. A request reaches the gateway.
2. The limiter builds a key (for example user:42:POST:/v1/orders) and looks up the matching rule from a rules store, cached locally and refreshed periodically so that changing a limit needs no deploy.
3. It checks and updates the counter for that key in a fast shared counter store.
4. If allowed, the request proceeds to the backend. If not, the gateway returns 429 with a retry hint.

The rules are configuration with a low change rate. The counters are state with a very high change rate, and they are the part that needs careful design.

4. Potential deep dives

Deep dive 1: Which algorithm?

The challenge. Count requests over time in a way that is cheap, accurate enough, and handles bursts sensibly.

Weak: fixed window counter. Keep a counter per key per window, such as per minute, and reject when it passes the limit. It is trivial and uses one integer. Its flaw is the boundary burst: a client sends 100 requests at the end of one minute and 100 more at the start of the next, so 200 requests pass in a couple of seconds against a limit of 100 a minute.

Solid: sliding window log, or sliding window counter. A sliding window log stores a timestamp for each request and counts those in the last window. It is exact, and memory grows with the number of requests, which is too heavy for a high limit or a large client population.

A sliding window counter is the practical compromise. Keep the counts for the current and previous fixed windows, and estimate the sliding count by weighting the previous window by how much of it still overlaps:

$\text{estimate}=\text{prev}\times (1-f)+\text{curr}$

where $f$ is the fraction of the current window already elapsed. With a limit of 100 a minute, 84 requests in the previous minute, 36 so far in this one, and 25 percent of the window elapsed, the estimate is $84\times 0.75+36=99$, so one more request is allowed. It uses two integers per key and removes the boundary burst to a good approximation, with the assumption that requests were spread evenly in the previous window.

Excellent: token bucket, with the choice justified. A bucket holds up to $B$ tokens and refills at $r$ tokens per second. Each request removes a token and is rejected if none are left.

Its properties are what product teams usually want:

• It allows bursts up to $B$ after an idle period, then enforces a long-run average of $r$.
• It stores only two values per key: the token count and the time of the last refill. Refill is computed lazily on each request, with no background timer:

tokens = min(B, tokens + (now - last_refill) * r)
last_refill = now
if tokens >= 1: tokens -= 1; allow
else: reject

• Different rules just use different $B$ and $r$.

Mention the leaky bucket, which pushes requests through a queue at a fixed rate and so smooths traffic instead of permitting bursts, which suits protecting a downstream with a fixed capacity. Finish by tying the choice to the requirement: if bursts are fine, use a token bucket, and if you need a strict smooth rate, use a leaky bucket.

Deep dive 2: How do you make the limit global across many gateways?

The challenge. If each gateway keeps its own counters, a client spreading requests across ten gateways gets ten times the limit.

Weak: local counters on each server. Fast and trivial, but the limit applies per server. You can approximate a global limit by dividing it by the number of servers, which breaks when load is uneven or servers come and go.

Solid: a shared counter store. Keep counters in a fast in-memory store that every gateway uses. Every check becomes one network call, which costs a fraction of a millisecond within a data centre and gives a true global count. The risk is that the shared store becomes a bottleneck and a single point of failure, so it needs sharding and replication.

Excellent: sharded counters with atomic updates, plus local caching for speed. Shard the counters by key, so every key has exactly one owner and a client's counter lives in one place. Route each check to the owning shard using a hash of the key, with consistent hashing so that adding a shard moves few keys.

Then address the two things that go wrong:

• Atomicity. Reading a counter and writing it back in two steps lets two gateways both see "one token left" and both spend it. Do the whole check-and-update as one atomic operation on the shard, using an atomic increment, a compare-and-set, or a short server-side script that executes without interruption. State this clearly: the race condition is the core correctness trap in this problem.
• Latency and load. To cut the cost of a remote call on every request, let each gateway take a batch of tokens from the shared bucket and spend them locally, returning to the store when the batch is used up. This trades a little accuracy, since a gateway may briefly hold tokens that another could have used, for a large reduction in calls. Accept it only if the product tolerates small overshoot.

Deep dive 3: What happens when the limiter fails?

The challenge. The counter store becomes slow or unreachable. The limiter is on the critical path of every request.

Weak: block requests until the store answers. Now a limiter outage is a total outage, and a slow store makes every request slow.

Solid: set a short timeout and fail open. If the check does not complete within a few milliseconds, let the request through and record that you did. For most APIs, the harm of briefly not limiting is smaller than the harm of rejecting everyone. Alert immediately, since an unprotected service is at risk.

Excellent: choose the failure mode per rule, and degrade gracefully. Fail open for ordinary API limits, fail closed for security-sensitive limits such as login attempts, where letting traffic through is the dangerous side. Keep a coarse local fallback limit in each gateway so that during a store outage there is still some cap, even if it is per server and approximate. Replicate each shard with automatic failover, and have the limiter's own metrics, such as check latency and the fraction of fail-open decisions, on a dashboard.

Deep dive 4: Hot keys and unfair limits

The challenge. One key receives vastly more traffic than the rest, or limits applied by IP address punish innocent users.

Weak: ignore it. A single abusive key can overload the shard that owns it, and a corporate network behind one address gets blocked as a whole.

Solid: tier the limits and choose the key carefully. Use authenticated identity (user or API key) as the key where possible, because IP address is shared by many users behind NAT and cheap to change for an attacker. Apply a coarse per-IP limit as a first line before authentication, and a precise per-account limit after it.

Excellent: layered limits and fast rejection of obvious abuse. Combine several limits: a high global ceiling per account, a lower limit per sensitive endpoint, and a burst limit per second. Block the worst offenders early with a cheap check, for example a local in-memory deny list populated from the shared store, so that a flood of rejected requests does not translate into a flood of calls to the counter shard. For a legitimately hot key, such as a very large customer, give it its own rule and its own capacity.

Deep dive 5: Rules and the client experience

Rules. Store them in a configuration service, cache them in each gateway, and refresh on a short interval or by push. Version them, so a bad change can be rolled back, and support per-tenant overrides.

Client behaviour. The server's job includes teaching clients to behave. Return the retry hint, document the limits, and encourage clients to use exponential backoff with jitter rather than hammering. For batch work that can wait, offer a queue instead of rejection.

Observability. Track allowed and rejected counts per rule, the top rejected keys, and the latency of the limiter itself. A sudden rise in rejections is either an attack or a misconfigured rule, and you need to tell which.

5. What is expected at each level

Mid-level. You name at least one algorithm correctly, such as a token bucket or a fixed window, and can describe it. You place the limiter at the gateway and use a shared store for counts. You return 429 with a retry hint.

Senior. You compare algorithms and explain the boundary-burst flaw of a fixed window. You identify the race condition in a distributed counter and fix it with an atomic operation. You discuss failure behaviour and choose fail-open or fail-closed with reasons.

Staff. You discuss the whole system: layered limits, the cost of the check on every request, batching tokens to save calls, abuse that arrives from many addresses, multi-region limits where a global count is expensive, and how you would roll out and observe the limiter safely. You also ask what the limit is protecting and whether load shedding or queueing would serve the goal better.

6. Interview questions and model answers

Q: Which algorithm would you choose? A token bucket in most cases, because it allows short bursts, enforces a long-run average, and needs only two values per key with lazy refill. If the downstream needs a strictly smooth rate I would use a leaky bucket instead.

Q: What is wrong with a fixed window counter? A client can use the whole limit at the end of one window and again at the start of the next, so twice the limit passes in a short span. A sliding window counter or a token bucket avoids that.

Q: How do you enforce a global limit across servers? Keep counters in a sharded, replicated in-memory store keyed by client, and make each check-and-update atomic on the owning shard. Each gateway can fetch a batch of tokens to reduce calls, at the cost of some accuracy.

Q: What if the counter store goes down? Time out quickly and fail open for ordinary limits, with a coarse local fallback and an alert. For security-sensitive limits like login, fail closed.

Q: Why not limit by IP address alone? Many users share one address behind NAT, and attackers can rotate addresses easily. I use authenticated identity as the main key and IP as a coarse first line.

Q: How do clients know when to retry? The 429 response carries a retry-after hint and limit headers, and clients should back off exponentially with jitter.

7. Common mistakes

• Counting per server and calling it a global limit.
• A non-atomic read-then-write on the counter.
• Using a fixed window without noticing the boundary burst.
• Blocking requests when the limiter's store is down.
• Keying only on IP address.
• Rejecting without a retry hint.
• Hard-coding limits so that changing one needs a deploy.