Rate Limiting and Backpressure

A rate limit is the service saying no before it has to say 503. This buyer may hold 10 seats a minute; this scanner key may check 50 tickets in a burst and 20 a second after that; this instance will run 20 checkouts at once and not a twenty-first. Each is a number the service chose in advance and enforces at the door, instead of a number it discovers when the pool runs dry and the acquire timeout of Chapter 6 turns a slow request into the slowest possible refusal. Chapter 2 promised the scanner app a 429 with a Retry-After, Chapter 4 drew the limiter as the ring outside authentication, Chapter 5 gave the login route its two limits, and Chapter 7 set the breaker beside a limiter it declined to build; this is the topic that builds it.

The token bucket is the algorithm, Redis is where the buckets live so that a limit is per buyer rather than per instance, 429 with a true Retry-After is the answer, and backpressure is the same idea turned around: a limit on what the service will accept from everyone, keyed on nothing, answered with 503. The two are confused constantly, and the comparison box is for the day someone proposes a 429 for a full pool.

The Token Bucket

A bucket holds at most N tokens and is refilled at R tokens a second. Each request takes one; a request that finds the bucket empty is refused. Bursts up to N are allowed, because a bucket that has been idle is full, and the sustained rate is R, because a bucket that is drained as fast as it fills yields R a second and no more. The two numbers are the whole policy. The buyer's hold bucket is N of 10 and R of one every 6 seconds, so a buyer can hold 10 seats in a rush and then one every 6 seconds; the scanner key's is N of 50 and R of 20, so a gate can scan a queue of 50 as the doors open and 20 a second after that; the login route's is 10 a minute per source address. A fixed window, 10 per calendar minute, allows 20 in the 2 seconds around the minute boundary, and a sliding log of every timestamp costs memory per request; the bucket costs two numbers per key and allows exactly what it says.

-- KEYS[1] = rl:user:8812   ARGV = capacity, refill_per_second, now_ms, cost
local capacity, rate, now, cost = tonumber(ARGV[1]), tonumber(ARGV[2]), tonumber(ARGV[3]), tonumber(ARGV[4])
local b = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(b[1]) or capacity            -- a key that does not exist is a full bucket
local ts     = tonumber(b[2]) or now
tokens = math.min(capacity, tokens + (now - ts) / 1000 * rate)   -- refill for the time elapsed
local allowed, retry_after = 0, 0
if tokens >= cost then
  tokens, allowed = tokens - cost, 1
else
  retry_after = math.ceil((cost - tokens) / rate)          -- seconds until one token exists
end
redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('PEXPIRE', KEYS[1], math.ceil(capacity / rate * 2000))   -- an idle bucket is a full one; let it go
return {allowed, math.floor(tokens), retry_after}

The script reads the bucket's two numbers, the tokens it held and the time it was last touched, adds the tokens that the elapsed time has earned up to the capacity, takes one if there is one, and writes the two numbers back. It returns whether the request is allowed, how many tokens remain, and, when it is refused, how many seconds until a token will exist, which is the Retry-After value ready-made. The clock comes from the caller as an argument, because a script that reads Redis's own clock is not a pure function of its inputs and the replica would compute a different answer. The expiry lets an idle buyer's bucket disappear, since an absent key is treated as a full one and costs nothing. And the whole thing runs as one command, which is the reason it is a script and not four calls from Python: when api-01 and api-02 both check the same buyer within the same millisecond, two clients reading, deciding and writing separately would both see 1 token, both allow, and both write 0, letting 11 holds through a limit of 10. Redis runs one script at a time, so the second sees what the first wrote. The redis-cell module does the same arithmetic as a built-in command, and Stagedoor keeps the script because it can read it.

What to Key On

A limit is a limit on whatever its key names, and the key is the design decision. The hold path is keyed on the buyer, rl:user:8812, because the thing being made fair is seats per buyer and the principal is known by the time the request reaches the hold route. The scanner endpoint is keyed on the API key's id, as Chapter 5 arranged, because a venue's ten phones share one Wi-Fi address and must not share one bucket, and an organizer's two integrations must not compete for one budget either. The login route is keyed on the source address, because there is no principal yet, and on the normalized email in the body, 20 an hour per account, because a credential-stuffing run spreads itself across a thousand addresses and one account. Only the address key is taken from the forwarded header, and only because Chapter 2 made the balancer the sole thing allowed to set it; a limiter that trusts X-Forwarded-For from anyone is a limiter one header defeats, 40 scans a second becoming 40 clients at one scan each.

A limit keyed on the wrong thing is either a limit on nobody or a limit on everyone behind one NAT. Keyed on the address for authenticated traffic, it lets the script with a thousand addresses hold every seat in the house, one seat per address, and locks out the 200 people in one office who share an address and wanted 200 seats between them. Keyed on the organizer for the scanner, it lets the tenth phone at the gate be refused during the rush because the first nine spent the budget. The principle is one sentence: key the limit on the identity whose fairness the limit is protecting, and fall back to the address only where there is no identity yet.

Where in the Rings

Chapter 4 drew one limiter ring outside authentication; on the night there are two, and their positions are the point. The per-address limiter is outside authentication, because the login route's password hash is 100 milliseconds of CPU by design and a limiter placed inside the auth ring would run after that hash rather than before it, and 1,000 stuffing attempts a second is every core on both instances doing exactly the work the limiter existed to refuse. The per-principal limiters are inside authentication, because the buyer's id and the scanner key's id exist only once the token or the key has been verified; they run as the innermost ring, with the principal in hand and before the router. Both short-circuit: a refused request returns its 429 and never reaches whatever is inside.

The two limiters protect two different things, which is why they cannot be one ring. The login limiter protects CPU: the hash is the most expensive computation in the request path and the limiter is what keeps an attacker from buying it at the service's expense. The hold limiter protects rows: the seat rows of Chapter 6 under their locks, the hold path's 300 a second, and the other buyers' share of it. One is a limit on work the service would do; the other is a limit on a resource the service would grant.

429 and Retry-After

A 429 says the caller was the reason, and the Retry-After header says when the caller may try again, in seconds, as Chapter 2 specified for every refusal the service sends on purpose. The value comes from the bucket: the script's third return is the seconds until one token exists, so a buyer who has spent her 10 holds sees Retry-After: 6 and the page says "please wait 6 seconds" instead of showing a spinner over a request that would be refused again. The mobile app and the scanner app both honour the header in their client library, waiting exactly that long and no less, and a client that ignored it would be treated by the bucket exactly as it deserves: refused again, at 200 microseconds a time, until it learned. Stagedoor also returns the bucket's remaining count in a response header on allowed requests, so a well-behaved client can slow down before it is refused at all.

A 429 without the header is a retry storm the service invited. The buyer's browser retries at once, because nothing told it not to; the retry is refused at once; the loop runs as fast as the network allows, and a limiter that was meant to reduce load has multiplied it, because every refusal is still a request through the outer rings and a Redis round trip. The header is what makes the refusal cheaper than the request would have been, and a 429 that does not carry a true one is half a mechanism.

Backpressure

Rate limits are about the callers. Backpressure is about the service, and the question it answers is what happens to the 21st checkout when 20 are already inside. Without a bound, the answer is the pool: the 21st waits for a connection behind the other 20, the acquire wait of Chapter 6 climbs, and after 5 seconds the request fails with a 503 that arrived as slowly as a refusal can. With a bound, a semaphore of 20 per loop around the checkout path, the same shape as the Payrail bulkhead of Chapter 7, the 21st fails in a millisecond with a 503 and a Retry-After of 2, and the 20 inside keep their connections and finish. Twenty of the loop's 24 connections is the bound on purpose: the other 4 are for the hold path and the seat-map rebuild, which must never queue behind checkout. The refusal is the same status code the pool timeout would have produced, delivered 5 seconds sooner, at the door instead of inside.

checkout_slots = asyncio.Semaphore(20)      # 20 of the loop's 24 connections; 4 stay free for holds and rebuilds

async def place_order(req: PlaceOrder, ctx: Ctx) -> ORJSONResponse:
    if checkout_slots.locked():                  # all 20 in use: refuse now, not after a 5 s pool wait
        metrics.shed.labels(path="checkout").inc()
        raise Overloaded(retry_after=2)             # 503, Retry-After: 2, problem type service-overloaded
    async with checkout_slots:
        return await ctx.svc.orders.place(ctx.principal, req)

The handler checks whether all 20 slots are taken and refuses at once if they are, rather than queueing on the semaphore; a queue here is the pool wait moved one layer up, and the point is to have no queue at all inside the process. The refusal is counted, because the shed rate per path is the gauge that says the bound is being hit, and it is a 503 with a Retry-After of 2 seconds, four times what a checkout takes with Payrail inside it, so that by the time the buyer returns several of the 20 slots have turned over and the header was true. Outside the handler sit the two coarser bounds: the server's limit of 400 in-flight requests per instance from Chapter 2, which sheds everything past it, and the loop lag of Chapter 1, which is the signal that the instance is behind on all its work at once. Shedding at the door, at the bound that matches the dependency, is what keeps the collapse from happening inside, where it would take every request on the instance with it.

Fairness Under the On-Sale

At 19:00:00 three limits are what "fair" means, and each catches something the others cannot. The per-buyer hold limit of 10 a minute stops one script from holding every seat in the house; a script that wants 2,000 seats needs 200 accounts or 200 minutes, and the seats it held in the first minute expire in 10. The per-organizer aggregate, 200 holds a second across all of an organizer's events, stops one hot event from taking the whole 300 the hold path serves and starving the four other organizers whose on-sales overlap it. And the waiting room of Topic 75 is the rate limit on entry to the flow itself, the one that decides how many buyers a second reach the seat map at all, which no per-principal bucket can decide because the buyers have not done anything yet. Per buyer, per organizer, per flow; a script is stopped by the first, a hot event by the second, the herd by the third.

When Redis is unreachable, all three go with it, and the decision Chapter 7 deferred to this topic is recorded here: the per-principal limiters fail open, because refusing every hold for the length of a Redis outage is a worse night than a minute without fairness; the login limiter falls back to a bucket in process memory, because the hash's CPU must be protected even at four times the limit; and the checkout bound never needed Redis at all, because it counts what this loop is doing. Fail open for fairness, fail closed for capacity, and the metrics ring counts every request that a fallback decided, so the outage is visible as a number and not as a rumour.