Module 12 · Lesson 02
Design a distributed rate limiter
A counter that must be shared, atomic, and fast — and must still work when the counter store is down.
What you will be able to do
- Implement a token bucket atomically in a shared store
- Estimate Redis operations per request at scale
- Choose a failure mode when the limiter is unavailable
- Layer per-IP, per-key and per-tenant limits
Requirements and estimates
- Functional: limit each API key to N requests per window, return 429 with Retry-After, expose current usage.
- Non-functional: under 5 ms added latency at p99, correct within a small overshoot, available during a cache outage.
- Scale: 100k rps across the fleet; roughly 10M active keys.
100,000 rps -> 100,000 Redis ops/s for a single-key check Redis node capacity ~100-200k ops/s => one node is tight; shard keys across 4-8 nodes by hash memory: 10M keys x ~100 B = ~1 GB, plus TTLs
Algorithm choice
| Algorithm | Burst | Accuracy | State per key |
|---|---|---|---|
| Fixed window counter | Up to 2x at boundaries | Poor at edges | One integer |
| Sliding window counter | Small | Good approximation | Two integers |
| Sliding window log | None | Exact | One timestamp per request |
| Token bucket | Up to bucket size | Exact rate | Tokens + timestamp |
Token bucket is the default for public APIs because real clients burst: a page load fires ten requests at once. Allow a bucket of 100 with a refill of 10/s and the client can burst, then settles to the steady rate. Sliding-window counters are the better answer when the contract promises a strict count per minute.
Atomicity
-- Lua, executed atomically in Redis
local tokens = redis.call('HGET', key, 'tokens') or capacity
local ts = redis.call('HGET', key, 'ts') or now
local refill = math.min(capacity, tokens + (now - ts) * rate)
if refill < cost then return 0 end
redis.call('HSET', key, 'tokens', refill - cost, 'ts', now)
redis.call('EXPIRE', key, ttl)
return 1Without a script, two app servers can both read 1 token and both decrement, allowing double the limit. The script makes the check-and-decrement one operation, and it is also one network round trip instead of three.
The hot key problem returns
A single global key for one large customer serialises every request through one Redis shard. Shard the counter by a small suffix and sum the parts, accepting slight inaccuracy, or keep a local token cache per instance with a short sync interval.
Failure modes and layering
Decide fail-open or fail-closed
Availability-critical read APIs fail open with a local emergency limit; login and payment endpoints fail closed.
Add a local pre-check
Each instance keeps an in-memory counter with a fraction of the limit, cutting Redis traffic and surviving a brief outage.
Layer the limits
Per-IP at the edge for floods, per-key at the gateway for contract, per-tenant concurrency in the service for fairness.
Return useful headers
RateLimit-Limit, RateLimit-Remaining and Retry-After. Clients that can see the budget behave better.
The complete answer
"Token bucket in Redis via a Lua script, sharded by key hash, with a local counter absorbing most checks. Fails open for reads with a conservative local limit, fails closed for auth. Limits layered by IP, key and tenant."
Worth remembering
- Read-modify-write without atomicity allows overshoot proportional to concurrency.
- One Redis op per request is fine at 10k rps; a Lua script keeps it to a single round trip.
- A rate limiter must decide explicitly whether to fail open or closed.
- Per-tenant fairness needs concurrency caps, not just request-rate limits.
Checkpoint
Answer all 3 questions to finish the lesson.
1. Why does a non-atomic read-modify-write limiter allow more requests than intended?
Two servers can both observe available capacity and both proceed. Atomic check-and-decrement closes that window.
2. Which algorithm best matches a client that fires ten requests on page load then idles?
A bucket accumulates tokens while idle, permitting a burst up to capacity and then enforcing the average rate.
3. The rate-limit store is unavailable. What is the right default for a payment endpoint?
For high-risk operations, refusing traffic is safer than allowing unlimited retries while protections are down.