Invalidation and the Stampede

Two hard problems, both on the seat map. The first: a hold commits, and the cache still says the seat is available. The invalidation has to happen after the commit, it has to be a delete rather than an update, and it has to survive being missed, because the process can die between any two lines and one of those lines is the delete. The second: at 19:00:00 the key expires, and every request that arrives before the first rebuild lands misses, queries the primary, and rebuilds the same 60 KB. On the night Marek first measured it, that took pg-primary from 10 percent CPU to 100 in one second.

The two problems pull in opposite directions. Invalidation wants the value gone the instant the truth changes; the stampede is what happens when the value is gone and 2,600 readers a second want it. Neither fix is complete without the other, and the topic ends with the seat map holding both: a delete after every commit, a TTL under it as the guarantee, one rebuilder per key, and expiries that do not line up.

Invalidate After Commit

The hold path from Chapter 6 locks the seat row, updates it, and commits. The delete of seatmap:v2:8812 goes after the commit, and the order is not a style choice. Put the delete before the commit and a concurrent read can miss, query the primary under Read Committed, see the seat still available because the hold has not committed yet, and set that map with a fresh 30-second TTL a few milliseconds after the commit lands. The delete ran; the cache is wrong anyway; and it stays wrong for the whole TTL, because nothing else will delete it.

With the delete after the commit, any read that misses after the delete queries a database in which the hold is already visible, and sets the right map. That leaves one gap: the process that commits and then dies, or times out against Redis, before the delete is sent. The old map survives, wrong, until its TTL ends 30 seconds later. That gap is why Topic 49 called the TTL the floor of correctness, and it is bounded rather than closed. Stagedoor also writes the invalidation as an outbox row in the same transaction as the hold, so the relay of Topic 41 sends the same delete a second time within 100 milliseconds of the commit; the direct delete is for speed, the outbox row is for the crash, and since a delete repeated is a delete, both can run.

Delete, Do Not Update

The write path could build the new map and set it, and it would be wrong more often than the delete. A read misses at 19:00:00.000 and starts its 8-millisecond query. A hold commits at 19:00:00.003 and sets the new map, with 14C held. The read's query, which started before the commit, returns the old rows, and at 19:00:00.009 its SET replaces the new map with the old one. The writer did everything right and the cache is wrong for 30 seconds, because the last SET wins and the last one was built first. Add a second instance and the race has more entrants; add a replica and the window grows to the lag.

A delete cannot lose that race in the same way. It carries no value, so it cannot carry an old one; the reader that set the stale map a moment before the delete has its map removed, and the next reader rebuilds from the committed rows. A delete is idempotent, so the direct one and the outbox's can both run in any order. And it is what a write path can send without knowing how the read path serializes, which is the second reason: the write path knows which key changed, and nothing about what goes in it. The residual race is the one from Topic 49, a slow read whose stale SET lands after the delete, and it is bounded by the TTL and made rare by how short the window is, a few milliseconds against 30 seconds.

The Stampede

One key, 2,600 readers a second, one expiry. At 19:00:00.000 the seat map's TTL ends. The first read after that misses and starts an 8-millisecond query; so do the next 20, because they arrived before the first one set the key. Twenty-one concurrent rebuilds of a 2,000-row join push the primary hard enough that each takes 40 milliseconds instead of 8, so 100 more readers miss, so the queries queue behind Chapter 6's pool of 20, so the rebuild takes 300 milliseconds, and by 19:00:01 every seat-map request is a query and the primary is at 100 percent. The queries were all going to produce the same 60 KB. The dashboard shows the query rate for one statement going from 3 a second to 2,600 in one second, with nothing else changed.

The fix has three forms, and they compose. A lock so that one reader rebuilds and the rest wait for its result. An early refresh so that the hottest keys are rebuilt before they expire and never miss at all. And jitter on every TTL so that keys set together do not expire together. Stagedoor puts the first and the third on every cached family, and the second on the seat maps of events that are on sale within the hour, where a single miss under 2,600 readers a second is the incident above.

Locking the Rebuild

On a miss, before querying, the reader tries SET lock:seatmap:v2:8812 with NX and EX 5: set the lock only if it does not already exist, and let it expire in 5 seconds in case its holder dies. Exactly one reader gets a positive answer, and that reader rebuilds, sets the map, and deletes the lock. Every other reader gets a negative answer, waits 50 milliseconds, and reads the key again. Since the rebuild takes 8 milliseconds on a primary that is not being stampeded, the losers find the map on their first retry, and the primary saw one query for 2,600 requests.

async def get_seat_map(svc, event_id: int) -> SeatMap:
    key, lock = f"seatmap:v2:{event_id}", f"lock:seatmap:v2:{event_id}"
    for _ in range(10):                                    # 10 x 50 ms: 500 ms, inside the budget
        raw = await svc.cache.get(key)
        if raw is not None:
            return SeatMap.from_json(raw)
        if await svc.cache.set(lock, svc.instance_id, nx=True, ex=5):   # SET ... NX EX 5
            try:
                seat_map = await rebuild_seat_map(svc, event_id)         # the one query
                await svc.cache.set(key, seat_map.to_json(), ex=jittered(30, 5))
                return seat_map
            finally:
                await svc.cache.delete(lock)
        await asyncio.sleep(0.05)                                # loser: wait, then GET again
    raise CacheRebuildTimeout(retry_after=1)                    # the rebuilder died; the lock expires in 5 s

The function reads the key, and returns on a hit as before. On a miss it tries to take the lock with a single set-if-absent command that also carries a 5-second expiry. If it gets the lock, it runs the one query, stores the map with a jittered TTL, releases the lock whatever happened, and returns. If it does not get the lock, it sleeps 50 milliseconds and goes round again, re-reading the key, up to 10 times. Everything turns on what the losers do: they wait and re-read, and they do not query, because a loser that queries anyway has made the lock decorative. After 500 milliseconds without a map the rebuilder has died mid-rebuild, and the loser gives up with an error the handler turns into a 503 and a Retry-After of 1 second, which the lock's own expiry makes true. That case has never fired in production; the ordinary case is one query and 50 milliseconds of waiting for everyone else.

Early Refresh

The lock bounds a miss to one query. Early refresh makes the hottest keys not miss. The seat map is stored with a physical expiry of 60 seconds, SET with EX 60, and a logical one of 30 written inside the value as expires_at. A reader that finds a value within 5 seconds of its logical expiry serves it as usual and starts a background rebuild: a fire-and-forget task on the loop, or for the maps that matter most a job on the stream of Chapter 8, so that it survives the instance. The rebuild sets a fresh value with a new expires_at, and under steady load the key is refreshed every 25 seconds or so and never absent. The stampede cannot form, because there is never a moment when 2,600 readers find nothing.

The 30 seconds between the logical and the physical expiry is also the "previous value" the lock's losers can serve. A loser that finds the key gone entirely has nothing; a loser that finds a value past its logical expiry but inside its physical one can serve it, stale by a few seconds, while the winner rebuilds. Stagedoor's losers do that for the seat map, and the code above is the version without it for clarity; with it, the branch that sleeps first checks for a logically expired value and returns it. The delete on the write path removes the key outright, so a hold is never served from the grace window; the window covers expiry, not invalidation.

Jittered TTLs

At deploy time a warm-up fills 2,000 event keys within the same few seconds, each with EX 30, and 30 seconds later they all expire within the same few seconds: a stampede across the fleet of keys instead of on one, 2,000 rebuilds in a burst against a primary that expected 3 a second. The fix costs one line: the TTL is 30 seconds plus a random 0 to 5, jittered(30, 5) in the code above, so that keys set together drift apart and the rebuilds spread across the 5-second window. Every family gets it, including the 60-second event list and the sales totals, because any key set at the same moment as its neighbours will expire with them.

Jitter spreads expiries that exist. It does nothing for a Redis that has just restarted empty, where there are no expiries to spread and 2,000 keys are missing at once; that is the cold start, and Topic 52 gives it a warm-up and the per-key lock as its fixes. The three mechanisms have three shapes of stampede between them: the lock for one hot key, the early refresh for the key that must never miss, the jitter for the fleet that was set together.