Problem RestatementProblem
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.
RequirementsRequirements
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.
High-Level ArchitectureArchitecture
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
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
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 --> C2Growing the Cache Step by Step
- One node: cache-aside with TTLs and LRU eviction. Easy.
- 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.
- 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.
- More reads than one shard can serve: read from replicas too, and add near-caches for the hottest keys.
- Multiple regions: a cache per region. Invalidate across regions through the replicated change stream.
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).
Deep Dive — When a hot key expiresDeep dive
A celebrity profile is read 100,000 times a second from cache. Its TTL passes. Whatever happens in the next fifty milliseconds decides whether the database survives.
On a miss, go to the database
The key is gone, so every request that finds nothing fetches from the database and writes the value back.
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
EXP["TTL expires at t=0"] --> MISS["100,000 requests miss within 50 ms"]
MISS --> DB[("Database - 100,000 identical queries")]
DB --> SAT["Connections exhausted, latency spikes"]
SAT --> CASC["Other keys' reads now miss their deadlines too"]
CASC --> MORE["Their misses add more database load"]One expiry becomes a hundred thousand identical queries for the same row. The database saturates, which slows every other cached read, which produces more misses — the cascade is the actual danger, not the single key.
Coalesce misses inside each server
Single flight: concurrent misses for the same key on one app server wait on one in-flight database call. The first requester fetches, the rest get the result.
That divides the stampede by the number of requests per server, which is a large win — from 100,000 queries to roughly one per server. With 200 servers it is 200 simultaneous queries for one row, at the same instant, every time that key expires. Better, still a thunderclap, and it repeats on every TTL boundary.
Never let the key be missing
Stop treating expiry as a cliff:
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
R["Read"] --> V{"Value present?"}
V -->|"yes, past soft expiry"| SERVE["Serve it now"]
SERVE --> BG["One holder of the lease refreshes in the background"]
V -->|"yes, fresh"| SERVE2["Serve"]
V -->|"no"| LOCK{"SET lock:key NX PX 3000"}
LOCK -->|"won"| LOAD["Load from the database, write back"]
LOCK -->|"lost"| WAIT["Serve stale, or retry the cache shortly"]
NEAR["Near-cache in app memory, 1-5 s"] --> R- Stale-while-revalidate. Put a soft expiry inside the value, before the real TTL. Past the soft expiry, readers still get the slightly old value while exactly one refreshes it in the background. The key is never absent, so there is nothing to stampede on.
- A distributed lease for the genuine-miss case:
SET lock:key NX PX 3000. One loader across the whole fleet; everyone else serves stale or retries in a few milliseconds. - Probabilistic early refresh. Each read refreshes early with a probability that rises as expiry approaches. Hot keys get refreshed well before they expire; cold keys almost never do.
- TTL jitter — 300 s ± 30 s. Keys populated together otherwise expire together, which turns one stampede into a synchronised fleet-wide one.
- A near-cache for the extreme keys: hold them in app memory for 1–5 seconds. 100,000 reads/sec across 200 servers becomes about 200 cache reads per second, and the cache node stops being a hot spot too.
Detect hot keys rather than guessing: sample key frequency at the client, and promote anything above a threshold into the near-cache automatically. The celebrity you hard-coded last month is not the one trending today.
Trade-offs & AlternativesTrade-offs
| Decision | Choice | Why | Alternative |
|---|---|---|---|
| Pattern | Cache-aside + delete on write | Simple, the DB stays the truth | Write-through: cache always fresh, slower writes |
| Sharding | Consistent hashing | Little data movement on scaling | Modulo hashing: remaps almost all keys |
| Stampede | Single flight + lock + stale-while-revalidate | DB sees one reload per key | Nothing: DB meltdown on hot key expiry |
| Hot keys | Near-cache + replication of the key | Spreads load | Bigger cache node: doesn't fix one hot key |
Common Follow-up QuestionsFollow-ups
- "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).
Wrap-UpWrap-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.