Cache invalidation and update strategies

"There are only two hard things in Computer Science: cache invalidation and naming things." — a saying usually attributed to Phil Karlton

When data changes in the database, cached copies become stale. The cache update strategy decides when the cache learns about the change, and so what you trade between write speed, read speed and staleness.

---

The four canonical cache update strategies

1. Cache-aside (lazy loading)

The application talks to both the cache and the database; the cache never talks to the database:

• Read path: Look in the cache; on a miss, load from the database, add the entry to the cache (usually with a TTL), and return it.
• Write path: Write to the database, then delete the cache entry so the next read reloads it. Facebook's memcache works this way.
• Pros: Only requested data is cached; later reads of it are fast. If the cache fails, the application still works, just more slowly.
• Cons: Each miss costs three trips (cache, database, cache). Data can be stale until its TTL expires. A replacement cache node starts empty, so latency rises until it warms up.

2. Write-through

The application uses the cache as its main data store; the cache reads from and writes to the database:

• Write path: Write the entry to the cache, which writes it synchronously to the database before returning.
• Pros: Data in the cache is not stale, and reads of just-written data are fast.
• Cons: Every write is slow (users usually tolerate slow updates better than slow reads). A new cache node holds nothing until entries are written again (combining with cache-aside helps), and much of what is written may never be read (a TTL helps).

3. Write-behind (write-back)

Write the entry to the cache, which writes it to the database asynchronously:

• Pros: Faster writes, and the cache can combine several updates before writing.
• Cons: Data is lost if the cache goes down before its contents reach the database, and it is more complex to build than cache-aside or write-through.

4. Refresh-ahead

The cache automatically refreshes recently accessed entries shortly before they expire:

• Pros: Lower latency than read-through, if the cache accurately predicts which items will be needed.
• Cons: Poor predictions can make performance worse than not refreshing at all.

---

Invalidation vs. update: why delete, not set, on write

A common anti-pattern is attempting to update the cache on write:

// ANTI-PATTERN (Vulnerable to Race Conditions):
await db.updateUser(user);
await cache.set(user.id, user); // WRONG!

If Thread A and Thread B update the same record concurrently:

1. Thread A writes $V_1$ to Database.
2. Thread B writes $V_2$ to Database.
3. Thread B updates Cache to $V_2$.
4. Thread A (delayed by network jitter) updates Cache to $V_1$.
5. Result: Database has $V_2$, but Cache has $V_1$. The cache is permanently corrupted!

Better pattern: delete (invalidate) the cache key after the database write. Deletes are idempotent, so repeating or reordering them is harmless:

await db.updateUser(user);
await cache.del(user.id); // the next read reloads the current value from the database

Deleting does not close every gap. A reader can miss, read $V_1$ from the database, stall, and then put $V_1$ back into the cache after a writer has stored $V_2$ and deleted the key: a stale set. Facebook's memcache fixes this with leases: on a miss the cache hands the reader a token, a delete invalidates outstanding tokens, and a set with an invalidated token is rejected. The same leases also limit thundering herds (next lesson).