Design a Rate Limiter: Algorithms Are the Easy Part

“Design a rate limiter” is the system design question with the most memorizable answer, and interviewers know it. Most candidates say “token bucket,” draw Redis, and stop. The interviewer then asks what happens when Redis is slow, and the answer either has depth or it does not.

The algorithm is maybe a fifth of the question. The rest is where the limiter lives, how you keep counters correct across many servers, what you do when the counter store fails, how you identify the client, and what you promise callers when you reject them. By the end of this post you will have a structure that covers all five, and a set of numbers and names to make each decision sound deliberate.

The Question

The direct forms:

• “Design a rate limiter for our public API.”
• “How would you prevent a single client from overwhelming the service?”
• “Which rate limiting algorithm would you use, and why?” (the narrowed version)

The variants that hide the same question: “design an API gateway” almost always turns into rate limiting within ten minutes, and “how do you protect a downstream dependency with a fixed capacity” is rate limiting pointed inward instead of outward.

What They Are Really Asking

1. Do you know why you are limiting? Abuse prevention, fairness between tenants, cost control, and protecting a fixed-capacity dependency are four different goals with different designs. A candidate who does not ask which one is building blind.
2. Can you reason about correctness in a distributed system? The counter lives somewhere shared. Check-then-increment is a race. The interviewer wants to hear the word “atomic” and see you know how to get it.
3. Do you think about failure? The rate limiter sits in the request path of every call. If it is slow, everything is slow. If it is down, you have to choose between letting everything through and blocking everything. That choice is the most revealing part of the answer.
4. Do you understand the contract with the caller? A rejected request is an API response, with a status code, headers, and documentation. Senior candidates treat that as part of the design.
5. Can you separate concepts that get conflated? Rate limiting, load shedding, backpressure, and circuit breaking are neighbors, not synonyms. Confusing them is a common tell.

A weak answer is “token bucket in Redis, 429 on reject.” A strong answer treats that as the starting sketch and spends its time on the decisions around it.

The Gotchas

Gotcha 1: Naming an algorithm without saying what it optimizes for. Every algorithm is a trade-off between allowing bursts, smoothing traffic, memory per key, and accuracy at window boundaries. Fixed window counters let a client send double the limit across a boundary (the last second of one window plus the first second of the next). If you pick one without naming its weakness, the interviewer will name it for you.

Gotcha 2: Check-then-increment. “Read the count, and if it is under the limit, increment it.” Two requests from the same client on two servers both read 99, both pass, both write 100. The fix is a single atomic operation in the store: a Lua script in Redis, a transaction, or a store-side increment that returns the new value. Say the word atomic and say how.

Gotcha 3: No answer for when the counter store is unavailable. This is the question most likely to be asked and least likely to be prepared. The two options are fail open (let traffic through unlimited) and fail closed (reject everything). The right answer depends on what you are protecting. Fail open for a public API where availability matters more than fairness. Fail closed for a limiter protecting a downstream that will fall over. Say the choice is per-rule, not global.

Gotcha 4: Keying on IP address by default. IP limits punish everyone behind a corporate NAT (Network Address Translation) or a mobile carrier gateway, and barely inconvenience an attacker with a botnet. Key on the authenticated identity (API key, user ID, tenant) when you have it. Use IP only as a fallback for unauthenticated endpoints, and expect it to be coarse.

Gotcha 5: Forgetting the response contract. A rejected request should return 429 Too Many Requests, a Retry-After header, and ideally the RateLimit headers (limit, remaining, reset) so well-behaved clients can back off before they hit the wall. If you return 503 or a generic 400, clients cannot distinguish “you are going too fast” from “we are broken.”

Gotcha 6: Making the limiter a synchronous hop to another region. If the counter store is in one region and requests arrive in three, every request pays cross-region latency for a counter check. Either keep limits per region or accept approximate global limits with local enforcement and async reconciliation.

Gotcha 7: Confusing rate limiting with load shedding. Rate limiting is a policy about a client: you may make N requests per minute regardless of how busy we are. Load shedding is a policy about the server: we are at capacity, so we are dropping requests regardless of who sent them. Both may exist. They are different mechanisms with different triggers.

Gotcha 8: A hot tenant on one shard. If you shard the counter store by client key, one enormous tenant lands on one shard and can saturate it. Mention it, and mention the fix: split the tenant’s counter into sub-keys and sum, or give the big tenant a local limiter in front of the shared one.

How to Answer

Step 1: Ask what you are protecting

Question	Why it matters
What is the goal: abuse, fairness, cost, or protecting a downstream?	Decides fail-open vs. fail-closed and how accurate the limit must be
How do we identify a client? API key, user, tenant, IP?	Decides the key and how coarse enforcement can be
What scale? Requests per second, and how many distinct clients are active at once?	Sizes the counter store and decides whether local enforcement is needed
Hard reject, or throttle and queue?	A hard limit returns 429. A soft limit delays. Different designs
Single region or multi-region?	Decides whether counters can be exact
Is a small amount of over-admission acceptable?	If yes, many cheaper designs open up
Do limits vary by plan tier or endpoint?	Means rules are data, not code, and need a config path

Defaults if the interviewer says “you choose”: public REST API, clients identified by API key, 10,000 requests per second aggregate, 1 million active keys, limits vary by tier, a few percent over-admission during failures is acceptable, one region to start.

Step 2: Define the rule model

Say it in one sentence: a rule is a key, a limit, and a window, and a request can match several rules that are all evaluated.

rule:   per API key, 1,000 requests per minute
rule:   per API key per endpoint, POST /orders, 60 per minute
rule:   per IP for unauthenticated routes, 100 per minute
rule:   global, 50,000 per second (protects the platform)

All matching rules must pass. This is the moment to say that rules are configuration, live in a store the gateway watches, and can change without a deploy.

Step 3: Compare the algorithms

Put them side by side and be explicit about the trade-offs.

Algorithm	How it works	Bursts	Memory per key	Boundary accuracy	Notes
Fixed window	Counter per window (e.g. per minute), reset at boundary	Allows 2x at the boundary	One integer	Poor	Simplest; fine for coarse quotas
Sliding log	Store the timestamp of every request; count those inside the window	Exact	One timestamp per request	Exact	Memory grows with the limit; too expensive at high rates
Sliding window counter	Weighted blend of the current and previous fixed windows	Approximate, no 2x spike	Two integers	Very good	Cloudflare’s choice; cheap and accurate enough
Token bucket	Bucket refills at rate r, holds up to b tokens; each request takes one	Allows bursts up to b, then rate r	Two numbers (tokens, last refill time)	Exact for the model it implements	The default for API limits; two tunable knobs
Leaky bucket	Requests enter a queue drained at a fixed rate	No bursts; smooth output	Queue	Exact	Shapes traffic rather than limiting it; adds latency

A defensible recommendation: token bucket for per-client API limits, because clients legitimately burst (a page load fires ten calls) and the bucket size lets you say how much burst is acceptable independently of the sustained rate. Sliding window counter if the requirement is a strict “no more than N per minute” with low memory. Leaky bucket only when the goal is smoothing traffic into a fixed-capacity downstream, and say that it adds queueing delay.

State the token bucket math so the interviewer sees you can size it: rate 1,000 per minute means refill at 16.7 tokens per second; bucket size 100 means a client can fire 100 requests instantly, then is held to 16.7 per second.

Step 4: Decide where it lives

Location	Pros	Cons	Use for
Client SDK	Zero server cost, good citizenship	Cannot be trusted; malicious clients ignore it	A courtesy layer, never the enforcement layer
Edge or API gateway	One place, protects everything behind it, rejects cheaply before work is done	Coarse; knows the route but not the resource	Per-client and per-endpoint limits
Service middleware	Knows the business context (tenant, resource)	Duplicated per service; request has already cost a hop	Resource-specific limits
Dedicated rate limit service	Shared logic, one place to change rules	An extra network hop on every request; must be very fast and highly available	Large orgs with many gateways

Recommend enforcing at the gateway for the standard rules, with a shared library for services that need resource-level limits. Reject before the expensive work happens.

Step 5: Make the distributed counter correct

This is the core of the design. Draw it.

flowchart LR
    C[Client] --> GW1[Gateway node 1]
    C --> GW2[Gateway node 2]
    C --> GW3[Gateway node 3]
    GW1 & GW2 & GW3 -->|atomic script| R[(Redis cluster<br/>sharded by client key)]
    RS[(Rules store)] -.->|watch/poll| GW1 & GW2 & GW3
    GW1 & GW2 & GW3 -->|allowed| API[Backend services]
    GW1 & GW2 & GW3 -->|429 + headers| C

Talk through the counter operation. For a token bucket, the state per key is the token count and the last refill timestamp. The check-and-take must be one atomic step:

-- KEYS[1] = bucket key; ARGV = rate, capacity, now, requested
local tokens, ts = unpack(redis.call('HMGET', KEYS[1], 'tokens', 'ts'))
tokens = tonumber(tokens) or capacity
ts = tonumber(ts) or now
local refill = (now - ts) * rate
tokens = math.min(capacity, tokens + refill)
local allowed = tokens >= requested
if allowed then tokens = tokens - requested end
redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('EXPIRE', KEYS[1], ttl)
return { allowed and 1 or 0, tokens }

You do not need to write this on the whiteboard. You need to say: the script runs atomically on the shard that owns the key, so two gateway nodes cannot both take the last token. Then size it: 1 million active keys times roughly 100 bytes each is 100 MB. One Redis node holds that; you shard for throughput and availability, not for size.

Mention the time source. Use the store’s clock (Redis TIME) or accept that gateway clocks are synchronized within tolerance. Do not let clients supply timestamps.

Step 6: Decide what happens when the store is slow or down

Say this unprompted. It is the part of the answer that gets remembered.

• Timeouts are tiny. The limiter check gets a few milliseconds. Past that, treat it as a failure, do not queue behind it.
• Fail open by default for public API limits. Losing fairness for a few minutes is better than a total outage caused by the component meant to protect you. Log and alert loudly.
• Fail closed for limits that protect a fragile downstream. If the limiter in front of a payment provider with a hard contract limit fails, blocking is safer than blowing the contract.
• Degrade to local enforcement. Each gateway node keeps an in-memory bucket per key and uses it when the shared store is unreachable. Enforcement becomes per-node instead of global, so a client gets roughly N times the limit across N nodes. Say that number, and say it is acceptable for the stated requirement.
• Wrap the store call in a circuit breaker so a struggling Redis does not get hammered by retries from every gateway node.

Step 7: Define the contract with callers

• 429 Too Many Requests on rejection, never 503, never 400.
• Retry-After header with seconds until the client may try again.
• RateLimit headers on every response (the IETF draft standardizes RateLimit-Limit, RateLimit-Remaining, RateLimit-Reset), so well-behaved clients back off before hitting the wall.
• Document the limits per tier and make them visible in the developer dashboard. Undocumented limits generate support tickets.
• Distinguish throttling from quota. “1,000 per minute” is throttling. “1 million per month” is a quota. Quotas are usually enforced by a slower, exact system (billing), not the hot-path limiter.

Step 8: Scale and multi-region

• Sharding. Shard the counter store by client key. Every operation is a single-key point operation, so it scales linearly.
• Hot tenants. Split a huge tenant’s key into K sub-keys, pick one at random, give each sub-key limit/K. Slight unfairness, no hot shard.
• High-throughput hybrid. For very high request rates, enforce locally on each node with a small local bucket, and sync to the shared store every few hundred milliseconds. You trade exactness for a large reduction in store traffic. Only offer this if the interviewer confirms over-admission is acceptable.
• Multi-region. Exact global limits require a synchronous cross-region call, which is a non-starter on the hot path. Options: per-region limits that sum to the global figure (a client with 1,000 per minute gets 333 in each of three regions), or local enforcement with asynchronous global reconciliation and a tolerance. State which and why.

Follow-Up Questions to Expect

• “Redis is at 20 ms latency. What happens?” The check times out, the circuit opens, nodes fall back to local buckets, an alert fires. Traffic continues with approximate limits. Name the over-admission factor.
• “How do you change a customer’s limit at runtime?” Rules are data in a config store; gateways watch it. Tier changes take effect within seconds, no deploy.
• “How would you rate limit an LLM API?” By cost, not count. Each request consumes a weight (input plus output tokens) from the bucket instead of one token. Same algorithm, weighted take. This is worth having ready in 2026.
• “What is the difference between this and a circuit breaker?” A circuit breaker protects a caller from a failing callee by stopping calls. A rate limiter protects a callee from a caller by capping calls. Opposite directions, both useful.
• “How do you test it?” Property tests on the algorithm (never admits more than limit plus tolerance), a load test that confirms 429s appear at the expected rate, and a chaos test that kills the store and confirms the fallback behaves as designed.
• “A client is retrying immediately on 429 and making it worse.” That is why you send Retry-After, and why the SDK implements exponential backoff with jitter. If they still hammer you, the limiter is doing its job; the rejects are cheap.

Key Takeaways

• Ask what you are protecting. It decides fail-open vs. fail-closed and how exact the limit must be.
• Compare algorithms by burst behavior, memory per key, and boundary accuracy. Default to token bucket for API limits and know why.
• The counter operation must be atomic on the store. Say “Lua script” or “transaction” and say why check-then-increment is a race.
• Have a failure story: short timeouts, circuit breaker, local fallback, stated over-admission factor.
• Key on identity, not IP, whenever you can.
• 429 plus Retry-After plus RateLimit headers. The rejection is part of the API.
• Rate limiting, load shedding, backpressure, and circuit breaking are different things. Use the right name.

Further Reading

• Stripe Engineering, Scaling your API with rate limiters
• Cloudflare, How we built rate limiting capable of scaling to millions of domains
• IETF, RateLimit header fields for HTTP
• Figma Engineering, An alternative approach to rate limiting
• Alex Xu, System Design Interview, chapter on rate limiters