Distributed Rate Limiter

"Design a rate limiter" is the most common warm-up question in system design interviews, and one of the most commonly failed. Not because it is hard, but because it is easy to answer badly at length.

Most candidates hear "rate limiter" and start listing algorithms. Fixed window. Sliding window log. Sliding window counter. Token bucket. Leaky bucket. Fifteen minutes later they have compared five algorithms carefully, and they still have not said where the limiter runs. Or what happens when Redis, holding its counters, goes down. Or what breaks when one customer sends a hundred times more traffic than everyone else put together.

The algorithms are the least interesting part of this problem. Each one is about twenty lines of code, each one is well documented, and in a real system the choice between them changes almost nothing. What changes everything is one decision you make in the first three minutes, usually without noticing you made it:

A rate limiter is a protection mechanism, not an accounting system. Its job is to keep your service standing up. Its job is not to produce a correct number. Once you accept that, every hard question here gets easier, because you are allowed to trade exactness for speed, uptime, and cost. Candidates who miss it spend the rest of the interview defending a consensus protocol nobody asked them to build.

This walkthrough follows the shape of a 45 minute interview, with a suggested time on each section. If you take one thing from it, take the sentence in bold.

Understanding the problem

A rate limiter sits in front of your API. For every request that arrives, it decides whether to let the request through or reject it. A rule looks like "this API key may make 1,000 write requests per minute." Requests past that get an HTTP 429 and never reach your application code.

Before you design anything, work out what you are protecting against. Four different problems get filed under one name, and they do not have the same answer:

1. Abuse. Scrapers, people trying stolen passwords against your login endpoint, someone walking through your /users/{id} route to collect data. This one is deliberate, and whoever is doing it will change tactics when you block them.
2. Accidental overload. A customer ships a retry loop with no backoff and sends you 40,000 requests per second by mistake. Far more common than abuse, and much easier to handle.
3. Fairness between customers. One noisy customer eats capacity that other customers paid for. Nobody is doing anything wrong. You just need to keep them from stepping on each other.
4. Plan quotas and billing. "Your plan includes 5 million API calls per month."

The first three are rate limiting. The fourth is not, and treating it as though it were is the most expensive mistake available on this question. A monthly quota is a billing number. It has to be exactly right, it is allowed to run minutes behind, and it gets checked against invoices. A rate limit only has to be roughly right, has a few milliseconds to answer, and is thrown away seconds later. Those are two different systems. We will design the rate limiter, and come back to this split in the deep dives.

Functional requirements

Core:

1. For every request, decide allow or reject against the configured rules, before the request reaches application code.
2. Support rules for different identities (API key, logged-in user, IP address, customer account) and different targets (the whole API, a group of routes, a single endpoint), each with its own limit and window.
3. Let operators change rules while the system is running, without a deploy.
4. Reject with a response the client can do something with, so a well-behaved client can correct itself.

Out of scope, deliberately:

• Authentication. We assume someone upstream has already worked out who the caller is.
• Monthly plan quotas and billing, for the reasons above.
• Bot detection, firewall rules, and soaking up a flood of traffic during a DDoS. That's a different layer.
• Limits on how many requests run at once, and shedding load when servers are struggling. Related and useful, but a separate mechanism.

Non-functional requirements

1. Low latency. Under 5 ms added at p99. This runs on every single request, so its slowest responses become your API's slowest responses.
2. More available than the service it protects. The limiter must never be able to take down the thing it is defending. That's a stronger statement than "it should be highly available."
3. Scale. 1 million requests per second at peak, roughly 100 million daily active users (DAU), tens of millions of live limit keys.
4. Approximately correct is correct. Going five percent over a limit is fine. Letting ten times through is not. Blocking traffic that is under the limit is worse than either.
5. Keep customers apart. One client's traffic volume must not affect decisions made for any other client.

Requirement 4 is the one everything else rests on. Write it down in exactly those words, because a version that says "must be accurate" will cost you the interview.

The set up

Core entities

Four things.

• Principal. Whoever is being limited, written with its type attached: api_key:ak_9f2c, user:u_881, ip:203.0.113.7, tenant:acme. The type matters, because "1,000 per minute" means something completely different for an API key than for an IP address.
• Rule. The policy. A matcher saying which requests it applies to, plus a limit, a window, an algorithm, and what to do on a reject.
• Bucket. The counter for one principal under one rule. This is the only thing in the system that changes constantly, and almost the whole design is about where it lives and who updates it and when.
• Decision. Allow or reject, plus which rule fired, how much allowance is left, and when it resets.

System interface

Two interfaces, and keeping them apart matters more than it looks. The data plane answers one question a million times a second. The control plane changes the rules a few times a week. They have nothing in common: different traffic, different accuracy needs, different behaviour when they break, different expectations of whoever is on call.

Data plane:

POST /v1/check
{
  "descriptors": [
    { "key": "api_key",  "value": "ak_9f2c" },
    { "key": "endpoint", "value": "POST /v1/messages" }
  ],
  "cost": 1
}

200 OK
{
  "decision":       "ALLOW",
  "matched_rule":   "rl_write_per_key",
  "limit":          1000,
  "remaining":      417,
  "reset_after_ms": 22400,
  "retry_after_ms": 0
}

Three details in that payload to note.

The descriptors are a list, and one call checks all of them. A descriptor is just one thing this request should be counted against. A single request usually falls under several rules at once: a limit per API key, a limit per endpoint, and an overall limit for the whole customer account. If your interface checks one rule per call, you have just put three network round trips, one after another, on every request, and the latency budget is gone. Check every matching rule in one call, and reject if any of them rejects. That's how Envoy's rate limit service works.

cost exists because not all requests are equal. A bulk export is not the same load as a health check. Letting the caller declare a weight means one mechanism covers "1,000 requests per minute" and "1,000 units of work per minute" without building a second system.

remaining and reset_after_ms come back on allowed requests too, not just on rejections. This is the cheapest large win in the whole design, and most implementations skip it. A client that can see it has 12 of its 1,000 calls left will slow down on its own. A client that only finds out at the moment of rejection can do nothing except retry and hope.

Control plane: ordinary create, read, update and delete over rules, versioned, with a record of who changed what. It is deliberately boring, and we will come back to why it still deserves a deploy pipeline rather than a form.

High-level design

We will work through the functional requirements in order. Each one forces a decision.

1. Where should the limiter run?

Before you choose an algorithm, choose a place. This decision has the largest consequences.

For the rest of this walkthrough, assume the gateway enforces the limit with shared state behind it. That keeps both the per-request path and the failure story clean.

2. Identify who is being limited

Prefer a lasting identity, fall back to a network one. For traffic you can authenticate, count against the API key or the user ID. Those are stable, they map to a real customer, and an attacker cannot cheaply get a new one.

For traffic you cannot authenticate, all you have is the IP address, and it is a bad signal in both directions. Mobile carriers put thousands of unrelated users behind one address, so a per-IP limit is either so loose it protects nothing or it blocks innocent people in large batches. Meanwhile an attacker rents a few thousand addresses for pocket change and walks straight through it.

And yet the endpoints you cannot authenticate are exactly the ones that need protecting most: login, signup, password reset, anything that sends an email or an SMS. So use two layers. Limit per address, and add a looser limit on something coarser, such as the surrounding /24 block of addresses or the whole network the traffic came from. Then rotating addresses inside a rented range does not reset the counter. Neither layer is good on its own. Together they make abuse expensive enough to matter.

Then think about how many distinct keys you can end up with, because the key format is a scaling decision. If the client controls part of the key, it can mint unlimited distinct keys, each with a fresh allowance, which is the same as having no limit. The classic version is counting against the raw path: /users/12345/messages and /users/12346/messages become separate keys, and the limit evaporates. Normalise to the route template, /users/{id}/messages, before it ever reaches the key.

A workable format:

rl:v1:{ak_9f2c}:write_per_key
   │   │         └── rule id, so different rules never collide
   │   └── principal, in hash-tag braces so all of one
   │       principal's rules land on the same shard
   └── schema version, so you can change the format later

The braces are Redis Cluster hash tags. Redis normally spreads keys across shards by hashing the whole key. When part of the key is wrapped in braces, it hashes only that part, so every key for one principal lands on the same shard. That is what lets a single script check all of that principal's rules in one round trip. A small piece of syntax carrying a large architectural consequence, and the kind of detail that reads as having actually built this.

3. Which algorithm decides?

Now the algorithms. There are four worth knowing, and the useful way to compare them is by what they cost, not by how they work. Two get eliminated by basic arithmetic.

Fixed window counter

Chop time into fixed blocks aligned to the clock, a minute each, say: 11:00:00 to 11:01:00, then 11:01:00 to 11:02:00. The state is one number per block: how many requests have landed in it so far, stored under a key that encodes which block it is, along the lines of rl:{rule_id}:{principal}:{window_start}.

Every request runs Redis's INCR on that key, which adds one and hands back the new count in the same call. If that count is over the limit, reject. On the very first increment of a block, also set an EXPIRE for the block's length, so the key deletes itself the moment the block ends instead of you resetting it by hand. One INCR per request, one EXPIRE set once per block, and a single integer as the entire state. As cheap as this gets.

It also has a flaw that is not an edge case:

A client can send its whole allowance at the end of one window and its whole allowance at the start of the next, putting twice the limit through in a couple of seconds. This is not a contrived attack. Any client running a cron job on the minute boundary does it by accident, and so does every other client on that boundary, at the same instant. That is how you get a spike across your entire customer base every sixty seconds.

Sliding window log

Store every request's timestamp as a member in a Redis sorted set, scored by time. On each check: drop entries older than the window with ZREMRANGEBYSCORE, add the new timestamp with ZADD, then count what's left with ZCARD. Reject if that count is over the limit. Exact, no boundary problems, and the cleanest idea on the list.

It is also dead on arrival, and one calculation shows why:

A client limited to 1,000 requests per minute holds 1,000 sorted-set members.
Each member costs roughly 100 bytes once you include the member string,
the score, and skiplist overhead.

  per key      1,000 × 100 B          ≈ 100 KB
  10M keys     10,000,000 × 100 KB    ≈ 1 TB

Compare a token bucket, which stores two numbers:

  per key      ~200 B with Redis overhead
  10M keys                            ≈ 2 GB

Roughly 500× the memory, and every check is an O(log N + M) write
(N = current set size, M = expired entries dropped) instead of a
counter increment.

A terabyte of memory, to buy exactness that requirement 4 said you do not need. Say that out loud and move on. The calculation is the argument.

There is a second, quieter problem. Redis runs the commands for a given shard on a single thread, so one script that walks ten thousand sorted-set members blocks every other command on that shard while it runs. The damage to your slowest responses is worse than the memory bill.

Sliding window counter

The approximation, and the right default when you want window semantics. Keep two counters, stored as two separate Redis keys: one for the current window, one for the previous window. Estimate the recent rate by counting the current window in full and the previous window in proportion to how much of it still falls inside the last sixty seconds.

estimate = current_count + previous_count × overlap_fraction

at 11:01:15 with a 60s window:
  25% into the current window, so 75% of the previous window
  is still inside the trailing 60 seconds

  estimate = 30 + (90 × 0.75) = 97.5  →  under 100, allow

This assumes traffic in the previous window was spread evenly, which it was not. The question is how much that assumption costs you, and Cloudflare published the answer. Across 400 million requests from 270,000 distinct sources, 0.003 percent of requests were wrongly allowed or wrongly blocked, and the gap between the real rate and the estimate averaged about six percent. Nothing under the threshold got blocked, and the few sources that slipped through were less than fifteen percent over.

Three thousandths of one percent, for two counters instead of a terabyte. That is the trade that makes the whole approach defensible, and quoting a real measurement for it is much stronger than calling the error "small."

Token bucket

A bucket holds up to capacity tokens and refills at rate tokens per second. Each request takes one token, or cost tokens. If the bucket is empty, reject.

You never run a background timer to add tokens. You refill when you read: a request arrives, you work out how many tokens should have built up since you last touched the bucket, cap that at capacity, then decide. Two numbers of state, the token count and the time of the last refill.

The reason to prefer it is not accuracy. It is that it has two knobs instead of one. Real requirements almost always arrive in two parts: "1,000 requests per minute sustained, but tolerate a burst of 100." The burst clause is there so a page load firing several calls at once does not get thrown out. A token bucket says both parts directly: capacity=100, rate=16.7/s. Window-based algorithms have one knob, so you have to choose between allowing bursts and holding a sustained rate. Stripe's public writeup describes exactly this setup: a token bucket per user in Redis, with the read, the arithmetic and the write all inside one Lua script so nothing can interleave.

Leaky bucket is worth one sentence: instead of instantly saying yes or no, it puts requests in a queue and lets them out one at a time at a fixed rate, so the output becomes perfectly smooth. The cost is that requests now wait in line instead of getting an instant answer, which is bad when the client is sitting there with a timeout. Know it exists, don't use it here.

Choosing

Default to the token bucket: it has two knobs, burst size and sustained rate, which matches how limits are usually described in the first place. It's no more expensive to run than the other options here, except the sliding window log.

Use a fixed window counter only for cheap, rough limits where the boundary-burst problem doesn't matter, like a very high per-customer ceiling whose only job is catching a runaway retry loop. It's just one INCR, so it's cheaper than running a script.

Use the sliding window counter when the requirement is actually stated as a trailing window, like "1000 requests in any rolling 60 seconds."

Never use the sliding window log in production.

4. What stops two requests reading the same counter?

This is the part that separates people who have implemented a rate limiter from people who have read about one. Everything above assumed that checking a counter and updating it happen as one act that nothing can get between. By default they do not, and the failure is not subtle.

-- KEYS[1] = the bucket's key
-- ARGV[1] = now_ms, ARGV[2] = capacity, ARGV[3] = refill_per_sec, ARGV[4] = cost
local now_ms         = tonumber(ARGV[1])
local capacity       = tonumber(ARGV[2])
local refill_per_sec = tonumber(ARGV[3])
local cost           = tonumber(ARGV[4])

-- 1. Read what's stored. If this bucket has never been touched before,
--    treat it as full, refilled just now.
local state  = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(state[1]) or capacity
local last   = tonumber(state[2]) or now_ms

-- 2. Work out how many tokens should have refilled since last time,
--    capped at capacity so it can't overfill.
local elapsed = math.max(0, now_ms - last) / 1000
local filled  = math.min(capacity, tokens + elapsed * refill_per_sec)

-- 3. Not enough tokens: deny, and report what's left.
if filled < cost then
  return { 0, math.floor(filled) }
end

-- 4. Enough tokens: spend `cost` of them, save the new state, and let
--    the key expire on its own if this principal goes quiet.
redis.call('HSET', KEYS[1], 'tokens', filled - cost, 'ts', now_ms)
redis.call('PEXPIRE', KEYS[1], 120000)
return { 1, math.floor(filled - cost) }

Which data store, and why persistence is actively wrong

Two storage decisions have been made by now: where the counters live, and where the rules live. They land on different data stores for opposite reasons, and the counter one is the interesting inversion.

The property that makes all of this safe is that the data is worthless within seconds. That single fact is what lets you skip persistence, skip synchronous replication, and treat resharding as a non-event, which the deep dives return to. A candidate who says "Redis" has named a product. A candidate who says "this state expires in one second, so durability buys nothing a user could perceive" has explained the choice. That answer covers why any in-memory data store would do, and why the expensive options are not better.

The state, and why it is barely a schema

There are no tables on the hot path. What there is:

# The counter. One key per (principal, rule, window).
#   key    rl:{rule_id}:{principal}:{window_start}
#   value  integer
#   ttl    2 x window        (long enough for the sliding
#                             window counter to read the
#                             previous window, no longer)

# The token bucket. Two fields, written together.
#   key    tb:{rule_id}:{principal}
#   value  { tokens: float, last_refill_ms: int64 }
#   ttl    idle timeout, so silent principals evict themselves

# The rules. Small, relational, replicated to every gateway.
rules (
  rule_id      bigint primary key,
  scope        smallint,        -- api_key | user | ip | route
  match        text,            -- which principals it applies to
  limit_count  int not null,
  window_ms    int not null,
  burst        int,             -- token bucket only
  version      bigint not null, -- for safe rollout
  updated_at   timestamptz
)

Three things to note.

The key encodes the window, so expiry does the cleanup. Putting window_start in the key means old windows become unreachable and are reclaimed by TTL rather than deleted. No sweeper, no delete rate to worry about.

The token bucket stores a timestamp, not a schedule. Tokens are refilled lazily, computed from elapsed time on read, so there is no background job ticking every bucket. A bucket nobody touches costs nothing at all, which matters because most principals are idle most of the time.

Rules carry a version, and it matters more than it looks. If a rule change reaches half your gateways before something goes wrong, you now have two different sets of rules running at once, which is worse than not pushing the change at all. So each gateway reports back which version it's currently running, and you only call the rollout complete once every single gateway has confirmed it moved past the old version, not just some of them.

The operations that carry the product

There's exactly one operation that matters here, and it runs on every request: the sliding window counter check from earlier, as a single atomic script. In Redis's language, that's:

-- KEYS[1] = current window's key, KEYS[2] = previous window's key
-- ARGV[1] = window_ttl_ms, ARGV[2] = overlap_fraction, ARGV[3] = limit
local window_ttl_ms    = tonumber(ARGV[1])
local overlap_fraction = tonumber(ARGV[2])
local limit            = tonumber(ARGV[3])

-- 1. Increment the current window's count. If this is the first
--    request in the window, make it expire once the window ends.
local cur = redis.call('INCR', KEYS[1])
if cur == 1 then redis.call('PEXPIRE', KEYS[1], window_ttl_ms) end

-- 2. Read the previous window's count. 0 if it's already expired.
local prev = tonumber(redis.call('GET', KEYS[2]) or 0)

-- 3. Estimate the rate: this window in full, plus however much of
--    the previous window is still inside the trailing period.
local est = cur + prev * overlap_fraction

-- 4. Allow if that estimate is under the limit. Report it either way.
return { est <= limit and 1 or 0, est }

-- Runs on rule change, not per request. Gateways poll or
-- subscribe, then serve every decision from local memory.
SELECT rule_id, scope, match, limit_count, window_ms, burst, version
FROM rules WHERE version > $1;

The first one runs hundreds of thousands of times a second and must be a single round trip, which is why it is a script rather than three calls. The second runs a handful of times a day.

That ratio is the whole storage story. One operation matters and it touches memory; everything else is configuration. If you find yourself designing indexes or thinking about joins in a rate limiter, you have added a data store the problem did not ask for.

5. What should a rejection actually say?

A rejection is an API response and it deserves the same care as a successful one. Most implementations treat it as an afterthought, then wonder why blocked clients hammer them harder.

Use 429, and keep it distinct from 503. A 429 means "you went over your allowance." A 503 means "we are unhealthy." Those call for different behaviour from the client and they belong on different dashboards. Mixing them means you cannot tell a customer's runaway script from your own outage.

Always send Retry-After. This is the header that actually changes behaviour. Without it, the client can only guess, and guessing in practice means retrying immediately, which means your limiter now serves more traffic than your API did before you installed it. Rejecting without a retry hint turns a load problem into a bigger load problem.

Vary the retry hint per client. If you tell 10,000 blocked clients to come back in exactly 30 seconds, you have scheduled a spike for 30 seconds from now. Add a small random amount to the value for each one. Do not count on clients to do this themselves. Some will, most will not.

Send the limit state on successful responses too. What everyone actually uses is X-RateLimit-Limit, X-RateLimit-Remaining and X-RateLimit-Reset, which is what GitHub and most large APIs send. A client that can see it has 12 calls left will slow itself down, and a client that throttles itself is worth more to you than any enforcement you can do at the edge.

Do not queue rejected requests. Holding a request until allowance frees up adds delay for a caller who has probably timed out already, and it turns a cheap rejection into a held resource. Drop the request and let the client come back.

Log every denial with the rule that caused it. Without that, "why is my integration getting throttled" is a support ticket nobody can answer, and you will get that ticket. Log a sample rather than every one, but make sure the rule ID is in there.

Deep dives

Which of these comes up depends on the interviewer and on the level you are interviewing at. The first three are the most common by a wide margin.

1. How big does Redis need to be?

This is where the design stops being a diagram. Run the arithmetic in the interview. It takes ninety seconds and it changes the answer.

Active keys
  1M req/s peak, average active principal makes ~10 req/min
  → 1,000,000 × 60 / 10        ≈ 6M active principals per minute
  × 3 rules each               ≈ 18M live keys

Memory
  token bucket entry, with key string and Redis overhead ≈ 200 B
  18M × 200 B                  ≈ 3.6 GB
  → comfortably one node

Throughput
  1M checks/s, one atomic script each
  a Redis shard handles ~100k simple ops/s with headroom for p99
  1,000,000 / 100,000          = 10 shards minimum
  plus headroom for failover and peak
                               ≈ 20 shards

Memory says one node. Throughput says twenty.

That gap is the interesting result, and it is worth stating plainly: this cluster is sized by operations per second, not by how much data it holds. Most data stores you size are the other way round, so the instinct to shard because the data is big will mislead you here. You are sharding for CPU.

Which sets up the payoff. Go back to leased quota with a block size of 50 and run the throughput line again: 20,000 operations per second instead of a million. That fits on a single primary with a replica. Batching does not just reduce load on the cluster. It removes the need for the cluster. Twenty nodes down to two, with far less that can break and nothing spanning shards. This is proof that the staff-level answer earlier wasn't just a nice idea, it actually holds up under the numbers.

But that 20,000 figure assumes every single rule can be leased, and that's not true: small limits can't be leased at all, so they still hit Redis once per request. The next section works out what fraction of your traffic realistically qualifies for leasing. The conclusion still holds, but only because of that traffic split, which you have to state as an assumption, not because batching guarantees it on its own.

A few more choices in this area, each with a one-line reason:

• Replication: asynchronous, and never wait for it. A counter increment lost during a failover costs you a handful of extra allowed requests. Waiting for replication costs you latency on 100 percent of requests. That trade is not close.
• Persistence: off, or as close to off as your operator lets you get. This data is worthless within seconds. Paying for a disk write on the hot path buys nothing. After a cold restart every key starts empty, which briefly hands everyone a fresh window. If that matters, warm up from a replica rather than from disk.
• Eviction: let idle keys expire. Every write to a counter also sets an expiry a little longer than the window it covers, say 65 seconds for a 60-second window. The extra 5 seconds isn't fixing anything specific, it's just a comfortable safety margin against ordinary timing slop (network delay, command processing time), not something that needs to be exact. Without a TTL at all, a key never disappears on its own, so every principal who ever made even one request, including someone who used your API once a year ago and never came back, still has a key sitting in Redis forever, and your key count keeps climbing toward "everyone who has ever existed" instead of staying near "who's active right now," which is the number you actually sized the data store for. maxmemory-policy = allkeys-lru is the backstop for when your TTL logic has a bug anyway: instead of Redis refusing writes or crashing once memory runs out, it quietly deletes the Least Recently Used keys to make room. Worst case, some rarely-used principal's counter resets a little early and gets a slightly fresher allowance than it should, a small accuracy hit you can absorb. Without that backstop, the same bug fills memory completely and takes the whole node down, which kills your rate limiter entirely, not just its accuracy.

2. Where does the 5 ms go?

The limiter runs on every request, so its p99 lands inside your API's p99 and its p999 lands inside your API's p9999. A limiter that is slow one time in a thousand, at 50 ms, shows up in your public latency graphs.

  same-AZ Redis round trip             0.4 to 1.0 ms
  cross-AZ round trip                  1.0 to 2.0 ms
  Lua script execution                 0.02 to 0.1 ms
  serialization + connection checkout  0.1 to 0.5 ms
  ─────────────────────────────────────────────────
  one round trip, same AZ              ~1.5 ms typical
  two round trips, cross-AZ            ~5 ms, budget gone

The rules that follow from it:

One round trip per request, never several. Check every matching rule in a single script over keys that live on the same shard. That is the whole reason for hash tags and for the descriptor list in the API.

Open your connections in advance, and size the pool for peak. Connecting per request is an obvious mistake. The less obvious one is a pool that is big enough at p50 and turns into a queue at p99. Time spent waiting for a connection does not appear in your Redis metrics at all, which makes it a nasty source of slow responses. Watch it from the client side.

Set a tight timeout, and treat a timeout as allow. Five to ten milliseconds. The version that goes badly wrong has no timeout at all. Redis gets slow, every gateway thread blocks on it, and the thread pool fills. A brief Redis wobble becomes a full outage in a service that had fail-open logic the whole time. The logic was right. The deadline was missing.

Remember the shard is single-threaded. One expensive command delays every other command on that shard. Cap the work any script can do, and never let an unbounded collection into one, like the sliding window log's sorted set from earlier. And keep the KEYS command out of production entirely: it scans your whole keyspace and blocks everything else while it runs, which on a database with millions of keys can freeze a shard for seconds. This is a different thing from the KEYS[1] you've seen throughout the Lua scripts in this doc, that's just how a script receives its key arguments. The standalone KEYS command is the dangerous one.

Cross-AZ writes are unavoidable in the obvious layout. Writes go to a primary, the primary sits in one availability zone, so two thirds of a three-zone gateway fleet pays a cross-zone hop on every request. You can pin shards per zone, but then your counts are per zone and the global limit is a fiction. Or call Redis less often instead, which is leasing again: batch 50 requests into one call instead of one call per request. Fewer calls means fewer cross-zone hops too, the same fix that already solved throughput and cluster size now solves this as well. One mechanism, three problems. That is usually the sign you have found the right abstraction.

3. How many gateway instances, and what does the fleet size break?

Nobody asks "how many servers" on its own. It arrives inside other questions. How does a gateway find the limiter service. What happens when the fleet scales up in the middle of an incident. What breaks when you add a shard. Every one of those needs a number the design has been quietly assuming, so work it out first.

Step 1: how many gateway instances are there?
  1M req/s peak, one gateway handles ~5,000 req/s comfortably
  1,000,000 / 5,000                       = 200 instances

Step 2: how much can leasing overshoot the limit, worst case?
  every instance could be sitting on a full unspent block at once:
  worst case overshoot = instances × block_size

Step 3: how big can a block be and stay under the 5% overshoot
allowed by requirement 4?
  block_size ≤ 0.05 × limit / 200 instances

  limit      1,000/min  →  max block     0.25   cannot lease at all
  limit     10,000/min  →  max block      2.5
  limit    100,000/min  →  max block       25
  limit 10,000,000/min  →  max block    2,500

Step 4: at what limit does the max block size finally reach 1 token?
  200 instances / 0.05 tolerance          = 4,000 per minute
  below that, no block size satisfies the 5% tolerance at all

A limit below roughly 4,000 per minute cannot be leased at all on a fleet this size. The block would have to be smaller than one token. That is the bound nobody states when they reach for leasing, and it follows from one multiplication.

So leasing is a decision per rule, not a decision for the system. Large limits lease with generous blocks. Small ones go to Redis on every request, which is exactly what the senior-tier answer already did. The staff-tier answer does not replace it. It sits on top of it for the rules where the arithmetic allows.

Which means the throughput figure from the sizing section deserves a harder look, because it assumed everything was leasable:

Assume 90% of your total traffic falls under large limits, the
enterprise API keys and per-tenant ceilings, and the remaining
10% falls under small limits (a strict per-IP limit, a tight
per-user limit) too small to lease at all, per the previous
section. These are aggregate req/s across however many
principals fall into each bucket, not a single rule's own limit.
Validate this split with the interviewer, because it is doing a
lot of work here.

  leasable traffic    900,000 req/s / 50 (block)  =   18,000 ops/s
  unleasable traffic  100,000 req/s × 1           =  100,000 ops/s
  ──────────────────────────────────────────────────────────────
  total                                           ≈  118,000 ops/s

  vs 1,000,000 with no leasing at all             →  8.5× reduction
  shards at ~100k ops/s each                      →  1.2, call it 2

If the split is 80/20 instead, the total is 216,000 ops/s
and you need three shards rather than the two above.

The twenty shards still collapse to two or three, so the earlier conclusion survives. But it survives because of a traffic assumption, not because of the batching alone, and the honest version of that claim names the assumption. The small-limit traffic sets the floor on Redis, and no amount of batching moves it.

Two things follow from this, and both need coordination the design didn't need before.

First: the fleet size itself now affects correctness. If autoscaling doubles you from 200 instances to 400 during a spike, every block size you sized against 200 now overshoots by double too. So instances need to know roughly how many of them there are. Don't build a whole gossip protocol for this: the control plane is already pushing rules to every gateway, so just have it push the current healthy instance count on that same channel, and calculate the block size from it. It's fine if that count is a few seconds stale, the bound changes slowly, and staying on the safe side just costs a few extra Redis calls, not correctness.

Second: a shrinking fleet is the dangerous direction. Scaling down, or a routine rolling deploy, kills instances that are still holding unspent leases. Those tokens are gone until the lease expires, so your effective limit temporarily drops below what the customer is paying for, right while you're deploying. Fix: keep lease expiry short, ten to thirty seconds, and have each instance hand back whatever it's still holding when it shuts down cleanly. That turns a deploy-time dip into nothing, and it's one line in your shutdown hook.

How a gateway finds the limiter service only matters in the senior-tier design, where the limiter is a separate process. Use whatever service discovery your platform already gives you, for example Kubernetes Endpoints or Consul. And register on readiness, not on start: a brand-new instance hasn't warmed up its Redis connection or cached its Lua scripts yet, so if it starts taking traffic immediately, its first few requests pay extra latency or fail outright. Wait until it's actually ready before the load balancer sends it real traffic. The failure to avoid is discovery being on the request path: resolve in the background, cache the result, and keep serving the last known good set of endpoints when discovery itself is unavailable. This is the same fail-to-stale rule as the rule cache, for the same reason.

Resharding Redis while it's live would be terrifying on almost any other kind of data store, but it's nearly free here. Moving a slot means the counters in it get lost or briefly split across two nodes mid-move. On most systems that's a real incident. Here, it just costs a handful of extra allowed requests during the move, and nothing else, because that data is worthless within seconds anyway. Compare that to resharding a data store of record, like a database holding actual user data, where losing or splitting records mid-move would be a genuine loss, not a shrug.

The same property that let you skip persistence, skip synchronous replication, and fail open now makes resharding harmless too. Say that out loud: it's the third place the same one requirement, approximately correct is correct, pays for itself.

When the limiter itself is the bottleneck, shed rather than queue. If Redis is saturated and the timeout is firing, let the circuit breaker fall back to local buckets and keep the fleet serving. Never let requests pile up waiting for a limiter decision, that's the exact same mistake as forgetting a timeout on a call to Redis from earlier: no bound on how long you wait, so a slow dependency turns into a full outage. Same bug, just showing up here instead of there.

4. Hot keys and contention

Traffic is never even. One enterprise customer, or one attacker with a valid key, sends 200,000 requests per second under a single principal. That principal's key hashes to exactly one shard.

Two things just broke. The shard is over capacity, and it also serves thousands of other customers. The requirement to keep customers apart is gone: one client's volume is now degrading everyone who shares a shard with them.

5. What happens when Redis goes down?

Frame this correctly before answering, because the framing is the answer. If the limiter is a hard dependency of the gateway, then your real availability is the two multiplied together, and you have made things worse by installing protection. The requirement was that the limiter must never be able to take down the service it protects.

6. How does a rule change reach the fleet without causing an outage?

The control plane is where the interesting failures hide, and almost nobody brings it up.

Matching and precedence. A request can match several rules. Check all of them and reject if any rejects, matching Envoy's behaviour, and when two rules cover the same ground let the more specific one win. Build the matchers into something you can look up fast when rules load, for example a hash map keyed by route template plus a sorted list for the general-purpose rules, instead of comparing every rule against every request.

Distribution: push, with polling underneath. Gateways hold rules in memory and never make a request wait on config. Pushing changes over pub/sub gets them out in under a second, which is what you want when you are trying to stop an incident. Polling every 10 to 30 seconds gives you a floor. You need that floor because a pub/sub message can be missed, and an instance quietly running stale rules forever is a bad failure. Doing both is two different guarantees: push for speed, polling so everything eventually catches up.

Config failure must be safe. If the rule service is unreachable, keep serving the last rules you know were good, for as long as it takes. Both tempting alternatives are wrong: falling back to "no rules" means unlimited, and falling back to "deny" means an outage. Stale is the right answer here, and a rule set fifteen minutes old is fine.

Now the part that matters. A rule change reaches all of your traffic. Someone types 100 where they meant 100000, and an enterprise customer's whole integration starts returning 429 within a second, because you built fast propagation. A mistake spreading fast is a worse outage than a mistake spreading slowly.

So treat the rule data store like a deploy pipeline:

• Shadow mode. Every new or changed rule first runs with a "shadow" flag set. The limiter still evaluates it on every request and logs what it would have decided, but the flag stops it from ever actually returning a reject for that rule. Once you've checked the log and you're sure it's safe, you remove the flag. You look at the count, discover the rule would have blocked your largest customer, and fix it before it ships. This is the highest-value feature in the control plane and it costs almost nothing to build.
• Staged rollout. Enforce on one percent of gateway instances, then ten, then all.
• Versioning with instant rollback. Rules are immutable versions, and rolling back means selecting the previous version, not editing fields under pressure.
• A record of changes. Who changed what, when, and why. The first question in an incident review is always "what changed."

7. Can the limit be exact across regions?

Sooner or later someone asks for a limit that is exact across regions. The honest answer has two halves.

First half: you cannot have it cheaply. A round trip between regions is 60 to 150 ms. Putting one on every request is a non-starter, and it makes each region's request path depend on another region's health, which defeats the reason you have regions at all.

The practical options, in ascending order of effort:

• Per-region limits, documented as such. Split nothing, coordinate nothing, and tell customers the limit is per region. A lot of large APIs do exactly this, and it is a legitimate answer as long as you say it out loud instead of implying global enforcement you do not have.
• Static allocation. Divide the global limit across regions in proportion to how much traffic each one normally gets. Simple, needs no coordination, and works while traffic stays where you expect. It breaks during a regional failover, when one region suddenly absorbs everything and starts rejecting traffic while another region's unused allowance sits idle.
• Allocation with background rebalancing. A controller watches demand per region every few seconds and moves quota around. The coordination happens off the request path, so the latency budget is untouched, and it settles in seconds. This is what you build if the limits are contractual.

The second half is the payoff for the frame set in the first section. If the requirement really is exact global counting, month over month, checked against an invoice, then it is not a rate limiter. It is a metering pipeline: emit a usage event per request, add it up in the background, enforce with a lag of seconds to minutes, and reconcile for billing on a slower path. Different accuracy requirement, different latency budget, different failure behaviour, different team on call.

Saying that sentence is how you avoid the trap this question is built around. The candidates who lose the interview accept "it must be exact and global" as a requirement. Then they spend twenty minutes designing consensus for a component whose whole job was to be cheap and fast.

8. How do you know it is working?

Short, and worth including, because operating experience shows up here more clearly than anywhere else.

You need to be able to answer four questions quickly. How much traffic is being rejected right now. Which rule is rejecting it. Which customers are affected. And would a proposed rule change have rejected anything.

• Metrics: decisions by rule and outcome, limiter latency as a histogram rather than an average, Redis error rate, circuit breaker state, and how many decisions were served from local state rather than Redis.
• Deny rate is a product metric, not just an ops metric. A sudden rise means either an attack or a customer integration that broke five minutes ago, and those need very different responses. Alert on the shape of the change rather than an absolute threshold, because an absolute threshold on deny rate means nothing across a diverse customer base.
• Watch how many distinct label values you create. A metric like decisions_total{rule, outcome} is cheap: a few dozen rules times two outcomes is a few dozen time series. If you add principal as a label instead, you'll get one time series per API key per rule per outcome, tens of millions of them, which is what destroys your metrics backend. It will do it during an incident too, when key churn spikes. Keep per-principal visibility in sampled logs and a top-N summary instead, not in labeled metrics.

Final design

The path of one request:

1. The request arrives at the edge and reaches a gateway instance, which has already worked out the principal from the API key or session and normalised the route to a template.
2. Rate limiter middleware looks up the matching rules in its in-memory cache, which was filled by a push and is kept fresh by polling.
3. If the instance still holds unspent leased allowance for those rules, it decides locally and the request continues. No network call.
4. Otherwise it makes one script call to the shard that owns that principal's keys, checking every matching rule together, and takes out a block of allowance sized to how much traffic that key gets.
5. If any rule rejects, the gateway returns 429 with Retry-After, varied per client, and the rule ID goes to the sampled denial log. If every rule allows, the request proceeds and the response carries the remaining allowance so the client can pace itself.
6. If Redis times out or the breaker is open, the instance's own local bucket decides instead. Coarser, still bounded, never blocking.
7. Every decision emits a metric labelled by rule and outcome, never by principal.

And the numbers that justify the shape. A million requests per second, and roughly 18 million live keys at about 200 bytes each. Leasing cuts that to roughly 20,000 Redis operations per second, which one primary with a replica serves comfortably. The requests that reach Redis cost about 1.5 ms at p99. The ones that do not cost effectively nothing.

What is expected at each level

Sources

This article takes inspiration from these pieces, and they're worth reading in full!

• Cloudflare, How we built rate limiting capable of scaling to millions of domains. The origin of the sliding window counter error analysis: 400 million requests, 270,000 sources, 0.003 percent misclassified.
• Stripe, Scaling your API with rate limiters. Token bucket in Redis with Lua for atomicity, and the argument for running several distinct limiters rather than one.
• Lyft, Announcing Ratelimit and the envoyproxy/ratelimit source. Where the descriptor model and the reject-if-any-rejects behaviour come from.
• IETF httpapi working group, RateLimit header fields for HTTP. Still a draft after many revisions, which is itself informative about how settled this is.