Skip to content

Redis / caching · 3 of 9

Step 1 · The pattern

Cache in front of the database

Readers get the price from the cache. The database holds the truth; the cache holds a copy of it. Right now they agree: £10.

  • read
  • correct value

In short

Stale set & invalidation: how it works and how it breaks

The usual way to keep a cache honest is: update the database, then delete the cached key so the next read reloads it. There is a race hiding in that. A reader misses the cache and fetches the current value from the database. Before it can write that value into the cache, a writer changes the database and deletes the key. Then the reader finishes and stores what it fetched, which is now out of date. Nothing will correct it until the TTL runs out, and every read in the meantime is wrong. This is a stale set. Facebook's memcache solved it with leases: on a miss the cache hands the reader a token, and a delete invalidates any outstanding token for that key. A set carrying a dead token is refused, so the reader simply fetches again. Version numbers or compare-and-set achieve the same thing.

How this comes up in interviews

"You update the database and then delete the cache key. Can the cache still end up holding old data? Walk me through how."

Then they ask

  1. Why delete the key on a write instead of setting the new value in the cache?
  2. The write commits but the cache delete fails. What does your design do about it?
  3. How does replication lag between a primary and its replicas affect this scheme?

A strong answer covers

  • Describe the race: a reader fetches the old value, a writer updates and deletes, then the slow reader caches the old value.
  • Nothing corrects that entry until its TTL runs out.
  • Leases close it: a miss hands out a token, a delete cancels it, and a set with a dead token is refused.
  • Version numbers or compare-and-set achieve the same result.
  • Delete, don't set: two writers can update the cache in the opposite order to the database, and a delete cannot be out of order.

Points to cover, not a script. Say them in your own words and tie them to a system you have worked on.

On one page: the track cheat sheet.

Last updated: Research paper

Diagrams are our own simulations: the timings, rates and counts in them are illustrative, not measurements. Captions are original wording.