Eviction and Invalidation

In one line: these two get conflated constantly, and they answer different questions. Eviction asks what should I drop to make room? Invalidation asks what is no longer true?

Eviction policies

Common strategies:

Policy	Evicts	Fits when
LRU — least recently used	The entry untouched for longest	Recent access predicts future access — the common case
MRU — most recently used	The entry just used	Data is read once and not needed again, like a sequential scan
LFU — least frequently used	The entry with fewest accesses	Popularity is stable over long periods
MFU — most frequently used	The entry with most accesses	Rarely — but useful as a contrast case
FIFO — first in, first out	The oldest entry regardless of use	Simplicity matters more than hit rate

The choice of algorithm depends on the application's access patterns.

Cache invalidation

Data in the cache can become stale if the original data in the database changes. Invalidating or deleting stale data is crucial for maintaining consistency.

The common mechanism is a time-to-live (TTL) on each entry: once the TTL expires, the entry is considered invalid. Two approaches to acting on that:

Approach	How it works	Trade-off
Active expiration	A background process periodically scans the cache and removes expired items	Frees memory promptly; costs continuous background work proportional to cache size
Passive expiration	An item's TTL is checked only when requested — if expired, it is removed and a cache miss is triggered	Zero background cost; expired entries occupy memory until someone asks for them

Expired items are removed from the cache upon discovery.

Real systems run both

Passive alone leaks memory: an entry nobody requests is never checked, so it sits expired and occupying space indefinitely. Active alone wastes CPU scanning entries that will never be requested again anyway.

Running both gives you the best of each — passive catches expiry exactly when it matters (at read time, for free), and a periodic active sweep reclaims the memory nothing is asking about.

When a popular key expires

TTL-based invalidation has a failure mode that only appears under load, and it is the most-asked follow-up in this whole topic.

This is the thundering herd, or cache stampede. The cache was absorbing thousands of reads per second for that key; the instant it expires, all of them become database queries at once. The more effective the cache was, the worse the spike.

Three fixes, and they compose:

Request coalescing (single-flight). Let the first miss fetch, and make every concurrent miss for the same key wait on that one fetch rather than issuing its own. This is the highest-value fix because it caps origin load at one query per key regardless of how many requests arrive.

Probabilistic early expiry. Rather than expiring at a fixed instant, let each read decide — with a probability that rises as the TTL approaches — to refresh the entry early. Requests then refresh at staggered moments and the synchronized cliff never forms.

Serve stale while revalidating. Keep the expired value and return it while a single background fetch refreshes it. Availability is preserved and readers see slightly old data instead of a latency spike.

The connection worth drawing: this is the same synchronized-retry problem as a thundering herd on reconnect, and the fixes rhyme — stagger the timing, or elect one actor to do the work for everyone.

Eviction versus invalidation

The distinction is worth stating precisely, because interviewers probe it:

	Eviction	Invalidation
Triggered by	The cache being full	The data becoming stale
The entry was	Still correct — just least valuable	Wrong — the database has moved on
Consequence of not doing it	Cannot admit new entries	Serving incorrect data
Governed by	LRU, LFU, FIFO...	TTL, explicit purge

An evicted entry was fine; you dropped it for space. An invalidated entry was wrong; you dropped it for correctness. Conflating them leads to designs that assume a full cache is also a fresh one.

TTL is a staleness bound, not a freshness guarantee

The CDN chapter made this point and it applies identically here: a 60-second TTL does not mean data updates within 60 seconds. It means an entry may be served up to 60 seconds stale before it is next checked.

When a change must take effect immediately — a deleted record, a revoked permission — TTL is the wrong tool and you need an explicit delete. Lesson 8 covers why that API exists despite eviction and expiry handling most cases.

Key takeaway

Eviction manages space; invalidation manages truth. LRU is the sensible default because it encodes locality of reference, and TTL bounds staleness — but neither removes the need for explicit deletion when correctness demands it.

Interview signal by level

Level	What a strong answer sounds like
L4	"We'd use LRU and set a TTL."
L5	Separates the concerns: "LRU decides what to drop when we're full; TTL decides what's gone stale — different problems."
Staff+	Adds the mechanics: "active and passive expiration together, because passive alone leaks memory on keys nobody requests. And LRU because it encodes locality — LFU would let last year's hot item squat a slot forever unless we age the counts."

Next: where an entry lives, and how it's found.