Cache Invalidation

Table of Contents

🔴 P0 — “There are only two hard things in CS: cache invalidation and naming things”

Problem #

Cached data becomes stale when the source changes. Serving stale data is sometimes acceptable (product listings), sometimes not (account balance). The question is: when and how to invalidate.

Strategies #

Strategy	Mechanism	Staleness	Complexity
TTL-based	Cache entry expires after N seconds	Up to TTL seconds	Lowest
Event-based	DB write triggers cache invalidation	Near-zero	Medium
Write-through	Cache updated on every write	Zero	Higher
Versioned keys	Cache key includes version/timestamp	Zero (reads miss)	Low

The Race Condition Problem #

Thread 1: UPDATE DB (balance = 100)
Thread 2: UPDATE DB (balance = 200)
Thread 2: SET cache (balance = 200)
Thread 1: SET cache (balance = 100)  ← WRONG! Stale value overwrites fresh

Solution: INVALIDATE cache on write (delete key), don't update it.
Next read will fetch fresh value from DB.

Instinct #

TTL + event-based invalidation is the sweet spot for most systems. TTL as a safety net (maximum staleness bound), event-based invalidation for important mutations (payment completed → invalidate balance cache). Never update the cache on write — always invalidate. The next reader will populate from the source of truth.

EXP: In practice, cache invalidation on writes (delete-on-write) combined with short TTLs as a safety net has been the most operationally robust approach I’ve seen. Pure TTL-based is simpler but the staleness window is harder to reason about under load.

Thundering Herd Mitigation #

When a popular cache key expires, hundreds of requests simultaneously hit the database. Aka cache-stampedes.

Solutions:

Stale-while-revalidate: serve stale value while one request refreshes
Lock-based refresh: only one request fetches from DB, others wait
Early Recomputation: refresh entries before they expire
Staggering TTLs / Jittered TTLs: add randomness to TTL to avoid simultaneous expiration

References #

Scaling Memcache at Facebook — includes lease-based thundering herd prevention
AWS Builders’ Library: Caching Challenges and Strategies