How would you design a rate limiter?
A rate limiter caps how many requests a client can make in a time window, for example 100 per minute per user, and rejects extras with HTTP 429. Common algorithms are token bucket (allows short bursts), fixed window, sliding window log and sliding window counter. In a distributed system the counters live in a shared store like Redis and are updated atomically.
Explain it simply
Think of the ticket counter at a cinema that gives each person a few tokens to spend on snacks. You start with 5 tokens. Each snack costs one token. Every minute, the counter gives you one more token, but your pocket can hold at most 5. If you rush in and buy 5 snacks at once, fine. But then you must wait for new tokens. That is a token bucket, the most common rate limiting idea.
A rate limiter protects a service from being overwhelmed, whether by a bug in a client, a scraper, a login brute-force attempt or a real traffic surge like the IRCTC Tatkal window opening at 10 AM.
Example
Token bucket with capacity 5 and a refill rate of 1 token per second:
time 0.0s tokens = 5
5 requests arrive -> all allowed, tokens = 0
time 0.5s request -> tokens = 0.5 -> rejected (429)
time 2.0s tokens = 2
1 request -> allowed, tokens = 1
time 10.0s tokens = 5 (capped, not 9)Pseudo-code, stored per client key in Redis:
allow(clientId):
bucket = load(clientId) // {tokens, lastRefill}
now = currentTime()
bucket.tokens = min(capacity, bucket.tokens + (now - bucket.lastRefill) * rate)
bucket.lastRefill = now
if bucket.tokens >= 1:
bucket.tokens -= 1
save(clientId, bucket)
return ALLOW
save(clientId, bucket)
return REJECT (HTTP 429, Retry-After header)In Redis this read-modify-write must be atomic, usually a Lua script, so two servers don't both spend the last token.
How it works
Requirements to clarify first
- Limit by what: user ID, API key, IP address, or endpoint?
- What limits: 100 per minute? Different tiers for free and paid users?
- Where: in an API gateway, as middleware in each service, or both?
- What happens on rejection: HTTP 429 with a
Retry-Afterheader, or queue the request? - Fail open or fail closed if the limiter's store is down?
Algorithms
| Algorithm | Idea | Pros | Cons |
|---|---|---|---|
| Token bucket | Tokens refill at a fixed rate up to a cap; each request spends one | Allows bursts, smooth average, tiny state | Two parameters to tune |
| Leaky bucket | Requests queue and leave at a fixed rate | Very smooth output | Bursts wait or get dropped |
| Fixed window | Count requests per calendar minute | Simplest, one counter | Up to 2x the limit at window edges |
| Sliding window log | Store timestamp of every request; count those in the last 60s | Exact | Memory grows with traffic |
| Sliding window counter | Weighted mix of current and previous window counts | Close to exact, small state | Approximate |
The fixed-window edge problem: with 100 per minute, a client can send 100 at 10:00:59 and 100 more at 10:01:00, so 200 in two seconds. Sliding windows fix this.
High-level design
Client -> API gateway / LB -> Rate limit middleware -> Service
|
v
Redis (shared counters, with TTLs)
Rules (limits per tier/endpoint) loaded from config, cached locally.Every app server checks the same Redis, so limits hold across all servers. Keys get a TTL so idle clients' counters disappear. Responses include headers like X-RateLimit-Remaining so clients can slow down politely.
Real-world use
Public APIs such as payment gateways and SMS providers limit calls per API key. Login and OTP endpoints limit attempts per phone number and per IP to stop brute force and SMS-cost abuse. API gateways and CDNs offer rate limiting as a built-in feature, often using token bucket.
Common mistakes
- Keeping counters in each server's memory. With 10 servers, a user effectively gets 10 times the limit.
- Non-atomic "get then set" in Redis, letting concurrent requests slip past the limit.
- Limiting only by IP. Many users behind one college or office NAT share an IP and get blocked together.
- Forgetting to decide fail-open versus fail-closed when Redis is unavailable.
- Returning a generic 500 instead of 429 with
Retry-After.
What to say in the interview
"First I'd clarify what we limit on, such as user ID or API key, the limits per tier, and whether it sits in the gateway. I'd use a token bucket because it allows short bursts while enforcing an average rate and needs only two values per client. The state lives in Redis so every server shares it, updated atomically with a Lua script, with TTLs to clean up idle keys. Rejected requests get HTTP 429 with a Retry-After header. If Redis is down I'd usually fail open for normal APIs but fail closed for sensitive ones like OTP. If exact window limits matter, I'd use a sliding window counter instead."
Follow-up questions
- Why does a fixed window allow double the limit at the boundary?
- How would you rate limit across multiple data centres?
- Should a rate limiter fail open or fail closed?
- How would you give paid users higher limits?
- How is rate limiting different from load shedding?
Go deeper
Read these once the basics above feel easy.
Sliding window counter estimate: count = current_window + previous_window * (1 - elapsed_fraction_of_current_window). With a limit of 100, 40 requests in the previous minute, 30 in the current one and 25% of the current minute gone, the estimate is 30 + 40 * 0.75 = 60, so the request is allowed. Two counters per key give near-exact behaviour with tiny memory.
At very high scale, a Redis round trip per request adds latency and load. Options: a local in-memory bucket per server that periodically syncs with Redis (slightly less accurate), sharding Redis by client key, or enforcing coarse limits at the edge and fine limits in services. Across regions, either accept per-region limits or sync counters asynchronously and tolerate small overshoot. Combine rate limiting with load shedding and circuit breakers so the system degrades gracefully when the limits themselves are not enough.