How to design a rate limiter

In this lesson, we’ll design a rate limiter: the component that sits in front of a service and decides, for each arriving request, whether to serve it or reject it. It makes that call from how many requests the same caller has already made recently. By the end you’ll be able to derive the worst-case burst each algorithm lets through, size the counter store from a request rate, pick an algorithm from a limit and a memory budget, and keep the count correct once twenty machines share it.

The whole design turns on one instant. There are five standard algorithms (the token bucket, the leaking bucket, the fixed window, the sliding window log, and the sliding window counter) and they differ mostly in what happens at a window boundary, the moment one counting period rolls over into the next. Each has a different worst case there, so we derive that worst case for each, show how to pick one from a limit and a memory budget, and then keep the decision correct once twenty machines share a single counter.

The input is one request, from which 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.”

The output is a verdict plus the numbers a well-behaved caller needs:

check(key="cust_42", route="POST /v1/charges", cost=1)
  ->  allowed = false
      limit = 100          the ceiling for this caller on this route
      remaining = 0        budget 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.

A 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 shared counter, and a design that turns on what each algorithm does at a window boundary.

The core trade-off is three-way:

• memory per key: bytes of state kept per caller;
• burst tolerance: how many requests you allow through at once;
• exactness: how far the count may drift from the truth.

Every algorithm below sits at a different corner of that triangle.

Framing: what a rate limiter is actually for

Before choosing an algorithm, decide which of three jobs the limiter is doing. All three get called “rate limiting,” but they want different algorithms and disagree about what “correct” means.

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 the sliding window counter section derives from counting statistics. So the job that most needs exactness is the one where approximation fails hardest.

Why a limiter at all

Without one, a single misbehaving client (usually a customer’s own retry loop, not an attacker) can saturate a shared database and turn 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, it has to sit before anything expensive in the request path. If authentication runs first and each authentication costs a database lookup, a flood of unauthenticated requests buys free database lookups at the rate the attacker can send them: the limiter rejects them, but only after you have paid for them. A rejection has to cost less than an acceptance, or the limiter is not protecting anything.

Requirements

Functional

Written as scope in and scope out:

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

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.

Two things in the OUT line are adjacent products that solve different problems. A WAF (web application firewall) inspects request content for attack patterns such as SQL injection; a rate limiter looks only at counts, so they share no machinery. DDoS scrubbing handles a distributed denial-of-service attack (many machines flooding you at once) and belongs upstream at the network edge, because by the time traffic reaches your gateway you have already paid to receive it.

Non-functional — these decide the architecture

Three terms in that table:

• p99 latency is the 99th percentile: the number that 99 of every 100 requests come in under. Averages hide the tail; percentiles are what users feel.
• Fail-open means that when the limiter’s own machinery breaks, requests are allowed through, not rejected. The opposite, fail-closed, turns a limiter outage into a total service outage that you caused.
• Eventually consistent means copies of a value on different machines may disagree for a while and are only guaranteed to agree once updates stop. That is fine for a profile picture and bad for a counter whose job is to be right during a burst, which is precisely when the copies disagree most.

Back of the envelope

One traffic figure sizes four things: how many counter-store machines you need, how much memory each algorithm costs, how much network the limiter uses, and how much of the latency budget a shared counter consumes.

The starting assumptions

A gateway 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 here is assumed, 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

Sanity-check the premise first. The median active client sends 100,000 / 200,000 = 0.5 req/s, or 30 per minute, 30% of an allowed 100. That is what a sane default looks like: most callers never notice the limiter. Had the ratio come out at 300%, the limit would be wrong, not the design.

Store throughput: how many shards

The shared counter lives in Redis, an in-memory key-value store that keeps all data in RAM and serves get/set/increment operations over the network in microseconds. Redis executes commands one at a time on a single thread. That is why no two commands interleave (the property the whole correctness argument in Where the counter lives rests on) and it is also why one instance has a hard throughput ceiling of roughly 100,000 simple operations per second (one thread is one thread).

Budget one shared-store operation per request. One instance would then carry the entire 100,000 req/s peak at 100% utilization: no headroom, and no second machine to survive the loss of the first. Provisioning for 30% utilization instead needs 100,000 / 0.30 = 333,333 ops/s, which rounds up to 4 shards. Four shards each carry 25,000 ops/s at 25% utilization; the 75% left idle absorbs a failover, since if one shard dies its traffic spreads over the other three and each rises only to about 33,300 ops/s.

A shard is one of several independent copies of the store, each owning a disjoint slice of the keys. A failover is the automatic promotion of a standby when the primary dies, during which the dead shard’s traffic has to go somewhere.

Network: not the bottleneck

Each check sends roughly 200 bytes up and 100 back, so 100,000 x 300 bytes = 30 MB/s, or 240 Mbps. Against a 1 Gbps network card that is 24% of one card, or 6% of each once spread across four shards. The limiter is a latency and correctness problem, not a bandwidth one.

Latency: what the budget forbids

A round trip within one availability zone (AZ: one datacenter, or a cluster close enough that the network between machines is cheap and fast) is about 0.5 ms. Two commands (INCR then EXPIRE) is 1.0 ms, 20% of the 5 ms budget. A cross-region round trip, from the estimation chapter’s constants, is 150 ms at worst (California to Europe), 150 / 5 = 30x over the entire budget.

Two conclusions follow. The store must live in the same region as the gateways. And 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, where each region enforces locally in real time and the regions compare notes afterwards.

Memory: the number that separates the algorithms

Redis costs roughly 100 bytes to hold one small key all-in (about 50 bytes of object and hash-table overhead, ~30 bytes of key string, plus the value). The absolute number is worth measuring with MEMORY USAGE on your own data, but the ratios below survive any plausible value.

Two rows are unlike the others. The sliding window counter stores its two counters in two Redis keys, not two fields of one key, because the window index lives in the key name (see Data model). So it pays the ~100-byte per-key overhead twice: ~200 bytes, 40 MB, not 130 and 26. The token bucket keeps both numbers in one hash, so it genuinely costs one key’s overhead.

The sliding window log stores one ~70-byte timestamp per admitted request, so one client’s key costs n x 70 + 100 bytes for n requests in the window. At the median 30 req/min that is 2,200 bytes per key and 440 MB across 200,000 keys; with every client pinned at the 100/min limit it is 7,100 bytes and 1.42 GB, about 36x the sliding window counter and 55x the token bucket.

The 1.4 GB still fits in RAM, so memory alone is not the objection. What disqualifies the log is that it 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 writes 50,000 x 60 x 70 bytes = 210 MB into its own sorted set in one 60-second window, and nothing stops the next window. Log only what you admit, and the set can never exceed L entries.

API and data model

API

The limiter is middleware: code that runs on every request, between the network and the application, not a separate service called by name. 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, read-mostly surface. Operators change limits rarely; 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 with opposite access patterns. The rules are read constantly and written almost never. The counters are written on every request. That difference is why they are two stores.

TTL is time to live, an expiry the store attaches to a key, after which the store deletes the key itself: how the limiter’s memory stays bounded without a cleanup job.

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:

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. 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 land on the same shard. That guarantee is what lets one script touch several keys at once: the sliding-window script reads the current and previous window key, and a script cannot span machines.

2. The window index is in the key name, not the value. Rolling over to a new window then costs nothing: the old key 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, so its stored state is indistinguishable from a fresh full bucket and deleting it loses nothing. At C = 100, r = 1.667/s that is 60 s; the + 1 is a rounding margin.

4. Rules never touch Redis on the hot path. The hot path is the code that runs on every request. The rule table is tiny (200 tiers at ~1 KB is 200 KB), so it sits in each gateway’s own process memory, refreshed by polling the config store every 10 seconds. When several rules could apply, the most specific wins: client+route beats client, beats tier+route, beats tier, beats the global default.

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. Solid arrows are the request path; dotted arrows are off it.

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"]

Walking one request through:

• Arrival. A request hits an L4 load balancer. “L4” means layer 4, the transport layer: it picks a destination using only addresses and ports and never reads the HTTP request, which is what makes it fast and also why it knows nothing about who the caller is.
• Gateway. The balancer hands the connection to one of twenty gateways, each holding the rule table in process memory, refreshed by polling the config store every 10 s.
• Deny cache (cheap branch). The gateway first consults its local deny cache, an in-process map from client id to the time until which that client is known to be blocked. A hit answers in 0 round trips with the full rejection.
• Redis (expensive branch). A miss costs exactly one call, EVALSHA (“run the script I already uploaded”), about 0.5 ms, addressed by a hash tag on client id so every key for one client lands on one shard.
• Verdict. Allowed requests continue to the upstream service; 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, derived in Failure modes.

Three load-bearing decisions are visible here, each defended below:

1. The limiter runs before authentication, because a rejection must cost less than an acceptance.
2. The decision is one round trip, not two, both a latency and a correctness argument (Where the counter lives).
3. The deny cache exists because the abusive client is, by definition, the one generating the most store load (The deny cache).

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 “may this request proceed?” from a small amount of stored state. They differ in what that state is, how much it costs, and how badly a client that times its requests carefully can game them.

Each subsection has the same four parts: mechanism, state, burst as a number, and the assumption that, when it fails, means you picked the wrong algorithm.

A window is the span 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. On average throughput these algorithms are the same; burst behaviour is where they differ. Throughout, L = 100, W = 60 s, and the nominal sustained rate is r = L / W = 1.667 requests per second.

Token bucket

The token bucket is for when a client may save up unused allowance and spend it in one go. It is the only algorithm here where burst size is a knob separate from sustained rate.

Mechanism. A bucket holds up to C tokens and is topped up at r tokens per second, with overflow discarded. Each request takes one token; if fewer than one is present, it is rejected. The refill is not a background process. It is computed lazily on read, from the time since the previous request:

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

(now - last) x r is how many tokens would have dripped in since the last request; adding it gives the theoretical level, and min(C, ...) clips it to capacity (the “overflow discarded” part). Lazy refill is what makes the algorithm affordable: a background refiller would need one timer per active key, and there are 200,000 of them.

State. Two numbers, tokens (a float) and last_refill (a timestamp), 16 bytes of information, ~130 bytes once Redis overhead is added.

Burst, derived. From a full bucket, the requests admitted over an interval T are the C already in the bucket plus the r x T that drip in:

A(T) = C + r x T
A(60) = 100 + 1.667 x 60 = 200 requests

Up to 2L in a 60-second window, and the first 100 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. Set C = 20 for 100/min sustained but never more than 20 at once; set C = L = 100 to let clients save up a full minute of allowance in exchange for a deliberate 2x window overshoot.

Implementation. The core is one lazy-refill line and a compare-then-subtract:

def allow(bucket, cost, now, capacity, refill):
    # lazy refill: add whatever would have dripped in since last touch
    bucket.tokens = min(capacity, bucket.tokens + (now - bucket.ts) * refill)
    bucket.ts = now
    if bucket.tokens >= cost:
        bucket.tokens -= cost
        return True
    return False

Two guards this skips are not optional in production. cost must be validated > 0: cost = 0 admits forever, and cost < 0 both admits and refunds the bucket past capacity, because the min against capacity runs before the subtraction. Write the check as not (cost > 0), not cost <= 0, because every comparison with NaN is False, so nan <= 0 lets a NaN through. Apply the same to capacity and refill, and reject infinities separately.

Assumptions, and what breaks. Three, and the first and third force a different algorithm, not just a different constant.

• The downstream can absorb C requests at once. Load-bearing. Permitting that clump is the entire point of the bucket, so shrinking C to make it safe gives up the feature you picked this algorithm for.
• The clock moves forward at the right speed. Mild, with a real fix. A clock that jumps backwards hands out negative tokens; one that jumps forwards refills for free. Use a monotonic clock, one that only counts upward and is immune to time-of-day adjustments.
• The read-modify-write is atomic. Load-bearing, and it must be enforced twice. Inside one process, by a lock: ship this into a threaded server without one and it admits 2–3x its capacity (measured: 570–1,767 admitted against a capacity of 500). Across the twenty gateways sharing one bucket, by moving the whole decision into the store, the Lua script of Where the counter lives. A lock does nothing across machines; a script does nothing about two threads inside one gateway’s 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 it 100 at once, causing the outage the limiter was installed to prevent.

Leaking bucket

The leaking bucket is for when the downstream needs a steady stream, not a bounded total. It is the only algorithm here that delays requests instead of rejecting them.

Mechanism. Requests enter a FIFO queue (first in, first out) of capacity q and leave at a fixed rate r. If the queue is full, a new request spills over and is rejected. The output rate is exactly r, always. 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. At 200 bytes per stub and q = 50, that is 10,000 bytes per key and 2 GB across 200,000 keys, plus a durability question, since queued requests are real work a customer is waiting on and they vanish if the queue’s machine restarts.

Burst, derived. The number admitted over T is r x T + q, the same shape as the token bucket with q playing the role of C; at q = L = 100 that is again 200. The difference is what happens to those 200: they leave at 1.667/s no matter how fast they arrived, so the cost lands on the caller as latency, not on the downstream. Draining a full q = 100 queue takes 100 / 1.667 = 60 seconds, fatal for a synchronous HTTP request whose client times out at 30. Even a modest q = 10 adds 6 seconds. The request holds a connection the whole time, the client times out and retries anyway, and a clean rejection becomes doubled load plus a held connection.

Assumptions, and what breaks. Load-bearing: the caller is willing to wait q/r seconds. For a synchronous request that is false, and no q or r rescues it. Milder: the queue survives a restart (a crash silently drops accepted work), and rejecting on overflow is acceptable (which reintroduces the “what do I tell the client” problem the queue was meant to remove).

Where it is right: outbound traffic to a third party with a hard 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.

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

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.

Mechanism. Chop time into fixed, clock-aligned windows: every minute starts exactly at :00, the same instant for every client and machine. Keep one counter per (key, window index). On each request, increment the counter (Redis’s INCR, which adds one and returns the new value in a single operation), compare against L, and let the key delete itself when its TTL passes.

State. One integer: the cheapest thing on the list, one store operation per request, no script.

Burst, derived. Use a small limit, L = 5 per minute, so the effect is visible:

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

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

The first five fill the 12:00 counter to the limit; 400 ms later a different key (counter[12:01], starting at zero) accepts five more. Both counters are individually correct. The algorithm is answering “how many in this aligned minute?” when you asked “how many in any minute?” As a rate, that is 10 / 0.4 = 25 req/s against a nominal 5 / 60 = 0.083 req/s, or 300x. And the 400 ms is arbitrary: send the same ten inside 4 ms and it is 30,000x. So the bound has two halves: the over-admission factor in count is exactly 2, and in instantaneous rate it is unbounded. The 2x is the number people quote; the rate bound is the one that matters.

A second, quieter problem is that aligned windows synchronize every client. Every counter resets at :00, so every blocked client’s natural retry time is the same instant, the seed of the retry storm, planted before any client misbehaves.

Assumptions, and what breaks. Load-bearing: the client does not know where the boundary is, or does not care. The boundary is public (the top of the minute), so against an adversary the algorithm admits 2L back to back on demand, which is why fixed window is never right for abuse prevention. Milder: every machine agrees which window it is in; a gateway whose clock is 400 ms fast is a constant error you can ignore against a 60 s window but is 40% of a 1 s window.

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

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 timestamp of every admitted request in a sorted set (a Redis structure ordered by a numeric score, here the timestamp, so a range can be trimmed or counted in one command). Each request:

1. deletes every entry older than now - W, those having aged out of the trailing window;
2. counts what is left;
3. admits if the count is under L;
4. if admitted, appends the current timestamp.

Step 1 is what makes the window sliding instead of aligned: the set always describes the last W seconds measured backwards from this instant.

State. One 8-byte timestamp per admitted request, ~70 bytes per member with Redis bookkeeping, 440 MB typical and 1.4 GB with every client at its limit, against 40 MB for the counter and 26 MB for the token bucket.

Burst. Zero error, at any alignment. The count between now - W and now is computed directly, so no W-length interval can ever contain more than L requests: there is no boundary to exploit because there is no boundary. It also gives the only exact Retry-After: the oldest timestamp still in the window, plus W, minus now, is the precise instant a slot frees up. Every other algorithm rounds up.

Assumptions, and what breaks. Load-bearing, in a security sense: only admitted requests are recorded. Log rejects too and the attacker sets your memory: 210 MB from one client in one window. Milder: the limit is small enough for a per-request record to be affordable, and the trim stays cheap: trimming a set of tens of thousands of entries inside a script blocks the whole Redis instance while it runs.

Where it is right: small, hard limits. Five password resets per hour costs 5 x 70 + 100 = 450 bytes, at which the memory argument disappears, and small limits are exactly where the cheap counter is at its worst, so both arguments point the same way.

Sliding window counter — and exactly how wrong it is

The sliding window counter is the algorithm most production limiters run: it approximates the log’s exact answer with two integers instead of a list of timestamps. How large that 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. The trailing window, the last W seconds counted backwards from now, always straddles the boundary: all of c is inside it, and only part of p is. The estimator does not know how much of p, so it assumes the previous window’s requests were spread evenly and credits a proportional slice:

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

If f = 0.25, the trailing window reaches back over the last three quarters of the previous one, so it credits 0.75 of p.

State. Two integers, but in two Redis keys because the window index is part of the key name: ~200 bytes per client, not 130. Memory and work per request are constant regardless of traffic, and the whole decision fits in one script.

Worked decision. 15 seconds into the current minute, p = 90, c = 40, L = 100:

f = 15 / 60 = 0.25
est = 90 x 0.75 + 40 = 107.5

107.5 exceeds 100, so the request is rejected even though the current window has used only 40. That is the algorithm working as designed: it refuses to let the client escape the previous minute’s traffic just because a clock boundary went past, the precise failure of the fixed window.

Bounding the error

The estimator makes exactly one assumption: uniform arrivals within the previous window. The true trailing count is p_in + c, where p_in is how many of the previous window’s requests genuinely fall in its final (1 - f) fraction; the estimator uses p x (1 - f) in its place, and all the error lives there. Holding p = 100, f = 0.5 (so the estimate is always 50) and varying only the shape of the previous window:

The error is p(1 - f) - p_in, and since p_in ranges from 0 to p, over-admission is at most p x f (worst as f -> 1) and under-admission at most p x (1 - f) (worst as f -> 0). At p = L and f near 1 the worst-case total is c + p_in = 2L, the same as fixed window. What is different is that reaching it needs the previous window to spike at its end and the current window’s requests paced against a budget growing at only 1.667/s; you cannot dump them in a millisecond. So the count error survives but the 300x instantaneous rate blowup does not, which is why this algorithm is the default and the fixed window is not.

The statistical answer

The 2L bound is adversarial. Real traffic is not, and the typical error is small enough to quote as a percentage. Suppose arrivals in the previous window carry no internal pattern (a Poisson process, or any process where the order of arrivals carries no information). Then each of the p requests independently lands in the trailing portion with probability 1 - f, in p biased coin flips, a binomial distribution Binomial(p, 1 - f). Its mean is p x (1 - f), exactly what the estimator computes, so the estimator is unbiased: over many windows it is neither high nor low.

How far off a single decision is is the standard deviation, sqrt(p f (1 - f)), largest at f = 0.5. At p = 100, f = 0.5 that is sqrt(25) = 5 requests, 5% of a limit of 100. Setting p = L and f = 0.5, the peak std dev is sqrt(L)/2, and relative to the limit it is 1 / (2 sqrt(L)). The sqrt(L) in the denominator is the whole story. The relative error shrinks as the limit grows:

The approximation is excellent where limits are large and terrible where they are small, and small limits are exactly the abuse-prevention case where you need it exact. So 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.

Assumptions, and what breaks. Three, one load-bearing.

• Uniformity within the previous window. Not load-bearing: the table above prices its failure exactly (p x f over, p x (1 - f) under), a bounded, quotable error.
• The limit is large enough that 1/(2 sqrt(L)) is small. Load-bearing. At L = 5 the typical error is 22%, and no tuning fixes it because it comes from counting statistics. When this fails, switch to the log.
• Every gateway agrees on where the window boundaries are. This is why the counter uses wall-clock time even though the token bucket wanted a monotonic clock: boundaries must be identical across twenty machines, and a per-process monotonic clock starts from an arbitrary point on each.

Implementation. Wall time moves backwards (NTP corrections step it), and a backwards step past a boundary would zero both counters and hand the client a fresh budget, the same 2L failure this algorithm exists to remove. The fix is to clamp the clock to the highest value it has ever seen, so a backwards step freezes the window instead of resetting it:

def roll(state, now, window):
    now = state.high = max(now, state.high)   # never backwards: a step back
    idx = int(now // window)                  # would zero BOTH counters
    if idx != state.idx:
        # only an immediately-preceding window contributes; a gap of two
        # or more means the previous one has fully aged out
        state.prev = state.curr if idx == state.idx + 1 else 0
        state.curr = 0
        state.idx = idx
    return (now % window) / window            # elapsed fraction f

def allow(state, now, window, limit):
    f = roll(state, now, window)
    if state.prev * (1 - f) + state.curr + 1 > limit:
        return False
    state.curr += 1
    return True

The clamp is per-process. It cannot stop a gateway whose clock is merely slow from filing requests under the wrong window index in the first place, because the index is part of the Redis key name. The fix for that is to read the clock inside the store, the subject of Where the counter lives.

Side by side

Every number derived above, in one table. C is the token bucket’s capacity, q the leaking bucket’s queue depth, L the limit, W the window, r = L/W. Two rows decide most arguments: worst count in a window is the number usually quoted, and worst instantaneous rate is the one that separates fixed window from everything else.

The decision tree turns that into a procedure, ordered so the most decisive question comes first:

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"]

• Smooth rate? Only the leaking bucket and GCRA deliver it, and only by making the caller wait, so this branch is for outbound calls. A “yes” eliminates four of five options at once.
• 2x overshoot acceptable? For daily and monthly quotas, the fixed window’s 8 bytes and single INCR are unbeatable.
• Limit under ~20? Below L = 20 the counter’s relative error passes 10% and only the log is trustworthy, and there the log costs almost nothing (450 bytes at L = 5).
• Controlled burst allowance? If saving up unused allowance is a product feature, the token bucket’s capacity C is the only knob that expresses it.

Otherwise the sliding window counter wins on cost. The default is a sliding window counter for tiered quotas, a token bucket where a deliberate burst allowance is a feature, and a sliding window log for small hard limits: one system, three rules, chosen per route.

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

The useful distinction is which assumption, when violated, means you picked the wrong algorithm, not the wrong constant. Load-bearing assumptions cannot be tuned around; their failure forces a different algorithm. Non-load-bearing failures cost a parameter change or a bounded, quotable error. Bolded rows are load-bearing.

Four assumptions cut across every algorithm:

• Clock skew: gateways kept in step by NTP (the Network Time Protocol, which disciplines a clock against reference servers) sit within about ±50 ms. Negligible against a 60 s window, 5% against a 1 s window, and against a fixed-window boundary it is the whole effect. The clean fix is to read the time inside the store.
• Burst tolerance: a contract with whatever sits behind the limiter, not a property of the algorithm alone. Getting it wrong is always a wrong-algorithm error.
• Key distribution: every memory and throughput number assumes traffic spreads evenly across keys. One partner integration can be a large fraction of the fleet’s requests on a single key, landing entirely on one shard.
• Node churn: machines joining and leaving changes how many independent counters exist, which is the quantity that sets the over-admission bound for every design that does not share one counter.

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 one 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: from everyone else’s point of view it either has happened completely or not at all.

Local versus shared

Can each gateway keep its own copy of the count, or must all twenty share one?

Local counters over-admit because each of the N gateways enforces the full limit alone: 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, and everything below makes that one shared round trip 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 here: two from splitting one decision across two commands, one from splitting it across two machines.

Race 1: the lost EXPIRE. INCR increments the counter; EXPIRE attaches a TTL. They are two commands, and anything can happen between them, including the calling process dying:

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 resets, so once it crosses 100 that client is rejected forever: a support ticket days later, not an alert. It also leaks memory: at a 0.1% loss rate across 1,000,000 daily clients able to open a window in any of 1,440 minutes, that is 1.44 billion x 0.001 = 1.44 million immortal keys, ~144 MB/day, ~4.3 GB/month, until Redis’s eviction policy starts deleting live counters and the limiter silently stops limiting.

Race 2: the window that never closes. If every request does INCR then EXPIRE key 60, the TTL is refreshed on every request, so for a client that keeps sending, the window never closes. A client that reaches 99 and then sends once every 59 seconds keeps pushing the expiry out, so the counter sits at 99 forever and the client is limited to 1/min instead of 100, a 100x error in the direction that generates angry customers. EXPIRE key 60 NX (Redis 7.0+) fixes it: NX means “set the expiry only if the key does not already have one,” in the same command. The alternative, “set the TTL only when INCR returns 1,” gets the semantics right and the atomicity wrong: it is two commands again, so it reintroduces race 1. One command, or a script. Never two.

Race 3: read-modify-write across two machines. The token bucket and both sliding windows fetch state, compute from it, and store the result. Any gap between read and write is a place where a second gateway reads the same stale value:

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

Two tokens spent, one recorded, once per race, which at 100,000 req/s is often. Redis offers WATCH/MULTI/EXEC, an optimistic concurrency scheme that proceeds without locking and retries if anyone else touched the key. It is correct and still wrong here: retries happen where contention is highest, which is the busiest key, so your largest client triggers a retry storm inside Redis on the one key you least want to slow down.

The fix: one script, one round trip

The fix for all three is the same: send the entire decision to Redis as a single Lua script, a short program Redis stores and executes server-side. Redis runs commands one at a time on one thread, and a script runs to completion before the next command is served, so a script is atomic by construction: no gap for a second gateway to read into, and no way to do the INCR without the EXPIRE. It also collapses two or three round trips into one and returns the verdict and Retry-After together.

The sliding window counter script is the estimator moved server-side:

-- Sliding window counter. Atomic, one round trip.
-- KEYS[1] = current window counter, KEYS[2] = previous window counter.
-- Both carry the {client} hash tag, so Redis Cluster routes them to one slot.
-- ARGV = limit, window_ms, elapsed_ms in this window.
-- `elapsed` comes from the gateway: the window index is part of the KEY NAMES,
-- which Redis Cluster requires the client to compute so it can route the call.
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 }

est = prev * (1 - f) + cur is the estimator, unchanged; everything above it just fetches p and c, defaulting a missing key to '0'. The if est + 1 > limit test asks whether admitting this request would exceed the limit: the + 1 is why a client at exactly the limit is rejected. PEXPIRE ... window * 2 sets a TTL of two windows because when the next window becomes current, this key becomes its previous-window counter; expire it after one and the algorithm degrades to a fixed window at the boundary it exists to handle.

The token bucket script is the same structure with one key, and it reads the clock server-side:

-- Token bucket. Atomic, one round trip.
-- KEYS[1] = rl:{client}:route.  ARGV = capacity, refill/s, 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: one Redis instance and twenty
-- gateways, so taking `now` from the gateway lets the slowest-clocked one drag
-- `ts` backwards for everyone sharing this key. This key has no window index
-- in its name, so unlike the sliding-window script it is free to read TIME.
local t   = redis.call('TIME')          -- {seconds, microseconds}
local now = tonumber(t[1]) + tonumber(t[2]) / 1000000

-- cost = 0 admits for ever; cost < 0 admits AND refunds past capacity.
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)
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 notes:

• EVALSHA, not EVAL. EVAL sends the whole script text every call; EVALSHA sends only a 40-character SHA-1 fingerprint of a script Redis has already cached. Sending the body adds ~800 bytes to a 200-byte request, a 5x increase for nothing. Cache the fingerprint on the gateway and fall back to EVAL when Redis replies NOSCRIPT (it has never seen that fingerprint, which happens after a restart).
• Read the clock in the script wherever you can. Calling redis.call('TIME') removes gateway clock skew entirely (one clock instead of twenty) and is safe on replicas, because since Redis 5 a primary ships the effects of a script to replicas instead of re-running it. The sliding-window script cannot, because the window index is in the key name and Redis Cluster requires the client to compute it. There, client-supplied time is fine when the window is large: ±50 ms of NTP skew is 0.08% of a 60 s window but 5% of a 1 s window.
• Scripts must be deterministic and short. Deterministic (no randomness, no reading outside state) so a replica replaying the effects reaches the same answer. Short because a script blocks the single Redis thread while it runs: a loop trimming a large sorted set 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 map in each gateway’s own memory from client id to the time until which that client is known to be blocked. It works because of an asymmetry: “allowed” stops being true the instant the next request arrives, so it cannot be cached, but “denied until T” stays true for the rest of the window, so it can. And that lines up with load: the client generating the most store traffic is the one exceeding its limit, whose answer is the cacheable one.

For one abusive client sending 50,000 req/s, that is 50,000 x 60 = 3,000,000 Redis operations in a window without the cache, versus 20 with it (each of the twenty gateways probes Redis once per window, then answers locally). That is a 150,000x reduction against the worst client on the platform, bought with a dictionary. 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, bounded, in the safe direction, and already visible in the Retry-After they were handed.

Distributed rate limiting, and what synchronization costs

Twenty gateway nodes all enforce a single limit that applies to the client as a whole, not to each node separately. There are four ways they might coordinate, and three lose on a number you can derive directly.

A. Divide the limit — L/N per node

Give each node L / N = 100 / 20 = 5 requests per minute and let it enforce that alone, with no communication. This is correct only if a client’s traffic spreads uniformly across the twenty nodes, and it does not. Statistically, a client sending 100 requests spread randomly makes the per-node count Binomial(100, 0.05): mean 5 (matching the limit), but standard deviation sqrt(100 x 0.05 x 0.95) = 2.18, so a node routinely lands two or three above its mean and roughly 13% of the time rejects a client comfortably under its global limit. Structurally, and worse: a well-written client opens one long-lived HTTP/2 connection assigned to one gateway, so all its traffic lands on one node: effective limit 5/min instead of 100, a 20x under-admission on the best-behaved client shape.

B. Central store

One shared counter every node reads and writes, the architecture of High-level architecture. It is exact, costs one 0.5 ms round trip (10% of the 5 ms budget), and makes the store a hard dependency whose failure would stop the request path. Failure modes answers that with a fail-open fallback, which is why fail-open is a requirement. This is the answer, and the alternatives are worse for reasons you can quantify.

C. Local counters plus periodic sync

Keep a counter per node and have nodes broadcast their recent deltas to peers every so often: gossip. Bandwidth is cheap: at a 100 ms interval each node touches ~500 keys, broadcasts ~10,000 bytes to 19 peers 10 times a second, about 1.9 MB/s, or 1.5% of a 1 Gbps card. But the correctness bound is set by N, not the interval: immediately after a sync every node believes the count is 0, and in the interval before the next sync each of the twenty admits up to L, so N x L = 2,000 against a limit of 100. Halving the interval does not improve the bound: it only lowers the probability of hitting it. 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

Make the gateway fleet its own counter store: assign each key an owner among the twenty gateways using consistent hashing (a scheme that maps keys and machines onto the same circular number space, the hash ring, so each key belongs to the first machine clockwise from it, and adding or removing a machine moves only a small share of keys; the consistent-hashing chapter derives this). Every gateway forwards a check to whichever node owns the key. It is exact, costs one ~0.5 ms hop, and needs no external system. But you now own cluster membership (the nodes must agree on who is alive), rebalancing (ownership moves when a node joins or leaves), and losing a node loses its counters mid-window. That is Redis with extra steps, unless you already run a hash ring for another reason.

What “global” actually means across regions

A cross-region round trip is 30x the latency budget, so a genuinely global counter is not something you can buy at 5 ms at any price. That leaves two honest designs:

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

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, because 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 will guess wrong.

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 here:

1. Retry-After in seconds, not an HTTP-date. Both are legal; only seconds 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 body that writes HTTP’s specifications), and its Reset carries seconds remaining (6). The older X-RateLimit-* convention predates the standard and its Reset carries a Unix timestamp (1738368060). Send both, document which is which, and never change either. This ambiguity has broken more client SDKs than any algorithm choice here.
3. Send the headers on 200s too, so a client can pace itself before it is blocked instead of discovering its budget only by being rejected.
4. 429 is not 503. 429 means “you, specifically, are over quota”; 503 means “the service is over capacity.” Conflate them and you cannot tell a noisy customer from an incident on your dashboards.
5. Intermediaries must not retry a 429. A proxy that retries on the client’s behalf multiplies the exact traffic the limiter is removing.

Computing Retry-After per algorithm

Each algorithm knows something different about when the budget will next allow a request:

The sliding counter’s row is the rejection from the worked decision above. The estimate p(1-f) + c falls as f rises, so the question is how far f must advance to leave room for one more: headroom is 100 - 1 - 40 = 59, that credits 59/90 = 0.6556 of p, so f must reach 1 - 0.6556 = 0.3444, minus the 0.25 already elapsed is 0.0944, times 60 is 5.67 s, rounded up to 6. Always round up: rounding down guarantees the first retry is also rejected, doubling your 429 rate for nothing.

The retry storm, derived

A retry storm (or thundering herd) is what happens when many clients are told to wait and all obey precisely. Nothing is malfunctioning: every client does what it was told, and the failure comes entirely from being told the same thing at the same time.

Suppose an incident causes the limiter to reject most traffic and hand every client the same Retry-After: 1. Client timers are not perfect, but all fire within about 10 ms of each other, so 100,000 requests land inside a 10 ms span: 100,000 / 0.010 = 10,000,000 req/s, against a gateway sized for 100,000, or 100x the design point. And it does not decay: the spike produces another wave of rejections carrying the same Retry-After, re-synchronizing the herd. The system becomes a phase-locked oscillator, and the limiter keeps it locked. Fixed windows make it worse by construction, handing every client the same boundary even when nothing is wrong.

The fix is jitter: randomness added to a wait so clients rejected together do not return together. Full jitter waits a uniformly random amount in [0, delay] instead of the delay itself, spreading the 100,000 retries over the whole second: 100,000 / 1 = 100,000 req/s, exactly the design point. 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.

Each peak is N divided by the spread. Exponential backoff does nothing about a herd, because every client doubles at the same moment: doubling changes when the herd arrives, never whether it arrives together.

Two more client-side rules

Retries belong at exactly one layer. If three tiers of your stack each retry three times, one client request becomes 3 x 3 x 3 = 27 backend requests during an incident. 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. A 10% budget funds one retry per ten successes, so steady-state load tops out at 1.1x the request rate (against 4x for three blind retries). During a total outage the success rate is zero, so nothing refills the budget and only the initial seed is spendable: with a seed of 10 against 100,000 failing requests, (100,000 + 10) / 100,000 = 1.0001x. The harder the dependency is failing, the less it is retried. A circuit breaker (a switch that trips after repeated failures and stops sending for a cooling-off period) is the same idea with a coarser control.

The two client-side pieces are small. Full jitter is a uniform draw; a retry budget refuses when empty and costs one token per retry:

def full_jitter(attempt, base_s=0.5, cap_s=30.0, rng=random.random):
    # the uniform draw is the point: doubling the delay lets clients rejected
    # in the same millisecond simply wait twice as long and arrive together
    return rng() * min(cap_s, base_s * (2 ** attempt))

class RetryBudget:
    def __init__(self, ratio=0.1, seed=10.0):
        self.ratio, self.tokens = ratio, float(seed)
    def record_success(self):
        self.tokens += self.ratio           # retries funded by successes
    def allow_retry(self):
        if self.tokens < 1.0:               # empty budget refuses; never negative
            return False
        self.tokens -= 1.0                  # a retry costs one token
        return True

Bottlenecks and scaling

The design has spare store throughput but a distribution problem. Every shard has 75% headroom, so the first bottleneck is not store throughput: it is that traffic is not spread evenly across keys, which every earlier number quietly assumed.

Hot keys

The first thing to fall over is a hot key: a single key receiving a disproportionate share of requests. One partner integration sending 50,000 req/s uses one client id, which hashes to one slot on one shard, so all 50,000 land there: 50,000 / 25,000 = 2x an entire shard’s provisioned throughput, and you cannot fix it by adding shards, because Redis Cluster moves whole slots and this key lives inside one slot.

Three fixes, in ascending cost:

1. Deny cache. A 150,000x reduction, but only once the client is over its limit. A whale (an unusually large customer) sitting at 99% of a very large limit is never denied, so it still hits Redis on every request.
2. Shard the counter. Split one counter into k sub-counters, each with limit L/k, assigned at random. At k = 8, L = 100, each allows 12.5, but this reintroduces the binomial fairness error, 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 per gateway sized at L/N. Dividing the limit works here precisely because a whale has thousands of connections, so its traffic really is spread across every node.

Store CPU

The second thing to fall over is store CPU under the sliding window log, which costs three commands per request, one of them a sorted-set trim, 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 same argument the memory table made. Both halves say the log is for small limits only.

Scaling levers, in order

Failure modes

This design breaks in production in ten ways. Each row has 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 that produces no error signal.

The one to watch is eviction. Every other row announces itself: 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, 100,000 / 20 = 5,000 req/s per node, protects aggregate downstream capacity (the original point) and gives up per-client fairness (the cheaper thing to lose).

Alternatives rejected

Each row names what the alternative genuinely does better, the number that rules it out here, and when you would change your mind.

Conclusion

• Name the job first. Capacity protection, fairness quota, and abuse prevention want different algorithms and disagree about what “correct” means. Abuse prevention is the only one that cannot tolerate an approximate count, and it has the smallest limits, where the cheap algorithms are worst.
• Default to the sliding window counter, and choose per rule. Two counters, one atomic script, unbiased error sqrt(L f (1-f)), 5% at L = 100, shrinking as 1/sqrt(L). Switch to the sliding window log for small hard limits (exact, ~450 bytes at L = 5), and the token bucket where a deliberate burst allowance is a product feature (the only algorithm where burst and sustained rate are separate knobs).
• One command or one Lua script, never two. INCR then EXPIRE is two commands: a lost EXPIRE locks a client out forever and leaks memory; a refreshed one never closes the window. A single script is atomic because Redis is single-threaded, cuts round trips to one, and returns Retry-After with the verdict.
• A shared counter is the only exact option, and it must fail open. Local counters over-admit by Nx; dividing the limit under-admits a persistent connection by Nx; gossip is useless against a burst. A central store costs one 0.5 ms round trip and becomes a hard dependency, so when it is down, fall open to a per-node bucket at capacity / nodes.
• The deny cache is the highest-leverage optimization: 150,000x fewer store operations against a 50,000 req/s abuser, and because it holds only denials it can never over-admit.
• A correct rejection can still take you down. A hundred thousand clients handed the same Retry-After return within 10 ms and hit 100x the design point, repeating every second. Full jitter (uniform(0, delay)) flattens it to exactly the design rate; exponential backoff alone does nothing.
• Watch for the silent failure. Key eviction under memory pressure removes live counters with no error signal: every request succeeds and the limits are simply gone.

Further reading

• Marc Brooker, “Exponential Backoff And Jitter,” AWS Architecture Blog (2015): the source of the full-jitter and decorrelated-jitter results in the retry-storm table.
• “RateLimit header fields for HTTP,” IETF (draft-ietf-httpapi-ratelimit-headers): the standard behind the RateLimit-* response headers.
• Stripe, “Scaling your API with rate limiters”: a production account of layering token buckets, load shedders, and per-endpoint limits.
• Redis documentation, the INCR command’s “Pattern: Rate limiter”: the fixed-window and atomicity patterns, with the INCR + EXPIRE pitfalls.
• Brandur Leach, “Rate limiting, cells, and GCRA”: a clear walkthrough of the generic cell rate algorithm, the leaking bucket’s counter form.

The estimation habits behind Back of the envelope are in the estimation chapter; the ring behind the key-owner alternative is in the consistent-hashing chapter. This counter lives in RAM, so the on-disk B-tree and LSM-tree internals of a database store are not what makes it fast.

One line to remember: a rate limiter is one shared counter, and every real decision here is about what that counter does at the window boundary and how it stays correct when the request that reads it costs less than the request it rejects.