Caching & Invalidation

Part 0. Start here

The problem: one price change and 12,000 page views a second

A shop's product reads go through a Valkey cache in front of a PostgreSQL read replica. At 20:00:00 a marketing email reaches 2 million people: the kettle k7 is on flash sale, $49 →$39. The price is changed in the database at 20:00:00.000. By 20:01, 12,000 page views a second reach k7's page, on top of 20,000 product reads a second for the rest of the catalog. The 12,000 is the number in the drill The Product Page That Melted Redis.

Two numbers make the problem felt.

The load. The replica answers at most 1,000 product queries a second (our example's number). Every read the cache doesn't answer becomes a query:

At 99%, losing one point of hit ratio doubles the database's load, losing three points quadruples it, and an empty cache sends 32 times what the replica can answer.

The freshness. Nothing in the chain is told that the price changed, except by whoever changes it. If the page's origin sends no Cache-Control header, a CloudFront cache policy's default TTL is 86,400 s, one day, and every browser keeps its own copy on top. In our story the app deletes the cache entry 5 ms after the commit, and the page still shows $49 for ten minutes, to about 6.8 million page views. A read that missed 6 ms after the delete refilled the cache from a replica that was 200 ms behind.

The big picture

Synthesizing vector architecture diagram...

What to notice: the read replica follows the primary's log, so it has a subscription and its staleness is its lag. Valkey, the shield, the edges and the browsers have none: the crossed dashed lines are the messages that nobody sends. Each copy is fresh only because it expires (its TTL) or because someone deletes or overwrites it.

What you'll be able to do after this page

1. Explain why a cache is load-bearing, turn a hit ratio into database load, and say what a TTL costs in misses (Part 1).
2. Compare cache-aside, read-through, write-through, write-behind, refresh-ahead and a stream-fed copy on equal terms (Part 2).
3. Explain the race that puts an old value back after a delete, and close it with versions or leases (Part 3).
4. Choose where invalidations come from: the app, the change stream, a new key per version, or only the TTL (Part 4).
5. Stop stampedes and avalanches with jitter, one fill per key, stale-while-revalidate and early refresh (Part 5).
6. Cache "absent" correctly, and say why it doesn't stop enumeration attacks (Part 6).
7. Size a cache from its working set and pick an eviction policy (Part 7).
8. Survive a dead cache node and a cold restart without taking the database down (Part 8).
9. Give a writer read-your-writes through a cache, invalidate a second Region safely, and use DAX without surprises (Part 9).
10. Set Cache-Control, build a cache key, add up the staleness of every HTTP tier, and choose between a purge and a versioned URL (Part 10).
11. Trace one page view and one price change through every layer (Part 11).
12. Map all of it to AWS services, and name the look-alikes that aren't caches (Part 12).

You may have arrived from a step that relies on this: step 1.5 of the URL shortener loop (a disable overwrites the entry, and refills use SET NX), step 2.2 of the news feed loop (the DAX query cache that writes don't invalidate), step 2.1 of the hotel reservation loop (a change-stream-fed cache that applies only newer versions) or step 1.1 of the Shopify case study (a version in the cache key, so nothing is deleted key by key). This page is the "why" behind all four, and behind about thirty other loop steps that put a cache in the path.

---

Part 1. What a cache is, and why the database now depends on it

The catalog gets 20,000 product reads a second, and the replica takes 1,000. Without a copy of the answers somewhere cheaper, the shop can't open. So we keep one, and from that moment the database's health depends on how often that copy answers.

A copy with no subscription

A cache holds copies of answers the database already gave. The database doesn't know the copies exist, so it can't tell them when a row changes. A copy becomes fresh again in only two ways:

• it expires: its TTL (time to live) runs out, and the next read fetches a new copy;
• someone invalidates it: deletes it or overwrites it after a write.

A few more words used on this page:

The read path and the write path

The default design is cache-aside: the application talks to the cache and to the database itself.

textCopy
READ(k)                                   (cache-aside)
  1. v = GET product:{k}
  2. hit  -> return v
  3. miss -> v = query the source (here: the read replica)
             SET product:{k} v EX 600
             return v

WRITE(k, new value)
  1. commit the change in the database (the primary)
  2. THEN invalidate product:{k}           (never before the commit; Part 3 decides
                                            what "invalidate" must write)

A miss costs three trips: the cache, the database, and the cache again.

Hit ratio and the database

The database only sees the misses. Formula 1:

$$\text{database queries per second} = \text{reads per second} \times (1 - \text{hit ratio})$$

That is the hook's table. Because the database is sized for the misses, a small drop in hit ratio is a large rise in its load: at 32,000 reads a second, 99% means 320 queries, 97% means 960, and 96% means 1,280, already over the replica's 1,000.

What a TTL costs in misses

A key read at rate λ is cached for one TTL after each miss, and then waits on average 1/λ for its next read, which misses. So it misses once every TTL + 1/λ seconds. In words: each key that is read costs at most one miss per TTL, and a hot key (many reads per TTL) costs almost exactly one. So the misses a second are at most the number of distinct keys read in one TTL ÷ the TTL.

For our catalog (event 1, from the reference implementation):

• The bound: 100,000 keys ÷ 600 s = 167 misses a second at most.
• The exact steady state, summing each key's 1 ÷ (TTL + 1/λ): 159 misses a second, a hit ratio of 99.2%, 16% of the replica. Cold products read less than once per TTL cost less than one miss per TTL each.
• At 19:59 the 10,000 most popular products were loaded by a job at 19:55 and none of them is due before 20:04, so only the others miss: 142 a second (14% of the replica).

Halving the TTL roughly doubles the misses of the keys that are read often; it can't more than double them.

Why not more read replicas instead?

Each replica adds about 1,000 queries a second, and each must apply every write (the Replication, Quorums & Read-Your-Writes loop primitive). At 32,000 reads a second with no cache, that is 32 replicas. With a 99% cache it's one. A cache turns a read-capacity problem into a memory problem: keep the working set in memory. The price is the rest of this page: staleness you must bound, and a database that can't survive the day the cache is empty.

Why not cache it forever?

The drill's second question asks exactly this. "Cache the whole catalog forever" means a changed price is invisible until something deletes the entry, and Part 3 shows how a delete can be undone by a racing refill. The TTL is the last bound on every invalidation you missed. With no TTL, a missed one is never repaired.

The example we follow

Our shop is small enough that each layer's arithmetic fits on a line; the numbers are smaller than a big shop's. Every trace on this page comes from running a private reference implementation of this shop, not from working by hand.

The overload model decides the overload numbers. Whether a query whose reader has gone still runs, and whether a late answer still writes the cache, changes the result completely. Every overload number on this page (Parts 5 and 8) uses the model in the table.

Snapshot S1, at 19:59:10, from the reference implementation:

The story has twelve beats, each in its own Part: the cache is load-bearing (Part 1); the same price change under five patterns, on a copy (2); the price changes and the old price comes back (3); an invalidation gets lost (4); a batch of keys and then k7 expire under load (5); a deleted product keeps being asked for (6); the cache shrinks, on a copy (7); a cache node dies (8); the merchandiser and the second Region (9); back to 20:00 at the edge (10); one page view and one price change, end to end (11); and on AWS (12). Replays marked "on a copy" run a what-if without changing the main timeline. The full event table is in Part 13.

Background reading, not relied on for any fact here: Primitive #04: Distributed cache patterns and eviction.

---

Part 2. Five ways to put a cache in the path, and one alternative

The price changes. Who updates the cache: the code that writes the database, a library, the cache itself, or nobody? Where the cache sits in the write path decides what can go wrong, so we replay the 20:00:00 change on a copy under each design.

Two writers cross

Take write-through: every write goes to the database, then sets the cache to the new value. It sounds like "the cache is never stale". Now two writers change k7 at nearly the same moment: the merchandiser's $39 (v8) and a correction to$38 (v9) ten milliseconds later. Writer 1 is slowed down on its way to the cache.

Side row P2, from the reference implementation. The database says $38 and the cache says$39 until the TTL, at 20:10:00.018. With a version compare on the cache write ("only if the stored version is lower"), writer 1's v8 is refused and the cache keeps $38 v9.

Synthesizing vector architecture diagram...

What to notice: in "Cache-aside" and "Write-through" the database is written first and stays the truth; the cache follows. In "Write-behind" the order is reversed: until step 2 the cache is the only place that knows the new price.

Six designs on equal terms

Check the rows from both sides. Write-through doesn't help a cold key's first read (nobody wrote it), and costs memory for keys nobody reads. Cache-aside adds almost nothing to write latency (one delete), and keeps the cache small. Refresh-ahead helps reads of hot keys (Part 5 makes it self-tuning with XFetch), not freshness after a write.

Write-behind: the cache is the truth until it flushes

Write-behind turns the cache into the source of truth until the next flush. Replayed for the price (side row P3): until the flush, the database still says $49, so checkout (which reads the database) charges$49; and if the cache node is lost before the flush, the price change is lost with it. So we use write-behind only for data we can lose or rebuild. In our shop that's the "trending" counter views:{k7}: one increment per view in Valkey, flushed every 10 s (Part 8 counts what a node failure loses).

A complete copy fed by the stream

Several loops don't use a cache at all where a missing key would be ambiguous. They keep a complete copy that an updater writes from the change stream, every row present, applied only if newer: the proximity service (step 2.1), the digital wallet (step 2.4) and ad-click aggregation (step 2.1). Its lag is the stream's lag, and a missing key means "doesn't exist", which a cache can never say. The updater itself is the cache updater of the Change Streams & the Transactional Outbox loop primitive. DAX, AWS's cache for DynamoDB, is a managed write-through item cache; Part 9 has its details.

---

Part 3. The race that leaves a stale value for good

The price changed at 20:00:00.000, and the app deleted the cache entry 5 ms later. Yet the page shows $49 for ten minutes. A delete leaves nothing behind, so a refill that read the old price can land after it, and nothing stops it.

Trace: the old price comes back

From the reference implementation (the naive design: DEL after commit, plain SET on refill; k7 still at its pre-sale 236 reads a second):

Checkout still charges $39, because it reads the primary. That's the rule the drill's gold answer depends on: the cache decides what is shown, never what is charged. Money, stock and permissions are decided against the source.

Snapshot S2, after event 4:

Synthesizing vector architecture diagram...

Snapshot S3, from the reference implementation. What to notice: the delete comes first and the stale SET second. At .200 the replica is right and the cache is still wrong, and nothing will tell it. (Three more fills repeat the same SET by .045.)

Race B: the lagging source

What we just saw. A fill that starts after the delete reads a copy that is behind (a replica, or another Region's copy), so it gets the old value and stores it after the delete. Reading the primary instead would close this race.

Race A: the slow reader

A fill that read the primary can be stale too, if it read before the commit and stored after the delete. Side row 6a, on a copy where k7's entry had expired at 19:59:59.985:

Reading the primary closes race B, not race A.

What the refill can see

Three ways to write the invalidation and the refill, each replayed on both races (side row 6b, from the reference implementation):

(iii) closes both races for one writer. Two writers can still cross, exactly as in P2: their overwrites arrive out of order, unless the overwrite compares versions. SET NX protects a value the write path wrote, not a key the write path deleted.

Two more ways people try, both side rows in Part 13:

• Delete before the commit (6c): the delete at 19:59:59.995 lets a reader miss at .997 and read v7 before the commit; its SET lands at 20:00:00.018, after the commit: stale until the TTL. Always invalidate after the commit.
• The delayed double delete (6d): delete again 500 ms later. It fixes event 5: the stale fills landed by .045, the second delete at .505 removes them, and the next fill reads the replica, which has had v8 since .200. It doesn't fix a reader paused for 1 s: its SET lands at 1.010, after the second delete. It narrows the window by a guess; it doesn't close it. The news feed loop uses it (step 3.2) with a 60 s TTL behind it.

Why does anyone delete at all? The memcache paper from Facebook says it plainly: "We choose to delete cached data instead of updating it because deletes are idempotent." A delete can be repeated and reordered safely. The paper then adds leases to order the refills, which is Fix 2 below.

Fix 1: versions on both sides

Every row already has a version from one authority, the database. The invalidation writes a tombstone carrying the new version. Both the invalidation and every fill are compare-and-sets, so nothing older ever replaces something newer:

textCopy
INVALIDATE(k, v)                          after the commit returned version v;
                                          one server-side script, atomic
  cur = product:{k}
  if cur holds version >= v                 -> do nothing (a newer write already got here)
  else write TOMB(v) with a TTL of 60 s
  (60 s > the slowest fill + the worst replica lag a fill can read)
  or, equally: write (new value, v) under the same compare

FILL(k, value, v')                        one server-side script, atomic
  cur = product:{k}
  if cur is empty                           -> store (value, v'), TTL 600
  if cur is TOMB(t) and t <= v'             -> store (value, v')
  if cur is a value with version < v'       -> store (value, v')
  else                                      -> refuse
  (a refused filler re-reads the primary, or serves its value once, marked stale)

Valkey's SET has NX, XX, IFEQ and IFNE (set only if the current value equals, or doesn't equal, a given one), but no "only if newer". A version compare needs a short server-side script. The nearby friends loop (step 1.2) keeps the version in a separate key and uses WATCH/MULTI/EXEC: a refill writes only if the version didn't change while it ran. That stops the slow reader, but not a refill that starts after the change and reads a lagging copy, so those refills must read the source.

Event 7 replays events 3 to 6 with Fix 1 (from the reference implementation):

Twelve fills were refused in all (every reader that missed before .053), each followed by a primary read: 24 queries instead of 4. The last read that got $49 from Valkey was at .004, before the tombstone. The stale window shrinks to the responses already in flight. Race A is refused the same way (A5's v7 meets `TOMB v8`). Two writers can't cross either, **because the invalidation compares too**. Side row 7c, from the reference implementation: writer 1 commits$39 v8 at .000 and writer 2 commits $38 v9 at .010; writer 2's TOMB v9 lands at .012 and writer 1's TOMB v8, delayed, at .018; at .205 a reader reads the replica, which has v8 but not yet v9 (it applies v9 at .210), and its fill lands at .226.

TOMB v8 is this page's invalidation marker: "version 8 exists; don't store anything older". The Change Streams & the Transactional Outbox loop primitive (Part 8) stores GONE@6 for a deleted row. Same shape, different meaning, and the same lesson: caches must store something, so a late refill can't bring the old value back.

Fix 2: leases

The memcache paper introduced leases "to address two problems: stale sets and thundering herds". On a miss, the cache hands the client a 64-bit token bound to the key. A delete of the key voids its tokens, and a SET with a void token is refused.

Leases close the slow reader, not the lagging source. The paper says as much for its own replicas: "A cache refill from a replica's database should only be allowed after the replication stream has caught up." So with leases, fill from the primary, or invalidate only after the copy you fill from has the write (Part 4). (A lease here is a cache mechanism, not the ownership lease of the Leases, Fencing Tokens & Distributed Locks loop primitive.)

The TTL is the last bound

With no TTL at all (side row 7b), event 5's $49 v7 would stay until an eviction or the next price change. Every fix above has rare holes; the TTL is what bounds them.

Every write-path option on equal terms

The eviction column needs no event: a marker is evicted between the write and a stale refill only under memory pressure, and the TTL bounds it. A lost invalidation is Part 4's subject.

---

Part 4. Where invalidations come from

Fix 1 needs someone to write the tombstone after every commit. From 20:02:00 the team turns Fix 1 on by a flag (the stale k7 entry from event 5 is already stored and stays). One minute later, the app's own invalidation gets lost.

Trace: the invalidation that timed out

k30003 is on shard B too (slot 5,231). It's the 30,003rd most popular product: one read every 18 seconds, and it wasn't pre-warmed. From the reference implementation:

The old price was served for 607 s: the rest of the entry's TTL, plus the wait for the next read. The app's invalidation is a second write after the commit. A timeout, a crash or a deploy between the two loses it, and nothing notices.

Sources on equal terms

We run the combination. The app's tombstone stays as the fast path; the stream is the guarantee; the TTL is the bound.

Synthesizing vector architecture diagram...

What to notice: three paths write the same marker. The dashed app path is fast but can be lost; the primary's stream is retried until it lands; the replica's stream acts only after the copy that fills read has the write. The TTL bounds whatever all three miss.

A repeated tombstone is harmless: it's an absolute write, not an increment, so applying it twice leaves the same state, and the compare turns an older, replayed tombstone into a no-op (the Idempotency & Effectively-Once Processing loop primitive, Part 5). From 20:04:00 the CDC invalidator runs in the main line. It and the app's fast path write through the same compare-and-set script, so whichever lands second, or a replay hours later, can't put an older version over a newer one.

Invalidate from the copy you fill from

An invalidator that tails the replica's change stream acts only after the replica has applied the change. Replayed for k7 at 20:00 with no versions at all (side row 8b, from the reference implementation): the replica applies v8 at .200 and its invalidator deletes the key at .250. Event 5's stale fills (landed by .045) are deleted then, and the next miss reads the replica, which has v8: $39 v8 is stored. Race B is closed by ordering, without versions.

Race A is not. A reader that read the replica at .190 (still v7), paused 70 ms and stored at .260 lands after the .250 delete. The versioned fill still closes that one. This ordering rule is the memcache paper's own ("A cache refill from a replica's database should only be allowed after the replication stream has caught up"), and it's why the Figma case study's invalidator tails one replication stream per shard.

A new key per version

Some caches avoid invalidation entirely: the key names the version. The rendered page for k7 is cached as page:{k7}:v7; readers learn the current version from a small pointer ver:{k7} that they cache for 1 s (labelled). Side row 8d, from the reference implementation:

There is nothing to invalidate and no refill race, since a refill of v7 writes a key nobody asks for any more. The cost: every bump is a cold key, a pointer read on every request, and the pointer is itself a cached value with a staleness bound. The Shopify case study (step 1.1) puts a shop version in every page key, so a shop-wide edit is a cold cache for that shop (Part 8); notifications (step 1.5) key templates by version and never invalidate them.

The invalidator's lag is your staleness

Side row 8c, on a copy: a bulk import changes 50,000 prices at 20:04:00 in 20 s, 2,500 a second. The invalidator writes 1,000 tombstones a second (labelled), so a backlog builds, and the last change waits 50,000 ÷ 1,000 − 20 = 30 s for its tombstone. While the lag lasts, it is the staleness; the TTL still bounds it. So alarm on the invalidator's lag, and keep the tombstone TTL (60 s) longer than the slowest fill plus the worst replica lag a fill can read. The stream itself (ordering, retention, poison records) is the Change Streams & the Transactional Outbox loop primitive's subject, Parts 3, 4 and 6.

---

Part 5. Stampedes: when a hot key or a batch of keys expires

A cache protects the database only while it answers. Misses don't come evenly: they come in herds. Many keys can expire in the same second, or one very hot key can expire under thousands of readers. First, a herd that the team saw on a copy, which is why the main line's pre-warm job uses jitter.

Many keys at once: the avalanche, on a copy

Side replay 14: the same 19:55 pre-warm job without jitter. All 10,000 keys get TTL 600 and expire together at 20:05:00. They carry 81% of catalog reads, so at 20:05:00 misses arrive at about 16,200 a second (0.81 × 20,000) against a replica that answers 1,000. The hottest keys are refilled in the first few tens of milliseconds, so the first second counts 8,243 misses. Under the overload model (a FIFO queue, queued queries whose reader has given up dropped before they run, late answers don't fill, one retry), from the reference implementation:

The replica keeps working at 1,000 queries a second, but from the third second every answer arrives after its reader gave up. The FIFO queue always holds about a second of requests, so the query at its head is always about to time out: it runs, finishes late, and its fill is thrown away. Over the minute after 20:05:01 the replica ran 59,000 queries and only 80 were answered in time. Just 644 of the 9,999 keys got refilled, so misses never fall: useful work collapses to near zero and stays there until something sheds load. That mechanism (timeouts, retries, shedding) is the Retries, Timeouts, Backpressure & Load Shedding loop primitive's subject (coming). This page keeps the cache's side: cap the fills, fail fast, serve stale.

Two words for two herds:

• Avalanche: many keys, one moment (a batch filled together expires together, or a node dies).
• Stampede (thundering herd): one key, many readers at the moment it expires.

Jitter, the main line

The main line's pre-warm (event 13) gave each key a TTL of 600 s ± 10%, 540 to 660 s. Their expiries spread from 20:04:00 to 20:06:00: 10,000 ÷ 120 s ≈ 83 extra fills a second. From the reference implementation, the replica averaged 225 queries a second (at most 263) over those two minutes, with no queue and no timeouts. Jitter spreads many keys expiring together. It does nothing for one hot key: that key still expires, once, under all its readers.

Trace: k7expires under 12,000 reads a second

Event 5's stale entry expires at t₅ + 600 s = 20:10:00.045. k7 now gets 12,000 reads a second, and nothing collapses them (the protection flag comes at 20:10:05). From the reference implementation:

The stampede is also the moment the price finally becomes right: $39 v8 replaces ten minutes of$49.

Synthesizing vector architecture diagram...

Synthesizing vector architecture diagram...

Snapshot S4, from the reference implementation. What to notice: about 230 queries are sent in the first 21 ms and the queue then drains at 1,000 a second for about 270 ms. With one fill per key the same expiry costs 8 queries (one per server) or 1.

One fill per key

Single-flight and the micro-cache are the Sharding, Hot Keys & Rebalancing loop primitive's tools for one hot key (Part 4): one fetch per process, everyone else waits for it, and a short cache in front. Here they are one row of the comparison.

A lease (Part 3's mechanism) is single-flight across the whole cluster. The memcache paper's servers "return a token only once every 10 seconds per key"; a client refused a token waits a short time and retries, and "typically, the client with the lease will have successfully set the data within a few milliseconds". The paper reports the effect on keys prone to herds: "Without leases, all of the cache misses resulted in a peak database query rate of 17K/s. With leases, the peak database query rate was 1.3K/s." One risk: a lease holder that dies makes the others wait up to the 10 s token interval, unless they can take a stale value.

Serve stale, refresh once

Stale-while-revalidate keeps an entry past its soft expiry: readers get the stored value while one refresh runs.

textCopy
READ(k)                  main line from 20:10:05: leases + stale-while-revalidate
  1. e = GET product:{k}          (value, version, soft expiry; hard TTL = soft + 60 s)
  2. e is a value and now < e.soft_expiry  -> serve e
  3. e is a value (hard TTL not up)        -> serve e; if we get the lease, refresh in the background
  4. no e (a tombstone counts as no e):
       we get the lease           -> fill (compare-and-set, Fix 1), serve
       someone else holds it      -> wait 5 ms, go to 1 (until the request's own timeout)

The memcache paper does the same after a delete: it hands out the deleted value "marked as stale" to readers that can use it.

Refresh before it expires

A hot key could be refreshed a little before it expires, by one reader, while everyone else keeps hitting. XFetch (Vattani, Chierichetti and Lowenstein, "Optimal Probabilistic Cache Stampede Prevention") does it with no scheduler and no coordination. Each read recomputes early if Formula 2 holds:

$$t_{\text{now}} - \Delta \cdot \beta \cdot \ln(\text{rand}()) \;\ge\; t_{\text{expiry}}$$

where Δ is how long the last recompute took (20 ms here), β = 1 is the paper's default, and rand() is uniform in (0, 1], so −ln(rand()) is 0 or more, usually around 1, rarely much larger. Each read pretends it's a little later than it is. A key read 12,000 times a second has many reads in its last 100 ms, and one of them fires; a key read once a second almost never fires. The rule scales itself: hot keys refresh early, cold keys just expire.

The fixes on equal terms

The main line from 20:10:05 runs leases, stale-while-revalidate, jitter on every fill, and fail fast with capped fills (Part 8), by a flag (event 16).

Drill 01, question 1: a restarted cache

The drill asks why a restarted, empty cache melts the database. It's a stampede on every key at once: each key's first readers all miss together. One fill per key (single-flight or a lease) turns that into one query per distinct key requested, which is still far more than the replica takes in the first seconds. Part 8 does that capacity math.

Why didn't k7's herd grow here? The replica was nearly idle at 20:10:00, so the first query found a free connection and landed in 21 ms. If the replica is already busy when a hot key expires (Part 8), the first fill waits in the queue, the window stays open longer, more readers miss, and the herd feeds itself into timeouts and retries.

---

Part 6. Negative caching: the keys you don't have

A cache normally stores what exists. A key that doesn't exist misses every time, and every miss is a query. The email links to a product that was deleted yesterday.

Trace: a deleted product in an email

k9 was deleted yesterday, and the email still links to it: 500 reads a second (labelled). Side replay 17, on a copy without leases, and the main line (from the reference implementation, one minute):

Negative caching gives the lease's protection without a lease server, and it gives every reader an answer.

A create must replace a cached "absent"

Side row 17b: at 20:11:20 a probe for k12 (not yet created) caches "absent" until 20:12:20. k12 is created at 20:11:30. If the create doesn't invalidate it, readers are told "no such product" until 20:12:20: 504 reads at 10 a second (labelled), from the reference implementation. With Fix 1 it's automatic: the create writes k12 version 1, and "absent" counts as version 0, so it loses. A create is a write like any other.

Random keys never repeat

Side row 17c: a bot asks for 300 random ids a second (30% of the replica, labelled). Nothing repeats (the reference implementation drew 18,000 ids in a minute and saw no repeat), so negative caching stores 300 × 60 = 18,000 useless "absent" entries a minute, which take memory, and still sends 300 queries a second. Enumeration is stopped before the cache: validate the id's format, limit each client (the Rate Limiting loop primitive, coming), or keep a filter of the ids that exist (a Bloom filter) where the id space is known.

---

Part 7. Sizing and eviction

The main line's cache holds the whole catalog. Then the next budget review halves the cache. What does that do to the database? Side replay M, on a copy: the same 20,000 reads a second, with memory for fewer entries.

Working set and hit ratio

When memory is full, the cache must evict an entry for every new one, and which one it evicts decides the hit ratio. From the reference implementation (eviction only, no TTLs; the sampled policies work as Valkey does, described below):

Exact LRU gives the same as sampled LRU to within half a point (73.8%, 81.2%, 91.8%). Every size below the whole catalog puts the replica over its 1,000 ceiling. Formula 1 is the whole argument: a cache sized for "most" of the working set still sends the database more than it can take.

Synthesizing vector architecture diagram...

What to notice: the curve flattens slowly. Going from half the catalog to all of it moves the hit ratio from 91.5% to 99.2%, and the replica's load from 1,690 to 159 queries a second.

LRU, LFU and scans

• LRU (least recently used) evicts the key read longest ago. Under skew, a cold key that was just read once pushes out a warm key that is read every few seconds.
• LFU (least frequently used) evicts the key read least often. It keeps more of the hot set: 78.7% against 74.2% at 10,000 entries.

Valkey approximates both by sampling. It doesn't keep a list of every key in order. On each eviction it samples a few keys (maxmemory-samples), keeps the best candidates in a small pool, and evicts the best one. ElastiCache's default is 3 samples ("By default, Redis OSS chooses 3 keys and uses the one that was used least recently"); open-source Valkey's valkey.conf uses 5. In the reference implementation 3 or 5 samples changed the hit ratio by less than 1 point. Sampling, and a logarithmic counter that makes many keys look alike, keep the sampled LFU below the best possible 81%.

Scan pollution (side row M2): a nightly job reads all 100,000 products once, in 10 s, through the cache (misses fill it), with memory for 50,000. From the reference implementation, the normal traffic's hit ratio (a separate run with its own random draws, so its "before" figures differ from M1's by a few tenths):

Under LRU the scan's one-off keys push out part of the hot set, and the hit ratio dips for about 20 s. Under LFU a new key starts with a small counter, so the scan's keys are evicted first. The fix is to keep the job out of the cache: it reads the replica directly, throttled. The job's own misses are replica queries too: about half of 10,000 a second would be 5 times the replica.

Eviction policies

The defaults differ, so check yours: ElastiCache's default parameter groups use volatile-lru; open-source Valkey's valkey.conf uses noeviction.

Side row M3, from the reference implementation: under volatile-lru, a developer's keys written with SET and no EX have no TTL, so nothing is evictable. With memory for 1,000 entries, the 1,001st write and every one after it fails with an out-of-memory error (200 of 1,200 in the run). Keep sessions, locks, counters and dedup keys out of a cache cluster; they need noeviction in a cluster of their own.

Usable memory is less than the node's. ElastiCache reserves memory for background work: reserved-memory-percent defaults to 25%, so on a node with 13.5 GB, "the maxmemory is about 10.1 GB". Tombstones and "absent" entries count against it too.

---

Part 8. When the cache is empty: failover, cold starts and warming

The database was sized for a 99% hit ratio. At 20:15:00, in the middle of the sale, shard B's node fails. It holds k7 and 22.7% of the catalog's reads, and it has no replica.

Trace: shard B dies during the sale

The main line already runs the 20:10:05 flag: fail fast, with capped fills (18a below). First, what the naive app would have done.

Cache error is not a miss, on a copy

Side replay 18x: the same failure with the naive rule "cache error = miss: read the database". Every shard-B read goes to the replica: 4,539 catalog reads plus all of k7's 12,000 = about 16,500 reads a second, 16.5 times the replica's ceiling, on top of the other shards' fills. Under the overload model, from the reference implementation:

The other shards' top keys were expiring for the second time between 20:14 and 20:16 (they were refilled 20:04 to 20:06 with a plain 600 s TTL). Once the replica stops answering in time, each of those keys fails to refill and keeps missing, so the load grows past 42,000 queries a second. Over the two minutes: about 4.9 million queries sent; the replica ran 119,983 of them, and 1,060 (0.9% of the queries it ran) came back in time. About 2.4 million readers failed after their retry, on all four shards: a cache outage on one shard became a database outage for the whole shop. Retries doubled the offered load; how retries and shedding should work is the Retries, Timeouts, Backpressure & Load Shedding loop primitive's subject (coming). A busy replica is also where a single hot key's herd grows by itself: its first fill waits in the queue, so more readers miss.

Cap the fills

textCopy
READ(k) on app server s                    main line from 20:10:05
  1. GET product:{k} with a short timeout
  2. the cache errors (the node is down):
       a. last_known[s][k] is younger than 5 s        -> serve it
       b. a fill for k is already in flight on s      -> wait for that one
       c. fewer than 2 shard-B fills are in flight on s
                                                      -> fill from the replica, keep it in last_known, serve
       d. otherwise                                   -> a degraded page ("price unavailable"); no query
  3. never retry the cache in a loop; never send the database an uncapped read

connection budget: 8 servers x 2 = 16 of the replica's 20 connections for shard B,
leaving 4 (200 queries a second) for the other shards' misses

last_known is each app server's in-process copy of what it read recently, kept 5 s. Event 18a, the main line, from the reference implementation:

Over the two minutes, shard B's 515,126 catalog reads were served 44% from last-known copies, 16% by capped fills, and 40% got a degraded page. k7 hardly noticed: every server reads it 1,500 times a second, so its last-known copy is always fresh (99.5% served from it, 0.1% degraded). The fills ran at about 670 a second, not the full 800: a server's slot often sits idle for a few milliseconds between reads that need it. The replica stayed at about 800 queries a second with no timeouts, and the other shards' fills (about 170 a second at 20:15, their top keys' second expiry included) never noticed. The CDN keeps serving /p/k7 from its copy under stale-if-error (Part 10, event 28).

Trace: back, empty

At 20:17:00 the node returns with nothing in it. Every shard-B key misses. With leases (one fill per key) and the same cap, from the reference implementation (event 19; hit ratio of shard B's catalog reads):

The hit ratio is back above 99%, and stays there, from 20:18:40: 100 s after the node returned. k7 was filled once in the first milliseconds; its other readers waited on the lease a few milliseconds.

Synthesizing vector architecture diagram...

Snapshot S5, from the reference implementation: the fills that would be needed if every fill succeeded at once. What to notice: the bars stay above the 1,000-a-second line (the replica's ceiling) for the first three seconds, which alone need 4,398 fills, and drop below it from second 3. The capped run in the table above takes them at about 670 a second and serves the rest from last-known copies or a degraded page.

Warming

Warming rules: pre-load at a capped rate, most popular first; and when a deploy changes the key format, roll it out gradually or read the old key on a miss, because a new key format is a cold cache for every key.

A replica keeps it warm

Side row 19b: with one replica per shard and Multi-AZ on, ElastiCache "promotes the replica with the least replication lag to primary. Writes can resume within seconds." Shard B keeps its keys; the hit ratio stays near its 99.2%; nothing above happens. The cost is one more node per shard. A cache replica is for warmth, not durability: Valkey replication is asynchronous, and AWS says "when a primary node fails over to a replica, a small amount of data might be lost due to replication lag". For a cache that lost data is not just values. It includes invalidations.

What a failover loses

Write-behind data is lost too (event 20, in the main line, with no replica): views:{k7} was last flushed at 20:14:50, so the node failure loses the increments since then, 119,465 views in the reference implementation. That's acceptable only because a trending count can be off.

ElastiCache's durability mode for Valkey 9.0 and later changes this: "synchronous writes ensure zero data loss, while asynchronous writes may lose up to 10 seconds of uncommitted data". That is a durable store's job; the Replication, Quorums & Read-Your-Writes loop primitive covers the trade-off.

---

Part 9. Consistency: your own writes, other Regions and DAX

We rewind to 20:00:00 and follow the same price change through the people and places that read it. The first is the person who made it.

Trace: the merchandiser can't see her price

Had the second save written v9, the app's delete would have cleared the stale entry by luck, and the next refill would have read the replica, which has had v8 since .200. Nobody should rely on that.

Read-your-writes through a cache

The writer knows the version its write produced, so it can ask for "at least that version". This is the position token of the Replication, Quorums & Read-Your-Writes loop primitive (Part 4), applied to a cache:

textCopy
SAVE(k, fields)           returns the committed version, here 8

PREVIEW(k, at_least = 8)
  1. e = GET product:{k}
  2. e is a value with version >= 8          -> serve it
  3. otherwise (older, a tombstone, or empty) -> read the PRIMARY (20 ms) and serve it;
                                                  a fill, if any, is a compare-and-set
  the response: Cache-Control: private, no-store
  under a CDN cache behaviour whose minimum TTL is 0 (Part 10 says why)

The preview costs one primary read per request, which is fine for a merchandiser and far too much for 12,000 viewers.

Trace: the second Region

eu has its own app servers, its own Valkey, and a cross-Region replica 1 s behind. The home Region broadcasts each invalidation to eu, where it arrives in 80 ms.

Synthesizing vector architecture diagram...

What to notice: the invalidation reached eu 920 ms before the data did, so the first refill after it read the old price. The fix makes the invalidation wait for the data: eu invalidates from its own replica's stream.

The memcache paper ran one invalidation daemon per database for the same reason ("mcsqueal"), and for a writer's own reads it added a remote marker: the writer sets a marker in its Region before writing to the master Region; a later miss that finds the marker reads the master Region instead of the local, possibly stale replica. ElastiCache Global Datastore replicates a cache across Regions asynchronously, so the secondary Region's copy also receives every invalidation after the replication lag: in the news feed loop's words (step 3.2), a copy of a cache is a second cache.

DAX

Side replay D1, the same product on DynamoDB behind DAX, both TTLs at their default of 5 minutes:

More DAX facts that decide designs: a TTL of 0 on the item cache means entries are refreshed only by eviction or write-through, and on the query cache means nothing is cached; DAX caches negative results in both caches (an item that wasn't found stays "not found" until its TTL, or until it's written through DAX); TransactGetItems passes through like a strongly consistent read; a hit never reaches the table, so it uses no table read capacity, and a miss is an ordinary eventually consistent read.

---

Part 10. The edge: CDN, browser and HTTP caching

We rewind to 20:00 once more. Valkey is only one of the copies: the CDN's edges, its shield and every browser keep their own, each with its own clock. And a CDN that doesn't recognize two requests as the same object doesn't cache at all.

Back to 20:00, on a copy: every link is a different object

Side replay 24, on a copy where the email's links carried ?utm_campaign=flash&sub=<subscriber id> and the cache policy kept every query string in the cache key. (The main line's policy keys on the path only.) The 12,000 page views a second are requests that reach the CDN; a reload that the viewer's browser answers from its own copy isn't one. From the reference implementation, one minute:

Synthesizing vector architecture diagram...

What to notice: in the main line, identical requests are collapsed twice (at each edge and at the shield), so the origin sees one fetch every 5 s. In the "On a copy" panel, the key includes the subscriber id, so nothing is identical and nearly every view reaches the origin.

CloudFront collapses simultaneous requests: "if there are simultaneous requests for the same object … CloudFront pauses before forwarding the additional requests", and it "only collapses requests that share a cache key". It even collapses under no-cache; only a minimum TTL of 0 together with private, no-store, no-cache, max-age=0 or s-maxage=0 prevents it. Origin Shield adds one more layer in front of the origin, consolidating misses from all edges to "as few as one request going to your origin".

Cache-Controldirectives, and the Ageheader

stale-while-revalidate and stale-if-error are defined in RFC 5861; the others, with Age and Vary, in RFC 9111 (HTTP Caching). CloudFront caps both stale windows at the cache policy's maximum TTL. Our origin sends public, max-age=30, s-maxage=5, stale-while-revalidate=10, stale-if-error=300.

The cache key

Put in the cache key everything the response depends on, and nothing else. On CloudFront the key is what the cache policy names: the path, plus the query strings, headers and cookies it lists. Every value you add splits the objects and lowers the hit ratio, as event 24 showed. Every value you leave out that the response depends on serves one viewer's answer to another (side row 25a, in Part 13: the page renders euros or dollars by Accept-Language, an origin request policy forwards that header to the origin but leaves it out of the cache key, so each edge stores whichever currency filled it first). CloudFront doesn't build the key from the origin's Vary header; it removes some Vary values before replying, and without a policy that forwards it, it removes Accept-Language before the origin ever sees it. Cookies you forward become part of the key, and CloudFront caches the origin's Set-Cookie too.

Snapshot S6, the last moment each layer served $49 in the main line, from the reference implementation (worst case over request timings, high traffic):

A browser that honors stale-while-revalidate can show the old copy once more, up to 10 s later, while it refreshes in the background. CloudFront sends Age on cache hits: we saw it on live responses (age: 692387 on a Hit from cloudfront response). AWS doesn't document how its tiers age a copy fetched from another tier, so plan with the column without Age. With Fix 1 in place from the start, Valkey would have been wrong for milliseconds, not ten minutes, and each tier's window would start at 20:00:00.

A personal page cached publicly

The fix has two parts. Personal data goes only in the private request /api/me/k7, which answers Cache-Control: private. And the CDN cache behaviour for /api/me/* must have a minimum TTL of 0: "If your minimum TTL is greater than 0, CloudFront uses the cache policy's minimum TTL, even if the Cache-Control: no-cache, no-store, and/or private directives are present in the origin headers." The managed CachingOptimized policy has a minimum TTL of 1 s, so it would cache a private response for a second.

Purge or version

At 20:20:00 k7's photo changes (event 27). The photo gets a new, versioned URL, k7.9f3a.jpg, cached for a year; the page now points at the new name, and nothing is invalidated. AWS recommends this: "Versioning is less expensive". Now the arithmetic if you purged on every price change instead:

A wildcard path (/p/*) counts as one path, and cache-tag invalidation (one tag per product) also counts one path per tag. Use versioned URLs for files, short TTLs for data, and purges for takedowns. That answers the drill The Image Service That Made Every Origin Server Sweat (question 1): with a versioned URL, the new photo shows as soon as a viewer gets a page that points at it (at most the page's own TTLs); with a purge, the edges drop the old one within seconds, but browsers keep it for its max-age. Takedowns that must reach further, like the YouTube loop's harmful content (step 3.4), add an edge blocklist and invalidation by cache tag; ISP caches outside your CDN are beyond any purge.

Serving stale at the edge

During shard B's outage (event 28, 20:15:00 to 20:17:00), the origin's render of /p/k7 doesn't use the last-known copy: on a cache error it answers 503, so the edge's copy is the fallback, rather than a degraded page the edge would then cache for 5 s. The edge keeps its copy under stale-if-error=300. From the reference implementation: no viewer got an error, and the oldest copy served was 125 s old, inside 5 + 300. CloudFront also serves an expired copy when the origin is unreachable and the minimum or maximum TTL is above 0, even without the directive; and it caches an error response for 10 s by default, so an early 5xx or 404 from a half-deployed origin doesn't stick for long.

A stale copy doesn't always need a new body: if it carries an ETag, the cache can revalidate it with If-None-Match, and the origin answers 304 Not Modified with no body.

Why an edge at all

The drill's second question: why a CDN rather than a bigger origin? A bigger origin can take more requests, but it can't remove the distance: every viewer far from it pays the round trips of TLS setup and the request itself. An edge answers from nearby and collapses identical misses, so the origin's load stops depending on the number of viewers (24a: 0.2 fetches a second for 12,000 views). The costs: every request is billed, hit or miss, so a CDN saves origin capacity, egress and latency, not request fees; and it adds the staleness above.

---

Part 11. End to end through the layers

Each layer caches something, has its own staleness bound, learns about a change in its own way, and fails in its own way. Follow one page view of k7 at 20:30:00 from a phone, and then the next price change, k7 back to $49 as v9 at 21:00:00, with every fix on.

Synthesizing vector architecture diagram...

What to notice: the public page and the private request take different paths from the phone. The public one stops at the first cache that has it; the private one always reaches the app and Valkey. The dotted line is the only path to the database, and only one fill per key takes it.

Synthesizing vector architecture diagram...

What to notice: two paths write the same tombstone at home, and eu waits for its own replica before invalidating. The HTTP tiers are never told: their TTLs are the only bound, and the browsers' is the longest.

The price change, from the reference implementation (event 29):

The app server's in-process copy is the same idea as the Sharding, Hot Keys & Rebalancing loop primitive's micro-cache (Part 4). If in-process copies must follow changes faster than their TTL, Valkey's server-assisted client-side caching (the CLIENT TRACKING command) sends invalidation messages to the clients that hold copies.

---

Part 12. On AWS

Every AWS cache has a TTL, an invalidation story, and a failure mode. Stated only from AWS's public documentation.

Managed services that use it

Running it yourself

Look-alikes that are not this mechanism

DNS answers are caches (a TTL per answer, with the same stacking rule), and they matter most when traffic moves between Regions: the Multi-Region Failover loop primitive covers the DNS tail (Part 5).

---

Part 13. What you've learned

Back to the kettle

At 20:00:00 the price dropped to $39, and the page showed$49 for ten minutes, to about 6.8 million page views. And the database, sized for a 99% hit ratio, would take 32 times its ceiling on the day the cache was empty. The pieces:

• A cache is a copy with no subscription (Part 1). Its load on the database is reads × (1 − hit ratio), and each key read costs at most one miss per TTL.
• Where the cache sits decides what can go wrong (Part 2): write-through still crosses with two writers, write-behind makes the cache the truth until it flushes.
• The ten minutes of $49 came from a refill that read a lagging replica and landed after the delete (Part 3). A tombstone with a version and a compare-and-set fill refused it; a lease would have stopped only a slow reader.
• Invalidations get lost (Part 4): the change stream retries them, and invalidating from the copy you fill from orders them.
• Herds: jitter kept 10,000 expiries at 225 queries a second instead of a collapse where 80 answers in a minute arrived in time; one fill per key took k7's expiry from 231 queries to 1 (Part 5). Negative caching gave the deleted product one query a minute (Part 6).
• Memory: half the catalog in memory still put the replica at 1,490 to 1,690 queries a second (Part 7).
• The empty day: "cache error = miss" answered 0.9% of the queries the replica ran in time; fail fast with capped fills kept the replica under its ceiling, the cold shard was back to 99% in 100 s, 28 s with warm-up, and a replica per shard avoids the cold start (Part 8).
• Readers who must see the write carry its version; another Region invalidates after its own replica has the data; DAX's query cache follows no writes (Part 9).
• The edge: a cache key with a subscriber id cached almost nothing; the HTTP tiers added 30 to 60 s after the app was right; purging every price change would cost $7,495 a month (Part 10).
• The costs: a version on every row and a script per fill, an invalidator and its lag, stated TTLs at every tier, a capacity plan for the empty day, and one more node per shard.

The whole story, event by event

From the reference implementation:

The cheat card

Failure checklist

• Does every copy (browser, edge, shield, app, cache, replica) have a stated staleness bound, and does someone know their sum?
• Does every invalidation run after the commit, and leave a new value or a versioned tombstone (written with a compare, so an older one can't replace a newer one) rather than a bare delete?
• Is every refill conditional (SET NX against an overwrite, or a version compare), never a plain SET?
• Is the change stream the guarantee behind the app's invalidation, with an alarm on the invalidator's lag?
• Do fills and invalidations read the same copy, or does the invalidator wait for the replica the fills read?
• Does every hot key have one fill per key (single-flight or a lease), and do batch loads use TTL jitter?
• Is the database sized for the day the hit ratio drops, with fills capped per server and a degraded answer ready?
• Does a cache error fail fast instead of becoming an uncapped database read with retries?
• Do cache shards the database can't live without have replicas, and is the invalidator rewound after every cache failover?
• Is the eviction policy what you think it is, and are sessions, locks and counters in a cluster of their own?
• Does the CDN's cache key hold everything the response depends on and nothing else (no tracking parameters, no per-viewer values)?
• Is personal data only in private responses, under a CDN behaviour with a minimum TTL of 0?

Think-first drills

Interview questions

Where to go next

• Change Streams & the Transactional Outbox: the stream that feeds the invalidator, order per key, and why caches store "gone" (Parts 3, 4 and 8).
• Replication, Quorums & Read-Your-Writes: the replica's lag behind race B, position tokens (Part 4), and why asynchronous copies lose their tail.
• Sharding, Hot Keys & Rebalancing: one hot key, the micro-cache, single-flight and coalescing routed by key (Part 4).
• Idempotency & Effectively-Once Processing: why a replayed tombstone is safe (Part 5).
• Multi-Region Failover: DNS caches and the tail after a Region moves (Part 5).
• Leases, Fencing Tokens & Distributed Locks: the other meaning of "lease".
• The Retries, Timeouts, Backpressure & Load Shedding loop primitive (coming): why answers arrive after their readers gave up, and how to shed load. The Rate Limiting loop primitive (coming): per-client limits against enumeration.
• Background: Primitive #04: Distributed cache patterns and eviction.
• Drills: The Product Page That Melted Redis (question 1 in Parts 5 and 8, question 2 in Parts 1 and 3) and The Image Service That Made Every Origin Server Sweat (both questions in Part 10).
• Loops: the key-value store (step 2.7), the rate limiter (steps 1.4, 2.4), the URL shortener (steps 1.3, 1.4, 1.5, 2.1, 2.4, 2.6, 3.3, 3.4), the news feed (steps 2.2, 2.5, 3.2), chat (step 2.1), the gaming leaderboard (steps 2.2, 2.4), notifications (step 1.5), search autocomplete (step 2.1), the job scheduler (step 2.1), the digital wallet (step 2.4), hotel reservations (steps 2.1, 3.4), the proximity service (steps 2.1, 2.6), maps and routing (step 1.1), nearby friends (step 1.2), ride-sharing dispatch (step 2.5), YouTube (steps 2.3, 2.4, 3.4), Google Drive (step 2.4), ad-click aggregation (step 2.1), the mobile news feed (step 1.4), mobile stock trading (step 2.6), and the Netflix (step 2.4), Discord (step 3.2), Shopify (step 1.1) and Figma case studies.