# Cache Invalidation

> "There are only two hard things in Computer Science: cache invalidation and naming things." — Phil Karlton

## 1. The Problem

The moment you copy data into a cache, there are two versions of the truth. **Invalidation** is how you make the cached copy stop being served once the source changes. Get it wrong and users see stale prices, deleted posts, revoked permissions — or, worse, data that belongs to someone else.

There are three basic strategies, and real systems combine them:

| Strategy | How | Staleness bound | Cost |
|---|---|---|---|
| **Expiration (TTL)** | every entry dies after N seconds | ≤ TTL | simplest; stale for up to TTL (`07-ttl/`) |
| **Explicit invalidation** | on write, delete/update the cached key(s) | ~0 (if it works) | must know every key affected by a write |
| **Versioned keys** | include a version in the key; bump the version on write | 0 for new readers | old entries linger until evicted/TTL |

## 2. Explicit Invalidation: Delete, Don't Update

On a write, the safest default is to **delete** the cache entry and let the next read repopulate it:

```ts
async function updateProduct(id: string, patch: Partial<Product>) {
  await db.products.update(id, patch);       // 1. write the source of truth
  await redis.del(`product:${id}`);          // 2. invalidate
}
```

Why delete instead of `SET` with the new value? Because two concurrent writers can interleave so that the *older* value is written to the cache last:

```
writer A: UPDATE price=10          writer B: UPDATE price=12
writer B: SET cache price=12
writer A: SET cache price=10        ← cache now says 10, DB says 12 — stale until TTL
```

With delete, the worst case is an extra miss. (Order matters too: write the DB **first**, then delete. Deleting first lets a reader refill the cache with the old value before the DB write lands.)

## 3. The Remaining Race — and Delayed Double Delete

Even "update DB, then delete" has a narrow race with a concurrent **reader**:

```
reader: cache miss → SELECT price (gets OLD 10)
writer: UPDATE price=12 → DEL cache
reader: SET cache price=10          ← stale value written after the delete
```

Mitigations, in increasing strength:

1. **Always set a TTL** — bounds how long any such race can last.
2. **Delayed double delete** — delete again ~a second after the write, catching late refills.
3. **Version/compare-and-set on fill** — readers only write the cache if the version they read is still current (e.g. `SET key value` only if `key:version` matches, via a Lua script).
4. **Invalidate from the database's change stream** (CDC, below) — a single ordered source of invalidations.

## 4. Knowing *Which* Keys to Invalidate

A product edit doesn't just affect `product:42`. It may affect `category:7:page:1`, `search:shoes`, `homepage:featured`, and a rendered fragment in three languages. Options:

- **Tag-based invalidation**: when caching, record which entities an entry depends on (`tag:product:42 → {category:7:page:1, homepage:featured}` as a Redis SET). On write, delete every key in the tag set. CDNs support this as *surrogate keys* / *cache tags*.
- **Version stamps per entity group**: store `ver:category:7 = 18` and build keys as `category:7:v18:page:1`. Bumping the version orphans every old page at once — no need to enumerate them.
- **Keep derived caches short-lived**: for fan-out-heavy aggregates, rely on a short TTL instead of precise invalidation.

## 5. Event-Driven Invalidation (CDC)

Invalidating in application code has a gap: anything that writes to the DB *without* going through that code (a migration, an admin script, another service) leaves the cache stale. **Change Data Capture** reads the database's replication log (PostgreSQL WAL via Debezium, MySQL binlog) and emits an event for every committed row change. A small consumer turns those into cache deletes:

```
UPDATE products ... COMMIT → WAL → Debezium → Kafka topic "db.products" → invalidator → DEL product:42
```

Because the log is ordered and contains only committed changes, this closes both the "forgot to invalidate" and most of the ordering races — at the cost of extra infrastructure and a little added lag.

## 6. Invalidating Many Caches at Once

With several app instances, each holding an in-process L1 (`04-caching_strategies/` section 2), deleting the Redis key isn't enough. Broadcast invalidations — Redis **pub/sub** or Redis 6+ **client-side caching** (server-assisted tracking: the server remembers which keys each client cached and pushes invalidation messages) — so every instance drops its local copy.

For HTTP caches you don't control, invalidation is either a **purge API** (CDN), or impossible (browsers) — which is why static assets use **content-hashed filenames** (`app.3f9a1c.js`): a new version is a new URL, so the old one never needs invalidating.

## Under the Hood: Why "Update DB, Delete Cache" Is Still Not Linearizable

The database and the cache are two separate systems with no shared transaction. The DB commit and the cache delete are two independent operations separated by network hops; between them, any number of readers can observe "new DB, old cache". And because a cache fill is *read DB → (time passes) → write cache*, a fill that started before the commit can complete after the delete — the race in section 3. No ordering of two non-atomic steps can eliminate this; it can only make the window smaller or bound its duration (TTL).

The only ways to get strict consistency are to (a) **not cache** that data, (b) make the cache a write-through **part of the same consistency protocol** (e.g. a lease or version check on every fill), or (c) route reads that need freshness straight to the primary. Facebook's memcache paper ("Scaling Memcache at Facebook") solves the fill race with **leases**: on a miss, the cache hands the reader a lease token; a delete invalidates outstanding leases, so a stale fill presenting an old token is rejected.

![A reader misses and reads the old value, a writer updates the database and deletes the key, then the slow reader writes the stale value back into the cache; a lease or version check rejects that late fill](diagrams/01-stale-fill-race.svg)

## Common Pitfalls

1. **Updating the cache instead of deleting** — concurrent writers leave the older value cached.
2. **Deleting before writing the DB** — a reader refills the old value immediately.
3. **No TTL "because we invalidate explicitly"** — any missed invalidation becomes permanent staleness.
4. **Forgetting derived keys** — lists, search results, aggregates and translations of the changed entity.
5. **Invalidating only the shared cache** while instances keep L1 copies.
6. **Caching permission/authorization results** without invalidating on role changes — revoked access keeps working.

## Quick Reference

| Situation | Approach |
|---|---|
| single entity changed | write DB → `DEL key` (+ TTL as a safety net) |
| many dependent keys | tags (SET of keys) or versioned key prefix |
| writes from many sources | CDC-driven invalidation |
| many app instances with L1 | pub/sub or client-side-caching invalidation |
| static assets | content-hashed filenames, long TTL |
| must never be stale | don't cache it, or read from primary |