Rate limiting
How to cap requests per user with token buckets, leaky buckets and sliding windows, enforce limits across many servers with Redis and Lua, and reply with 429s clients can use.
On this page
- The problem: one client can ruin it for everyone
- The idea: a counter per key, checked before the work
- How it works: the five algorithms
- A token bucket in code
- Rate limiting across many servers
- Where to enforce the limit
- Telling the client what happened
- Where this breaks
- When not to use it
- In the interview
- Quiz
The problem: one client can ruin it for everyone
Your public API can handle about 2,000 requests per second, and normal traffic is 1,200. Then, in the same week:
- A customer's app release retries every failed call in a tight loop: 40,000 phones now send 5 requests per second each.
- A scraper on a few hundred cloud machines downloads your whole catalogue as fast as it can.
- Someone tries 10 million leaked passwords against your login endpoint.
Each of these alone uses more capacity than you have. The servers cannot tell which requests are "fair", so they slow down for everybody, and your best customers see timeouts because of someone else's bug.
One noisy client overloads the API, and a limiter in front stops it
- Most users send a few requests a minute. But one buggy script, scraper or attacker can send thousands a second, and slow the service down for everybody.
- A rate limit caps how many requests each user, key or IP address may send, for example 10 per second. Requests over the limit are rejected straight away with status 429, Too Many Requests.
A rate limiter counts how many requests each client has sent recently and rejects the ones over an agreed limit, straight away and cheaply, before they reach the expensive parts of the system. The rejected client gets HTTP 429 Too Many Requests. Everyone else carries on as normal.
The idea: a counter per key, checked before the work
Every rate limiter answers one question per request: has this key used up its allowance? Three choices define it.
- The key: who is being limited. An API key, a user ID, an IP address, or a combination such as
user:42:POST /orders. - The limit: how many requests over what period, and how much bursting is allowed. "100 per minute, bursts of 20".
- The action: reject with 429 (the usual), queue the request until it can run, or just log it ("shadow mode", useful when you introduce a new limit and want to see who it would hit).
Limits serve several purposes, and it helps to say which one you are designing for:
| Purpose | Example limit | Key |
|---|---|---|
| Protect capacity | 1,000 requests/s per API key | API key |
| Fairness between tenants | Free plan 60/min, paid plan 6,000/min | Account and plan |
| Stop abuse | 5 failed logins per account per 15 min | Account, and separately IP |
| Control cost | 20 SMS verification codes per phone number per day | Phone number |
| Protect a fragile dependency | 50 calls/s to a partner's API | Destination |
Choosing the key is harder than it looks. IP address is the only option before login, but many people share one IP (offices, universities, mobile carriers using carrier-grade NAT), while one attacker can rotate through thousands. Account or API key is fairer and harder to dodge, so use it whenever the request is authenticated, and keep per-IP limits generous.
How it works: the five algorithms
All five keep a little state per key and decide in constant time. They differ in how they treat bursts and how much memory they use.
Fixed window counter
Split time into windows (each minute, say) and keep one counter per key per window. Increment it on each request; reject once it passes the limit. The key can include the window number, rl:42:28736541, and expire shortly after the window ends.
A fixed window lets a burst through at the boundary
- The simplest method is a fixed window: count requests in each one-second window, and refuse once the count hits the limit. Easy, but a client can squeeze two windows’ worth of requests around the boundary.
It is the cheapest option (one integer per key), but with a limit of 100 per minute a client can send 100 requests at 12:00:59.9 and another 100 at 12:01:00.0: 200 requests in a fraction of a second, all allowed, because they fall in two windows. A fixed window can let through twice the limit in a short burst.
Sliding window log
Store the timestamp of every accepted request per key, for example in a Redis sorted set. On each request, drop timestamps older than the window, count what is left, and accept if the count is under the limit.
This is exact: at no moment does any 60-second span contain more than 100 accepted requests. The cost is memory. A limit of 1,000 per hour means storing up to 1,000 timestamps per key; at roughly 60–80 bytes per sorted-set entry in Redis, one million active keys need tens of gigabytes. Use it when limits are small (5 logins per 15 minutes) or exactness matters.
Sliding window counter
A clever middle ground: keep the fixed-window counters for the current and previous window, and estimate the count over the last full window by weighting the previous one by how much of it still overlaps.
Worked example. Limit 100 per minute. The previous minute had 80 requests; this minute has had 30 so far, and we are 15 seconds (25%) into it. The sliding minute still overlaps the last 75% of the previous window:
estimate = 30 + 80 × 0.75 = 90 → under 100, allow.
The estimate assumes the previous window's requests were spread evenly, so it can be slightly off when they were bunched, but it removes the 2× boundary burst, needs only two counters per key, and is accurate in practice: Cloudflare reported that only about 0.003% of requests were wrongly allowed or limited when it measured this approach on real traffic.
Token bucket
Each key has a bucket holding at most B tokens (the burst size) that refills at r tokens per second. A request takes a token; if the bucket is empty it is rejected. You do not need a timer to add tokens: store the token count and the time of the last update, and on each request add (now − last) × r, capped at B.
A token bucket saves up tokens, so short bursts are fine
- A token bucket is smoother. Each user has a bucket that refills with tokens at a steady rate, say 2 per second, and holds at most, say, 6. Each request spends a token. Short bursts are fine; sustained floods are not.
Worked example. r = 10 per second, B = 20. A client that has been quiet can send 20 requests instantly, then 10 per second after that. Over any 60 seconds it can send at most 20 + 60 × 10 = 620 requests: the long-run rate is capped by r and the burst by B, and you tune them separately. That is why it is the most widely used algorithm: AWS API Gateway and Stripe describe their limits as token buckets.
A useful extension is cost: an expensive call (a search, a bulk export) can take 5 tokens instead of 1.
Leaky bucket
The name is used for two slightly different things, and interviewers may mean either:
- As a queue: requests join a FIFO queue of size B and leave at a fixed rate r. Output is perfectly smooth, which suits a fragile downstream system, but requests wait (latency).
- As a meter: the bucket "drains" at rate r, each request adds one unit, and a request that would overflow B is rejected. This is mathematically the mirror image of a token bucket. NGINX's
limit_reqworks this way (with aburstparameter), and GCRA (the generic cell rate algorithm) is a compact version that stores a single timestamp per key: the "theoretical arrival time" of the next allowed request.
Comparing them
| Algorithm | State per key | Bursts | Accuracy | Use when |
|---|---|---|---|---|
| Fixed window | 1 counter | Up to 2× the limit at a boundary | Rough | Daily quotas, cheap coarse limits |
| Sliding window log | 1 timestamp per request | None beyond the limit | Exact | Small limits that must be exact (logins, OTPs) |
| Sliding window counter | 2 counters | Smoothed | Very close | Large per-minute limits at scale |
| Token bucket | Tokens + timestamp | Allowed up to B, tunable | Exact for its model | The default for API limits |
| Leaky bucket (queue) | A queue | Absorbed, then released steadily | Exact | Smoothing traffic into a fragile consumer |
A token bucket in code
On one server, a token bucket is a few lines. The bucket refills lazily when it is checked.
public final class TokenBucket {
private final double capacity; // B: the biggest burst
private final double refillPerSec; // r: the long-run rate
private double tokens;
private long lastNanos;
public TokenBucket(double capacity, double refillPerSec) {
this.capacity = capacity;
this.refillPerSec = refillPerSec;
this.tokens = capacity; // start full
this.lastNanos = System.nanoTime();
}
public synchronized boolean tryAcquire(double cost) {
long now = System.nanoTime();
double elapsed = (now - lastNanos) / 1e9;
tokens = Math.min(capacity, tokens + elapsed * refillPerSec);
lastNanos = now;
if (tokens >= cost) {
tokens -= cost;
return true;
}
return false;
}
/** Seconds until `cost` tokens will be available: the value for Retry-After. */
public synchronized double secondsUntil(double cost) {
return Math.max(0, (cost - tokens) / refillPerSec);
}
}
// one bucket per key, created on first use
ConcurrentHashMap<String, TokenBucket> buckets = new ConcurrentHashMap<>();
boolean ok = buckets.computeIfAbsent(apiKey, k -> new TokenBucket(20, 10)).tryAcquire(1);import threading
import time
class TokenBucket:
def __init__(self, capacity: float, refill_per_sec: float):
self.capacity = capacity # B: the biggest burst
self.refill_per_sec = refill_per_sec # r: the long-run rate
self.tokens = capacity # start full
self.last = time.monotonic()
self.lock = threading.Lock()
def try_acquire(self, cost: float = 1) -> bool:
with self.lock:
now = time.monotonic()
self.tokens = min(self.capacity, self.tokens + (now - self.last) * self.refill_per_sec)
self.last = now
if self.tokens >= cost:
self.tokens -= cost
return True
return False
def seconds_until(self, cost: float = 1) -> float:
"""Seconds until `cost` tokens are available: the value for Retry-After."""
with self.lock:
return max(0.0, (cost - self.tokens) / self.refill_per_sec)
buckets: dict[str, TokenBucket] = {}
bucket = buckets.setdefault(api_key, TokenBucket(capacity=20, refill_per_sec=10))
ok = bucket.try_acquire()Two details matter. Use a monotonic clock (nanoTime, time.monotonic), not wall-clock time, so a clock adjustment cannot hand out or take away tokens. And a map of buckets for every key ever seen grows forever; in production, evict idle buckets (a full bucket is the same as no bucket, so dropping it loses nothing).
Rate limiting across many servers
The in-memory version breaks as soon as you have more than one API server. With 10 servers behind a load balancer, each one sees about a tenth of a client's requests, so a limit of 100 per minute per server lets the client send 1,000. You have three options.
| Option | How | Good at | Weak at |
|---|---|---|---|
| Local limit ÷ N | Each of N servers allows limit/N | No network call, no shared state | Wrong when traffic is uneven or N changes; useless for small limits |
| Central store (Redis) | Every server checks a shared counter | Accurate global limit | +0.2–0.5 ms per request; Redis must be highly available |
| Local + periodic sync | Servers count locally and push deltas every second or so | Cheap and close to accurate | Can overshoot by up to one sync interval of traffic |
The usual interview answer is Redis, because it is fast (about 100,000+ operations per second per node), supports expiring keys, and runs commands one at a time on each shard.
The race: check-then-set is not atomic
The obvious Redis code reads the count, compares it, then writes it back. With two API servers that is a race:
- Server A reads
count = 99. Server B readscount = 99. - Both decide 99 < 100 and allow the request.
- Both write
100. Two requests were allowed, but the counter only went up by one.
Under load this happens constantly, so the limit leaks. The fix is to make the read, decision and write one atomic step. For a fixed window, INCR already is one (it returns the new value, and you reject if it is over the limit). For a token bucket or sliding window, which need several commands, run them in a Lua script: Redis executes a script from start to finish without running any other command in between.
-- KEYS[1] = bucket key, e.g. "rl:{apikey_42}"
-- ARGV[1] = refill rate (tokens/s), ARGV[2] = capacity, ARGV[3] = cost
local rate = tonumber(ARGV[1])
local capacity = tonumber(ARGV[2])
local cost = tonumber(ARGV[3])
local t = redis.call('TIME') -- Redis's clock, same for every app server
local now = tonumber(t[1]) + tonumber(t[2]) / 1000000
local state = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(state[1]) or capacity -- a new key starts full
local ts = tonumber(state[2]) or now
tokens = math.min(capacity, tokens + math.max(0, now - ts) * rate)
local allowed, retry_after = 0, 0
if tokens >= cost then
tokens = tokens - cost
allowed = 1
else
retry_after = (cost - tokens) / rate
end
redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('EXPIRE', KEYS[1], math.ceil(capacity / rate) + 1) -- idle keys clean themselves up
-- Lua numbers become integers when returned, so send the fractions as strings
return {allowed, tostring(tokens), tostring(retry_after)}
// Jedis; load the script once, then call it by its SHA on every request
String sha = jedis.scriptLoad(TOKEN_BUCKET_LUA);
List<Object> r = (List<Object>) jedis.evalsha(sha,
List.of("rl:{" + apiKey + "}"),
List.of("10", "20", "1")); // rate, capacity, cost
boolean allowed = ((Long) r.get(0)) == 1L;
double retryAfter = Double.parseDouble((String) r.get(2));import redis
r = redis.Redis()
token_bucket = r.register_script(TOKEN_BUCKET_LUA) # uses EVALSHA, falls back to EVAL
def check(api_key: str, rate=10, capacity=20, cost=1) -> tuple[bool, float]:
allowed, _tokens, retry_after = token_bucket(
keys=[f"rl:{{{api_key}}}"], args=[rate, capacity, cost])
return allowed == 1, float(retry_after)Using redis.call('TIME') means every app server uses the same clock, so skew between app servers cannot add or remove tokens. (Redis 5 and later replicate the script's writes rather than re-running it, which makes reading the time inside a script safe.) The braces in rl:{apikey_42} are a hash tag: in Redis Cluster, only the part inside braces decides the shard, so any other keys you add for the same client land on the same shard and can be used in one script.
A sliding window log in Redis
A sorted set per key, scored by time, does the sliding log. Run it as one script so the trim, count and add are atomic:
-- KEYS[1] = log key; ARGV[1] = window in ms; ARGV[2] = limit; ARGV[3] = unique request id
local t = redis.call('TIME')
local now = tonumber(t[1]) * 1000 + math.floor(tonumber(t[2]) / 1000)
local window = tonumber(ARGV[1])
redis.call('ZREMRANGEBYSCORE', KEYS[1], 0, now - window) -- forget old requests
if redis.call('ZCARD', KEYS[1]) < tonumber(ARGV[2]) then
redis.call('ZADD', KEYS[1], now, ARGV[3]) -- the id keeps same-ms requests distinct
redis.call('PEXPIRE', KEYS[1], window)
return 1
end
return 0
Only accepted requests are recorded, so a client hammering away while blocked does not extend its own ban. Some APIs deliberately do the opposite (record rejected requests too) to punish clients that ignore 429s.
Where to enforce the limit
Limits work best in layers, each stopping a different kind of traffic as early and cheaply as possible.
Limits usually live in the gateway, in front of every service
- Rate limits usually live in an API gateway or load balancer in front of everything, so bad traffic is stopped before it costs you anything. They protect your servers, keep things fair, and limit the damage from bugs and abuse.
| Layer | Limits on | Catches |
|---|---|---|
| Edge / CDN / WAF | IP address, country, request signature | Floods and crude bots before they reach your data centre |
| API gateway | API key, user, plan, endpoint | Per-customer quotas and fairness: the main place |
| Inside a service | Business keys (account, phone number, card) | Logins, OTPs, coupon abuse: rules that need business data |
| Before a dependency | Destination | Staying under a partner's quota or a fragile database's capacity |
| Client | Itself | Well-behaved SDKs that throttle themselves and honour Retry-After |
A gateway limit is generic; "5 failed logins per account in 15 minutes" needs to know whether the password was wrong, so it lives in the login service.
Telling the client what happened
A good rejection is fast, cheap and tells the client exactly what to do.
HTTP/1.1 429 Too Many Requests
Content-Type: application/json
Retry-After: 3
RateLimit-Policy: 100;w=60
RateLimit: limit=100, remaining=0, reset=3
{"error": "rate_limited", "message": "Limit of 100 requests per minute reached. Retry in 3 seconds."}
Retry-After (seconds, or an HTTP date) is the standard header. The RateLimit-* headers come from an IETF draft that is still evolving; many APIs use the older X-RateLimit-Limit, X-RateLimit-Remaining and X-RateLimit-Reset, as GitHub does. Sending the remaining allowance on successful responses too lets good clients slow down before they hit the wall.
Retry-After tells polite clients how long to wait
- Good limits also tell clients when to come back, with a Retry-After header. Well-behaved apps wait instead of hammering the server with instant retries.
Use 429 when one client exceeded its own limit, and 503 Service Unavailable (also with Retry-After) when the server itself is overloaded and shedding load from everyone (see circuit breakers and load shedding).
Clients that retry a 429 immediately make things worse, so client SDKs should honour Retry-After and otherwise back off exponentially with jitter (see timeouts, retries and circuit breakers).
Where this breaks
Two more to mention: a botnet of 100,000 IPs, each sending 2 requests a minute, never trips a per-IP limit (bot detection, CAPTCHAs and per-account limits are the other layers); and limits that are too tight hurt real users, so introduce new limits in shadow mode first and look at who would be blocked.
When not to use it
- Internal batch jobs talking to systems you control. A queue with a fixed number of consumers controls throughput more simply than a limiter.
- As your only overload protection. Per-client limits do not help when 50,000 well-behaved clients together exceed capacity. You also need autoscaling, load shedding and circuit breakers.
- Where waiting is better than refusing. For a job that must eventually run (sending invoices), queue it and drain at the allowed rate (a leaky bucket as a queue) rather than rejecting it.
In the interview
Your login endpoint is under a credential-stuffing attack: millions of leaked username and password pairs, sent from about 20,000 IP addresses, each IP trying a few passwords a minute. Normal users log in a few times a day. Design the rate limits: what keys, what limits, what algorithm, what response, and what else you would add.
Compare with our answer
- Per account: at most about 5 failed attempts per 15 minutes, using a sliding window log (small and exact). After that, slow down or require a CAPTCHA rather than locking the account outright, because a hard lockout lets an attacker lock real users out on purpose.
- Per IP: a generous limit (say 50 failures an hour), since many real users share IPs; it catches lazy attackers but not this one.
- Global signal: a jump in the overall login failure rate (2% to 60%) means an attack even if no single key trips a limit; respond with CAPTCHAs or extra checks for unfamiliar devices.
- Count failures, not attempts, so a user who types the password right is never limited.
- Respond the same way whether the account exists or not, so the limiter does not reveal valid usernames.
- Beyond limits: check passwords against known-breached lists, offer two-factor authentication, and use device fingerprints.
A strong answer mentions: per-account and per-IP keys and why each alone fails · failures counted rather than attempts · soft responses (CAPTCHA, delay) instead of hard lockout · a global failure-rate alarm for distributed attacks · not leaking which accounts exist.
A team implements a fixed window limit of 100 requests per minute like this. Users occasionally report being blocked "forever", and under load the limit lets through more than 100. Find both bugs and fix them.
def allow(user_id):
key = f"rl:{user_id}:{int(time.time() // 60)}"
count = int(r.get(key) or 0)
if count >= 100:
return False
r.set(key, count + 1)
if count == 0:
r.expire(key, 60)
return TrueCompare with our answer
Bug 1, lost updates: GET then SET is check-then-act. Two servers both read 99, both allow, both write 100. Use INCR, which increments atomically and returns the new value, and reject when it exceeds 100.
Bug 2, the key may never expire: the expiry is a separate command after the write. If the process crashes or times out between them, the key has no TTL. Here the window number in the key means a stuck key only blocks one old window, but the same pattern on a key without a window number (rl:{user_id}) really does block a user forever. Set the TTL in the same step.
def allow(user_id):
key = f"rl:{user_id}:{int(time.time() // 60)}"
pipe = r.pipeline(transaction=True) # MULTI/EXEC: both commands run together
pipe.incr(key)
pipe.expire(key, 120) # longer than the window; harmless to repeat
count, _ = pipe.execute()
return count <= 100
A strong answer mentions: the check-then-act race and INCR (or a Lua script) as the fix · the INCR/EXPIRE gap and setting both atomically · that rejected requests still increment the counter here (fine for a fixed window, but worth saying) · the boundary burst of up to 200 that remains · using the server's clock consistently (or Redis TIME) across app servers.
- Limit = key (API key, user, IP, account) + rate and burst + action (429, queue, or shadow-log).
- Fixed window: one counter, cheap, up to 2× bursts at the boundary. Sliding log: exact, one timestamp per request. Sliding counter: two counters,
current + previous × overlap, very close. - Token bucket: refill r/s, hold B; long-run rate r, burst B; 60 s max = B + 60r. The default for APIs.
- Leaky bucket: as a queue it smooths output (adds latency); as a meter it mirrors the token bucket (NGINX, GCRA).
- Many servers: shared state in Redis; make check-and-update atomic with
INCRor a Lua script; TTL on every key; hash tags in Redis Cluster. - Enforce in layers: edge (IP), gateway (API key, plan), service (business rules), before dependencies.
- Respond: 429 +
Retry-After+ remaining-quota headers; 503 for whole-server overload. Clients back off with jitter. - Failure plan: Redis down → fail open with local limit ÷ N; fail closed only for security limits. Per-region shares for multi-region.
1. A public API allows 100 requests per minute per key using a fixed window. A partner complains that a client sent 190 requests within two seconds without being limited. What is the most likely explanation?
A fixed window resets at the boundary, so up to twice the limit can pass in a short span around it. Per-server counters could also leak, but they would leak all the time, not specifically in a short burst. A sliding window or token bucket removes the boundary burst.
2. You need an API limit of 600 requests per minute on average, while letting a quiet client fire 50 requests at once when a page loads. Which configuration fits?
Refill rate sets the average (10/s = 600/min) and capacity sets the burst (50), tuned separately. The fixed window would allow 600 at once (and 1,200 around a boundary). The queue delays the page load instead of serving it. The 5-second log averages 600/min but caps sustained bursts oddly and costs a timestamp per request.
3. Ten API servers share a Redis-backed token bucket. Each server runs HGET to read the tokens, decides in application code, then runs HSET with the new value. What goes wrong under load?
Read-decide-write in separate commands is a race: concurrent requests read the same state and overwrite each other's updates. A Lua script runs the read, refill and write atomically on the Redis shard. Clock skew is a real but smaller issue, which Redis TIME inside the script also fixes.
4. A limit of 1,000 requests per hour per user must be exact, and you have 2 million active users. Which concern is the strongest argument against a sliding window log?
The log keeps a timestamp per accepted request: up to 1,000 per user × 2 M users, tens of gigabytes in Redis. A sliding window counter (two integers per user) is the usual compromise. The log is exact, has no boundary burst, and works fine in a Lua script.
5. The Redis cluster behind your API gateway's rate limiter becomes unreachable. For the general per-key API limit, what is the best behaviour?
Failing closed turns a limiter outage into a full outage, and queuing exhausts gateway memory. A local fallback keeps rough protection without a dependency. Security-critical limits such as OTP sends may reasonably fail closed instead.
6. An endpoint is rate limited per IP address at 60 requests per minute. Users at a large university and on one mobile carrier report being blocked constantly, while a scraper still gets through. What change helps most?
Many people share one IP behind NAT, and scrapers rotate through many IPs, so IP is a poor key whenever a better identity exists. A token bucket or CDN placement changes the shape or location of the limit but keeps the wrong key.
7. A client exceeds its quota. What should the response look like?
429 says "you, specifically, are over your limit", and Retry-After tells a well-behaved client when to come back. 503 means the server is overloaded for everyone; 403 means not allowed at all; a fake 200 hides the problem and breaks clients.
Score 60% or more and the lesson is marked complete.