The problem: one edit, many copies
Phil Karlton's line that "there are only two hard things in Computer Science: cache invalidation and naming things" (quoted by Martin Fowler) is a joke engineers repeat because it's true. Here's why.
An owner edits x7Kp to point at the summer sale. The database row changes in one place, but copies of the old
destination may be sitting in Redis, in the in-process caches of 40 app servers, and, if Snip caches redirects at the
edge (06.07 CDNs in depth), in CDN edges around the world. Each has to be cleared, or has to expire, before every user sees
the new destination.
Invalidation is hard for three reasons: there are many copies, the messages that clear them can be delayed, lost or reordered, and a read and a write racing each other can put an old value back after you cleared it.
First: how stale is acceptable?
Perfect freshness everywhere is expensive. Decide per kind of data what a user can tolerate, and design for that:
| Snip data | Acceptable staleness | How |
|---|---|---|
| An edited destination | Up to a minute | Delete from Redis on edit; in-process TTL of 5 s; edge TTL of 60 s |
| A link blocked as phishing | Seconds, everywhere | Delete from Redis, broadcast to app servers, purge the CDN |
| Click totals on the dashboard | A few minutes | TTL only |
| The owner's own list after an edit | None, for that owner | Read their own writes from the database (04.07 Replication: leaders, followers and lag) |
Snip tells owners "edits take up to a minute to reach everyone", which turns a hard problem into an easy one.
Ways to clear a copy
1. TTL only. Do nothing on change; every copy expires on its own. Staleness is bounded by the TTL, and it can't fail, because there's nothing to fail. Right for data where the bound is acceptable.
2. Delete on write. The code that changes the row deletes the cache entry (06.02 Cache-aside, write-through, write-behind). Simple, but every code path that writes must remember to do it, including scripts, admin tools and other services. Miss one and the copy is stale until its TTL.
3. Delete from the change stream. Instead of trusting every writer, a separate process reads the database's own log of committed changes (change data capture, 07.06 The outbox pattern and change data capture) and deletes the affected keys. Every committed change is seen, whoever made it, and the log can be replayed if deletes were lost. Facebook built its memcache invalidation this way (below).
4. Versioned keys. Put a version in the key: link:x7Kp:v4. An edit bumps the version stored with the link, so
readers ask for v5, which isn't cached yet, and the old entry is simply never read again until it's evicted.
Nothing needs deleting, but readers need the current version from somewhere, so it suits data looked up through a
parent that's already fresh, such as file names in HTML (02.05 A CDN for static content).
5. Broadcast to local caches. In-process caches on 40 servers can't be deleted with one call. Publish "x7Kp changed" on a pub/sub channel that every server subscribes to, and keep their TTLs short in case a message is missed.
The race that undoes a delete
Even with update-then-delete, one interleaving leaves the cache wrong. It needs a cache miss and an edit at the same moment, with the slow read finishing last:
5 messages. Use Next and Back to follow them in order.
Text version
- Redirect (read) → Redis: GET x7Kp → miss — The entry has just expired, so the redirect goes to the database.
- Redirect (read) → Postgres: SELECT → spring — It reads the current destination, the spring sale. Then it's paused for a moment before writing the cache.
- Edit (write) → Postgres: UPDATE → summer — Meanwhile the owner's edit commits.
- Edit (write) → Redis: DEL x7Kp — The edit deletes the cache entry. There isn't one yet, so nothing happens.
- Redirect (read) → Redis: SET spring (fails) — The slow read now caches the value it read before the edit. The database says summer; the cache says spring until the TTL expires.
It's rare, because the read must be slower than a whole write and delete, but at millions of reads a second rare things happen daily. Three fixes, in increasing strength:
- A TTL bounds the damage. Always have one.
- Versions on set. Store the row's version with the cached value, and only let a fill write the cache if its version is newer than what's there. That needs the cache to remember versions, including for deleted entries.
- Leases. On a miss, the cache hands the reader a token. A delete for that key cancels the token, and the cache
rejects a
SETwith a cancelled token. The slow read above would be refused. Facebook added leases to memcache for exactly this "stale set", and the same tokens help with stampedes (06.05 Stampedes and request coalescing).
Measure it
You can't fix staleness you can't see. A simple check: sample a small share of cache reads and compare them with the database (after allowing for in-flight changes). Count mismatches as a rate, and alert on it. Meta built a service for this at scale, below, and found bugs no one had known about.
Seen in production
memcache invalidation
Facebook amended the SQL statements that change data to include the memcache keys to invalidate once the transaction commits. A daemon called mcsqueal on every database reads the committed statements, extracts the deletes and broadcasts them to the memcache servers in every frontend cluster, batching them to keep packet rates down. Because the deletes are stored in the database's reliable log, mcsqueal can replay invalidations that were lost or misrouted. The same paper introduces leases to stop stale sets.
What we foundRead deletes from the database's commit log, not from every writer, so lost invalidations can be replayed.
Scaling Memcache at Facebook (NSDI 2013)usenix.org ↗Meta
2022TAO and memcache consistency
Meta describes the same race as above: a cache fill reads x=42, x changes to 43, the invalidation for 43 reaches the cache first, and then the fill writes 42, leaving 42 in the cache indefinitely. To measure such problems it built Polaris, which receives invalidation events like a cache server and then checks cache replicas for values that should have changed. With it, Meta raised TAO's measured consistency from six nines (99.9999%) to ten nines: 99.99999999% of cache writes consistent within five minutes.
What we foundMeasure cache consistency directly, and the race between a fill and an invalidation becomes visible and fixable.
Cache made consistent (Engineering at Meta)engineering.fb.com ↗Snip deletes cache entries in the edit API. An admin script that bulk-changes 10,000 destinations updates Postgres directly. What happens, and what's the robust fix?
Recap
Interview questions
How do you keep a cache consistent with the database?