Cache Design (HLD)

Principles of What to Cache

Caching is not free. Every cache entry consumes memory, adds complexity to your invalidation logic, and introduces consistency risks. The key question is: is the cost of caching less than the cost of recomputing or re-fetching?

Categories of Cacheable Data

Category	Example	Cache Benefit
Expensive database queries	JOIN across 5 tables for product recommendations	Reduces DB load by 10-100x
Static or semi-static content	Product images, CMS pages, configuration	Eliminates repeated fetches
Session data	User login state, shopping cart	Enables stateless app servers
Computed/aggregated results	Leaderboard scores, analytics dashboards	Avoids repeated heavy computation
External API responses	Third-party weather, exchange rates	Reduces latency and API costs

Cost-Benefit Analysis

Before caching, ask:

1. How often is this data read? High read-to-write ratio (10:1 or more) makes caching very attractive.
2. How expensive is the uncached path? A 200ms DB query is worth caching; a 1ms in-memory lookup is not.
3. How stale can the data be? If users can tolerate 5 minutes of staleness, TTL-based caching is simple and effective.
4. How large is the data? Caching 10KB per user is fine; caching 10MB per user may not fit in memory.
5. What is the write frequency? High write frequency means frequent invalidation, which erodes cache benefits.

What NOT to Cache

• User-specific data with low reuse (e.g., a single user's draft document viewed once)
• Data that changes on every read (e.g., real-time stock prices with sub-second freshness)
• Extremely large objects that don't fit cache memory efficiently
• Data with strict strong-consistency requirements where even brief staleness is unacceptable

Prioritization Framework

Score each potential cache candidate on a 1-5 scale:

• Read frequency (5 = millions of reads/day)
• Compute cost (5 = takes seconds to generate)
• Staleness tolerance (5 = can be minutes old)
• Size efficiency (5 = under 1KB)

Items scoring 15+ out of 20 are strong cache candidates.

Cache-Aside (Lazy Loading)

The application is responsible for all cache interactions. The cache is a passive key-value store.

Read path:

1. App checks cache for key
2. If hit → return cached value
3. If miss → query database → write result to cache → return value

Write path:

1. App writes to database
2. App invalidates (deletes) the cache entry

App ──lookup──► Cache
  │               │
  │ miss          │ hit
  ▼               │
Database          │
  │               │
  └──write back───┘

Pros: Simple, only cached data is loaded, resilient to cache failures.
Cons: First request for any key always results in a cache miss (cold start).

Read-Through

The cache itself is responsible for loading data on a miss. The application only talks to the cache.

App ──read──► Cache ──miss──► Database
  │              │
  ◄──────────────┘

Pros: Application code is simpler. Cache warming happens automatically.
Cons: Cache layer must understand your data source. Tighter coupling.

Write-Through

Writes go to both the cache and the database synchronously. The cache is always consistent with the database.

App ──write──► Cache ──write──► Database
  │              │
  ◄──────────────┘

Pros: Strong consistency. Reads after writes always hit cache.
Cons: Write latency increases (two synchronous writes). Cache may hold data that is rarely read.

Write-Behind (Write-Back)

Writes go to the cache first. The cache asynchronously flushes to the database.

App ──write──► Cache ──async flush──► Database
  │              │
  ◄──────────────┘

Pros: Very fast writes. Can batch database writes for efficiency.
Cons: Risk of data loss if cache crashes before flush. Increased complexity.

Comparison Table

Strategy	Read Latency	Write Latency	Consistency	Complexity
Cache-Aside	Medium (miss on cold)	Low	Eventual	Low
Read-Through	Low (auto-load)	N/A	Eventual	Medium
Write-Through	Low	High (sync dual-write)	Strong	Medium
Write-Behind	Low	Very Low	Eventual	High

Multi-Layer Cache Architecture

Most production systems use multiple cache layers, each serving a different purpose:

Client
  │
  ▼
CDN Cache (Edge) ─── Static assets, API responses
  │
  ▼
Application-Level Cache (Local/In-Process) ─── Hot data, config
  │
  ▼
Distributed Cache (Redis/Memcached Cluster) ─── Shared state
  │
  ▼
Database (with its own buffer pool)

Local (In-Process) Cache

• Lives in the application's memory space
• Examples: Guava Cache (Java), LRU Cache (Python functools.lru_cache), node-cache (Node.js)
• Latency: Nanoseconds (memory access)
• Scope: Single process only
• Use cases: Configuration flags, hot lookups, rate limiter counters
• Consistency: Perfect within one process, but no shared state across instances

Distributed Cache

A separate service accessed over the network by all application instances.

Redis:

• Data structures: strings, hashes, lists, sets, sorted sets, streams, HyperLogLog
• Persistence: RDB snapshots and AOF (Append Only File)
• Replication: Master-replica with automatic failover (Redis Sentinel or Redis Cluster)
• Max throughput: ~100K-500K ops/sec per node

Memcached:

• Pure key-value (strings only)
• Multi-threaded (better CPU utilization per node)
• No persistence, no replication
• Simpler operational model
• Max throughput: ~100K-200K ops/sec per node

CDN Cache

• Sits at the edge, close to users
• Caches static content (images, CSS, JS) and API responses with appropriate headers
• Controlled via HTTP headers: Cache-Control, ETag, Vary
• Invalidation: Purge APIs (CloudFront, Cloudflare), versioned URLs
• Best for: Content that is the same for many users and doesn't change frequently

Cache Topology Patterns

Single-Instance Cache:
One Redis instance. Simple, but single point of failure.

Replicated Cache:
One primary, multiple read replicas. Good for read-heavy workloads. Writes go to primary, reads load-balance across replicas.

Partitioned (Sharded) Cache:
Data is spread across multiple Redis instances using consistent hashing. Used when data exceeds a single node's memory. Redis Cluster provides automatic sharding.

Tiered Cache:
Local cache in front of distributed cache. Reduces network calls for hot keys. Requires coordination for invalidation.

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

TTL (Time-To-Live)

The simplest approach: each cache entry has an expiration time.

SET user:1234 {name: "Alice"} EX 3600  // Expires in 1 hour

Pros: Self-healing. Stale data is automatically purged. No coordination needed.
Cons: You choose between freshness (short TTL) and hit rate (long TTL).

TTL jitter: Add randomness to TTLs to prevent synchronized expiration of many keys at once (thundering herd on the database). Instead of EX 3600, use EX (3600 + random(0, 300)).

Event-Based Invalidation

Delete cache entries when the underlying data changes.

// On data write
UPDATE users SET name = 'Bob' WHERE id = 1234;
DELETE cache:user:1234;  // Invalidate immediately

Can be implemented via:

• Direct deletion in application code
• Database triggers publishing change events
• CDC (Change Data Capture) with tools like Debezium polling the DB binlog

Pros: Cache is always fresh (low staleness).
Cons: Complex. Race conditions: read-miss-write can re-populate stale data if writes and invalidations are not atomic.

Versioned Keys

Instead of invalidating, include a version in the cache key:

cache:user:1234:v7

When the data changes, increment the version. Old keys expire naturally.

Pros: No need to delete old keys. Avoids race conditions.
Cons: Temporary memory bloat from old versions. Requires a version counter somewhere (database row, Redis counter).

Invalidation Patterns Comparison

Strategy	Staleness	Complexity	Memory Efficiency
TTL	Bounded by TTL	Low	High (auto-cleanup)
Event-Based	Near-zero	High	High (explicit delete)
Versioned Keys	Near-zero	Medium	Medium (old versions linger)

Cache Stampede (Thundering Herd)

When a popular cache key expires, hundreds or thousands of concurrent requests all see a cache miss simultaneously, all hit the database at once, and the database may overload.

Time ──►

Key expires
  │
  ├─ Request 1 ──► MISS ──► DB query ──► SET cache
  ├─ Request 2 ──► MISS ──► DB query ──► SET cache (redundant)
  ├─ Request 3 ──► MISS ──► DB query ──► SET cache (redundant)
  └─ ... 500 more requests

Prevention Techniques

1. Mutex Locking (Singleflight)

Only one process loads the cache; others wait or get stale data.

// Go singleflight example
var group singleflight.Group

func getData(key string) (interface{}, error) {
    val, err, _ := group.Do(key, func() (interface{}, error) {
        // Only one goroutine executes this
        return fetchFromDB(key)
    })
    return val, err
}

2. Probabilistic Early Expiration

Before the TTL actually expires, a small percentage of requests proactively refresh the cache.

if (TTL_remaining / TTL_total) < random(0, 1):
    refresh asynchronously

3. Stale-While-Return

Serve the stale value immediately while asynchronously refreshing.

if (cache_expired):
    serve stale value
    trigger async refresh

4. Request Coalescing

Deduplicate in-flight requests for the same key at the load balancer or application level.

Hot Keys

Some keys are accessed far more frequently than others. Even with caching, a single Redis node serving a hot key can become a bottleneck.

Solutions:

• Local caching: Cache hot keys in the application process memory. Add a short TTL (seconds) to keep them fresh.
• Replication: Use Redis read replicas and load-balance reads across them.
• Key splitting: Replicate the hot key into multiple copies: hot_key:1, hot_key:2, etc. Randomly read from one.
• Write-behind aggregation: Batch updates to hot keys and write less frequently.

Cache Sharding

When data exceeds the capacity of a single cache node, shard across multiple nodes.

Consistent Hashing:

• Map both keys and cache nodes onto a ring (0 to 2^32)
• A key is stored on the next node clockwise from its hash position
• When a node is added/removed, only neighboring keys need to move
• Virtual nodes ensure even distribution

       Node A (15%)
          |
    ╱─────────────╲
   /               \
  Node D            Node B
   \               /
    ╲─────────────/
          |
       Node C (35%)

Redis Cluster uses 16,384 hash slots distributed across nodes.

Head-to-Head Comparison

Feature	Redis	Memcached
Data structures	Strings, hashes, lists, sets, sorted sets, streams, HyperLogLog	Strings only
Persistence	RDB + AOF	None
Replication	Master-replica, Redis Cluster	None built-in
Clustering	Redis Cluster (sharding)	Client-side sharding
Threading	Single-threaded (6.0+ has I/O threads)	Multi-threaded
Memory efficiency	Higher overhead per key	Lower overhead per key
Max value size	512 MB	1 MB default
Pub/Sub	Built-in	Not available
Lua scripting	Supported	Not available
TTL	Supported	Supported
Eviction policies	LRU, LFU, random, TTL	LRU only
Operations	Atomic, transactions, pipelines	Pipelines only

When to Choose Redis

• You need data structures beyond simple key-value (sorted sets for leaderboards, lists for queues)
• You need persistence or replication for high availability
• You need pub/sub for real-time messaging
• You need atomic operations (INCR, WATCH, MULTI/EXEC)
• You want Lua scripting for complex server-side logic

When to Choose Memcached

• Your use case is purely simple key-value caching
• You want maximum throughput with minimal memory overhead
• You don't need persistence or replication
• You want simpler operations
• Multi-threaded performance is important (more CPU-efficient per node)

Recommendation for Most Amazon SDE-1 Interviews

Default to Redis. It is more versatile, covers more use cases, and is what most interviewers expect. Mention Memcached as an alternative for simpler caching needs.

Problem Statement

Design the caching layer for a news feed system (like Twitter's timeline). The system serves 100M daily active users. Each user follows 200 accounts on average. Feed generation involves aggregating posts from followed users.

Cache Architecture

User Request
  │
  ▼
App Server
  │
  ├─► Local Cache (hot feeds, top 1000 users)
  │
  ├─► Redis Cluster
  │     ├── Feed cache: feed:{user_id} → sorted set of post IDs
  │     ├── Post cache: post:{post_id} → post content
  │     └── User cache: user:{user_id} → user profile
  │
  └─► Database (MySQL/DynamoDB)

What to Cache

Data	Cache Key	TTL	Strategy
Pre-computed feed	feed:{user_id}	5 min	Write-Behind (fan-out on write)
Post content	post:{post_id}	1 hour	Cache-Aside
User profile	user:{user_id}	10 min	Cache-Aside
Follower list	followers:{user_id}	1 hour	Cache-Aside

Feed Generation Strategies

Fan-Out on Write (Push Model):
When a user posts, immediately push the post ID into the feed cache of all their followers.

def publish_post(user_id, post_id):
    # Write to database
    db.save_post(user_id, post_id)
    # Push to all followers' feed caches
    followers = get_followers(user_id)
    for follower_id in followers:
        redis.zadd(f"feed:{follower_id}", {post_id: timestamp})
        redis.zremrangebyrank(f"feed:{follower_id}", 0, -501)  # Keep last 500

Fan-Out on Read (Pull Model):
When a user requests their feed, fetch recent posts from all followed users and merge.

def get_feed(user_id):
    following = get_following(user_id)
    all_posts = []
    for fid in following:
        posts = redis.lrange(f"posts:{fid}", 0, 10)
        all_posts.extend(posts)
    return sorted(all_posts, key=lambda p: p.timestamp, reverse=True)[:50]

Hybrid (What Twitter/Facebook actually use):

• For regular users (< 10K followers): push on write
• For celebrities (> 10K followers): pull on read (too many followers to push to)
• Merge both at read time

Cache Warming

When a new user signs up or a dormant user returns, their feed cache is empty. Solutions:

1. Pre-compute on first login: Generate their feed asynchronously and store it.
2. Read-through with fallback: On miss, compute from DB and populate cache.
3. Background job: Periodically refresh feeds for active users.

Handling Hot Keys

Celebrity accounts (e.g., a post going viral) cause hot keys. Mitigations:

• Local cache the celebrity's post content in app servers
• Use Redis read replicas for the celebrity's feed cache
• Rate-limit feed refreshes for celebrity followers
• Asynchronous fan-out with priority queues