Cache Invalidation
Transcript
Made automatically from the video's sound, so it may contain mistakes. Click a line to play from there.
Welcome back to The Explainer. Today we're diving into episode S08E09, and we're tackling an absolute monster of a topic. Why invalidating copied truth is just fundamentally hard.
Whether you're a systems engineer tuning heavy distributed infrastructure, or a vibe coder, shipping full stack apps with AI agents, we're gonna look at the silent failures that happen everywhere. I'm talking from bare CPU silicon right the way up to browser service workers.
And for a quick recap of SO8E08, where we uncovered how text representations silently diverge across layers. Keep that in mind because that divergence is exactly what we're fighting today. We're officially wrapping up ARC 3 today, our deep dive into deceptively broken primitives with this legendary maxim from Phil Carlton.
It perfectly captures what goes completely off the rails the instant you copy truth into a faster layer, just to buy a little speed. Because the second you cache something, you're literally creating an alternate timeline.
Here's our roadmap for the journey today. We'll start with deceptively broken primitives, move through the full stack cache hierarchy, tackle stale overwrite races, look at metastable collapses, dig into edge security disasters, and finally outline the AI cache contract.
Alright, let's jump right into part one. Deceptively broken primitives. Think about it. We usually just think of caching as storing data to make things load faster, right?
But building on our last explainer about Unicode string divergence, you've got to realize that caching isn't just storage. It is fundamentally about forking reality. You are making a massive, dangerous promise that all these scattered, drifting copies of the truth are eventually going to synchronize.
And keeping that promise? Yeah, that's incredibly difficult. The full stack cache hierarchy. Take a look at this timeline.
It brilliantly illustrates Ulrich Drepper's latency hierarchy and the exponential risk of staleness across a modern architecture. We're zooming all the way out from microscopic one nanosecond 64-byte CPU cache lines through the OS kernel page cache into in-process L1 heaps, like caffeine window tiny LFU, then out to distributed L2 stores like Redis or Memcached, and finally hitting the HTTP CDN edge and 100 millisecond browser service workers.
Every single jump outward is a brand new liability. So down at the bare silicon level, we hit what Martin Thompson famously calls false sharing. Imagine two parallel threads.
They're updating completely independent variables, right? But plot twist, those variables happen to live on the exact same 64-byte cache line. The hardware literally forces them to fight for ownership. It's a silent performance killer on symmetric multi-processing systems.
Your code looks totally fine, but your scalability is just getting crushed behind the scenes. To fix this, the hardware plays this microscopic high-stakes game of hot potato using the messy cache coherency protocol.
When those competing cores ping-pong data, they're passing invalidation messages through the L3 cache, demanding a request for ownership. If you modify a shared line, you force every other processor to mark their local copy as invalid, and boom, they suffer a brutal latency penalty to reload it from scratch.
Let's move up the stack to distributed systems. In part three, stale overwrite races. Okay, let's map out the classic cache-aside stale overwrite race. This is straight out of Facebook's legendary 2013 Usenyx memcache paper.
Imagine a slow read misses the cache and grabs old data from the database. But while it's lagging, a write transaction sneaks in, updates the database, and deletes the cache key. Then that initial slow read finally finishes.
And what does it do? It blindly repopulates the cache with that old stale data. It completely breaks Jepson Read Your Rights guarantees. The user saves their changes, hits refresh, and poof, their updates just vanish.
Meta tackled this elegant nightmare using two methods. First, they introduced lease tokens, basically handing out a 64-bit token bound to specific keys to referee those concurrent rights and prevent stale sets. Second, they unleashed MC Squeal Demons.
These little demons sit on the database, inspect the actual committed SQL statements, and safely broadcast invalidations, like their Skybridge invalidation streams directly from the commit log across regions. It completely sidesteps replication lag.
You'll see a super similar pattern in Redis RESP3 when it comes to client-side caching. Redis handles these race conditions using an internal invalidation table. The server tracks exactly which clients requested which keys.
So when a key gets modified, the server fires off an invalidation message. The clients safely garbage collect those keys locally, and you guarantee your in-process heap isn't accidentally serving straight up lies to your users. But what happens when everything misses all at once?
Let's look at part four Herds and Metastable Collapses. Check out this chart from the ACM HotOs 2021 paper. It visually proves Mark Brooker's bimodal cache math, and honestly, it's terrifying. Imagine a hotkey expires while taking 10,000 requests per second.
You get this massive synchronized cluster of misses that hits simultaneously. This triggers an unrecoverable metastable failure loop. A thundering herd just steamrolls your undersized database. And worse, just shedding load won't even fix the sustaining effect, especially if you compound it with RFC9520, negative caching of transient errors.
To fight off these thundering herds, Facebook's memcached servers tightly regulate the rate of their lease tokens. They only give out a token once every 10 seconds per key. If a thousand other clients ask for that key in that 10-second window, they are told to wait.
By the time they retry, that furked lucky client has usually repopulated the cache. Or you can take a slightly different route. The VLDB 2015 XFetch paper suggests probabilistic early expiration. Basically, individual requests independently pick a random time gap to sort of peek into the future.
If the item would expire in that future window, the process just regenerates it early. It's a brilliant use of TTL Jitter to gracefully absorb stampedes without needing heavy external lock management.
Now for the really scary stuff, at the very edge of the stack. Part 5, edge security disasters. Out at the edge, we live and die by RFC 911, HTTP Cache Control Directives. Look at this table.
I literally cannot overstate how crucial it is to know the exact difference between no store and no cache when you are handling sensitive user payloads. No cache actually lets the CDN store the data, it just forces a revalidation. If you want to absolutely guarantee a private payload never touches a disk, you have to use no store, no exceptions.
This ties perfectly into Portswigger's vital distinction between web cache deception and webcache poisoning. Cache deception is when you trick the cache into storing a victim's private data, like an attacker appending.css to an account URL, so the CDN caches a private profile as if it were a static style sheet.
Cache poisoning is when an attacker uses unkeyed headers to inject a malicious payload that then gets served to innocent users. Both happen because the origin server and the caching layer are completely disagreeing on paths and delimiters.
And we absolutely have to explicitly warn builders about what I call the vibecoder trap. If you're out there shipping apps and you rely on overlapping framework caches, say Next.js router caches sitting on top of CDN layers without strict private headers, or if you use a global new map in a serverless function that causes OOMs or split brain, you will eventually leak user A's private profile to user B.
Blind sets on write operations, missing cache control, it's a catastrophic vulnerability hiding in plain sight. Finally, let's establish a framework to tame all this chaos. Part 6.
The AI cache contract. But wait, before you write a single line of caching logic, you have to pass the Yagny gate. You aren't gonna need it.
Look, can you prove that an explain analyze on your database isn't just showing a missing SQL index? Please never invite these synchronization nightmares into your infrastructure simply because you forgot to add a basic index.
But okay, if you prove you absolutely must cache, you have to strictly enforce this five-part AI cache contract. One, bounded evictions with tenant-scoped versioned keys. Two, explicit DEL leases or fastly surrogate key tag purges.
Three, jittered TTLs capped with strict under five-second negative cache caps. Four, single-flight request coalescing or stale while revalidate stampede guards, and five, circuit broken degraded fallbacks. This contract is your shield.
Garbage collection versus ownership. It leaves us with a pretty provocative question. Once you've actually managed to invalidate the truth and collapse all those forked realities, who is actually responsible for sweeping up the memory left behind in the void?
Think about that for a bit. Thanks for hanging out, and I'll catch you in the next one.