System Design

Design Distributed Cache

Redis cluster, consistent hashing, replication, cache-aside vs read-through, and invalidation at scale.

Interview tip Explain sharding with consistent hashing, replication for HA, cache-aside pattern, thundering herd mitigation (singleflight), and cache invalidation strategies (TTL vs delete-on-write).

① Functional requirements

get(key) → value or miss
set(key, value, ttl_sec) — store with optional expiration
delete(key) — explicit invalidation
Support cache-aside pattern (app manages cache)
Atomic increment/decrement for counters
Batch get (mget) for multiple keys
Namespace/prefix support for logical isolation

Out of scope (state in interview)

Redis-specific commands (focus on concepts)
Cache warming strategies (brief mention)
Multi-region cache coherence
Persistent cache (AOF/RDB backup — brief)

② Non-functional requirements

1M operations/sec across cluster
get latency p99 < 5ms
99.99% availability — survive single node failure
Horizontally scalable to 10TB total memory
Consistent performance under node add/remove (minimal key redistribution)

③ Back-of-the-envelope scale

Assumptions

1M ops/sec: 80% get, 20% set → 800K gets/sec, 200K sets/sec
100M unique keys × 10KB avg = 1TB data (10TB with replication factor 3)
Cache hit ratio target: 95% → 50K DB queries/sec on miss
Cluster: 100 nodes × 100GB RAM = 10TB; ~10K ops/sec per node
Network: 1M ops × 10KB = 10 GB/sec aggregate bandwidth
Consistent hash: 100 physical nodes × 150 virtual nodes = 15K ring positions

Each shard: 1 primary + 2 replicas. On primary failure, replica promoted in <30s. Client library handles topology changes via gossip protocol. Hot keys: replicate to all nodes or local L1 cache on app servers.

④ High-level architecture

Distributed Cache Cluster

Application Servers

Cache Client Library (consistent hash router)

Shard 1 (Primary + 2 Replicas)

Shard 2 (Primary + 2 Replicas)

Shard N…

Gossip Protocol (cluster membership)

Database (on cache miss)

get(key)→Hash → shard→Hit / miss→DB on miss

Client library computes shard = consistent_hash(key) → routes to primary. On miss: app fetches DB, populates cache (cache-aside). Replication: primary streams writes to replicas asynchronously (eventual consistency within shard).

⑤ Data flow & execution path

End-to-end execution flow

① Client→② API / LB→③ Core services→④ Cache + DB→⑤ Message queue→⑥ Async workers

Sync path: validate → authorize → read/write primary store
Async path: publish domain events → consumers (email, analytics, search index)
Read-heavy path: CDN / edge cache → regional cache → DB replica
Failure path: retry with backoff, DLQ, idempotent handlers

In interviews, trace one user action through this diagram. State what is synchronous (user waits) vs asynchronous (background), and where you enforce idempotency.

⑥ API & interfaces

Endpoint / flow	Purpose	Notes
GET key	Retrieve value	Returns value or nil; p99 <5ms
SET key value EX ttl	Store with TTL	Atomic; replicates to replicas async
DEL key	Delete / invalidate	Propagates to replicas; returns count deleted
MGET key1 key2 …	Batch get	Routes to multiple shards in parallel; merges results
INCR key	Atomic counter	Used for rate limiting, view counts
CLUSTER NODES	Topology discovery	Client bootstraps shard map; refreshed on MOVED redirect

⑦ Data model & storage

Cache entry (in-memory per shard): key (string, max 512MB value), value (bytes), ttl_expiry (absolute timestamp), access_count (for LFU eviction)

Cluster metadata: node_id, ip:port, role (primary|replica), hash_slots[], status (online|fail|handshake)

Store	What	Why
In-memory (per shard node)	Cache data	RAM; eviction when maxmemory reached
AOF (append-only file)	Durability (optional)	fsync every sec; rebuild on restart — most caches skip for speed
Gossip state	Cluster topology	In-memory; exchanged every 1s between nodes

⑧ Deep dive — core components

Consistent hashing with virtual nodes

Hash ring (conceptual)

Keys A, B, C hash onto ring → walk clockwise to nearest vnode → physical node owns key. Adding Node D only moves keys between C and D.

Hash ring: 0 to 2³². Each physical node has 150 virtual nodes on ring (better balance). key → hash(key) → walk clockwise to first virtual node → that physical node owns the key. Add node: only keys between predecessor and new node move (~1/N keys). Remove node: keys redistributed to next node.

Without virtual nodes: uneven distribution when few nodes. With 150 vnodes per node: std deviation < 5% key distribution.

Cache-aside pattern and thundering herd

Cache-aside: App checks cache → on miss, read DB → write to cache → return. App owns consistency. On write: update DB first, then delete cache key (not update — avoids race).

Thundering herd: Hot key expires → 10K concurrent requests miss → all hit DB. Fixes: (1) Singleflight — only one request fetches DB, others wait. (2) Probabilistic early expiration — expire at random time before TTL. (3) Never expire hot keys — background refresh before TTL.

Replication and failover

Each shard: 1 primary + 2 replicas. Writes go to primary → replicated via command stream. Reads: default from primary (strong); can read from replica (eventual, lower load). Primary failure: replicas gossip elect new primary in <30s. Clients receive MOVED/ASK redirects during rebalancing.

Eviction policies

When maxmemory reached: allkeys-lru (evict least recently used — general purpose), volatile-lru (only keys with TTL), allkeys-lfu (least frequently used — better for hot key retention). Never noeviction in production cache — causes OOM errors. Monitor eviction rate; scale if > 100/sec.

⑨ Trade-offs & alternatives

Decision	Option A	Option B	Pick when
Pattern	Cache-aside	Read-through	Cache-aside: app control; read-through: simpler app code
Write	Delete on write	Update cache on write	Delete safer; update risks stale if DB write fails
Consistency	Eventual (replicas)	Strong (primary only)	Primary reads for strong; replicas for scale
Eviction	LRU	LFU	LRU general; LFU better for skewed access patterns
Hot key	Local L1 cache	Replicate key to all nodes	L1 simpler; replicate for extreme hot keys

⑩ 45-minute interview script

0–5 min: Clarify cache-aside, TTL, scale, availability requirements
5–12 min: Scale — 1M ops/sec, 1TB data, hit ratio math
12–22 min: Consistent hashing diagram with virtual nodes
22–30 min: Cache-aside pattern; delete vs update on write
30–36 min: Thundering herd — singleflight and early expiration
36–42 min: Replication and failover
42–45 min: Eviction policy selection

⑪ Likely follow-up questions

Question	Short answer
Hot key on one shard?	Local L1 cache on app; or replicate hot key to all shards; client-side hash override
Cache node dies?	Replica promoted; ~1/N keys unavailable for 30s; clients retry with redirect
Cache and DB inconsistent?	TTL bounds staleness; delete-on-write for critical data; accept eventual for most
10TB — all in RAM?	Yes for Redis-class; larger: tiered cache (hot in RAM, warm on SSD with Redis on Flash)
How to monitor cache health?	Hit ratio, eviction rate, memory usage, p99 latency, replication lag per shard
Add node without downtime?	Add node → reshard slots gradually → each slot migration moves keys live with dual-write period

⑫ Revision checklist

Consistent hashing with virtual nodes
Cache-aside pattern explained
Delete-on-write (not update-on-write)
Thundering herd + singleflight solution
Primary + replica per shard
Failover and MOVED redirects
95% hit ratio → DB load calculation
Eviction policy (LRU/LFU)
1M ops/sec cluster sizing
Hot key mitigation strategies

Redisconsistent hashingcachingreplicationperformance