Design a rate limiter for a public API that allows each user at most 100 requests per minute. Which algorithm would you use, where would the limiter run, and how do you make it work when the API runs on many servers?
Show hints
Compare token bucket with fixed and sliding windows.
Show the explanation
Model answer.
Requirements: limit per user (API key, or IP for anonymous traffic); low latency, since it runs on every request; work across many servers; over the limit, return HTTP 429 Too Many Requests with a Retry-After header.
Algorithm options
- Fixed window counter: count requests in each calendar minute and reject after 100. Simple, but a user can send 100 requests at 12:00:59 and 100 more at 12:01:00 — 200 in about two seconds at the window boundary.
- Sliding window log: store each request's timestamp and count those in the last 60 seconds. Accurate, but memory grows with the request rate.
- Sliding window counter: estimate using the current and previous window counts weighted by overlap. Good accuracy with constant memory.
- Token bucket: each user has a bucket with capacity b tokens, refilled at r tokens per second; each request consumes one token, and an empty bucket means rejection. It allows controlled bursts up to b while enforcing the average rate. For 100/minute, r ≈ 1.67 tokens/s with b = 100 (or a smaller b to limit bursts).
- Leaky bucket: requests drain from a queue at a constant rate, smoothing output. Token bucket is a strong default.
Where it runs
In the API gateway or a middleware layer in front of the services, so requests are rejected before they consume backend resources.
Distributed design
- Keep counters in a shared, fast store such as Redis, keyed like
rl:{userId}. - Updates must be atomic: use
INCRwithEXPIREfor window counters, or a Lua script that reads tokens, refills based on elapsed time and decrements in one step for a token bucket. Otherwise two servers can read the same value concurrently and both allow a request.
Operational decisions
- Fail open vs fail closed: if Redis is unavailable, allowing traffic keeps the API usable; rejecting it protects the backend. Most public APIs fail open.
- Expose remaining-quota headers; configure different limits per tier (free vs paid).
Common follow-up: "How does a client handle 429s?" Retry after the indicated delay with exponential backoff and jitter.
Original UniCircle question. Last reviewed 28 Oct 2026.