Chapter 21: Caching Strategies

1. Why Cache

Latency Comparison

Benefits Beyond Latency

Cache Hierarchy

2. Cache-Aside (Lazy Loading)

Read Flow

Write Flow

Trade-offs

Implementation Patterns

3. Write-Through Cache

Write Flow

Trade-offs

Use Cases

4. Write-Behind (Write-Back) Cache

Write Flow

Trade-offs

Failure Scenarios

Use Cases

5. Read-Through Cache

Read Flow

Comparison: Read-Through vs Cache-Aside

Implementation Details

Example: Guava Cache (Java)

LoadingCache<String, User> cache = CacheBuilder.newBuilder()
    .maximumSize(10000)
    .expireAfterWrite(10, TimeUnit.MINUTES)
    .refreshAfterWrite(8, TimeUnit.MINUTES)  // Async refresh before expiry
    .build(new CacheLoader<String, User>() {
        public User load(String userId) throws Exception {
            return database.getUser(userId);  // Called on miss
        }
    });

// Application code - cache miss handled transparently
User user = cache.get("user:123");  // Blocks if loading, returns immediately if cached

6. Cache Invalidation

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

Invalidation Strategies

TTL Best Practices

Thundering Herd on Expiry

Mitigation Strategies

7. Eviction Policies

Common Algorithms

Hit Rate Comparison (Simulated Workload)

Redis Eviction Policies

8. Cache Stampede

Problem: Concurrent Misses

Solutions Comparison

Locking Implementation

def get_with_lock(key):
    data = cache.get(key)
    if data:
        return data

    lock_key = f"lock:{key}"
    lock_acquired = cache.set(lock_key, "1", nx=True, ex=10)  # 10s timeout

    if lock_acquired:
        try:
            data = db.query(key)
            cache.set(key, data, ex=3600)
            return data
        finally:
            cache.delete(lock_key)  # Release lock
    else:
        # Another thread is loading, wait and retry
        time.sleep(0.1)
        return get_with_lock(key)  # Retry (or loop with timeout)

Probabilistic Early Expiry

def get_with_early_refresh(key):
    entry = cache.get_with_metadata(key)  # Returns {data, created_at, ttl}

    if not entry:
        # Hard miss - load from DB
        data = db.query(key)
        cache.set(key, data, ex=3600)
        return data

    # Probabilistic refresh before expiry
    age = now() - entry.created_at
    refresh_probability = age / entry.ttl

    if random() < refresh_probability:
        # Refresh in background (non-blocking)
        background_task(lambda: refresh_cache(key))

    return entry.data  # Return cached data (may be slightly stale)

# Refresh probability increases as TTL approaches:
# Age=0s (just cached): 0% chance
# Age=1800s (50% of 3600s TTL): 50% chance
# Age=3500s (97% of TTL): 97% chance

Stale-While-Revalidate

def get_stale_while_revalidate(key):
    entry = cache.get_with_expiry(key)  # Returns {data, expired}

    if entry and not entry.expired:
        return entry.data  # Fresh data

    if entry and entry.expired:
        # Return stale data immediately
        background_task(lambda: refresh_cache(key))
        return entry.data  # Stale but instant

    # No data at all - synchronous load
    data = db.query(key)
    cache.set(key, data, ex=3600)
    return data

# HTTP header equivalent:
# Cache-Control: max-age=3600, stale-while-revalidate=60
# Browser can use stale data for 60s after expiry while fetching fresh

9. Multi-Layer Caching

Typical Architecture

Layer Characteristics

Request Flow Example

Invalidation Challenges

HTTP Cache-Control Headers

10. Consistency

Cache vs Database Divergence

Consistency Models

Facebook's Lease Approach

Facebook uses a lease-based invalidation protocol (TAO) to handle race conditions:

Lease Protocol Steps

Alternative: Read-After-Write Pattern

def update_with_consistency(key, new_value):
    # Write to DB
    db.update(key, new_value)

    # Invalidate cache
    cache.delete(key)

    # Option 1: Warm cache immediately (read-your-writes)
    fresh_data = db.query(key)
    cache.set(key, fresh_data, ttl=3600)

    # Option 2: Return DB data directly (bypass cache for this request)
    return fresh_data

# Risk: If another thread writes between delete and set, race condition
# Mitigation: Use versioned keys or leases

11. When NOT to Cache

Anti-Patterns

Decision Framework

Cost-Benefit Analysis

12. Sizing & Monitoring

Working Set Calculation

Redis Overhead

Hit Rate Targets

Monitoring Metrics

Cache Warming Strategies

Capacity Planning Example

# Given:
# - 10M active users/day
# - 80/20 rule: 20% of users = 80% of traffic
# - Avg 10 API calls/user/day
# - Cache user profiles (10KB) and session (2KB)

Hot users = 10M × 20% = 2M
Cache entries = 2M users × (1 profile + 1 session) = 4M keys
Memory = 2M × 10KB + 2M × 2KB = 24GB
With overhead (1.3x) = 31GB
With growth buffer (2x) = 62GB

Redis configuration:
- 3-node cluster (replication factor 2)
- 64GB RAM per node
- maxmemory-policy: allkeys-lru
- TTL: session 30min, profile 1hr

Production Implementation Examples

Cache Stampede Prevention: XFetch Algorithm (Probabilistic Refresh)

Actual production pseudocode for preventing thundering herd using probabilistic early refresh:

def get_with_probabilistic_refresh(key, ttl, beta=1.0):
    """
    XFetch algorithm: Probabilistically refresh before expiry to prevent stampede.

    Args:
        key: Cache key
        ttl: Time-to-live in seconds (e.g., 3600 for 1 hour)
        beta: Refresh probability multiplier (default 1.0)
              Higher beta = more aggressive refresh (more stale data)
              Lower beta = less aggressive (more stampede risk)

    Returns:
        Cached value (may trigger async refresh)
    """
    # Attempt to get value with metadata (created_at, expiry)
    value, expiry = cache.get_with_ttl(key)

    if value is None:
        # Hard cache miss - synchronously recompute
        value = recompute(key)
        cache.set(key, value, ttl)
        return value

    # Value exists - calculate probabilistic refresh
    now_ts = time.time()
    remaining = expiry - now_ts

    # XFetch probability formula:
    # P(refresh) increases as expiry approaches
    # P = 0 at creation, P ≈ 1 near expiry
    refresh_probability = beta * random.random() * (ttl / remaining)

    if refresh_probability >= 1.0:
        # Probabilistic early refresh triggered
        # Refresh in background (non-blocking)
        background_task(lambda: refresh_cache_async(key, ttl))

    # Always return cached value immediately (even if refreshing)
    return value

def refresh_cache_async(key, ttl):
    """Background refresh job (runs in thread pool or async worker)"""
    try:
        new_value = recompute(key)
        cache.set(key, new_value, ttl)
    except Exception as e:
        log_error(f"Cache refresh failed for {key}: {e}")
        # Keep stale cache entry (graceful degradation)

# Refresh probability examples (TTL=3600s, beta=1.0):
# Time since creation | Remaining | P(refresh)
# -------------------+-----------+------------
# 0s (just cached)    | 3600s     | ~0% (3600/3600 × rand(0-1) = ~0-1)
# 1800s (50% TTL)     | 1800s     | ~50% (3600/1800 × rand(0-1) = ~0-2 = 50% >1)
# 3500s (97% TTL)     | 100s      | ~97% (3600/100 × rand(0-1) = ~0-36 = 97% >1)
# 3600s (expired)     | 0s        | 100% (handled by cache miss path)

Capacity Planning Worked Example

Design a Redis cache cluster for a high-traffic service:

Requirements

Step 1: Cache QPS Calculation

Cache QPS = Total QPS × Cache-Eligible %
          = 100,000 × 0.9
          = 90,000 cache lookups/sec

DB QPS (with cache) = Cache QPS × (1 - Hit Rate)
                    = 90,000 × 0.15
                    = 13,500 DB queries/sec

DB QPS (without cache) = 90,000 queries/sec

DB Load Reduction = 90,000 / 13,500 = 6.7x
                  → Cache reduces DB load by 85%

Step 2: Memory Sizing

Raw Data Size = Unique Keys × Avg Value Size
              = 1,000,000 × 2 KB
              = 2,000,000 KB = 2 GB

Redis Overhead (20%):
- Key storage: ~50 bytes per key = 50 MB
- Redis object metadata: ~16 bytes per key = 16 MB
- Hash table overhead: ~24 bytes per key = 24 MB
- Fragmentation: ~10% of data size = 200 MB
Total Overhead ≈ 20% = 400 MB

Total Memory Required = 2 GB + 0.4 GB = 2.4 GB

Safety Buffer (for growth, spikes, evictions):
- Add 50% buffer = 2.4 GB × 1.5 = 3.6 GB
- Round up to next instance size: 4 GB

Step 3: Redis Cluster Sizing

Chosen Configuration: Option 1 (Single Master + 2 Replicas)

• Node Type: AWS r6g.large (16 GB RAM, 2 vCPU, $0.133/hr)
• Cluster: 1 master + 2 replicas = 3 nodes
• Cost: 3 nodes × $0.133/hr × 730 hrs/mo = $291/month

Step 4: ROI Calculation

Without Cache:
- DB QPS: 90,000 queries/sec
- DB instance cost (to handle 90K QPS): ~$5,000/month (provisioned IOPS, large instance)

With Cache:
- DB QPS: 13,500 queries/sec (6.7x reduction)
- DB instance cost: ~$750/month (smaller instance, fewer IOPS)
- Cache cost: $291/month (Redis cluster)
- Total: $1,041/month

Savings = $5,000 - $1,041 = $3,959/month

ROI = $3,959 / $291 = 13.6x return on cache investment
    = $47,508/year savings

Facebook's TAO Cache (Simplified Architecture)

Facebook's social graph cache (TAO: The Associations and Objects) uses a two-tier cache hierarchy:

TAO Architecture Details

Consistency via Invalidation Messages

TAO uses a write-through invalidation protocol:

1. Write Path:
   • Client writes to database (e.g., UPDATE users SET status='online')
   • DB write triggers invalidation message to Kafka/pub-sub
   • All L1 and L2 caches in all regions subscribe to invalidation topic
   • Caches delete affected keys (e.g., DELETE user:123:status)
2. Propagation Latency: 10-50ms (eventual consistency across regions)
3. Handling Lag: Brief window of stale reads (acceptable for social data)

Key Optimizations

Real-World Lessons: Cache Stampede in Production

Case study from a major e-commerce site (Black Friday):

Incident Timeline

Root Cause & Fix

• Root Cause: No stampede protection. Cache expiry triggered thundering herd: 10K concurrent cache misses → 10K DB queries.
• Immediate Fix: Deploy cache locking (SETNX lock pattern). First miss acquires lock, others wait. Reduced 10K queries to 1 query.
• Long-Term Fix: Implement XFetch probabilistic refresh. Keys refresh before expiry (no hard expiry stampede). Jittered TTL (15 min ± 2 min) prevents simultaneous expirations.
• Monitoring: Add alerting on cache miss rate >20% and DB connection pool >80% capacity.