Designing a Distributed Rate Limiter: Local Buckets, Global Truth

Rate limiting as an algorithm is a solved flashcard: token bucket, sliding window, done. Rate limiting as a system starts with an unpleasant question the flashcard hides: your API tier is fifty stateless gateway nodes behind a load balancer, the limit is "100 requests/second per API key," and a key's requests spray across all fifty nodes. Where does the counter live? Every answer is wrong in a different way, and the design skill is choosing your wrongness deliberately.

Requirements

Enforce per-key/per-user/per-endpoint limits across a horizontally scaled gateway fleet; decision latency ~1ms (it sits in front of everything); limits from 1/s to 100K/s; graceful behavior when the limiter itself degrades; useful rejection responses (429 + Retry-After).

The centralized answer: Redis, atomically

The baseline that works: counters in Redis (sharded by key), checked per request. The classic bug at this layer is the read-modify-write race — GET, decide, INCR as separate commands lets two concurrent requests both pass on the last token. The fix is making the decision atomic inside Redis with a Lua script (or Redis functions):

-- token bucket, atomic: KEYS[1]=bucket, ARGV = {rate, burst, now}
local tokens = tonumber(redis.call('HGET', KEYS[1], 't') or ARGV[2])
local last   = tonumber(redis.call('HGET', KEYS[1], 'ts') or ARGV[3])
tokens = math.min(ARGV[2], tokens + (ARGV[3] - last) * ARGV[1])
if tokens < 1 then return 0 end
redis.call('HSET', KEYS[1], 't', tokens - 1, 'ts', ARGV[3])
redis.call('PEXPIRE', KEYS[1], 60000)
return 1

Token bucket over fixed windows for the standard reason — fixed windows admit 2× bursts at boundaries; the bucket's burst parameter makes the burst policy explicit instead of accidental. TTLs keep the keyspace from accumulating one hash per key-that-ever-existed.

This design is correct and has two costs: a network round-trip on every request (~0.5-1ms, in front of everything), and Redis as a critical-path dependency with a hot-shard problem (one enormous customer = one hot key — familiar medicine applies).

The distributed answer: lie a little, locally

The insight that unlocks the better design: rate limits are not invariants, they are pressure valves. Nobody's data corrupts if a key gets 104 requests in a second against a limit of 100. Once you say that out loud, you can buy latency with bounded error:

each gateway node: local token bucket per key, budget = share of global limit
async sync loop (every 50-200ms): report usage to central store,
                                  rebalance shares by observed demand

Requests hit only node-local memory — nanoseconds, no network. The error is bounded by the sync interval: a key can exceed its limit by at most (burst headroom × nodes) between syncs. Demand-weighted rebalancing handles the skew case (all of a key's traffic landing on three of fifty nodes): nodes that see demand get bigger shares, idle nodes shrink toward zero, converging within a few sync rounds.

The honest framing for the interview: the centralized design is exactly correct and pays latency per request; the local design is approximately correct and pays with a tolerance band. Tier it — cheap local pre-filter in front (kills the flagrant abuse at zero cost), authoritative shared bucket behind it for keys near their limit — and you get both properties where each matters. Cloudflare and every large gateway run some version of this two-tier shape.

Failure policy is a product decision

The limiter will degrade — Redis partition, sync loop stalling. Two choices, both defensible, never accidental:

• Fail open: limiter unreachable → allow. Availability of the API preserved; abuse window opens. Right default for revenue-serving APIs with other abuse backstops.
• Fail closed: deny (or clamp to conservative local limits). Right for expensive/destructive operations — password attempts, SMS sends, LLM inference.

The refined version: fail open with local fallback buckets at conservative rates — degraded mode is "each node enforces a pessimistic share alone," so a Redis outage costs precision, not protection. Also: rejection is API surface — 429 with Retry-After and rate-limit headers (X-RateLimit-Remaining/Reset) turns well-behaved clients into cooperating backoff participants; silence turns them into synchronized retry storms (pair with jitter guidance in your SDKs).

Placement and layering

Real deployments run limits at multiple radii, and each layer catches what the previous can't:

Layer	Granularity	Catches
CDN/edge	IP, coarse	Volumetric floods before they cost you compute
Gateway	API key, endpoint	Quota enforcement, tenant fairness (this post's system)
Service-local	per-instance concurrency	Overload protection regardless of who's asking — the load-shedding cousin

The gateway tier is also where quota semantics live (monthly plans, spike allowances) — same buckets, longer windows, durable counters (a monthly quota can't live in volatile memory; it's a small ledger, and idempotent increment matters because gateway retries shouldn't double-charge a request).

Interview probe	Answer sketch
Exactly 100, never 101?	Then it's not a rate limit, it's a semaphore — centralized atomic path only, pay the latency
Clock skew across nodes?	Buckets use each node's monotonic clock for refill; shares sync by interval, not timestamps — skew shifts error bands, doesn't break correctness
One key = 80% of traffic?	Hot-key handling: dedicated shard or fully-local shares for that key; detect via top-K sketch
Why not sticky-route each key to one node?	It works until one key exceeds one node's capacity — and you've rebuilt the hot-partition problem in your load balancer

The transferable lesson: classify every "limit" by whether it protects an invariant (inventory, money — must be exact, centralize it) or applies pressure (rate limits, fairness — bounded error is fine, localize it). Systems that get this backwards are either slow everywhere or wrong where it counts.