Distributed Cache

Problem Statement & Requirements

Design a distributed, in-memory caching system that sits between application servers and persistent storage to dramatically reduce read latency, offload databases, and absorb traffic spikes — similar to Redis, Memcached, or Amazon ElastiCache.

Functional Requirements

• GET / SET / DELETE — basic key-value operations with sub-millisecond latency
• TTL (Time-to-Live) — automatic key expiration
• Rich data structures — strings, hashes, lists, sets, sorted sets, bitmaps, HyperLogLog, streams
• Atomic operations — INCR, DECR, SETNX (set-if-not-exists), CAS (compare-and-swap)
• Pub/Sub — publish-subscribe messaging for cache invalidation and real-time events
• Lua scripting — execute atomic multi-step operations server-side
• Persistence — optional RDB snapshots and AOF (append-only file) for durability
• Cluster mode — automatic sharding across nodes with rebalancing
• Replication — master-replica for high availability and read scaling

Non-Functional Requirements

• Ultra-low latency — < 1 ms for cache hits (p99 < 2 ms)
• High throughput — 100K-1M+ operations/second per node
• High availability — 99.999% uptime with automatic failover
• Horizontal scalability — add nodes to increase capacity linearly
• Memory efficiency — maximize useful data per GB of RAM
• Consistency — strong consistency for single-key operations; eventual consistency across replicas
• Predictable performance — no garbage collection pauses, no swap, bounded tail latency

Out of Scope

• Full database replacement (we're designing a cache, not a primary data store)
• SQL query caching (application-level concern)
• Multi-region active-active replication (mention as extension)

Scale Estimations

Traffic

Storage

Bandwidth

Hardware Estimate (Per Node)

This first layer defines the system boundary. The next chapters add application logic and data dependencies. After examining the request paths and tradeoffs, we will add operational safeguards and bring the complete architecture together.

API Design

Core Operations

# String operations
SET key value [EX seconds] [PX milliseconds] [NX|XX]
GET key                           → value or nil
MGET key1 key2 key3              → [val1, val2, val3]  (batch read)
MSET key1 val1 key2 val2         → OK (batch write, atomic)
INCR key                          → new_value (atomic increment)
SETNX key value                   → 1 if set, 0 if already exists (mutex primitive)

# Hash operations (object caching)
HSET user:123 name "Alice" age 30 city "Tokyo"
HGET user:123 name               → "Alice"
HGETALL user:123                 → {name: "Alice", age: "30", city: "Tokyo"}

# List operations (queue, feed)
LPUSH queue:emails msg1 msg2     → push to head
RPOP queue:emails                → pop from tail (FIFO queue)
LRANGE feed:user:123 0 19       → get first 20 items

# Set operations (unique collections)
SADD tags:article:456 "redis" "cache" "design"
SISMEMBER tags:article:456 "redis"  → 1 (true)
SINTER tags:article:456 tags:article:789  → intersection

# Sorted set operations (leaderboards, priority queues)
ZADD leaderboard 9500 "player-A" 8200 "player-B" 9800 "player-C"
ZREVRANGE leaderboard 0 9 WITHSCORES   → top 10 players
ZRANK leaderboard "player-A"            → rank

# TTL and expiration
EXPIRE key 3600                  → expires in 1 hour
TTL key                          → seconds remaining (-1 = no expiry, -2 = doesn't exist)

# Pub/Sub
PUBLISH channel:inventory msg    → broadcast to all subscribers
SUBSCRIBE channel:inventory      → receive messages

# Atomic transactions (MULTI/EXEC)
MULTI
SET account:A:balance 900
SET account:B:balance 1100
EXEC                             → atomic execution of both commands

# Lua scripting (complex atomic operations)
EVAL "if redis.call('get',KEYS[1]) == ARGV[1] then
        return redis.call('del',KEYS[1])
      else return 0 end"
      1 lock:resource "lock-token-123"
→ atomic compare-and-delete (used for distributed locks)

Application-Level Caching Patterns (Client-Side)

# Cache-Aside (Lazy Loading) — most common
def get_user(user_id):
    cached = cache.get(f"user:{user_id}")
    if cached:
        return deserialize(cached)
    
    user = db.query("SELECT * FROM users WHERE id = ?", user_id)
    cache.set(f"user:{user_id}", serialize(user), ex=3600)
    return user

# Write-Through
def update_user(user_id, data):
    db.update("UPDATE users SET ... WHERE id = ?", data, user_id)
    cache.set(f"user:{user_id}", serialize(data), ex=3600)

# Write-Behind (Write-Back)
def update_user_async(user_id, data):
    cache.set(f"user:{user_id}", serialize(data), ex=3600)
    queue.enqueue("db_write", {"user_id": user_id, "data": data})
    # Background worker flushes to DB in batches

# Read-Through (cache library handles miss transparently)
# Configured at infrastructure level, not application code

Data Model

Internal Memory Layout

Data Structure Encodings (Memory Optimization)

Cluster Slot Assignment

Core Design Decisions

Decision 1: Single-Threaded vs Multi-Threaded Execution

This is the most debated design choice in cache systems.

Option A: Single-Threaded Command Execution (Redis)

Option B: Multi-Threaded (Memcached / Dragonfly)

Recommendation

Single-threaded command execution (Redis model) for most use cases:

• Simplicity and correctness trump raw throughput per node
• Network is the bottleneck, not CPU — single thread saturates the NIC
• Scale horizontally via sharding (more shards, more nodes)
• I/O threads in Redis 6+ handle the socket bottleneck

Multi-threaded (Dragonfly) when:

• You want to minimize node count (cost optimization)
• Workload is dominated by large values (serialization-heavy)
• You can tolerate more complex operational model

Decision 2: Eviction Policies

Decision 3: Persistence Strategy

Consistent Hashing & Data Distribution

Why Consistent Hashing

Redis Cluster Approach (Hash Slots)

Detailed Flow Diagrams

Cache-Aside Read Flow

Write-Invalidate Flow (Cache + DB Consistency)

Cluster Redirect Flow (MOVED / ASK)

Failover Flow (Sentinel / Cluster)

Caching Patterns Deep Dive

Pattern Comparison

When to Use Which Pattern

Redis vs Memcached — When to Use Which

A hot key can overwhelm one shard even when the cluster has plenty of free memory. Replicating reads or keeping a small local copy may help, but both add invalidation work. Measure the key’s request rate separately from total cluster traffic before assuming that adding partitions will distribute its load.

Handling Edge Cases

Cache Stampede / Thundering Herd

Problem: Hot key expires → 10,000 threads all miss simultaneously
         → all 10,000 query DB → DB overwhelmed

Solution 1: Distributed Lock (Setnx)
  Thread 1: SETNX lock:user:123 "1" EX 5 → OK (acquired)
  Thread 2: SETNX lock:user:123 "1" EX 5 → FAIL (wait)
  Thread 3: SETNX lock:user:123 "1" EX 5 → FAIL (wait)
  ...
  Thread 1: fetches from DB → SET user:123 → DEL lock:user:123
  Threads 2,3,...: retry GET → HIT

Solution 2: Probabilistic Early Expiration (best for high-throughput)
  Actual TTL = 3600s
  Each read: if current_time > (expire_time - delta * beta * ln(rand()))
    → preemptively refresh (only one thread statistically wins)
  → Cache never fully expires under load

Solution 3: Background Refresh
  TTL = 3600s, but at 3000s (80% of TTL), background thread refreshes
  → Key never expires → zero stampede
  → Requires tracking hot keys

Hot Key Problem

Problem: One key gets 100K reads/sec (celebrity profile, flash sale item)
         → Single shard/node overwhelmed

Solution 1: Local In-Process Cache (L1)
  App server caches hottest keys in process memory (HashMap with TTL)
  → Short TTL (5-10s) to limit staleness
  → Zero network overhead for hits
  → Each app server has its own copy

Solution 2: Key Replication (read replicas for hot keys)
  Detect hot key → replicate to N random shards with suffix:
    "user:celebrity" → "user:celebrity#r1", "user:celebrity#r2", ...
  Client randomly picks one → distributes load across N nodes

Solution 3: Shard-level Read Replicas
  Hot shard gets more read replicas (3 → 6)
  Client reads from any replica → load distributed

Detection: track per-key access frequency at proxy layer
  → Key exceeding 10K RPS threshold → trigger hot key mitigation

Cache Penetration

Cache Avalanche

Problem: Many keys expire at the SAME time (e.g., all set at startup with same TTL)
         → Massive simultaneous cache miss → DB overload

Solution: Jittered TTL
  base_ttl = 3600
  jitter = random(0, 600)  // ±10 minutes
  actual_ttl = base_ttl + jitter
  
  → Expirations spread over 10-minute window instead of all at once

Solution: Staggered warming
  On service restart, don't load all cache at once
  → Load in batches of 1000, with 100ms delay between batches
  → Prevents overwhelming both cache and DB

Cache-Database Consistency

Tradeoffs & Design Decisions Summary

Reliability & Fault Tolerance

Single Points of Failure & Mitigations

Graceful Degradation

Level 1 (single replica failure):
  → Primary continues serving. No impact.
  → New replica auto-provisioned.

Level 2 (single primary failure):
  → Sentinel promotes replica in 5-15s.
  → Brief connection errors during failover.
  → Clients reconnect to new primary via Sentinel.

Level 3 (multiple shard failures):
  → Affected key ranges unavailable.
  → Application circuit breaker activates → fall back to DB.
  → Other shards continue normally.

Level 4 (full cache cluster down):
  → ALL reads go to database.
  → Database must handle full load (capacity plan for this!).
  → Rate limiting to protect DB.
  → Cache rebuilt on restart (warm-up takes minutes to hours).

Key design principle: 
  Cache is an OPTIMIZATION, not a requirement.
  The system MUST function (slower) without cache.
  Never put data ONLY in cache unless you accept loss.

Data Loss Scenarios

High-Level Architecture

Component Breakdown

Full System Architecture (Production-Grade)

Remove the busiest cache node during peak traffic. Estimate the new load on its neighbors and on the backing database. Compare consistent hashing, replication, and request coalescing: each protects a different part of the recovery path, and none removes the need to bound concurrent cache fills.

Interview Tips

1. Start with caching patterns — Explain cache-aside vs write-through vs write-behind. Most interviews expect you to know these cold. Draw the flow for cache-aside (check cache → miss → query DB → populate cache).

2. Discuss consistency immediately — "How do you keep cache and DB in sync?" Explain why DELETE is safer than UPDATE, the double-write race condition, and CDC as the gold standard.

3. Cache stampede is the #1 follow-up question — Have the three solutions ready: distributed lock (SETNX), probabilistic early expiration, and background refresh. Know when each applies.

4. Know your eviction policies — Don't just say "LRU". Explain why approximate LRU (sampling) is used over true LRU (no linked list overhead), and when LFU beats LRU (scan resistance).

5. Hot key problem — Interviewers love this. Solution: L1 in-process cache (5-10s TTL) for zero-network hot reads, then key replication across shards for extreme cases.

6. Explain why single-threaded works — "Isn't single-threaded slow?" No — in-memory ops are 100-500 ns, network is 50K+ ns. CPU isn't the bottleneck. Single-thread gives atomicity for free. Scale horizontally via sharding.

7. Cluster topology — Explain hash slots (16,384), how slot migration works live with MOVED/ASK redirects, and why cross-AZ replica placement matters.

8. Persistence tradeoffs — RDB (fast recovery, data loss) vs AOF (minimal loss, slower recovery) vs hybrid (best of both). Mention fork overhead and why replicas should handle RDB saves.

9. Size your cache — Don't guess. Calculate: key count × (key size + value size + overhead). Remember jemalloc fragmentation (~10-20%). Account for replication doubling the node count.

10. End with operational concerns — Memory monitoring (never let it hit maxmemory without an eviction policy), slow log analysis, replication lag alerting, and the importance of connection pooling (100K app connections → 1K with pools → manageable for cache nodes).