Lesson 13: Rate Limiting & Backpressure

Lesson 12 ended with four ways an asynchronous system can say no, and promised that the last one — slowing the sender down — would be this lesson. Rate limiting is the mechanism by which a system refuses in a controlled way, instead of accepting everything and breaking, or accepting everything and promising a six-hour backlog.

This lesson's lab runs all four rate-limiting algorithms for real on Redis, each as a Lua script. Three measurements stand out. First, with the same limit of 100 requests/second, fixed window lets 200 requests through in one second right at the window boundary — twice the limit, and that number repeated identically across all three runs. Second, writing the limiter as INCR then EXPIRE in two separate commands left 20 of 200 keys stuck with no TTL — that is, 20 users blocked forever. Third, the four algorithms barely differ in speed (p50 all around 0.08 ms) but differ more than tenfold in memory.

13.1 Who rate limiting actually protects you from

The familiar answer is "from attackers". That answer is not wrong, but it leads people to put rate limits in the wrong place. In most real incidents, what brings a system down is not a stranger but your own clients: a mobile app that just shipped a release with a retry loop and no jitter, another team's cron job firing at midnight, or an internal service retrying frantically because the service behind it is slow. Strangers get stopped at another layer (a WAF, DDoS protection); your own clients hold a valid API key and walk straight in the front door.

Three concepts get conflated constantly, while they serve three quite different purposes and usually live in three different places:

The most memorable difference is in the last column. A rate limit says no; a throttle says wait. Throttling sounds kinder, and that is exactly the trap: every slowed request still holds a connection, a thread, a slot in a queue. Lesson 1 showed what happens when a queue rises — throttling does not remove load, it converts load into latency. When you are genuinely overloaded, refusing quickly is the kinder act.

13.2 Four algorithms, and what each really costs

The four algorithms below answer the same question — "may this request go through?" — but they define the words "one second" in four different ways, and the entire difference lies there.

Fixed window's weakness gets mentioned everywhere, but nearly always as an anecdote. This lesson's lab builds exactly that scenario and counts: a limit of 100 requests per 1000 ms, firing 100 requests just before the window boundary and 100 just after it, then measuring the only number the server behind it actually cares about — the most requests that got through in any sliding 1-second window.

Fixed window's 200% is not a rare worst case — it happens every time traffic clusters around the window boundary, and that boundary is a fixed instant in the day, so clustering is very easy: cron jobs are scheduled on round numbers, and retrying clients round to the second. Worse, no parameter fixes it: the 2× is a direct consequence of the counter resetting abruptly.

A point worth stating correctly: token bucket also allows a burst — 119% in the measurement above, not 100%. Many articles present token bucket as if it "has no burst problem", which is not true. The real difference is that token bucket's burst is capped and adjustable: it is at most the bucket capacity, so if you need a flat output, lower the capacity below the refill rate. Fixed window's burst is 2× no matter how you configure it.

So why not use sliding window log for everything, given that it is perfectly exact? The answer is not speed but memory. Measured over 20,000 calls per algorithm, all four take almost exactly the same time — because what costs time is the network round trip to Redis, not the arithmetic inside:

The first four columns are practically indistinguishable; the last differs more than tenfold. That is because sliding window log has to remember the timestamp of every request still in force, so its memory is proportional to the limit rather than to the number of users: a limit of 100 costs 1,499 bytes per user, a limit of 10,000 would cost a hundred times more. With a million active users that is the difference between a few hundred megabytes and a few dozen gigabytes — which is to say, between "one Redis node" and "a Redis cluster to operate".

13.3 In a distributed system, the counter must be atomic

Lesson 3 gave the system three app replicas, and that immediately breaks the most natural way to write a limiter: keeping the counter in process memory. With three replicas, each counts separately, and the real limit becomes three times the one you configured. The counter has to live somewhere shared — but shared alone is not enough.

This is the most common limiter you will find online, and it has a serious bug:

// WRONG: two separate commands, with a gap in between
const n = await redis.incr(key);
if (n === 1) {
  await redis.expire(key, 60);   // (!) if the process dies BEFORE this line...
}
if (n > limit) return deny();

The gap between INCR and EXPIRE is small, but it is real. If the process dies right there — a deploy, an OOM kill, a CPU-throttled container that gets reaped — that key exists forever with no TTL. The counter never resets, and that user is blocked permanently until somebody deletes the key by hand. The lab reproduces exactly this with 200 users, "dying" on 1 in 10:

{
  "role": "nonatomic",
  "crashEvery": 10,
  "report": [
    { "mode": "two-commands", "keyCount": 200, "keysWithoutTtl": 20,
      "consequence": "20 users blocked FOREVER" },
    { "mode": "lua", "keyCount": 200, "keysWithoutTtl": 0,
      "consequence": "no keys stuck" }
  ]
}

The fix is to bundle the whole "read — decide — write" into one Lua script. Redis runs a complete script as a single command, so either both commands run or neither does. This is the real token bucket running in the lab:

-- A bucket of capacity `cap`, refilled steadily at `cap` per `win`.
-- There are no window boundaries at all, so there is no cliff to exploit. Bursts are
-- ALLOWED but capped by exactly the bucket capacity — the difference from fixed window.
--
-- The time comes from redis.call('TIME'), NOT from the client: many app instances call
-- the same limiter and their clocks differ. If the client sent `now`, a machine running
-- 200 ms fast would move itself into the next window early.
local cap  = tonumber(ARGV[1])
local win  = tonumber(ARGV[2])
local k    = KEYS[1]
local t    = redis.call('TIME')
local now  = t[1] * 1000 + math.floor(t[2] / 1000)
local d    = redis.call('HMGET', k, 'tokens', 'ts')
local tokens = tonumber(d[1])
local ts     = tonumber(d[2])
if tokens == nil then
  tokens = cap
  ts = now
end
local delta = now - ts
if delta < 0 then delta = 0 end
tokens = math.min(cap, tokens + delta * cap / win)
local ttl = win * 2
if tokens < 1 then
  redis.call('HSET', k, 'tokens', tokens, 'ts', now)
  redis.call('PEXPIRE', k, ttl)
  return '0|0|' .. math.ceil((1 - tokens) * win / cap)
end
tokens = tokens - 1
redis.call('HSET', k, 'tokens', tokens, 'ts', now)
redis.call('PEXPIRE', k, ttl)
return '1|' .. math.floor(tokens) .. '|0'

This runs on all three app replicas at once in the lab, behind the load balancer, with a global limit of 500 requests/second. Firing 20 connections for 10 seconds:

An error of 7 in 5,500 — that is 0.13%. That is measured evidence that a shared atomic counter really does hold a global limit, rather than the limit multiplied by the replica count.

There is one more decision as important as the algorithm: which dimension to limit on. Per logged-in user is the most precise but does not protect the login endpoint (there is no user yet). Per IP protects public endpoints but runs into NAT. Per endpoint protects exactly the expensive places. In practice you need several dimensions at once, and each is its own Redis key.

13.4 Refusing properly

Refusing is an act of communication. A refused client will do something, and what it does depends entirely on what you told it. This is the lab's real response once the bucket is empty:

$ curl -si "localhost:3001/limited?user=drain2"

HTTP/1.1 429 Too Many Requests
X-RateLimit-Limit: 500          # your quota
X-RateLimit-Remaining: 0        # how much is left
X-RateLimit-Reset: 1            # how long until it refills (seconds)
Retry-After: 1                  # WAIT EXACTLY THIS MANY SECONDS
Content-Type: application/json; charset=utf-8

{"error":"rate_limited","retryAfterMs":2}

Those four headers are the contract. Retry-After tells the client exactly when to come back — without it, the client can only guess, and the most common guess is to retry immediately, exactly what you were trying to prevent. The three X-RateLimit-* headers additionally let a client self-regulate before hitting the limit: a well-behaved SDK seeing Remaining: 3 slows itself down rather than driving into the wall.

That real response exposes a notable detail: the true wait is 2 milliseconds (the token bucket refills 500 tokens per second, so the next token arrives after 2 ms), but Retry-After is measured in seconds, so the smallest thing it can say is 1 — 500 times slower than the truth. That is why the response body also carries retryAfterMs: the header stays correct HTTP for generic clients, while a client that understands your API reads the exact number. With only the header, every refused client would wait a round second and all come back at the same moment — you would have created a synchronised wave, exactly the problem jitter exists to solve in Lesson 17.

A question that often goes unasked: what does the limiter cost? It sits on the path of every request, including the ones allowed through, so its cost adds directly to the whole system's p99. Measured by comparing the same endpoint with and without a limiter, with the limit set high enough that no request is refused (four paired runs, 20 connections, 10 seconds each):

p50 rises by about 0.04 ms — exactly one network round trip to Redis, no surprise there. The surprise is that p95 and p99 are consistently lower, across all four paired runs. A plausible explanation: /fast replies entirely synchronously so many requests are handled in clumps within one event-loop turn, while /limited has a yield point (the await on Redis) that breaks those clumps up. This is a hypothesis, not a proven conclusion — this lab does not measure event-loop delay directly, so I am recording exactly what was measured.

13.5 Load shedding: when refusal has to be selective

A rate limit answers "has this client used more than its share?". Load shedding answers a quite different question: "the system is overloaded, what do we drop?" The second question only arises when every client is within its limit and the total still exceeds capacity — and at that point a rate limit helps not at all, because nobody is violating anything.

The figures from the global measurement in section 13.3 show the first thing to know about refusing: it is not free, but it is far cheaper than serving. In 10 seconds the lab served 5,493 requests and refused 185,660 — so it handled about 18,500 refusals per second, 34 times the number of requests it actually served. That is why "fail fast" is a viable strategy: you still pay a price, but the price is an order of magnitude smaller.

But that price is only small when the refusal happens early. Refusing after you have already queried the database to check the limit means you paid almost the entire cost before saying no. The rule: the limiter must sit before everything expensive — before authentication if possible, certainly before the database.

The easiest detail to miss in that figure is the first row: health checks. If load shedding also drops health checks, the load balancer concludes the node is dead and pulls it out of rotation (Lesson 3), pushing the load onto the remaining nodes, which then start shedding too, failing their health checks too, and being pulled out too. The mechanism built to save the system becomes the mechanism that kills it. This is the form of cascade failure that Lesson 17 dissects in full.

Reproduce the measurements yourself

cd blog/sysdesign/sysdesign-lab

# --- Window boundary: same 100/s limit, count the worst 1-second window ---
./tools/ratelimit-test.sh boundary    # fixed=200 · log=100 · counter=105 · token=119

# --- Time vs memory: the 4 algorithms are near-identical in speed... ---
./tools/ratelimit-test.sh bench       # p50 all ~0.08ms (empty GET baseline: 0.073ms)
# --- ...but differ more than 10-fold in memory ---
./tools/ratelimit-test.sh memory      # log 1499 B/user vs 121-171 B/user

# --- INCR + EXPIRE as two commands: keys stuck forever ---
./tools/ratelimit-test.sh nonatomic   # two-commands: 20/200 keys with no TTL · lua: 0/200

# --- What the limiter adds to every request ---
./tools/ratelimit-test.sh overhead    # /fast vs /limited: p50 +0.04ms

# --- 3 replicas behind the LB, a GLOBAL 500/s limit, 10 seconds ---
./tools/ratelimit-test.sh e2e 500     # 5493 allowed (expected 5500) · 185,660 x 429

In summary

Rate limiting mostly protects you from your own clients, not from attackers — so putting it only at the edge leaves exactly the place where cascade failure begins uncovered.

On algorithms, the measurements give a compact conclusion: choosing an algorithm is not about speed. All four give a p50 around 0.08 ms because what costs time is the network round trip, not the arithmetic. The real differences are elsewhere — behaviour at the window boundary (fixed window lets 200% through and no configuration fixes it) and memory (sliding window log costs 1,499 bytes per user, more than ten times the other three). Token bucket also allows a burst, 119% rather than 100% — but its burst is capped and adjustable, and that is the difference worth stating.

On implementation, one rule with almost no exceptions: bundle the whole decision into one Lua script. The INCR-then-EXPIRE version left 20 of 200 keys stuck with no TTL in the measurement — 20 users permanently blocked by the very mechanism meant to protect them. In return, a shared atomic counter holds the global limit very tightly: 5,493 against an expected 5,500, with three replicas that never talk to each other.

And on how to refuse: 429 with Retry-After, never 5xx. Refusing is about 34 times cheaper than serving in this lab — but only when it happens early, and only when it is selective. Shedding uniformly is a reliable way to break the SLO of your most important group.

Lesson 14 changes direction: instead of storing the current state and overwriting it continuously, we store the sequence of events that happened and recompute the state from it. That opens up the ability to replay history to find a bug — and it requires something from Lesson 11 as a precondition: idempotency.