Start with the requirement
"Rate limit our public API to 100 requests per minute per API key" sounds simple until you ask:
- Is 100/min a hard ceiling or a moving window?
- Do we need burst tolerance (e.g., 10 in 1 second is fine, but not 100)?
- Is this per-key or per-key-per-endpoint?
- What should happen on failure — fail open or fail closed?
For this walkthrough: per-API-key, 100 requests per 60 seconds, sliding window, fail open (better to over-serve than to take down traffic if the limiter dies).
The four algorithms to know
Fixed window. Count requests in each minute-long bucket. Simple, but allows 2x traffic at the minute boundary (99 at :59, 99 more at :00).
Sliding log. Store every request timestamp, count how many are within the last 60 seconds on each incoming request. Accurate but expensive — memory grows with request rate.
Sliding window counter. Keep two fixed-window counters and weight them by how far into the current window you are. Accuracy close to sliding log, memory close to fixed window. This is the default I recommend in interviews.
Token bucket. Tokens refill at a steady rate; each request consumes one. Handles bursts naturally — a bucket can fill up during idle time. Best for "X per second with occasional bursts" semantics. Used by AWS, Stripe, GitHub.
Sketch the implementation
Sliding window counter in Redis:
key = rate:{api_key}:{window_start}
INCR key
EXPIRE key 120 # two windows worth
On each request, read current window counter and previous window counter, apply weight:
current = GET rate:{key}:{now_window}
prev = GET rate:{key}:{prev_window}
elapsed_in_window = (now - now_window_start) / 60
estimate = prev * (1 - elapsed_in_window) + current
if estimate >= limit: reject
else: INCR current
Survives a restart; memory is O(1) per key.
The distributed problem
Single Redis is a single point of failure and limits throughput to Redis's write ceiling. Options:
Redis Cluster with key-based sharding. Each API key hashes to a shard. Works up to millions of keys.
Local counters with periodic sync. Each edge node tracks locally, flushes deltas to a central store every N seconds. Much faster but less accurate — a user can exceed the limit on a single node without the central store knowing yet.
Hybrid: local burst protection + central quota. Cheap local fixed-window catches obvious abuse; central store enforces the overall limit. Common at CDN-scale services.
Failure modes
- Redis down. Fail open (let traffic through) or fail closed (reject all)? For most public APIs, fail open — a limiter outage should not be a service outage. Log loudly.
- Clock skew across nodes. Sliding window math assumes synchronized clocks. NTP gets you within milliseconds; do not hand-roll clocks.
- Hot keys. A single API key with massive traffic can saturate one Redis shard. Solve with per-shard sub-counters or client-side pre-sharding (
key#0,key#1, ...). - Cold start. Right after deploy, edge nodes have no local state. Brief grace period before enforcement helps avoid false positives.
The answer that wins the interview
Ask about limits (per-what, what window semantics, burst tolerance). Pick an algorithm with reasoning (sliding window counter for most cases). Sketch the Redis implementation. Discuss scaling via sharding. Name the failure modes and your posture on each. End with monitoring — an unmonitored rate limiter is indistinguishable from broken code.