Every public API has one. Type a wrong OTP too many times, refresh a ticket site during a sale, or hammer an API with a script, and you'll meet a rate limiter. “Design a rate limiter” is one of the most frequently reported system design questions at companies like Stripe, Amazon, Google and Uber because it's small enough for 45 minutes yet touches algorithms, distributed state, race conditions and failure handling.
Step 1 · Requirements
- Functional: limit requests per client by rule (e.g. 100/min per user, 5 login attempts/min per IP); reject extra requests with a clear error.
- Non-functional: adds only about a millisecond per request; works across many servers; highly available (if the limiter breaks, the API shouldn't); limits roughly accurate.
- Clarify: limit by user, IP or API key? Hard limit or soft? Server-side (yes: clients can't be trusted).
Step 2 · Estimates
Say 10 million daily users and a peak of 50,000 requests per second. Each check is one tiny Redis operation, and a single Redis node handles on the order of 100,000 simple operations per second, so a few nodes are enough. Memory: a token bucket needs two numbers per active user, say ~50 bytes with the key, so 10M users ≈ 500 MB. Small.
Step 3 · API and where it lives
The limiter usually isn't a public API; it's a check inside the request path. Common places: an API gateway (managed gateways offer it built-in), or middleware in your app servers. Internally it looks like allow(clientId, rule) → true/false. When rejecting, reply:
HTTP/1.1 429 Too Many Requests
Retry-After: 30
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 0
{"error": "Too many requests. Try again in 30 seconds."}Step 4 · Design: pick an algorithm
Five algorithms come up again and again. Interviewers expect you to compare a few and pick one with a reason.
| Algorithm | How it works | Pros | Cons |
|---|---|---|---|
| Token bucket | Tokens refill at a steady rate; each request spends one | Allows bursts; 2 numbers per user; simple | Tuning two knobs |
| Leaky bucket | Requests queue and leave at a constant rate | Perfectly smooth output | Bursts wait or are dropped; old requests can block new ones |
| Fixed window counter | Count requests per calendar minute; reset each minute | Easiest; one counter per user | Up to 2× the limit at window edges |
| Sliding window log | Store a timestamp per request; count those in the last 60 s | Exact | Memory grows with traffic |
| Sliding window counter | Blend current and previous window counts by overlap | Smooth, cheap, nearly exact | Approximate (assumes even spread) |
The fixed-window trap
The sliding window counter fixes this cheaply: at 1:15 with a 1-minute window, count = requests so far in the current minute + 75% of the previous minute's count (because 75% of the last 60 seconds overlaps it).
Token bucket: the most popular answer
Play with it. Spend the saved-up tokens with a burst, then watch them drip back:
🎮 Token bucket simulator
Send some requests. Try a burst, then click fast.
Notice the two knobs: capacity decides how big a burst is allowed, refill rate decides the long-run average. That's why APIs often say things like “100 requests per minute, bursts up to 20”.
import time
class TokenBucket:
"""Allow bursts up to `capacity`, refilling `rate` tokens per second."""
def __init__(self, capacity: int, rate: float):
self.capacity = capacity
self.rate = rate
self.tokens = capacity # start full
self.last = time.monotonic()
def allow(self, now: float | None = None) -> bool:
now = time.monotonic() if now is None else now
# 1. Refill for the time that has passed (never above capacity)
self.tokens = min(self.capacity, self.tokens + (now - self.last) * self.rate)
self.last = now
# 2. Spend one token if we have it
if self.tokens >= 1:
self.tokens -= 1
return True
return False # caller replies HTTP 429
bucket = TokenBucket(capacity=3, rate=1) # burst of 3, then 1 request/second
t = bucket.last
print([bucket.allow(t) for _ in range(4)]) # [True, True, True, False]
print(bucket.allow(t + 1)) # True (one token refilled)
print(bucket.allow(t + 1)) # FalseStep 5 · Scale: many servers, one limit
The code above lives in one server's memory. With 20 servers behind a load balancer, a user's requests are spread across all of them, so each server sees only a slice and the user effectively gets 20× the limit. The fix is a shared counter store, usually Redis:
-- Fixed window in Redis, as an atomic Lua script
-- KEYS[1] = "rl:user42:202611151031" ARGV[1] = limit ARGV[2] = window seconds
local n = redis.call("INCR", KEYS[1])
if n == 1 then redis.call("EXPIRE", KEYS[1], ARGV[2]) end
if n > tonumber(ARGV[1]) then return 0 end -- reject: 429
return 1 -- allow- Race conditions: two servers read “99”, both allow, both write “100”: one request slipped through. Use atomic commands (
INCR) or run the whole read-check-write as one Lua script. - Latency: keep Redis close to the servers (same data centre). For extreme scale, servers can batch counts locally and sync every few hundred milliseconds, trading exactness for speed.
- Scale Redis: shard keys across nodes by client ID; add replicas for failover.
- Failure: if Redis is unreachable, fail open (allow and alert) for most APIs; fail closed for sensitive actions like login or payments.
- Rules config: store rules (endpoint, limit, window, per what) in config, cached in each server and reloaded on change.
- Layers: real systems combine limits: per IP at the edge (stops floods early), per user or API key at the gateway, and per expensive endpoint (search, login) in the service.
🧠 PATH memory card
Remember the rate limiter design for good
Picture it · Anchor it · Trace it · Hit-recall it. Four quick steps that turn “I read it once” into “I can explain it in an exam”.
- P
Picture it
Your brain remembers scenes far better than definitions.
← swipe to see the whole picture →
Hostel mess coupons: your wallet holds at most 3, the warden adds one every hour, every plate costs one coupon, and with no coupon left you're turned away. Save up and you can have a feast, but over a whole day you can't beat the refill rate.
- A
Anchor it
A silly sentence you can't forget, where every word maps to the concept.
“Coupons drip in, plates spend them, no coupon = 429”
- Wallet of 3→Bucket capacity = biggest allowed burst
- Drip in→Refill rate = long-run average limit
- Plate→One request spends one token
- No coupon = 429→Reject with Too Many Requests + Retry-After
- Shared register→Redis: one count for all servers, updated atomically
- T
Trace it
Run it by hand on a tiny example once. Doing beats reading.
Capacity 3, refill 1/second, bucket full at t=0. Requests at t=0, 0, 0, 0 → ✓ ✓ ✓ ✗ (3 tokens spent, 4th finds 0). At t=1: 1 token dripped back → request ✓, another at t=1 → ✗. At t=5: bucket refilled to 3 (never above capacity) → three quick requests all pass. - H
Hit-recall it
Test yourself now, then again on the day each card comes back.
Card 1 / 8 · new0 mastered · 0 practisedSay the answer out loud first, then flip and be honest.
Follow-up questions interviewers ask
- “Limit by IP or by user?” Both: IP for anonymous traffic and floods (but many users share one IP behind college or office Wi-Fi), user or API key once logged in.
- “Rejected requests: drop or queue?” APIs usually reject with 429. Background jobs can be queued and retried later.
- “Different limits for free vs paid plans?” Look up the client's plan, then pick the rule. Cache plans to avoid a database call per request.
- “Multiple regions?” Keep counts per region (simple, slightly generous) or sync between regions (accurate, slower).
Where to go next
The rate limiter kept its counters in Redis. Next, open that box and design the cache itself, including the trick that decides which server holds each key: design a distributed cache.
Key takeaways
- ✓A rate limiter caps requests per client per time window and returns HTTP 429 with Retry-After.
- ✓Token bucket: capacity = burst, refill rate = average. The most common interview answer.
- ✓Fixed windows leak up to 2× at boundaries; sliding windows fix it.
- ✓With many servers, store counts in Redis and update them atomically (INCR or Lua).
- ✓Decide failure behaviour: fail open for most APIs, fail closed for sensitive ones.
Frequently asked questions
What is a rate limiter?
A rate limiter controls how many requests a user, IP address or API key can make in a period of time, for example 100 requests per minute. Requests over the limit are rejected, usually with HTTP 429 Too Many Requests. It protects servers from overload and abuse (bots, brute-force logins, scraping) and keeps the service fair for everyone.
How does the token bucket algorithm work?
A bucket holds up to N tokens and is refilled at a fixed rate, for example 1 token per second. Each request takes one token; if the bucket is empty, the request is rejected. The capacity sets the largest burst allowed, and the refill rate sets the long-term average. It is simple, memory-efficient (two numbers per user) and widely used in real APIs.
What is the difference between token bucket and leaky bucket?
A token bucket allows bursts: if tokens have saved up, many requests can pass at once. A leaky bucket puts requests in a queue that is processed at a constant rate, so output is perfectly smooth but bursts wait in line or are dropped when the queue is full. Token bucket suits APIs; leaky bucket suits systems that need a steady outflow.
How do you build a distributed rate limiter?
Keep the counters in a shared, fast store like Redis instead of each server's memory, so every server sees the same count. Use atomic operations (INCR with EXPIRE, or a Lua script for token bucket) to avoid race conditions when two servers update the same key at once. For very high traffic, shard the keys across Redis nodes and accept slightly approximate limits.
What HTTP status code is used for rate limiting?
HTTP 429 Too Many Requests. Good APIs also send headers that tell the client what's going on: the limit, how many requests remain, and when to try again (Retry-After). Many use names like X-RateLimit-Limit and X-RateLimit-Remaining, and there is an IETF draft standardising RateLimit headers.
🧠 Quick check: rate limiter
1. A token bucket has capacity 10 and refills 1 token per second. It's full. How many requests can pass instantly?
2. What's the weakness of a fixed-window counter (10 per minute)?
3. You run 20 API servers. Why not keep each user's counter in each server's memory?
4. Redis is down. Your rate limiter protects a public read-only API. A reasonable default?
Checking your access…