Cache invalidation & eviction

A sneaker shop runs a flash sale: one model drops from $120 to $90 until noon. At peak its product page is read 2,000 times a second, so the page's data sits in a shared cache under the key product:881, with a TTL of 10 minutes.

At noon the sale ends and the database says $120 again. The cache still holds the copy it loaded at 11:58. Until that copy expires, shoppers see $90 on the page, and checkout, which always reads the database, charges them $120.

Closing that gap is cache invalidation: making a cache stop serving a copy once the data behind it has changed. A copy that no longer matches its source is stale.

The TTL already bounds the damage, since no copy outlives it, and the TTL is also the longest a change can stay hidden. But a shorter TTL costs database load: every expiry of a product someone is still reading is one more reload. If 200,000 cached products are each read again before their TTL runs out, the reloads per second are 200,000 ÷ TTL:

Every row is a bad trade: fresh and expensive, or cheap and stale. To get both, the cache has to be told when the data changes.

With cache-aside, the usual answer is to make the code that changes the data also remove the cached copy:

Two details in those steps matter, and each one comes from a race that real systems hit.

Delete, don't overwrite. Writing the new value into the cache looks faster, but two writers can reach the cache in the opposite order from the database. A delete carries no value to get wrong: two deletes, in either order, leave the same empty key. Deletes are idempotent, and that is why Facebook's memcache deployment deletes cached data on writes instead of updating it.

Database first, then the cache. Deleting the key before the database write opens a gap: a read that lands between the two misses, loads the old $90 from the database, and caches it again for a full TTL.

Keep the TTL anyway. Deletes get lost: a server crashes between the commit and the delete, a network blip drops one, a new code path forgets it. The TTL is the backstop that makes each of those bugs heal on its own, within one TTL.

Even in the right order, one race is left. It needs a cache miss and a write on the same key within a few milliseconds of each other, which sounds rare until a page is read thousands of times a second.

The fixes, from simplest to strongest:

Facebook built leases into memcached. A lease there is a 64-bit token tied to one key: the cache hands it out on a miss and checks it when the value comes back, and a delete in between voids it.

The same tokens also tame a thundering herd of readers reloading one key at once. The cache hands out at most one token per key every 10 seconds and tells the other readers to wait briefly and try again. On keys prone to that pile-up, the database's peak fell from 17,000 to 1,300 queries a second.

The race also appears with no slow reader at all, when misses load from a read replica: a copy of the database that serves reads and receives each write a little later. If the replica hasn't received the new price yet, the reload after the delete fetches $90 from it and caches that. Facebook's answer is a marker set with the write: a miss that finds the marker reads from the main database instead.

The shop doesn't have one cache. Each of its 40 app servers keeps the 1,000 hottest products in its own memory for 30 seconds, which saves a network hop on the most-read pages. When the sale job deletes product:881 from the shared cache, those 40 local copies don't hear about it.

The third approach fixes what the other two share: they rely on the writer remembering. Every code path that updates the database, a migration, an admin script, a new service, also has to delete the right keys, and the one that forgets leaves stale copies. A process reading the database's own log of committed changes sees every write, whoever made it, and a crash between commit and delete can't lose one, because the log is still there.

Facebook's memcache works this way. A daemon on every database reads the statements it commits, pulls out the keys to delete, and sends the deletes to the caches of every cluster in the region. The web server that made a write also deletes the key in its own cluster at once, so the person who changed something sees the change. Only 4% of those deletes find anything to remove, so the daemons batch them to keep the number of packets down.

Reading a database's log of changes is the subject of Change data capture.

The shop sells 2,000,000 products. At about 4 KB each, caching all of them takes 8 GB, and the cache has 2 GB: room for 500,000. Once it is full, every new entry pushes an old one out. Which one goes is the cache's eviction policy.

Eviction is not expiry. An expired copy is removed because it may be wrong; an evicted copy is still correct and goes only to make room. Either way, the next read of it is a miss.

The default in most caches is LRU, least recently used: forget the key nobody has asked for in the longest time. Here it is in a cache with room for three products:

A was read again, so it survived; B had gone quiet the longest when D arrived. LRU bets that what was read recently will be read again soon, which holds whenever a small set of keys gets most of the reads, as it does in most shops. Its main alternative is LFU, least frequently used, which counts reads instead of timing them.

Real caches approximate these rather than keep an exact order of every key, which would cost memory and work on every read:

• Redis samples 5 keys by default, keeps a small pool of good candidates between evictions, and forgets the least recently used of them; with 10 samples it is very close to true LRU.
• Redis's LFU keeps a small counter per key that grows more slowly the higher it gets and counts down as minutes pass without reads, so yesterday's favorites can fall.

Memcached groups items by size and runs an LRU for each size class, split into hot, warm and cold segments. It evicts from the cold end, and an item has to be read twice to move up from hot.

One default catches people out. Redis has no memory limit on 64-bit machines until you set maxmemory, and once you do, the default policy is noeviction: a full Redis returns errors to commands that add data, while reads keep working. The volatile-* policies evict only keys that have a TTL, and behave like noeviction if none do. For a cache, set allkeys-lru or allkeys-lfu.

Every night a job exports all 2,000,000 products for a price-comparison site, and it reads them through the same cache-aside code as the product pages. Under LRU, each product it touches becomes the most recently used. Once it has read 500,000 of them, every product no shopper has read since the export began is gone, and at 3 a.m. that is nearly all of them. The cache is full of products nobody will ask for again.

When the morning rush starts, the hit ratio is far below normal, and the database takes the misses until shoppers' reads fill the cache again. A small trace shows it, with A and B as the hot products and X, Y and Z as the scan:

The right column is a segmented LRU: a new key enters a small probation area and moves to the protected area only when it is read a second time. Keys read once, like everything a scan touches, push each other out of probation and never reach the hot products.

The fixes, in the order to reach for them:

Whichever you pick, watch the hit ratio after nightly jobs and deploys. A sudden drop is the cache saying it has been filled with the wrong things, and Cache failure modes covers what that does to the database.