Cache Invalidation

Cache Invalidation Strategies

Cache invalidation is the process of removing or updating cached data when the underlying data changes.

Strategy Overview

Invalidation Strategies:

1. Time-Based (TTL):
   - Auto-expire after duration
   - Simple, automatic
   - May serve stale data

2. Event-Based:
   - Invalidate on data change
   - Immediate consistency
   - More complex

3. Version-Based:
   - Cache key includes version
   - New version = new key
   - Automatic invalidation

4. Manual Invalidation:
   - Explicit delete/update
   - Full control
   - Requires code changes

Implementation Patterns

# 1. Direct Invalidation
def update_user(user_id, data):
    db.update(user_id, data)
    cache.delete(f"user:{user_id}")

# 2. Pattern-Based Invalidation
def invalidate_user_cache(user_id):
    # Delete all cache entries for this user
    keys = cache.keys(f"user:{user_id}:*")
    cache.delete(*keys)

# 3. Tag-Based Invalidation
def invalidate_by_tag(tag):
    # Delete all entries with this tag
    keys = cache.keys(f"tag:{tag}:*")
    cache.delete(*keys)

# 4. Version-Based Keys
def get_user_versioned(user_id, version):
    key = f"user:{user_id}:v{version}"
    return cache.get(key)

Time-Based Invalidation (TTL)

TTL Implementation

class TTLCache:
    def __init__(self, redis_client):
        self.redis = redis_client
    
    def set_with_ttl(self, key, value, ttl_seconds):
        """Set with explicit TTL"""
        self.redis.setex(key, ttl_seconds, json.dumps(value))
    
    def get_ttl(self, key):
        """Get remaining TTL"""
        return self.redis.ttl(key)
    
    def refresh_ttl(self, key, new_ttl):
        """Refresh TTL on access"""
        self.redis.expire(key, new_ttl)

# Usage
cache.set_with_ttl("user:123", user_data, ttl_seconds=3600)

# Remaining TTL
ttl = cache.get_ttl("user:123")  # 3599, 3598, ...

TTL Strategies

Strategy	Description	Use Case
Fixed TTL	Same duration for all entries	General purpose
Variable TTL	Different TTLs per data type	Mixed workloads
Sliding TTL	Refresh on access	Active data
Adaptive TTL	Adjust based on patterns	Dynamic workloads

Stale Data Window

TTL Analysis:

Data written: 10:00 AM
TTL: 1 hour
Data updated: 10:30 AM (in DB)

10:00 - 11:00: Cache serves data (potentially stale after 10:30)
11:00: Cache expires, next read gets fresh data

Stale window: Up to 30 minutes in this example

Event-Based Invalidation

Event-Driven Architecture

Event-Based Flow:

Data Change → Event Published → Consumer Invalidates Cache

Components:
1. Event Producer (DB trigger, app code)
2. Event Bus (Kafka, RabbitMQ)
3. Event Consumer (Cache invalidator)

Implementation with Event Bus

# Producer: Publish invalidation event
def update_product(product_id, data):
    db.update(product_id, data)
    
    # Publish invalidation event
    event_bus.publish('cache.invalidation', {
        'type': 'product',
        'id': product_id,
        'timestamp': time.time()
    })

# Consumer: Handle invalidation events
def handle_invalidation_event(event):
    if event['type'] == 'product':
        cache.delete(f"product:{event['id']}")
        # Also invalidate related caches
        cache.delete(f"product:{event['id']}:details")
        cache.delete(f"product:{event['id']}:reviews")

# Subscribe to events
event_bus.subscribe('cache.invalidation', handle_invalidation_event)

Database Trigger Approach

-- PostgreSQL example
CREATE OR REPLACE FUNCTION invalidate_cache()
RETURNS TRIGGER AS $$
BEGIN
    -- Publish to notification channel
    PERFORM pg_notify('cache_invalidation', 
        json_build_object(
            'table', TG_TABLE_NAME,
            'id', NEW.id,
            'operation', TG_OP
        )::text
    );
    RETURN NEW;
END;
$$ LANGUAGE plpgsql;

CREATE TRIGGER user_cache_invalidation
AFTER INSERT OR UPDATE ON users
FOR EACH ROW EXECUTE FUNCTION invalidate_cache();

Pros and Cons

Aspect	Time-Based	Event-Based
Consistency	Eventual	Stronger
Complexity	Simple	Complex
Network overhead	None	Event bus traffic
Reliability	Automatic	Depends on event delivery
Latency	Up to TTL delay	Near real-time

The Two Hard Problems of Caching

Phil Karlton famously said: "There are only two hard things in Computer Science: cache invalidation and naming things."

Why Cache Invalidation is Hard

Challenges:

1. Distributed Consistency:
   - Multiple cache nodes
   - Network partitions
   - Eventual consistency

2. Complex Data Relationships:
   - Derived data
   - Aggregations
   - Cross-entity dependencies

3. Timing Issues:
   - Race conditions
   - Concurrent updates
   - Out-of-order events

4. Failure Scenarios:
   - Lost invalidation events
   - Partial failures
   - Recovery after crash

Common Solutions

# 1. Version-Based Keys (Simplest)
def get_user(user_id, version=None):
    if version is None:
        version = get_user_version(user_id)
    return cache.get(f"user:{user_id}:v{version}")

# 2. Cache Stampede Prevention
def get_with_lock(key, loader):
    value = cache.get(key)
    if value is None:
        if lock.acquire(f"lock:{key}"):
            try:
                value = loader()
                cache.set(key, value)
            finally:
                lock.release(f"lock:{key}")
    return value

# 3. Read-Through with Versioning
class VersionedReadThrough:
    def get(self, key, version):
        versioned_key = f"{key}:v{version}"
        value = cache.get(versioned_key)
        if value is None:
            value = db.get(key)
            cache.set(versioned_key, value)
        return value

Best Practices

1. Use short TTLs as a safety net
2. Implement idempotent invalidation
3. Version your cache keys
4. Monitor stale data detection
5. Have fallback mechanisms