Design a Rate Limiter: Interview Answer
On this page
The problem: design a rate limiter for a public API
"Design a rate limiter for our public API: each API key gets 100 requests per minute." Work through it yourself first. The interesting part isn't the counting algorithm; it's making the limit hold when requests from one client land on twenty different servers.
Rate limiter requirements
Functional: allow requests under the limit; reject the rest with HTTP 429 Too Many Requests, plus headers saying the limit, how many requests remain, and when to retry (Retry-After). Limits can differ per plan.
Non-functional: it runs on every request, so it must add very little latency, around a millisecond. It must be accurate across many servers. And it must not take the API down if it fails.
Rate limiting algorithms: token bucket vs sliding window
| Algorithm | How it works | Strength | Weakness |
|---|---|---|---|
| Fixed window counter | Count per key per minute; reset each minute | Tiny and simple | A client can send 100 at 0:59 and 100 at 1:00 |
| Sliding window log | Store each request's timestamp; count those in the last 60 s | Exact | Memory grows with the limit |
| Sliding window counter | Weighted mix of this and last window's counts | Close to exact, small | An approximation |
| Token bucket | Bucket of N tokens refilled at a steady rate; each request spends one | Allows short bursts, enforces the average | Two parameters to tune |
The sliding window counter deserves one worked line, because interviewers ask for it. Keep one counter per fixed minute. At 12:01:15, a quarter of the way into the current minute, estimate the last 60 seconds as the current minute's count plus 75 percent of the previous minute's. With 40 requests so far and 80 in the previous minute, that's 40 + 0.75 × 80 = 100, so the next request is rejected. It needs two small counters per key, and its only error comes from assuming the previous minute's requests were spread evenly.
Token bucket is a strong default for APIs: clients really do send bursts, and the bucket size says how big a burst is acceptable while the refill rate sets the long-run average.
Distributed rate limiting with Redis and Lua
The roadmap's rate limiting lesson compares these algorithms in more depth.
Put the limiter in the API gateway, the entry point for all traffic. Each request is checked once, before it reaches any backend service, and services don't each reimplement limiting.
There are many gateway servers behind a load balancer. If each kept counts in its own memory, a client spread across 20 servers would get 20 times the limit. So the counts live in a shared fast store, typically Redis, keyed by API key.
The check must be atomic. If two servers both read "1 token left" and both allow a request, the limit breaks. A Lua script runs as one indivisible step in Redis:
-- KEYS[1] bucket key; ARGV: now (ms), refill rate (tokens/s), capacity
local now = tonumber(ARGV[1])
local rate = tonumber(ARGV[2])
local capacity = tonumber(ARGV[3])
local state = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(state[1]) or capacity
local ts = tonumber(state[2]) or now
tokens = math.min(capacity, tokens + (now - ts) / 1000 * rate)
local allowed = 0
if tokens >= 1 then
tokens = tokens - 1
allowed = 1
end
redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('PEXPIRE', KEYS[1], math.ceil(capacity / rate * 1000) + 1000)
return allowedRun against Redis with a capacity of 5 and a refill of 1 token per second, seven instant requests returned 1111100: five allowed, two rejected. Two seconds later, two more were allowed and the third rejected. The expiry removes buckets for keys that stop sending traffic, so memory doesn't grow forever.
The gateway passes its own clock as now. If gateway clocks disagree by a lot, buckets refill unevenly; using Redis's TIME inside the script avoids that.
The script touches one key per bucket, so it also runs unchanged on Redis Cluster, where each key lives on one shard. A script that touched several keys would need them on the same shard, which Redis Cluster arranges with hash tags such as {key:42}:tokens.
When Redis is down: fail open or fail closed
The limiter must not become the reason the whole API is down. Run Redis with a replica and failover, keep the call timeout short, and decide in advance what happens on failure. Usually that's fail open: allow requests without limiting for the moment and alert. Briefly unlimited traffic is a smaller risk than rejecting every request. For a limit that protects something fragile, such as an expensive downstream partner, you might fail closed instead and say so.
What a strong rate limiter answer includes
- A clear algorithm choice with its trade-off.
- Placement at the gateway, with keys per API key, user or IP.
- Shared state with an atomic check, and why local counters fail.
- Correct client responses: 429 and retry headers.
- A stated fail-open or fail-closed decision.
- Scale: one Redis key per active client is small; shard Redis by key if needed.
Check yourself
A client's requests spread across servers, and each server enforces the full limit on its own, so the effective limit is multiplied by the number of servers.
All 200 are allowed within two seconds because the counter resets at the boundary. A sliding window or token bucket prevents the burst.
Every API request is rejected, so the limiter caused a full outage. For most APIs, fail open with alerting, and protect Redis with replication and short timeouts.
Reading the counter, deciding and updating it must happen atomically, or two concurrent requests could both see room and both be allowed. A Lua script runs as one operation on Redis, so the check and update can't interleave with other clients.
Status 429 Too Many Requests, a Retry-After header saying when to try again, and ideally headers showing the limit and remaining quota. That lets well-behaved clients back off correctly instead of hammering the API.