Caching at scale, and why invalidation is hard

“There are only two hard things in computer science: cache invalidation and naming things.” Phil Karlton’s line gets quoted as a joke. After a few years running caches in front of 100M+ views a month, I read it as a warning.

The caching half is the easy, fun 80%: put the answer closer to the reader and watch the origin go quiet. Invalidation is the other 20%: deciding when a cached answer has stopped being true, and making every copy of it agree. That’s the part that pages you at 2am, and it’s hard for a reason worth unpacking.

Four caches, one job

First, the easy part. Every request runs a gauntlet of caches, and each layer exists to keep the next one quiet. By the time anything reaches the database, it should be a genuinely uncacheable request.

# where a request can stop
browser   immutable assets, content-hashed filenames
edge/CDN  full HTML + JSON, keyed by URL (+ a header or two)
redis     computed fragments and hot rows
database  read replicas, the last resort

Most of what gets called “scaling” is really just moving the cache boundary one hop closer to the user. The trouble starts the moment any of those copies needs to change.

The only question that matters: how stale can it be?

A cache is a deliberate trade of freshness for speed and cost. Every entry has a staleness budget whether you named it or not, and invalidation is just how you enforce that budget. So the first design question is never “how do I cache this.” It’s “how wrong is this allowed to be, and for how long?”

A stock price tolerates seconds. A published article tolerates minutes. A user’s avatar tolerates an hour. A bank balance tolerates nothing. Name that budget per data type up front and almost every other decision falls out of it. Skip it and you’ll reach for the most aggressive invalidation you can build, then spend months debugging the races it creates.

Strategies, from blunt to precise

TTL / expiry: the blunt instrument. Stamp the entry with a lifetime and let it die on a timer. No coordination, no source of truth, no distributed anything. The cost: you sit somewhere between fresh and max-age seconds stale at all times, and you can’t react to a change faster than the TTL. For most content with a real staleness budget, it’s the right default.

Cache-Control: public, max-age=60, s-maxage=86400, stale-while-revalidate=600, stale-if-error=86400

Write patterns: keep the copy in step with the source. Cache-aside (lazy) is the common one: read misses load from the source and populate; writes update the source and then drop the cache entry. Write-through updates cache and source together for consistency at the cost of slower writes; write-back updates the cache and flushes later for speed at the cost of durability; write-around skips the cache on write so you don’t pollute it with data nobody’s reading yet. Which you pick is mostly a function of that staleness budget and how much you trust a crash.

Explicit purge / event-driven: precise and real-time, and now it’s your problem. On change, actively evict. This gives near-immediate correctness, but you’ve signed up for a distributed-systems problem: every copy, in every region, has to receive the purge, and until it does it’s serving stale. A global CDN purge is fast, not instant.

Key versioning: stop deleting, start renaming. The cleanest trick I know is to change an entry’s key instead of invalidating it, so a new version is simply a new key and the old one ages out on its own. Carry the version on the parent object so you have it at read time.

// a write bumps updatedAt; readers compute a new key, nothing to delete
const key = `post:${post.id}:v${post.updatedAt.getTime()}`;

You never coordinate a deletion because you never delete. The catch is memory (old generations linger until eviction) and discipline (every reader must derive the same key).

Surrogate keys / tags: invalidate by relationship, not by URL. Tag each response with what it depends on, then purge by tag. One author edits their bio; you want to drop every page that renders it without enumerating URLs.

Surrogate-Key: post-123 author-7 home
# one purge drops every cached page that depends on author 7:
#   curl -X POST -H "Surrogate-Key: author-7" https://api.fastly.com/.../purge

This is how you handle fan-out (one change touching many derived pages) sanely.

Stale-while-revalidate: serve stale, refresh behind the reader’s back. The pragmatic favorite (RFC 5861). On expiry, hand back the stale copy instantly and refresh in the background. Readers never wait on a rebuild, the origin sees one refresh instead of a flood, and staleness stays bounded. stale-if-error extends the same idea to outages: serve stale rather than fail.

Why invalidation is actually hard

Notice what happened above: a list of performance techniques quietly turned into a list of consistency problems. That’s the whole thing. Cache invalidation is a distributed-consistency problem wearing a performance costume, and consistency is hard. Concretely:

There’s no single source of truth anymore. The moment you copy data, you have N copies that can disagree, and you’ve opted into eventual consistency whether or not you used the words.
Propagation isn’t instant. Between “I purged” and “every edge agrees” there’s a coherence window. Usually fine. But you have to know the window exists and decide it’s acceptable, rather than assume purges are atomic.
Naming is the other hard thing, and it leaks in here. The cache key is the design. Too broad and you serve the wrong answer or tank the hit rate; too narrow and the keyspace explodes; miss a dimension that changes the output (auth state, locale, device) and you serve stale data, or worse, leak user A’s page to user B. Half of “invalidation is hard” is really “naming the key is hard.”
Dependencies fan out. One row change can invalidate a list, a count, three rendered pages, and a derived aggregate. The full set of entries a write invalidates is a graph most systems don’t track, so people over-purge and kill the hit rate, or under-purge and serve stale.
Races interleave badly. The classic cache-aside bug: a reader misses and loads the old value, a writer updates the source and deletes the key, then the reader writes its now-stale value back. The entry is wrong until the next write. Ordering rules (delete after write, double-delete, version-checked writes) and a short backstop TTL are how you survive it.

And then the one that actually takes sites down: the thundering herd. A hot key expires and thousands of concurrent requests miss at the same instant, all stampeding the origin right when traffic is highest. The fix is to make sure only one of them does the work (single-flight):

// golang.org/x/sync/singleflight: one rebuild per key, the rest share the result
v, err, _ := g.Do(key, func() (any, error) {
    return loadFromOrigin(key)
})

Pair single-flight with jittered early recomputation (refresh a hot key slightly before it expires, with randomness so they don’t all line up) and stale-while-revalidate, and an expiring hot key becomes a non-event instead of an outage.

What I actually reach for

Name the staleness budget per data type first. Everything else follows from it.
Default to TTL plus stale-while-revalidate. It covers most cases with zero coordination.
Version keys instead of deleting wherever you can. Deletion is the hard part, so avoid it.
For precise, real-time invalidation, use surrogate keys, not lists of URLs.
Coalesce on miss with single-flight for hot keys, and add jittered early refresh.
Make keys explicit and namespaced, and include every dimension that changes the output. Audit for cross-user leakage specifically.
Keep a short TTL even when you purge. It caps the damage from the one invalidation you’ll inevitably miss.

Why the quip endures

Caching looks like a performance feature, so people treat invalidation as a performance detail. It isn’t. It’s distributed consistency, and the moment you have more than one copy of the truth you’ve taken on every hard problem that comes with that. The win isn’t a perfect invalidation scheme. It’s choosing a staleness budget on purpose, then picking the cheapest strategy that honors it. Cache the easy 80% freely. Respect the 20%.