Rate Limiting Algorithms and Distributed Throttling
Four algorithms, one correct default, and the hard part nobody mentions: enforcing a global limit across fifty servers without a round trip on every request.
Covers: Token bucket, leaky bucket, fixed and sliding windows, distributed counters, response headers, layered limits
Rate limiting protects you from abusive clients, buggy clients, and your own retry logic. It is also a favourite interview question because the algorithms are simple enough to implement on a whiteboard and the distributed version is genuinely hard.
30-second answer
Token bucket refills tokens at a fixed rate up to a capacity, so it enforces an average rate while allowing bursts up to the bucket size - that flexibility makes it the usual default for APIs. Leaky bucket drains at a constant rate, smoothing traffic completely, which suits downstream systems that cannot absorb bursts at all. Fixed window is the simplest and has a serious flaw: a client can send a full window's quota at the end of one window and again at the start of the next, achieving double the intended rate. Sliding window log is exact but stores a timestamp per request; sliding window counter approximates it cheaply and is the right choice when precision matters more than burst tolerance.
| Algorithm | Allows bursts | Memory per key | Accuracy | Best for |
|---|---|---|---|---|
| Token bucket | Yes, up to capacity | 2 numbers | Good | Public APIs - the usual default |
| Leaky bucket | No - output is perfectly smooth | 2 numbers | Good | Protecting a fragile downstream |
| Fixed window | Yes, 2× at boundaries | 1 counter | Poor | Rough internal limits only |
| Sliding window log | No | One timestamp per request | Exact | Low-volume, high-value limits |
| Sliding window counter | Slightly | 2 counters | Very good | High volume with accuracy needs |
class TokenBucket:
def __init__(self, capacity, refill_per_sec):
self.capacity, self.rate = capacity, refill_per_sec
self.tokens, self.updated = capacity, time.monotonic()
def allow(self, cost=1):
now = time.monotonic()
# Refill lazily on read - no timer, no background job.
self.tokens = min(self.capacity, self.tokens + (now - self.updated) * self.rate)
self.updated = now
if self.tokens >= cost:
self.tokens -= cost
return True
return False
# capacity=100, rate=10/s:
# sustained 10 req/s forever, or a burst of 100 then 10/s.
# 'cost' lets expensive endpoints consume more than one token - a neat touch
# that turns a request limiter into a rough capacity limiter.def sliding_window_allow(key, limit, window=60):
now = time.time()
cur_key = f"{key}:{int(now // window)}"
prev_key = f"{key}:{int(now // window) - 1}"
cur = int(redis.get(cur_key) or 0)
prev = int(redis.get(prev_key) or 0)
# Weight the previous window by how much of it still overlaps the last
# 'window' seconds. Smooths the boundary without storing per-request data.
overlap = 1.0 - (now % window) / window
estimated = prev * overlap + cur
if estimated >= limit:
return False
redis.incr(cur_key)
redis.expire(cur_key, window * 2)
return TrueThe hard part: distributed enforcement
One server enforcing 1,000 requests/minute is trivial. Fifty servers enforcing a shared 1,000 requests/minute is not, because every request would need a round trip to a shared counter - adding latency to every request and making the counter a single point of failure.
| Approach | Accuracy | Latency cost | Notes |
|---|---|---|---|
| Central Redis counter | Exact | +0.5–1 ms per request | Simple; Redis becomes a hard dependency and a hot key |
| Local buckets, limit ÷ N | Poor | None | Breaks badly with uneven load balancing or instance count changes |
| Local with periodic sync | Approximate | Negligible | Each node holds a lease on part of the quota, refreshed every second |
| Sticky routing by client key | Exact per key | None | Consistent-hash clients to nodes; rebalancing loses state |
Limit on more than one dimension
- Per API key - the commercial contract limit.
- Per user - stops one user inside a large customer degrading the rest.
- Per IP - catches unauthenticated abuse, but beware shared NAT and corporate proxies.
- Per endpoint - a search endpoint costs far more than a health check, so weight the token cost accordingly.
- Global - a final backstop so the total load cannot exceed capacity regardless of how it is distributed.
HTTP/1.1 429 Too Many Requests
RateLimit-Limit: 1000
RateLimit-Remaining: 0
RateLimit-Reset: 42 # seconds until the quota refreshes
Retry-After: 42 # honoured by most well-behaved HTTP clients
{"error":"rate_limit_exceeded","message":"Retry in 42 seconds","retry_after":42}
# Without Retry-After, clients retry immediately and you have converted one
# rate-limited client into a tight retry loop against your own limiter.Say these points
- Token bucket is the default: average rate enforced, bursts permitted up to capacity.
- Fixed window allows 2× the limit at boundaries - name this failure explicitly.
- Sliding window counter is the accurate-but-cheap compromise.
- Distributed: local buckets with periodic sync beat a per-request central counter.
- Always return Retry-After and RateLimit headers, and limit on several dimensions.
Avoid these mistakes
- Fixed window for anything protecting real capacity.
- A Redis round trip on the hot path of every request.
- Dividing the limit by instance count and ignoring uneven balancing.
- 429 responses with no Retry-After, causing tight client retry loops.
- IP-based limits that block an entire office behind one NAT.
Expect these follow-ups
- Redis is down. Does your limiter fail open or closed, and why?
- How do you rate limit by user when the user ID is inside an encrypted token?
- How would you offer a customer a burst allowance without letting them sustain it?
Showing 1 of 1 questions for rate-limiting-algorithms.
Check your understanding
4 questions · no sign-up, nothing stored
Hands-on challenge
Build it - this is what you talk about in a deep-dive round.
Build a distributed rate limiter
Implement a limiter enforcing 1,000 requests per minute per API key across a fleet of ten nodes, with no Redis call on the hot path.
Requirements
- Implement token bucket locally with lazy refill and configurable per-endpoint cost.
- Design the quota-lease protocol: how each node claims and returns unused allowance.
- Handle the shared store being unavailable, and justify fail-open or fail-closed.
- Return correct RateLimit and Retry-After headers on rejection.
- Load-test with uneven distribution across nodes and measure actual overshoot against the 1,000 target.
Stretch goals
- Add a second dimension (per user inside an API key) and show both being enforced.
- Add a burst allowance that recharges hourly and cannot be sustained.