How to run a distributed rate limiter design in a 45-minute interview: algorithm trade-offs, an atomic Redis Lua token bucket, hot keys, and fail-open vs fail-closed.
Published September 21, 2026
This lesson is the interview version: how to present the design, the algorithms to compare, and the distributed-systems details interviewers probe. The full reference design is the case study Design a Rate Limiter in this chapter. For the class-level version (implementing a limiter inside one process), see In-Memory Rate Limiter in the LLD course.
A rate limiter caps how many requests a client may make in a period ("100 requests per minute per API key"). It protects services from abuse and accidental overload, keeps one noisy customer from starving others, and enforces pricing tiers. It sits on the path of every request, so it must be fast (well under a millisecond or two), accurate enough, and must fail safely when its own storage has problems.
429 Too Many Requests with Retry-After and X-RateLimit-* headers. client ──▶ API gateway ──▶ rate-limit check ──allow──▶ backend service
│ ▲
▼ │ atomic "check and consume" (one round trip)
Redis cluster (counters/buckets, sharded by key)
▲
rules config (limits per plan/endpoint), cached in each gateway
Each request builds a key such as rl:{apiKey}:{endpoint}, runs one atomic check against Redis, and either continues or returns 429. The rules (who gets which limit) are loaded from configuration and cached locally, so they aren't fetched per request.
| Algorithm | How it works | Pros | Cons |
|---|---|---|---|
| Fixed window counter | Count requests per clock window (e.g. per minute) | Tiny state, one INCR | Allows 2× the limit across a window boundary (100 at 0:59 + 100 at 1:00) |
| Sliding window log | Keep every request timestamp and count those in the last 60 s | Exact | Memory per request, which is expensive at high limits |
| Sliding window counter | Current window's count + previous window's count × the fraction of overlap | Near-exact with two counters | An approximation (assumes even spread within the previous window) |
| Token bucket | A bucket of capacity C refills at rate r; each request takes a token | Allows controlled bursts up to C while enforcing the average r; tiny state | Two values to update atomically |
| Leaky bucket | Requests queue and drain at a constant rate | Perfectly smooth output | Adds queueing delay; bursts wait instead of being served |
The usual recommendation: a token bucket for API limits (bursty clients are normal, and the average rate is what matters), or a sliding window counter when the product wants "N per minute" semantics without the boundary problem.
The check "read current state, decide, update" must be atomic. Otherwise two nodes both read "99 used" and both allow request 100. In Redis, run the whole decision as one Lua script, which executes atomically on the server in a single round trip. A token bucket:
-- KEYS[1] = bucket key
-- ARGV[1] = capacity, ARGV[2] = refill rate (tokens per second), ARGV[3] = now (ms), ARGV[4] = tokens requested
local capacity = tonumber(ARGV[1])
local rate = tonumber(ARGV[2])
local now = tonumber(ARGV[3])
local want = tonumber(ARGV[4])
local state = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(state[1]) or capacity -- new client starts with a full bucket
local ts = tonumber(state[2]) or now
tokens = math.min(capacity, tokens + (now - ts) / 1000 * rate) -- refill for the time elapsed
local allowed = 0
if tokens >= want then
tokens = tokens - want
allowed = 1
end
redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('PEXPIRE', KEYS[1], math.ceil(capacity / rate * 1000) * 2) -- idle buckets expire
return { allowed, math.floor(tokens) } -- remaining → X-RateLimit-Remaining
The gateway passes now from its own clock. With many gateway nodes, their clocks differ slightly. That's acceptable for rate limiting, and you can use Redis's TIME command inside the script if tighter accuracy matters. Because each client's key lives on one Redis shard, the cluster scales horizontally by key.
If Redis is unreachable, the limiter must decide quickly (tight timeout) and fail open for most APIs, meaning allow the request and log it, because blocking all traffic turns a limiter outage into a full outage. Sensitive endpoints (login, OTP, payments) can fail closed, or fall back to a conservative local in-memory limiter.
429, Retry-After and remaining-quota headers.Q: Token bucket or leaky bucket? A: Token bucket allows bursts up to the bucket size while enforcing an average rate, and requests are served immediately if tokens are available. That suits APIs. Leaky bucket smooths traffic to a constant outflow by queueing, which suits protecting a downstream system that can't absorb bursts. It adds latency.
Q: How do you rate-limit across multiple data centres? A: Either split the global limit between regions (each enforces its share locally, and shares are adjusted periodically from observed traffic), or accept per-region limits. Synchronizing one global counter across regions on every request adds too much latency. Exactness is traded for speed.
Q: How would you limit by IP when many users share one IP (offices, mobile carriers)? A: Use IP limits only as a coarse safety net for anonymous traffic, with generous thresholds, and prefer authenticated identities (user, API key) for real limits. Combine signals (IP + device + account) for abuse detection rather than relying on IP alone.
Q: Why use a Lua script instead of MULTI/EXEC?
A: A Redis transaction (MULTI/EXEC) can't make decisions based on values read inside it. The logic needs "read tokens, compute refill, compare, then write". A Lua script runs that entire read-compute-write atomically on the server, in one network round trip.
Q: What should the client do on a 429?
A: Honour Retry-After (or back off exponentially with jitter), and not retry immediately in a tight loop. Well-behaved SDKs do this automatically. Servers should make the headers accurate so clients can pace themselves.