d03 — Distributed Rate Limiter

A fully worked design. Small surface, deep tradeoffs — which makes it a good early confidence build and a very common warm-up question. The reported anti-pattern (name-dropping without defending the tradeoff) is especially easy to fall into here, because "use Redis" is the obvious answer and it is not an answer.

Run it first. A companion page builds five rate limiters as numbered, independently runnable blocks and measures where they disagree: Hands-On — Rate Limiting, Block by Block. Every number on it was produced by running the code.

Table of Contents

The Prompt

"Design a rate limiter for our API. We have a lot of customers on different plans, we run in several datacenters, and we need it to actually hold the limit — customers are billed on it."

"Customers are billed on it" is the load-bearing clause and it is easy to skim past. It changes the whole design: it means accuracy matters more than availability, which flips the fail-open/fail-closed decision that most candidates get wrong by reflex.

1. Requirements and Scope

Clarifying questions asked

"Is this protecting us from overload, or enforcing a billing/abuse limit?" The fulcrum. Overload protection wants fail-open (a limiter outage must not become a total outage). Billing enforcement wants fail-closed (failing open means free unlimited usage during your incident). The prompt says billed → fail-closed, with a caveat I will develop.

"How exact does it need to be?" Assumed: within ~1% over a minute is fine for billing reconciliation; a hard cap that is never exceeded is not required, because the billing system is the source of truth and the limiter is enforcement.

"What is the limit keyed on?" Assumed API key, with per-endpoint cost weights (a search request costs more than a health check).

"Are bursts legitimate?" Assumed yes — customers batch. That selects a token bucket over a window, because only a bucket can express "average 100/s but 1,000 at once is fine".

Functional

  1. allow(key, cost) -> (allowed, remaining, retry_after).
  2. Per-plan limits, changeable without a deploy.
  3. Per-endpoint cost weights.
  4. Multi-datacenter, one global limit per key.

Non-functional

PropertyTarget
Added latencyp99 < 2 ms — this is on every request, so it is the number that matters
Accuracywithin 1% of the limit over a minute
Availabilitymust not be a single point of failure for the API
Throughput1M decisions/sec

Explicitly out of scope

  • Per-user (as opposed to per-key) limits.
  • Dynamic limits that react to system load — that is d05, and it is a different problem: this one enforces a contract, that one protects capacity.
  • Quota accounting for billing itself; we enforce, the billing pipeline counts.

2. Scale Numbers

Decisions/sec. 1M. That is the number that kills naive designs, so say it early.

Latency budget. If the limiter adds 2 ms to a 50 ms request that is 4% — acceptable. If it adds 2 ms to a 5 ms request it is 40% — not. So the design must have a local fast path, and that observation drives deep dive A.

Keys. 1M active API keys. Per key we need: tokens (float), last refill (float), and the window — call it ~64 bytes with overhead. 1M × 64 B = 64 MB. Trivially memory-resident, which is a useful thing to notice out loud: this is not a storage problem, it is a coordination problem.

Network. At 1M/s, one round trip per decision to a shared store is 1M round trips/sec. At 0.5 ms same-DC that is 500 seconds of round-trip time per second — i.e. 500 concurrent in-flight requests just for rate limiting, by Little's law. Feasible, but it makes the store a critical dependency on the hottest path in the system. That is the argument for leasing.

Store sizing. 1M ops/s against Redis is roughly 10 shards at 100k ops/s each. With leasing at a factor of 20, it is 50k ops/s — one shard, comfortably. That is a 10× infrastructure difference from one design decision, and it is worth stating in exactly those terms.

3. API Surface

# In-process library, not a network service. See below.
allow(key, cost=1) -> Decision(allowed: bool, remaining: int, retry_after: float)

# Control plane
PUT  /limits/{plan}        {rate, capacity}      -> 204
GET  /limits/{key}                               -> {rate, capacity, remaining}

Why a library, not a service. A rate-limiting service adds a network hop to every request — which is the thing we are trying to bound to 2 ms. Every serious implementation (Envoy's local rate limit, gRPC, Stripe's) puts the decision in-process and uses a shared store only for coordination. Saying this unprompted is the strongest single move in this design, because "deploy a rate limiter service" is the reflex answer.

On the response: always return retry_after, computed as (cost - tokens) / rate. Without it clients retry blindly and you get a retry storm on top of the overload you were limiting. That one header is the difference between a limiter that sheds load and one that amplifies it.

4. Data Model

Shared store (Redis), per key per window:
  key: "rl:{api_key}:{window_index}"
  value: consumed (integer)
  TTL: 2 × window            # self-cleaning; no sweeper needed

Local, in each process:
  key -> (window_index, permits_held_locally, tokens, last_refill)

Config (pushed, not polled):
  plan -> (rate, capacity)
  endpoint -> cost_weight

Why the window index is in the key: it makes expiry free. The bucket for window N is never touched again once window N+1 starts, and the TTL reclaims it. The alternative — one key per API key with a stored timestamp — needs a read-modify-write to roll the window and cannot use TTL, which means you need a sweeper. This is a small decision that removes an entire background job.

Why TTL = 2× window, not 1×: a client whose clock is slightly behind may still be writing to window N as the store is expiring it. Two windows of slack costs nothing and removes a race.

5. High-Level Architecture

      request
         │
         ▼
  ┌──────────────────────────────────────────┐
  │  API process                             │
  │  ┌────────────────────────────────────┐  │
  │  │ Local limiter (in-process)         │  │   FAST PATH: no network
  │  │  • token bucket per key            │  │   ~200 ns
  │  │  • spends locally-held permits     │  │
  │  └───────────────┬────────────────────┘  │
  └──────────────────┼───────────────────────┘
                     │ only when the local lease is exhausted
                     ▼
        ┌──────────────────────────────┐
        │  Shared counter store        │  Redis Cluster, sharded by key
        │  atomic INCRBY via Lua       │  the ONLY coordination point
        │  TTL-scoped window buckets   │
        └──────────────────────────────┘
                     ▲
                     │ config push (not poll)
        ┌────────────┴─────────────┐
        │  Control plane           │  plan limits, endpoint weights
        └──────────────────────────┘

The whole design in one sentence: decisions are local; coordination is amortized by leasing; the store is on the slow path only.

6. Deep Dive A: Atomicity and the Round Trip

Two problems that pull in opposite directions.

The atomicity problem

Read-then-write over the network is a race:

Process A: GET rl:k:100 -> 99
Process B: GET rl:k:100 -> 99
Process A: SET rl:k:100 = 100   allow
Process B: SET rl:k:100 = 100   allow      ← 101 requests admitted at a limit of 100

Fix: one atomic operation. INCRBY returns the new value, so the increment and the read are the same operation:

-- KEYS[1] = bucket, ARGV[1] = amount, ARGV[2] = ttl, ARGV[3] = limit
local count = redis.call('INCRBY', KEYS[1], ARGV[1])
if count == tonumber(ARGV[1]) then
  redis.call('EXPIRE', KEYS[1], ARGV[2])   -- set TTL only on creation
end
return count

The Lua script matters for a second reason: INCRBY then EXPIRE as two commands can leave a key with no TTL if the process dies between them — a permanent leak, one key per API key per window, forever. Bundling them makes it atomic.

Note what this does NOT need: a distributed lock. The store is already a serialization point for a given key; using a lock on top would be strictly worse and is a common over-engineering tell.

The round-trip problem

One round trip per decision, at 1M/s, makes the store a critical dependency on the hottest path. Leasing fixes it: claim a batch of permits in one round trip, spend them locally.

def allow(key, cost=1):
    now = clock()
    window = int(now // WINDOW)
    held = local.get(key)

    if held and held.window == window and held.permits >= cost:
        held.permits -= cost                       # FAST PATH: no network
        return Decision(True, held.permits, 0.0)

    count = store.incrby(f"rl:{key}:{window}", LEASE, ttl=2*WINDOW)
    over = count - limit
    granted = LEASE if over <= 0 else max(0, LEASE - over)
    if granted < cost:
        return Decision(False, 0, retry_after(window, now))
    local[key] = Lease(window, granted - cost)
    return Decision(True, granted - cost, 0.0)

What leasing costs, precisely — and this is the part to volunteer:

  1. Over-admission on the tail. A process holding 20 unspent permits when the window rolls simply loses them — which is under-admission, harmless. But if a process holds permits and the limit is reached elsewhere, those permits are still spendable. Worst case over-admission = lease_size × process_count, once per window. At lease 20 and 50 processes that is 1,000 over a limit of, say, 100,000 — 1%, exactly my stated accuracy budget. That arithmetic is the justification for the lease size, and it should be stated as such rather than picked.

  2. Idle processes hoard. A process that leases 20 and then goes idle has stranded 19 permits for the rest of the window. With many low-traffic processes this becomes systematic under-admission.

Adaptive leasing fixes the second: size the lease from the key's observed local rate.

lease = clamp(1, observed_rate_per_window * 0.1, 100)

A hot key on a busy process leases 100 and almost never touches the store. A cold key leases 1 and is exact. The store load becomes proportional to the number of distinct busy keys, not to request volume, which is the property that makes this scale.

7. Deep Dive B: What Happens When the Store Is Down

The question the prompt actually set up, and the one most candidates answer by reflex.

The reflex answer is wrong here

"Fail open — a limiter outage shouldn't take down the API" is right for overload protection and wrong for billing. Failing open on a billing limit means every customer gets unlimited free usage for the duration of your incident, and your heaviest users — the ones most likely to be hitting the limit — get the most. That is a revenue incident on top of an availability incident.

But fail-closed is also wrong

Failing closed means a Redis outage becomes a total API outage. You have made the rate limiter — a supporting component — a hard dependency of the entire product. That is worse.

The answer: fail open with a degraded local limit

try:
    count = store.incrby(bucket, lease, ttl)
except StoreUnavailable:
    return self._degraded_allow(key, cost)

def _degraded_allow(self, key, cost):
    # Each process independently enforces global_limit / process_count.
    # We lose global precision; we keep a bound.
    local_limit = self.limit / self.process_count_estimate
    return self._local_bucket(key, local_limit).allow(cost)

What this gives you: the API stays up, and total admitted traffic is bounded at roughly the real limit rather than being unbounded. You lose exactness — a customer whose traffic is skewed across processes may get somewhat more or less than their limit — and you keep both availability and a bound.

process_count_estimate comes from the service discovery layer, which you already have and which fails independently of Redis. Stale by a few seconds is fine; the estimate only needs to be right to within a factor.

And then reconcile. Because this is billing, record every degraded-mode decision with a flag. When the store recovers, the billing pipeline knows which windows were enforced approximately. That is what makes fail-open acceptable for a billed limit — you are not abandoning the contract, you are deferring enforcement to a system that can be exact after the fact.

Three things fall out of this that are worth saying:

  • The limiter is enforcement; billing is accounting. Conflating them is what makes people choose fail-closed.
  • Degraded mode must be observable. A metric, an alarm, and a flag on the decision — otherwise you find out about it from a customer.
  • Test it. Failure-injection in CI that kills the store and asserts the API stays up and the degraded bound holds. Untested failure paths do not work.

8. Failure and Recovery

FailureDetectionContainmentRecovery
Store unavailableconnection error / timeout on incrbydegraded local limit (global/process_count), decisions flaggedstore returns; leases refresh within one window; billing reconciles flagged windows
Store slow (not down)p99 on the store callhard timeout of 5 ms → treat as unavailable. A slow limiter must never become the latency problemcircuit breaker; probe
One store shard downper-shard errorsonly keys hashing to that shard degradeshard recovers
Process dies holding a leasenone — invisiblepermits are simply lost → under-admission, which is safenext window
Clock skew across processeswindow index disagreementuse the store's clock for the window index (redis TIME), not each caller'smonitor skew; eject outliers
Config push failsconfig version metric per processprocesses keep the last known config — stale limits are better than no limitsretry; alarm on version divergence
Hot key (one customer 100× everyone)per-key store op rateadaptive leasing already amortizes it; the key is one shard's problemdedicated shard if sustained
Retry storm from limited clients429 rate vs request rateRetry-After on every 429 so clients back off correctly—
Thundering herd at window boundarystore op spike every windowjitter the window per key — window_index = (now + hash(key) % WINDOW) // WINDOW — so buckets do not all roll at once—

The window-jitter row is the non-obvious one and it is a real production problem: with a synchronized window, every key's bucket rolls at the same instant and every process misses its lease simultaneously, producing a 1M-op spike on the store once per window.

Deliberately accepted: up to ~1% over-admission from leasing, once per window per key. I accept it because eliminating it costs a round trip on every request, and the billing pipeline reconciles exactly. I would not accept it if the limit were a safety property rather than a commercial one.

9. Bottlenecks and Evolution

1. The store, at ~10× traffic. Adaptive leasing means store load scales with distinct busy keys, not requests — so this bottleneck arrives much later than the naive design. When it does: shard by key (already done), then increase lease sizes at the cost of accuracy.

2. Local memory, at ~50M active keys. 64 B × 50M = 3.2 GB per process, which is too much. Fix: a bounded LRU of local lease state, evicting cold keys back to store-per-request. Cold keys are by definition low-traffic, so the extra round trips are affordable — the memory bound and the latency bound are in tension and the LRU is where you resolve it.

3. Multi-region. This is the one that changes the design rather than scaling it. A global limit across regions needs cross-region coordination on the hot path, which is 80–150 ms — 40× my latency budget. The honest answer is that you cannot have an exact global limit across regions at low latency. The options are: partition the limit by region (simple, and a customer in one region cannot use another's allowance), or accept eventual reconciliation with a cross-region gossip of consumed counts (approximate, higher accuracy than partitioning). I would default to partitioning by region weighted by historical traffic, and say why.

4. Cost weights make the "limit" ambiguous. If a search costs 10 and a health check costs 1, is the limit in requests or in cost units? It must be cost units, and the API must return remaining in the same units, or customers cannot reason about it.

10. Tradeoffs Explicitly Rejected

Rejected: a rate-limiter microservice. The obvious answer, and it adds a network hop to every request — 0.5 ms minimum, against a 2 ms budget — plus a new hard dependency. Rejected because the decision is 200 ns of arithmetic; only the coordination needs to be remote. Flip condition: if limits had to be enforced across systems that cannot share a library (different languages, third-party gateways), a service or a sidecar becomes necessary.

Rejected: fixed windows. O(1) and simplest. Rejected because they admit 2× the limit across a boundary — 100 requests at 11:00:59.9 and 100 more at 11:01:00.1 are both within their windows. For a billed limit that is a contract violation a customer will find. Flip condition: if the limit were advisory, the simplicity would win.

Rejected: sliding window log. Exactly correct, no boundary effect. Rejected on memory: O(limit) timestamps per key, so at 10k/min across 1M keys that is ten billion timestamps. Flip condition: for a small number of high-value keys where exactness matters — say, a partner integration with a contractual hard cap — I would use it for those keys specifically. Nothing forces one algorithm for all keys.

Rejected: fail-closed. Correct-sounding for billing, and it makes the limiter a hard dependency of the whole API. Rejected in favour of degraded-local + reconciliation, which keeps both availability and a bound. Flip condition: if over-admission were a safety or compliance violation rather than a revenue leak, fail-closed is right and the availability cost is the price.

Rejected: a distributed lock per key. Rejected because the store is already a serialization point per key — INCRBY is atomic. A lock would add a round trip and a liveness failure mode (the holder dies, the key is locked) to buy nothing. Mentioning that you considered and rejected it is worth more than never raising it.

Rejected: strict global exactness. Achievable with a round trip per request and no leasing. Rejected on the arithmetic: 1M round trips/sec makes the store a critical hot-path dependency for a 1% accuracy gain that the billing pipeline recovers anyway.

The Hostile Critique

C1. "Your degraded mode divides the global limit by the process count. Your traffic isn't uniformly distributed across processes — you have a load balancer, sticky sessions, and one customer whose traffic all lands on three of your fifty boxes. Walk me through what that customer actually gets in degraded mode."

C2. "Adaptive leasing sizes the lease from the observed rate. A key that has been idle for an hour has an observed rate of zero, so it leases 1. Then a customer starts a batch job and sends 10,000 requests. What does your store see in the first second?"

C3. "You said use the store's clock for the window index. That's another round trip, on the path you just spent a deep dive removing. Or are you caching it — in which case, what happens to the cached offset when your process is descheduled for 200 ms?"

C4. "You return remaining from the local lease. That number is wrong — it's what's left in this process's lease, not what's left in the customer's global budget. A customer polling remaining across two connections gets two different answers. What are you actually telling them?"

C5. "1% over-admission 'reconciled by billing'. Show me the reconciliation. The limiter flags degraded windows — but leased over-admission isn't flagged, it happens in normal operation. So how does billing know?"

The Revision

R1 — Degraded mode must be traffic-weighted, not uniform (answers C1)

The critique is correct and it is a real flaw. With one customer's traffic on 3 of 50 processes, global_limit / 50 gives that customer 3/50ths of their limit — a 94% false-rejection rate during a store outage, which for a billed customer is worse than over-admission.

Change: derive the degraded local limit from that key's observed local share, not from the process count.

# Each process continuously tracks its share of each key's traffic, from the
# ratio of its own local decisions to the counts it observes at the store.
local_share = ewma(local_decisions_for_key / store_count_for_key)
degraded_limit = self.limit * clamp(local_share, MIN_SHARE, 1.0)

Because the share is measured while the store is healthy, it is available exactly when the store is not. A process that normally serves 60% of a key's traffic enforces 60% of its limit.

Cost: more per-key state (one EWMA), and the share is stale by however long the outage has lasted. If traffic shifts during the outage the enforcement is wrong — but wrong by a factor, not by a factor of 17. And MIN_SHARE (say 0.02) prevents a process that has never seen a key from rejecting everything.

R2 — Lease size must react to a burst, not just to history (answers C2)

The critique is right: rate-based sizing is backward-looking, and a cold-start burst is exactly when you need a big lease. 10,000 requests with lease 1 is 10,000 store round trips in the first second for one key.

Change: multiplicative increase on lease exhaustion, within the window.

# Each time a lease is exhausted before the window rolls, double the next one.
if lease_exhausted_early:
    next_lease = min(next_lease * 2, MAX_LEASE)
else:
    next_lease = max(next_lease // 2, 1)      # decay when unused

A burst now costs log2(burst / initial_lease) round trips — about 13 for 10,000 requests instead of 10,000. It is AIMD's shape applied to lease sizing, and it converges within milliseconds.

Cost: the first few requests of a burst are slower (they take the store path), and the doubling can overshoot into more over-admission on the last lease. Bounded by MAX_LEASE, which I would set from the accuracy budget: MAX_LEASE × process_count ≤ 0.01 × limit.

R3 — Do not use the store's clock per request (answers C3)

The critique catches a contradiction. Fetching the store's time per decision reintroduces the round trip I designed away.

Change: synchronize the offset on the leasing round trip, which is already happening.

  • The Lua script returns the store's time alongside the count — free, same round trip.
  • The process maintains offset = store_time - local_time, smoothed.
  • The window index is computed from local_time + offset.

Since a lease refresh happens at least once per window per active key, the offset is never more than one window stale for any key actually in use.

On the 200 ms descheduling case: the offset is still valid on wake — it is a clock offset, not a timestamp, and the wall clock advanced normally while the process was descheduled. What is stale is the lease's window index, and the existing check (held.window == window) already catches it and forces a store round trip. So the answer is that the design already handles it, and I should have said so.

Cost: none meaningful. This is what should have been written the first time.

R4 — remaining must not lie (answers C4)

The critique identifies a genuine API defect. Returning a local lease count as remaining gives different answers on different connections and is actively misleading.

Change: return the number the customer can act on, and say what it means.

X-RateLimit-Limit:      100000        # the plan limit, per window
X-RateLimit-Remaining:  42317         # global, as of the last store sync
X-RateLimit-Reset:      1735689600    # when the window rolls
X-RateLimit-Stale:      0.8           # seconds since the global number was refreshed

Remaining is the global count from the last store interaction, not the local lease. It is slightly stale, and X-RateLimit-Stale says by how much — so a client that needs precision knows when to distrust it.

Cost: Remaining is stale by up to one lease's worth of local spending. That is honest and bounded, versus the previous version which was wrong and unbounded. And exposing staleness rather than hiding it is the right instinct for any cached value on an API.

R5 — Reconciliation needs the leased counts, not just the flags (answers C5)

The critique is correct and this was hand-waving. Leased over-admission happens in normal operation, so a degraded-mode flag does not capture it.

Change: the store is the accounting record, and it already has the answer.

  • The store's per-window counter is incremented by leased amounts, so it records what was authorized, not what was spent. At window roll, authorized ≥ spent.
  • Each process reports its actually spent count per key per window to the metrics pipeline on window roll — one small message per busy key per window, not per request.
  • Billing uses spent, which is exact. The store's authorized count is only used for enforcement.

So the reconciliation is: enforcement is approximate and cheap; accounting is exact and asynchronous. They are different systems with different guarantees, deliberately.

Cost: a metrics path that must not lose messages, or billing under-counts. That is a lower-stakes durability requirement than the request path and can use at-least-once with dedupe by (key, window, process_id).

And the general lesson worth stating: when a system needs both fast enforcement and exact accounting, do not try to make one component do both. Enforce approximately on the hot path and count exactly off it.

References