Cache Invalidation & Eviction

A cache has two problems that a database does not. It is small, so it must decide what to throw away; and it is a copy, so it must decide when the copy has gone out of date. Eviction answers the first problem and invalidation the second. Between them they hide most of the difficulty of caching, and they are the two topics interviewers like to probe.

Picture a desk that holds only three papers. When a fourth arrives, one has to go back to the filing room. Which one? Two simple policies are in everyday use.

• -Least Recently Used (LRU): send back the paper that has gone longest without being touched. The bet is that what you used lately you will use again soon.
• -Least Frequently Used (LFU): send back the paper that has been used the fewest times overall. The bet is that popularity is stable.

They can disagree sharply. Suppose the desk holds A, B and C, and the recent history is: A used three times, then B once, then C once. Now D arrives. LRU asks when each was last used: A was used longest ago, so LRU evicts A, even though it is the most popular paper on the desk. LFU asks how often: A has 3 uses and B and C have 1 each, so LFU evicts B (the older of the two ties) and keeps A.

LFU has the opposite weakness: something hugely popular last month keeps its high count and stays in the cache long after nobody wants it, unless counts are aged down over time. LRU is the usual default because it is simple, cheap and adapts quickly. Reach for LFU when popularity is stable and bursts of one-off reads would otherwise push the genuinely hot items out. The simulation below lets you watch a small cache fill up and evict as requests arrive; follow one key to see when it is kept and when it is thrown out.

A cache is only useful if it tells the truth. There are two ways to keep it honest. Time-to-live (TTL) invalidation gives every entry a best-before date, like milk: after N seconds it is dropped and fetched again. It is simple and needs no cooperation from the code that writes, but you may serve data that is up to N seconds old. Event-driven invalidation removes or updates the entry the moment the underlying data changes. It is accurate, but every code path that writes the data now has to remember to tell the cache, and forgetting once leaves a wrong value in place. So keep a TTL as a safety net even when you invalidate on events.

How stale is acceptable depends on the data. A like count that is 60 seconds old harms nobody. A price that is 60 seconds old might charge a customer the wrong amount, so read the price from the database at the moment of checkout and let the cache serve only the browsing view.

Here is the failure that surprises people. A very popular key serves 5,000 requests a second from the cache, and then its entry expires. For as long as it takes to rebuild the value, every request misses. If rebuilding takes 200 ms, that is about 5,000 x 0.2 = 1,000 requests all going to the database for the same value at once. If the database struggles under that burst, the rebuild takes longer, more requests pile up, and it gets worse. This is a cache stampede.

• -Single flight (a lock): the first request to miss rebuilds the value while the others wait a moment and then read the fresh copy, so the database sees one request instead of a thousand.
• -Jittered TTLs: add a small random amount to each TTL so that many keys cached together do not all expire in the same second. The many-keys version of the problem is sometimes called a cache avalanche.
• -Refresh ahead: rebuild a hot key a little before it expires, so readers never see a miss.
• -Serve stale while revalidating: hand readers the old value while one request fetches a new one.

A related trap is cache penetration: requests that keep asking for keys that do not exist at all, such as random ids from a scraper. Every one of them misses and reaches the database. Caching the answer not found for a short time stops it.