A distributed rate limiter

1 · Clarifying questions

2 · Capacity math, on a napkin

The math says one Redis cluster easily handles 50K QPS — even with no local pre-deduction. The local-cache-with-sync pattern below is for two reasons: (1) shave the 0.5–1 ms RTT from the hot path, (2) keep working when Redis is unhappy.

3 · API and data model

Limiter check (RPC, called by the gateway)

# Check + atomically deduct
RateLimit.Check(key, n=1) → { allowed, remaining, reset_at }

# A request matches multiple rules — check each in order; deny on first deny.
# Example rules for a single request:
# ip:1.2.3.4 rate=1000/min capacity=2000
# user:u_abc rate=100/min capacity=200
# user_endpoint:u_abc:POST /v1/posts rate=10/min capacity=20

# Response when blocked:
HTTP/1.1 429 Too Many Requests
RateLimit-Limit: 100
RateLimit-Remaining: 0
RateLimit-Reset: 12 # seconds until next token
Retry-After: 12

Storage

# Token bucket state, per (rule, key) pair
# Lives in Redis; sharded by hash(rule:key)

bucket:rule_id:key_hash → {
 tokens: FLOAT, # current token count
 last_refill: TIMESTAMP, # last refill time (ms)
 capacity: INTEGER, # max tokens
 rate: FLOAT # tokens / second
}
TTL: 2 × window # auto-expires when key goes cold

# Rule definitions live in config (etcd / consul), pushed to gateways.
rules → {
 rule_id: "ip-default",
 match: {dimension: "ip", scope: "global"},
 rate: 1000,
 per: "minute",
 capacity: 2000,
 on_fail: "fail_open" | "fail_closed",
 enabled: true
}

4 · The four algorithms, ranked

Use token bucket. It models the product behaviour most engineers actually want — "you can do up to N per second, with a burst budget of M". Sliding window counter is a fine alternative when bursts are not allowed.

5 · The hard part — distributed atomicity

Two gateway pods see two requests for the same user simultaneously. They both read the bucket, both find 1 token, both write back 0 tokens, both allow. Counter under-counts; user gets to send 2 instead of 1.

The fix is atomic check-and-decrement. Three options:

The Lua script

-- KEYS[1] = bucket key
-- ARGV[1] = capacity
-- ARGV[2] = refill rate (tokens/sec)
-- ARGV[3] = now (ms since epoch)
-- ARGV[4] = requested tokens (default 1)

local bucket = redis.call("HMGET", KEYS[1], "tokens", "last")
local tokens = tonumber(bucket[1]) or tonumber(ARGV[1])
local last = tonumber(bucket[2]) or tonumber(ARGV[3])

local elapsed = (tonumber(ARGV[3]) - last) / 1000.0
tokens = math.min(tonumber(ARGV[1]), tokens + elapsed * tonumber(ARGV[2]))

local need = tonumber(ARGV[4])
local allow = (tokens >= need) and 1 or 0
if allow == 1 then tokens = tokens - need end

redis.call("HMSET", KEYS[1], "tokens", tokens, "last", ARGV[3])
redis.call("EXPIRE", KEYS[1], 60)
return { allow, math.floor(tokens) }

~25 lines, runs in ~50 µs on the Redis main loop. The atomicity is "Redis processes one Lua call at a time on a single shard" — exactly what we need.

6 · The local-cache-with-sync pattern

The Lua call adds 0.5–1 ms of network RTT to every API request. At 50K QPS, that's a lot of round-trips. The optimisation: each gateway pod holds a local "lease" on a fraction of each user's tokens, and only goes to Redis when its lease runs out.

1. On first request for user U: pod calls Redis, reserves K tokens (e.g., 10), gets back { tokens, leaseExpires }.
2. On subsequent requests: decrement the local lease in process memory. No network call.
3. When lease runs out or expires: ask Redis for K more.
4. On pod shutdown: return remaining lease tokens.

Trade-off: a pod crashing loses its in-flight lease — users effectively get a small burst they didn't earn. Bound the loss by leasing small chunks (5–10 tokens) and short TTLs (1–5 s).

7 · Hot-key sharding

Some keys are very hot — the IP rule for a NAT gateway, the API key for a popular downstream service. Single-shard hot-keying causes one Redis node to saturate while the others idle.

8 · Fail-open vs fail-closed

When the limiter itself fails (Redis down, network partition), what does the gateway do? The two answers solve different problems.

• Fail-open (allow). Use for fairness rules — "you get 100/min". Brief overshoot is fine; refusing all traffic is worse than serving a bit too much.
• Fail-closed (block). Use for anti-abuse rules — "users with this auth get 1/sec". A flood while the limiter is down is worse than blocking briefly.

Make this per-rule, not per-system. The right rule design specifies on_fail explicitly, not by convention.

9 · Failure modes & runbook

10 · Cost & SLOs

SLOs

• P99 added latency: 5 ms. 80% local cache hit + 1 ms Redis budget for the rest.
• Availability: 99.99%. Per-rule fail-open/closed dictates what "available" means.
• Configuration propagation: P99 ≤ 60 s. Rule changes reach all gateways within a minute.
• Accuracy: ≤ 5% drift over a 60-second window. Local-cache-with-sync trades exact accuracy for latency; bound the drift in the SLO.

11 · Trade-offs & "what would you change at 10×"

Further reading

• Stripe — "Scaling your API with rate limiters". The canonical engineering writeup. Token bucket, fail-open semantics, the operational details.
• Cloudflare — "How we built rate limiting capable of scaling to millions of domains". The CDN-edge view; useful for the highest-scale shape.
• GitHub — "GitHub's Engineering Team Has Joined Slack" — actually, look up "How we built the GitHub.com rate limiter". A different shape (per-API-key) at meaningful scale.
• Lyft Engineering — "Envoy's local rate limiting". The colocated-on-the-gateway design point — useful counterpoint.
• Marc Brooker — "Exponential Backoff and Jitter". The client-side companion to a rate limiter. Without jitter, retries synchronise and re-saturate.
• RFC draft 9 — "RateLimit Header Fields for HTTP". The standard headers; use them so clients can be polite back.
• Adjacent: API gateway. Where the limiter actually lives.
• Adjacent: Redis. The substrate.