Design a distributed rate limiter.

Summary

Count requests per key (user, API key, IP) in a shared fast store like Redis using a token bucket or sliding-window algorithm executed atomically, enforce it in a gateway or middleware, and return 429 with Retry-After when limits are exceeded.

Requirements

• Limit requests per client per time window with configurable rules (per endpoint/plan)
• Low added latency (< 2 ms)
• Works across many API servers
• Return limit headers and 429s; fail-open or fail-closed configurable

API

# Middleware decision
allow(key="user:42:POST /orders", limit=100, window=60s) → {allowed: true, remaining: 57, reset: 23s}
# Response headers
RateLimit-Limit: 100   RateLimit-Remaining: 57   Retry-After: 23

Data Model

-- Redis keys (token bucket)
rl:{key} → hash {tokens: float, updated_at: ms}   TTL = window
-- Rules (config DB or file)
rate_rules(id, match_route, match_plan, limit, window_s, burst)

Architecture

Requests pass through an API gateway or middleware that builds the key, loads the matching rule (cached locally), and executes an atomic Lua script in Redis that refills and consumes tokens. Redis is clustered and sharded by key. Rules are distributed via config with hot reload.

Deep Dives

• Algorithms: fixed window (simple, bursty at edges), sliding log (accurate, memory heavy), sliding window counter (good approximation), token bucket (allows bursts, smooth refill)
• Atomicity: a Lua script or Redis functions avoid race conditions between read and write
• Local + global: in-process pre-limiting reduces Redis load for very hot keys
• Failure mode: if Redis is down, fail open for most traffic but fail closed for sensitive endpoints like login

Scaling

• Shard keys across a Redis cluster
• Keep Redis close to gateways (same region)
• Use approximate local counters synchronized periodically for extreme throughput

Comparison / Tradeoffs

What interviewers look for

A structured approach: clarify requirements and scale, sketch the API and data model, draw the high-level architecture, then go deep on the hardest component and discuss trade-offs, bottlenecks and failure modes.

Follow-up questions

• How do you rate limit across regions?
• How would you implement per-tenant quotas per month?
• How do you protect the rate limiter itself?