Distributed Rate Limiting

One server, one dict — everything so far assumed that. Now put ten API servers behind a load balancer, each running its own TokenBucket. A client whose requests are spread round-robin sees ten independent buckets: the effective limit is N_servers × limit. Your "100 per minute" is quietly 1,000. Every distributed limiter design is a different answer to one question: where does the shared counter live?

Centralized counter in Redis (fixed window)

Why this survives concurrency: INCR is atomic. Redis executes commands one at a time, so ten servers incrementing simultaneously receive distinct values 1, 2, 3, … — no lost updates — and each server judges the value it got back. Compare the broken version: GET then SET count+1 from two servers means both read 99, both write 100, and one request vanishes from the books.

Two details are load-bearing:

• The window index is baked into the key (now // window). If a server crashes between INCR and EXPIRE, that key leaks — but the next window uses a new key, so decisions stay correct; the TTL is only memory hygiene.
• Cost: one Redis command per request (sub-millisecond inside a VPC), plus a one-time EXPIRE when each window's key is first created.

Token bucket in Redis: the race, and Lua

A token bucket must read two fields (tokens, last), compute the refill, and write both back — a read-modify-write that INCR cannot express. Done naively from two servers with one token left: both HMGET tokens=1, both decide "allow," both write back 0 → two requests admitted on one token. A textbook race condition.

The fix is to make the whole read-compute-write atomic on the Redis side with a Lua script:

-- Atomic token bucket
local tokens, last = redis.call('HMGET', KEYS[1], 'tokens', 'last')
local now = tonumber(ARGV[1])
local rate = tonumber(ARGV[2])
local cap = tonumber(ARGV[3])
tokens = math.min(cap, tonumber(tokens or cap) + (now - tonumber(last or now)) * rate)
if tokens >= 1 then
  tokens = tokens - 1
  redis.call('HMSET', KEYS[1], 'tokens', tokens, 'last', now)
  return 1
else
  redis.call('HMSET', KEYS[1], 'tokens', tokens, 'last', now)
  return 0
end

Redis runs a script single-threaded, start to finish — no interleaving is possible. This is the pattern production limiters such as Envoy's global rate limit service (lyft/ratelimit) run on Redis. Two refinements the minimal script skips: call PEXPIRE inside the script so idle clients' hashes eventually vanish (otherwise memory grows with every client you've ever seen), and don't trust each app server's clock for now — skew between servers distorts the refill; use Redis TIME or one designated clock source. (Cosmetic: modern Redis deprecates HMSET in favor of HSET.)

The cheaper, looser alternatives

• Local counters + periodic sync: each node enforces locally and reconciles every few hundred milliseconds. No per-request network hop, but bursts can overshoot between syncs. Edge networks count this way — per-datacenter, converging asynchronously.
• Static split: give each of N servers limit / N. Zero coordination, but uneven routing produces false denials on hot nodes while budget idles on cold ones.

When Redis is down

Decide before the incident: fail-open (skip limiting; risk overload) or fail-closed (deny everything — congratulations, you built a kill switch for your own API). Most systems fail open and alert loudly.

Your exercise

Write out, by hand, the interleaving that breaks the naive two-step token bucket: servers A and B, one token left — A: HMGET → 1, B: HMGET → 1, A: HSET 0, allow, B: HSET 0, allow — two ALLOWs spent from one token. Then rerun it through the Lua script: script calls serialize, so A's run sees 1 token → ALLOW, and B's run sees 0 (plus the few microseconds of refill, ~0.0001 tokens at 10/s) → DENY. If you can produce both interleavings from memory, you understand distributed rate limiting — the entire discipline is making the second interleaving the only possible one.