Cache Invalidation Strategies: The Hardest Problem in Computer Science

The outage that put cache invalidation on the map

Phil Karlton's line — "there are only two hard things in computer science: cache invalidation and naming things" — is one of the most quoted lines in software engineering, and it's stuck around because it's precisely correct, not because it's clever. The clearest demonstration of why is a real, well-documented incident: on September 23, 2010, Facebook went down for over four hours after a configuration change produced a value every client interpreted as invalid. Each client tried to "fix" it by deleting the corresponding cache key and re-querying the database. That alone would have been a manageable spike — except every failed database query was itself interpreted as another invalid value, triggering another cache deletion and another retry. The result was a self-perpetuating feedback loop: invalidations caused failed queries, failed queries caused more invalidations, and the database stayed buried under the load even after engineers fixed the original configuration error, because the loop had become self-sustaining. It took hours to fully recover.

That incident is worth understanding in detail because it isn't really a story about "the cache broke" — it's a story about invalidation logic that, under a specific failure condition, kept invalidating itself faster than the system could recover. That's the general shape of almost every serious cache invalidation bug: not a single bad delete, but an invalidation path that becomes self-reinforcing under load.

Why invalidation is genuinely hard

The core difficulty is structural: your cache and your database are two separate systems with no shared transaction boundary. When you update the database, the cache has no idea unless something explicitly tells it. When you delete a cache key, a race condition can put stale data right back before the next read arrives. And when multiple services share the same cached data, there's often no single place that owns invalidation for all of them.

The problem also compounds with scale in a way that's easy to underestimate. At 10 requests per second, a 5-minute stale window barely matters — a handful of users see slightly old data for a few minutes. At 100,000 requests per second, that same 5-minute window means tens of thousands of users see wrong information before it clears, and if the invalidation path itself has a bug, the failure mode isn't "some stale reads" — it's the 2010 Facebook scenario, where the invalidation logic itself becomes the outage.

Invalidation strategies

Cache Invalidation Methods:

Strategy           Staleness       Complexity   Best For
----------------   -------------   ----------   ------------------
TTL-based          Up to TTL       Trivial      Product listings,
                   (5 min max)                  blog posts,
                                                any read-heavy data

Delete-on-write    Milliseconds    Low          User profiles,
                   (next read                   inventory counts,
                   repopulates)                 permissions

Event-based        Milliseconds    Medium       Multi-service
(Pub/Sub)          (async event                 architectures
                   triggers                     where writer and
                   invalidation)                reader are separate

Version/Hash       Zero             Low         Static assets,
(Cache busting)    (new version =               API responses
                   new cache key)               with ETag

CDC-based          Seconds          High        Database changes
(Debezium)         (DB change                   that must propagate
                   stream)                      to multiple caches

Best practice: COMBINE strategies
  - TTL as a safety net (ensures stale data eventually dies)
  - Delete-on-write for immediate freshness
  - Event-based for cross-service invalidation

TTL-based expiration is the trivial default: set a time-to-live, let the cache expire naturally, and accept bounded staleness. It requires no coordination between the writer and the cache, which is exactly why it should exist everywhere as a backstop — if every other invalidation mechanism fails silently, TTL is what guarantees stale data doesn't live forever.

Delete-on-write is the workhorse for anything that needs near-immediate freshness: when the underlying data changes, delete the cache key rather than update it (more on why that distinction matters below), and let the next read repopulate the cache from the source of truth.

Event-based invalidation (typically pub/sub) is what delete-on-write becomes once you have more than one service reading the same cached data. The writer publishes an event when data changes; every service that caches that data subscribes and invalidates its own copy. This is the mechanism that would have prevented a variant of the 2010 Facebook incident from cascading indefinitely — a well-designed event-based system needs an explicit circuit breaker so failed re-fetches don't themselves trigger more invalidation events.

Version or hash-based invalidation ("cache busting") sidesteps the delete/race-condition problem entirely by never invalidating anything — instead, a new version of the data gets a new cache key or URL (bundle.a3f9c2.js), so the old cached copy simply becomes unreferenced and ages out naturally. This is the standard approach for static assets and works cleanly for API responses using ETags too.

CDC-based invalidation (Change Data Capture, via tools like Debezium) taps the database's own replication/write-ahead log and streams every change out to whichever caches need to react, which is powerful for propagating invalidation to many downstream caches consistently, but it's the highest-complexity option on this list and usually only worth it once you have several independently-cached views of the same underlying data.

No single strategy is sufficient alone in a real system. The practical pattern is layering them: TTL as the safety net that guarantees eventual correctness no matter what else fails, delete-on-write for the critical path where freshness actually matters, and event-based invalidation once more than one service needs to react to the same change.

The thundering herd problem, and how the 2010 Facebook mechanism generalizes

Thundering Herd Problem:
  Popular cache key expires.
  10,000 concurrent requests all miss cache.
  10,000 identical database queries fire simultaneously.
  Database: dead.

This is the failure mode underneath the Facebook incident, generalized: any time a lot of traffic converges on re-fetching the same data at once — because a popular key expired, or because an invalidation event fired — the database can get hit with a spike of duplicate, redundant queries for identical data. Three established fixes, roughly in order of how commonly they're implemented:

Mutex lock (request coalescing / singleflight): the first request to miss the cache acquires a lock and is the only one allowed to query the database; the other 9,999 requests wait briefly and then read the now-freshly-populated cache instead of hitting the database themselves. Net effect: one database query instead of ten thousand, regardless of how many requests arrived in the gap.

Stale-while-revalidate: instead of making requests wait, serve the expired value immediately to everyone while exactly one background task refreshes the cache. Users see slightly stale data for roughly the duration of that refresh, but the database still sees only one query, and nobody experiences added latency waiting on a lock.

Probabilistic early refresh (and TTL jitter): rather than waiting for a hard expiry and reacting to the stampede, get ahead of it. As a key's TTL approaches, give each request a small and increasing probability of proactively refreshing it early, so one "lucky" request refreshes the cache before expiry and the stampede window never opens. A simpler, closely related fix for the case where many keys share the same TTL is to add small random jitter to each key's expiry time, so thousands of keys set at the same moment don't all expire in the same instant — spreading the rebuild load out instead of concentrating it.

Common anti-patterns

The most common mistake is updating the cache instead of deleting it. This looks harmless but creates a real race condition: Thread A reads stale data from the database, Thread B writes new data to the database and updates the cache with the fresh value, and then Thread A — still working with data it read before B's write — writes its now-stale value into the cache, silently overwriting B's fresh update. Delete-on-write avoids this entirely: deleting the key means the next read is guaranteed to fetch current data from the database, rather than trusting whichever thread happens to write to the cache last.

The second common mistake is invalidating too aggressively. If deleting a user's profile cache key also cascades into invalidating their friends list, activity feed, and recommendation cache, a single profile edit turns into a burst of database queries across several unrelated systems. Scope invalidation to exactly what changed — this is also, structurally, a smaller-scale version of the same self-reinforcing pattern that took Facebook down in 2010: an invalidation that triggers more invalidation than the actual change warrants.

Multi-layer invalidation

Real systems rarely have just one cache. A typical request path crosses a browser cache, a CDN edge cache, an application-level cache (Redis or similar), and sometimes a database query cache — and invalidating only one layer while the others still hold the old value means users can see stale data despite your backend being fully correct.

• Browser cache — controlled via Cache-Control headers. Use no-cache (revalidate every time) or a short max-age for anything that changes often.

• CDN edge cache — either versioned URLs (bundle.a3f9c2.js, so a new deploy is automatically a cache miss everywhere) or an explicit purge API call at deploy/update time.

• Application cache (Redis, etc.) — delete-on-write as the default, with pub/sub to propagate that invalidation across every application instance if you're running more than one.

• Database query cache, where present, generally follows the database's own invalidation and is the layer you have the least direct control over — a strong argument for not depending on data being fresh at that layer specifically.

The organizing principle across all of them is the same one that shows up everywhere in this topic: TTL at every layer as the safety net that guarantees eventual correctness, with active invalidation reserved for the specific paths where staleness is actually unacceptable.

Interview framing

A strong answer sounds like: "I'd combine several strategies rather than rely on one. TTL everywhere as a safety net, so nothing stays stale indefinitely even if an invalidation path fails. Delete-on-write, not update-on-write, for the critical path — updating the cache directly creates a race condition where an in-flight stale read can overwrite a fresh write, while deleting guarantees the next read always goes back to the source of truth. If more than one service caches the same data, I'd use event-based invalidation over pub/sub so the writer doesn't need to know about every downstream cache. And I'd explicitly plan for thundering herd: when a popular key expires or gets invalidated, I don't want thousands of simultaneous requests all hitting the database for the same data, so I'd use request coalescing — a single in-flight request per key — or stale-while-revalidate so the database only ever sees one query per refresh, not one per concurrent request." Mentioning the delete-vs-update race condition and the thundering herd mitigation by name are usually the two signals that separate a surface-level TTL answer from one that shows real production experience.

Key takeaway

Cache invalidation is hard because the cache and the database are separate systems with no shared transaction boundary — nothing guarantees they agree at any given instant. Use delete-on-write, not update-on-write, for anything on the critical freshness path, since updating creates a race condition that deleting avoids entirely. Layer TTL underneath everything as a safety net, add event-based invalidation once more than one service shares the same cached data, and always plan explicitly for thundering herd — via request coalescing, stale-while-revalidate, or probabilistic early refresh — since an unprotected cache-miss spike is exactly the mechanism that turned a configuration typo into a multi-hour Facebook outage in 2010. And remember invalidation isn't a single-layer problem: browser, CDN, and application caches all need their own invalidation path, or a technically-correct backend can still serve stale data to real users.

FAQ

Why is deleting a cache key safer than updating it? Updating the cache directly can race with a stale read that's still in flight: if Thread A read old data before Thread B's write, A can overwrite B's fresh cache update with its own stale copy. Deleting the key removes that race entirely — the next read is always forced back to the database, guaranteeing freshness rather than depending on write ordering.

What's the difference between a cache stampede and the thundering herd problem? They describe the same phenomenon: a large number of requests converging on the database at once because a popular cache entry expired or was invalidated simultaneously for everyone. "Cache stampede" and "thundering herd" are generally used interchangeably in this context.

Is TTL alone ever good enough? For read-heavy, low-consequence data — a blog post list, a product catalog page — yes, a short TTL alone is often sufficient and far simpler than active invalidation. It stops being good enough once staleness has a real cost (stale permissions, stale inventory counts, stale pricing), which is when delete-on-write or event-based invalidation becomes necessary on top of it.

How does stale-while-revalidate differ from just increasing the TTL? A longer TTL means everyone sees stale data for longer, full stop. Stale-while-revalidate keeps the TTL short but serves the (briefly) expired value while exactly one background refresh happens, so staleness is bounded to roughly the length of one refresh rather than the length of the whole TTL window.

Does a CDN purge count as cache invalidation? Yes — it's the CDN-layer equivalent of delete-on-write. The distinction worth remembering is that purging a CDN and invalidating your application cache are two separate operations against two separate systems; doing one without the other is a common way stale data survives at the layer you forgot to touch.