Design a distributed rate limiter

1. Clarify the requirements

"Rate limiter" covers very different systems, so scope it first. Is this a server-side limiter for a public API, or an internal one protecting a fragile dependency? What is the key: user ID, API key, IP address, or a combination? Are limits per endpoint? Is it single-region or global?

Functional requirements

• Limit requests per key per time window, for example 100 requests per minute per API key, with different rules per endpoint or plan.
• Reject excess requests with HTTP 429 and tell the client when to retry.
• Rules can change without a deploy.

Non-functional requirements

• Low overhead: the check should add around a millisecond, not tens of milliseconds, to every request.
• Accurate enough: small overshoot under races is acceptable; systematically letting through 2× the limit is not.
• Highly available: if the limiter fails, the API shouldn't fail with it.

2. Estimates

The takeaways: memory is not the problem, request rate to the store is. That pushes you towards one atomic operation per check and possibly local batching for the hottest keys.

3. Choosing an algorithm

Pick token bucket for an API limiter and say why: constant memory, burst tolerance that matches real client behaviour, and a refill that can be computed lazily on each request (no background job). The refill is tokens = min(capacity, tokens + (now − last) × rate); if tokens ≥ 1, decrement and allow.

4. High-level architecture

The limiter is middleware in the API gateway (or a sidecar), so every service gets it without code changes. For each request it builds a key such as rl:{api_key}:{endpoint}, looks up the rule from an in-process cache, and runs one atomic check against Redis. Rules live in a config store and are pushed to gateways (or polled every few seconds), so changing a limit doesn't need a deploy.

5. Making it correct across servers

The classic bug is a read-modify-write race: two gateways both read 1 token left, both allow, and the bucket goes negative. Fixes, in order of preference:

• Atomic Lua script in Redis. Read tokens and timestamp, refill, decide, write back, set a TTL, all in one script. Redis runs scripts atomically, so there's no race and only one round trip.
• Use Redis server time (TIME) inside the script rather than each gateway's clock, so clock skew between gateways can't mint extra tokens.
• Shard by key with Redis Cluster hash slots, so all checks for one key hit one node and stay atomic.

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

6. Data model

Redis (hot state, expires automatically)
  rl:{key}:{endpoint}  HASH { tokens: float, ts: float }   TTL ≈ 2 × refill time

Rules (config store, cached in every gateway)
  rule_id, match { plan, endpoint, method }, capacity, refill_per_sec,
  scope (key | ip | global), action (reject | shadow)

A shadow action logs what would have been rejected without rejecting it; it's how you roll out a new limit safely.

7. Scaling and failure handling

• Hot keys. One huge customer can saturate a single Redis shard. Give each gateway a small local token allowance (for example 10% of the limit) and only sync with Redis when it's exhausted, trading a little accuracy for far fewer round trips.
• Redis failure. Fail open with a conservative per-gateway in-memory limiter, and alert. Failing closed turns a cache outage into a full API outage.
• Multi-region. A truly global limit needs cross-region coordination, which is slow. The usual answer is per-region limits (global limit ÷ regions, rebalanced periodically from observed traffic) plus asynchronous counter sync for reporting.
• Layering. Combine a coarse per-IP limit at the edge/CDN (cheap, blocks floods) with precise per-key limits in the gateway.

8. Client experience and trade-offs

Return 429 Too Many Requests with a Retry-After header, plus remaining-quota headers (commonly X-RateLimit-Limit, X-RateLimit-Remaining, X-RateLimit-Reset) so well-behaved clients slow down themselves. Trade-offs worth naming:

• Accuracy vs latency: a central store is accurate but adds a network hop; local counters are fast but drift.
• Fail open vs closed: availability of the API vs protection of the backend.
• Burst tolerance: token bucket's capacity lets legitimate bursty clients through but also lets abusers burst; tune capacity separately from rate.

9. Common follow-up questions

1. How would you limit by "requests per user across all devices"? Key on user ID after authentication; for unauthenticated traffic fall back to IP plus a device fingerprint, and accept that NATs make IP limits blunt.
2. How do you rate-limit expensive operations differently? Charge variable token costs: a search might cost 1 token and a bulk export 50.
3. How would you test it? Unit-test the algorithm with a fake clock, load-test with many gateways hitting one key to confirm no overshoot, and run new rules in shadow mode first.
4. What about queues instead of rejection? For internal callers, a leaky bucket that delays rather than rejects can be friendlier, as long as callers have timeouts.
5. How do you protect against a DDoS? The application rate limiter isn't the right layer for that; volumetric attacks are absorbed at the network edge/CDN before they reach your gateways.

Rate limiting shows up inside many other designs too, such as abuse prevention in a URL shortener and per-user caps in a notification system.