Cruxly › System design › Design Exercises

Distributed Rate Limiter Service

a counter that hundreds of gateways share, on a path that cannot afford to wait for it

Prompt: design a rate limiter service for a public API platform. Many gateway nodes in several regions must enforce per-customer limits, the limits must be changeable without a deploy, and the limiter must never become the reason the API is down.

Give yourself a session before reading on, 40 minutes and a blank page. The token bucket is the easy part; this exercise starts where Rate Limiting stops, at the service around it.

Applying the four moves: Scope — whose limits, enforced where, how strict; billing, quotas measured in days and abuse detection are out. Estimate — checks per second sets the shard count, active keys set the memory, and the ratio of the two shows that the network round trip, not the arithmetic, is the cost. Sketch — a check in the gateway, a sharded atomic counter store behind it, a local layer in front of the store for heavy keys, and a rules service that pushes configuration. Deep dive — the three places it breaks: a read-then-write race, one key that is hotter than one shard, and the store being unreachable. Further reading: Designing Data-Intensive Applications by Martin Kleppmann, for the replication and clock chapters this design leans on; the algorithms themselves are in Rate Limiting in this track.

Scope: whose limits, enforced where, how strict

In scope: limits keyed by customer, API key, IP and endpoint class; several rules per request; limits that differ per plan; a decision (allow, or reject with a retry time) returned within a few milliseconds; rule changes without a deploy; behaviour when the store is down; several regions. Out of scope: billing-grade usage metering (it must be exact and durable; the limiter is neither), quotas measured over days, bot and fraud detection, and the choice between token bucket and window counters, which Rate Limiting covers.

Say the two properties you will optimise out loud, because they fight each other: low added latency on every request, and tight accuracy at the limit. A limiter that is exact costs a network round trip to a single authority on every request. One that is fast lets some excess through. Everything below is a choice along that line, and the choice is per rule, not per system: a login-attempt limit wants accuracy, a 10,000-per-second API limit wants speed.

How strict? Settle this before drawing anything, with the interviewer if possible:

AWS states the stance plainly for its own product. The API Gateway throttling page says throttles and quotas are applied on a best-effort basis and should be thought of as targets rather than guaranteed request ceilings. A production limiter that calls itself exact is making a claim it cannot keep across regions and failures.

Numbers: checks per second, shards and memory

Assumption (the interviewer would give you these): a public API with 300,000 requests per second at peak, 400 gateway nodes, 2 rules checked per request (per customer, and per IP), and 20 million keys live at any moment (customer x rule, with IP keys expiring fast).

Worked arithmetic, not any company's number:

• Checks: 300,000 x 2 = 600,000 checks/s.
• Per gateway: 600,000 / 400 = 1,500 checks/s each, so each node makes 1,500 script calls a second. The two rule keys (customer, IP) usually hash to different shards and a script cannot span shards, so send the two calls in parallel rather than as one call.
• Shards: assume a Redis shard sustains 100,000 scripted operations per second with sub-millisecond service time. This is an assumption; benchmark your own script on your own hardware, because script length and key size move it by multiples. 600,000 / 100,000 = 6 shards at 100% busy. Run at 50% to leave headroom for a hot spike: 12 primaries, each with a replica.
• Memory: a token-bucket entry is a small hash with two fields (tokens, last-refill time) plus an expiry. Assume 150 bytes per key with Redis overhead. 20,000,000 x 150 = 3 GB in total, about 250 MB per primary across 12. Memory is not the constraint.

What the numbers say. Memory is trivial, so the design is not about fitting counters. The cost is the round trip: if the datacentre network adds 0.5 ms and the script 0.1 ms, every request pays about 0.6 ms of limiter time, and 600,000 checks/s is real load on 12 machines. The second conclusion is about skew: the average shard serves 50,000 checks/s, but one customer sending 100,000 requests/s to one key lands every check on one shard. Total capacity is irrelevant when a single key exceeds a single shard.

Where the limiter sits

Four placements, and the choice is about who owns the code and what a failure costs.

Envoy's own design shows the mature combination. Its docs describe global rate limiting as calling an external gRPC rate limit service (the reference implementation, written in Go, uses a Redis backend), and local rate limiting as a token bucket inside the proxy itself. The docs describe using both: the local limit takes the large bursts first, so they never reach the global service, and the global limit then handles the shared, accurate part. AWS API Gateway applies four layers in a fixed order: per-client or per-method limits from a usage plan, then per-method stage limits, then the account limit in the Region, then the AWS regional limit, with the per-API and per-client limits unable to exceed the AWS-set and per-account ceilings.

The chosen design. Edge gateway nodes call a limiter client library, which has a small local layer (a token bucket for heavy keys, section 5) and talks to a sharded counter store. The "standalone service" is not an extra network hop here, because the client talks straight to the shards; the service is the rules plane (section 7) and the shared script. Say why you avoided a stateless proxy tier between gateway and store: it adds a hop and a failure domain and, since counters live in the store, it adds no capacity.

Shared counters in Redis: the atomic script, the race, clocks and hot keys

The check must be one atomic step, and in Redis that means a script. The race is concrete. Two gateways each read tokens = 1, each decides to admit, each writes 0. Two requests were admitted on one token. Under a limiter's own workload (many gateways, same key, same millisecond) this is not rare, it is the case. A read-then-write from the client cannot be fixed with retries; it needs the read, the decision and the write to happen as one indivisible step.

The Redis scripting docs give the guarantee: scripts run atomically, and while a script runs all other server activity is blocked, so its effects either have not happened yet or have already happened. The same page gives the rules you must follow:

• Every key a script touches must be passed as a key argument, never built inside the script, or it breaks in Redis Cluster. One key per rule keeps each call on one slot.
• The script cache is volatile. It can be cleared on restart or when a replica takes over, so call EVALSHA and fall back to SCRIPT LOAD on a NOSCRIPT error. In a pipeline that error cannot be handled, so the docs say clients should use plain EVAL there.
• Because a script blocks the server, it must be short. A slow script stalls every other key on that shard; the docs note a slow script can only be interrupted by SCRIPT KILL and only if it has not written yet.

Clock skew is solved by whose clock you use. The script reads TIME from the Redis server, so every gateway's decision uses one clock per shard, and skewed gateway clocks are irrelevant. The Redis scripting page says that since version 5.0 replication sends the script's effects (the write commands) rather than the script, which is why calling TIME inside a write script is allowed; from 7.0 verbatim script replication is gone entirely. On older versions, the same script would have been refused. Pass the limit (rate and burst) as arguments, not baked into the script, so a rule change needs no script reload and no counter reset.

:::key Verified November 2026

• Redis scripting docs (read 2 November 2026): scripts are atomic and block other activity while running; effects replication is the default since 5.0 and the only mode since 7.0; the script cache is volatile and not persisted; all keys must be passed as key arguments.
• Cloudflare's counting post: a sliding-window approximation stores two numbers per counter, increments with a single INCR and reads with one GET; they avoided a leaky bucket because it needs several operations that cannot be done atomically in memcached.

:::

Sharding. Hash the key (customer id plus rule id) to a shard, with consistent hashing or Cluster slots, so adding a shard moves a fraction of keys instead of all of them. The key space is large and mostly small, which is the ideal case for hashing.

Replication and durability, on purpose. Replicas are asynchronous, so a failover loses the last few milliseconds of decrements, and a restarted shard with no persistence starts every bucket full. Both produce a brief over-admission, bounded by one burst per key. That is the correct trade: do not buy fsync-level durability for a counter that refills in seconds. Say so before the interviewer asks.

Hot keys. One key's traffic cannot be spread by hashing. Two fixes, and you want both: split the key into k sub-keys (cust42#0 to cust42#3), each with limit/k, chosen by the gateway at random. Worked arithmetic: 100,000 checks/s on one key at 4 sub-keys is 25,000 each, comfortably under a shard. The cost is accuracy at the edge, since one sub-key can empty while others have tokens. The better fix, for the heaviest keys, is the local layer in the next section, which removes most calls to the store altogether.

Local-plus-global hybrid and approximate counting

The cheapest check is the one that never leaves the process. At 100,000 checks/s on one heavy key, even a perfect shard is a bottleneck and a latency cost. The hybrid keeps the store as the authority but removes most calls to it. There are two schemes, with opposite error directions.

Scheme A: leases (under-admits). A gateway asks the store for a chunk of tokens (a lease), deducts them from the shared bucket immediately, and spends them locally. Give each lease a short life (about the 100 ms it should last) and discard what is unspent, otherwise a node can hoard tokens and spend them later as a burst. Worked arithmetic for a key with a limit of 100,000/s across 400 gateways: each node sees about 250 requests/s on it. A lease of 25 tokens lasts about 100 ms, so each node makes 10 calls a second, 4,000 calls/s in total against 100,000 unbatched, a 25x reduction. Error: tokens already deducted but unspent sit on idle nodes, at most 400 x 25 = 10,000, that is up to 10% of one second's limit, and the error is toward rejecting early. Strict, but uneven traffic can see wrongful 429s.

Scheme B: local counting with periodic sync (can over-admit). Each gateway admits against a cached view and sends its count deltas every 100 ms. Error: nodes cannot see each other's use in between, so the overshoot is up to nodes x per-node rate x interval = 400 x 250 x 0.1 = 10,000 requests, again 10% of the limit but toward admitting too much.

It only helps heavy keys. A key with a limit of 1,000/s spread over 400 nodes sees 2.5 requests/s per node, 0.25 per 100 ms. A lease of 25 tokens would hold 10 seconds of the whole key's quota on one node. So the rule is: keys below some rate threshold (for example 5,000/s) always go straight to the store; only keys above it get leases, sized at about 100 ms of that node's share. That threshold is a configuration, not a constant.

Approximate counting trades accuracy for speed, and the data supports it. Cloudflare's counting post measured its sliding-window approximation (the previous window weighted by how much of it overlaps, plus the current window) on 400 million requests from 270,000 sources: 0.003% of requests were wrongly allowed or limited, and the average difference between the real and approximated rate was 6%. Three sources were wrongly allowed, none by more than 15% over the threshold, and none were wrongly limited. The point for this exercise: an error of single-digit percent at the limit is normal and nobody notices, so do not spend a round trip to remove it. Cloudflare also does not make every request pay for the counting: increments run asynchronously, and once a client exceeds the threshold, a mitigation flag with a known end time is stored and servers cache it locally, so a limited client costs no further lookups. The same idea applies to us: once a key is over its limit and the retry time is known, cache the rejection in the gateway until then.

Multi-region: local versus global limits

Do not put a cross-region round trip in the request path. Assume 70 to 150 ms between regions (an assumption; measure yours). A global check costs more than most APIs' entire latency budget, and a region cut off from the others would have to choose between failing and ignoring the limit. So each region owns a local counter store and enforces a regional share of each global limit.

Cloudflare's counting post shows the same reasoning in a different form. Their traffic arrives over anycast, so under normal conditions one IP's traffic reaches the same data centre, and counting can be isolated per data centre, which they say avoids the latency and availability problems of a single global counter. Servers inside a data centre share counters through a sharded memcache, because connections from one IP can still land on different servers. That is the lesson: make the common case local, and share state at the narrowest scope that still sees the traffic.

Three ways to split a global limit L across R regions:

Chosen: rebalancing, with a floor. Each region starts with its share (L x last period's traffic fraction, never below 10% of L so a new region can serve its first requests). Worked arithmetic: with L = 10,000/s, three regions, a one-second rebalance and a customer whose load flips entirely from region A to region B, B is capped near 1,000/s until the next rebalance, then moves towards 9,000/s. The cost is up to a second of wrongful 429s in B after a shift, and up to L/R of the limit left unused if a region fails and its share is still assigned. Both are bounded and visible, which is what you can defend.

Customers who must be exact (a low-limit, security-relevant rule such as login attempts per account) use the home-region scheme: send the check to the owner and accept the latency, because accuracy was named as the priority for that rule. This is the per-rule choice from section 1 in action.

What goes wrong in the room. "What if the coordinator is down?" Regions keep their last-assigned shares, which are still correct in sum. "What if a region is partitioned?" It keeps enforcing its share, so the global total can only rise to the sum of shares; and shares are set to sum to L, so no overshoot, just the lost reallocation. Say that the design degrades to static split, never to unlimited.

Rules and configuration: distribution and hot reload

The rules are data, the limiter code never contains a limit. A rule says: match (customer, endpoint class, plan), the limit (rate, burst, cost), the identity to key on, and the failure policy (open or closed). It is stored in a database with a version, edited through a review flow, and served by a rules service that gateways read.

Distribution. Gateways keep the whole rule set in memory, which is small (tens of thousands of rules, a few MB). They get changes two ways: a push or long-poll for speed, and a full poll every 30 seconds as the safety net if a push is missed. A gateway applies a new version atomically (swap a pointer), and reports its version to the rules service so you can see how many nodes are on which version. A gateway that cannot reach the rules service keeps its last good rules; a limiter must not stop limiting because configuration is unreachable.

Why hot reload is cheap here: the rate and burst travel as script arguments (section 4). The stored state is only tokens and a timestamp, independent of the limit, so a new rate takes effect on the next check with no counter migration. A designer who bakes the limit into the counter key has to explain what happens at the moment of change.

Safe rollout is the real deliverable. Stripe's rate-limiter post names the practices: dark launch each limiter so you can watch the traffic it would reject before it rejects anything; keep kill switches and feature flags to disable a limiter fast; and emit metrics on how often each fires. Apply that to rules, not only to code:

1. A new or tightened rule starts in shadow mode: the decision is computed and counted, but the request is allowed.
2. Review the would-have-rejected rate per customer. If a rule would reject a paying customer's normal traffic, fix it before it bites.
3. Promote to enforce, with the old version one click away.

:::warn The change that causes the incident Most limiter outages are not store failures, they are a rule change: a limit set 10x too low, or a wildcard matching an internal service. Require a shadow period, a maximum percentage change per edit without extra approval, and an instant rollback. Compare with Rate Limiting: the algorithm never takes the API down, the configuration does. :::

Precedence needs a defined order. Several rules can match one request (global, plan, endpoint, IP). AWS applies its throttle settings in a stated order, most specific first; copy that idea: evaluate all matching rules, reject if any rejects, and return the retry time of the rule that will clear last, so the client does not retry into a different limit. Note that rules checked independently each spend a token, so a request rejected by one rule has still used the other rule's token; check the strictest rule first, or accept the small over-count.

Failure modes: fail open or closed, and the limiter's own budget

The limiter is on the hot path of every request, so it needs a latency budget and a failure policy before it needs anything else.

Give every check a hard timeout. Assume 5 ms: against a normal 0.6 ms that is generous, and anything slower is a sick shard. On timeout or error the gateway applies the rule's failure policy:

Stripe's post says to fail open if the limiter has bugs or Redis goes down, so the API keeps working. Envoy exposes the same decision as a setting: its rate limit filter has failure_mode_deny, and when the call to the rate limit service errors, true returns a 500 and false lets the request through, with a counter of requests allowed because of it. Both pick a side per deployment; choose per rule, record it in the rule, and make "fail to local" the default for traffic rules, since it fails open without being unbounded. Worked arithmetic: limit 10,000/s, 400 nodes, safety factor 2 gives each node 50/s, so even during a total store outage the platform admits at most 20,000/s, twice the limit instead of infinity.

Failures to raise unprompted:

• A shard dies. Its keys fail over to a replica with a loss of the last few milliseconds of state. Cost: a brief over-admission. With 12 primaries, one dead primary is 1/12 of keys, about 8% of traffic on the fail-policy path until failover finishes.
• Slow script. One slow script (a loop that grew with the key's size) blocks the whole shard, since all activity stops while it runs. Keep scripts constant time, and alert on the shard's slow-log.
• Retry amplification. A shard blip makes gateways time out and retry, doubling load on a struggling store. Do not retry the limiter call; take the failure policy immediately.
• Thundering reset. A restarted shard has no state, so all its buckets start full. Bounded by one burst per key, and acceptable, but name it.
• A hot customer. Handled by the local layer from section 5; also alert when one key exceeds 25% of a shard.
• The limiter's own limit. Protect the store from gateways: cap in-flight limiter calls per gateway, and if you must shed, shed the checks (take the failure policy) rather than queue them.

Use the right status. A rejection because the caller is over its limit is a 429. A rejection because the limiter failed closed is not the caller's fault and should be a 503, so clients know that lowering their own rate will not help. Rate Limiting covers the headers.

What clients see, testing under load, and what to say

Clients. Rejections carry a 429 with a retry time, and the SDK retries with jittered exponential backoff (see Rate Limiting; do not repeat the arithmetic here). Two service-level additions: Envoy sets an x-envoy-ratelimited header on its 429s unless disabled, which lets a client or a dashboard tell a limiter rejection from a backend 429; and your own responses should name which rule rejected, so a customer asking support "why am I limited" gets an answer from the response alone. Expose usage to customers (a dashboard or endpoint) so they see limits before they hit them.

Testing a limiter is testing its error, not its happy path.

1. Accuracy under concurrency. Run N simulated gateways (use all 400) against one key with a limit of 1,000/s and offered load of 3x for 60 seconds. Measure admitted requests per second. Pass if it stays within the error budget you stated (for example under 5% above the limit for exact rules, under 10% for leased heavy keys). Run this on the local layer too; the 10% figure from section 5 is a prediction you can falsify.
2. Race test. Hammer one key with 1,000 parallel requests on a bucket with 1 token. Exactly one must be admitted. This is the test that catches a read-then-write bug.
3. Skew test. Shift half the gateways' clocks by 5 seconds; admitted rate must not change, because the shard's clock is used.
4. Hot-key test. One key at 3x a shard's capacity: confirm sub-keys or leases keep shard CPU below the alert threshold.
5. Chaos. Kill a primary under load: measure the over-admission and the time to recover; stop the store entirely: confirm the fail-to-local ceiling of 20,000/s holds.
6. Replay. Replay a recorded production hour against new rules in shadow mode before enforcing (section 7).

Observability. Per rule: allowed, rejected, failed-open and failed-closed counts; limiter latency percentiles; rule version per gateway; and the top ten keys by rejection rate. Alert on the ratio of fail-open to total, because a limiter that silently fails open all day looks healthy and is not limiting.

What to say, in order. "I would scope accuracy per rule, then size it: 600,000 checks a second is about six shards on an assumption I would benchmark, so I run twelve. Each check is one Redis script reading the shard's clock, passed rate and burst as arguments so rules reload without touching state. Heavy keys get local leases, which cut store calls from 100,000 a second to about 4,000 at a cost of up to 10% error. Regions enforce shares of the global limit, rebalanced every second. Every check has a five-millisecond budget and a per-rule failure policy, defaulting to a bounded local limit. New rules start in shadow mode."

Further reading: Designing Data-Intensive Applications by Martin Kleppmann (the chapters on replication and on the trouble with distributed clocks); Stripe's post "Scaling your API with rate limiters"; and Cloudflare's "Counting things, a lot of different things".

How to say it in the interview

"The algorithm is a solved choice, so I would spend the time on the service. Every check must be atomic, so I would run it as one Redis script keyed by customer and rule, sharded by key, with a local lease layer in front for the few keys that exceed one shard. The limiter has a five millisecond budget and fails open on timeout, because a limiter outage should cost us accuracy, not availability. At 300,000 requests a second with two rules each, that is 600,000 checks a second, about six shards on my assumption of 100,000 scripted operations per shard."

Checklist

• Scoped accuracy per rule and named latency versus accuracy as the tension
• Sized checks per second, shards and memory, and said which figures are assumptions
• Showed that memory is trivial and the real risks are the round trip and a hot key
• Made the check one atomic script and named the read-then-write race
• Used the store's clock inside the script, not the gateways' clocks
• Handled hot keys with sub-keys or leases, and gave the error direction of each
• Kept the cross-region round trip out of the request path with regional shares and rebalancing
• Put rate and burst in the rule data and passed them as arguments, with shadow mode for new rules
• Gave every check a time budget and a per-rule failure policy, defaulting to a bounded local limit
• Described tests for concurrency, skew, hot keys and store failure, and alerts on fail-open ratio

Related lessons

• Short Links at Scale
• Activity Feed
• Real-time Messaging
• Seat Booking
• Notification System (HLD)
• Search Autocomplete (HLD)