Design a distributed rate limiter

An API that accepts every request it is sent has no defence against one client with a loop. A rate limiter decides, before any expensive work happens, whether this request counts against a quota already spent. The counting is arithmetic; the design problem is keeping one honest count across dozens of app servers without taxing every request, and knowing exactly how wrong the cheap answers are.

Step 1 — Requirements

Functional:

• Limit per identity: API key for authenticated traffic, user ID where a session exists, source IP only as a last resort — everyone behind a NAT shares an IP, so an IP limit punishes an office rather than an abuser.
• Rules are configuration, not code: free tier 100 requests/minute, paid tier 10,000/minute, writes tighter than reads. Changing one customer's limit must not need a deploy.
• Reject with a status the client can act on, and say when to come back.

Non-functional:

• Added latency at p99 under 2 ms: the limiter runs on allowed requests too, so its cost taxes the whole API.
• Correct enough that a customer cannot quietly take 3x its paid limit.
• The limiter failing must not take the API with it, and rejecting must cost far less than serving.

Out of scope: volumetric DDoS absorption, which belongs at the edge in front of this (CDN), and monthly billing quotas, which are durable accounting and belong in a database, not a cache with a TTL.

Step 2 — Scale, memory, and the latency budget

Assume 100 million API requests/day. 100,000,000 ÷ 86,400 s ≈ 1,160 QPS average; peak at 3x is roughly 3,500 QPS. Every request needs exactly one decision, so limiter throughput equals API throughput — there is no hit rate to hide behind.

Assume 1 million keys active inside any 60-second window. Memory per key, at round Redis overheads:

• Fixed window counter: one integer plus key overhead, ~100 B → 1M x 100 B = 100 MB.
• Sliding window counter: two integers, ~200 B → 200 MB.
• Token bucket: a hash of two fields, ~150 B → 150 MB.
• Sliding window log at a 100/minute limit: 100 sorted-set entries at ~64 B = 6.4 KB per key → 1M x 6.4 KB = 6.4 GB.

The log costs 30 to 60 times every other option, and that ratio is the whole argument.

One round trip inside a datacenter is 0.5 ms (network fundamentals). Redis runs an INCR or a small script in tens of microseconds, so the hop dominates and the limiter costs one round trip: 0.4% of an endpoint with a p99 of 120 ms, 10% of one with a p99 of 5 ms. Which of those you have, not a general principle, decides whether the centralised design is affordable.

Little's Law sizes the pool: 3,500 QPS x 0.5 ms = 1.75 requests in flight against Redis across the whole fleet, under one connection per app server, so a pool of 8 absorbs jitter rather than throughput. One Redis instance handles order 100,000 simple operations/second, so peak is 4% of one box: one instance plus a follower for failover, and no sharding until traffic grows 10x — and it shards cleanly then, since no decision touches two keys.

A distributed rate limiter at the gateway with shared Redis counters and a local fallback100%−+FitSVGEsc

Scroll to zoom · drag to pan · 0 fits · Esc closes

Step 3 — The design

Fixed window, and the 2x burst it permits

Count into a bucket named by the truncated minute; reset at the boundary. One INCR, one TTL.

Work the failure at a limit of 100/minute. A client sends 100 requests between 10:00:59.0 and 10:00:59.9 — bucket 10:00 hits exactly 100, all allowed. At 10:01:00.1 the counter is a fresh key at zero, so another 100 in the next 900 ms are allowed too. That is 200 requests in 1.1 seconds, and 200 in any trailing 60-second window straddling the boundary: double the configured limit. Size downstream for 2x what the config says, or the limit is a claim you cannot keep.

Sliding window log, exact and expensive

Store the timestamp of every accepted request in a sorted set scored by time. Per request, drop entries older than now - 60 s, count what remains, admit if under the limit. No boundary artefact, because there is no boundary.

The cost is the 6.4 GB above, plus per-request work proportional to the expired entries rather than O(1). It is right when the limit is small and exactness is a security property: 5 password resets per hour is 5 x 64 B = 320 B per key, and the memory objection disappears.

Sliding window counter, the practical compromise

Keep the current and previous fixed-window counters and interpolate by how far into the current window we are:

elapsed_fraction = seconds_into_current_window / window_seconds
estimate = current_count + previous_count * (1 - elapsed_fraction)

Limit 100/minute, request at 10:01:15. elapsed_fraction = 15/60 = 0.25, so the trailing minute still covers the last 75% of window 10:00. With previous_count = 80 and current_count = 30:

estimate = 30 + 80 x 0.75 = 90 → under 100, admit. Ten more requests in that second bring the estimate to 100 and the next is rejected.

The formula assumes the previous window's requests were spread uniformly. If those 80 all landed in its first 10 seconds, the true trailing count is 30 and we have just rejected 70 legitimate requests. The error is bounded by the previous count and shrinks to zero as the window fills. Cloudflare reported a misclassification rate in the low thousandths of a percent on real traffic — small enough that the 32x memory saving wins for ordinary API limits.

Token bucket, bursts on purpose

A bucket holds up to C tokens and refills at r tokens/second; each request spends one. Sustained rate is r, and a client idle for C/r seconds can spend C at once. With C = 100 and r = 10/s: 600/minute sustained plus a 100-request burst, and an empty bucket refills in 100 ÷ 10 = 10 s.

Refill lazily — a timer per key means a million ticks per interval. Store the token count and last-refill timestamp, and do the arithmetic only on requests that arrive.

-- Runs atomically as one Redis script. KEYS[1] is the bucket key.
-- capacity = 100 tokens, refill = 10 tokens/second, cost = 1 per request
-- `now` is passed in by the caller so the script stays deterministic.

tokens, last = HMGET(key, "tokens", "ts")

if tokens == nil then
    tokens = capacity          -- new key: start full
    last   = now
end

elapsed = max(0, now - last)
tokens  = min(capacity, tokens + elapsed * refill)

if tokens >= cost then
    tokens  = tokens - cost
    allowed = true
else
    allowed = false
end

HSET(key, "tokens", tokens, "ts", now)
EXPIRE(key, ceil(capacity / refill) + 60)   -- idle buckets evict themselves

retry_after = allowed and 0 or ceil((cost - tokens) / refill)
return { allowed, floor(tokens), retry_after }

Passing now in keeps the script deterministic and safe to replicate, at the cost of trusting app-server clocks. Skew of tens of milliseconds is irrelevant against a 60-second window, and stops being irrelevant the day someone sets a 100 ms one.

Leaky bucket, smoothing rather than rejecting

Requests enter a fixed-size queue drained at a constant rate, so output is exactly r/second whatever the input shape and bursts become delay instead of rejection. Use it when the protected thing cannot absorb a burst at all: a third-party API with a contractual rate, or a backend with a fixed concurrency ceiling.

The cost is that delay: a 100-slot queue draining at 10/s makes the last admitted request wait 100 ÷ 10 = 10 s holding a connection open. Immediate rejection is better for everyone there, so leaky bucket belongs in front of an async worker pool or an egress client, not a browser.

Algorithm	Memory at 1M keys	Burst behaviour	Accuracy
Fixed window	~100 MB	Allows 2x the limit at the boundary	Poor at boundaries, exact within a window
Sliding window log	~6.4 GB	None, hard ceiling	Exact
Sliding window counter	~200 MB	Smoothed, no 2x edge	Approximate, error bounded by the previous count
Token bucket	~150 MB	Burst up to capacity, by design	Exact for the rate it defines
Leaky bucket	~150 MB plus queued items	None, bursts become delay	Exact output rate, adds latency

Token bucket is the default production answer: O(1) memory, one round trip, a burst allowance that matches how real clients behave. Sliding window counter wins when the contract literally says "N per minute" and a burst would be a surprise.

Sharing the counter across app servers

Centralised Redis. Every app server runs one atomic operation against one shared counter: one clock, one answer, for 0.5 ms and a hard dependency (caching infrastructure).

Local counters with periodic sync. Each server counts in memory and pushes deltas every 500 ms. Added latency is effectively zero, but every decision uses a count up to one interval stale. Quantify it: 20 servers, 500 ms sync, a client pushing 50 req/s against a 100/minute limit. Each server sees 50 ÷ 20 = 2.5 req/s, so it admits 2.5 x 0.5 = 1.25 on a stale count and the fleet over-admits about 20 x 1.25 = 25 — a 25% overshoot. Sync every 100 ms and that falls to roughly 5, at 5x the sync traffic.

Dividing the limit by the server count (100 ÷ 20 = 5 each) breaks the moment traffic is uneven: a client whose connections land on 3 of 20 servers gets 15 of its 100 and sees rejections it did not earn. That works only if the load balancer hashes on the key the limiter counts.

Choose centralised when the limit is a billing boundary; local plus sync when it only protects capacity and 25% overshoot changes nothing. That is PACELC inside one component: during a partition between an app server and Redis, choose availability (admit and over-count) or consistency (reject and stay correct); else, with no partition, choose latency (local counters) or consistency (the shared hop).

The read-modify-write race

The obvious implementation is broken. Server A runs GET count and reads 99; server B reads 99. Both compare against a limit of 100, both SET it to 100, both admit. 101 requests went through and the counter claims 100.

The window is the two round trips of the read-modify-write cycle, about 1 ms. Little's Law says a hot key at 500 QPS has 500 x 0.001 = 0.5 requests inside that window at any moment, so at the boundary collisions are the normal case. This is an ordinary lost update (concurrency); the fix is an indivisible decision, not a mutex.

count = INCR(key)      # atomic; returns the value after incrementing
if count == 1:         # first request in this window
    EXPIRE(key, 60)
allowed = count <= limit

INCR returns the post-increment value, so no two callers read the same number and the decision is one round trip. The snippet still has a bug: INCR and EXPIRE are two commands, and if the process dies between them the key has no TTL and that customer is limited forever. Either use SET key 0 EX 60 NX then INCR — the SET is a no-op after the first request and the TTL arrives with the key — or use a Lua script, which Redis runs atomically so counter, TTL and decision share one round trip and one failure unit. Token bucket has no single-command form, so it must be a script.

Where the limiter lives

API gateway. One place, one config, and rejection happens before the request reaches service code, so a 429 costs a counter lookup and nothing else. It cannot see per-endpoint cost. The default (API gateways).

Application middleware. Full context: charge a search 10 tokens and a health check 0, and read the authenticated principal. The price is that every service configures its own limiter, and the request has already crossed the network and been parsed before it is thrown away.

Sidecar. A proxy in each pod checks over loopback, dropping the hop from 0.5 ms to well under 100 µs when the counter is local, for another process per pod and a mesh to operate.

Production usually runs both: coarse per-key limits at the gateway, fine limits inside the service for the few genuinely expensive endpoints.

The response

Return 429 Too Many Requests, never 503. A 503 says the service is broken when the truth is the client is over quota, and generic retry logic treats 503 as immediately retryable.

Carry back Retry-After: 12 in seconds — from a token bucket exactly (cost - tokens) / refill, from a fixed window the seconds left in the window — plus RateLimit-Limit, RateLimit-Remaining and RateLimit-Reset on every response, not only rejections. A client that sees 4 of 1,000 calls remaining slows itself down; one that first learns at the 429 has already sent the burst and is about to send it again. Without Retry-After, clients retry on the same schedule and synchronise into a herd at the boundary, so publish the number and require jitter on top.

Step 4 — Failure modes and wrap-up

Redis unreachable. Wrap the call in a 5 ms timeout — 10x the expected 0.5 ms — behind a circuit breaker. For a limiter protecting capacity, fail open onto a local per-server limit of roughly limit / servers x 2: brief over-admission beats rejecting paying customers, and the cushion stops a stampede. For login, fail closed — unlimited password attempts is a security incident and a short outage is not.

One very hot key. A key taking 50,000 QPS cannot be sharded, because it is one counter. Pre-check locally at each server's share of the rate and consult the shared counter only near the boundary.

Clock skew. Token bucket and both sliding windows are time-dependent, so keep one timestamp source and know your skew.

Decision	Cheap option	Correct option	Take the cheap one when
Algorithm	Fixed window, ~100 MB, one INCR	Sliding window log, ~6.4 GB, exact	The 2x boundary burst fits downstream headroom
Counter location	Local plus 500 ms sync, ~0 ms added	Centralised Redis, 0.5 ms added	Limits protect capacity, not billing, and 25% overshoot is fine
Update	GET then SET, two round trips	INCR or Lua, one atomic round trip	Never — the race is real at any load
Placement	Gateway only	Gateway plus per-endpoint middleware	Endpoint costs sit within an order of magnitude
Store down	Fail open	Fail closed	The limiter guards capacity rather than credentials

In an interview

The interviewer is testing whether you see that a rate limiter is a shared-mutable-state problem in a simple costume. Anyone can name five algorithms; the signal is the arithmetic and the concurrency.

Say the numbers out loud. "100 million requests/day is about 1,200 QPS average, 3,500 at peak. A Redis round trip is 0.5 ms — 0.4% of a 120 ms p99 endpoint but 10% of a 5 ms one, so I want to know which we have before putting it in the hot path." Then commit: token bucket in Redis, one Lua script per decision, gateway placement, 429 with Retry-After and quota headers on every response.

Two mistakes lose points reliably. First, describing GET, compare, SET without noticing the race — and reaching for a distributed lock rather than an atomic increment buys a round trip and a failure mode to solve what INCR solves for free. Second, calling fixed window "good enough" without saying it admits 2x at the boundary; the number proves you thought about it.

Volunteer the failure mode before you are asked: "if Redis is down I fail open onto a local cushion, except on login where I fail closed" shows you know the limiter is itself a dependency.

Check yourself

1. A customer's limit is 5,000 requests/minute. You run 40 app servers with local counters syncing every 250 ms, and the customer pushes a steady 2,000 req/s. How far over can they get, and would you accept it?

Each server sees 2,000 ÷ 40 = 50 req/s, so it admits about 50 x 0.25 = 12.5 requests on a count one interval stale. Across the fleet that is 40 x 12.5 = 500 beyond the limit — roughly 10% overshoot on 5,000. Accept it if the limit protects backend capacity; reject it, and move to a centralised counter, if 5,000 is what the contract sold them.

2. An internal endpoint has a p99 of 8 ms and peaks at 200 QPS. Justify centralised Redis or reject it, with numbers.

Latency: 0.5 ms on 8 ms is a 6% p99 increase. Capacity: 200 QPS x 0.5 ms = 0.1 concurrent requests against Redis by Little's Law, so throughput and pool size are non-issues. Take the hop unless 8 ms is a hard SLO with no room, in which case move the counter into a sidecar for under 100 µs of loopback.

3. Which algorithm limits password resets to 5 per hour per account, and what does it cost?

Sliding window log. Exactness is a security property here, and the memory objection vanishes at this limit: 5 entries x 64 B = 320 B per account, so a million accounts is 320 MB — and only accounts that actually attempted a reset hold a key. Fail closed if the store is unavailable.