Cache invalidation

A cache is only useful if its copies match the source. Invalidation is the work of removing or replacing copies that no longer match. It is the hardest part of caching, because the cache and the database are two systems that change at different moments.

The big idea

There are four ways a cache finds out that data changed.

1. TTLs. Every entry expires after N seconds. You accept up to N seconds of staleness. This is simple and it backs up every other strategy.
2. Explicit delete on write. The code that changes the data also deletes the key. It's precise, but it only covers writes that go through that code path.
3. Versioned keys. Embed a version in the key, such as product:v3:42. Bumping the version makes old entries unreachable, and they expire by TTL.
4. Change-data-capture (CDC). Tail the database's log, such as the Postgres WAL or MySQL binlog, and delete affected keys. This catches writes from any source, in commit order.

None of these gives strong consistency between cache and database. They give bounded staleness. Choose N from the business. A product description can be 10 minutes stale. A stock count might be 5 seconds stale. An account balance shouldn't be cached this way at all.

Walking through it

Why delete instead of set? Two writers update one price:

Writer A: UPDATE price = 10 in DB
Writer B: UPDATE price = 12 in DB      (DB now says 12)
Writer B: SET cache price = 12
Writer A: SET cache price = 10          (cache says 10, until TTL)

The two cache writes landed in the opposite order from the database writes. If both writers delete the key instead, the next reader loads the current database value.

Delete isn't perfectly safe either. A reader can miss, read the old value from the database, and get delayed. If it writes that old value back after the writer's delete, the cache holds stale data.

A short TTL is the backstop. Any stale entry heals itself within minutes. Leases, covered in the memcache case study, close this gap.

Common mistakes

• Setting the new value on write. Concurrent writers can leave an old value in the cache. Delete instead.
• Invalidating in one code path only. A batch job that writes the database directly skips the delete. CDC covers that case.
• Caching data that must be fresh. If a withdrawal needs the latest balance, read it from the database inside the transaction. Use the cache only for display. See consistency models.

Check yourself

1. Why delete the cache key instead of setting the new value? Concurrent writers can finish their cache writes out of order and leave the older value. A delete makes the next reader load the current value.
2. Which strategy catches writes from a batch job that bypasses the app? Change-data-capture, which tails the database log and deletes affected keys.

Key takeaways

• The four invalidation tools are TTLs, deletes on write, versioned keys and CDC.
• They all give bounded staleness. None gives strong consistency.
• Delete on write, don't set. Keep a TTL as a backstop.
• Read anything that must be exact from the database, not from the cache.

Further learning

Next, read about cache stampedes, the failure that often follows an expired key.