Cache Invalidation

The Hardest Problem

“There are only two hard things in Computer Science: cache invalidation and naming things.”
— Phil Karlton

Cache invalidation is deciding when and how to remove or update cached data when the underlying data changes.

Why is it hard?

• When do you invalidate? (on write, on time, on events?)
• What do you invalidate? (single key, related keys, entire cache?)
• How do you invalidate? (delete, update, version?)
• What if invalidation fails?

---

The Stale Data Problem

Stale data = cached data that doesn’t match the database anymore.

Impact:

• Users see wrong prices
• Inventory counts are incorrect
• User profiles show old data
• Search results are outdated

---

Strategy 1: Write-Through

Update cache when data is written. Cache and database stay in sync.

How it works:

1. Application writes data
2. Update cache immediately
3. Update database simultaneously
4. Wait for both to complete
5. Return success

When to use:

• ✅ Strong consistency required
• ✅ Can’t afford stale data
• ✅ Write latency acceptable
• ✅ Critical data (prices, inventory)

Trade-offs:

• ✅ Cache always has latest data
• ✅ No stale data
• ✅ Simple to understand
• ❌ Higher write latency (waits for both)
• ❌ Database becomes bottleneck

Implementation

Python

write_through.py

class WriteThroughCache:
    def __init__(self, cache: CacheClient, db: Database):
        self.cache = cache
        self.db = db

    def update_user(self, user_id: int, data: dict):
        # Write to cache
        cache_key = f"user:{user_id}"
        self.cache.set(cache_key, data, ttl=3600)

        # Write to database
        self.db.update_user(user_id, data)

        # Both complete - return success
        return True

Java

WriteThroughCache.java

class WriteThroughCache {
    private final CacheClient cache;
    private final Database db;

    public WriteThroughCache(CacheClient cache, Database db) {
        this.cache = cache;
        this.db = db;
    }

    public boolean updateUser(int userId, UserData data) {
        // Write to cache
        String cacheKey = "user:" + userId;
        cache.set(cacheKey, serialize(data), 3600);

        // Write to database
        db.updateUser(userId, data);

        // Both complete - return success
        return true;
    }
}

---

Strategy 2: Write-Invalidate

Delete cache on write. Next read fetches fresh data.

How it works:

1. Application writes data
2. Delete from cache (invalidate)
3. Update database
4. Return success
5. Next read fetches fresh data from DB and caches it

When to use:

• ✅ Simpler than write-through
• ✅ Lower write latency (no cache write)
• ✅ Good for write-heavy workloads
• ✅ When cache miss is acceptable

Trade-offs:

• ✅ Lower write latency
• ✅ Simple to implement
• ✅ Ensures fresh data on next read
• ❌ Next read has cache miss (slower)
• ❌ May cause cache stampede

Implementation

Python

write_invalidate.py

class WriteInvalidateCache:
    def __init__(self, cache: CacheClient, db: Database):
        self.cache = cache
        self.db = db

    def update_user(self, user_id: int, data: dict):
        # Update database
        self.db.update_user(user_id, data)

        # Invalidate cache
        cache_key = f"user:{user_id}"
        self.cache.delete(cache_key)

        return True

    def get_user(self, user_id: int):
        # Cache-aside pattern
        cache_key = f"user:{user_id}"
        cached = self.cache.get(cache_key)

        if cached:
            return cached

        # Cache miss - fetch from DB
        user = self.db.get_user(user_id)

        # Cache it
        if user:
            self.cache.set(cache_key, user, ttl=3600)

        return user

Java

WriteInvalidateCache.java

class WriteInvalidateCache {
    private final CacheClient cache;
    private final Database db;

    public WriteInvalidateCache(CacheClient cache, Database db) {
        this.cache = cache;
        this.db = db;
    }

    public boolean updateUser(int userId, UserData data) {
        // Update database
        db.updateUser(userId, data);

        // Invalidate cache
        String cacheKey = "user:" + userId;
        cache.delete(cacheKey);

        return true;
    }

    public Optional<User> getUser(int userId) {
        // Cache-aside pattern
        String cacheKey = "user:" + userId;
        Optional<String> cached = cache.get(cacheKey);

        if (cached.isPresent()) {
            return Optional.of(deserialize(cached.get()));
        }

        // Cache miss - fetch from DB
        Optional<User> user = db.getUser(userId);

        // Cache it
        user.ifPresent(u -> cache.set(cacheKey, serialize(u), 3600));

        return user;
    }
}

---

Strategy 3: TTL Expiration

Time-based expiration. Items expire after fixed time.

How it works:

1. Set TTL when caching data
2. Background process checks expiration
3. Expired items removed automatically
4. Next read fetches fresh data

When to use:

• ✅ Data changes infrequently
• ✅ Some staleness acceptable
• ✅ Simple to implement
• ✅ Good for read-heavy workloads

Trade-offs:

• ✅ Simple
• ✅ Automatic cleanup
• ✅ No manual invalidation needed
• ❌ May serve stale data until expiration
• ❌ Doesn’t react to actual changes

---

Strategy 4: Event-Driven Invalidation

Invalidate on data change events. Most sophisticated approach.

How it works:

1. Data updated in database
2. Publish event (e.g., “user:123 updated”)
3. Cache listens to events
4. On relevant event, invalidate cache
5. Can invalidate related keys too

When to use:

• ✅ Complex invalidation logic
• ✅ Need to invalidate related data
• ✅ Event-driven architecture
• ✅ Multiple cache layers

Trade-offs:

• ✅ Precise invalidation
• ✅ Can handle complex relationships
• ✅ Reactive to actual changes
• ❌ More complex to implement
• ❌ Requires event infrastructure

---

The Cache Stampede Problem

Cache stampede (thundering herd) happens when cache expires and many requests simultaneously try to fetch from database.

Impact:

• Database overloaded with duplicate queries
• Slow response times
• Potential database crash
• Wasted resources

Solution 1: Distributed Locks

Only one request fetches; others wait.

How it works:

1. Request checks cache (miss)
2. Try to acquire distributed lock
3. Only one request gets lock
4. Winner fetches from database and caches
5. Others wait, then read from cache

Python

cache_stampede_prevention.py

import redis
import time
import uuid

class CacheWithLock:
    def __init__(self, redis_client: redis.Redis):
        self.redis = redis_client
        self.lock_ttl = 10  # seconds

    def get_with_lock(self, key: str, fetch_func):
        # Try cache first
        cached = self.redis.get(key)
        if cached:
            return cached

        # Cache miss - try to acquire lock
        lock_key = f"lock:{key}"
        lock_value = str(uuid.uuid4())

        # Try to acquire lock (set if not exists)
        acquired = self.redis.set(
            lock_key, lock_value,
            nx=True, ex=self.lock_ttl
        )

        if acquired:
            # We got the lock - fetch from DB
            try:
                data = fetch_func()
                self.redis.set(key, data, ex=300)
                return data
            finally:
                # Release lock (only if we still own it)
                if self.redis.get(lock_key) == lock_value:
                    self.redis.delete(lock_key)
        else:
            # Someone else has lock - wait and retry
            time.sleep(0.1)
            # Retry cache (winner should have cached it)
            return self.redis.get(key) or fetch_func()

Java

CacheWithLock.java

import redis.clients.jedis.Jedis;
import java.util.UUID;

class CacheWithLock {
    private final Jedis redis;
    private final int lockTtl = 10;

    public CacheWithLock(Jedis redis) {
        this.redis = redis;
    }

    public String getWithLock(String key, Supplier<String> fetchFunc) {
        // Try cache first
        String cached = redis.get(key);
        if (cached != null) {
            return cached;
        }

        // Cache miss - try to acquire lock
        String lockKey = "lock:" + key;
        String lockValue = UUID.randomUUID().toString();

        // Try to acquire lock (set if not exists)
        boolean acquired = "OK".equals(
            redis.set(lockKey, lockValue, "NX", "EX", lockTtl)
        );

        if (acquired) {
            // We got the lock - fetch from DB
            try {
                String data = fetchFunc.get();
                redis.setex(key, 300, data);
                return data;
            } finally {
                // Release lock (only if we still own it)
                if (lockValue.equals(redis.get(lockKey))) {
                    redis.del(lockKey);
                }
            }
        } else {
            // Someone else has lock - wait and retry
            try {
                Thread.sleep(100);
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
            // Retry cache (winner should have cached it)
            String retry = redis.get(key);
            return retry != null ? retry : fetchFunc.get();
        }
    }
}

Solution 2: Probabilistic Early Expiration

Refresh cache randomly before expiration. Spreads load over time.

How it works:

1. Set TTL (e.g., 300 seconds)
2. In last 10% of TTL (270-300s), randomly refresh
3. First request in window refreshes cache
4. Others use refreshed cache
5. Spreads refresh load over time

Python

"probabilistic_refresh.py

import random
import time

class ProbabilisticRefreshCache:
    def __init__(self, cache: CacheClient, db: Database):
        self.cache = cache
        self.db = db

    def get_with_refresh(self, key: str, ttl: int = 300):
        cached_data = self.cache.get(key)

        if cached_data:
            # Check if we should refresh (last 10% of TTL)
            # This is simplified - in practice, store timestamp
            if random.random() < 0.1:  # 10% chance
                # Refresh in background
                self._refresh_async(key, ttl)

            return cached_data

        # Cache miss - fetch and cache
        data = self.db.fetch(key)
        self.cache.set(key, data, ttl=ttl)
        return data

    def _refresh_async(self, key: str, ttl: int):
        # Background refresh (simplified)
        data = self.db.fetch(key)
        self.cache.set(key, data, ttl=ttl)

Java

ProbabilisticRefreshCache.java

import java.util.Random;

class ProbabilisticRefreshCache {
    private final CacheClient cache;
    private final Database db;
    private final Random random = new Random();

    public ProbabilisticRefreshCache(CacheClient cache, Database db) {
        this.cache = cache;
        this.db = db;
    }

    public String getWithRefresh(String key, int ttl) {
        String cached = cache.get(key);

        if (cached != null) {
            // Check if we should refresh (last 10% of TTL)
            if (random.nextDouble() < 0.1) {  // 10% chance
                // Refresh in background
                refreshAsync(key, ttl);
            }

            return cached;
        }

        // Cache miss - fetch and cache
        String data = db.fetch(key);
        cache.set(key, data, ttl);
        return data;
    }

    private void refreshAsync(String key, int ttl) {
        // Background refresh (simplified)
        String data = db.fetch(key);
        cache.set(key, data, ttl);
    }
}

---

Invalidation Strategies Comparison

Strategy	Consistency	Complexity	Latency	Use Case
Write-Through	Strong	Low	High (write)	Critical data
Write-Invalidate	Eventual	Low	Low (write)	General purpose
TTL	Eventual	Low	Low	Read-heavy
Event-Driven	Strong	High	Low	Complex systems

---

Key Takeaways

🔥 Hardest Problem

Cache invalidation is famously difficult. Choose strategy based on consistency needs.

⚡ Write-Invalidate

Most common: delete cache on write. Next read fetches fresh. Simple and effective.

🐘 Prevent Stampede

Use distributed locks or probabilistic refresh to prevent cache stampede.

🔄 Event-Driven

For complex systems, use event-driven invalidation for precise control.

---

Next Steps

• Understand CDN & Edge Caching - caching at the edge for global users
• Review Caching Fundamentals - the four fundamental patterns