Invalidation and Eviction

Invalidation and Eviction

Step 1 of 12

used0 / 3

Two problems, one name. Invalidation: when does a copy stop being true? Eviction: what goes when it is full?

The Idea

Two different problems wear one name. Invalidation asks when a cached copy stops being true: let it expire after a TTL, or delete it the moment the source changes. Eviction asks what to drop when the cache is full — LRU discards whatever went longest untouched, LFU the least often requested.

Real-World Example

A supermarket's shelf-edge label is a cache of the price in the till. When head office cuts the price, either somebody walks the aisle replacing labels, or every label carries a "valid until Sunday" date. Stores pick one strategy, and the till always wins the argument.

The Tradeoff

TTLs are cheap but guarantee a window of wrongness, and a popular key expiring under load sends a stampede of misses at the database. Deleting on write is exact, but it couples the writer to every cache that has ever held that key.

maxmemory 512mb                 # hard ceiling for the whole cache
maxmemory-policy allkeys-lru    # when full, drop the coldest key
SET price:8842 "4.50" EX 300    # this copy self-destructs in 5 minutes

Your turn

Put the steps in the right order.

1. 1A write updates the row and deletes the cached copy↑↓
2. 2The next reader misses, fetches fresh data, and caches it↑↓
3. 3Readers are served the cached value while it is still true↑↓
4. 4The value is loaded once and stored, with a size limit in force↑↓

Check order

Mini quiz

1 / 3

A time-to-live guarantees that:

• AThe value is never stale
• BThe value is wrong for at most that long
• CThe cache never fills up
• DWrites get faster