Design a Distributed Rate Limiter

Clarifying questions I'd ask first

Before drawing anything, I'd want to confirm a few things with the interviewer:

• What are we rate-limiting — per user, per API key, per IP, or some combination?
• Where does it live — at the API gateway in front of all services, or inside one specific service?
• Strict per-second enforcement, or is occasional bursting fine?
• What's the latency budget on the limiter itself — usually under five milliseconds?
• Fail-open or fail-closed when our backing store is unreachable?

Assumptions for this design

I'll assume per-API-key limiting at the gateway, ten million requests per day spread across multiple gateway instances behind a load balancer, a sub-five-millisecond latency budget, and fail-open semantics so a Redis blip doesn't take down the API.

Quick capacity check

Ten million per day averages around one hundred fifteen requests per second. Traffic isn't uniform though — peaks usually run five to ten times average — so I'd plan for one to two thousand sustained, with short bursts higher. That throughput rules out anything that sits in a relational database; we need an in-memory store with atomic operations, which is why Redis.

High-level shape

• Every request hits the gateway
• Gateway calls a rate-limit check against Redis
• On allow, forward to the downstream service and set X-RateLimit-* headers
• On deny, return 429 with a Retry-After header
• On Redis error, log, increment circuit-breaker, allow through (fail-open)

State lives in Redis because all gateway instances need to share the same counter — if each kept local state, a client could multiply their quota by the number of instances.

Algorithm choice — token bucket

My default is token bucket. The two-knob design maps cleanly to how APIs are actually priced:

• Capacity controls burst size
• Refill rate controls sustained throughput
• A client with capacity 10 and refill 1/sec can burst 10 requests instantly, then settles to 1/sec

Why not the others:

• Sliding-window-log is more precise but stores every request timestamp, so memory scales with traffic
• Fixed window lets clients double their effective rate by timing requests at the window boundary — usually disqualifying for paid tiers
• Sliding-window-counter is a reasonable approximation if strict accounting matters more than burst tolerance

The critical detail — atomicity via Lua script

Reading the bucket, computing refill, and decrementing has to happen as a single atomic operation, or two concurrent requests can both pass when only one should.

• I do this with a Lua script via Redis EVAL — it runs server-side with no interleaving possible
• The script also sets the TTL on the key, so inactive clients evaporate automatically and Redis memory stays bounded
• Pre-load the script with SCRIPT LOAD at startup and call it via EVALSHA to avoid sending the script body on every request

Class design — keep it swappable

• A RateLimiter interface with one method: tryAcquire(key) returning a result record (allowed flag, remaining count, retry-after seconds)
• Redis token-bucket implementation lives behind that interface
• Separate TierResolver maps API key to capacity and refill rate, cached locally with a 30-second TTL so we don't hit the database per request
• Tests use an in-memory implementation; we can A/B-test sliding-window behind the same contract

Failure handling — fail open with a circuit breaker

When Redis is unreachable I fail open:

• A brief loss of rate limiting is much less harmful than a complete API outage
• Circuit breaker (Resilience4j) on the Redis call so we stop hammering a dead Redis
• Local fallback to a per-instance in-memory counter — rough but better than nothing
• Alert on any non-zero fallback invocations so the team knows

Production extras worth mentioning

• Multi-tier limits — free, pro, enterprise each get independent buckets
• Response headers — X-RateLimit-Limit, X-RateLimit-Remaining, X-RateLimit-Reset, Retry-After so well-built client SDKs self-throttle before hitting 429
• Observability — top denied keys (identifies abuse), denial rate per tier (signals pricing issues), p99 limiter latency (must stay under budget)
• Per-endpoint cost weighting — a /search request might count as 10 tokens vs 1 for /health

At 10× scale

• Shard Redis with Redis Cluster, hash by API key
• Add a local in-process cache for the hot 1% of keys (top traffic usually comes from < 100 keys)
• Switch paid tiers to sliding-window-counter for stricter accounting

Recommendation

Token bucket in Redis with Lua-script atomicity, fail-open with a circuit breaker, multi-tier limits, and rate-limit headers on every response — essentially the design Stripe, Cloudflare, and GitHub run in production.