Worked Design — Distributed Rate Limiter

A focused design question that tests algorithm knowledge, distributed-state handling, and failure-mode thinking. Stack: FastAPI + Redis + AWS.

1. Requirements

Functional: limit a caller (by API key / user ID / IP) to N requests per time window; reject excess with 429 + Retry-After.

Non-functional: the limiter is on every request’s hot path — it must add single-digit milliseconds, be highly available, and be roughly accurate (a few requests of slop is fine; exact counts are not worth a latency penalty).

Clarify: per-key limits or global? Fixed tiers (free = 100/min, paid = 10k/min)? What happens when the limiter store is down — fail open (allow) or fail closed (deny)?

2. Where it runs

Often layered. This design focuses on the application-level distributed limiter because that’s where the algorithm question lives.

3. The algorithms

The two interview-favorite answers: sliding window counter (good general default, O(1), no burst flaw) and token bucket (when you want controlled bursts).

Sliding window counter

def allowed(key, limit, window) -> bool:
    now = time.time()
    cur = int(now // window)
    pos = (now % window) / window          # 0.0 → 1.0 through the current window
    cur_count  = int(r.get(f"{key}:{cur}")     or 0)
    prev_count = int(r.get(f"{key}:{cur-1}")   or 0)
    estimate = cur_count + prev_count * (1 - pos)
    if estimate >= limit:
        return False
    p = r.pipeline()
    p.incr(f"{key}:{cur}")
    p.expire(f"{key}:{cur}", window * 2)
    p.execute()
    return True

The weighted previous-window term removes the fixed-window boundary burst at O(1) memory. Slightly approximate — acceptable per the requirements.

Token bucket (Lua for atomicity)

Tokens refill at a fixed rate; each request consumes one; burst up to the bucket capacity. The check-and-decrement must be atomic, so it’s a Lua script:

-- KEYS[1] = bucket key; ARGV: capacity, refill_rate, now
local tokens = tonumber(redis.call('hget', KEYS[1], 'tokens') or ARGV[1])
local last   = tonumber(redis.call('hget', KEYS[1], 'last')   or ARGV[3])
local elapsed = math.max(0, ARGV[3] - last)
tokens = math.min(ARGV[1], tokens + elapsed * ARGV[2])
if tokens < 1 then
  redis.call('hset', KEYS[1], 'last', ARGV[3]); return 0
end
redis.call('hmset', KEYS[1], 'tokens', tokens - 1, 'last', ARGV[3])
redis.call('expire', KEYS[1], 3600)
return 1

4. Why distributed state

N API servers must share one view of “how many requests has this key made.” Per-server in-memory counters would let a caller get N× their limit by spreading requests across servers. So the counter lives in Redis, and the atomic operations (INCR, Lua scripts) keep it consistent under concurrency.

request → API server (any) → Redis (atomic check) → allow / 429

The Redis op is the only added latency — sub-millisecond on a local network. That’s the whole “single-digit ms” budget spent on one round trip.

5. The response

HTTP/1.1 429 Too Many Requests
Retry-After: 30
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 1709125800

Emit the X-RateLimit-* headers on every response (not just 429s) so well-behaved clients self-throttle before they hit the wall.

6. Failure modes & trade-offs

• Redis down — fail open or fail closed? This is the key trade-off question. Fail open (allow requests when the limiter store is unreachable) keeps the service usable but removes protection during the outage — usually the right call for a limiter protecting against abuse, since the limiter being down shouldn’t take the whole API down. Fail closed (deny) is right when the limiter protects something that must not be overrun (a fragile downstream, a cost ceiling). State which and why.
• Redis as a bottleneck / SPOF — every request hits it. Mitigate with a Redis cluster (HA) and key hashing; or a two-tier scheme — a local in-process approximate counter that flushes to Redis periodically, trading exactness for fewer Redis hits.
• Hot key — one very active API key’s counter all lands on one Redis shard. Usually fine (it’s one tiny key, very fast); if a single key is truly enormous, shard its counter across N suffixed keys and sum.
• Clock skew — token bucket and sliding window use timestamps; if computed on the app servers, skew between servers causes drift. Compute time inside Redis (Lua redis.call('TIME')) to have one clock.
• Distributed accuracy — under heavy concurrency two requests can both read “99” before either increments. Atomic ops (INCR, Lua) prevent that; the residual slop is bounded and acceptable.

7. Scaling note

At extreme RPS where even one Redis round trip per request is too much: each server keeps a local token bucket sized to global_limit / server_count, with periodic rebalancing against Redis. Less precise, near-zero added latency. State it as the “if 1 ms is too much” escape hatch.

Interview angle

• “Which rate-limiting algorithm and why?” — sliding window counter as the general default (O(1) memory, no fixed-window boundary burst, slightly approximate). Token bucket when you specifically want to allow controlled bursts. Fixed window only for very forgiving limits — its boundary burst lets callers hit 2× the limit.
• “Why does the counter have to be in Redis?” — N API servers must share one view of the count; per-server counters let a caller get N× their limit by spreading load. Redis + atomic ops (INCR, Lua) is the shared, consistent, fast store.
• “Redis is down — do you allow or deny?” — the defining trade-off. Fail open for an abuse-protection limiter (the limiter being down shouldn’t kill the API); fail closed when it guards something that must not be overrun (fragile downstream, cost ceiling). Name the choice and the reasoning.
• “Why use a Lua script for token bucket?” — the read-modify-write (compute refill, check tokens, decrement) must be atomic; doing it in app code with separate Redis calls has a race. Lua runs atomically on the Redis server, and computing time inside Redis also dodges app-server clock skew.
• “What’s the boundary burst problem?” — with fixed windows, a caller can spend their full limit at the very end of one window and again at the very start of the next — 2× the rate across the boundary. Sliding window counter fixes it by weighting in the previous window’s count.
• “How do you keep this off the latency budget at huge scale?” — two-tier: a local in-process approximate counter per server (sized to its share of the global limit) that periodically reconciles with Redis. Trades exactness for near-zero added latency.