Distributed Cache#

Q: How does a distributed cache work?

Clients hash a key to pick a shard, talk directly to that node for sub-millisecond GET/SET, and rely on consistent hashing plus replication to survive node failures.

Q: Redis vs Memcached: which should I use?

Use Redis when you need data structures, persistence, pub/sub, or cluster mode. Use Memcached for the simplest, lowest-overhead string cache with multithreaded scaling.

Q: What is a cache stampede and how do I prevent it?

A stampede happens when a hot key expires and many requests hit the database at once. Prevent it with request coalescing, probabilistic early expiry, or per-key locks.

Q: How does consistent hashing help a distributed cache?

Consistent hashing maps keys and nodes onto a ring so only a fraction of keys move when a node joins or leaves, avoiding the mass remap that plain modulo hashing forces.

Q: What is the hot key problem?

A hot key concentrates traffic on one shard, exhausting its CPU. Mitigate with per-node read replicas, key splitting with random suffixes, or a small in-process L1 cache.

Q: LRU vs LFU eviction: which is better?

LRU is simple and works well when access patterns are temporal. LFU keeps frequently used keys longer and resists one-off scans, at the cost of extra bookkeeping.

Problem statement (interviewer prompt)

Design a distributed in-memory cache (Redis/Memcached cluster). Support sub-millisecond GET/SET at 1M+ ops/s, sharding, replication, eviction (LRU/LFU/TTL), and handle the operational pitfalls - cache stampedes, hot keys, big keys, mass-expiry storms.

flowchart LR
  C[App]
  R([Client<br/>consistent hash])
  N1[(Cache 1)]
  N2[(Cache 2)]
  N3[(Cache 3)]
  C --> R
  R --> N1
  R --> N2
  R --> N3

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class R client;
    class C service;
    class N1,N2,N3 datastore;

flowchart TB
  subgraph App[App Tier]
    A1[App pod]
    A2[App pod]
    AN[App pod]
    SDK([Smart client<br/>consistent hash<br/>or slot map])
  end

  subgraph Cluster[Cache Cluster]
    direction TB
    subgraph Shard1
      P1[Primary 1]
      R1a[Replica 1a]
    end
    subgraph Shard2
      P2[Primary 2]
      R2a[Replica 2a]
    end
    subgraph ShardN
      PN[Primary N]
      RNa[Replica Na]
    end
    SLOT[Slot map<br/>16384 slots → shards]
    SENT[Sentinel / Cluster bus<br/>failover]
  end

  subgraph Engines[Data structures]
    KV[String GET/SET]
    LIST[List - LPUSH BRPOP]
    HASH[Hash - HSET]
    SET[Set / ZSET]
    STREAM[[Stream - XADD XREAD]]
    HLL[HyperLogLog]
    GEO[Geo - GEOADD]
    PSUB[[Pub/Sub]]
    LUA[Lua scripts<br/>atomic]
  end

  subgraph Patterns[Access patterns]
    CA[Cache-aside]
    RT[Read-through]
    WT[Write-through]
    WB[Write-back]
    LOCK[Distributed lock<br/>SET NX EX]
    QUEUE[[Job queue]]
    RL[Rate limiter]
  end

  subgraph Pitfalls[Pitfalls]
    STMP[Stampede / dogpile]
    BIG[Big keys / hot keys]
    EVICT[Eviction storm]
    NET[Latency spikes]
  end

  subgraph Mit[Mitigations]
    SF[Single-flight / lock]
    JIT[Jittered TTL]
    SPLIT[Split big key into chunks]
    HOTS[Hot key replication / split]
    LRU[allkeys-lru / lfu]
    PIPE[Pipelining / batching]
  end

  subgraph Persist[Optional Persistence]
    RDB[RDB snapshot]
    AOF[AOF append log]
  end

  A1 --> SDK
  A2 --> SDK
  AN --> SDK
  SDK -. slot mod 16384 .-> SLOT
  SLOT --> Shard1
  SLOT --> Shard2
  SLOT --> ShardN
  P1 -.repl.-> R1a
  P2 -.repl.-> R2a
  PN -.repl.-> RNa
  SENT -.health.-> Cluster
  SENT -. promote .-> R1a
  Engines --- Cluster
  Patterns --- App
  STMP -. fix .-> SF
  STMP -. fix .-> JIT
  BIG -. fix .-> SPLIT
  BIG -. fix .-> HOTS
  EVICT -. fix .-> LRU
  NET -. fix .-> PIPE
  Cluster --> Persist

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class SDK client;
    class SENT edge;
    class A1,A2,AN,P1,R1a,P2,R2a,PN,RNa,SLOT,KV,LIST,HASH,SET,HLL,GEO,LUA,CA,RT,WT,WB,LOCK,RL,STMP,BIG,EVICT,NET,SF,JIT,SPLIT,HOTS,LRU,PIPE,RDB,AOF service;
    class STREAM,PSUB,QUEUE queue;

Sharding#

Redis Cluster: 16384 slots, slot = CRC16(key) mod 16384.
Memcached: client-side consistent hashing (Ketama).
Resharding: SLOT MIGRATE moves slots online.

Replication#

Async leader-follower; replica promotion via Sentinel / Cluster bus quorum.
Optional waitfor sync confirm before ack.

Eviction#

maxmemory-policy: allkeys-lru, allkeys-lfu, volatile-lru, noeviction.
TinyLFU / W-TinyLFU (Caffeine) for app-local L1.

Common usages#

Object cache, session store, leaderboard (ZSET), rate limiter, distributed lock, event stream (Stream), pub/sub bus, geo index.

Pitfalls#

Big key: 10 MB ZSET blocks the event loop. Split or move to DB.
Hot key: shard cannot scale on one key. Replicate or pre-compute at app.
Cache stampede: single-flight via Redis LOCK or async refresh.

Glossary & fundamentals#

Concepts referenced in this design. Each row links to its canonical page; the tag column shows whether it is a high-level (HLD) or low-level (LLD) concept.

Tag	Concept	What it is	Page
`HLD`	Sharding	horizontal partitioning across nodes	database-sharding
`HLD`	Consistent hashing	key placement with minimal remap	consistent-hashing
`HLD`	Cache strategies	cache-aside, read/write-through, eviction	caching-strategies
`HLD`	Pub/Sub & message brokers	topics, consumer groups, delivery semantics	pub-sub-pattern
`HLD`	Raft / Paxos consensus	replicated state machine via majority quorum	consensus-raft-paxos
`HLD`	Leader/follower replication	sync/semi-sync/async replication, failover	replication-leader-follower
`HLD`	Probabilistic data structures	Bloom, HLL, Count-Min, MinHash, t-digest	probabilistic-data-structures
`HLD`	Idempotency & retries	safe re-execution, backoff + jitter	idempotency-retries
`LLD`	Concurrency primitives	mutex, semaphore, RW lock, atomic, CAS	concurrency-primitives

Quick reference#

Functional#

O(1) GET/SET; rich data structures.
TTL, LRU/LFU eviction.
Horizontal scale via sharding.
Optional replication + persistence.

Non-functional#

p99 GET < 1 ms LAN; throughput 50-200k ops/s/node.
99.99% via cluster + replicas.

Capacity#

1 TB hot data → 30 shards × 32 GB (3 replicas each) = 90 instances.
Throughput 1M ops/s → 10 shards if 100k ops each.

Patterns#

Cache-aside (most common).
Read-through, write-through, write-back (rare in practice for KV cache).
Locks, counters, leaderboards, queues, pub/sub bus.

Operational concerns#

BGSAVE forks: COW memory doubling risk.
AOF rewrite IO spikes.
Replication lag during big-load on primary.
Cluster split-brain - Sentinel quorum size critical (3+).

Trade-offs#

Persistence on = recovery without re-warm but write amplification.
Multiple data structures vs Memcached's pure KV simplicity.
Client-side hashing (Memcached) vs server-side cluster (Redis Cluster) - Redis handles migrations better.
TLS / authn in latency-sensitive cache = significant overhead.

Refs#

Facebook memcached at scale (NSDI '13), Redis docs (replication, cluster), Netflix EVCache, DynamoDB DAX, Twitter Twemcache.

FAQ#

How does a distributed cache work?#