Distributed Cache and the Hot Key / Cache Stampede Problem

0) Problem Restatement

Design a distributed cache (like a Redis or Memcached cluster) that sits in front of a database, and explain how it changes as data grows and it runs on many machines (asked at Meta). Then solve a classic failure (asked at TikTok): a hot key, for example a celebrity's profile, is read 100,000 times per second. When its cache entry expires, thousands of app servers miss the cache at the same moment and all hit the database together. This is a cache stampede (or "thundering herd"), and it can take the database down.

1) Requirements

1.1 Functional

• get(key), set(key, value, ttl), delete(key).
• Serve reads for the application, with the database as the source of truth.

1.2 Non-Functional

• Sub-millisecond reads.
• High hit rate (e.g., over 95%) so the DB sees little traffic.
• Scale out by adding nodes.
• No stampedes when hot keys expire or nodes fail.

1.3 Scale Estimates

• 1M reads/sec, and 1 TB of hot data.
• A cache node (e.g., 64 GB RAM, ~100K ops/sec) → about 20 nodes for memory, more for throughput, ×2 for replicas.

2) High-Level Architecture

2.1 Overview

• Cache-aside pattern (most common): the app checks the cache first. On a miss, it reads the DB and puts the value into the cache with a TTL.
• Sharding: keys are spread over nodes with consistent hashing, so adding a node only moves a small part of the keys.
• Replication: each shard has a replica for failover and for spreading hot reads.
• Local near-cache: a tiny in-process cache on each app server for the very hottest keys.

2.2 Architecture Diagram

flowchart LR
    APP["App servers + small local cache"] -->|"hash(key)"| C1["Cache shard 1 + replica"]
    APP --> C2["Cache shard 2 + replica"]
    APP --> C3["Cache shard N + replica"]
    APP -->|"on miss - single flight"| DB[("Database")]
    DB -->|"change events (CDC)"| INV["Invalidator"]
    INV -->|"delete key"| C1
    INV --> C2

3) Growing the Cache Step by Step

1. One node: cache-aside with TTLs and LRU eviction. Easy.
2. More data than one node: shard by consistent hashing with virtual nodes. The client library (or a proxy like Twemproxy or mcrouter) routes each key.
3. Node failures: add replicas. On failure, promote the replica. Without replicas, a lost node means a burst of misses on its keys, which is itself a mini stampede.
4. More reads than one shard can serve: read from replicas too, and add near-caches for the hottest keys.
5. Multiple regions: a cache per region. Invalidate across regions through the replicated change stream.

4) Keeping the Cache Correct (Invalidation)

• TTL only: simple, but data can be stale for up to the TTL.
• Delete on write: when the app updates the DB, it deletes the cache key (not "set new value", which can race and leave old data). The next read reloads it.
• CDC-based invalidation: a process reads the DB's change log and deletes affected keys. This is more reliable, because it catches every writer, even scripts and other services.
• A known race: a reader loads an old value just before a writer deletes the key, then writes the old value into the cache. Fixes: short TTLs as a safety net, versioned values, or Facebook's lease mechanism (the cache gives the reader a token, and a later delete invalidates it, so the stale set is rejected).

5) Deep Dive — Preventing Cache Stampedes

When a hot key expires, we want one request to reload it, not ten thousand. Techniques (combine several):

1. Single flight / request coalescing: inside each app server, concurrent misses for the same key wait for one DB call. This cuts the load from "every request" to "one per server".
2. Distributed lock (or lease): the first miss across the cluster takes a short lock like SET lock:key NX PX 3000 and reloads. Others briefly serve the stale value (if kept) or wait and retry the cache.
3. Stale-while-revalidate: store a "soft" expiry inside the value, before the real TTL. After the soft expiry, one request refreshes it in the background while everyone else still gets the slightly old value.
4. Probabilistic early refresh: each request refreshes early with a small probability that grows as expiry approaches, so hot keys are refreshed before they expire and cold keys aren't.
5. TTL jitter: add randomness to TTLs (e.g., 300s ± 30s), so many keys set at the same time don't all expire together.
6. Near-cache for super-hot keys: keep them in app memory for 1–5 seconds. 100K reads/sec across 200 servers become about 200 cache reads per second.

6) Trade-offs & Alternatives

7) Common Follow-up Questions

• "Eviction policy?" LRU is the default. LFU is better when some keys stay popular for a long time.
• "What if the cache cluster is down?" Limit how many DB requests are allowed (a circuit breaker or bulkhead), serve degraded responses, and warm the cache gradually after recovery.
• "Write-back caching?" Writes go to the cache and flush to the DB later. It's fast, but risky if the cache loses data, so use it only for data you can lose or rebuild (like counters).

8) Wrap-Up

Use cache-aside with TTLs, shard with consistent hashing, add replicas for failover, and invalidate by deleting keys on write or from the DB change stream. Stop stampedes with request coalescing, a short distributed lock, stale-while-revalidate, early refresh and TTL jitter, and protect super-hot keys with local near-caches and key replication.