Cache Invalidation: The Hardest Problem in Computer Science (How to Solve It)

Cache invalidation isn’t just hard; it’s where performance optimizations meet the brutal realities of distributed systems.
We will see different cache invalidation techniques with simple and short explanations with real word examples.

• The Cache Invalidation Problem
• Time-Based Invalidation (TTL/TTI)
• Event-Based Invalidation
• Write-Through and Write-Behind Strategies
• Cache-Aside Pattern
• Versioning-Based Invalidation
• Tag-Based Invalidation
• Purge and Flush Strategies
• Distributed Systems: The Real Challenge
• The Thundering Herd Problem
• Multi-Region Cache Invalidation

Imagine you’re running a library. To speed things up, you create a “quick access” shelf near the entrance with the most popular books. Great! Checkout times drop dramatically. But then someone returns a book with notes in the margins, or a new edition arrives. Now you have a problem: when do you update the quick access shelf?

- Update too often? You lose the speed benefit.
- Update too rarely? People get outdated books.
- Miss an update? Someone gets wrong information.

This is cache invalidation in a nutshell.

Why This Is Actually Hard

The challenge comes from juggling three competing forces:

1. Performance/Speed — Caches exist to make systems fast. Every extra validation or invalidation step eats into that gain.
2. Consistency — Users expect fresh data. When the cache lies, trust erodes quickly.
3. Complexity — In real systems, there isn’t just one cache. There are many, spread across servers, regions, and layers — CDNs, app caches, databases, even browsers.

The Core Trade-Off

Every system is forced to choose a balance:

• Invalidate aggressively: Data stays accurate, but performance drops and stampedes become likely
• Invalidate cautiously: Performance shines, but stale data slips through
• Invalidate cleverly: Best of both worlds — at the cost of complexity

There’s no universal right answer. The best approach depends entirely on what your system values most. Let’s look at the techniques.

Time-Based Invalidation (TTL/TTI)

Set an expiration time on cached data. After that time, the cache entry is considered stale and must be refreshed.

Two Flavors

- TTL (Time To Live): Absolute expiration from when the item was cached “This data expires at 2:00 PM, no matter what”
- TTI (Time To Idle): Expiration based on last access
“This data expires 5 minutes after the last time someone accessed it”

Real-World Example: YouTube View Counts

Ever noticed YouTube view counts don’t update in real-time? That’s TTL at work:

- View counts: 1–2 hour TTL for most videos
- Trending videos: 5–15 minute TTL (more frequent updates)
- Live stream viewers: 10–30 second TTL

Why? Updating view counts in real-time for billions of views would be impossibly expensive. The trade-off is acceptable because exact view counts aren’t critical for user experience.

When to Use TTL/TTI

Use when:
- Data changes predictably or infrequently
- Slight staleness is acceptable
- You want simple implementation
- You’re caching expensive computations
- You have read-heavy workloads

Avoid when:
- Data must be immediately consistent (financial transactions, inventory)
- Changes are unpredictable and critical
- You need fine-grained control over invalidation

TTL works best when you can answer: “What’s the maximum acceptable staleness?” If you can say “5 minutes of stale data is fine,” TTL is your friend. Use different TTLs for different data types. Don’t use a one-size-fits-all approach.

Event-Based Cache Invalidation

Event-based invalidation means your cache updates the moment data changes. No waiting. No stale data.
Think of it like a notification system: “Hey cache, this data just changed — fix yourself.”

How It Works

1. Data changes in the database
2. An event is triggered
3. Cache receives the event
4. Cache updates or deletes the old data

That’s it.

Why It Matters (Quick Examples)

E-commerce Inventory — If a product sells out, users should see “Out of Stock” immediately.
Without events, cached data lies for minutes. With events, the cache updates in milliseconds.

Imagine you’re Amazon during Black Friday. A PlayStation 5 has 10 units left. Event-based invalidation is critical here:
Scenario without event-based invalidation:
- 10 units in stock
- 50 people see “In Stock” (cached for 1 minute)
- All 50 try to buy
- 40 people get “Out of Stock” errors
- Customer service nightmare

Used for: inventory counts, prices
TTL is fine for: reviews, recommendations

When to Use Event-Based Invalidation

Use it when:
- Data must be accurate immediately
- Stale data hurts the business (inventory, pricing, money)|
- You have reliable events

Avoid it when:
- Updates happen constantly
- Slight staleness is okay
- You want simple infrastructure

The Catch
Event systems aren’t perfect:
- Events can arrive out of order
- Events can be lost
- Massive invalidations can overload databases

Best practice:
Use event-based invalidation + a backup TTL
Events handle speed. TTL handles safety.

Write-Through vs Write-Behind Caching

These aren’t just cache invalidation tricks — they’re full caching strategies that decide when and how data moves between your cache and database.

Write-Through: Consistency Over Speed

What it means:
Every write updates both the cache and the database at the same time. The operation succeeds only if both succeed.

How it works:

1. App writes data
2. Cache is updated
3. Database is updated
4. Success is returned only after both complete

Real-World Example: Banking Systems

Banks rely on write-through for account balances.

Why it’s required:

• Balances must always be accurate
• Cache and database can’t disagree
• Regulations demand strong consistency
• Audits must be flawless

Flow in practice:

• User transfers $100
• Cache updates balance to $900
• Database updates balance to $900 in the same transaction
• If anything fails, everything rolls back
• User immediately sees the correct balance

Trade-off: Writes are slower, but data is always correct.

Write-Behind: Speed Over Consistency

What it means:
Writes go to the cache first. The database is updated later, in the background. This is also called write-back.

How it works:

1. App writes data
2. Cache updates immediately
3. Request returns success
4. Database write happens asynchronously
5. Failures are retried later

Real-World Example: Analytics and Metrics

Monitoring platforms use write-behind for metrics.

Their challenge:

• Massive data volume
• Dashboards must feel real-time
• Databases can’t handle every write
• Losing a small amount of data is acceptable

Their solution:

• Metrics written to in-memory cache
• Data is aggregated and batched
• Database writes happen periodically
• Occasional loss is acceptable

When to Use Each

Use Write-Through when:

• Accuracy is mandatory
• Compliance or audits are involved
• Handling money, accounts, inventory
• Slower writes are acceptable

Use Write-Behind when:

• Performance matters most
• Eventual consistency is fine
• Write volume is extremely high
• Some data loss is tolerable

Cache-Aside Pattern (Lazy Loading)

The application manages the cache itself. Data is added to the cache only when it’s requested.
That’s why it’s also called lazy loading.

How It Works
Reads
- App checks the cache
- If found → return it
- If missing → fetch from DB, store in cache, return
Writes
- App writes to the database
- Cache entry is invalidated or updated
- Next read loads fresh data into cache

Real-World Examples

GitHub

• Millions of repositories exist
• Only a few are accessed often
• Popular repos stay cached
• Rarely visited repos skip the cache

Result: Cache automatically fills with what people actually use.

When to Use Cache-Aside

Good fit when:

• Reads are much higher than writes
• Access patterns are unpredictable
• You want a simple, reliable cache
• Cache misses are acceptable

Not ideal when:

• Writes happen constantly
• First-request latency must be low
• Cache must always be up to date

Versioning-Based Invalidation

Instead of invalidating cache entries, you change the cache key when data changes. Old cached data becomes unreachable, effectively “invalidated.”
Think of it like this: Instead of erasing a whiteboard, you just start using a new whiteboard.

Get Tech Mentor’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

How It Works

Traditional approach:
- Cache key: `user:123`
- Data changes → Invalidate `user:123`
- Next request caches new data at `user:123`

Versioning approach:
- Cache key: `user:123:v1`
- Data changes → Start using `user:123:v2`
- Old data at `user:123:v1` just sits there until TTL expires
- No explicit invalidation needed

Real-World Example: API Versioning

Companies like Stripe and Twilio use versioning for API responses:

The challenge:
- API responses are expensive to generate
- Multiple API versions in production (v1, v2, v3)
- Can’t invalidate all versions when data changes
- Different clients use different versions

Their solution:
- Cache key includes API version: `api:v2:customer:cus_123`
- When customer data changes, version increments
- New key: `api:v2:customer:cus_123:v2`
- Old cached response naturally expires
- Each API version has independent cache

When to Use Versioning

Use when:
- Data changes infrequently but must be reflected immediately
- You have immutable data (static assets, API responses)
- You need atomic cache updates
- You want to avoid distributed invalidation complexity
- You’re using CDNs
- You need rollback capability

Avoid when:
- Data changes very frequently (version churn)
- Cache keys become too long
- You need to actively remove old data (compliance, privacy)
- Memory is extremely limited (old versions waste space)

Tag-Based Invalidation

Associate cache entries with tags (labels), then invalidate all entries with a specific tag. It’s like organizing files with labels and deleting all files with a certain label.

How It Works

Setup:
- Cache entry for user profile: Tags = [`user:123`, `profile`]
- Cache entry for user posts: Tags = [`user:123`, `posts`]
- Cache entry for user comments: Tags = [`user:123`, `comments`]

Invalidation:
- User updates profile → Invalidate tag `user:123`
- All entries with that tag are invalidated (profile, posts, comments)

Real-World Example: E-commerce Product Catalog

Amazon uses tag-based invalidation for product pages:

The complexity:
- Product page includes: product details, reviews, recommendations, inventory
- Each piece comes from different services
- Each piece is cached separately
- Product update should invalidate all related caches

Their approach:
- Product details cache: Tags = [`product:B08N5WRWNW`, `electronics`, `kindle`]
- Product reviews cache: Tags = [`product:B08N5WRWNW`, `reviews`]
- Product recommendations: Tags = [`product:B08N5WRWNW`, `recommendations`]

When product updates:
- Invalidate tag `product:B08N5WRWNW`
- All related caches cleared
- Next request rebuilds all caches

When to Use Tag-Based Invalidation

Use when:
- Cache entries have complex relationships
- You need to invalidate groups of related data
- You have hierarchical data (categories, organizations)
- You’re building multi-tenant applications
- Your cache system supports tags natively (Varnish, Fastly)

Avoid when:
- Relationships are simple (just use direct invalidation)
- Your cache system doesn’t support tags
- You have very high write volume (tag lookups add overhead)

Purge vs Flush Cache

Sometimes you need to clear cache fast — either specific entries (purge) or everything (flush).

Purge = Delete specific cache keys or patterns
Use it when you know exactly what data is wrong.
Flush: Clear It All

Flush = Wipe the entire cache (or big sections)
Use it when you can’t risk any stale data.

Real-World Examples

Security Bugs — When GitHub hit a security issue:

• They flushed all caches immediately
• Fixed the bug
• Let caches rebuild naturally

Why: Security mattered more than performance.
When to Use Each

Use Purge when:

• Only specific data is wrong
• You can identify affected entries
• You want minimal impact

Use Flush when:

• Security or data corruption issues
• You don’t know what’s affected
• A temporary slowdown is acceptable

Avoid Flush when:

• A purge would work
• Traffic is at peak and it’s not an emergency

Distributed Systems: The Real Challenge

Everything we’ve discussed so far gets exponentially harder in distributed systems. This is where cache invalidation truly earns its reputation as “one of the hardest problems.”

The Distributed Cache Problem
In a distributed system, you don’t have one cache — you have dozens or hundreds:

Multiple Layers:
- Browser cache (millions of clients
- CDN edge caches (hundreds of locations)
- API gateway cache
- Application server caches (dozens of servers)
- Database query cache
- Microservice caches (hundreds of services)

The nightmare scenario:
- User updates their profile
- Database updated
- Application cache invalidated
- But CDN still has old data
- And 3 microservices have stale caches
- And user’s browser cached the old page

Result: User sees old data for minutes or hours.

Real-World Example: Uber’s Microservices

Uber has 2000+ microservices, each with its own cache:

Their challenge:
- Rider updates payment method
- Must invalidate caches in: Payment Service, Rider Service, Trip Service, Billing Service
- Services are independent — no shared cache

Their solution: Event-Driven Invalidation

Flow:
1. Rider updates payment method
2. Payment Service updates database
3. Payment Service publishes event to Kafka
4. All interested services subscribe to this event
5. Each service invalidates its own cache
6. Services update at their own pace (eventual consistency)

Why it works:
- Loose coupling: Services don’t need to know about each other
- Resilience: If one service is down, others still update
- Scalability: Adding services doesn’t increase complexity

Distributed Cache Invalidation Patterns

Pattern 1: Gossip Protocol
- Nodes share invalidation information with neighbors
- Information spreads through the network
- Eventually all nodes know about invalidation
- Used by: Cassandra, DynamoDB

Pattern 2: Pub/Sub
- Central message broker (Kafka, RabbitMQ)
- Invalidation events published to topics
- Cache nodes subscribe to relevant topics
- Used by: Most microservices architectures

Pattern 3: Centralized Coordinator
- Single source of truth for cache state
- All invalidations go through coordinator
- Coordinator notifies all cache nodes
- Used by: Redis Cluster, Memcached

Pattern 4: Peer-to-Peer
- Cache nodes communicate directly
- No central coordinator
- More resilient but more complex
- Used by: Hazelcast, Infinispan

The CAP Theorem and Caching

The CAP theorem states you can only have 2 of 3:

- Consistency: All nodes see the same data
- Availability: System always responds
- Partition Tolerance: System works despite network failures

For caching, this means:

CP (Consistency + Partition Tolerance):
- Sacrifice availability
- If cache can’t confirm invalidation, reject requests
- Example: Banking systems

AP (Availability + Partition Tolerance):
- Sacrifice consistency
- Serve potentially stale data
- Example: Social media, content sites

Most systems choose AP: Better to show slightly stale data than be unavailable.

The Thundering Herd Problem

What it is:
When a popular cache entry expires, many requests hit the database at the same time, overwhelming it.

Also called cache stampede.
Simple Example

• Cache expires
• Thousands of users arrive at once
• All see a cache miss
• All query the database
• Database overloads
• Site goes down

Real-World Case

Ticket sales (like Taylor Swift tours):

• Millions of users refresh at once
• Ticket cache expires
• Database gets flooded
• Site crashes

This has happened in real life.

Common Fixes

1. Request Coalescing
Only one request rebuilds the cache. Others wait.
2. Early Refresh
Refresh the cache before it expires to avoid mass misses.
3. Stale-While-Revalidate
Serve old data while refreshing in the background.
4. Pre-Warming
Refresh popular data on a schedule so cache never goes cold.

Key Idea

Never let thousands of requests regenerate the same cache at once.
Protect the database, even if users briefly see slightly old data.

Multi-Region Cache Invalidation

What it is:
Keeping caches in sync across multiple data centers around the world.

The Problem

• User updates data in one region
• Other regions have their own caches
• Network latency is high
• Networks can fail or split

You can’t update every region instantly.

How Big Systems Handle It

Common approach (used by WhatsApp, Instagram, Netflix):

• Each region has its own cache
• Writes go to the nearest data center
• Changes replicate asynchronously to other regions
• Caches update locally in each region
• System is eventually consistent

Result:
Local users see updates instantly.
Other regions see them after 1–2 seconds.

Common Patterns

• Primary–Secondary: One region writes, others follow
• Multi-Master: Any region can write (needs conflict handling)
• Geo-Partitioned: Data owned by a region, no cross-region invalidation
• Hybrid: Mix of all three (most common)

Key Trade-Off

Consistency vs Speed
Most global apps choose speed + eventual consistency over perfect accuracy.

Best Practices

• Accept brief inconsistency
• Invalidate caches per region
• Use TTLs as a safety net
• Monitor replication lag

Please refer for more info on how to make right cache invalidation decision with real world examples: https://medium.com/@jayashri98/from-facebook-to-github-cache-invalidation-lessons-decision-framework-9e4ac4a6a7e4?postPublishedType=initial

Conclusion:

Cache invalidation isn’t about picking one perfect strategy — it’s about choosing the right trade-offs. TTL keeps things simple, event-based invalidation keeps data fresh, cache-aside adapts to real usage, and write-through or write-behind balance consistency versus performance. In real systems, these techniques are layered together, with TTL acting as a safety net when things fail. The goal isn’t just speed — it’s reliability under load. Get cache invalidation right, and your system stays fast, correct, and resilient; get it wrong, and your cache becomes a production liability.

Hit follow for more tech content!