System Design · Design Question

Design a Distributed Cache

Build a Redis-like cluster: APIs, partitioning, replication, eviction, and consistency under node failure.

1. Requirements

GET/SET/DEL with optional TTL; high QPS, low latency (sub-ms–few ms).
Data partitioned across nodes; survive node loss (replicas).
Eviction when memory full (LRU/LFU/TTL).
Client or proxy discovers topology.

Ask: durability needed (AOF) or pure cache (OK to lose)? max value size? data structures beyond strings?

2. API

SET key value EX 60 GET key → value | nil DEL key MGET k1 k2 ... (fan-out to shards) PING / INFO / CLUSTER SLOTS

3. Data model (per node)

In-memory dict: key → { value, expire_at, lru_clock } Optional: persistence WAL/AOF for warm restart (not required for pure cache)

4. High-level design

Client / Smart client → hash(key) → shard primary | consistent hash / slot table (16384 slots like Redis Cluster) | Primary --async repl--> Replica(s) | Gossip / config bus for membership

5. Partitioning

Hash slots or consistent hashing with vnodes.
Client caches slot→node map; MOVED/ASK redirects on reshard.
Multi-key ops only when keys share a slot (hash tags {user}.a).

6. Replication & failover

Primary receives writes; replicas async replicate Primary down → replicas elect / cluster bus promotes Clients retry on new primary Trade-off: async repl may lose last writes (OK for cache)

7. Eviction and memory

Policy	When
volatile-lru	Evict LRU among keys with TTL
allkeys-lru	Evict LRU among all keys
allkeys-lfu	Frequency-based
noeviction	Return errors on OOM

Expire passively on access + active expire sampler cycle.

8. Consistency vs cache semantics

Caches are usually AP-ish: prefer availability; stale OK with TTL.
App still owns DB as source of truth (cache-aside).
Hot key: replicate read-only copies or local L1 cache on app.

9. Scaling operations

Add node → migrate slots gradually; use ASK redirects mid-move.
Monitor hit rate, eviction rate, RSS, blocked clients.
Big keys / hot keys dashboards — operational killers.

10. Failure modes to mention

Thundering herd on cold cluster → stampede controls in clients.
Split brain without proper quorum — prefer managed election.
Network partition: serve stale vs error — product choice.

11. Client library responsibilities

Maintain cluster slot map; follow MOVED/ASK.
Timeouts, retries with jitter, circuit breaking to bad nodes.
Pipelining / connection pooling for throughput.
Optional local L1 LRU for ultra-hot keys (short TTL).

get(k): if L1 hit: return node = slot_map[hash(k)] v = node.GET(k) with timeout on MOVED: refresh map; retry once fill L1; return

12. Security

AUTH/ACL per app, TLS in transit, network isolation. Caches often hold sessions and PII — treat them like production data stores for access control, even if durability is weaker.

Quick revision

In-memory KV + TTL + eviction; DB remains source of truth for cache use.
Hash slots / consistent hashing for partition.
Async replicas; failover via cluster membership.
Smart clients handle MOVED and slot maps.
LRU/LFU/TTL policies when RAM full.
Hot/big keys need explicit design.
Reshard online with gradual slot migration.