Cache Invalidation Isn't One Problem: It's Three Layers With Different Guarantees

Cache invalidation only sounds like one problem because the famous line about it compresses everything into a single clause. In a system built from a browser cache, a CDN, and a distributed application cache sitting in front of a database, a single write actually has to be reported to three places that don't share a clock, a protocol, or an agreed notion of when data changes.

How RFC 9111 Puts an Expiration Date on Every Cached Response

The closest thing to a formal specification for invalidation is not really about invalidation at all. RFC 9111, the current IETF standard for HTTP caching, defines when a stored response is allowed to be reused rather than how an origin server tells a cache to stop reusing one. A response carries a freshness lifetime, set through the max-age directive or an Expires header, and a cache treats max-age as authoritative enough that it must ignore an Expires header field once a max-age directive is present. If neither is set, the specification allows a cache to assign a heuristic expiration time based on signals like the Last-Modified field, without prescribing a specific algorithm for doing so.

Once a response goes stale, the cache doesn't discard it automatically. It revalidates, sending an ETag or Last-Modified value back to the origin and asking whether anything changed. That gives an origin server one lever: it can shorten how long a response is trusted, or it can answer a revalidation request with new data. What it cannot do is reach into a client's cache and force an early expiry. The freshness model in RFC 9111 is entirely pull-based: the cache decides on its own schedule when to check again, and until that schedule runs out, a write on the origin server has no way to reach it.

Cloudflare Rebuilt Its Purge Pipeline to Turn Edge Invalidation Into a Push

A CDN sits between that pull-based client cache and the origin, and it solves the same expiration problem differently: the operator can ask it, directly, to discard a specific piece of content. Cloudflare's cache documentation lists five ways to do that, purging a single file, purging everything in a zone, or purging by cache tag, hostname, or URL prefix, with single-file purge recommended as the default because it affects the least content.

That push only works if it actually reaches every location holding a copy. Cloudflare says it spent roughly two years rebuilding its purge pipeline, work that began near the end of 2022, with the explicit goal of increasing purge throughput while keeping invalidation close to instant across its network. Before that rebuild, a purge by tag, prefix, or hostname marked matching content as expired and left it to be evicted later rather than removing it immediately, which meant a purge call could succeed at the API level while stale copies kept answering requests at some data centers until their own eviction cycle ran. The purge cache-tag documentation now describes different behavior: purging a cache tag forces every matching cached object into a miss, sending the next request for it back to the origin. The mechanism moved from marking to removing, a meaningfully different guarantee for anyone relying on a purge call to actually stop stale content from being served.

Facebook's Memcache Paper Shows Why a Push Signal Can Still Race Itself

A CDN purge invalidates a copy of a response. A distributed application cache sitting closer to the database has a harder version of the same job, because the value it holds is read and written by many servers at once, and the delete signal itself can arrive out of order. The clearest public account of how this gets solved at scale is Nishtala et al.'s "Scaling Memcache at Facebook", presented at NSDI in 2013 and still the most detailed open description of production cache-invalidation engineering at that scale.

The paper names two specific failure modes. A stale set happens when a web server writes a value into the cache that no longer reflects the latest state, because concurrent updates got reordered. A thundering herd happens when a specific key under heavy read and write activity is invalidated so often that a large share of reads fall through to the database at once. Facebook's fix, leases, hands a client a token on a cache miss and rejects a later write carrying a token that a subsequent delete has already invalidated; rate-limiting those tokens to one per key every ten seconds took the peak database query rate for a set of especially contended keys from about 17,000 requests per second without leases to about 1,300 with them.

Delivery of the delete itself is measured, not assumed. Facebook's own monitoring over a 30-day span found that deletes issued and consumed within a single region reached four nines of reliability within one second and five nines within an hour, while deletes crossing between regions reached three nines within one second and needed ten minutes to reach four nines. Even inside a system built specifically to solve this problem, a delete is a message that can be delayed or retried, not an instruction that takes effect the moment it's issued.

Lining Up Three Layers' Guarantees Shows Where the Real Gaps Sit

None of the three sources above set out to compare themselves to each other. Read side by side, they describe the same shape of problem at three different distances from the database, each with its own trigger, and each honest about where its own guarantee stops.

The pattern across all three rows is the same: each layer's invalidation mechanism is trustworthy inside its own boundary and silent about everything outside it. RFC 9111 has nothing to say about a CDN. Cloudflare's purge API has nothing to say about an application's memcache pool. Facebook's paper solves consistency within one memcache deployment, not between memcache and whatever CDN sits in front of it. Coordinating all three for a single piece of data is left to whoever wrote the application: delete the database row, delete the cache key, call the purge endpoint, in that order, and hope none of the three calls fails silently.

What Breaks When One Layer's Delete Never Reaches the Next

The open question this leaves isn't whether any one layer works. RFC 9111's freshness model, Cloudflare's rebuilt purge pipeline, and Facebook's lease mechanism each do what they claim, and each publishes real numbers or specification language to back that up. What none of them can detect is a gap between layers: an application that successfully deletes a memcache key but never calls the CDN purge endpoint, or a purge that succeeds at the edge while a browser two clicks away is still inside its max-age window from an earlier fetch. Because each layer's guarantee stops at its own boundary, a request can pass every one of the checks above and still return stale data, simply because the write that should have triggered all three never told the second or third layer it happened. There is no fourth layer that verifies the other three agree with each other. That coordination, when it exists at all, is application code someone wrote and has to keep maintaining, not a property any of these systems provide on their own.