Knowledge Guide
Home › Hands-On Builds › SD Design Labs

Design a Distributed Rate Limiter

Design a Distributed Rate Limiter

You already built a rate limiter that is correct on one box: a single lock guards a single token bucket, and the tests prove it holds under concurrency. Ship that exact class to a fleet of app servers behind a load balancer and it quietly stops doing its job — each instance enforces the limit against its own traffic only, and the limit you promised the business ("100 requests/second per client") turns into something nobody agreed to. This is the escalation every senior candidate is expected to make unprompted: local correctness does not imply global correctness the moment you have more than one process. This lab is the HLD worksheet version of that escalation — no code kata, a design workshop with a model answer and a rubric, exactly like the room you'll sit in.

1. The Trap — per-node limits don't add up to the number you promised

Take the token-bucket class from the LLD kata and deploy 10 identical copies, one per app server, each configured with "100 requests/second per client." A load balancer round-robins each client's requests evenly across the 10 nodes. Trace what actually happens to one client hammering the API as fast as it can for one second:

Nothing is "broken" in the code sense — the bug is architectural. A limit enforced independently by N cooperating-but-unaware processes is not a global limit; it's N separate local limits that happen to share a number. The trap widens with fleet size: at 200 nodes the same "100/s" config now permits ~20,000/s. This is the gap between an LLD kata (prove one process is correct) and an SD lab (prove a system of processes is correct) — and it's exactly the "what changes when there's more than one machine" question interviewers use to separate junior from senior answers.

2. Scope it like a senior

Before reaching for Redis, pin down what "correct" means here — the wrong assumption on any of these silently reshapes the whole design:

For the rest of this lab: global exact-enough limit, per-client-key granularity, a shared network hop is acceptable, fail-open for general endpoints, fail-closed for sensitive ones, single-region first (multi-region is the movement-7 escalation).

3. Reason to the design

Simplest thing that could work: keep the per-node token bucket from the LLD kata, unchanged. It fails immediately — that's the trap in movement 1. The bug isn't in the bucket; it's that N independent buckets can never sum to one global number without talking to each other.

Next idea: sticky routing. Hash each client key to exactly one node (consistent hashing at the load balancer), so that client's whole quota lives on one bucket again. This actually works for the accuracy problem — but it trades one bug for three new ones: (a) a hot client key now overloads exactly one node instead of spreading load, (b) that node restarting or being redeployed silently resets or loses the bucket's state, and (c) it doesn't survive a multi-region fleet, where "one node" might not even be reachable from every region. Good instinct, wrong layer — the state needs to live somewhere shared, not be pinned to a single compute node.

Centralize the state. Move the counter out of the app process entirely into a fast shared store all nodes can reach — Redis is the standard choice (sub-millisecond, single-threaded execution model, built-in TTL). Every node, on every request, does one round trip: "increment this client's counter, tell me if it's still under the limit."

The race that centralizing alone doesn't fix. Naively that round trip looks like GET count; if count < limit: SET count+1; allow — two separate Redis calls with a decision made by the app in between. Two requests for the same client arriving within microseconds of each other can both GET the same count (say 99, with limit 100), both decide "under limit," and both SET — two requests admitted when only one slot remained. Centralizing the state didn't remove the race, it just moved it from "across nodes" to "across concurrent connections to the same node's data." This is a classic check-then-act (TOCTOU) bug.

The core mechanism: make the check-and-increment one atomic operation. Redis is single-threaded for command execution, so any single command — or any Lua script run via EVAL — runs to completion with no other client's command interleaved. Do the increment and the comparison inside one EVAL, and the race in the previous paragraph becomes structurally impossible: there is no gap between "read" and "write" for another request to land in. That one property — one atomic round trip per request — is the entire design. Everything from here (movement 4) is about making that round trip cheap enough and available enough at real scale. (Background on the algorithm menu — token bucket vs sliding window vs fixed window — is covered in Rate Limiting Algorithms; this lab assumes you know the algorithms and focuses on the distributed-systems problem of sharing one.)

4. Build it — the design worksheet

This is the movement an LLD kata would spend on dual Java+Go code. A distributed-systems design lab spends it on a worksheet instead: pin the requirements, do the arithmetic, sketch the API and data model, draw the path, then show the one artifact that has to be exactly right — the atomic script.

a) Requirements (from movement 2)

b) Back-of-envelope estimation — arithmetic visible

  1. Scale target: 1,000,000 requests/second peak, fleet-wide, across 5,000,000 distinct client keys.
  2. Naive Redis ops/sec: one EVAL per request, unbatched → 1,000,000 ops/sec.
  3. Redis single-shard capacity: a Lua EVAL costs more than a bare GET/SET (script dispatch overhead) — plan for ~60,000 ops/sec per shard, not the ~100k–150k you'd budget for plain commands.
  4. Shards needed (unbatched): 1,000,000 ÷ 60,000 ≈ 17 → round up to 20 shards for headroom, each with a primary + replica → 40 Redis nodes.
  5. Memory: 5,000,000 keys × ~80 bytes (key + integer counter + TTL bookkeeping) ≈ 400MB total — ~20MB/shard. Trivial; this design is CPU/ops-bound, not memory-bound.
  6. Cut the ops with local batching: instead of one EVAL per request, each node claims a local mini-budget from Redis every N requests (e.g. "give me 20 tokens for this client") and spends it locally between claims. At a batch size of 20: real Redis load drops to 1,000,000 ÷ 20 = 50,000 ops/sec — now a single well-provisioned shard could carry it, though you still keep several shards for hot-key isolation and HA (movement 4d, 4g).

Batching is the lever every strong answer reaches for once the naive number looks too big — and it's exactly what the "how many Redis ops at 1M QPS" pushback in movement 7 is testing whether you'll find unprompted.

c) API sketch

This is an internal middleware/library call, not a client-facing endpoint. Two levels worth sketching:

// Library-level, called from the app-node request pipeline
boolean allow(String clientKey, int cost)   // cost > 1 for expensive endpoints

// Wire-level, if the limiter is its own service (mirrors Envoy's ext_authz-style shape)
POST /v1/ratelimit:check
{ "domain": "api-gateway", "descriptors": [{ "key": "client_id", "value": "abc123" }] }
→
{ "overallCode": "OK" | "OVER_LIMIT", "limitRemaining": 42, "resetAfterSeconds": 1 }

d) Data model & partitioning

e) High-level diagram

The path every request takes, and the one artifact — the Lua script — that makes it correct under concurrency:

Fleet of app nodes fanning into a sharded, replicated Redis cluster via one atomic Lua EVAL per request; allow is a solid green disc, reject is a hollow red ring
Fleet of app nodes fanning into a sharded, replicated Redis cluster via one atomic Lua EVAL per request; allow is a solid green disc, reject is a hollow red ring

f) The atomic artifact — the Lua script

This is the piece that closes the race from movement 3. It is not "a nice-to-have" — it is the entire design:

-- KEYS[1] = rl:{clientKey}:{windowId}
-- ARGV[1] = limit          e.g. 100
-- ARGV[2] = windowSeconds  e.g. 1

local count = redis.call("INCR", KEYS[1])
if count == 1 then
    -- first hit in this window: arm the TTL so the key self-expires
    redis.call("EXPIRE", KEYS[1], ARGV[2])
end

if count > tonumber(ARGV[1]) then
    return 0   -- reject
else
    return 1   -- allow
end

INCR and the comparison happen inside one EVAL, which Redis's single-threaded execution model runs to completion with zero interleaving from any other client's command. There is no separate GET, so there is no gap for a second request to read a stale count — the exact bug traced in movement 3 and re-run as a failing test in movement 5. (An INCR+EXPIRE pair called as two separate commands would reopen a smaller race — a crash between them leaves a key with no TTL. The script is the unit of atomicity, not the individual commands.)

g) Bottlenecks & scaling

Rubric — what a strong answer hits

Model answer: compare your worksheet against Designing an API Rate Limiter, the existing guide page that walks the full RESHADED treatment for this exact problem — use it to check what you missed, not as a first read.

5. Break it — run the design as a test and watch it fail

Design flaw 1 — the naive per-node counters (movement 1), as a test. Fire 1,000 requests for one client key in one second, round-robin across a 10-node fleet, each node locally capped at 100/s. Expected result if the limit were real: ≤100 admitted. Actual result with independent per-node buckets: each node sees ~100 of its own share and admits all of it before any node individually hits its cap — up to 1,000 admitted, 10× over budget. Every node's unit test still passes; the fleet-level test is the one that catches it. This is the design-lab equivalent of "remove the lock and watch the concurrency test fail" from the LLD kata — except here the missing ingredient isn't a mutex, it's shared state.

Design flaw 2 — the non-atomic GET-then-SET, even with centralized state. Centralizing the counter in Redis is necessary but not sufficient. Trace two concurrent requests for the same client at count=99, limit=100:

The fix, traced against the same scenario: replace the two-call GET-then-SET with the single EVAL from movement 4f. Request A's INCR runs to completion (count → 100, allowed) before Redis's single-threaded loop even looks at Request B's command. B's INCR then sees count → 101, which is > limit → rejected. Same two concurrent requests, same timing — correct outcome, because there is no longer a gap between the read and the write for B to sneak into.

6. Optimise — with trade-offs

The Lua-EVAL design in movement 4 is the "centralized exact" point on a spectrum. A strong answer names the neighboring points and says explicitly why it picked one:

ApproachAccuracyAdded latencyState costBest for
Centralized exact (Redis INCR+EXPIRE via Lua)Exact, fleet-wide+1 round trip (~0.5–2ms same-DC)O(1) per keyHard quotas, abuse protection where exactness matters, this lab's baseline
Local-approximate (per-node token bucket + periodic global-budget sync)Approximate, error bounded by fleet-size × sync-interval0 — fully localO(1) per node per keyQPS too high for a synchronous round trip; slight overshoot tolerable (general DoS protection)
Sliding-window-log (Redis sorted set: ZADD+ZREMRANGEBYSCORE+ZCARD)Exact, no fixed-window boundary burstHigher — 3 ops vs 1O(requests in window) per key — expensive at high per-key rateStrict smoothing requirements, moderate per-key QPS
Token-bucket-in-Redis (GCRA / redis-cell)Exact, smooth, burst-awareSimilar to the Lua fixed-window scriptO(1) per key — single timestamp, no counter reset logicProduction APIs wanting burst tolerance and centralized exactness — often the real production answer once you'd otherwise reach for fixed-window
In-memory gossip / no central store (e.g. Envoy local limits + periodic peer sync)Eventually-consistent, approximate0 — synchronous cost is zeroO(1) per nodeScale where even a sharded Redis can't keep up (see "100×" in movement 7)

The fixed-window Lua script earns its place on this page because it's the simplest thing that teaches the atomicity requirement cleanly — in a real production system, GCRA/token-bucket-in-Redis is usually the better default once you'd otherwise reach for fixed-window, because it removes the fixed-window boundary-burst problem (up to 2× limit right at a window edge) for the same O(1) state cost.

7. Defend under drilling

Q1 — "What happens when Redis is down?"
A circuit breaker trips after N consecutive failures/timeouts. For general endpoints: fail-open onto a conservative local per-node budget (globalLimit / fleetSize, biased down) — some accuracy is lost but the service stays up. For sensitive endpoints (auth, payments): fail-closed — reject rather than risk unbounded load with zero protection. This is a per-endpoint policy decision, not one global answer, and saying so is the point.

Q2 — "One client key just went viral and every check for it hits the same shard — now what?"
That's the hot-key bottleneck from 4g. Two concrete levers: local batching (claim a mini-budget of tokens per Redis call instead of one call per request, cutting that key's Redis load by the batch factor) and splitting the logical counter into K physical sub-counters summed at read time, trading a bounded amount of over-admission for spreading the write load off a single shard. See Rate-Limit Hot Keys for the full derivation.

Q3 — "Does clock skew across nodes break this?"
No — and that's a direct consequence of centralizing the state. Redis is the sole authority on "which window is this," computed server-side inside the Lua script; app nodes never need synchronized clocks because none of them decide the window boundary locally. Clock skew only becomes a live concern if you fall back to the local-approximate design (movement 6), where each node's own clock drives its local bucket — there, skew affects how evenly each node's share of the budget refills, not global correctness.

Q4 — "When is exact wrong to insist on?"
When the QPS math (4b) says exact costs more round trips than you can afford, and the business impact of a client occasionally getting 105/s instead of 100/s is negligible — abuse protection and DoS mitigation, not billing. Insisting on exact everywhere is itself a design smell if it forces an architecture (a synchronous call on every single request) that can't hit the latency or throughput target.

Q5 — "At 1M QPS fleet-wide, how many Redis operations per second, and how do you keep that from being a wall?"
Naively: 1M ops/sec, one EVAL per request (4b, step 2). Batching tokens locally in groups of 20 cuts that to 50,000 ops/sec (4b, step 6) — well within one well-provisioned shard's headroom, with several shards kept anyway for hot-key isolation and HA rather than raw throughput.

Escalation — what breaks at 100× (100M QPS)? Even with 20:1 batching that's 5,000,000 Redis ops/sec — on the order of 100 shards just for throughput, which starts to make cross-shard hot-key skew and replica-lag-during-failover materially worse, not just theoretically possible. At this scale the honest answer shifts: stop insisting on synchronous-exact everywhere and move the bulk of enforcement to the local-approximate or gossip model (movement 6's rightmost rows), reserving the centralized-exact Redis path only for the subset of endpoints (Q4) that actually need it. This is also where multi-region enters for real — a single Redis Cluster stops being "just add shards" once nodes span regions with real network latency between them; see Multi-Region Rate Limiting for how that changes the design (per-region local limiters with async global reconciliation, rather than one global synchronous store).

The pairs_with move: if you're asked this cold in an interview, say the LLD-to-HLD escalation out loud — "single-process token bucket (build it first) is correct but doesn't survive more than one machine; here's what changes and why" — that's exactly the arc this lab walked movements 1 through 4.

8. You can now defend

Re-authored/Deepened for this guide.

🤖 Don't fully get this? Learn it with Claude

Stuck on Design a Distributed Rate Limiter? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🎨 Explain it visually

Build the mental picture, not memorization.

I just read a lesson on **Design a Distributed Rate Limiter** (Hands-On Builds) and want to truly understand it. Explain Design a Distributed Rate Limiter from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🤔 Walk me through it (interactive)

Socratic — adapts to where you're stuck.

Teach me **Design a Distributed Rate Limiter** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🧪 Quiz me & fix my gaps

Active recall exposes what you missed.

Quiz me on **Design a Distributed Rate Limiter** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🧠 Make it stick

Intuition + hook + flashcards for long-term memory.

Help me remember **Design a Distributed Rate Limiter** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Design a Distributed Multi-Garage Design Ledger Reconciliation →