Rate Limiting Algorithms
On this page
A free user writes a script that calls your search API 300 times a second. Search shares the database with checkout, so checkout slows down for everyone. You add a rule, "100 requests per minute per user", but now you have to decide how to count. Count per calendar minute and the script sends 100 at 12:00:59 and 100 more at 12:01:01, 200 requests in two seconds, both "allowed". Count too strictly and a real user who opens five tabs at once gets blocked.
How you count decides what the limit actually means. These counting methods are the rate limiting algorithms.
How it works
Fixed window counter
Keep one counter per user per window: rl:u42:12:01. Increment it on each request (INCR, with a TTL of one window). If it exceeds the limit, reject.

It is one counter and one atomic increment, very cheap. The flaw is the boundary burst: a client can send the full limit at the end of one window and again at the start of the next.
Sliding window log
Store the timestamp of every request (a Redis sorted set per user). On each request, remove timestamps older than 60 seconds, count what is left, and allow if under the limit. Exact, but memory grows with the limit: 1,000 requests per minute means up to 1,000 timestamps per user.
Sliding window counter
Keep the fixed-window counters, but estimate the last 60 seconds as:
estimate = current_window_count + previous_window_count × (fraction of previous window still inside the last 60 s)
At 12:01:15, 75% of the previous minute is still inside the last 60 seconds, so 100 requests there count as 75. Two counters per user, close to exact, no boundary burst. A good default when you want "N per minute" to mean what it says.
Token bucket

Each user has a bucket that holds up to capacity tokens and refills at rate tokens per second. Each request takes one token; with no token left, the request is rejected.
You do not need a timer to refill. Store tokens and last_refill per key, and on each request compute:
tokens = min(capacity, tokens + (now - last_refill) × rate)
then take a token if one is there. Two numbers per user, and two knobs that match product language: "10 requests per second on average, bursts up to 20". This is why token bucket is the most common choice for public APIs.
Leaky bucket is the mirror image: requests enter a queue that drains at a fixed rate, which smooths output to a steady flow. It is useful in front of something that needs a constant rate (a third-party API, a payment processor).
Where it runs
- Usually at the API gateway, keyed by user ID, API key or IP, so rejected requests never reach the services.
- Counters live in a shared store (Redis) so all gateway instances see the same count. Read, compute and write must be atomic, done in a Lua script or a single command, or two gateways will both allow the last token.
- A rejected request gets
429 Too Many RequestswithRetry-Afterand, ideally,X-RateLimit-Remainingheaders so well-behaved clients slow down.
Trade-offs and costs
| Algorithm | Memory per key | Accuracy | Bursts |
|---|---|---|---|
| Fixed window | 1 counter | Up to 2× at boundaries | Uncontrolled at the boundary |
| Sliding log | 1 entry per request | Exact | None beyond the limit |
| Sliding counter | 2 counters | Close to exact | Smooth |
| Token bucket | 2 numbers | Exact for its model | Up to capacity, by design |
- A shared counter store adds about 1 ms per request and becomes a dependency. If it fails, you choose: fail open (allow everything, protect availability) or fail closed (reject, protect the backend). Many systems fail open with a local in-memory fallback limit.
- Hot keys: one abusive key hammers one Redis shard. Local pre-filtering per gateway helps.
- Distributed accuracy vs cost: exact global counts cost a round trip per request; local counters synced every few hundred milliseconds are cheaper but slightly loose.
When to reach for it
- Public APIs, per API key and per plan (free vs paid).
- Login and password-reset endpoints, per IP and per account, to slow brute force.
- Expensive endpoints (search, exports, LLM calls), often with a lower limit than the rest.
- Protecting a fragile downstream (a partner API that allows 50 calls per second): a leaky bucket or token bucket on your side.
Example
A public API for the course site. Assumptions: free plan 60 requests per minute with bursts of 20; paid plan 600 per minute with bursts of 100; 30,000 requests per second at peak across 12 gateway instances.
- Algorithm: token bucket per API key. Free: rate 1 per second, capacity 20. Paid: rate 10 per second, capacity 100.
- Storage: a Redis cluster, key
tb:{api_key}holdingtokensandlast_refill, with a TTL of a few minutes so idle keys disappear. A Lua script refills and takes a token in one atomic step. - Cost: 30,000 script calls per second across a 3-shard Redis cluster is comfortable, about 1 ms added per request.
- Login: a separate fixed-window limit of 5 attempts per 15 minutes per account and 50 per IP. Simplicity matters more than precision here.
- Failure policy: if Redis is unreachable, each gateway applies a local limit of 1/12 of the global rate per key and logs it. The API stays up; limits are approximate for a few minutes.
Common mistakes
- Fixed window without mentioning the boundary burst.
- Non-atomic read-then-write on the counter, so concurrent requests all pass.
- Rate limiting only by IP, which blocks whole offices behind one NAT and misses attackers with many IPs. Use user or API key where possible.
- Limiting inside each service instead of at the gateway, so rejected requests still cost work.
- No failure policy for the counter store.
- Returning 500 or 403 instead of 429 with Retry-After.
Say this in the interview
"I'll rate limit at the API gateway with a token bucket per API key: refill rate is the plan's average, capacity is the allowed burst. Tokens and last-refill time live in Redis and are updated in one Lua script, so concurrent gateways can't both take the last token. Over the limit returns 429 with Retry-After. If Redis is down, gateways fall back to a local per-instance limit, failing open, so the API stays available."
Used in
- API Gateway, Backpressure & Circuit Breaker, TTL, Expiration & Cleanup.
- Design a Rate Limiter, Design Quota Service, Design Rate Limiter for VM Bandwidth.