Cache Invalidation: The Hard Problem
"There are only two hard things in Computer Science: cache invalidation and naming things."
— Phil Karlton
Caching gives you speed. But caching creates a new problem: when the source data changes, the cached copy becomes a lie. The question of when and how to remove or update stale cached data is genuinely one of the hardest problems in distributed systems.
The Fundamental Problem
The moment you write data to two places (a cache and a database), you have a consistency problem. There's always a window where one is updated and the other isn't.
Invalidation Strategies
1. TTL-Based Expiration
Set a Time-To-Live on every cache entry. After the TTL expires, the entry is automatically removed. Simple, but the data is guaranteed stale for up to the TTL duration.
TTL Trade-off
- Short TTL (5-30s) — More fresh data, but more cache misses and DB load
- Long TTL (5-60min) — Better hit ratio, but staler data
- Sweet spot: Match TTL to how stale your users can tolerate the data being
2. Event-Based Invalidation
When data changes, actively purge or update the cache. Usually via pub/sub, webhooks, or database triggers. Fastest freshness, but complex to implement correctly.
3. Version-Based Invalidation
Include a version number or hash in the cache key (e.g., user:123:v7). When data changes, increment the version. Old cache entries naturally become unreachable orphans.
The Thundering Herd Problem
Imagine a cache key that's read 10,000 times per second. It expires. Suddenly, all 10,000 requests hit the database simultaneously. The database buckles under the load, responses slow down, timeouts cascade, and your system crashes.
⚡ Thundering Herd Scenario
- Popular cache key expires (TTL reached)
- 1000 concurrent requests all see a cache miss
- All 1000 query the database for the same data
- Database overwhelmed → slow responses → timeouts
- All 1000 try to write to cache simultaneously (wasted work)
Solutions to Thundering Herd
Mitigation Techniques
- Lock/Mutex: First request to miss acquires a lock, loads from DB, populates cache. Other requests wait for the lock (or get stale data).
- Probabilistic Early Expiration: Each request has a small random chance of refreshing the cache before it expires. Spreads the recomputation over time.
- Stale-While-Revalidate: Serve the stale value immediately while one background request refreshes the cache. Users get fast (slightly stale) responses.
- Request Coalescing: Collapse multiple identical in-flight requests into one. Only one actually hits the DB; all others receive its result.
Cache Problems: Stampede vs Penetration vs Avalanche
| Problem | What Happens | Mitigation |
|---|---|---|
| Cache Stampede | Hot key expires → many requests hit DB simultaneously | Mutex lock, early recomputation, stale-while-revalidate |
| Cache Penetration | Requests for keys that don't exist in DB always miss cache | Cache null results (short TTL), bloom filter to reject impossible keys |
| Cache Avalanche | Many keys expire at the same time → sudden DB overload | Randomize TTLs (add jitter), stagger expiration, use circuit breakers |
Real-World: Wikipedia's Purge Cascades
🏢 Wikipedia Cache Invalidation
Wikipedia serves billions of page views per month. Almost every page is served from cache (Varnish). But Wikipedia is editable by anyone, at any time.
- The challenge: When someone edits an article, the cached HTML must be purged — but so must every page that transcludes (includes content from) that article.
- Purge cascades: Editing a template used on 100,000 pages triggers 100,000 cache purges. Wikipedia uses a job queue to process these asynchronously.
- Strategy: Event-based invalidation (edit triggers purge) + TTL as a safety net (pages re-render periodically even without edits).
- Trade-off accepted: After a popular template edit, some pages may be stale for seconds to minutes while the purge cascade completes.
Real-World: Twitter and Celebrity Tweets
🏢 Twitter's Invalidation Challenge
When a celebrity with 50M followers tweets:
- The tweet must appear in 50M users' timelines — each is a cached timeline object.
- Option A (fan-out on write): Push the tweet into all 50M cached timelines immediately. Massive write amplification.
- Option B (fan-out on read): Don't pre-compute. When each follower checks their timeline, merge the celebrity's tweets in real-time. Expensive at read time.
- Twitter's hybrid: Fan-out on write for normal users (< 10K followers). For celebrities, fan-out on read — their tweets are fetched separately and merged at read time.
- This avoids invalidating millions of cache entries for every celebrity tweet while keeping timelines fast for most users.
Interactive: Thundering Herd Simulator
Simulate a popular cache key expiring. Watch requests pile up on the database, then apply mitigations: