System designCore3 min

Cache invalidation & eviction

How a cached copy stops being wrong (invalidation) and how the cache decides what to forget when it's full (eviction).

1 · The problem

A copy can go stale the moment you make it

Once data lives in two places, a write to one leaves the other behind. You have three tools, and most systems use all of them together.

Tool	How	Stale for at most
TTL	Every key expires after a set time	The TTL. Simple, and a safety net for every bug below
Delete on write	The writer deletes the key after updating the database	Until the delete lands, if nothing races it
Versioned keys	Put a version in the key: `event:42:v7`. A write bumps the version	Never: old versions are just never read again

2 · The catch

A slow reader can put old data back

Delete-on-write has a well-known race. A reader misses, loads the old value, and is slow to write it into the cache. Meanwhile a writer updates the database and deletes the key. Then the reader's old value lands.

Reader

Cache

Database

Writer

get: miss

read → v1

write v2

delete key

set v1

holds v1 until the TTL

The window is small but real at scale.

Fix	How it closes the window
Short TTL	Bounds how long the wrong value can live
Leases	A miss hands out a token; a delete voids it, so the late set is refused (Memcached at Facebook)
Delayed second delete	Delete again a moment after the write, after any in-flight reader has finished
Versioned keys	The late set writes v1 under the old key, which nobody reads any more

3 · When the cache is full

Eviction: what to forget

Policy	Evicts	Good at	Weak at
LRU	The least recently used key	Most workloads: recent keys tend to be read again	A one-off scan pushes out the whole working set
LFU	The least frequently used key	Steady popularity, such as a catalog's best sellers	Yesterday's hits linger; needs ageing
FIFO	The oldest key	Very cheap to run	Evicts hot keys just because they're old
TTL first	Keys closest to expiry	Data with natural lifetimes	Doesn't look at use at all
Random	Any key	Almost free; surprisingly close to LRU on big caches	No guarantees

Redis and Memcached approximate LRU by sampling a few keys and evicting the oldest of them, which is almost as good and far cheaper than a perfect ordering.

4 · In a real system

Data that never changes is easy

URL Shortener System Design

Short links never go stale

A short link points to the same long URL for life, so the URL shortener's cache has nothing to invalidate; only eviction and expiry matter. Design for immutable data where you can, and invalidation stops being a problem.

See it in the simulator Read the full design

Check yourself

3 questions

1. Why keep a TTL even if every write deletes its cache key?

2. In the reader/writer race, what ends up in the cache?

3. A nightly job reads every row once. Which policy lets it wipe out the cache's hot keys?

Takeaways

Remember this

Use TTLs everywhere as a backstop, delete on write, and version keys where you can.
Delete-on-write can race a slow reader; leases or versioned keys close the gap.
LRU is the sensible default for eviction; beware of scans.
Immutable data needs no invalidation at all.