Cache Invalidation: The Delete Ran, and the Page Is Still Wrong

📺 Prefer to watch? 90-second YouTube Short · 💬 Telegram

Originally published on software-engineer-blog.com.

The ticket that makes no sense

A user changes her email address. The form says saved.

She reloads the page. The old address is still there.

You go and look, because you wrote this code and you know it is fine. The database has the new value. You check the logs: the UPDATE returned ok. The cache delete right after it returned ok too. There is no exception, no timeout, no retry, no failed job sitting in a queue. Every single call in that request succeeded.

And the cache is still holding the old email, with five minutes left on its timer.

Nothing failed. Nobody forgot anything. So what actually happened?

---

What this article covers, and what it does not

Three things are covered:

1. Why an invalidation that provably ran can leave a stale value behind — and why the delete was not too late, it was too early.
2. The three moves that fix it, in order, each one measured rather than asserted.
3. The honest limit: the class of cached answers you cannot invalidate at all, and what the workaround costs.

Five things are deliberately not covered, because each one is its own subject and gets confused with this one:

• This is not the dual-write problem. That is the case where the second write never happened — the database committed and the cache call died. Here the cache call ran and returned successfully. If your failure mode is a lost second write, you want an outbox, not this article.
• This is not the write path. Write-through and write-back are about whether writes go through the cache at all. Everything below assumes cache-aside: your application code reads the cache, falls back to the database, and fills the cache itself.
• This is not the stampede. Invalidating a hot key sends every waiting reader to the database at the same instant. That is a real and separate cost, and it is a real and separate article.
• This is not eviction. LRU and LFU decide what to throw away when memory runs out. Eviction is about space. Invalidation is about truth. They both remove keys and that is the entire similarity.
• This is not HTTP caching. No browser caches, no ETag, no max-age, no CDN purge. Everything here happens on your side of the wire, inside your own service.

---

One system, drawn once

There are exactly three things, and everything below is a mutation of this picture.

A service. Beside it a cache — say one Redis. Under it a database — say one Postgres primary. The service talks to both. The cache and the database never talk to each other. Nothing keeps them in step except the code you write.

The read path:

# every read goes through here. ex=300 is five minutes.
def get_user(user_id):
    key = "user:" + str(user_id)
    hit = cache.get(key)
    if hit is not None:
        return hit          # a hit. No database call.
    row = db.query_one(
        "SELECT * FROM users WHERE id = %s", (user_id,))
    cache.set(key, row, ex=300)  # a miss. Fill it back.
    return row

And the write path — the one in the ticket:

# the write path. Two calls, and both of them succeed.
def change_email(user_id, new_email):
    db.execute(
        "UPDATE users SET email = %s WHERE id = %s",
        (new_email, user_id))
    cache.delete("user:" + str(user_id))
    return "saved"

# Order matters. Database first, cache second.
# Delete before the commit and a reader can refill the
# key from the old row before the new one is even there.

Look at those two functions. They are correct. That is the point of the article.

---

The race: the delete was too early

Put a second person in the picture. Not a second writer — a reader, doing nothing unusual.

Follow one clock:

1. A read arrives. Cache miss.
2. That reader runs SELECT and gets the old row. It is now holding that value in a local variable, on its way to cache.set.
3. The writer commits UPDATE. The database now holds the new value.
4. The writer runs DELETE user:42.
5. The reader — a couple of milliseconds late — finally runs cache.set(key, old_row, ex=300).

The database says new. The cache says old. And the cache has a full five-minute timer ahead of it, because step 5 set a fresh one.

Here is the part that surprises people, measured on a real Redis 7.4.9 rather than reasoned about. In step 4, the delete returns:

4. writer DEL user:42 -> DEL returned 0
   (key existed before = 0, exists after = 0)

Zero. The delete removed nothing, and it removed nothing because there was nothing there yet. The stale value was still in flight inside another thread. You cannot delete a value that has not been written.

Say that out loud, because it is the whole idea: the invalidation was not too late. It was too early.

And it is not a fluke of the cold cache. A second run was built where a different reader had already cached the old value, so the delete had a real victim and returned 1. Same ending: database new, cache old, five minutes on the clock. A delete that provably removed a real key is still undone by one slow reader.

How often, honestly

The tempting thing to do here is put a percentage on the screen. It would be wrong, because there is no single rate. The rate is a ratio:

how long a reader takes between reading the row and writing it to the cache, over how often writes arrive.

Timing every step of 5,000 runs, that predicate predicted the actual outcome 99.8–100% of the time — the mechanism is verified, not assumed. But the rate moved enormously with database commit latency:

Reader gap (row read → cache set)	With a ~3.3 ms fsync commit	With a ~0.02 ms commit
0 ms	0 / 500 (0.00%)	1 / 500 (0.20%)
2 ms	0 / 500 (0.00%)	56 / 500 (11.20%)
5 ms	31 / 500 (6.20%)	122 / 500 (24.40%)
10 ms	148 / 500 (29.60%)	264 / 500 (52.80%)
20 ms	400 / 500 (80.00%)	416 / 500 (83.20%)

Below a 3 ms gap with slow commits it is literally 0/500, because the writer physically cannot finish before the reader has already filled the cache. Make your database faster and the window opens. This is not a bug you can benchmark your way out of.

The case that actually hurts

Under continuous writes to the same row this heals itself — the next writer's delete clears the poisoned key. Measured under eight readers and one writer hammering the same row, the cache held a wrong value at 0.43% of sampled instants, and 0.48% of hits were wrong: about 68 wrong answers in six seconds, in short bursts.

The dangerous case is the opposite one. A row nobody writes again. A profile edited once. A price changed once. A feature flag flipped once. There is no next writer to heal it, so the wrong value sits there for the entire remaining TTL, answering every read.

That is the common case, and it is the expensive one.

---

Move 1: delete, do not update

The first instinct after seeing this is to make the write path more authoritative: I already know the new value, so let me put it straight into the cache.

# tempting, and wrong: it writes a value you computed
def change_email_bad(user_id, new_email):
    row = db.update_and_return(user_id, new_email)
    cache.set("user:" + str(user_id), row, ex=300)

# what you actually want: it writes no value at all
def change_email_ok(user_id, new_email):
    db.execute(
        "UPDATE users SET email = %s WHERE id = %s",
        (new_email, user_id))
    cache.delete("user:" + str(user_id))

Why the first one is worse: two writers can commit in the order A then B, and have their cache writes arrive in the order B then A. The database ends holding B, which is right. The cache ends holding A — a value that nobody wrote last — and it holds it for a full TTL.

Two concurrent writers, 1,500 runs each way:

Policy	Cache order ≠ commit order	Cache ≠ database at the end
write, then SET	590 / 1500 (39.33%)	589 / 1500 (39.27%)
write, then DELETE	573 / 1500 (38.20%)	0 / 1500 (0.00%)

The reorder happens just as often either way — 39% versus 38%, that is the same physics. Under SET, essentially every reorder produced a wrong cache. Under DELETE, none did, because a delete carries no value to get out of order. It says "whatever is there is now suspect", and the next reader re-reads the truth.

Two honest qualifications.

It costs you a miss. That miss is priced:

Setup	Hit	Miss (get + select + set)	Extra cost of the miss
Local database, no network	91.9 µs	176.4 µs	+84.6 µs
With a 5 ms database round trip	77.5 µs	6.91 ms	+6.84 ms, once

Seven milliseconds, one time. Compare that against what the SET policy buys you in the next section: five figures of wrong answers.

And it does not fix everything. DELETE removes the writer-versus-writer reorder completely. It does not remove the read-path race from the section above — that one is still there, and it is what versioned keys and a sane TTL are for.

---

Move 2: put a version in the name

The second problem is not correctness, it is bookkeeping. One user does not have one cached key. She has a profile, her settings, five pages of feed, her friends list, her badges, her unread count, her avatar. Eleven keys, in this example.

When her row changes, which of those do you delete?

You could hunt. Measured on a 200,000-key cache:

How you find them	Wall time	Round trips	Cost
All 11 in one variadic DEL	0.16 ms	1	you must know all 11 names
11 named DELs, one at a time	1.93 ms	11	you must know all 11 names
KEYS user:42:*	12.4 ms	1	blocks the whole server
SCAN MATCH user:42:* COUNT=1000	58.0 ms	200	safe, but 200 trips
KEYS *	299.7 ms	1	blocks the whole server

The reason KEYS is disqualified is not its own runtime. Redis executes commands on a single thread, so while KEYS * runs, everyone else waits. Latency of an unrelated GET from a second client, measured during it:

Server state	p50	p99	max
idle	0.079 ms	0.177 ms	0.279 ms
while KEYS * runs	0.721 ms	246.9 ms	516.2 ms

An unrelated GET got 1,851× worse at the tail. SCAN exists precisely so you never do that.

But look again at the top row of the hunt table. If you genuinely know all eleven names, one variadic DEL does it in 0.16 ms — faster than any alternative here. So the cost of the hunt was never round trips.

The cost of the hunt is knowing the names. They are scattered across a codebase, built by string concatenation in six different modules, and the bug is always the twelfth key somebody added last month and forgot to add to the list. The list is the bug.

So stop keeping a list. Put a version in the name instead:

# the key carries a version number for that one user
def key_for(user_id, part):
    v = cache.get("user:" + str(user_id) + ":ver") or 1
    return "user:%s:v%s:%s" % (user_id, v, part)

# invalidating every derived key for one user
def invalidate_user(user_id):
    cache.incr("user:" + str(user_id) + ":ver")

# One call. Every old key is now unreachable, because
# nothing composes those names any more. You never had
# to know how many there were, or what they were called.

One INCR, 0.701 ms, one round trip. Keys a v8 reader can still reach: 0 of 11. Not because they were deleted — because nothing constructs those names any more.

The honest cost: orphans

Nothing about this is free, and the bill is memory.

After the bump, all 11 of 11 old keys are still resident, with 3,600 seconds of TTL left on them. Nothing reclaims them early. They held 16,552 bytes for one user — about 1,505 bytes per key. Scale that: 100,000 users bumping once is roughly 1.7 GB of unreachable data sitting in your cache until it expires.

That is only survivable under one of two conditions: every versioned key has a TTL, or your maxmemory-policy is an LRU/LFU variant that will evict them. Redis defaults to noeviction, which means an orphan pile eventually stops accepting writes rather than making room.

Versioning trades memory you cannot reach for invalidation you cannot get wrong. That is usually a good trade. It is not a free one.

---

Move 3: the timer is a backstop, not a plan

Every cache line you write has an ex=, and it is the most misunderstood argument in the file.

# the TTL is not the plan. It is the bound.
cache.set(key, row, ex=300)

# what that one argument actually promises:
#   it does NOT make the copy correct
#   it DOES cap how long a wrong copy can live
#   so pick it from what a stale answer costs you,
#   not from how much memory you happen to have

# and this line says: be wrong forever
cache.set(key, row)

A TTL has never once made a cached value correct. All it does is put a ceiling on how long a wrong one is allowed to keep answering. So price it that way. One incident, one poisoned key, fifty reads a second:

TTL	Wrong answers served	Self-heals?
5 s	251 (measured)	yes, after 5.02 s
10 s	500 (measured)	yes, after 10.00 s
30 s	1,500 (measured)	yes, after 30.00 s
5 min	~15,000 (extrapolated)	yes
1 hour	~180,000 (extrapolated)	yes
none	unbounded	no

The measured rate came out at 50.07 wrong answers per second of TTL at fifty reads a second — linear enough that the extrapolations are safe. And the rate is what makes the number mean anything: "fifteen thousand" is only true at fifty reads a second, on a row nobody writes again.

Which reframes the question you should be asking. Not "how long can I cache this for?" but "how many wrong answers is this row worth?" A stale marketing headline: thousands, fine. A stale account balance, permission check, or price: the honest answer might be zero, and that is a signal not to cache that read at all.

The last line in that snippet — cache.set(key, row) with no expiry — is a promise to be wrong forever if anything ever goes sideways. It is worth grepping for.

---

The limit: you cannot invalidate what you cannot name

Everything above assumes the cached value has a name derived from the thing that changed. user:42:profile obviously belongs to user 42.

Now cache a search result. The key is a hash of the query — search:results:<sha1> — and the value happens to contain twenty user records. Or cache leaderboard:top10, computed from every score in the system.

User 42 changes her name. Which keys do you delete?

There is no answer. The key name is a function of the query, not of user 42. leaderboard:top10 does not mention a user at all. Every classic move above is unavailable, because all of them start with a name.

The only way back is to write the mapping down as you fill the cache:

# when you cache a COMPUTED answer, write down which
# rows it was built from. That list is the only way
# back from a changed row to the keys holding it.
def cache_search(query_key, rows, result):
    cache.set(query_key, result, ex=300)
    for r in rows:
        cache.sadd("tag:user:" + str(r.id), query_key)

# when a row changes, read its list and delete them
def invalidate_row(user_id):
    tag = "tag:user:" + str(user_id)
    for key in cache.smembers(tag):
        cache.delete(key)
    cache.delete(tag)

Over 5,000 cached search pages, finding the 40 keys that embed user 42:

Approach	Found	Time	Round trips
Brute force: scan, fetch and parse all 5,000 values	40	40.8 ms	10 scans + 5,000 values parsed
Tag set: SMEMBERS tag:user:42 then delete	40	0.860 ms	3

47× faster, and the gap widens as the keyspace grows, because the tag lookup does not care how many keys exist.

And here is what it costs, which is the part usually left out:

• 20× write amplification. Building the index for those 5,000 pages took 100,000 SADD calls — one per embedded entity, on every single cache fill.
• +130% memory. 2.58 MB of cached pages became 5.93 MB. The reverse index more than doubled the workload.
• Dangling members forever. After invalidating user 42, the neighbouring tag:user:43 set still listed two keys that no longer exist. Nothing cleans them. Tag sets grow without bound unless you also keep a key → tags reverse map (doubling the write amplification again) or put a TTL on the tag sets themselves.

Tags turn an impossible problem into a solvable but expensive one, and they introduce a second garbage-collection problem of their own. That is the trade. Make it deliberately, on the handful of computed keys that actually need it — not as a default for everything.

---

The same problem, wearing an AI hat

If you are serving an LLM application, you already have three caches and probably have not named them as caches.

The semantic cache is the unnameable-key problem, exactly. You store an answer under an embedding of the question so that a similar question can reuse it. Now a document changes, or a price changes, or a policy changes. Which cached answers were built from that fact? The key is a vector derived from the question — it says nothing about which sources produced the answer. There is no name to delete. This is the search-result case from the section above, and the way out is the same: record which retrieved chunks fed each cached answer, tag by source document, and accept the write amplification. If you cannot afford that bookkeeping, the honest fallback is a short TTL, priced by the table above — how many wrong answers is this document worth?

The RAG index is derived data with a version. Re-embedding after a chunker change, an embedding-model swap, or a bulk document update is the version bump from move 2 — a new index name, atomically switched, rather than a hunt for which vectors are stale. The orphan bill is the same too: the old index stays resident and costs money until something deletes it.

And the write-then-delete rule survives intact. Two pipelines that re-embed the same document concurrently can have their index writes land in the opposite order to their source commits, leaving the index holding a vector nobody wrote last. Invalidating the entry and letting the next read re-embed removes that class of bug for the price of one miss — and in this setting the miss is a real embedding call, so it is worth measuring rather than assuming.

The provider-side prompt cache is the one you do not control: it has its own timer and its own key derivation, so treat it as a bound you were given, not a plan you made.

---

The verdict

The delete ran. That was never the problem.

Invalidation fails because of ordering, not omission: a reader that read before the write and wrote after it, holding a stale value in a variable across the exact moment the delete fired. The delete was too early, not too late.

So, in order:

1. Delete, never update. 589 divergences in 1,500 runs the other way, zero this way. It costs one miss — about 7 ms once, against a five-figure count of wrong answers.
2. Put a version in the name when a row has many derived keys. Not because it is faster — a variadic DEL beats it — but because you never needed the list of names, and the list was always the bug. Budget for the orphans, and give every versioned key a TTL.
3. Treat the TTL as a bound, and choose it from what a wrong answer costs rather than from how much memory you have. A cache line with no ex= is a promise to be wrong forever.

And then the limit: you cannot invalidate what you cannot name. For computed answers — search results, leaderboards, semantically cached LLM responses — either write down the mapping and pay for it, or admit you are relying on a timer and price that timer honestly.

The two-hard-things joke gets repeated because it is funny. The real reason invalidation is hard is duller and more useful: a cache is a second copy of the truth, kept in step by nothing but your own code, on a clock that two independent parties are writing to at once.

---

References and further reading

On the pattern itself

• Microsoft, Cache-Aside pattern, Azure Architecture Center — the pattern every code sample above assumes: the application, not the cache, is responsible for loading data on a miss and for removing it when the underlying data changes, with the consistency caveats stated plainly: learn.microsoft.com/azure/architecture/patterns/cache-aside

On deleting rather than updating, and on the read-path race

• Rajesh Nishtala et al., Scaling Memcache at Facebook (USENIX NSDI, 2013) — the production argument for deleting cached data instead of updating it (deletes are idempotent, so concurrent invalidations cannot reorder into a wrong value), and the "stale set" race in which a reader holding an old value writes it back after the invalidation — the exact failure this article opens on, which is why the paper introduces leases to close it: usenix.org/system/files/conference/nsdi13/nsdi13-final170_update.pdf

On finding the keys, and why KEYS is disqualified

• Redis, SCAN command reference — the cursor-based iteration guarantees, and the explicit warning that KEYS may block the server for a long time on a large keyspace, which is what the tail-latency measurement above shows in practice: redis.io/docs/latest/commands/scan

On what a TTL actually promises

• Redis, EXPIRE command reference and key expiration semantics — how expiry is stored with the key, how it is cleared by a write that replaces the value, and the lazy plus active expiration model that decides when the key really goes away: redis.io/docs/latest/commands/expire

On the orphans left behind by versioned keys

• Redis, Key eviction and maxmemory-policy — the available policies and the fact that the default is noeviction, which is why unreachable versioned keys are only reclaimed by their own TTL and can otherwise fill the instance until writes start failing: redis.io/docs/latest/develop/reference/eviction

On caches as derived data — the "cannot name it" limit

• Martin Kleppmann, Designing Data-Intensive Applications (O'Reilly, 2017), ch. 11 "Stream Processing", sections on change data capture and derived data — a cache is a derived view of a system of record, and keeping derived views correct by ad-hoc writes scattered through application code is precisely what produces the inconsistencies above; a single ordered stream of changes is the alternative framing.

If a reference you would expect is missing, say so in the comments and I will add it.

---

Watch the full episode: Cache Invalidation — Explained in Detail · the short version