"Design a rate limiter" sounds like an algorithm question, and candidates often answer it with one: they explain the token bucket and stop. The interviewer wants more. Where does the counter live when 40 gateways share one limit? What happens to every API call when that counter store goes down? How do you stop one abusive client from melting the Redis shard that holds its key?
You run a public API behind a fleet of API gateways. Protect the backend from abuse and accidental floods, and enforce per-plan quotas: for example, 100 requests a minute per user on the free plan, more on paid plans.
In scope
- Limits per user, per API key or per IP, per endpoint group
- Many gateways enforcing one shared limit
- Clear feedback to throttled clients
A gateway rate limiter decides on every request, at an assumed 150,000 checks a second, whether a client is within limits such as 100 requests a minute, adding under 2 ms and answering 429 with Retry-After when not. Each gateway makes one atomic Lua call to a 4-shard Redis Cluster (about 2 GB of counters) with rules pushed from a rules service. The deep dives show the fixed window's 2x burst at the boundary, the sliding window counter (80 × 0.75 + 30 = 90), the token bucket and the GET-compare-SET race; failure modes cover failing open, a local deny cache for noisy clients and splitting limits across regions.
Phase 1: Requirements (3 minutes)#
"Is this a server-side limiter in our gateways, not a client library? Hard limits, or is a small overshoot fine? What should happen if the limiter itself fails?"
"Server side, in the gateway. A few percent over is fine; a client getting double its limit is not. And the API must stay up even if the limiter has problems."
Functional requirements#
- Rules keyed on any of: user ID, API key, IP, endpoint group, plan
check(key, rule)returns allow or deny, remaining quota and reset time- Rejected requests get 429 Too Many Requests with
Retry-Afterand remaining-quota headers - Rules change without a deploy (a new enterprise plan, an emergency limit on one endpoint)
Non-functional requirements#
- Low latency: under 2 ms added at p99, because it runs on every request
- Accurate enough: small overshoot is fine, a 2x burst is not
- Highly available: a limiter failure must not become an API outage
- Shared state: 40 gateways enforcing "100 a minute" must not each allow 100
Phase 2: Estimation (3 minutes)#
- Peak traffic: assume 150,000 requests/s (50,000 average, 3x peaks)
- Each request costs one atomic call to the counter store (a script that reads and updates in one round trip)
- Assume one Redis shard serves about 100,000 simple operations/s: you need at least 2 shards; run 4 for headroom and failover
- Counter state per (client, rule): key, two counters and a TTL, assume ~100 bytes
- 10M clients × 2 active rules × 100 B ≈ 2 GB: small, it's the operation rate that drives the shard count
- Latency: a same-zone Redis round trip is typically well under a millisecond, which leaves room inside the 2 ms budget
"Memory is easy. The design problem is doing 150,000 atomic decisions a second without a single hot spot, and deciding what happens when the store is unreachable."
Phase 3: API (2 minutes)#
The limiter is an internal call made by the gateway, plus what the client sees.
# internal, gateway → limiter (in-process library + Redis)
check(key="user:8812:search", rule="free.search")
→ { allowed: false, remaining: 0, reset_ms: 41000 }
# what the client sees
HTTP/1.1 429 Too Many Requests
Retry-After: 41
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 1793181641# a rule, stored in the rules service and pushed to every gateway
- id: free.search
match: { plan: free, endpoint_group: search }
key: user_id
algorithm: sliding_window
limit: 100
window: 60sPhase 4: High-level design (4 minutes)#
%% title: Rate limiting in the API gateway
flowchart TD
C@{ icon: "sd:users", label: "Clients and API keys" } --> LB@{ icon: "sd:load-balancer", label: "Load balancer" }
LB --> GW["API gateways<br/>limiter middleware<br/>+ local deny cache"]:::core
GW -->|"one atomic script per request"| R@{ icon: "tech:redis", label: "Redis Cluster<br/>counters, sharded by key" }
CFG@{ icon: "sd:file", label: "Rules service<br/>limits per plan and endpoint" } -.->|"push on change"| GW
GW -->|"allowed"| BE@{ icon: "sd:servers", label: "Backend services" }
GW -->|"over the limit"| REJ["429 + Retry-After"]:::bad
GW -.->|"decisions, rejects"| M@{ icon: "sd:dashboard", label: "Metrics and alerts" }
class C client
class LB edge
class R cache
class CFG store
class BE service
class M service- Limiter middleware in each gateway builds the key (
user:8812:search), finds the matching rule in its local copy of the rules, and calls Redis once. - Redis Cluster holds the counters. Keys are hashed across shards, so load spreads with the number of clients.
- Rules service stores rules and pushes changes; gateways never read rules on the request path.
- Local deny cache: once a key is denied, the gateway remembers that until the reset time and rejects locally without calling Redis. This matters in deep dive 2.
Phase 5: Deep dives (5 minutes)#
Deep dive 1: Which algorithm?#
"Walk me through the options. Why not just count requests per minute?"
"100 per minute" counted in calendar minutes lets a client send 100 requests at 12:00:59 and another 100 at 12:01:00. Both windows are within the limit, but the backend just took 200 requests in two seconds, double the intended rate.
Sliding log
- Store a timestamp per request, count those in the last 60 s
- Exact
- Memory grows with the limit: 100 timestamps per client per rule
Sliding window counter
- Keep this window's and last window's counts
- Estimate:
prev × (1 − elapsed/window) + curr - Two integers per key; close to exact; the usual default
Token bucket
- A bucket of capacity B refills at R tokens/s; each request takes one
- Allows short bursts up to B, then the steady rate R
- Two numbers: tokens left and last refill time
Leaky bucket
- Requests join a queue drained at a fixed rate
- Smooths output perfectly
- Adds queueing delay; better for outbound traffic shaping than API admission
"For per-user API quotas I'd use the sliding window counter: two integers, no 2x boundary burst. For endpoints where short bursts are legitimate, like a mobile app syncing on launch, a token bucket with capacity 20 and refill 10 a second expresses that directly."
- Limit 100 per minute; it is 15 s into the current minute (25% elapsed)
- Last minute's count: 80; this minute so far: 30
- Estimate: 80 × (1 − 0.25) + 30 = 60 + 30 = 90, below 100, so allow and increment to 31
- The estimate assumes last minute's requests were spread evenly, which is why it is approximate; in practice the error is small
Deep dive 2: Counting correctly across 40 gateways#
"Two gateways read the counter at 99 at the same moment. What happens?"
"If they do GET, compare, SET, both see 99, both allow, and the client gets 101. The fix is to make check-and-increment a single atomic operation in Redis: a Lua script runs without interleaving, so the second caller sees the first caller's increment."
-- sliding window counter, atomic in Redis
-- KEYS[1] = current window key, KEYS[2] = previous window key, same hash slot: rl:{user:8812:search}:<window>
-- ARGV[1] = limit, ARGV[2] = window_ms, ARGV[3] = ms elapsed in the current window
local limit, window, elapsed = tonumber(ARGV[1]), tonumber(ARGV[2]), tonumber(ARGV[3])
local curr = tonumber(redis.call("GET", KEYS[1]) or "0")
local prev = tonumber(redis.call("GET", KEYS[2]) or "0")
if prev * (window - elapsed) / window + curr >= limit then
return 0 -- deny: the gateway answers 429
end
redis.call("INCR", KEYS[1])
redis.call("PEXPIRE", KEYS[1], 2 * window) -- kept for one more window as "previous"
return 1- Hash tags (
{user:8812:search}) put both window keys on the same shard, which the script needs. - Clocks: gateways compute the window from their own clock, kept in sync by NTP. A few milliseconds of skew moves a window boundary slightly, which the "a few percent over is fine" requirement tolerates.
- The problem: an abusive client sending 50,000 requests a second sends all of them to the one shard that owns its key, a hot key.
- Local deny cache: after the first deny, each gateway caches "denied until reset" in memory and answers 429 itself. Redis sees roughly one call per gateway per reset period instead of 50,000 a second.
- Edge limits first: a coarse per-IP limit at the load balancer or CDN drops floods before they reach the gateway at all.
- Very high limits: for a single key with a huge limit (an internal service at 50,000 a second), count locally in each gateway and sync to Redis every 100 ms; you trade a little accuracy for far fewer calls.
Algorithms and atomicity
Q1/2 With a fixed one-minute window and a limit of 100, what is the worst burst a client can send?
Answer & explanation
Answer: B
100 at the end of one window plus 100 at the start of the next are both allowed, which is double the intended rate. Sliding windows remove this edge.
Q2/2 Two gateways run GET, compare, then SET on a counter at 99 at the same time. What is the fix?
Answer & explanation
Answer: C
Both gateways read 99 and both allow. A Lua script (or INCR followed by a check) runs atomically, so the second caller sees the first one's increment.
Phase 6: Trade-offs and failure modes (2 minutes)#
Redis is unreachable
Fail open for ordinary API limits: allow the request, log it, and alert. A limiter outage should not become an API outage. Fail closed only where over-admission is dangerous (login attempts, OTP sends, expensive jobs), and fall back to a conservative per-gateway local limit rather than rejecting everything.
Latency creeps up
Put a short timeout (a few milliseconds) on the Redis call and treat a timeout like an outage. A limiter that waits 200 ms on every request is worse than one that occasionally lets a request through.
Multi-region
A global "100 a minute" needs cross-region coordination on every request, which is too slow. Usual answers: split the limit per region (each of 4 regions allows 25), or enforce locally and reconcile counts asynchronously, accepting a short overshoot.
Rules go wrong
A bad rule push can throttle everyone. Validate rules before publishing, roll them out gradually, keep the last good version, and watch the reject rate per rule.
Clients retry in a storm
Return Retry-After and document exponential backoff with jitter; otherwise throttled clients retry at once and make the spike worse.
Phase 7: Go deeper in the course#
- Every algorithm, distributed limiting and failure modes in depth: Week 1 · Day 3: Rate Limiting at Scale
- Build it yourself in the browser: Lab: Token bucket rate limiter and Lab: Sliding window counter
- Hot keys and the noisy client: Week 1 · Day 4: Hot Keys and Skew
- Per-tenant limits and fairness: Week 9 · Day 2: Noisy Neighbor Prevention
- Timeouts on the limiter call, failing open: Week 2 · Day 1: Timeout Hell
- Why clients must back off with jitter: Lab: Retry with backoff and jitter
- Shedding load when the backend is saturated: Week 3 · Day 3: Backpressure and Flow Control
Final check#
Final check · Rate limiter
Q1/4 At 150,000 checks a second and about 100,000 operations a second per Redis shard, why run 4 shards rather than 2?
Answer & explanation
Answer: B
The counters fit in 2 GB, so memory is not the constraint. 150,000 ÷ 100,000 means at least 2 shards; running at the edge of capacity leaves nothing for a burst or a failed node.
Q2/4 Redis becomes unreachable for ordinary API traffic. What is the usual choice, and why?
Answer & explanation
Answer: C
A limiter protects the API; it should not become a single point of failure for it. Fail closed only for flows where over-admission is dangerous, like login or OTP sends.
Q3/4 One client sends 50,000 requests a second and all of them hit the shard that owns its key. What helps most?
Answer & explanation
Answer: A
After the first deny, each gateway answers 429 from memory until the window resets, so Redis sees about one call per gateway per period instead of 50,000 a second.
Q4/4 Limit 100 a minute, 15 s into the window, last window 80 requests, this window 30. What does a sliding window counter estimate?
Answer & explanation
Answer: C
80 × (1 − 0.25) + 30 = 90, which is under 100.
New lessons by email
New lessons, side quests and case files as they ship, at most once a week. No spam, unsubscribe anytime.
Discussion · …
Public: everyone reading this lesson sees comments. Be kind and keep it on the material.