Caching System Design.
Cheat sheet.

Comprehensive guide to caching strategies for system design interviews. Covers cache locations, eviction policies, distributed caching, and implementation patterns. Essential for optimizing system performance, reducing latency, and scaling read-heavy workloads effectively.

What is Caching?

• Definition: Storing frequently accessed data in fast storage layer
• Purpose: Reduce latency, decrease load on primary data source, improve performance
• Trade-off: Memory vs Speed

Cache Hit vs Cache Miss

• Cache Hit: Data found in cache (fast)
• Cache Miss: Data not in cache, fetch from source (slow)
• Hit Rate: (Cache Hits / Total Requests) × 100

1. Browser Cache

• Stores static assets (CSS, JS, images)
• Controlled via HTTP headers

2. CDN (Content Delivery Network)

• Geographically distributed servers
• Caches static content close to users

3. Web Server Cache

• Reverse proxy cache (Nginx, Varnish)
• Caches HTTP responses

4. Application Cache

• In-memory cache in application layer
• Examples: Redis, Memcached

5. Database Cache

• Query result cache
• Buffer pool (InnoDB)

1. Cache-Aside (Lazy Loading)

def get_data(key):
    # Check cache first
    data = cache.get(key)
    if data is None:
        # Cache miss - fetch from DB
        data = db.query(key)
        cache.set(key, data)
    return data

• Pros: Only cache what's needed
• Cons: Cache miss penalty, potential stale data

2. Write-Through

def save_data(key, value):
    # Write to cache and DB
    cache.set(key, value)
    db.save(key, value)

• Pros: Cache always consistent with DB
• Cons: Higher write latency

3. Write-Behind (Write-Back)

def save_data(key, value):
    # Write to cache immediately
    cache.set(key, value)
    # Queue for async DB write
    queue.add_write(key, value)

• Pros: Low write latency
• Cons: Risk of data loss, complex implementation

4. Refresh-Ahead

• Proactively refresh cache before expiration
• Good for predictable access patterns

1. LRU (Least Recently Used)

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.cache = OrderedDict()
        self.capacity = capacity
    
    def get(self, key):
        if key in self.cache:
            # Move to end (most recent)
            self.cache.move_to_end(key)
            return self.cache[key]
        return None
    
    def put(self, key, value):
        self.cache[key] = value
        self.cache.move_to_end(key)
        if len(self.cache) > self.capacity:
            # Remove least recent
            self.cache.popitem(last=False)

2. LFU (Least Frequently Used)

• Tracks access frequency
• Removes least accessed items

3. FIFO (First In First Out)

• Simple queue-based eviction
• Not optimal for most use cases

4. TTL (Time To Live)

• Items expire after fixed time
• Good for time-sensitive data

Strategies

1. TTL-based: Automatic expiration
2. Event-based: Invalidate on update events
3. Manual: Explicit cache clear

Patterns

# Tagged invalidation
cache.set("user:123:profile", data, tags=["user:123"])
cache.set("user:123:posts", posts, tags=["user:123"])
# Invalidate all user data
cache.delete_by_tag("user:123")

Consistent Hashing

• Minimizes redistribution when nodes added/removed
• Virtual nodes for better distribution

Replication Strategies

1. Master-Slave: Read replicas
2. Peer-to-Peer: All nodes equal
3. Sharding: Data partitioned across nodes

Cache Coherence

• Strong Consistency: All nodes see same data
• Eventual Consistency: Nodes converge over time
• Weak Consistency: No guarantees

Redis

# Connection
import redis
r = redis.Redis(host='localhost', port=6379)

# Basic operations
r.set('key', 'value', ex=3600)  # TTL 1 hour
value = r.get('key')

# Data structures
r.hset('user:123', 'name', 'John')
r.lpush('queue', 'task1')

Memcached

import memcache
mc = memcache.Client(['127.0.0.1:11211'])
mc.set('key', 'value', time=3600)
value = mc.get('key')

Comparison

Key Metrics

1. Hit Rate: Higher is better (>90% ideal)
2. Miss Rate: Lower is better
3. Eviction Rate: Monitor for capacity issues
4. Latency: Cache vs source comparison

Monitoring

# Simple cache metrics
class CacheMetrics:
    def __init__(self):
        self.hits = 0
        self.misses = 0
    
    def record_hit(self):
        self.hits += 1
    
    def record_miss(self):
        self.misses += 1
    
    def hit_rate(self):
        total = self.hits + self.misses
        return self.hits / total if total > 0 else 0

1. Cache Warming

# Pre-populate cache on startup
def warm_cache():
    popular_items = db.get_popular_items()
    for item in popular_items:
        cache.set(f"item:{item.id}", item)

2. Circuit Breaker

def get_with_fallback(key):
    try:
        return cache.get(key)
    except CacheException:
        # Fallback to DB if cache fails
        return db.get(key)

3. Multi-Level Cache

def get_data(key):
    # L1: Local cache
    data = local_cache.get(key)
    if data:
        return data
    
    # L2: Redis
    data = redis_cache.get(key)
    if data:
        local_cache.set(key, data)
        return data
    
    # L3: Database
    data = db.query(key)
    redis_cache.set(key, data)
    local_cache.set(key, data)
    return data

Key Design Challenges

• Distributed Cache Design: Consistent hashing, replication strategies, failure handling
• Cache vs Database Trade-offs: Consistency requirements, staleness tolerance, cost considerations
• Cache Stampede Prevention: Lock-based protection, probabilistic expiration, request coalescing
• Cache Warming Strategies: Predictive loading, lazy loading, scheduled refresh
• Multi-tier Caching: L1/L2/L3 cache hierarchies, cache coherence protocols

Design Considerations

1. Cache Size: Monitor memory usage
2. Key Design: Include version in key for easy invalidation
3. Serialization: Consider format (JSON, Protocol Buffers)
4. Security: Don't cache sensitive data in shared caches

Anti-Patterns to Avoid

1. Caching Everything: Wastes memory
2. No Invalidation Strategy: Stale data forever
3. Single Point of Failure: Always have fallback
4. Ignoring Cache Misses: Monitor and optimize

When to Use Caching

• Expensive computations
• Frequent database queries
• External API calls
• Static/semi-static content
• Session data
• Configuration values

When NOT to Cache

• Rapidly changing data
• User-specific sensitive data
• Large datasets with random access
• Write-heavy workloads
• Transactional data
• Real-time analytics

Cache Key Best Practices

# Good
cache_key = f"user:{user_id}:profile:v2"
cache_key = f"product:{product_id}:{locale}"

# Bad
cache_key = "user_profile"  # No versioning
cache_key = str(user_id)    # No namespace

• Effective Access Time = (Hit Rate × Cache Time) + (Miss Rate × Memory Time)
• Cache Size = Number of Entries × (Key Size + Value Size + Metadata)
• Optimal TTL = Balance between freshness and hit rate

1. Clarify Requirements

   • Read/write ratio
   • Data size and access patterns
   • Consistency requirements

2. Choose Cache Strategy

   • Based on consistency needs
   • Consider implementation complexity

3. Design Cache Layer

   • Location (client/server/DB)
   • Technology choice
   • Eviction policy

4. Handle Edge Cases

   • Cache failures
   • Thundering herd
   • Data inconsistency

5. Scale Considerations

   • Sharding strategy
   • Replication needs
   • Monitoring approach

• Cache Hit Rate: Aim for >90% for effective caching
• Consistency vs Performance: Clear trade-off decision required
• Monitoring: Essential for cache effectiveness
• Invalidation: Hardest problem in caching
• Distribution: Consistent hashing for scalability
• Layers: Multiple cache levels for optimal performance