System Design HLD-05.04
Cache invalidation and consistency
Keeping cached copies correct when data changes: TTLs, delete versus update, the stale-set race, versioned keys and lease tokens.
The big idea
A cache is a copy, and copies go out of date. The moment someone changes a price, a profile or a permission in the database, every cached copy of it is wrong until something fixes it. Cache invalidationRemoving or updating cached copies when the underlying data changes, so readers stop seeing old values. is how you fix it, and it is famously one of the hard problems in computing, not because any single step is hard, but because many readers and writers act at once, and their steps interleave in surprising orders.
There is no free answer. You choose how stale data may be, and pay for that choice in complexity or load. A like count that is a minute old is fine; a permission that is a minute old can be a security hole; a price in a checkout that is a minute old can cost money.
Think of a printed train timetable pinned in a hundred stations. When the schedule changes, you can wait for the posters to be replaced on a schedule (TTL), send someone to tear the old ones down (invalidate), or print a version number on each so people can tell which is current (versioned keys).
How it works
Step 1: TTL alone
Give every entry a time to live. After it expires, the next read goes to the database. TTLs are simple, need no coordination, and guarantee that staleness is bounded by the TTL. But within that window, readers can see old data, and a short TTL means more misses and more database load. TTL is always worth having as a safety net; it is rarely enough alone.
Step 2: Delete on write
On every write, update the database and then delete the cached key, so the next read loads fresh data. Deleting is better than updating the cached value, because deletes are idempotent and cannot install the wrong value when writes race. But one race remains even with delete:
Step 3: Closing the race
- Leases: on a miss, the cache gives the reader a lease tokenA token the cache hands out on a miss; a later SET for that key is accepted only if the token is still valid, and a delete invalidates it.. When the reader later sets the value, it must present the token. A delete in between invalidates the token, so the late, stale set is rejected. Leases also tame thundering herds: the cache hands out only one token per key at a time and tells other readers to wait briefly and retry.
- Versioned keys: include a version in the key,
product:42:v17. Writers bump the version in the database; readers build the key from the current version, so an old value is simply never read again and eventually evicted. - Compare-and-set: store a version with the value and only overwrite if the stored version is older than yours.
- Delete twice: delete, write the database, then delete again after a short delay. Crude but it closes most of the window.
Step 4: Invalidating from the database
Instead of trusting every code path that writes to also delete cache keys, some systems watch the database's change log (change data captureChange data capture: reading a database's log of committed changes and publishing them as a stream of events., Transactional outbox and change data capture ) and issue invalidations from it. Every committed change triggers an invalidation, including writes from scripts and other services that forgot the cache exists.
Going deeper
Choose the staleness you can afford
Classify data. Some can be minutes old (counts, recommendations), some must be fresh on the next read by the same user (their own profile edits, read-your-writes, in PACELC and consistency models ), and some should not be cached at all, or only with strict invalidation (balances, permissions, inventory at checkout). One cache can use different TTLs and strategies per kind of key.
Multiple regions
With caches in several regions, an invalidation must reach every region, and replicated databases may lag, so a region can re-cache an old value from a replica that has not yet seen the write. Large systems route invalidations through the replication stream itself, so a region's cache is invalidated only after its database copy is updated.
Trade-offs
| Option | Wins when | Loses when |
|---|---|---|
| TTL only | Data that tolerates bounded staleness: counts, feeds, recommendations | Data that must be fresh soon after a write |
| Delete on write + TTL | Most read-heavy data: simple, mostly fresh | Strict correctness: the stale-set race remains |
| Leases or versioned keys | Hot, frequently updated keys where stale sets would be noticed | Simplicity: more protocol between app and cache |
| Invalidation from change data capture | Many writers and services touching the same data | Infrastructure to run and a short delay after each commit |
Common mistakes
- Updating the cached value on write instead of deleting it, so racing writers leave the older value.
- Caching without any TTL, so a single missed invalidation lasts forever.
- Invalidating in application code only, then a script or another service writes directly to the database.
- Caching permissions or balances with long TTLs.
In the wild
Facebook (Meta)
Scaling Memcache at Facebook (NSDI 2013) (opens in a new tab)This paper describes how Facebook built a cache handling billions of requests per second and trillions of items on top of memcached. It uses a demand-filled look-aside cache, and on writes "the web server issues SQL statements to the database and then sends a delete request to memcache", choosing delete over update "because deletes are idempotent". To prevent stale sets and thundering herds it introduces leases: a 64-bit token bound to the key on a miss, which a delete invalidates so that a late set fails, with tokens handed out at most once every 10 seconds per key. In their measurements, leases cut the peak database query rate from 17K/s to 1.3K/s.
Check yourself
-
What does a TTL guarantee?
Show answer
B. Staleness is bounded by the TTL An entry can be stale for at most the TTL before it expires and is reloaded.
-
In the stale-set race, what goes wrong?
Show answer
B. A slow reader stores a value it read before the write, after the writer's delete The delete happened between the reader's read and its set, so the old value is re-cached.
-
How does a lease prevent the stale set?
Show answer
B. A delete invalidates the reader's lease token, so its later set is rejected The set must present a valid token; deleting the key in between makes the token invalid.
-
Why invalidate from the database's change log?
Show answer
B. Every committed change triggers invalidation, even from code paths that forgot the cache The change stream sees all writes, not just the ones made by well-behaved application code.
Recap
- Cached data goes stale when the source changes; invalidation fixes it.
- TTLs bound staleness and should always be present as a safety net.
- Delete on write beats update on write, but a slow reader can still re-cache old data.
- Leases, versioned keys and compare-and-set close the stale-set race.
- Choose staleness per kind of data; invalidate from the change log when many writers exist.
Next up
- Crack the system design round learning path