Rate Limiting

Every public endpoint is one badly written client away from an outage. Rate limiting caps what any single caller can consume, so one caller's retry loop does not become everyone's downtime — and so a paying tier can be protected from a free one.

A token bucket rate limiter: capacity 100, refill 10 per second100%−+FitSVGEsc

Scroll to zoom · drag to pan · 0 fits · Esc closes

What it does, and where it runs

A rate limiter restricts how many requests one identity may make inside a time window: API key first, user ID second, IP last — everyone behind one NAT shares an address, so an IP limit punishes an office and misses a distributed abuser. It buys capacity no caller can exhaust, a floor under brute-force and scraping, and sellable quota tiers.

Where the check runs decides what it protects. The API gateway is the usual answer: it knows the caller, so a rejected request never reaches service code. A load balancer counts per instance, middleware is rewritten in every service, and a dedicated limiter keeps one counter store — usually a shared cache like Redis.

Counting algorithms

Memory figures assume Redis, where a key costs roughly 100 bytes once the key name, its expiry and hash-table overhead are counted — the integer inside is a rounding error. Count keys and entries, not integers.

Algorithm	Burst behaviour	Cost per million active keys
Token bucket	Capacity is the burst allowance, refill the sustained rate	1 key, ~100 MB
Leaky bucket	Output perfectly smooth; bursts delayed, not absorbed	1 key plus its queue
Fixed window counter	Admits 2× the limit across a boundary: 100 in one minute's last second, 100 in the next minute's first	1 key, ~100 MB
Sliding window log	Exact, no boundary effect	100 entries/key at a 100/min limit, ~100 bytes each: 10 KB/key, ~10 GB, 100× a counter
Sliding window counter	Error bounded by the previous window's count, assumed evenly spread; the usual choice	2 keys, 2 expiries, ~200 MB

The counter is shared mutable state, so the update has to be indivisible. GET, compare, SET loses updates: two servers read 99 against a limit of 100, both admit, both write 100. An atomic increment settles read, decision and write in one round trip; design a distributed rate limiter works that out across a fleet.

Where the number comes from

A limit picked because it sounds round protects nothing; derive it from the capacity behind it.

Assume each API request costs two queries against a commodity Postgres box, which handles roughly 5,000 simple QPS. The datastore ceiling is 5,000 ÷ 2 = 2,500 API QPS. Reserve about 30% for retries and background jobs, and the budget is roughly 1,750 QPS, or 105,000 requests per minute. With 200 tenants active in a minute, an equal share is 105,000 ÷ 200 = 525 each — which is where "500 a minute" comes from, not taste.

The split holds only while its assumption does: 400 active tenants at 525 each is 210,000 requests/minute, about 3,500 QPS — twice the budget, every tenant inside its limit. A per-key limit bounds one caller and says nothing about the sum, so protection needs a second gate that counts everything: a global limit, or a concurrency cap in front of the datastore.

Little's Law sizes that cap, provided you feed it the query rate, not the request rate. Assume a simple query holds its connection for roughly 10 ms — sanity-check it against the box: 5,000 QPS × 0.01 s = 50 queries at once is the right order for a commodity server, where 200 would not be. Queries arrive at twice the request rate, so 3,500 QPS × 0.01 s = 35 in flight, and a pool of 35 holds the same ceiling from the other side: 35 ÷ 0.01 s = 3,500 queries per second is 1,750 API requests per second.

Rejecting has to be cheap and actionable

Over quota returns 429 Too Many Requests, not 503, which says the service is broken and which retry logic treats as immediately retryable. Send Retry-After on rejections and the limit, remaining and reset headers on every response — a client that sees 4 of 1,000 calls remaining slows itself down; one that first learns at the 429 has already sent the burst.

A limiter that does real work on the reject path amplifies the traffic it absorbs. If deciding a 429 costs one lookup of the caller's plan, 20,000 QPS of abuse becomes 20,000 QPS against a database whose ceiling is 5,000 — the limiter takes down the service it protects. Rules belong in memory on every gateway node, so rejecting costs a counter increment.

Ten thousand clients rejected against the same fixed window learn the same reset instant, and the boundary becomes a spike larger than the traffic just refused. Treat Retry-After as a floor, and size the jitter against the herd rather than against the wait. A random 0–30% on top of the diagram's Retry-After: 2 spreads 10,000 clients over 600 ms — 16,000 QPS of retry, the spike you meant to remove. Work back from the rate you can absorb: 10,000 retries at 1,000 QPS need a 10-second window, so add a uniform random 0–10 s. Percentage jitter is enough only when the retry window is long relative to the burst. When repeated 429s mean your own dependency is unwell, stop calling: a circuit breaker, not a retry policy.

In an interview

What is tested is whether rate limiting is a design decision for you: which identity you count on, where the check runs, and what the number is and why.

Say them in that order. "Per API key, falling back to user ID, IP only as a last resort. The check goes at the API gateway. Token bucket, capacity 100, refill 10 a second: 600 a minute sustained with a burst of 100. Over quota returns 429 with Retry-After, and limit/remaining/reset headers on every response." Then volunteer the store's failure: fail open onto a small per-server limit when guarding capacity, fail closed on login, where unlimited password attempts are a security incident.

The mistake that loses points is presenting a per-key limit as protection for the backend — the interviewer only has to ask what happens when every tenant sits at its limit.

Check yourself

1. A partner contract says 600 requests/minute, and their client wakes once an hour to push a batch. Choose capacity and refill rate for a token bucket.

Refill is fixed by the contract: 600 ÷ 60 = 10 tokens per second. Capacity is the real decision, and it bounds instantaneous concurrency, not rate: C = 600 landing inside a window shorter than the 50 ms handler puts 600 requests in flight at once — an outage against a 50-thread pool as much as a 10-thread one. Little's Law does not rescue that case: it needs an arrival rate over a stable window, and a minute's quota landing in one instant is a count, not a rate. Spread the same 600 over a full second and the law applies again: 600 QPS × 0.05 s = 30 concurrent, comfortable against 50 threads. Size C at what the pool can hold: C = 25 against 50 threads leaves half for other callers and drains the rest at 10/s.

2. Your gateway limits 100/minute per key with a fixed window, downstream is provisioned for 3,000 QPS, and the steady peak is 2,000. Keep fixed window?

Move, or offset the windows. Fixed window admits up to 2× the limit across a boundary, and because the window is truncated wall-clock time every key's boundary falls on the same instant — so the spike is aggregate: roughly 4,000 QPS against 3,000 of capacity. The sliding window counter removes it for 200 MB per million keys instead of 100 MB; the cheaper fix offsets each key's window start by a hash of the key.