Rate Limiting
Token bucket vs sliding window, where to enforce limits, how to keep counters correct across servers with Redis, and what a good 429 response looks like.
A rate limiter bounds how many requests a key (a user, an API token, an IP) may make per unit of time, and rejects the rest with 429 Too Many Requests. The algorithm decides how bursts are treated and how much memory each key costs; the storage decides whether the limit holds across many servers. Get the key, the algorithm and the response contract right and the limiter protects you without punishing normal users.
Why it matters
Without a limiter, one misbehaving client, a retry storm, or a scraper decides your database load and your cloud bill. With a badly designed one, legitimate users get blocked at window boundaries, mobile users behind carrier NAT share one IP and one limit, and a Redis hiccup takes the whole API down. It is a small component with a large blast radius in both directions.
The algorithms, and the burst problem
All algorithms answer one question, "has this key exceeded R requests per T seconds?", but differ in how they treat a burst that straddles the boundary of T.
| Algorithm | Burst behaviour | Memory per key | Notes |
|---|---|---|---|
| Fixed window | Up to 2R at a boundary | 1 counter | Simplest; fine for coarse abuse limits |
| Sliding log | Exact | One timestamp per request | Accurate but O(R) memory; fine for small R |
| Sliding window counter | Approximately exact | 2 counters | Weights previous window by overlap; Cloudflare-style |
| Token bucket | Allows bursts up to bucket size, then steady rate | 2 numbers (tokens, last refill) | Most common for APIs; separate “burst” and “rate” knobs |
| Leaky bucket | Smooths output to a constant rate | queue or counter | What nginx limit_req implements; adds latency instead of rejecting |
Token bucket in detail
Each key owns a bucket holding up to capacity tokens. Tokens refill at rate per second; a request takes one token or is rejected if the bucket is empty. The bucket size is the permitted burst; the refill rate is the sustained limit. Nothing runs in the background: the refill is computed lazily from the time since the last request.
- 1
Read
(tokens, last)for the key; missing means a full bucket. - 2
tokens = min(capacity, tokens + (now − last) × rate). - 3
If
tokens ≥ 1: subtract one, store, allow. Else: store, reject with the time until the next token.
Steps 1 to 3 must be atomic: two app servers reading the same bucket at the same instant would both see one token and both allow. In Redis, a Lua script runs atomically on the server, so the read-modify-write cannot interleave.
-- KEYS[1] = bucket key
-- ARGV[1] = capacity, ARGV[2] = refill rate per second, ARGV[3] = now (ms)
local capacity = tonumber(ARGV[1])
local rate = tonumber(ARGV[2])
local now = tonumber(ARGV[3])
local state = redis.call('HMGET', KEYS[1], 'tokens', 'last')
local tokens = tonumber(state[1]) or capacity
local last = tonumber(state[2]) or now
tokens = math.min(capacity, tokens + (now - last) / 1000 * rate)
local allowed = 0
if tokens >= 1 then
tokens = tokens - 1
allowed = 1
end
redis.call('HSET', KEYS[1], 'tokens', tokens, 'last', now)
redis.call('PEXPIRE', KEYS[1], math.ceil(capacity / rate * 1000) + 1000)
return {allowed, tokens}app.use(async (req, res, next) => {
const key = `rl:${req.user?.id ?? req.ip}`;
const [allowed, tokens] = await redis.evalsha(
SHA, 1, key, 100, 10, Date.now(), // burst 100, 10 req/s sustained
);
res.setHeader('RateLimit-Limit', '100');
res.setHeader('RateLimit-Remaining', String(Math.floor(tokens)));
if (!allowed) {
res.setHeader('Retry-After', '1');
return res.status(429).json({error: 'rate_limited'});
}
next();
});Where to enforce, and on what key
Limits stack. The edge stops floods before they cost you compute and can key only on what it sees, mostly the IP. The gateway knows the route and the API key. The application knows the user and the action, so "5 password resets per hour per account" lives here. The closer to the expensive resource, the more specific the limit can be, and the more of the request's cost has already been paid.
Choose the key by what you are protecting against. Per-user limits protect fairness and quotas; per-IP limits protect against unauthenticated abuse but lump together everyone behind a corporate proxy or mobile carrier NAT; per-endpoint limits protect one costly operation without touching the rest. Real systems use two or three keys at once.
The response contract
| Element | Value | Why |
|---|---|---|
| Status | 429 Too Many Requests | Distinct from 503, so clients and dashboards treat it as “slow down”, not “outage” |
Retry-After | seconds until a token is available | Lets well-behaved clients wait exactly long enough instead of hammering |
RateLimit-Limit / -Remaining / -Reset | quota, what is left, when it resets | IETF draft headers; let clients pace themselves before hitting 429 |
| Body | machine-readable error code | So SDKs can branch on it |
Distributed limiters: consistency and failure
An in-memory counter per app server gives each server its own limit, so a client spread across 8 servers gets 8× the quota. That is acceptable for coarse protection and wrong for billing quotas. A shared store (Redis) makes the limit global at the cost of one round trip per request, which is why the operation must be a single atomic command or script, never GET then SET.
Then decide the failure mode. Fail open (allow when Redis is unreachable) keeps the product up and accepts a window of unlimited traffic; fail closed protects the backend and turns a cache outage into an API outage. Most public APIs fail open with an alert, and fail closed only on the endpoints where abuse is expensive, like sign-up or SMS sending.
Pitfalls
- Keying on X-Forwarded-For without trusting only your proxy
The header is client-controlled; a caller can put any IP in it and rotate freely. Take the IP the trusted proxy appended (rightmost entry it added), never the leftmost, and behind a CDN use the header the CDN sets for the real client.
- Counting after the expensive work
A limiter placed after authentication, body parsing and a database lookup has already spent most of the request's cost. Check the limit as early as the key is known, and put unauthenticated limits before auth entirely.
- One limit for every endpoint
A global 1000/min lets a client spend all of it on the slowest report endpoint. Weight requests by cost, or give expensive endpoints their own bucket with a smaller capacity.
- No Retry-After, or a 503 instead of a 429
Clients without Retry-After guess, and usually guess short. A 503 makes monitoring count throttling as downtime and makes SDKs retry immediately. Send 429 with a concrete wait.
- Failing closed on the whole API when Redis blips
If every request needs Redis to be allowed, a 2-second Redis failover is a 2-second full outage. Fail open by default with a short local fallback limiter and an alert, and fail closed only where abuse costs real money.
Interview questions
Q1Design a rate limiter for a public API. Walk me through it.
Key on API token for authenticated calls and IP for the rest, enforce at the gateway before auth-heavy work, use a token bucket so clients get a burst allowance plus a sustained rate, and store buckets in Redis updated by an atomic Lua script so the limit is global across servers. Respond 429 with Retry-After and RateLimit-* headers, fail open with an alert if Redis is unreachable, and give expensive endpoints their own smaller buckets.
Q2Fixed window vs sliding window vs token bucket: what is the difference?
Fixed window counts per calendar interval and allows up to double the limit at a boundary; sliding window counts the trailing interval and removes that burst, either exactly with a log of timestamps or approximately with two counters; token bucket refills continuously and lets you configure burst size and sustained rate separately, which is why most APIs use it. Leaky bucket is the queueing variant that smooths rather than rejects.
Q3Why must the counter update be atomic, and how do you get that in Redis?
Two servers reading the same bucket concurrently would both see a token available and both allow, so the limit leaks under exactly the load it exists for. Redis executes a single command or a Lua script atomically, so putting the read, refill, decrement and write in one EVAL removes the race without any external lock.
Q4What happens when Redis goes down?
It is a policy choice. Fail open keeps the API serving with no global limit, which I would default to for most endpoints, backed by a small per-process limiter and an alert. Fail closed rejects everything, which I would reserve for endpoints where unlimited traffic costs money or enables abuse, like sending SMS or creating accounts.
Q5How should a client behave when it receives a 429?
Stop sending, wait at least Retry-After seconds plus random jitter, then retry with exponential backoff and a cap on attempts. Reads can be retried freely; writes should carry an idempotency key so the retry cannot duplicate the side effect. Good SDKs also read RateLimit-Remaining to slow down before the first 429.
Q6What is wrong with limiting by IP address?
Many users share one IP behind corporate proxies and mobile carrier NAT, so a fair per-user limit becomes a per-office limit, while a single abuser can rotate through many IPs. It is useful as a coarse first layer against unauthenticated floods, not as the primary key; authenticated traffic should be keyed on the account or token.
Q7Where in the request path would you put the limiter and why?
As early as the key is known: at the CDN for IP-based flood protection, at the gateway for per-token limits, and in the application only for limits that depend on user or action semantics. Every layer the request passes before being rejected is cost already spent, so the limiter should sit before authentication lookups and body parsing where possible.
- A limiter is a key, an algorithm, a store and a response contract; each is a separate decision.
- Fixed windows leak 2× at boundaries; sliding windows fix that; token buckets add a separate burst allowance and are the usual choice for APIs.
- Across servers the counter must live in a shared store and be updated atomically, in Redis via one command or a Lua script.
- Enforce as early as the key is known, and use several keys (IP, token, user, endpoint) rather than one global number.
- Reply 429 with Retry-After and RateLimit-* headers; clients back off with jitter and use idempotency keys on retried writes.
- Decide fail-open vs fail-closed per endpoint before Redis has its first outage.