04 — Design A Rate Limiter

A rate limiter is code that sits in front of a service and decides, for each arriving request, whether to serve it or reject it. The decision is based on how many requests that same caller has already made recently.

The standard algorithms are the token bucket, the leaking bucket, the fixed window, and the sliding window. Sliding window comes in two forms different enough to be treated as separate algorithms, which is why there are five names and not four. Each one is derived below to how many requests it lets through in its worst case, which is the moment a counting period rolls over from one to the next.

The rest of the chapter keeps that decision correct when twenty machines share a single counter.

This chapter covers three things: how to pick an algorithm given a limit and a memory budget, how to state an algorithm’s worst case as a number rather than an adjective, and what happens to the service when the counter storage goes down.

The input is one request. From it the limiter extracts three things:

• a key naming who is being limited — a customer id, an API key, or an IP address;
• the route being called, so GET /v1/users and POST /v1/charges can carry different limits;
• a cost, almost always 1, meaning “this request counts as one request.”

The output is a verdict plus the numbers a well-behaved caller needs. The arrow separates the call from its reply, and the fields after allowed are what the caller is told:

check(key="cust_42", route="POST /v1/charges", cost=1)
  ->  allowed = false
      limit = 100          the ceiling for this caller on this route
      remaining = 0        how much budget is left
      retry_after_ms = 6000    when it is worth trying again
      reset_at = ...           when the budget refills

An allowed = false verdict becomes an HTTP 429 Too Many Requests response, carrying a Retry-After header telling the caller how long to wait.

The rest of this chapter is about how those five fields get computed correctly, cheaply, and identically on every machine in the fleet.

The rate limiter is a contended-counter system: every machine in the fleet reads and writes the same small piece of shared state. There is no fan-out to design, no ranking to invent, and no cache-invalidation puzzle. What is left is one counter shared by every machine that touches it, and the design turns on what each candidate algorithm does at a window boundary.

The core design decision is a three-way trade:

• memory per key — bytes of state kept per caller;
• burst tolerance — how many requests you are willing to let through all at once;
• exactness — how far the count is allowed to be from the truth.

Every algorithm below sits at a different corner of that triangle, and the arithmetic picks one.

This chapter follows the interview framework of chapter 03 — A Framework For System Design Interviews. The order is requirements, then estimates, then mechanism, then failures.

1. Framing: what a rate limiter is actually for

One question must be answered before choosing anything else: which of three different jobs the limiter is doing. The three jobs want different algorithms and disagree about what “correct” means, yet they all get called “rate limiting.” State which one you are building first.

The three jobs are below. The third column is where they diverge.

Note the third row. Abuse prevention is the only job where an approximate count is unacceptable; “about five password resets an hour” is not a security control. It is also the job with the smallest limits, because five is a sensible number of password resets and 100,000 is not.

Small limits are exactly where the cheap approximate algorithms are worst, for a reason Sliding window counter and exactly how wrong it is derives from counting statistics. So the job that most needs exactness is the job where approximation fails hardest.

Why a limiter at all

Consider what happens without one. A single misbehaving client — usually a customer’s own retry loop, not an attacker — saturates a shared database and turns into a full outage for everyone.

A rate limiter is the cheapest available bulkhead: a partition that keeps damage in one compartment from flooding the whole ship.

To do that job it has to sit before anything expensive in the request path. Suppose authentication runs first and each authentication costs one database lookup. A flood of unauthenticated requests then buys free database lookups at the rate the attacker can send them: the limiter rejects the requests, but only after you have paid for them. A rejection has to cost less than an acceptance, or the limiter is not protecting anything.

2. Requirements

Only a few requirements constrain the design. Two of them, the latency budget and the availability target, rule out entire architectures on their own.

Functional

The list is written as scope in and scope out: the IN lines are what you are building, the OUT lines are what you decline to build.

Two phrases need defining first. Per-route means the limit can differ for GET /v1/users and POST /v1/charges. Per tier means the free plan and the enterprise plan get different numbers for the same route.

IN     enforce a per-client request limit on a per-route basis
       return a machine-readable rejection (429 + when to retry)
       limits configurable per tier and per route, without a deploy
       multiple limits composable on one request (per-client AND per-IP)
OUT    billing, quota purchase flows, WAF/bot detection, DDoS scrubbing

Two acronyms in the OUT line are worth defining, because they are common follow-ups.

A WAF is a web application firewall. It inspects request content for attack patterns such as SQL injection. A rate limiter looks only at counts, not content, so the two share no machinery.

DDoS scrubbing handles a distributed denial-of-service attack, meaning many machines flooding you at once. It belongs upstream at the network edge, because by the time traffic reaches your gateway you have already paid to receive it.

Both are adjacent products that solve different problems.

Non-functional — these decide the architecture

The five rows below are the requirements that constrain the design. The third column says what each requirement removes from the option space.

Three terms in that table need pinning down before the rows mean anything.

p99 latency is the 99th percentile: the number that 99 of every 100 requests come in under. A p99 of 5 ms means the slowest one request in a hundred still finishes within 5 ms. Averages hide the tail; percentiles are what users feel.

Fail-open means that when the limiter’s own machinery breaks, requests are allowed through rather than rejected. The opposite policy, fail-closed, rejects them — which turns a limiter outage into a total service outage that you caused.

Eventually consistent means copies of a value on different machines are allowed to disagree for a while, and are only guaranteed to agree once updates stop. That is a fine bargain for a profile picture. It is a bad one for a counter whose job is to be right during a burst, which is precisely when the copies disagree most.

The limiter must be more available than the thing it protects. That requirement determines what happens when the counter store is down.

3. Back of the envelope

One traffic figure turns into the four numbers that decide the design:

1. how many counter-store machines you need,
2. how much memory each algorithm costs,
3. how much network the limiter uses,
4. how much of the latency budget a shared counter consumes.

Every later section spends one of these numbers.

3.1 The starting assumptions

Start from the assumed traffic. A gateway here is a machine at the front of the fleet through which every request passes before reaching the service being protected, the natural place to put a limiter.

Everything in the block below is an assumption, not yet derived:

peak gateway rate                          100,000 req/s
gateway nodes                                       20
distinct clients active per day              1,000,000
distinct clients active in any 60 s window     200,000
default limit                                100 per 60 s

Before spending those numbers, check they describe a coherent world. Divide the fleet’s request rate by the number of clients producing it to get what one median client sends:

requests/s per active client   100,000 / 200,000 = 0.5 req/s
requests/min per client                0.5 x 60 = 30  req/min

The median client uses 30 of an allowed 100, so it sits at 30% of its limit. That is what a sane default looks like: most callers never notice the limiter exists.

If that ratio had come out at 300%, the conclusion would be that the limit is wrong, not the design: you would be building a system whose normal state is rejecting everyone. This check catches a bad premise before you build on it.

3.2 Store throughput: how many shards

The shared counter needs somewhere to live, and the standard choice is Redis.

Redis is an in-memory key-value store: it keeps all data in RAM rather than on disk, and it serves simple get/set/increment operations over the network in microseconds. Two properties of it matter here, and they are two sides of the same fact.

Redis executes commands one at a time on a single thread. That is why it can guarantee no two commands interleave — the property Where the counter lives and the race that makes incr expire wrong builds the whole correctness argument on. It is also why one instance has a hard throughput ceiling: one thread is one thread.

That ceiling is roughly 100,000 simple operations per second, when each command is sent and answered on its own. Sending commands one at a time is called unpipelined, as opposed to pipelined, where many commands are batched into one network write. The ceiling comes from the per-command system-call and event-loop cost, not from the work the command does — which is why “simple operation” and “complicated operation” land in the same ballpark.

Budget one shared-store operation per request. Then one instance would have to carry the entire peak:

peak rate / one instance's ceiling
100,000 req/s / 100,000 ops/s = 1.0 instance

One instance at 100% utilization. That is not a design — there is no headroom for a peak you did not forecast, and no second machine to survive the loss of the first.

Pick a target utilization instead. At 30% utilization, the throughput you must actually provision is the peak divided by 0.30:

required capacity      100,000 / 0.30 = 333,333 ops/s
instances needed     333,333 / 100,000 = 3.33
round up                                 4 shards

Now check what four shards actually gives you, because 3.33 rounded up to 4 leaves you below the 30% you asked for:

per shard        100,000 / 4 = 25,000 ops/s
utilization   25,000 / 100,000 = 0.25 = 25%

Four shards, each at 25,000 ops/s, each 25% utilized. The 75% left idle on each shard is what absorbs a failover: if one of the four dies and its traffic spreads over the other three, each goes from 25,000 to about 33,300 ops/s, still a third of the ceiling.

Two terms. A shard is one of several independent copies of the store, each owning a disjoint slice of the keys; splitting the key space across shards is how you get past one machine’s ceiling. A failover is the automatic promotion of a standby machine when the primary dies, during which the dead shard’s traffic has to go somewhere.

3.3 Network: not the bottleneck, and saying so early

Each check sends roughly 200 bytes up (the script identifier, the key names, and the arguments) and gets about 100 bytes back, so one check moves 300 bytes total:

bytes per check          200 up + 100 down = 300 bytes
fleet bandwidth       100,000 x 300 = 30,000,000 bytes/s = 30 MB/s
as bits                  30,000,000 x 8 = 240,000,000 bits/s = 240 Mbps

Compare that against a standard 1 Gbps network card, which is 1,000 Mbps:

share of one card       240 / 1,000 = 0.24 = 24%
spread over 4 shards        24% / 4 = 6% of each card

24% of one NIC (network interface card, the machine’s link to the network), or 6% of each once the traffic is spread across four shards. Not a constraint.

The limiter is a latency and correctness problem, not a bandwidth one.

3.4 Latency: what the budget forbids

Assume a round trip of 0.5 ms between two machines in the same availability zone (AZ): one datacenter building, or a cluster of them close enough that the network between them is cheap and fast.

Both ends of the range are standing constants in this repo. 02 — Back Of The Envelope fixes the round trip within a datacenter at 500 us in its constants table and repeats it in Numbers worth memorizing cold. The same chapter fixes the two cross-region routes separately: 75 ms US-East to Europe, and 150 ms California to Europe.

Line the options up against the 5 ms budget from Requirements:

one round trip, same AZ                           0.5 ms
INCR then EXPIRE, two round trips     0.5 x 2 =   1.0 ms   (20% of budget)
the budget                                        5.0 ms
cross-region store, worst case                  150   ms

how far over budget         150 ms / 5 ms = 30x

A cross-region shared counter is 30x over the entire latency budget — out by more than an order of magnitude.

Two conclusions follow. First, the store must live in the same region as the gateways. Second, a limit that is supposed to be global cannot be enforced by one global counter; it has to be a per-region limit plus asynchronous reconciliation, meaning each region enforces locally in real time and the regions compare notes afterwards. The global number is then right eventually and wrong for a while.

3.5 Memory: the number that separates the algorithms

Redis costs roughly 100 bytes to hold one small key all-in. That breaks down as about 50 bytes for the hash-table entry and object header Redis wraps around everything it stores, plus a ~30-byte key string, plus the value itself.

Redis reports the true figure for any given key through its MEMORY USAGE command, and the absolute number is worth measuring on your own data. The ratios in the table below survive any plausible value for it, which is why the ratios are what you quote.

The table prices each algorithm at the 200,000 active keys assumed in The starting assumptions. The algorithm names are defined in The four algorithms derived; for now read the last column, and note that one row is unlike the others.

The sliding window counter’s row is easy to get wrong, and this chapter’s own key layout is why. The window index lives in the key name (rl:{client}:<route>:<window_idx>, see Data model), and the Lua script in The fix one script one round trip reads KEYS[1] and KEYS[2]. Those are two Redis keys, not two fields of one key. So the algorithm pays the ~100-byte per-key overhead twice: about 200 bytes per client, 40 MB across the fleet, not 130 and 26.

The token bucket, by contrast, keeps both of its numbers in a single Redis hash, so it genuinely does cost one key’s overhead.

The two sliding-window-log rows come from the arithmetic below. The log stores one timestamp per admitted request at ~70 bytes each, plus the ~100 bytes of key overhead every key pays. So the cost of one client’s key is n x 70 + 100, where n is how many requests that client made in the window.

The two rows use two different values of n: the median client’s 30 req/min from The starting assumptions, and a client pinned at the 100/min limit.

log, typical client at 30 req/min     30 x 70 + 100  =  2,200 bytes per key
across 200,000 keys      200,000 x 2,200 = 440,000,000 bytes = 440 MB

log, client pinned at the limit      100 x 70 + 100  =  7,100 bytes per key
across 200,000 keys      200,000 x 7,100 = 1,420,000,000 bytes = 1.42 GB

vs the token bucket           1,420,000,000 / 26,000,000 =  54.6x
vs the sliding counter        1,420,000,000 / 40,000,000 =  35.5x

The log costs 55x the token bucket in the worst case, and 36x the sliding window counter. State which baseline you mean, because the two counter algorithms do not cost the same and the two ratios are 20 apart.

Note what does not disqualify the log: 1.4 GB still fits comfortably in RAM. Memory alone is not the objection.

What disqualifies it is that the log is the only algorithm whose memory an attacker controls. If you record rejected requests as well as admitted ones, a client sending 50,000 req/s grows its own sorted set without bound:

requests in one window       50,000 x 60 = 3,000,000
bytes of timestamps       3,000,000 x 70 = 210,000,000 bytes = 210 MB

210 MB from one client in one 60-second window, and nothing stops the next window. Log only what you admit: then the set can never exceed L entries, and the memory is bounded by your own configuration rather than by the attacker’s send rate.

4. API and data model

The limiter exposes two surfaces, the per-request check and the configuration it reads, and its key layout carries four naming decisions.

API

The limiter is middleware: code that runs on every request, between the network and the application, rather than a separate service you call by name over the network.

It still has an internal contract, because that contract is where the Retry-After value comes from: the function has to return when to come back, not just no:

check(key, route, cost=1) -> {allowed, limit, remaining, retry_after_ms, reset_at}

Configuration is a separate surface, and a read-mostly one. Operators change limits rarely; the gateways read them constantly:

GET /v1/limits/{tier}
PUT /v1/limits/{tier}   {route_pattern, algorithm, limit, window_s, burst}

Data model

There are two stores, and their access patterns are opposites. The rules are read constantly and written almost never. The counters are written on every single request. That difference is why they are two stores and not one.

One abbreviation before the block: TTL is time to live, an expiry the store attaches to a key, after which the store deletes that key by itself. TTLs are how the limiter’s memory stays bounded without a cleanup job.

The block below is two schemas. The arrow in each COUNTERS line separates the key name from the value stored under it:

RULES  (config store; read-mostly)
  tier_id, route_pattern, algorithm, limit, window_s, burst, priority

COUNTERS  (Redis; hot path)
  sliding counter   rl:{client}:<route>:<window_idx>  -> int,  TTL 2 x window
  token bucket      rl:{client}:<route>               -> hash {tokens, ts},
                                                         TTL ceil(capacity/refill) + 1

Four details in that layout.

1. {client} is a Redis Cluster hash tag. Redis Cluster spreads keys across shards by hashing the key name into one of 16,384 numbered slots, with each shard owning a range of slots. When a key name contains braces, Redis hashes only the text inside them.

So rl:{cust_42}:api:99 and rl:{cust_42}:api:98 both hash on cust_42 and are guaranteed to land on the same shard. That guarantee is what makes a script touching several keys at once legal in cluster mode. Without it the sliding-window script — which reads the current and the previous window key — is rejected outright by the cluster, because the two keys might live on different machines and a script cannot span machines.

2. The window index is in the key name, not in the value. Rolling over to a new window then costs nothing at all: the old key simply stops being addressed, and deletes itself when its TTL passes. No code runs at the boundary.

3. Token-bucket TTL is derived, not chosen. After capacity / refill seconds with no traffic, the bucket has refilled completely. Its stored state now says exactly what a brand-new full bucket would say, so deleting it loses no information. At a capacity of 100 tokens and a refill of 1.667 tokens per second:

100 / 1.667 = 60 seconds

The + 1 in the schema above is a rounding margin, so the key never expires a fraction of a second before the bucket is genuinely full.

4. Rules never touch Redis on the hot path. The hot path is the code that runs on every single request, as opposed to background work that runs on a timer. Keeping rule lookups off it is what makes the limiter’s cost one round trip and not two.

That works because the rule table is tiny. 200 tiers at ~1 KB each is 200 KB — small enough to sit in every gateway’s own process memory, refreshed by polling the config store every 10 seconds.

When several rules could apply to one request, the most specific wins: client+route beats client, which beats tier+route, which beats tier, which beats the global default.

5. High-level architecture

A single request takes one path through the limiter, and that path contains the three choices the rest of the chapter defends.

The diagram below is that path, left to right. Solid arrows are the request path; dotted arrows are things that happen off it. The two branches out of the green diamond are the optimization story of The deny cache and why it is the highest leverage optimization.

flowchart LR
    C(["Client"]) -->|"100,000 req/s peak"| LB["L4 load balancer"]
    LB --> GW["Gateway<br/>20 nodes<br/>rules cached in-process"]
    GW --> DC{"Local deny cache:<br/>already blocked?"}
    DC -->|"yes · 0 round trips"| R429["429<br/>Retry-After + RateLimit-*"]
    DC -->|"no"| LUA["EVALSHA<br/>1 round trip · 0.5 ms"]
    LUA --> RS[("Redis · 4 shards<br/>hash tag on client id")]
    RS -->|"allowed"| UP["Upstream service"]
    RS -->|"denied"| R429
    CFG[("Rule config")] -.->|"poll every 10 s"| GW
    RS -.->|"unreachable"| FB["Local fallback bucket<br/>5,000 req/s per node"]

    style DC fill:#2d6a4f,color:#fff
    style RS fill:#1d3557,color:#fff
    style R429 fill:#9d0208,color:#fff
    style FB fill:#bc6c25,color:#fff

01 — Scale From Zero To Millions publishes a colour key for these same four hex values, and only two of them transfer here.

• Blue is the authoritative copy of the data, exactly as in ch 01 — the counter in Redis is the only copy that decides anything.
• Green takes load off the request path, also exactly as in ch 01 — the deny cache answers without a round trip.
• Orange is local to this chapter: the degraded path the limiter falls back to when the store is gone.
• Red is also local: a rejected request.

Orange and red are not ch 01’s meanings (“forced by something other than CPU” and “the one rung you cannot undo”), and nothing in this chapter is irreversible.

Walking one request through

Arrival. A request comes from a client, one of the 100,000 req/s peak of Back of the envelope, and hits an L4 load balancer. “L4” means layer 4, the transport layer: this box picks a destination using only the connection’s addresses and ports, and never reads the HTTP request itself. That is what makes it fast and cheap, and it is also why it cannot know anything about who the caller is.

Gateway. The balancer hands the connection to one of the twenty gateway nodes. Each gateway holds the rule table in its own process memory and refreshes it by asking the rule config store for changes on a poll every 10 s — the dotted arrow, off the request path.

Deny cache, the cheap branch. The gateway first consults its local deny cache, an in-process dictionary mapping a client id to the time until which that client is known to be blocked. A hit answers in 0 round trips and returns the full rejection immediately: 429 Retry-After + RateLimit-*, meaning the 429 status code plus the headers telling the caller when to come back, which The client contract 429 retry after and the retry storm specifies in detail.

Redis, the expensive branch. A miss costs exactly one call to Redis. That call is EVALSHA, which means “run the script I already uploaded to you” — 1 round trip, about 0.5 ms. It goes to the four Redis shards, addressed by a hash tag on client id so that every key belonging to one client lands on one shard (Data model).

The verdict. Redis answers allowed or denied. Allowed requests continue to the upstream service being protected. Denied requests become the same 429 the deny cache would have returned.

Store down. If Redis is unreachable, the gateway falls back to a local fallback bucket admitting 5,000 req/s per node, a number derived in Failure modes.

The three choices to defend

Three load-bearing decisions are visible in that picture, each defended in its own section below:

1. The limiter runs before authentication, because a rejection must cost less than an acceptance (Framing what a rate limiter is actually for).
2. The decision is one round trip and not two, which is both a latency argument and a correctness argument (Where the counter lives and the race that makes incr expire wrong).
3. The deny cache exists because the abusive client is, by definition, the one generating the most store load (The deny cache and why it is the highest leverage optimization).

6. The four algorithms, derived

Here are the five algorithms, the four classic ones plus the approximation most systems actually ship, each derived to how many requests it can let through in the worst case.

Every one answers the same question, “may this request proceed?”, from a small amount of stored state. They differ in three ways: what that state is, how much it costs, and how badly they can be gamed by a client that times its requests carefully.

Each subsection has the same four parts, for direct comparison: mechanism, state, burst derived to a number, and the assumption that, when it fails, means you picked the wrong algorithm. Side by side collects every number into one table, and What each algorithm assumes and what breaks when it does not hold collects every assumption.

Two terms recur. A window is the span of time over which requests are counted; “100 per minute” has a 60-second window. A burst is a clump of requests arriving much faster than the sustained rate. Burst behaviour is the axis on which these algorithms differ; on average throughput they are the same.

Common parameters throughout. The limit is L = 100 requests, the window is W = 60 s. Dividing one by the other gives the nominal sustained rate that everything below is measured against:

r = L / W = 100 / 60 = 1.667 requests per second

6.1 Token bucket

The token bucket is the algorithm to reach for when a client is allowed to save up unused allowance and spend it in one go, and it is the only one here where you can set the burst size independently of the sustained rate.

Mechanism. Picture a bucket that holds up to C tokens and is topped up at r tokens per second, with any overflow discarded. Each request must take one token to proceed. If fewer than one token is present, the request is rejected.

The refill is not performed by a background process. It is computed lazily on read, meaning the arithmetic happens at the moment a request arrives, from the time elapsed since the previous one:

tokens = min(C, tokens + (now - last) x r)

Read that line right to left. (now - last) x r is how many tokens would have dripped in since the last request. Adding it to the stored count gives the theoretical level, and min(C, ...) clips it to the bucket’s capacity, which is the “overflow discarded” part.

Lazy refill is not an optimization detail; it is what makes the algorithm affordable. A background refiller would need one timer per active key, and The starting assumptions counted 200,000 active keys. That is 200,000 timers you do not have to run.

State. Two numbers: tokens, a floating-point count, and last_refill, the timestamp of the previous request. Two 8-byte floats is 16 bytes of actual information, and about 130 bytes once Redis’s per-key overhead is added.

Burst, derived. Start from a full bucket and ask how many requests can get through in an interval of length T. Two sources of tokens are available: the C already sitting in the bucket, and the r x T that drip in during the interval. So

A(T) = C + r x T

Substitute the chapter’s numbers — capacity C = 100, refill r = 1.667 tokens/s — over one nominal window of T = 60 s:

A(60) = 100 + 1.667 x 60 = 100 + 100 = 200 requests

Up to 2L in a 60-second window, and the first 100 of them can land inside a single millisecond, because the bucket started full and nothing paces how fast you drain it.

That instantaneous burst is the feature. This is the only algorithm here where burst size is a knob separate from sustained rate, and the two settings below show what that buys:

• Set C = 20, r = 1.667: 100/min sustained, but never more than 20 at once.
• Set C = L = 100, r = 1.667: 100/min sustained, with a deliberate 2x window overshoot in exchange for letting clients save up a full minute of allowance.

Neither is wrong, but the second is a deliberate decision.

The implementation. The class below is the whole algorithm in about thirty lines. Three parts carry the lesson; everything else is bookkeeping:

• _spend is the algorithm itself: the min(...) refill line and the compare-then-subtract that follows it;
• the with self.lock in allow stops two threads from spending the same token, and the docstring gives the measured numbers for what happens without it;
• the not (x > 0) guards in __init__ are written that way because nan <= 0 is False, so a NaN would walk straight through the obvious spelling.

The docstrings record the failure each line prevents.

import math
import random
import sys
import threading
import time


class TokenBucket:
    """Lazy-refill token bucket: two floats of state, no timer per key.

    A background refiller would need one timer per active key -- 200,000 of
    them at the scale in section 3. Computing the refill at read time is
    exactly equivalent and costs one multiply and one min().

    THREAD SAFETY, WHICH IS NOT OPTIONAL. `allow` is a read-modify-write of
    `self.tokens`: read the count, compute the refill, compare, subtract,
    store. Two threads that read the same count both spend it and only one
    subtraction survives -- the identical race section 7 draws between two
    gateways, only inside one of them, and the reason it is drawn there and
    guarded here is that a reader who drops this class into a threaded
    gateway gets a limiter that does not limit. Measured: 16 threads x 1,500
    calls against a capacity of 500 admit 570-1,767 without the lock below
    and exactly 500 with it.

    In-process the fix is the `threading.Lock` this class takes: it is
    uncontended in the common case and costs tens of nanoseconds. ACROSS
    processes or machines a lock buys nothing at all, because there is no
    shared object to lock -- there the state has to live in the store and
    the whole decision has to be one server-side operation, which is the
    Lua script in section 7. Neither fix substitutes for the other.
    """

    def __init__(self, capacity: float, refill_per_s: float,
                 clock=time.monotonic):
        # `not (x > 0)`, never `x <= 0`. EVERY comparison with NaN is False,
        # so `nan <= 0` is False and a NaN refill walks through the guard --
        # after which `min(capacity, nan)` returns `capacity`, the bucket
        # silently refills to full on every call, and 20 of 20 requests are
        # admitted against a capacity of 3. Infinities do the same thing
        # without being NaN, so they are rejected on their own line.
        if not (refill_per_s > 0):
            raise ValueError("refill must be positive; NaN is not positive")
        if not (capacity > 0):
            raise ValueError("capacity must be positive; NaN is not positive")
        if math.isinf(capacity) or math.isinf(refill_per_s):
            raise ValueError("capacity and refill must be finite")
        self.capacity = float(capacity)
        self.refill = float(refill_per_s)
        self.clock = clock
        self.tokens = float(capacity)
        self.updated = clock()
        self.lock = threading.Lock()

    def allow(self, cost: float = 1.0):
        """Return (allowed, seconds_until_allowed)."""
        # `cost` is a public API parameter, so it is attacker-reachable in
        # exactly the way the key is. cost = 0 always passes `tokens >= 0`
        # and admits for ever. cost < 0 both admits AND refunds, because the
        # min() against capacity happens before the subtraction and never
        # after it: one call with cost = -1000 on a drained bucket leaves
        # 1000 tokens in a bucket whose capacity is 3.
        if not (cost > 0):
            raise ValueError("cost must be positive: 0 admits for ever and "
                             "a negative cost refunds the bucket past capacity")
        if math.isinf(cost):
            raise ValueError("cost must be finite")
        with self.lock:                        # ONE thread inside the
            return self._spend(cost)           # read-modify-write below

    def _spend(self, cost: float):
        """The read-modify-write itself. The caller holds self.lock."""
        now = self.clock()
        self.tokens = min(self.capacity,
                          self.tokens + (now - self.updated) * self.refill)
        self.updated = now
        if self.tokens >= cost:
            self.tokens -= cost
            return True, 0.0
        return False, (cost - self.tokens) / self.refill

    def ttl_s(self) -> float:
        """Correct Redis TTL for this key.

        After capacity/refill seconds an untouched bucket is full, so its
        stored state is indistinguishable from a fresh one and evicting it
        is free. At C=100, r=100/60 this is 60 s.
        """
        return self.capacity / self.refill

Four things in that listing are guards, not decoration: the lock, the two constructor checks, and the cost check. Each was a live defect before it became a guard.

An assertion that still passes when you delete its guard is testing nothing. The block below exercises each guard directly: delete the corresponding line from the class above and one of these four assertions fails. Numbered comments map each assertion to its guard.

# --- the guards, exercised. Each assertion fails if its guard is removed. ---

# 1. The limiter still limits when nothing is wrong.
tb = TokenBucket(3, 1.0, clock=lambda: 0.0)
assert [tb.allow()[0] for _ in range(4)] == [True, True, True, False]

# 2. NaN and infinity are rejected, in BOTH parameters. `nan <= 0` is False,
#    which is why the guard is written `not (x > 0)`.
for bad in (float("nan"), float("inf"), 0.0, -1.0):
    for args in ((100, bad), (bad, 1.667)):
        try:
            TokenBucket(*args)
        except ValueError:
            pass
        else:
            raise AssertionError(f"TokenBucket{args} was accepted")

# 3. cost must be positive and finite, and a rejected cost must not have
#    moved the bucket on its way out.
tb = TokenBucket(3, 1.0, clock=lambda: 0.0)
for bad in (0.0, -1000.0, float("nan"), float("inf")):
    try:
        tb.allow(bad)
    except ValueError:
        pass
    else:
        raise AssertionError(f"cost={bad} was accepted")
assert tb.tokens == 3.0            # nothing admitted, nothing refunded

# 4. The lock. 16 threads against a capacity of 500 admit exactly 500.
#    The switch interval is lowered so the race, which is real but rare at
#    the default 5 ms, shows up in milliseconds instead of hours.
_switch = sys.getswitchinterval()
sys.setswitchinterval(1e-6)
try:
    def _race(threads=16, calls=1500, capacity=500):
        bucket = TokenBucket(capacity, 1e-9, clock=lambda: 0.0)
        granted = [0] * threads

        def worker(i):
            n = 0
            for _ in range(calls):
                if bucket.allow()[0]:
                    n += 1
            granted[i] = n

        ws = [threading.Thread(target=worker, args=(i,)) for i in range(threads)]
        for w in ws:
            w.start()
        for w in ws:
            w.join()
        return sum(granted)

    for _ in range(2):
        got = _race()
        assert got == 500, f"{got} admitted against a capacity of 500"
finally:
    sys.setswitchinterval(_switch)

Assumptions, and what breaks when they fail. Three, and the first and third are the ones that force a different algorithm rather than a different constant.

First: the thing behind the limiter can absorb C requests arriving simultaneously. This is load-bearing. If it is false you have chosen the wrong algorithm, not the wrong constant, because permitting that clump is the entire point of the bucket. Shrinking C to make it safe means giving up the only feature you picked this algorithm for.

Second: the clock moves forward, at the right speed. The refill is (now - last) * r, so a clock that jumps backwards makes now - last negative and effectively hands out negative tokens; a clock that jumps forwards refills the bucket for free. This one is mild, because there is a real fix: use a monotonic clock, one that only counts upward from an arbitrary start and is immune to time-of-day adjustments. That is what time.monotonic in the code above is.

Third: the read-modify-write is atomic — nothing can slip between reading the token count and writing it back. This is load-bearing, and it has to be enforced twice, by two different mechanisms:

• Inside one process, by a lock, as the code above does. Ship this class into a threaded server without the lock and it admits two to three times its capacity — the measured range in the docstring is 570 to 1,767 admitted against a capacity of 500.
• Across the twenty gateways sharing one bucket, by moving the whole decision into the store, which is the subject of Where the counter lives and the race that makes incr expire wrong.

Neither fix covers the other’s case. A lock does nothing across machines, because there is no shared object to lock; a server-side script does nothing about two threads racing inside one gateway’s own in-memory fallback bucket.

Where it is wrong: anywhere the downstream cannot absorb the burst. A 100-token bucket in front of a database that handles 20 concurrent queries hands that database 100 queries at once, and the limiter has caused the outage it was installed to prevent.

6.2 Leaking bucket

The leaking bucket is the algorithm to reach for when the downstream needs a steady stream rather than a bounded total, and it is the only one here that delays requests instead of rejecting them.

Mechanism. Picture a bucket with a hole in the bottom. Requests pour in at whatever rate they arrive and drain out at a constant rate r. If the bucket is already full, the new request spills over the rim and is rejected.

Concretely, requests enter a FIFO queue — first in, first out, so requests are served in arrival order — of capacity q, and leave at the fixed rate r.

The output rate is exactly r, always. No other algorithm here gives you that. Every other algorithm bounds a total; this one bounds the shape.

State. In the queueing form the state is q actual requests, not a counter. Price it at 200 bytes for a stub of each request, with q = 50:

per key            50 x 200 = 10,000 bytes
200,000 keys   200,000 x 10,000 = 2,000,000,000 bytes = 2 GB

You have also acquired a durability question you never wanted. Those queued requests are real work that a customer is waiting on, and they vanish if the queue’s machine restarts.

Burst, derived. The number admitted over an interval of length T is r x T + q — the same shape as the token bucket, with the queue depth q playing the role of the capacity C. At q = L = 100 that is again 100 + 100 = 200, the same 2x ceiling.

The difference is what happens to those 200 requests. They are not served in a burst; they leave at exactly 1.667 per second no matter how fast they arrived. So the cost does not land on the downstream service — it lands on the caller, as latency. Here that is fatal:

queue is full, q = 100 requests waiting
drain rate                              r = 1.667 req/s
wait for the request at the back    100 / 1.667 = 60 seconds

60 seconds of queueing delay for a synchronous HTTP request whose client times out at 30. Shrinking the queue does not save it: even a modest q = 10 gives 10 / 1.667 = 6 seconds of added latency on a request that should take milliseconds.

What happens next is worse than a slow request. The request occupies a connection for the whole wait, the client times out anyway and retries, and you have converted a clean rejection into doubled load plus a held connection.

Assumptions, and what breaks when they fail. The load-bearing one is that the caller is willing to wait q/r seconds. For a synchronous HTTP request that is false, and no tuning of q or r rescues it; you have chosen the wrong algorithm.

Two milder assumptions: that the queue survives a restart, since a crash silently drops work you already accepted, and that rejecting on overflow is acceptable, which reintroduces the “what do I tell the client” problem the queue was supposed to remove.

Where it is right: outbound traffic to a third party with a hard contractual rate cap, such as a payments API at 10 req/s, where smoothness is required and delay is acceptable because the work is already asynchronous, meaning nobody is waiting on a connection for the answer.

The counter form worth naming: the generic cell rate algorithm (GCRA), also called the virtual scheduling algorithm, is the leaking bucket with the queue replaced by a single stored number, the earliest time at which the next request would be “on schedule”. It gives the same smoothing with 16 bytes of state, and it rejects early arrivals instead of queueing them.

6.3 Fixed window — and the boundary problem with real numbers

The fixed window is the cheapest algorithm here and the one with the worst worst case, derived below as a number.

Mechanism. Chop time into fixed, clock-aligned windows. Aligned means every minute starts exactly at :00 on the wall clock — the same instant for every client and every machine, with no per-client offset.

Keep one counter per (key, window index) pair. On each request: increment that counter, compare the result against the limit L, and let the key delete itself when its TTL passes. The increment is Redis’s INCR command, which adds one and returns the new value in a single operation.

State. One integer. This is the cheapest thing on the list, and it costs one store operation per request — no script, no read-then-write.

Burst, derived. The derivation below uses a small limit, L = 5 per minute, because the effect is easiest to see at that scale. The same shape holds at any limit.

The trace has two lines. The timestamps are 400 milliseconds apart, and a window boundary falls between them.

12:00:59.700   requests 1-5    counter[12:00] -> 5   all admitted
12:01:00.100   requests 6-10   counter[12:01] -> 5   all admitted

requests inside the 400 ms span [12:00:59.700, 12:01:00.100]
5 + 5 = 10

The first five land at the very end of the 12:00 window and fill its counter to exactly 5, the limit. Four hundred milliseconds later the clock ticks past :00, which means a different key is now being incremented — counter[12:01], which starts at zero. Five more requests fill that one to exactly 5, the limit.

Ten requests in 400 milliseconds against a limit of five per minute — and neither window ever exceeded its limit. Both counters are individually correct. The algorithm has no bug in it. It is simply answering a question (“how many in this aligned minute?”) that is not the question you asked (“how many in any minute?”).

The count understates how bad this is, so convert it to a rate:

observed rate      10 requests / 0.4 s  =  25 req/s
nominal rate        5 requests / 60 s   =  0.0833 req/s
ratio                   25 / 0.0833     =  300x

300x the nominal rate, sustained for 400 ms.

And the 400 ms is arbitrary — it is just how fast this hypothetical client sent them. Send the same ten inside 4 ms and the observed rate is 10 / 0.004 = 2,500 req/s, which is 2,500 / 0.0833 = 30,000x. Nothing in the algorithm sets a floor on that span.

So state the fixed-window bound in two halves: the over-admission factor in count is exactly 2; in instantaneous rate it is unbounded. The 2x is the count bound; the rate bound is the one that gets skipped. At this chapter’s production limit of 100/min, it means 200 requests in however long the client takes to send them.

There is a second, quieter problem. Aligned windows synchronize every client. Every counter resets at :00, so every blocked client’s natural retry time is the same instant. That is the seed of the retry storm derived in The retry storm derived, planted by the algorithm itself before any client has done anything wrong.

Assumptions, and what breaks when they fail. The load-bearing assumption is that the client does not know where the boundary is, or does not care. Against an adversary who does know, the assumption is false, and the boundary is public: it is the top of the minute, there is nothing to discover. The algorithm then admits 2L back to back on demand, which is why fixed window is the wrong choice for abuse prevention no matter how you tune it.

The milder assumption is that every machine agrees on which window it is in. A gateway whose clock is 400 ms fast files requests into the next window early. Against a 60-second window that is a constant-sized error you can ignore; against a 1-second window it is 40% of the window (The fix one script one round trip prices clock skew properly).

Where it is right: limits that exist to stop a runaway loop rather than to protect capacity — “no more than 10,000 API calls per day per account.” A 2x overshoot on a daily quota is a rounding error; on a per-second capacity limit it is an outage.

6.4 Sliding window log

The sliding window log is the only exact algorithm here: it never admits more than L requests in any W-second stretch, whenever that stretch starts. You buy that exactness with memory.

Mechanism. Instead of a count, keep the actual timestamp of every admitted request. Store them in a sorted set: a Redis structure that holds members ordered by a numeric score, so a whole range of scores can be trimmed or counted in one command. Here the score is the timestamp.

Each request runs four steps:

1. delete every entry older than now - W — those requests have aged out of the trailing window;
2. count what is left;
3. admit if that count is under L;
4. if admitted, append the current timestamp.

Step 1 is what makes the window sliding rather than aligned: the set always describes exactly the last W seconds, measured backwards from this instant, not from :00.

State. One 8-byte timestamp per admitted request, which costs about 70 bytes per sorted-set member once Redis’s per-member bookkeeping is included. From Memory the number that separates the algorithms: 440 MB for typical traffic and 1.4 GB with every client pinned at its limit, against 40 MB for the sliding window counter and 26 MB for the token bucket.

Burst. Zero error, at any alignment. The number of requests between now - W and now is computed directly, not estimated, so no W-length interval anywhere on the timeline can ever contain more than L requests. There is no boundary to exploit because there is no boundary.

This is the only algorithm on the list with that property, and it is what the 36x memory over the default algorithm buys (55x over the token bucket).

It also gives the only exact Retry-After value. Take the oldest timestamp still inside the window, add W, subtract now: that is the precise instant at which one slot frees up. Every other algorithm rounds up and tells the client to wait longer than it needs to.

Assumptions, and what breaks when they fail. The load-bearing assumption is that only admitted requests are recorded. It is load-bearing in a security sense rather than an accuracy one: log rejected requests too and the attacker, not you, sets your memory usage — 210 MB from one client in one window, from the arithmetic in Memory the number that separates the algorithms.

Two milder assumptions: that the limit is small enough for a per-request record to be affordable, and that the trim stays cheap. Trimming a sorted set holding tens of thousands of entries inside a script blocks the entire Redis instance while it runs, which is how a rate limiter takes down the service it protects.

Where it is right: small, hard limits. Five password resets per hour costs one key’s worth of overhead plus five timestamps — the same n x 70 + 100 formula from Memory the number that separates the algorithms:

5 x 70 + 100 = 450 bytes per key

At 450 bytes the memory argument against the log disappears. And Sliding window counter and exactly how wrong it is shows that the cheap approximation is at its worst precisely at limits that small, so the two arguments point the same way.

6.5 Sliding window counter — and exactly how wrong it is

The sliding window counter is the algorithm most production limiters run: it approximates the exact answer of the log using two integers instead of a list of timestamps. How large the approximation error can be determines where you can use it.

Mechanism. Keep two counters: c for the current fixed window, and p for the one immediately before it. Use them to estimate how many requests fall in the trailing window — the last W seconds counted backwards from right now, rather than a clock-aligned block.

The trailing window always straddles the boundary. Part of it is the current fixed window (all of c is inside), and part of it is the tail end of the previous fixed window (only some of p is inside).

How much of p? The estimator does not know, so it assumes the previous window’s requests were spread evenly across it and credits a proportional slice:

est = p x (1 - f) + c        where f = fraction of the current window elapsed

If f = 0.25, a quarter of the current window has elapsed, so the trailing window reaches back over the last three quarters of the previous one, and the estimator credits 1 - 0.25 = 0.75 of p.

State. Two integers — but in two Redis keys, because the window index is part of the key name. That is about 200 bytes per client, not 130 (Memory the number that separates the algorithms). Memory and work per request are both constant no matter how much traffic arrives, and the whole decision fits in one script.

Work through one decision. Suppose the clock is 15 seconds into the current minute, the previous minute saw p = 90 requests, and the current minute has seen c = 40 so far. The limit is L = 100.

elapsed fraction            f = 15 / 60 = 0.25
previous window credited    1 - f       = 0.75
estimate               90 x 0.75 + 40   = 67.5 + 40 = 107.5

The estimate of 107.5 exceeds the limit of 100, so the request is rejected — even though the current window has used only 40 of its 100.

That is the algorithm working exactly as designed. It is refusing to let the client escape the previous minute’s traffic just because a clock boundary went past, which is the precise failure of the fixed window in Fixed window and the boundary problem with real numbers.

Bounding the error

The estimator makes exactly one assumption: that requests were spread uniformly within the previous window. Everything else about it is exact arithmetic.

The true trailing count is p_in + c, where p_in is how many of the previous window’s requests genuinely fall inside the trailing window — that is, how many landed in its final (1 - f) fraction. The estimator uses p x (1 - f) in place of the true p_in. All of the error lives in that one substitution.

To isolate it, hold everything constant — p = 100, L = 100, f = 0.5, so the estimator always credits 100 x 0.5 = 50 — and vary only the shape of the previous window’s traffic. The middle two columns are what to compare:

The error is p(1 - f) - p_in. Since p_in can be anything from 0 to p, substituting the two extremes gives the two-sided bound:

p_in = 0   ->  error = p x (1 - f)     the estimator is too HIGH by this
p_in = p   ->  error = p(1-f) - p
                     = -p x f          the estimator is too LOW by this

over-admission at most      p x f          maximized as f -> 1
under-admission at most     p x (1 - f)    maximized as f -> 0

At p = L and f approaching 1, the worst-case trailing-window total is c + p_in = L + L = 200, the same 2L worst case as fixed window.

What is different is how hard that worst case is to reach. It needs two things at once: the previous window has to be a spike at its very end, and the current window’s requests have to be paced against a budget that only grows at p/W = 1.667 per second as f advances. You cannot dump them in a millisecond the way you can against a fixed window.

So the count error survives, but the instantaneous 300x rate blowup of Fixed window and the boundary problem with real numbers does not. That distinction is why this algorithm is the default and the fixed window is not.

The statistical answer, which is the one worth having ready

The 2L bound above is the adversarial worst case. Real traffic is not adversarial, and the typical error is much smaller, small enough to quote as a percentage.

Suppose requests inside the previous window arrive with no internal pattern. Formally that is a Poisson process: arrivals are independent, and equally likely at any instant. It also holds for any process where the order of arrivals carries no information, which statisticians call exchangeable.

Under that assumption each of the p requests independently lands in the trailing portion with probability 1 - f. That is p independent coin flips with the same bias, which is the definition of a binomial distribution, written Binomial(p, 1 - f). So p_in ~ Binomial(p, 1 - f).

A binomial count with n trials at probability q has mean n x q. Here that is:

E[p_in] = p x (1 - f)

which is exactly what the estimator computes. The estimator is therefore unbiased: averaged over many windows it is neither systematically high nor systematically low.

Unbiased says nothing about how far off any single decision is. That spread is the standard deviation — roughly, the typical distance between the estimate and the truth. For a binomial count it is sqrt(n q (1-q)), which here is sqrt(p (1-f) f), or just sqrt(p f (1-f)).

That expression is largest when f = 0.5, halfway through the window, because f(1-f) peaks there. Substitute p = 100 and f = 0.5:

variance      p x f x (1-f)  =  100 x 0.5 x 0.5  =  25
std dev            sqrt(25)  =  5 requests

A typical error of five requests against a limit of 100 — 5%.

Now generalize. Set p = L (a client using its full budget) and f = 0.5 (the worst point), and the peak standard deviation simplifies:

sqrt(L x 0.5 x 0.5) = sqrt(L x 0.25) = sqrt(L) / 2

Divide that by L to get the error relative to the limit:

(sqrt(L) / 2) / L  =  1 / (2 sqrt(L))

The sqrt(L) in the denominator is the whole story: the relative error shrinks as the limit grows. The table substitutes four limits into sqrt(L)/2 and 1/(2 sqrt(L)):

The approximation is excellent where limits are large and terrible where they are small, and small limits are exactly the abuse-prevention case from Framing what a rate limiter is actually for where you needed it to be exact.

The design consequence is that the algorithm choice is per rule, not per system: sliding window counter for the 100/min fairness tier, sliding window log for the 5/hour password reset. One limiter, two algorithms, chosen by the size of the limit.

Assumptions, and what breaks when they fail. Three, and only one is load-bearing.

Uniformity within the previous window. Not load-bearing. The table above prices its failure exactly: a spike at the end of the previous window means up to p x f too many admitted, a spike at the start means up to p x (1 - f) wrongly rejected. That is a bounded, quotable error, not a wrong-algorithm error — which is why the counter is a fine default despite being wrong.

The limit is large enough for 1/(2 sqrt(L)) to be small. Load-bearing. At L = 5 the typical error is 22% of the limit, and no amount of tuning fixes it, because the error comes from counting statistics rather than from any parameter you control. When this fails you must switch to the log.

Every gateway agrees on where the window boundaries are. This one shapes the code below: it is why SlidingWindowCounter deliberately takes wall-clock time, even though Token bucket told you a monotonic clock is safer. Boundaries must be identical across twenty machines, and a per-process monotonic clock starts from an arbitrary point on each of them, so it cannot produce a shared boundary.

The implementation. Wall time has a price, and the class pays it in _roll. Wall clocks move backwards — NTP corrections step them — and a backwards step past a window boundary would make _roll see an unexpected index, zero both counters, and hand the client a completely fresh budget. That is the same 2L failure this algorithm exists to remove, reintroduced by the clock instead of the client.

The one line that prevents it is now = self.high = max(now, self.high), which clamps the clock to the highest value it has ever seen. Read that line, and read _roll’s handling of idx == self.idx + 1 — a gap of two or more windows means the previous window has aged out entirely and must not be credited.

class SlidingWindowCounter:
    """Two counters per key. Memory is O(1); relative error is O(1/sqrt(limit)).

    The clock is wall time on purpose. Window boundaries must be identical on
    every gateway, so a monotonic per-process clock is wrong here even though
    it is right inside TokenBucket.

    THE PRICE OF WALL TIME IS THAT WALL TIME MOVES BACKWARDS. An NTP
    correction that steps the clock back one window makes `_roll` see an
    index it did not expect, zero BOTH counters, and hand the client a fresh
    limit: 200 admitted inside one real minute at L = 100. That is exactly
    the 2L boundary failure this algorithm exists to remove, reintroduced by
    the clock rather than by the client -- and section 6.1 fixes backwards
    clocks for the token bucket by using a monotonic one, which is the fix
    this class cannot take.

    So `_roll` refuses to go backwards: it clamps `now` to the highest value
    it has ever seen. A backwards step then freezes the window instead of
    resetting it, and the client waits out the skew rather than being handed
    a second budget -- the safe direction, and the cost is a client that
    stays limited for the length of the correction. That defence is
    per-process only. It cannot stop a gateway whose clock is merely SLOW
    from filing requests under the wrong window index in the first place,
    and no per-process fix can, because the index is part of the Redis key
    name. The fix for that is to read the clock inside the store instead of
    on twenty gateways -- `redis.call('TIME')`, section 7.
    """

    def __init__(self, limit: int, window_s: float, clock=time.time):
        self.limit = int(limit)
        self.window = float(window_s)
        self.clock = clock
        self.idx = -1
        self.prev = 0
        self.curr = 0
        self.high = float("-inf")

    def _roll(self, now: float) -> float:
        """Advance to the window containing `now`; return elapsed fraction."""
        now = self.high = max(now, self.high)   # never backwards: a step back
        idx = int(now // self.window)           # would zero BOTH counters
        if idx != self.idx:
            # Only an immediately-preceding window contributes. A gap of two
            # or more windows means the previous one has fully aged out.
            self.prev = self.curr if idx == self.idx + 1 else 0
            self.curr = 0
            self.idx = idx
        return (now % self.window) / self.window

    def estimate(self, f: float) -> float:
        return self.prev * (1.0 - f) + self.curr

    def allow(self):
        """Return (allowed, seconds_until_allowed)."""
        now = self.clock()
        f = self._roll(now)
        if self.estimate(f) + 1 > self.limit:
            return False, self._retry_after(f)
        self.curr += 1
        return True, 0.0

    def _retry_after(self, f: float) -> float:
        """Smallest wait after which the estimate admits one more request.

        est(f) = prev*(1-f) + curr decreases linearly in f, so solve
        prev*(1-f') + curr <= limit - 1 for f'. With prev == 0 the estimate
        does not decay at all and the only relief is the window rolling over.
        """
        rest = self.window * (1.0 - f)
        head = self.limit - 1 - self.curr
        if self.prev <= 0 or head < 0:
            return rest
        need_f = 1.0 - head / self.prev
        return min(rest, max(0.0, (need_f - f) * self.window))

The backwards-clock price is worth measuring rather than asserting, because the number it produces is the same 2L the algorithm was chosen to avoid.

The block below runs 300 requests at 10 ms intervals — three seconds of traffic at L = 100 — then steps the clock back two minutes and runs 300 more. Watch the assertion after the step: the total is still 100, not 200. The third assertion checks the opposite failure, that the clamp does not freeze the limiter permanently.

# One real minute of traffic at L = 100, with NTP stepping the clock back
# two minutes halfway through. Without the clamp in _roll this admits 200.
_t = [1000.0]
swc = SlidingWindowCounter(100, 60.0, clock=lambda: _t[0])

admitted = 0
for _ in range(300):
    if swc.allow()[0]:
        admitted += 1
    _t[0] += 0.01
assert admitted == 100                       # the limit, as advertised

_t[0] -= 120.0                               # the NTP correction
for _ in range(300):
    if swc.allow()[0]:
        admitted += 1
    _t[0] += 0.01
assert admitted == 100, f"{admitted} admitted in one real minute at L = 100"

# And the clamp must not freeze the limiter for ever: two clear windows
# later, the budget is genuinely back.
_t[0] = 1000.0 + 240.0
assert swc.allow()[0] is True

6.6 Side by side

Every number derived above collects into one table, which turns into the four questions that pick an algorithm.

Symbols, all defined above: C is the token bucket’s capacity, q the leaking bucket’s queue depth, L the limit, W the window, and r = L/W the sustained rate.

Two rows decide most arguments. “Worst count in a window” is the number usually quoted; “worst instantaneous rate” is the number that separates fixed window from everything else, and it is the one that gets skipped.

The decision tree below turns that table into a procedure. Each diamond is one question; follow the answers down and the leaf you land on is the algorithm. The questions are ordered by how many options each one eliminates, so the first is the most decisive.

flowchart TD
    Q1{"Must the downstream see<br/>a perfectly smooth rate?"} -->|"yes"| LBK["Leaking bucket / GCRA<br/>accept the queueing delay<br/>outbound calls only"]
    Q1 -->|"no"| Q2{"Is a 2x overshoot at a<br/>boundary acceptable?"}
    Q2 -->|"yes · daily quotas"| FW["Fixed window<br/>8 B, one INCR"]
    Q2 -->|"no"| Q3{"Is the limit small,<br/>under about 20?"}
    Q3 -->|"yes · abuse limits"| SWL["Sliding window log<br/>exact · 70 B per request"]
    Q3 -->|"no"| Q4{"Do you want a controlled<br/>burst allowance?"}
    Q4 -->|"yes"| TB["Token bucket<br/>burst = capacity C"]
    Q4 -->|"no"| SWC["Sliding window counter<br/>16 B · 5% error at L = 100"]

Here is each question and why it sits where it does.

1. Must the downstream see a perfectly smooth rate? Only the leaking bucket and its counter form GCRA deliver that, and only by making the caller wait. So this branch is for outbound calls, where nobody is holding a connection open waiting for an answer. It goes first because a “yes” eliminates four of the five options in one step.

2. Is a 2x overshoot at a boundary acceptable? If yes — the case for daily and monthly quotas — the fixed window’s 8 bytes and single INCR are unbeatable and nothing else needs considering.

3. Is the limit small, under about 20? Below L = 20 the counter’s relative error 1/(2 sqrt(L)) passes 10% (Sliding window counter and exactly how wrong it is) and only the log is trustworthy. At those limits the log costs almost nothing: 450 bytes at L = 5.

4. Do you want a controlled burst allowance? If a customer is supposed to be able to save up unused allowance and spend it in one go, the token bucket’s capacity C is the only knob in this chapter that expresses that.

If none of those apply, the sliding window counter wins on cost.

Default: sliding window counter for tiered quotas, token bucket where a deliberate burst allowance is a product feature, sliding window log for small hard limits. One system, three rules, chosen per route.

6.7 What each algorithm assumes, and what breaks when it does not hold

Every algorithm above is correct only in a world that behaves a certain way. The useful distinction is which assumption, when violated, means you picked the wrong algorithm rather than the wrong constant.

That is the “Load-bearing?” column:

• Load-bearing means the assumption cannot be tuned around. Its failure forces a different algorithm.
• Not load-bearing means its failure costs you a parameter change, or a bounded error you can state as a number.

A bolded algorithm name in the first column marks a load-bearing row. Unbolded rows are the milder assumptions for the same algorithm.

Four assumptions cut across every algorithm, which is why the last four rows say “all of them, shared”.

Clock skew — the disagreement between two machines’ clocks. Gateways kept in step by NTP (the Network Time Protocol, which disciplines a machine’s clock against reference servers) sit within roughly +/- 50 ms of each other. Against a 60-second window that is negligible; against a 1-second window it is a 5% error; against a fixed-window boundary it is the entire effect. The clean fix is to read the time inside the store rather than on the gateway (The fix one script one round trip).

Burst tolerance — how many requests may arrive at once. This is not a property of the algorithm alone. It is a contract with whatever sits behind the limiter, and getting it wrong is always a wrong-algorithm error rather than a wrong-constant one.

Key distribution — how traffic spreads across keys. Every memory and throughput number in Back of the envelope assumes it is roughly even. Real traffic is not: one partner integration can be a large fraction of the fleet’s requests, and because that partner is one key, the whole load lands on a single shard (Bottlenecks and scaling).

Node churn — machines joining and leaving, in the gateway fleet or in the store. Churn changes how many independent counters exist, and that count is the quantity setting the over-admission bound for every design that does not share one counter (Distributed rate limiting and what synchronization costs).

7. Where the counter lives, and the race that makes INCR + EXPIRE wrong

The counter has to live somewhere, a naive implementation corrupts it in three ways, and a single change fixes all three. The word atomic runs through all of it: an operation is atomic when no other operation can observe or interleave with its intermediate state; it either has happened completely or not at all, from everyone else’s point of view.

Local versus shared

The first question is whether each gateway can keep its own copy of the count in its own memory, or whether all twenty must share one. The row that settles it is the fourth.

Local counters over-admit because each of the N gateways enforces the full limit L on its own, with no idea the other nineteen exist:

N x L = 20 x 100 = 2,000 requests per minute against a limit of 100

A 20x over-admission is not approximately right; it is not a rate limiter. So the counter is shared. Everything below is about making that one shared round trip both correct and rare.

The race

A race condition is a bug where the outcome depends on the relative timing of operations that were supposed to be independent.

There are three races here, in increasing order of subtlety. Two of them come from splitting one logical decision across two commands, and the third comes from splitting it across two machines.

Race 1: the lost EXPIRE. INCR increments the counter; EXPIRE attaches a time-to-live to the key. They are two separate commands, and two commands are not atomic: anything can happen between them, including the calling process dying.

The trace below is that gap. At t1 the gateway that was going to set the TTL never does.

t0   gateway A    INCR rl:{c1}:api        -> 1
t1   gateway A    process dies / packet lost before EXPIRE
t2   gateway B    INCR rl:{c1}:api        -> 2
...
     the key has no TTL. It is permanent.

A key with no TTL never expires. Two consequences follow.

Permanent lockout. The counter never resets, so once it crosses 100 that client is rejected forever. There is no alert for this, only a support ticket days later from your largest customer.

Unbounded memory. Price it. Suppose 0.1% of window-openings lose their EXPIRE, across 1,000,000 daily clients, each of which could open a window in any of the 1,440 minutes in a day:

window-openings per day     1,000,000 x 1,440 = 1,440,000,000
of which 0.1% leak     1,440,000,000 x 0.001 = 1,440,000 immortal keys
at ~100 bytes each         1,440,000 x 100   = 144,000,000 bytes = 144 MB/day
over a month                     144 x 30    = 4,320 MB = 4.3 GB

That 4.3 GB keeps growing until Redis’s eviction policy starts deleting live counters to make room, at which point the limiter silently stops limiting. Failure modes has that failure as its own row, because it produces no error signal.

Race 2: the window that never closes. This one is subtler and more common than race 1.

Suppose every request does INCR then EXPIRE key 60. The TTL is now refreshed on every request, so for a client that keeps sending, the window never closes.

Work the example: a client reaches 99, then sends one request every 59 seconds. Each of those requests pushes the expiry out another 60 seconds, so the counter sits at 99 forever. The client is effectively limited to 1 request per minute instead of 100 — the limiter’s error is 100x, in the direction that generates angry customers.

EXPIRE key 60 NX (Redis 7.0 and later) fixes exactly this. The NX flag means “set the expiry only if the key does not already have one”, and it does so in the same command.

The common alternative is “set the TTL only when INCR returns 1.” That gets the semantics right and the atomicity wrong. It is two commands again, so it reintroduces race 1 verbatim: the gateway that saw the 1 can die before its EXPIRE lands, and the key is immortal and the client permanently locked out. One command, or a script. Never two.

Race 3: read-modify-write across two machines. This one applies to every stateful algorithm, not just plain counters. The token bucket and both sliding windows are read-modify-write: they fetch the current state, compute a new value from it, and store the result.

Any gap between the read and the write is a place where a second gateway can read the same, now-stale value. The sequence diagram shows it:

sequenceDiagram
    participant A as Gateway A
    participant B as Gateway B
    participant R as Redis
    A->>R: HGET bucket tokens
    R-->>A: 5.0
    B->>R: HGET bucket tokens
    R-->>B: 5.0
    Note over A,B: both compute 5.0 - 1 = 4.0
    A->>R: HSET bucket tokens 4.0
    B->>R: HSET bucket tokens 4.0
    Note over R: two tokens spent, one recorded

Both gateways read 5.0. Both compute 4.0. Both write 4.0. Two tokens were spent and one was recorded, so the bucket now over-admits by one — and it does so once per race, which at 100,000 req/s is often.

Redis does offer a fix: WATCH/MULTI/EXEC, an optimistic concurrency scheme. Optimistic means it assumes conflicts are rare — it proceeds without locking, detects afterwards whether anyone else touched the key, and retries the whole operation if so.

It is correct, and it is still the wrong tool here. Retries happen where contention is highest, and contention is highest on the busiest key. Your largest client would trigger a retry storm inside Redis, on the one key you least wanted to slow down.

The fix: one script, one round trip

The fix for all three races is the same: send the entire decision to Redis as a single Lua script, a short program, written in the Lua language, that Redis stores and executes server-side.

Why that fixes all three at once: Redis runs commands one at a time on a single thread (Store throughput how many shards), and a script runs to completion before the next command is served. A script is therefore atomic by construction. There is no gap for a second gateway to read into, and there is no way to complete the INCR without the EXPIRE, because both are inside the same indivisible unit.

It buys two other things. It collapses two or three round trips into one, which halves the latency contribution. And it returns the allow/deny decision and the Retry-After value together in one reply, so the caller learns when to come back without a second call.

The sliding window counter script. This is Sliding window counter and exactly how wrong it is’s estimator, moved server-side. Three things to look at: the two KEYS at the top and why there are two, the est line (the formula p x (1 - f) + c verbatim), and the PEXPIRE ... window * 2 at the bottom.

-- Sliding window counter. Atomic, one round trip.
-- KEYS[1] = rl:{client}:route:<idx>      current window counter
-- KEYS[2] = rl:{client}:route:<idx-1>    previous window counter
-- Both carry the {client} hash tag, so Redis Cluster routes them to one slot.
-- ARGV[1] = limit   ARGV[2] = window_ms   ARGV[3] = elapsed_ms in this window
-- `elapsed` comes from the gateway here, and it has to: the window index is
-- part of the KEY NAMES, which Redis Cluster requires the client to compute
-- so it can route the call. Reading TIME server-side would give an elapsed
-- fraction measured against a different window than the one being counted,
-- which is worse than the skew it removes. The token-bucket script below has
-- no index in its key and therefore does read TIME. Gateway clock skew is
-- priced against the window length in the notes after these two scripts.
local limit   = tonumber(ARGV[1])
local window  = tonumber(ARGV[2])
local elapsed = tonumber(ARGV[3])
local f       = elapsed / window

local cur  = tonumber(redis.call('GET', KEYS[1]) or '0')
local prev = tonumber(redis.call('GET', KEYS[2]) or '0')
local est  = prev * (1 - f) + cur

if est + 1 > limit then
  local rest = window - elapsed
  if prev > 0 then
    local head = limit - 1 - cur
    if head >= 0 then
      local need = (1 - head / prev) * window
      rest = math.min(rest, math.max(0, need - elapsed))
    end
  end
  return { 0, math.ceil(rest), limit, 0 }
end

redis.call('INCR', KEYS[1])
redis.call('PEXPIRE', KEYS[1], window * 2)   -- 2x so the NEXT window can read it
return { 1, 0, limit, limit - math.ceil(est) - 1 }

Three lines carry the lesson.

local est = prev * (1 - f) + cur is the estimator from Sliding window counter and exactly how wrong it is, unchanged. Everything above it is just fetching p and c, defaulting a missing key to '0' so a first-ever request works.

The if est + 1 > limit test asks whether admitting this request would exceed the limit — the + 1 is the request being decided, which is why a client at exactly the limit is rejected rather than admitted.

PEXPIRE KEYS[1], window * 2 sets a TTL of two windows, not one, because when the next window becomes current, this key becomes its KEYS[2], the previous-window counter it reads. Expire it after one window and the algorithm loses p and degrades to a fixed window at exactly the boundary it exists to handle.

The token bucket script. Same structure, one key instead of two. Note the redis.call('TIME') at the top, and the comment explaining why this script may read the clock server-side while the one above may not.

-- Token bucket. Atomic, one round trip.
-- KEYS[1] = rl:{client}:route
-- ARGV[1] = capacity  ARGV[2] = refill/s  ARGV[3] = cost
local capacity = tonumber(ARGV[1])
local refill   = tonumber(ARGV[2])
local cost     = tonumber(ARGV[3])

-- The clock is the STORE's, not the caller's. There is one Redis instance
-- and twenty gateways, so taking `now` from the gateway means twenty clocks
-- writing one timestamp: the slowest-clocked gateway drags `ts` backwards
-- for everyone sharing this key, the next refill computes a negative
-- elapsed time, and the bucket is zeroed for every other caller. This key
-- has no window index in its name, so unlike the sliding-window script
-- below it is free to read the time server-side. TIME returns
-- {seconds, microseconds}.
local t   = redis.call('TIME')
local now = tonumber(t[1]) + tonumber(t[2]) / 1000000

-- Validate before touching state. `cost` is a public API parameter and it
-- gets the same `not (x > 0)` treatment as the Python: cost = 0 admits for
-- ever, and cost < 0 both admits AND refunds, because the math.min against
-- capacity below runs before the subtraction and never after it.
if not (capacity > 0) or not (refill > 0) or not (cost > 0) then
  return redis.error_reply('capacity, refill and cost must all be positive')
end

local st     = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(st[1]) or capacity
local ts     = tonumber(st[2]) or now

tokens = math.min(capacity, tokens + (now - ts) * refill)
local ok = tokens >= cost
if ok then tokens = tokens - cost end

redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
-- Untouched for capacity/refill seconds, the bucket is full again, so the
-- stored state carries no information past that point.
redis.call('EXPIRE', KEYS[1], math.ceil(capacity / refill) + 1)

if ok then return { 1, 0 } end
return { 0, math.ceil((cost - tokens) / refill) }

Three implementation notes.

EVALSHA, not EVAL. EVAL sends the whole script text with every call. EVALSHA sends only a short fingerprint, a SHA-1 hash: a fixed 40-character digest identifying a script Redis has already cached.

The difference is bandwidth. Sending the script body adds roughly 800 bytes to a 200-byte request, a 5x increase in limiter traffic for nothing gained. Cache the fingerprint on the gateway, and fall back to EVAL when Redis replies NOSCRIPT, its way of saying it has never seen that fingerprint, which happens after a restart.

Pass time in, or read it in the script. Calling redis.call('TIME') inside the script takes the time from the store instead of the gateway, which removes gateway clock skew entirely: one clock instead of twenty.

It is safe on replicas. Since Redis 5, a primary ships the effects of a script to its replicas rather than re-running the script there, so the primary and the replica cannot diverge even though TIME returns a different value on each machine.

Read it in the script wherever you can — which is why the token-bucket script does. The sliding-window script cannot: Redis Cluster requires the client to compute the key names so it can route the call, and the window index is inside those names. Reading TIME server-side there would give an elapsed fraction measured against a different window than the one being counted, which is worse than the skew it removes.

Client-supplied time is acceptable when the window is large. Twenty gateways disciplined by NTP sit within about +/- 50 ms of each other. Express that as a fraction of the window:

against a 60 s window     50 ms / 60,000 ms = 0.000833 = 0.08%
against a  1 s window     50 ms /  1,000 ms = 0.05     = 5%

Negligible at 60 seconds, a real 5% error at 1 second, and against the fixed-window boundary case of Fixed window and the boundary problem with real numbers it is the entire effect, because there the whole question is which side of a boundary a request falls on.

Scripts must be deterministic and short. Deterministic means the same inputs always produce the same result, with no randomness and no reading of outside state, so a replica replaying the work reaches the same answer.

Short matters because a script blocks the entire Redis instance while it runs, and Redis has one thread. A loop trimming a large sorted set inside a script is how a rate limiter takes down the thing it protects.

The deny cache, and why it is the highest-leverage optimization

A deny cache is a small dictionary held in each gateway’s own memory, mapping a client id to the time until which that client is known to be blocked.

It works because of an asymmetry between the two possible answers. “Allowed” stops being true the instant the next request arrives, so it cannot be cached. “Denied until T” stays true for the rest of the window no matter what happens, so it can.

That asymmetry lines up with load: the client generating the most store traffic is, by definition, the one exceeding its limit, and its answer is the cacheable one.

Price it. Take one abusive client sending 50,000 req/s. Without a cache, every one of those requests is a Redis operation. With a per-node cache, each of the twenty gateways asks Redis once per window, then answers locally for the rest of it:

requests in one 60 s window     50,000 x 60 = 3,000,000
Redis ops without the cache                   3,000,000
Redis ops with the cache
  (20 gateways x 1 probe each)                       20
reduction                  3,000,000 / 20 = 150,000x

150,000x fewer store operations against the worst client on the platform, bought with a dictionary of client_id -> blocked_until.

The safety argument matters as much as the number: the cache holds only denials, so it can never over-admit. The worst it can do is keep rejecting a client for up to one window after they should have been readmitted, an error that is bounded, in the safe direction, and already visible to the client in the Retry-After they were handed.

8. Distributed rate limiting, and what synchronization costs

Twenty machines cannot cheaply agree on one number, and pricing the four ways they might try is what proves it.

The setup is fixed throughout: twenty gateway nodes all enforce a single limit that is supposed to apply to the client as a whole, not to each node separately.

Three of the four options lose on a number you can derive at the whiteboard, and knowing which number, for each, is the point of the section.

A. Divide the limit — L/N per node

The simplest idea: give each of the N nodes a fraction of the limit and let it enforce that fraction alone, with no communication between nodes at all.

per-node limit    L / N = 100 / 20 = 5 requests per minute

This is correct only if a client’s traffic spreads uniformly across the twenty nodes. There are two reasons it does not, and the second is fatal.

Statistically. Take a client sending exactly 100 requests, spread randomly across the twenty nodes by the load balancer. Each request lands on any given node with probability 1/20 = 0.05, independently of the others — which makes the per-node count a binomial again, Binomial(100, 0.05).

Its mean is 100 x 0.05 = 5, matching the per-node limit, which is why the idea looks fine. Its standard deviation is sqrt(n q (1-q)):

variance     100 x 0.05 x 0.95 = 4.75
std dev            sqrt(4.75)  = 2.18 requests

So the per-node count routinely lands two or three above its mean of 5. Summing the binomial tail gives P(count >= 8) = 12.8%: roughly 13% of the time, some node rejects a client that is comfortably under its global limit.

Structurally, and this is the decisive failure. A well-written API client opens one long-lived HTTP/2 connection and sends everything down it. A connection is assigned to one gateway when it is established, and it stays there.

So all of that client’s traffic lands on one node. Its effective limit is 5 per minute instead of 100, a 20x under-admission, inflicted on the best-behaved client shape you have.

B. Central store

The second option is one shared counter that every node reads and writes. This is the architecture of High level architecture.

It is exact — there is one number, and every decision reads it.

It costs one 0.5 ms round trip on every request, which is 0.5 / 5 = 10% of the 5 ms budget from Requirements.

And it makes the store a hard dependency: a component whose failure stops the request path. Failure modes answers that with a fail-open fallback, which is why fail-open is a requirement and not a nicety.

This is the answer. The three alternatives are worse for reasons you can quantify, which is what the rest of this section does.

C. Local counters plus periodic sync

The third option keeps a counter on each node and has the nodes tell each other what they have seen every so often. That is gossip: each node periodically broadcasts its own recent deltas to its peers, rather than routing everything through one authority.

Price both halves of it, because the half that kills the design is not the half people expect.

Bandwidth is cheap. Work down the block — each line uses the one above it:

sync interval                                     100 ms = 0.1 s
fleet requests per interval    100,000 x 0.1   =  10,000 requests
deltas per node                  10,000 / 20   =  500 keys touched
bytes per delta (16 B key + 4 B count)            20 bytes
bytes per broadcast                 500 x 20   =  10,000 bytes
sent to 19 peers                 10,000 x 19   =  190,000 bytes per sync
syncs per second (one per 100 ms)                 10
bandwidth per node              190,000 x 10   =  1,900,000 bytes/s = 1.9 MB/s

Compare that to a 1 Gbps NIC, which carries 125 MB/s: 1.9 / 125 = 1.5%. Cheap enough to build, which is why the correctness bound is the thing to check.

The correctness bound is set by N, not by the sync interval. The worst case: immediately after a sync, every node believes the count is 0. In the interval before the next sync, each of the twenty independently admits up to the full limit L:

N x L = 20 x 100 = 2,000 admitted against a limit of 100

Notice what is not in that expression: the sync interval. Halving it does not improve the bound at all — it only lowers the probability of hitting it, because there is less time for twenty nodes to each fill a budget.

Under steady traffic the error really is tiny. The fleet admits 10,000 requests per interval on stale state, spread over the 200,000 active keys of The starting assumptions:

10,000 / 200,000 = 0.05 extra requests per key per interval

Which is what rejects the design: gossip is accurate under steady traffic and useless against a burst, which is the only thing a rate limiter exists to stop.

D. Key-owner sharding

The fourth option makes the gateway fleet its own counter store, removing Redis from the picture entirely.

Assign each key an owner among the twenty gateways using consistent hashing: a scheme that maps both keys and machines onto the same circular number space, called the hash ring, so each key belongs to the first machine clockwise from it. Its useful property is that adding or removing a machine moves only a small share of keys instead of reshuffling all of them (chapter 05 derives this).

Every gateway then forwards a check to whichever node owns that key.

The good news: it is exact, it costs one internal network hop of about 0.5 ms — the same as option B — and it needs no external system.

The cost arrives elsewhere, in three parts. You now own cluster membership, meaning the twenty nodes have to agree on which of them are alive. You own rebalancing, meaning key ownership has to move when a node joins or leaves. And losing a node loses its counters in the middle of a window.

That is Redis with extra steps, unless you already run a hash ring for another reason.

The arithmetic for how many keys a membership change reshuffles (94% of them going from 16 to 17 nodes under plain mod N, against only 1/(N+1) on a ring) is derived in The baseline mod n and the 94, and priced for a sharded database in Scaling partitioning sharding pooling caching.

What “global” actually means across regions

From Latency what the budget forbids, a cross-region round trip is 30x the latency budget. A genuinely global counter is therefore not something you can buy at 5 ms — at any price, with any technology.

That leaves two honest designs. The interview question is which one you pick, and what a user actually sees when it is wrong.

Pick one and name what a user sees when it is wrong. A globally consistent counter is not an available option.

9. The client contract: 429, Retry-After, and the retry storm

A rejection has to say certain things to be useful, each algorithm computes the “come back later” number differently, and a correct rejection can still destroy your service. The last part is the surprising one: the limiter tells a hundred thousand clients the same thing at the same moment, and they believe it.

The response

A rejection is a machine-readable message, not just a status code. A client that gets only “429” has to guess when to come back, and it will guess wrong.

Below is the whole response. Two families of headers are present, RateLimit-* and X-RateLimit-*, and their Reset fields hold different-looking numbers. That is deliberate, and it is the first thing explained after the block.

HTTP/1.1 429 Too Many Requests
Retry-After: 6
RateLimit-Limit: 100
RateLimit-Remaining: 0
RateLimit-Reset: 6
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 1738368060
Content-Type: application/problem+json

{"type":"https://api.example.com/errors/rate-limit",
 "title":"Too Many Requests","limit":100,"window":"60s","retry_after":6}

Five decisions are embedded in that response.

1. Retry-After in seconds, not as an HTTP-date. Both formats are legal. Only one is parsed correctly by every client library.

2. RateLimit-Reset and X-RateLimit-Reset disagree, on purpose. The RateLimit-* family is the standardised one, defined by the IETF — the Internet Engineering Task Force, the body that writes the specifications underlying HTTP. Its Reset field carries seconds remaining, which is why it reads 6.

The older X-RateLimit-* family is a de-facto convention that grew up before the standard. Its Reset field carries a Unix timestamp, an absolute time expressed as seconds since 1 January 1970, which is why it reads 1738368060.

Send both, document which is which, and never change the meaning of either. This ambiguity has broken more client SDKs (software development kits, the libraries you publish for callers to use) than any algorithm choice on this page.

3. Send the headers on 200s too. A client that only discovers its budget after being blocked cannot pace itself in advance, so it will keep discovering it the same way.

4. 429 is not 503. 429 means “you, specifically, are over quota.” 503 means “the service is over capacity.” They imply different client behaviour and different alerting. Conflate them and you cannot tell a noisy customer from an incident on your own dashboards.

5. Intermediaries must not retry a 429. A proxy that retries on the client’s behalf multiplies the exact traffic the limiter is trying to remove.

Computing Retry-After per algorithm

Each algorithm knows something different about when the client’s budget will next allow a request, so each computes Retry-After differently. In the last column, the log’s exactness is the one benefit of its memory cost that a user can feel.

The sliding counter’s row is the only one that needs working out, and it is the same rejection from Sliding window counter and exactly how wrong it is: p = 90, c = 40, L = 100, currently at f = 0.25.

The estimate p(1-f) + c falls as f rises, because the previous window’s contribution decays. So the question is: how far does f have to advance before the estimate leaves room for one more request?

head room, requests we can still fit    100 - 1 - 40 = 59
the (1-f) that credits only 59 of p          59 / 90 = 0.6556
so f must reach                           1 - 0.6556 = 0.3444
minus the 0.25 already elapsed          0.3444 - 0.25 = 0.0944
convert the fraction to seconds          0.0944 x 60  = 5.67 s

Round up: Retry-After: 6.

Always round up. Rounding down guarantees the client’s first retry is also rejected, which doubles your 429 rate and buys nothing.

The retry storm, derived

A retry storm, sometimes called a thundering herd, is what happens when a large number of clients are told to wait and all obey precisely.

Nothing here is malfunctioning. Every client is doing what it was told, and the limiter is doing what it was designed to do. The failure comes entirely from the fact that they were all told the same thing at the same time.

Deriving the spike. Suppose an incident upstream causes the limiter to reject most traffic, and every rejected client is handed the same Retry-After: 1:

clients simultaneously rejected                 100,000
Retry-After handed to all of them                  1 s
client timer resolution + clock skew              10 ms

That third line is the width of the window they actually fire in. No client’s timer is perfect, but they are all within about 10 ms of each other, so 100,000 requests land inside a 10-millisecond span. Convert that count and span to a rate:

100,000 requests / 0.010 s = 10,000,000 req/s

Ten million requests per second, against a gateway sized for 100,000. As a multiple of the design point:

10,000,000 / 100,000 = 100x

And it does not decay. The spike produces another wave of rejections, each carrying the same Retry-After, which re-synchronizes the herd for the next second. The system becomes a phase-locked oscillator, and the limiter is keeping it locked.

Fixed windows make this worse by construction: as Fixed window and the boundary problem with real numbers showed, they hand every client the same boundary even when nothing has gone wrong.

The fix is jitter: adding randomness to a wait so that clients rejected together do not return together.

Full jitter means waiting a uniformly random amount anywhere between zero and the intended delay, rather than waiting the delay itself. The 100,000 retries then spread evenly over the whole second instead of piling into 10 ms:

100,000 requests / 1 s = 100,000 req/s

Exactly the design point. And the amplification you removed is just the ratio of the interval to the firing width:

1 s / 0.010 s = 100x

One line of client code removes a factor of 100.

The table below prices every common backoff strategy at N = 100,000 clients. The second row is the surprising one. In the table, d is the delay the client would otherwise have waited, n is the attempt number, and prev is the previous delay.

Each peak is just N divided by the spread. Equal jitter, for instance, randomizes only the second half of the delay, so its arrivals cover 500 ms:

100,000 / 0.5 s = 200,000 req/s

Exponential backoff — doubling the wait after each failure — does nothing about a herd, because every client doubles at the same moment. Doubling changes when the herd arrives; it never changes whether it arrives together.

Two more client-side rules

Retries belong at exactly one layer. Suppose three tiers of your stack each retry three times. The retries multiply:

3 x 3 x 3 = 27 backend requests from one client request

Twenty-seven backend requests during an incident, from a client that asked once. Every layer that is not the designated retrier must pass the 429 through untouched.

Cap retries as a fraction of successes — a retry budget. A retry budget permits retries only in proportion to how many requests recently succeeded.

Two numbers come out of that mechanism, and they are routinely quoted for each other. Keep them straight.

1.1x is the steady-state ceiling. While requests are succeeding, a 10% budget funds one retry per ten successes, so total load tops out at 1.1x the request rate — against the 4x that three blind retries give.

During a total outage it is 1.0001x. This is not a different mechanism; it is the same one. Retries are funded by the success rate, and during an outage that rate is zero, so nothing refills the budget. The only retries left are whatever seed the budget started with — 10, in the implementation below, against 100,000 failing requests: (100,000 + 10) / 100,000 = 1.0001.

The harder the dependency is failing, the less it is retried. 1.0001x is the number that demonstrates it.

A circuit breaker — a switch that trips after repeated failures and stops sending requests entirely for a cooling-off period — is the same idea with a coarser control.

The implementation. Three small pieces below: full_jitter is the uniform draw from the table, honor_retry_after is what a client should do with the server’s number, and RetryBudget is the budget. In RetryBudget, the two lines that matter are the self.tokens < 1.0 guard (an empty budget refuses rather than going negative) and self.tokens -= 1.0 (a retry costs a token). Delete either and the assertions below fail.

def full_jitter(attempt: int, base_s: float = 0.5, cap_s: float = 30.0,
                rng=random.random) -> float:
    """AWS-style full jitter.

    The uniform draw is the whole point. Doubling the delay does not
    desynchronize clients that were all rejected in the same millisecond --
    they simply all wait twice as long and arrive together again.
    """
    return rng() * min(cap_s, base_s * (2 ** attempt))


def honor_retry_after(retry_after_s: float, rng=random.random) -> float:
    """Never sleep exactly Retry-After.

    The server hands the identical value to every blocked client, so obeying
    it literally is what builds the herd. Sleep somewhere in [0, Retry-After]
    instead, so clients rejected together do not return together.
    """
    return rng() * retry_after_s


class RetryBudget:
    """Retries funded by recent successes, so a failing dependency is retried
    less, not more.

    A 10% budget adds one token per ten successes, capping steady-state load
    at 1.1x. During a total outage the success rate is zero, so nothing
    refills the budget; only the initial seed is spendable, which is
    (100,000 + 10) / 100,000 = 1.0001x against 100,000 failing requests.
    """

    def __init__(self, ratio: float = 0.1, seed: float = 10.0):
        self.ratio = ratio
        self.tokens = float(seed)

    def record_success(self) -> None:
        self.tokens += self.ratio

    def allow_retry(self) -> bool:
        if self.tokens < 1.0:      # empty budget refuses; never goes negative
            return False
        self.tokens -= 1.0         # a retry costs one token
        return True

# --- the RetryBudget guards, exercised. ---

# During an outage nothing refills the budget, so only the seed is spendable:
# 10 retries and no more, against any number of failures.
rb = RetryBudget(ratio=0.1, seed=10.0)
assert sum(rb.allow_retry() for _ in range(100)) == 10

# Successes refill the budget: at ratio 1.0, ten successes fund ten retries.
rb = RetryBudget(ratio=1.0, seed=0.0)
for _ in range(10):
    rb.record_success()
assert sum(rb.allow_retry() for _ in range(100)) == 10

10. Bottlenecks and scaling

The design has spare store throughput but a distribution problem. Store throughput how many shards already showed there is 75% headroom on every shard, so the first bottleneck is not store throughput. It is that traffic is not spread evenly across keys, which every number in Back of the envelope quietly assumed it was.

Hot keys

The first thing to fall over is a hot key, meaning a single key receiving a disproportionate share of all requests.

One partner integration sending 50,000 req/s uses a single client id. That id hashes to one slot, that slot lives on one shard, so all 50,000 land there. Compare against what one shard was provisioned for:

50,000 req/s / 25,000 ops/s per shard = 2x

That single key is 2x an entire shard’s provisioned throughput, and you cannot fix it by adding shards. Redis Cluster cannot split a key across shards, because resharding moves whole slots between machines and this key lives inside one slot.

Three fixes, in ascending order of cost.

1. Deny cache (The deny cache and why it is the highest leverage optimization). A 150,000x reduction, but only once the client is over its limit. A whale, meaning an unusually large customer, that sits at 99% of a very large limit is never denied, so it still reaches Redis on every request. The deny cache does nothing for it.

2. Shard the counter. Split one counter into k sub-counters, each carrying limit L/k, and send each request to one of them at random.

At k = 8 and L = 100, each sub-counter allows 100 / 8 = 12.5. But this reintroduces the binomial fairness error from A divide the limit ln per node, with random assignment across k buckets instead of N nodes and the same sqrt(L/k) spread. That is acceptable when L/k is large and nonsense when it is 12.

3. Dedicated tier. Give whales their own limiter shard, or a local token bucket on each gateway sized at L/N.

The structural objection from A divide the limit ln per node, that one client on one persistent connection lands entirely on one node, does not apply here, precisely because it is a whale. A whale has thousands of connections, so its traffic really is spread across every node, which is the one case where dividing the limit works.

Store CPU

The second thing to fall over is store CPU under the sliding window log. It costs three commands per request, one of which trims a sorted set, against a single script for the counter.

At 100,000 req/s that is the difference between 25% shard utilization and comfortably over 100%, the throughput half of the argument Memory the number that separates the algorithms made on memory. Both halves point the same way: the log is for small limits only.

Scaling levers, in order

Pull these top to bottom. The first is free and the ones below it are not.

11. Failure modes

This design breaks in production in ten ways. Each row has three parts: the trace an operator would see, the signal that detects it, and the guard that prevents it.

The last row is the important one: eviction is the only failure here that produces no error signal.

The one to watch is eviction. Every other row announces itself somehow: an error rate, a latency spike, a support ticket. Eviction does not. Every request succeeds, every dashboard is green, and the limits are gone until the day someone abuses the API and nothing stops them.

The fail-open number in the first row is the fleet’s total capacity divided across the nodes that have to enforce it alone:

100,000 req/s / 20 nodes = 5,000 req/s per node

That protects aggregate downstream capacity, which was the original point, and gives up per-client fairness, which is the cheaper of the two to lose.

12. Alternatives rejected

Every row names three things: what the alternative genuinely does better, the number that rules it out here, and the condition under which you would change your mind.

The last two rows matter most, because one of them says do not build this at all.

13. Interviewer pushback

Here is how the material above sounds when spoken out loud under pressure.

Each question names what it is testing, then gives an answer of the length and shape that earns the point. Every claim carries the number that backs it, which is the pattern to copy.

“Which algorithm, and why?” Testing: whether the four names come with numbers. Sliding window counter as the default, and it is a per-rule choice rather than a system-wide one. Two counters, 16 bytes, one atomic script. The error is unbiased with standard deviation sqrt(L f (1-f)), so at a limit of 100 the typical error is 5 requests — 5% — and it shrinks as 1/sqrt(L). But at a limit of 5 that same formula gives 22%, so for abuse limits like five password resets an hour I switch to the sliding window log, which is exact and costs 5 x 70 + 100 = 450 bytes at that limit. And where a burst allowance is a deliberate product feature I use a token bucket, because it is the only one where burst size and sustained rate are separate knobs.

“Show me the fixed-window boundary problem.” Testing: whether you can produce the number rather than the phrase. Limit five per minute. Five requests at 12:00:59.7 fill the 12:00 counter; five more at 12:01:00.1 fill the 12:01 counter. Both windows are individually correct and ten requests went through in 400 milliseconds. As a rate that is 25 per second against a nominal 0.083 per second, so 300x — and the 400 ms is arbitrary, so the instantaneous overshoot is unbounded. The bound people quote, 2x, is only the bound on the count.

“How wrong is the sliding window counter approximation?” Testing: whether you know its assumption. It assumes the previous window’s requests were uniform within it. If they were all in that window’s last second, the estimator discounts requests that are genuinely still in the trailing window: at halfway through the current minute it credits 50 when the truth is 100, so it admits 50 too many and 150 land in a 60-second window against a limit of 100. Push it to the end of the window and the worst case is 2L, the same as fixed window — but reaching it needs the current window’s traffic paced to a budget growing at 1.667 per second, so you get the count error without the rate spike. Statistically it is better than that sounds: the count still inside the window is Binomial(p, 1-f), whose mean is exactly the estimate, so the estimator is unbiased with standard deviation sqrt(p f (1-f)) — five requests at a limit of 100.

“What is wrong with INCR then EXPIRE?” Testing: whether you have implemented one. They are two commands. If the process dies between them the key has no TTL, so that client’s counter never resets and they are 429’d permanently — which surfaces as a support ticket, not an alert, and at a 0.1% loss rate it also leaks about 144 MB a day of immortal keys. Refreshing the TTL unconditionally is the opposite bug: the window never closes and a client sitting at 99 is limited to one request a minute. The fix is one Lua script — atomic because Redis is single-threaded and a script runs to completion — which also cuts two round trips to one and returns the Retry-After in the same reply.

“Twenty gateways. How do you enforce one global limit?” Testing: whether you know what synchronization buys and what it does not. Central store, one 0.5 ms round trip, 10% of my 5 ms budget. I would say why the alternatives lose. Dividing the limit by 20 gives 5 per node, which is fine on paper and catastrophic for a client on a single persistent connection — a 20x under-admission on the best-behaved client shape. Local counters with gossip are cheap, about 1.9 MB/s per node, but the over-admission bound is N x L = 2,000 and it is set by the node count, not the sync interval, so shortening the interval does not help — gossip is accurate under steady traffic and useless against a burst, which is the only thing a limiter exists to stop. And across regions none of this is available at all: a cross-region round trip is 150 ms against a 5 ms budget, 30x over, so global means per-region allocations that sum to the global limit.

“Redis is down. Now what?” Testing: whether the limiter can take down the service. Fail open, to a local token bucket on each gateway sized at total capacity divided by node count — 5,000 requests per second per node here. That protects the downstream from aggregate overload, which was the point, and gives up per-client fairness, which is the cheaper thing to lose. Failing closed converts a store blip into a full outage that I caused, on a component whose entire job is to be more available than the thing it protects. I would page on it, because during fail-open the fairness limits are simply not enforced, and I would keep the fallback bucket warm rather than construct it during the incident.

“You are handing out Retry-After: 1 to a hundred thousand clients. What happens?” Testing: whether you close the loop back to the client. They all come back inside about ten milliseconds of each other, which is ten million requests per second against a gateway sized for a hundred thousand — a hundred times the design point, repeating every second, and it does not decay because each wave regenerates the same Retry-After. Full jitter on the client, sleeping uniformly in the interval, flattens the same volume to exactly the design rate. Exponential backoff without jitter does nothing here, because every client doubles at the same instant. And I would jitter server-side too, returning base + uniform(0, base) rather than a constant, because I cannot make every client SDK on the internet do the right thing.

“Why is the limiter before authentication?” Testing: whether you have thought about cost per rejected request. Because a rejection has to be cheaper than an acceptance, and authentication costs a database lookup. If auth runs first, an unauthenticated flood buys free lookups at the rate it can send. So the first middleware limits on the IP with a generous pre-auth floor, and the tight per-client limits run after identity is established. The cost of that ordering is that CGNAT puts a whole office behind one key, which is why the pre-auth floor is generous and the real limit is on identity.

Cheat sheet

Every claim in this chapter, compressed to one line each, for the last five minutes before a round.

Next: the framework this chapter applied is 03 — A Framework For System Design Interviews; the estimation habits behind Back of the envelope are 02 — Back Of The Envelope; the ring behind the key-owner alternative in D key owner sharding is 05 — Design Consistent Hashing; and the sharding, pooling and caching layers the counter store itself sits in are Scaling partitioning sharding pooling caching. Note what is not cited: this counter lives in RAM in Redis, so the on-disk B-tree and LSM-tree internals in the rest of sql 03 are not what makes it fast.