Design a distributed rate limiter

The setup

"You're at an API company. Your customers have rate limits (1000 requests/minute per API key, for example). Design the rate-limiting system. Must work across 100 API gateway nodes; per-customer limits must be enforced accurately (not 100× the limit just because we have 100 nodes); failures must be graceful."

This problem isolates a single distributed-systems concept: shared state with strong consistency requirements at high throughput. The test is whether you can navigate the speed/accuracy/availability tradeoff explicitly.

Clarifying questions

Design Decision 1: which algorithm?

flowchart LR
    C1[Client] --> G1[API Gateway 1]
    C2[Client] --> G2[API Gateway 2]
    C3[Client] --> G3[API Gateway N]
    G1 -->|EVAL Lua: take token?| R[("Redis cluster
per-key bucket")]
    G2 -->|EVAL Lua| R
    G3 -->|EVAL Lua| R
    R -.replication.-> RR[(Replica)]
    G1 -->|"allowed / 429"| C1
    G2 --> C2
    G3 --> C3

Production pick: token bucket. Smooth, easy to reason about, widely battle-tested. State per user: (current_tokens: float, last_refill_at: timestamp) — 16 bytes. For 10M users: 160 MB. Trivial.

Design Decision 2: where does the bucket state live?

The central architectural question. Options span a spectrum of speed/accuracy/availability tradeoffs.

Production answer: sharded Redis cluster with atomic operations. Each customer's bucket lives on one Redis shard via consistent hashing. Gateway makes a single Redis call per request:

def is_allowed(customer_id):
    bucket_key = f"ratelimit:{customer_id}"
    # Atomic Lua script:
    #   - Refill tokens based on time elapsed since last refill
    #   - If tokens >= 1: decrement, return ALLOWED + remaining
    #   - Else: return REJECTED + retry-after
    result = redis.eval(token_bucket_script, key=bucket_key, args=[
        bucket_size, refill_rate, current_time
    ])
    return result

Lua script ensures atomic check-and-decrement. Without it: two simultaneous requests could both see "1 token available," both decrement, both pass — bucket goes to -1.

The Lua script — the actual atomicity primitive

local bucket_size = tonumber(ARGV[1])
local refill_rate = tonumber(ARGV[2])  -- tokens per second
local current_time = tonumber(ARGV[3])

local state = redis.call('HMGET', KEYS[1], 'tokens', 'last_refill')
local tokens = tonumber(state[1] or bucket_size)
local last_refill = tonumber(state[2] or current_time)

-- Refill based on time elapsed
local elapsed = current_time - last_refill
local refilled = math.min(bucket_size, tokens + elapsed * refill_rate)

if refilled >= 1 then
  refilled = refilled - 1
  redis.call('HMSET', KEYS[1], 'tokens', refilled, 'last_refill', current_time)
  redis.call('EXPIRE', KEYS[1], 3600)  -- TTL for cleanup
  return {'allowed', refilled}
else
  redis.call('HMSET', KEYS[1], 'tokens', refilled, 'last_refill', current_time)
  redis.call('EXPIRE', KEYS[1], 3600)
  return {'rejected', refilled}
end

Single Redis roundtrip; atomic via Lua execution; ~0.5-1ms latency.

Cross-examination round 1: Redis hot key

Cross-examination round 2: Redis failure

Cross-examination round 3: configuration changes

Takeaway

Distributed rate limiting is the classic "where does shared state live?" question. Pure local is wrong (over-allocates); pure central is fragile and slow; sharded central with caching and graceful failure handling is what works. The interview test is whether you can articulate why each option falls short and explicitly pick the right tradeoff for the use case.

The deeper lesson: any distributed enforcement of a shared limit requires choosing between speed, accuracy, and availability — never all three. There's always a tradeoff. Senior engineers explicitly name the chosen point on this triangle (sharded Redis with fail-open) and justify it in terms of the use case.