Invalidating cached content with complex dependencies

"A cached page depends on 15 upstream entities. Any of them can change. How do you invalidate?"

What it is

The problem is not "how do I delete a cache key". It is that the thing you cached is a function of many inputs, and the cache is keyed by the output, so when an input changes you do not know which outputs to remove.

A product page renders from the product record, its price, its inventory, its category, the seller's profile, three promotions, a review summary, and the recommendation block. Cached under /product/8821. The seller changes their display name. Which of the two million cached pages does that invalidate?

Three families of answer exist:

Strategy	How invalidation happens	Staleness
Time-based (TTL)	You wait	Up to the TTL, always
Tag / surrogate-key	Purge everything tagged with the changed entity	Seconds
Versioned keys	Bump a version so old keys become unreachable	Zero, at read time

Commonly confused with cache eviction, which is the cache reclaiming memory under pressure and is the cache's decision. Invalidation is your decision, driven by correctness. Also commonly confused with the stampede problem: invalidation is about which entries to remove, stampede is about what happens to concurrent readers when one is removed. They compose, and getting invalidation right while ignoring stampede turns a correctness fix into an outage.

The problem it solves

Without a dependency mechanism you get exactly one of two bad outcomes.

TTL too long, and you serve wrong data. A price change takes 15 minutes to appear. For a price, that is a customer-service problem and possibly a legal one.

TTL too short, and the cache stops working. At a 30-second TTL on a page that takes 400 ms to render, a moderately popular page is regenerated constantly and the hit rate collapses. You have paid for a cache and kept the origin load.

The dependency-tracking approaches break the trade: long TTL for efficiency, precise purge for correctness.

Mechanics

Tag-based invalidation (surrogate keys)

The dominant approach at the CDN layer. When the origin renders a response, it declares what the response depends on:

HTTP/1.1 200 OK
Cache-Control: public, max-age=86400
Surrogate-Key: product-8821 seller-441 category-12 promo-77 promo-91

The CDN stores the response and indexes it under each key. When the seller's name changes, the application sends one purge:

POST /service/{service_id}/purge/seller-441

and every cached object tagged seller-441 is invalidated, wherever it is: the product page, the seller storefront, the search result fragment, the API response. You did not need to know which URLs those were, which is the entire point.

The equivalents:

Fastly: Surrogate-Key header, purge by key, propagates globally in roughly 150 ms. Purge-all is separate and much blunter.
Varnish: xkey module for the same model, or ban expressions, which are evaluated lazily on lookup and get slower as the ban list grows.
Cloudflare: cache tags on Enterprise plans; Cache-Tag header.
Application caches: you build the index yourself, and Redis makes it easy:

# Writing: store the value and register it under every dependency.
def cache_page(key: str, html: str, deps: list[str], ttl: int = 86400) -> None:
    pipe = r.pipeline()
    pipe.setex(f"page:{key}", ttl, html)
    for dep in deps:
        # A set per dependency, holding the pages that depend on it.
        pipe.sadd(f"dep:{dep}", key)
        # The dep set must outlive the pages it points at, or a purge
        # arriving after the set expires silently does nothing.
        pipe.expire(f"dep:{dep}", ttl * 2)
    pipe.execute()

# Invalidating: one entity changed, remove everything that depends on it.
def invalidate(dep: str) -> int:
    keys = r.smembers(f"dep:{dep}")
    if not keys:
        return 0
    pipe = r.pipeline()
    for k in keys:
        pipe.delete(f"page:{k}")
    pipe.delete(f"dep:{dep}")
    pipe.execute()
    return len(keys)

The failure mode to design against is right there in the comment: the dependency index must live at least as long as the entries it tracks. If dep:seller-441 expires before page:product-8821, the purge finds an empty set, deletes nothing, and the page serves a stale seller name until its own TTL runs out. This bug is subtle, intermittent, and extremely common.

Versioned keys (generational caching)

Instead of deleting anything, make the old key unreachable by including a version in it.

def page_key(product_id: int, seller_id: int) -> str:
    # One round trip fetches all the versions this page depends on.
    v_product, v_seller, v_promos = r.mget(
        f"v:product:{product_id}",
        f"v:seller:{seller_id}",
        "v:promos",
    )
    return f"page:{product_id}:p{v_product}:s{v_seller}:m{v_promos}"

def bump(entity: str) -> None:
    # Every key derived from this entity now points somewhere new.
    r.incr(f"v:{entity}")

Nothing is ever deleted. A write is a single INCR, which is O(1) regardless of how many cached entries depend on the entity, and old entries fall out by TTL or LRU. This is Rails's cache_key_with_version and the "Russian doll caching" pattern, and it is the right answer when the fan-out is large: bumping a category that 50,000 products belong to is one increment rather than 50,000 deletes.

The costs are real and worth naming:

Cache pollution. Superseded entries occupy memory until evicted. With a frequently-changing entity you can fill the cache with garbage.
A read now costs a version lookup. Batch it with MGET, and it is one extra round trip, not fifteen.
Cold after every bump. A version bump invalidates everything derived from that entity simultaneously, so it is a stampede trigger. Pair it with request coalescing or probabilistic early expiry.

Event-driven invalidation from the database

The most robust source of purge events is the database's own change log, because it cannot be forgotten.

Postgres WAL / MySQL binlog
        |  Debezium
        v
   Kafka topic: db.public.sellers
        |
        v
  Invalidation service
        |  reads the change, maps entity -> tag
        v
  CDN purge API  +  Redis dependency purge

The argument for CDC over application-emitted events: an application-emitted invalidation is a line of code someone can forget to write. Every path that mutates a seller must remember to purge, including the admin tool, the batch importer, the data fix someone ran by hand, and the migration. CDC captures all of them because it reads the log, not the code.

The costs: added latency (typically 100 ms to 2 s end to end), one more system to operate, and the mapping from table rows to cache tags has to be maintained deliberately.

Stale-while-revalidate: the pressure valve

Whatever the invalidation strategy, stale-while-revalidate changes what invalidation costs:

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

A request arriving after the fresh window gets the stale copy immediately while the cache refreshes in the background. Nobody waits for the origin. And stale-if-error means an origin outage serves last-known-good rather than a 500.

This is why aggressive invalidation is safe in practice: purging a hot key does not produce a latency cliff if the stale copy can cover the refresh.

Choosing

Is the fan-out from one entity to cached objects LARGE (>1000)?
    -> Versioned keys. One INCR beats 50,000 deletes.

Is the cache at the CDN edge, where you cannot enumerate keys?
    -> Surrogate keys. Purge by tag, the CDN finds the objects.

Is correctness critical and are writes rare?
    -> Event-driven purge from CDC, plus tags.

Is the data genuinely tolerant of being a bit stale?
    -> TTL, and stop. Do not build machinery you do not need.

And the rule that governs all of them: pick the TTL by asking how wrong the data can be if every invalidation mechanism fails. TTL is the backstop, not the strategy, and a system whose correctness depends entirely on purges arriving is one dropped message away from serving a wrong price forever.

A worked example

An e-commerce product page: 400 ms to render, 2 million products, 40,000 requests per second at peak, 15 upstream dependencies. Current state is a 5-minute TTL, which produces a 91 percent hit rate and a five-minute window of wrong prices that the merchandising team has escalated twice.

Step 1: classify the dependencies by change rate and by correctness tolerance.

Entity          Changes/day   Tolerable staleness   Fan-out per change
----------------------------------------------------------------------
price            50,000        0 s   (legal)          1 product
inventory       800,000       30 s   (UX)             1 product
product record   20,000        60 s                   1 product
seller profile      500      300 s                   ~4,000 products
category            20       3600 s                   ~80,000 products
promotion          200         0 s   (campaign start) ~200,000 products
review summary  100,000       600 s                   1 product

That table is the whole design, and building it is the first thing I would do. It shows immediately that one strategy cannot be right for all fifteen, because the fan-out spans five orders of magnitude and tolerance spans four.

Step 2: split the page rather than caching it whole.

/product/8821
  |
  +-- shell (product record, seller, category)   TTL 1h + tags
  +-- price + inventory block                    ESI / client fetch, TTL 10s
  +-- promotions block                           TTL 1h + tag purge on campaign
  +-- reviews summary                            TTL 10m
  +-- recommendations                            TTL 1h, personalised, not shared

The price and inventory block is the only piece that genuinely needs near-real-time freshness, and it is 2 percent of the render cost. Caching it separately for 10 seconds means the expensive 400 ms shell can be cached for an hour.

Step 3: tag what remains.

Surrogate-Key: product-8821 seller-441 category-12 promo-77 promo-91
Cache-Control: public, max-age=3600, stale-while-revalidate=86400

Step 4: use versioned keys where the fan-out is large. A category change touches 80,000 products. Purging 80,000 tagged objects is a large operation and a stampede. Instead the category version participates in the shell's cache key, so a category change is one INCR and the old shells age out.

Step 5: drive purges from CDC, so an admin tool that updates a seller directly still invalidates.

Result, measured on the parts that can be computed:

Before: TTL 300 s uniformly
  Origin renders/sec at peak = 40,000 x (1 - 0.91) = 3,600/sec
  Price staleness: up to 300 s

After: split fragments, 3600 s shell TTL + tag purge
  Shell hit rate ~99.4%; shell renders = 40,000 x 0.006 = 240/sec
  Price block: 10 s TTL on a 4 ms render = cheap even at 4,000/sec
  Price staleness: <= 10 s, and 0 s on an explicit purge
  Origin CPU for the expensive path: down ~93%

And the honest caveat: the fragment split adds complexity and a second request per page, so it is worth it here because the expensive part and the volatile part were different parts. If the volatile input had been inside the expensive render, the answer would have been versioned keys on the whole page and a stampede control, not a split.

Production evidence

Fastly's surrogate-key purging is the reference implementation of tag-based invalidation, and its documented global purge propagation (roughly 150 ms) is what makes "long TTL plus precise purge" a viable strategy rather than an aspiration. The Surrogate-Key header comes from the Edge Architecture spec that Akamai and Fastly both implement.

Varnish's xkey module provides the same model for self-hosted caches, and its documentation is explicit that ban expressions degrade as the ban list grows, because they are evaluated on every lookup, which is the reason tag indexes exist.

Rails's cache_key_with_version and Russian doll caching are the canonical versioned-key implementation: a record's cache key includes its updated_at, so touching a parent invalidates every nested fragment without any explicit purge.

Debezium is the standard CDC path from Postgres, MySQL and MongoDB into Kafka, and using it to drive cache invalidation is a documented pattern rather than an improvisation.

HTTP stale-while-revalidate is standardised in RFC 5861 and supported by Cloudflare, Fastly, Akamai and browsers, which is why it is the safe default rather than a vendor feature.

The debate

The case for tags: precise, no cache pollution, and the CDN does the hard part of finding the objects. When the fan-out per change is small to moderate, it is the cleanest answer and the operational story is simple.

The case for versioned keys: O(1) invalidation regardless of fan-out, no purge infrastructure, no purge that can fail or be dropped, and it works identically in a CDN, in Redis and in process memory. The cost is memory spent on superseded entries.

The case for just using TTLs: every mechanism above is machinery that can break, and a wrong purge is harder to debug than a stale page. If the business can tolerate 60 seconds of staleness, a 60-second TTL is correct and everything else is over-engineering.

My position: classify the dependencies first, then use tags as the default, versioned keys where fan-out exceeds roughly a thousand objects per change, and always a TTL underneath as the backstop. The mistake I see most often is treating this as one decision for the whole page when the inputs differ by orders of magnitude in both change rate and tolerance. The table of entity, change rate, tolerable staleness and fan-out is the actual deliverable, and once it exists the strategy per entity is nearly mechanical.

I would also insist on the backstop TTL even with perfect purging, because a purge is a message and messages get dropped, and the failure mode of a purely purge-driven cache is a wrong value cached forever with no self-healing.

Follow-up Q&A

"How do you invalidate a page with 15 dependencies?" I would not answer for the page, I would answer per dependency, because they differ enormously. First I build a table: for each entity, how often it changes, how stale it can be, and how many cached objects one change touches. Then: tags for the small fan-out, versioned keys where one change touches thousands of objects, a short TTL for the genuinely volatile fields, and a long TTL underneath everything as the backstop. And where the volatile input is cheap to render and the rest is expensive, I would split the fragment rather than choosing one TTL for both.

"Tags or versioned keys?" Fan-out decides it. Tags are precise and leave no garbage, but purging 80,000 objects because a category name changed is both a large operation and a stampede. A version bump is one INCR no matter how many objects derive from it, at the cost of superseded entries sitting in memory until eviction. So: tags below roughly a thousand objects per change, versions above it. At the CDN edge, tags, because you cannot enumerate keys there.

"What breaks in the dependency-index approach?" The index outliving the entries it tracks. If the dep:seller-441 set expires before the pages registered in it, the purge finds nothing, deletes nothing, and the pages go stale until their own TTL. It is intermittent and it is very common. The fix is to give the dependency sets a TTL strictly longer than the entries, and to have the backstop TTL bounded at a value the business can survive.

"Why CDC instead of just purging in the application?" Because an application-emitted purge is a line of code that someone can forget. Every write path has to remember: the API, the admin tool, the bulk importer, the migration, the data fix someone ran by hand at 2am. CDC reads the write-ahead log, so it captures every one of those including the ones that bypass your service entirely. The cost is 100 milliseconds to a couple of seconds of extra latency and one more system to run.

"Doesn't invalidating a hot key cause a stampede?" Yes, and that is why invalidation and stampede control are one design rather than two. stale-while- revalidate means the request after invalidation gets the stale copy immediately and the refresh happens in the background, so nobody waits on the origin. Below that, a lease or single-flight so only one worker regenerates. Without this, a correct invalidation strategy causes the outage that the wrong one avoided.

"What if a purge is dropped?" The TTL catches it, which is exactly why the TTL stays. A purely purge-driven cache with an infinite TTL has no self-healing path: one lost message means one wrong value served forever with no mechanism to notice. I set the backstop TTL to the longest staleness the business can absorb, then treat purges as the optimisation that gets it down to seconds.

Common misconceptions

"Invalidation and eviction are the same thing." Eviction is the cache reclaiming memory on its own schedule; invalidation is you asserting that a value is now wrong. Confusing them leads to designs that rely on LRU for correctness.

"Versioned keys leak memory." They accumulate superseded entries, which LRU reclaims. It is a capacity consideration, not a leak, and it is bounded by the cache size.

"A short TTL is a dependency strategy." It is a bound on how wrong you can be, not a mechanism for being right. At the TTLs required for real correctness, the hit rate collapses and you have paid for a cache that is not caching.

"Purge everything is a reasonable fallback." At CDN scale, purging all leaves your origin serving a cold cache under full production load, which is a self-inflicted thundering herd. It is a break-glass operation with a real blast radius, not a routine tool.

Interview delivery note

Refuse the single-answer framing immediately, because that is the depth signal: "I wouldn't pick one strategy for the page, because the fifteen dependencies differ by orders of magnitude. The first thing I'd build is a table: per entity, how often it changes, how stale it can be, and how many cached objects one change touches. Price changes fifty thousand times a day with zero tolerance and a fan-out of one. A category changes twenty times a day, tolerates an hour, and touches eighty thousand products. Those need different mechanisms."

Then the mechanisms, with the rule for choosing: "Surrogate keys for the small fan-out, so I purge by tag and the CDN finds the objects. Versioned keys where one change touches thousands, because a version bump is one INCR instead of eighty thousand deletes. Short TTL for the genuinely volatile fields. And a long TTL underneath everything as the backstop, because a purge is a message and messages get dropped."

Two lines that separate senior from staff. The fragment split: "and where the volatile input is cheap to render and the rest is expensive, I'd split the fragment rather than compromise on one TTL. Price is two percent of the render cost and needs ten-second freshness; the shell is the expensive part and can live an hour." And the stampede connection: "invalidation and stampede control are one design. stale-while- revalidate is what makes aggressive purging safe, because the request after the purge gets the stale copy immediately while the refresh happens behind it."

The Staff & Team Lead Interview Reference