Cache Invalidation

Cache invalidation is the set of rules that decide when a cached copy no longer matches its source of truth, so that the next read either removes it, refreshes it, or serves it while re-fetching — the cache is never allowed to silently keep returning a value the origin has since changed.

Two mechanisms are constantly confused, so pin them down before anything else:

• Write policies (write-through, write-around, write-back / write-behind) decide how a write reaches storage — whether the new value lands in the cache, the store, or both, and in what order. They keep cache and store consistent on the write path you control.
• Invalidation methods decide when an existing cached read-copy must be retired because the truth changed underneath it — often through a path the cache never observed (a batch job, a replica, another service, a human editing the DB).

This page is about the second. Write policies are a separate topic; listing them as "invalidation schemes" is the classic category error. Invalidation methods themselves split cleanly into two families:

• Event-driven — a writer tells the cache something changed: Purge, Refresh, Ban.
• Expiry-driven — the cache decides on its own from a clock: TTL and Stale-While-Revalidate.

The methods, by mechanism

Purge (event-driven, eager)

A hard delete of a specific key/URL. The entry is dropped from the cache immediately; the very next request for it is a guaranteed miss that goes to the origin, repopulates, and returns fresh. You must name each key you want gone.

Refresh (event-driven, eager)

Force a re-fetch from origin and overwrite the cached value in place, without deleting it first. Unlike purge, there is no window where the key is absent — a concurrent reader that arrives mid-refresh still gets a (stale) hit instead of a miss, so refresh avoids the miss-storm that mass purges cause.

Ban (event-driven, lazy)

Invalidate by criteria — a URL pattern or header — instead of by exact key. Issuing a ban does not touch any object; it appends a rule to a ban list stamped with the time it was issued. From then on, every incoming read is checked against the list: if the requested object matches a rule and was cached before that rule's timestamp, it is treated as stale and re-fetched; otherwise it is served normally. Objects are cleaned lazily as they happen to be requested, and a rule can be dropped once every object older than it has been refreshed. One O(1) command can invalidate millions of keys.

TTL expiration (expiry-driven)

Each entry carries a time-to-live. A read served before expiry is a hit; after expiry the entry is stale and the next read re-fetches. No coordination with writers at all — the cache heals itself on a fixed clock, at the cost of serving stale data for up to one TTL.

Stale-while-revalidate (expiry-driven)

On a read of an expired entry, serve the stale copy immediately and kick off an asynchronous re-fetch; the fresh value replaces the stale one when it lands. The reader never blocks on the origin — freshness is traded for latency.

Worked example: ending a holiday sale with one Ban

A CDN caches 40,000 product pages under /category/holiday-sales/…. At 09:00 the sale ends and every price under that path changes. Firing 40,000 individual purges would hammer the origin and the cache's control plane, so instead you issue one ban: pattern ^/category/holiday-sales, timestamped 09:00:00. Here is what the next few reads actually do:

The cost of invalidation is now paid lazily, per read, only for objects that are actually requested — and only once each. Cold objects nobody asks for are never re-fetched at all; their rule simply sits in the list until GC.

Pitfalls

Invalidate-then-write races (the classic correctness bug)

The intuitive order — delete the cache, then update the DB — is wrong under concurrency:

// WRONG: a reader can slip in between the two lines
cache.delete(key)      // 1. cache is now empty
// <-- concurrent reader misses, reads OLD row, repopulates cache
db.update(key, newVal) // 2. DB now new, but cache holds OLD forever

Why the naive version is wrong: between steps 1 and 2 the DB still holds the old value. A concurrent read misses the empty cache, loads the old row, and writes it back — so the cache is repopulated with stale data that no further event will clear until TTL. Fix the ordering: commit the DB write first, then invalidate (db.update(...); cache.delete(key)), so any repopulating read after the delete can only load the new value. Even this leaves a narrow window; systems that need more use versioned keys or a short "delay-delete" second invalidation.

Purge storms / thundering herd

Purging a hot key sends every concurrent reader to the origin at the same instant (a cache stampede). Prefer refresh (overwrite in place) for hot keys, or add request coalescing / a short lock so only one fetch hits origin.

Ban-list growth

Every read scans the ban list, so its cost is O(list length) per request. Rules for objects nobody re-requests never get to GC, so an unbounded, ever-growing ban list slowly taxes every single read. Cap the list, coalesce overlapping rules, and expire old ones.

Multi-layer invalidation

Browser cache, CDN, and app cache are independent. Purging the CDN does nothing to copies already sitting in users' browsers — those obey the Cache-Control: max-age you sent. Set short/validated TTLs at the edge you cannot purge.

TTL extremes

TTL too long → stale data lingers with no way to force freshness; TTL too short → the cache barely absorbs load and the origin sees near-uncached traffic. TTL is a staleness-vs-load knob, not a fire-and-forget default.

When to use which — and what it costs

The real decision is do you know precisely what changed, and how many keys does it touch?

• Purge — signals: a small, known set of exact keys changed (one product edited). Gain: immediate, exact, no lingering staleness. Cost: you must enumerate every key, so pattern-shaped invalidations explode into huge fan-out, and mass purges cause miss storms.
• Ban — signals: the affected set is large or defined by a pattern you can't cheaply list (a whole category, everything with a header). Gain: O(1) to issue no matter how many objects match; work is amortized over real reads. Cost: every read pays a ban-list scan, stale objects linger until requested, memory held until GC.
• TTL — signals: you can't hook the writers (third-party origin, another team's DB) and bounded staleness is acceptable. Gain: zero invalidation infrastructure, self-healing. Cost: guaranteed staleness up to one TTL; short TTL trades away hit ratio.
• Stale-while-revalidate — signals: user-facing reads where latency matters more than being perfectly current. Gain: reads never block on origin. Cost: knowingly serves stale during the revalidation window; extra background fetches.

Choose Purge when the key set is small and known; prefer Ban when it's large or pattern-defined; reach for TTL when you can't observe the writes; layer Stale-While-Revalidate on top when a read must never wait. The main axis to reason about is Purge (eager, exact, expensive to fan out) versus Ban (lazy, pattern-based, cheap to issue but taxes every read).

Takeaways

• Invalidation answers "when is this cached copy no longer true?" — it is not the same thing as a write policy, which answers "where does a new write land?"
• Event-driven methods (purge/refresh/ban) need a signal from the writer; expiry-driven methods (TTL/SWR) need only a clock. Pick event-driven when you can observe writes, expiry-driven when you can't.
• Ban buys O(1) invalidation of huge, pattern-defined sets by making every read pay a timestamped check — cheap to fire, but the ban list must be bounded and GC'd.
• Order matters: write the store first, then invalidate, or a concurrent read will re-cache the stale value permanently.

Sources: Fastly and Varnish documentation on purge vs. ban and lazy ban-list invalidation; MDN and RFC 5861 on Cache-Control, TTL, and stale-while-revalidate; the well-known cache-aside consistency discussion in Facebook's "Scaling Memcache at Facebook" (NSDI 2013) for the invalidate-ordering race. Re-authored/Deepened for this guide.