System design deep dive14 min read

Distributed Rate Limiter

A rate limiter is the one component that touches every single request before any useful work happens. That position is what makes it both critical and dangerous: if it is slow, the whole API is slow; if it is down, the whole API can be down; if it is wrong, you either let an abusive botnet through or you throttle your paying customers. The job sounds trivial — count requests per key, reject past a threshold — but the moment you put it in front of a fleet of stateless servers, the counting has to be shared, atomic, and microsecond-cheap all at once. This guide walks from a blank requirements sheet to the exact reference architecture the SysGym simulator grades you against: a token-bucket limiter backed by a central atomic counter store, sitting in front of a generously replicated API, designed to fail open. The scenario throws 8,000 requests per second at you, doubles it to 16,000 during an abuse surge, settles to 1.6x sustained pressure, then kills API replicas at 12s and 28s and stalls the API tier mid-surge at 20s. The targets are availability at or above 98.5 percent, hot-path p99 at or below 85 ms, sustained throughput at or above 8,000 rps, and peak saturation at or below 90 percent. We will derive each design choice and show the math that clears those bars.

Clarify the requirements before drawing anything

Start by separating what the limiter must do from how well it must do it. The functional contract here is narrow: cap requests per key over a time window, support configurable limits per route or plan, and make consistent decisions across every server in the fleet. The word consistent is the whole problem. With the API spread over several stateless replicas, each seeing only its slice of traffic, the replicas must still agree on whether key K has exhausted its budget, even though no single replica has seen all of K's requests.

The non-functional requirements are where this problem earns its difficulty, and they map one-to-one onto the simulator's scored SLOs. First, microsecond-ish overhead on the hot path: the limiter runs before every request, so its added latency is pure tax on every call, which is why the p99 target is 85 ms for the entire chain, not just the limiter. Second, resilient: a limiter outage must not take down the API, which is the availability SLO at 98.5 percent surviving a replica death mid-surge. Third, scales horizontally with the fleet: adding API capacity must not require re-architecting the counter store.

Two clarifying questions are worth asking out loud in an interview because they change the design. What is the key — user ID, API key, IP, or a tuple of those? And is approximate enforcement acceptable, or must the limit be exact to the request? Public-API abuse protection tolerates a little slop; a billing quota does not. The simulator models the abuse-protection case: it rewards serving the legitimate load while a surge hits, and the quiz rubric explicitly rewards failing open over hard enforcement.

Functional: limit requests per key per window; per-route and per-plan limits; identical decisions across all replicas.
Non-functional: tiny hot-path latency, survive a limiter or replica outage, scale with the API fleet.
Scope cut for the interview: approximate global enforcement is acceptable; absolute exactness is a different, more expensive problem.
Decide the key dimension early (user, API key, IP, route) because it determines where hot keys and skew will appear.

Back-of-the-envelope: how much does a limiter actually cost?

The traffic profile is concrete: a base of 8,000 rps, a 2x abuse surge to 16,000 rps, then sustained pressure at 1.6x, or 12,800 rps. The engine wiggles offered load by a 5 percent sine term, so your true peak to design for is about 16,800 rps. Every one of those requests costs exactly one limiter decision, so the limiter's work rate equals the request rate: roughly 17,000 decisions per second at the peak. That number is small, and recognizing that it is small is the first insight — a rate limiter is not a big-data problem, it is a low-latency, high-availability problem.

Now size the counter store. A single Redis instance comfortably sustains well over 100,000 simple operations per second on commodity hardware, and a token-bucket check is a short Lua script touching one key. So 17,000 checks per second uses under a fifth of one Redis node. You do not shard Redis for throughput at this scale; you replicate it for availability. State is tiny too: a token bucket needs two numbers per key, the current token count and the last-refill timestamp, which with key overhead is roughly 100 bytes. Ten million distinct active keys is about 1 GB of RAM, well within a single instance, and expired keys drop out via TTL.

Latency is the binding constraint, not capacity. A same-zone Redis round trip is roughly 0.2 to 0.5 ms, so a synchronous central check adds well under a millisecond to a request whose backend work already costs 10 to 20 ms. The simulator encodes this with a limiter processing latency of 2 ms against an API latency of 10 ms and a datastore of 6 ms. The lesson the numbers teach: the limiter is cheap in absolute terms, so the engineering effort goes entirely into keeping that cheap check both atomic and survivable, never into scaling its throughput.

Peak to design for: 8,000 rps base x 2 surge x 1.05 wiggle is about 16,800 rps of limiter decisions.
Counter store load: about 17,000 ops/sec, under 20 percent of one Redis node — replicate for HA, do not shard for throughput.
State size: roughly 100 bytes per key; 10M active keys is about 1 GB, fits in RAM with TTL eviction.
Added latency: a same-zone Redis check is sub-millisecond against a 10–20 ms backend, so the limiter's tax is small if you keep it to one round trip.

High-level architecture and why each piece is there

The reference topology is a straight chain: client, edge load balancer, rate-limiter service, API servers, datastore. The load balancer spreads traffic across the limiter fleet. The limiter service does one atomic counter check per request and either rejects with a 429 or forwards. The API servers do the real work once allowed. The datastore backs the API. The limiter's own shared state — the counters — lives in a central in-memory store with atomic operations, the single source of truth that makes decisions consistent across replicas; the simulator folds that store's round trip into the limiter's 2 ms rather than drawing it as a separate node.

Why a central counter store rather than per-server memory? In-memory counting is the fastest possible option and earns partial credit, but it is wrong for this requirement: each node sees only its slice of traffic, so a limit of N enforced independently on M nodes lets through close to N times M before anyone notices. You would have to divide the limit by the replica count and you would still lose burst tolerance and mishandle scaling events. The opposite mistake — a SQL row inserted per request — is worse: 17,000 throwaway inserts per second is write amplification that melts a relational database and adds tens of milliseconds of write latency to the hot path. The central in-memory store with atomic increments is the only option that is both consistent and fast.

The numbers that clear the SLOs come from sizing every hop above the surge with replication headroom. The reference uses a load balancer at 50,000 rps, a limiter at 2 replicas times 24,000 (48,000 effective), an API at 5 replicas times 9,000 (45,000 effective), and a datastore at 30,000. Against a 16,800 rps peak, the worst-loaded node — the datastore — runs at 56 percent utilization, and the whole chain drops zero requests, so availability sits near 100 percent and the run-median p99 lands in the mid-40s of milliseconds (the steady-surge path is about 44 ms). Both are comfortably inside the 85 ms and 90 percent targets, and the generous replica counts are what let a node death pass unnoticed, which the next sections make precise.

Edge LB to spread load; limiter service for the atomic check; API fleet for real work; datastore behind the API.
Counters live in a central in-memory store with atomic ops — one source of truth, consistent across all replicas.
Per-server in-memory counting is fast but inconsistent (each node sees 1/M of traffic); a SQL insert per request is write amplification that melts the DB.
Reference sizing: LB 50k, limiter 2x24k, API 5x9k, DB 30k — worst node (the DB) at 56 percent utilization, zero drops, steady-surge p99 near 44 ms.

Deep dive 1: an atomic decision without a lock

The hard part of a distributed rate limiter is not counting — it is counting correctly when many servers increment the same key concurrently. A naive read-modify-write (GET the count, compare to the limit, SET the new count) has a race: two replicas both read 99, both decide they are under the limit of 100, and both allow, so the true count becomes 101. The obvious fix is a distributed lock per request — and it is a trap that the rubric explicitly marks wrong. A lock adds a round trip to acquire and release, serializes the hot path so concurrent requests for the same key wait in line, and turns the lock service into a new single point of failure. You have made the cheap check expensive and fragile.

The right tool is atomicity from the store itself, not from a lock around it. For a simple fixed window, Redis INCR is atomic by construction: one round trip returns the post-increment value, and you reject if it exceeds the limit, setting a TTL on first touch so the window resets. For a token bucket — the workhorse algorithm — you run a single Lua script on Redis that reads the token count and last-refill time, computes how many tokens to add for the elapsed time, clamps to the bucket capacity, and if at least one token is available decrements and returns allow, otherwise returns deny. The entire read-compute-write executes atomically inside Redis in one round trip, with no WATCH retry loop and no external lock. That is why the rubric scores the Lua script and atomic INCR as the resilience answer and the per-request lock as the anti-pattern.

Choosing the algorithm is the other half of this dive, and it is a memory-versus-accuracy trade. Token bucket keeps O(1) state per key (two numbers), allows controlled bursts up to the bucket size while smoothing to a steady refill rate, and is the default for good reason. A sliding window log is the most accurate — it stores a timestamp per request in a sorted set and counts entries in the live window — but its memory is O(requests in window) per key, which is heavy for hot keys. A fixed window counter is the simplest and cheapest, one integer per key per window, but it permits up to 2x the limit across a boundary: a client can fire a full window's worth at 0.999 seconds and another full window at 1.001 seconds. A sliding window counter, which blends the current and previous fixed windows by weight, is the common compromise that approximates the log's accuracy with O(1) state. The reference picks token bucket because burst tolerance plus O(1) state is exactly what a public API wants.

The race: concurrent read-modify-write on the same key over-admits; a per-request distributed lock fixes it but adds a round trip, serializes the hot path, and becomes a new SPOF.
The fix: push atomicity into the store — Redis INCR for fixed windows, a single Lua token-bucket script for refill-and-decrement in one atomic round trip.
Token bucket: O(1) state, allows bursts, smooths to a rate — the default.
Sliding window log: exact but O(requests) memory per key; fixed window: cheapest but allows 2x at boundaries; sliding window counter: the O(1) compromise.

Deep dive 2: hot keys and failing open

Even with atomic operations, one key can become a bottleneck. Picture a global limit, or a single whale customer, or one IP under a credential-stuffing attack: all of that key's increments hash to the same Redis slot, so one shard gets hammered while the rest sit idle. The check is still atomic, but it is now serialized on a single hot partition. Three mitigations stack. First, a local pre-decision: once a node learns a key is over budget for the rest of the window, it caches that verdict and rejects locally without asking Redis again — denials become free and the hot key stops generating remote traffic. Second, key sharding: split a limit of L across K sub-keys (key:0 through key:K-1), each granted L over K, and hash each request to one sub-key; this spreads load across K slots at the cost of slight inaccuracy at the bucket edges. Third, batching or coalescing increments under extreme fan-in.

The same hot-path pressure motivates a two-tier design that the rubric rewards: a local approximate counter, asynchronously synced. Each node keeps an in-process token bucket sized to its fair share and only reconciles the aggregate to the central store every 100 ms to 1 second. Requests are decided locally in nanoseconds with no network hop at all, and the central store converges slightly behind reality. You trade a small amount of accuracy — a brief over-admit right after a sync — for a large latency win and immunity to a central-store blip. This is the concrete meaning of the microsecond-ish overhead requirement: the truly hot path should not pay a network round trip on every request.

Resilience closes the loop: decide what happens when the counter store is unreachable. Fail open — allow the request — is the correct default here, and the rubric scores it explicitly. The reasoning is a blast-radius argument: if the limiter is down and you fail closed, you have converted a limiter outage into a total API outage, throttling everyone to zero. Letting some extra traffic through for a few seconds is strictly better than hard-downing the product, especially since your API is replicated with headroom and can absorb the overflow. The exception is a security- or billing-critical limit where over-admission is unacceptable; there you fail closed and accept the availability hit. For abuse protection — this scenario — fail open, and pair it with the local approximate tier so that even a total Redis outage degrades to per-node limits rather than to nothing.

Hot key: all of one key's increments hit one shard. Mitigate with local cached denials, key sharding (L split across K sub-keys), and increment coalescing.
Two-tier limiting: per-node local bucket decided in nanoseconds, reconciled to the central store every 100 ms–1 s — trades a little accuracy for big latency and resilience wins.
Fail open by default: a limiter outage should not become an API outage; allow overflow and let the replicated API absorb it.
Fail closed only for security or billing limits where over-admission is worse than a brief unavailability.

Bottlenecks under load and how to scale them

The simulator's starter design is a teaching failure on purpose, and tracing it shows exactly where limiters break. The starter limiter is a single replica at 9,000 rps, the API is 3 replicas at 3,000 (9,000 effective), and the datastore is 5,000. At base load the datastore alone drops 3,000 of 8,000 rps — availability around 62 percent before any abuse even starts. At the surge the limiter itself can only pass 9,000 of the ~16,800 offered, shedding roughly 7,800 rps of legitimate traffic — and the trickle that gets through still meets a 5,000-rps datastore that cuts it again. That is the signature mistake: the component you installed to protect the API has become the thing dropping good requests. A rate limiter that is under-provisioned for peak is worse than no rate limiter, because it adds a hop that fails.

The fix is to size every hop above the surge and replicate enough that a failure still leaves headroom. The reference limiter at 2 times 24,000 is nearly 3x peak, so even losing a replica leaves 24,000 — above the 16,800 peak. The API at 5 times 9,000 is the key move: the scenario's scripted kills land on a service node, and the engine resolves that to the API tier, so when one replica dies 4 times 9,000 is 36,000, still more than double the peak, the death drops zero requests, and it never cascades. This is the difference between the availability SLO passing at near 100 percent and a single kill snowballing as survivors saturate and shed in turn.

The subtler bottleneck is the coupling between saturation and latency, which is why there is a 90 percent saturation SLO at all. The engine models per-node queueing latency as roughly 1 divided by (1 minus utilization), the standard single-server queue blow-up, capped at 95 percent. At 56 percent utilization the factor is about 2.3; at 90 percent it is 10x; at the 95 percent cap it is 20x. So a node you let run hot does not fail gracefully — its tail latency explodes and blows the p99 budget long before it drops a request. The reference keeps its worst node, the datastore, at about 56 percent, which is why the steady-surge chain p99 is near 44 ms. The latency-spike chaos at 20 seconds slows the API node 8x for 6 seconds — 10 ms times 8, amplified by queueing and summed down the chain — briefly pushing the path p99 toward 190 ms. That blip does not sink the score for two reasons: the graded metric is the median per-tick p99 over the 35-second run, so a 6-second spike barely moves it; and because utilization is kept low, even the 8x spike is multiplied by a small queueing factor rather than a runaway one.

Starter failure: a 9k limiter sheds ~7.8k rps of good traffic at the surge, and a 5k datastore drops even at base load — the protector becomes the dropper.
Fix throughput: size each hop above the ~16.8k peak; reference LB 50k, limiter 48k, API 45k, DB 30k.
Fix availability: replicate so a kill leaves headroom — the scripted kills hit the API tier, and 4 of 5 replicas still serve 36k, double the peak, so a death drops nothing.
Fix latency: queueing cost is about 1/(1-utilization) (capped at 95 percent); keep nodes near 56 percent (2.3x) not 90 percent (10x) so p99 stays bounded.

Key trade-offs to state out loud

Every defensible answer here is a trade, and naming the axis is what separates a strong interview from a recited solution. The central axis is accuracy versus latency: a synchronous central atomic check is exact but pays a round trip per request, while a local approximate counter synced asynchronously is nearly free but drifts between syncs. Most public APIs sit in the middle — central token bucket for correctness, with a local cache of recent denials and an optional local tier for the hottest keys.

The second axis is the algorithm's memory versus accuracy, already covered: token bucket for O(1) state and burst tolerance, sliding window log when you must be exact and can afford per-request timestamps, fixed window when simplicity dominates and the 2x boundary burst is acceptable. The third is failure posture: fail open maximizes availability and is right for abuse protection, fail closed enforces strictly and is right for billing and security — you cannot have both, so you choose per limit. The fourth is the central store as a single point of failure versus cost and complexity: you replicate or cluster Redis for HA, but cross-region replication adds latency to the hot path, so the common pattern is regional limiter state with per-region limits rather than one global counter, accepting that a user could get slightly more than their global budget if they span regions.

Tie it back to the SLOs to show the design is not arbitrary. Token bucket plus a central atomic store delivers consistent decisions and burst tolerance; replicating both the limiter and the API at roughly 2-to-3x peak delivers the 98.5 percent availability through replica deaths and keeps the worst node near 56 percent for the saturation budget; one cheap atomic round trip plus generous headroom keeps the steady-surge chain p99 near 44 ms against the 85 ms target; and failing open guarantees a limiter outage degrades to extra traffic, not to a dead API. Each number on the canvas exists to clear a specific bar, and being able to say which is the difference between a passing design and a graded one.

Accuracy vs latency: central atomic check (exact, one round trip) vs local approximate sync (fast, drifts).
Memory vs accuracy: token bucket O(1) and bursty; sliding window log exact but O(requests); fixed window cheap but 2x at boundaries.
Availability vs enforcement: fail open for abuse protection, fail closed for billing and security.
SPOF vs latency: replicate or cluster the counter store for HA, but keep state regional rather than paying cross-region round trips on every request.

Key takeaways

A rate limiter is a low-latency, high-availability problem, not a throughput problem: at 16,800 peak rps the counter store does about 17,000 ops/sec, under 20 percent of one Redis node — you replicate for HA, not shard for scale.
Make the decision atomic in the store, never with a lock: Redis INCR for fixed windows or a single Lua token-bucket script does refill-and-decrement in one atomic round trip; a per-request distributed lock adds a hop, serializes the hot path, and is a new SPOF.
Token bucket is the default — O(1) state per key, allows bursts, smooths to a rate; reach for a sliding window log only when you need exactness and can pay per-request timestamps.
Keep counters in one central in-memory store for consistent decisions; per-server memory over-admits by roughly the replica count, and a SQL insert per request is write amplification that melts the DB.
Fail open: a limiter outage must degrade to extra traffic the replicated API absorbs, not to a dead API — unless the limit is billing- or security-critical, where you fail closed.
Size every hop above the surge and replicate so a node death leaves headroom (4 of 5 API replicas still serve 36k against a 16.8k peak); keep utilization near 56 percent because queueing latency scales like 1/(1-utilization) and explodes past 90 percent.

Now build it and watch it survive the chaos run.

Build it