System Design Interview Question: Design a Rate Limiter

Rate limiters protect services from abuse and overload. This question tests algorithm choice and distributed-state thinking.

Requirements

• Limit requests per user/API key (for example 100 per minute), with different tiers.
• Low added latency (a few milliseconds).
• Work across many API servers.
• Clear responses: HTTP 429 with Retry-After.

Algorithms

• Fixed window counter: one counter per minute. Simple and cheap, but allows double bursts at window edges.
• Sliding window log: store each request timestamp; exact, but memory-heavy at high limits.
• Sliding window counter: weighted mix of the current and previous window counts. A good approximation with tiny memory.
• Token bucket: tokens refill at a steady rate up to a capacity; each request takes one. Allows controlled bursts. Very common.

Where it runs

• In an API gateway or edge proxy, so bad traffic is stopped early.
• Or as middleware in each service, calling a shared store.

Shared state in Redis (token bucket)

-- KEYS[1] = bucket key; ARGV = capacity, refill_per_sec, now_ms
local b = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local capacity, rate, now = tonumber(ARGV[1]), tonumber(ARGV[2]), tonumber(ARGV[3])
local tokens = tonumber(b[1]) or capacity
local ts = tonumber(b[2]) or now
tokens = math.min(capacity, tokens + (now - ts) / 1000 * rate)
local allowed = tokens >= 1
if allowed then tokens = tokens - 1 end
redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('PEXPIRE', KEYS[1], math.ceil(capacity / rate * 1000))
return allowed and 1 or 0

Running the logic as a Lua script makes the read-modify-write atomic, avoiding race conditions between API servers.

Trade-offs to discuss

• Redis down? Fail open (allow traffic) to stay available, or fail closed for protection; most APIs fail open with alerts.
• Latency: a local in-memory pre-check plus periodic sync reduces Redis calls at very high volume, at the cost of precision.
• Hot keys: one huge customer can overload a single Redis shard.
• Multi-region: per-region limits are simpler than global exact counts.