Cache Invalidation: Races, Leases, Versions and Dependencies

What you'll learn: By the end of this lesson you will be able to split "cache invalidation" into its three separate problems (the signal, the dependencies and the ordering), list the races that leave stale data in a cache even when every write deletes the key, close the main one with a lease and say what that costs, find the entries that depend on one change with tags or generation numbers, make the signal survive crashes, and keep a hard bound on how wrong a cache can be.

A shop pins a price list at the door, the till and the window. When a price changes, someone must find every copy, and a missed copy shows the old price with no sign that it is wrong. A cache is the same: copies near the reader, and a source of truth that does not know where they are.

Caching basics and advanced caching cover write policies, TTLs, delete versus update and stampedes; the four layers and eviction policies cover where copies live and what leaves a full cache. This lesson takes one question further: how does a cache learn that an entry is no longer true, and what goes wrong between the change and the news?

Verified against the Redis documentation (client-side caching and scripting pages), RFC 9111, the memcache paper from NSDI 2013 and the Fastly surrogate-key guide, read on 2026-11-08.

The core idea

Invalidation is three problems that share a name.

1. The signal. Something must tell the cache that data changed. Signals can be lost, duplicated, late or sent before the change is visible.
2. The dependencies. One change usually makes several entries wrong: a product page, a category list, a search result, a cart total.
3. The ordering. Readers keep filling the cache while the signal travels. A reader that read the old value before the change can write it in after the signal has passed.

The saying that cache invalidation is one of the two hard problems in computer science is credited to Phil Karlton (Martin Fowler's page records the attribution and says he could not find a satisfactory URL for it). Three examples run through the lesson: a minimal example (a scripted reader and writer, with and without a lease), a realistic example (a ShopStream price change) and a failure example (the signal itself getting stuck).

Problem 1: the signal

RFC 9111 section 4.4 says a cache must invalidate the target URI when it receives a non-error response (2xx or 3xx) to an unsafe method such as PUT, POST or DELETE, may also invalidate the URIs in Location and Content-Location, and must not invalidate a URI of another origin. The result is not global: a browser or CDN node the request never passed through keeps its copy.

The sturdiest source is the log, and the memcache paper (NSDI 2013) shows it. SQL statements that change authoritative state are amended to name the cache keys to delete once the transaction commits. A daemon on each database inspects the statements it commits, extracts the deletes and broadcasts them to the cache servers. Because the keys travel in statements the database stores in reliable logs, the daemon can replay invalidations that were lost or misrouted. A signal derived from a durable log can be replayed; one sent from a request handler cannot.

Redis client tracking moves the bookkeeping to the server, which remembers the keys each connection read and sends an invalidation when one is modified, evicted or expires. The table of tracked keys has a maximum size; when it is full the server may invalidate a key that did not change, to free memory.

Problem 2: the dependencies

A milk price change touches product:42, category:dairy:page:1, search:results:milk and every cart that caches a total. The writer knows the row it changed, not the entries built from it. Three techniques bridge the gap.

• Enumerate in the writer. Simple and brittle: each new listing needs every writer updated.
• Tags (surrogate keys). Each cached object carries labels for the entities it depends on, and invalidating a label removes every object that has it. Fastly's feature works this way: the origin adds a Surrogate-Key response header with one or more keys, and one key purge removes every object tagged with it. The relation is many-to-many. The documentation states limits: a key token may not exceed 1 KB and the header value may not exceed 16 KB, and tokens past a limit are ignored. An application cache can copy the idea with a set per tag, but those sets are cached state that can go wrong too.
• Generation numbers. Put a counter in the key, category:dairy:g12:page:1. To invalidate the group, increment the counter; old entries are never read again and age out. The cost is an extra lookup per read and some garbage. If readers cache the counter for a few seconds to save the lookup, those seconds become staleness.

Figure 1. Choosing a dependency technique. How to read this: take the first branch that fits. Deleting known keys is exact, tags reach objects you cannot list, generations reach whole groups, and a TTL reaches anything, slowly.

Problem 3: the ordering

The advanced caching lesson shows one race: a reader misses and reads the old row, a writer commits and deletes the key, and the slow reader then fills the old value in. The memcache paper calls it a stale set: a value in the cache that does not reflect the latest value that should be cached. It is not the only race.

The lagging-replica row is reasoning from asynchronous replication: a refill from a replica can read an old row after the key was deleted. The memcache paper describes a cousin: a client in a cold cluster that reads from a warm cluster can get a value before the warm cluster has received the invalidation. Its mitigation is a delete with a hold-off, two seconds by default, during which the cache rejects add operations for the key; a refill that fails tells the client newer data exists.

The early-signal row is documented for Redis client-side caching. When the invalidation arrives on one connection before the data reply on another, the client would cache a value that is already wrong. The page's fix is a placeholder, "caching in progress", set before the read: an invalidation deletes it, and a data reply that finds no placeholder is not stored.

A lease makes the fill conditional

A lease is a token handed out on a miss. The cache accepts the later fill only if the token is still valid, and a delete voids any token outstanding for the key. The memcache paper describes it as a 64-bit token bound to the key, with verification failing if memcached has invalidated the token on receiving a delete, and compares it to load-link and store-conditional. It also limits stampedes: by default a server hands out a token for a key once every 10 seconds, and other readers are told to wait briefly and retry. For a set of keys prone to stampedes, measured over one week, the paper reports a peak database query rate of 17,000 per second without leases and 1,300 with them. Those numbers belong to that system.

The code is the core of a lease in a toy cache. The scenario around it is the minimal example: a reader misses, reads price 3.99 and stalls; a writer commits 3.49 and deletes the key; the reader then tries to fill.

Reply get(String key) {
    String hit = values.get(key);
    if (hit != null) {
        return new Reply(hit, 0);
    }
    long token = nextToken++;
    leases.put(key, token);
    return new Reply(null, token);
}

boolean setWithLease(String key, String value, long token) {
    Long current = leases.get(key);
    if (current == null || current != token) {
        return false;
    }
    values.put(key, value);
    leases.remove(key);
    return true;
}

void delete(String key) {
    values.remove(key);
    leases.remove(key);
}

Output of the scripted scenario, run as a single-file Java program (Java 26.0.1, 2026-11-08), once with an unconditional fill and once with the lease:

plain fill: reader's late fill of 3.99 stored; cache holds 3.99, database holds 3.49
lease fill: reader's late fill of 3.99 refused; cache holds null, database holds 3.49

Figure 2. The stale-fill race with a lease. How to read this: the only change from the unprotected sequence is the token on the last write. The delete removes the value and cancels every fill that began before it.

A lease costs per-key state in the cache, a changed protocol (the get returns a token, the set sends it) and a decision for the reader whose fill is refused: serve what it read, which is old, or read again. The Redis pages read for this lesson describe no lease command, so a team using Redis builds the same check with an atomic step: the scripting documentation says a script runs atomically and blocks other server activity meanwhile, so a script that compares a stored version before writing makes a fill conditional.

Figure 3. The states of a key. How to read this: "Filling" is the window in which a stale fill is possible. A lease turns that window into a state a delete can cancel.

Bounding the damage

Every design above can still fail, so bound how wrong the cache can be instead of claiming it is never wrong.

• A TTL on every entry. The Redis page advises a maximum TTL on every key, even one with none, to protect against bugs or connection problems that leave old data in the client. The TTL is the contract.
• A flush when the signal path breaks. Redis's guidance is to flush the local cache if the invalidation connection is lost, and to ping that connection so a silent break is noticed.
• A replayable signal, so a consumer that was down catches up.
• An audit. Sample a small share of hits, read the same keys from the database and count mismatches. This is a design suggestion, not from a source: the mismatch rate shows whether invalidation works, which hit rate cannot.

The other side of this topic

The browser holds copies the server cannot reach, so HTTP relies on freshness lifetimes, revalidation and versioned URLs there. The Frontend System Design track covers that side (no link: it is not published yet).

In practice: a price change across a product page, a category list and search

This is the realistic example, an educational scenario on ShopStream. Nothing in it describes a real company, and every figure is illustrative.

This is a realistic scenario, not a case history.

The situation

A store changes the price of a litre of milk. ShopStream serves the product page fragment from Redis behind a CDN, a category listing that embeds the price, and cached search responses. Deletes exist only in the product service. The product owner's tolerance, set for this exercise: a price must be correct within one minute everywhere, and checkout always reads the database.

Starting architecture

Figure 4. The starting point: one delete, other copies learn nothing. How to read this: only the product key in Redis is invalidated. The category and search entries in Redis, and the CDN pages, hold the old price until their TTLs end.

Options considered

The decision

Option C, with a TTL as the backstop. The catalogue service writes the change and an outbox row in one transaction (see message queues). A consumer reads the outbox, deletes the Redis keys derived from the product and its category, and purges the CDN by tag if the CDN supports tags; product pages carry Surrogate-Key: product-42 category-dairy. The product key uses a lease. Every Redis entry keeps a 10-minute TTL (illustrative), so even a total pipeline failure is bounded.

Rollout and verification

The consumer first runs in shadow mode, comparing the keys it would delete with what the product service deletes today, then takes over per category. An audit job samples hits, reads the price from PostgreSQL and counts mismatches. Metrics: invalidation lag (commit to delete), consumer backlog and mismatch rate, with an alert at half the one-minute promise.

The 2 a.m. failure

The consumer is stuck on one malformed event; its backlog grows and category prices stay stale beyond a minute while the mismatch rate climbs. Mitigation: skip or fix the event and let the consumer replay (the source is durable, so nothing is lost), and purge the affected tags by hand. The lasting fix is a dead-letter path for bad events, an alert on lag, and a fallback: when lag passes the promise, shorten TTLs for the affected keys until the backlog clears.

Architect's notes

• State the staleness contract per data type first: "prices within a minute, stock at checkout exact". The mechanism follows from the number.
• Keep the TTL. It turns an unbounded failure into a bounded one.
• Measure the mismatch rate, not only the hit rate.

Common mistakes

• Deleting before the commit.
• Believing a delete stops a reader that started earlier from filling.
• Refilling from a lagging replica straight after an invalidation.
• Updating the cache with set from two writers and trusting arrival order.
• Sending invalidations only from the request handler, with no replay, and leaving out the TTL because "we invalidate on every write".

Key takeaways

• Invalidation is three problems: the signal, the dependencies and the ordering.
• A signal derived from a durable log can be replayed; one sent from a request handler cannot.
• A delete does not stop a reader that started earlier from filling an old value (a stale set).
• A lease or version check makes the fill conditional, at the price of per-key state and a protocol change.
• Tags and generation numbers find dependents you cannot list by hand, each with its own bookkeeping.
• Put a TTL on every entry, distrust the cache when the invalidation channel breaks, and audit hits against the source of truth.

Practice exercises

Exercise 1 (30 min). Draw the delete-before-commit race as a sequence diagram and mark the line after which the stale value is in the cache.

Exercise 2 (45 min). Add an expiry to the lease tokens in the code above. What should a reader do when its fill is refused because the token expired rather than because of a delete?

Exercise 3 (1 hour). List every cached entry that depends on a ShopStream product's price, and choose enumerate, tag or generation for each.

Exercise 4 (1 hour). Write the audit job in pseudocode, including how to avoid flagging an entry that changed a moment ago.

Exercise 5 (2 hours). Design the Option C consumer: offsets, a malformed event, and a failed CDN purge call.

Related reading

• Caching Basics and Advanced Caching.
• Cache Layers: Client, CDN, App, Database.
• Eviction Policies: LRU, LFU and TTL.
• Replication and Message Queues.
• ShopStream: scale reads.

Official documentation

• Nishtala et al., Scaling Memcache at Facebook (NSDI 2013): leases, stale sets, the invalidation pipeline, delete hold-off.
• IETF, RFC 9111: HTTP Caching, section 4.4, invalidating stored responses.
• Redis documentation, Client-side caching reference: tracking, races, lost connections.
• Redis documentation, Scripting with Lua: atomic script execution.
• Fastly documentation, Working with surrogate keys.
• Martin Fowler, Two Hard Things: the attribution of the saying.