Q63 — Design a rate limiter from scratch

What the system must do

A rate limiter enforces a policy: "this client (user, IP, API key) may make at most N requests per time window." Requests that exceed the limit are rejected (HTTP 429 Too Many Requests) before reaching the backend.

Why it exists: prevents abuse (credential stuffing, scraping, DDoS), protects backend services from overload (Q32's backpressure at the edge), enforces business-tier limits (free plan: 100 req/day, pro plan: 10,000 req/day).

Key questions to settle before designing:

What is the rate limit unit? Per user? Per IP? Per API key? Per endpoint?
What is the window? Per second? Per minute? Per day? Sliding or fixed?
Where does the limiter run? At the API gateway? In each service? Centralized?
What happens on limit hit? Reject immediately? Queue the request?

Four algorithms (already covered in Q31, now applied to full system design)

Fixed window: count requests in a fixed time window (this minute, this hour). Simple, but the boundary problem: a client can burst 2N requests across a window boundary (N in the last second of minute 1, N in the first second of minute 2) and get double the intended rate.

Sliding window log: track the exact timestamp of every request in a sorted set. On each request, remove timestamps older than the window, count what remains, compare to limit. Accurate but memory-expensive — you store one entry per request.

Sliding window counter: divide the window into smaller buckets (e.g., 60 one-minute buckets for an hour limit). Approximate the sliding window by weighting the current bucket and the previous one by how much of the window each covers. Memory-efficient, nearly as accurate as the log approach.

Token bucket: a bucket fills at a constant rate (the rate limit) up to a maximum capacity. Each request consumes one token. If the bucket is empty, the request is rejected. Allows bursts (up to the bucket capacity) while enforcing average rate. Natural fit for APIs where occasional bursts should be allowed.

Leaky bucket: requests enter a queue and are processed at a constant output rate. If the queue is full, excess requests are dropped. Enforces strict throughput at the cost of adding latency for requests that wait in the queue.

For most API rate limiting: token bucket (allows controlled bursts) or sliding window counter (smooth, accurate). Token bucket is the practical standard.

Where rate limit state lives — the central question

A rate limiter is useless if each application server maintains its own counter. With 10 servers behind a load balancer, each server sees 1/10 of the traffic — locally, each thinks the client is within its limit, while globally the client has exceeded it by 10x.

Rate limit state must be centralized. Redis is the canonical solution:

Atomic operations (INCR, EXPIRE, Redis transactions, Lua scripts) allow safe concurrent updates from multiple servers
Sub-millisecond latency doesn't meaningfully slow the request path
Redis can handle millions of counter updates per second

For a token bucket in Redis:

code

-- Lua script executed atomically
local tokens = redis.call('GET', key)
if tokens == false then
    tokens = rate_limit  -- initialize full bucket
end
tokens = tonumber(tokens)
if tokens < 1 then
    return 0  -- rejected
end
redis.call('SET', key, tokens - 1, 'EX', window_seconds)
return 1  -- allowed

Lua scripts in Redis run atomically — no race conditions between the read-check-decrement sequence.

Fixed window counter implementation in Redis

This is the most common practical approach for per-minute/per-hour limits (it is a fixed window — one counter per calendar minute; the sliding versions are below):

code

key = "rl:{user_id}:{current_minute}"

-- one atomic Lua script, so the key can never exist without a TTL
count = EVAL "local c = redis.call('INCR', KEYS[1])
              if c == 1 then redis.call('EXPIRE', KEYS[1], 60) end
              return c" 1 key

if count > limit:
    reject

Why the script: sent as two separate commands, a crash or timeout between INCR and the "first increment only" EXPIRE leaves a counter with no TTL. It never resets and that user is rate-limited forever. (An equivalent fix: SET key 0 EX 60 NX, then INCR key — INCR keeps the existing TTL.)

One Redis key per user per minute, auto-expiring. At 1M active users, this is 1M keys at any time — trivially small for Redis.

For a true sliding window: use a sorted set where the score is the request timestamp, add each request with ZADD, remove old entries with ZREMRANGEBYSCORE, count remaining with ZCARD. More accurate, higher memory cost.

Distributed rate limiting — the coordination problem

At global scale (multiple data centers), centralized Redis creates a problem: a rate limit check in us-east must round-trip to the Redis cluster, which might add 50ms of cross-region latency on every request. Unacceptable.

Solution: local approximate limiting + global correction.

Each edge node (API gateway in each region) maintains a local counter in memory, synced with the global Redis counter periodically (every 100ms or every N requests). Locally, the node makes fast decisions. Globally, the counters are eventually consistent.

This means a client can exceed the limit slightly during the sync window — the rate limiter is approximate, not exact. For most rate limiting purposes (abuse prevention, rough tier enforcement), slight over-allowance is acceptable. If strict exactness is needed (billing, hard quota enforcement), synchronous global state is required.

Alternatively: partition rate limits by region ("100 req/min globally, enforced as 30 req/min per region" for 3 regions with some slack). Simpler but less flexible.

What to return on rate limit rejection

code

HTTP 429 Too Many Requests
Retry-After: 30              # seconds until the next window
X-RateLimit-Limit: 100      # the limit
X-RateLimit-Remaining: 0    # how many requests left
X-RateLimit-Reset: 1710086400  # Unix timestamp when the window resets

Clients that respect Retry-After back off correctly. Well-behaved clients check X-RateLimit-Remaining and self-throttle before hitting 429. This reduces hammering on near-limit traffic.

Rate limiter placement

API gateway (best for most cases): the limiter runs before requests reach any backend service. One central enforcement point. Works across all services automatically. Add rate limiting logic once, apply everywhere.

Per-service: each service enforces its own limits. More granular (different limits per service), but requires the limiter to be implemented in every service. Useful when services have very different limit policies.

Client-side: in SDKs, the client self-throttles. Unreliable — clients can be malicious or misconfigured. Never the only layer.

The mental model

code

Rate limiter = enforce "at most N requests per window per client"
  Client = user_id, API key, IP, or combination

Algorithms:
  Fixed window: simple, boundary exploit vulnerability
  Token bucket: allows bursts (capacity), enforces average rate — practical standard
  Sliding window counter: accurate, memory-efficient, no boundary problem
  Leaky bucket: strict throughput, adds latency for waiting requests

State must be centralized: Redis
  INCR + EXPIRE in one Lua script = fixed window counter (never two separate commands)
  Lua scripts = atomic read-check-decrement (token bucket, sliding window)
  ~1ms latency — acceptable in request path

Implementation (fixed window, per minute):
  key = "rl:{user_id}:{minute_bucket}"
  Lua: INCR → count; if count == 1: EXPIRE 60 (atomic, so no TTL-less keys)
  count > limit → 429

Distributed rate limiting:
  Cross-region central Redis = 50ms latency = unacceptable
  Solution A: local counter + periodic global sync → approximate
  Solution B: per-region quota partition → simpler, less flexible

Response on 429:
  Retry-After, X-RateLimit-Limit, X-RateLimit-Remaining, X-RateLimit-Reset

Placement: API gateway (single enforcement point, all services covered)

Key trade-off: exact global limiting requires synchronous coordination (latency cost)
               approximate limiting allows brief overages (acceptable for most use cases)

A rate limiter's design reduces to two questions: which algorithm (what shape of traffic do you allow?), and where does state live (how do you enforce globally without adding intolerable latency?). Everything else is tuning.