Distributed cache

Design a Memcached/Redis-style cache tier that absorbs most reads for a database. The hard parts are not the hash map: they are partitioning, hot keys, invalidation races and what happens when a cache node restarts empty.

Open reference design Interactive lesson Practice an interview

Arrows show permitted calls. Open the canvas to inspect route programs.

Component labels and connections

Clients (client) · calls: Load balancer
Load balancer (loadBalancer) · calls: App 1, App 2
App 1 (service) · calls: Cache cluster, Profiles DB
App 2 (service) · calls: Cache cluster, Profiles DB
Cache cluster (cache) · calls: none
Profiles DB (database) · calls: none

Requirements

Functional

get, set with TTL, delete for keys up to 250 B and values up to 1 MB.
Used cache-aside by many services.
Optional: atomic increment and compare-and-set.

Non-functional

Sub-millisecond p99 inside a data centre.
Sustain a hit rate high enough that the database never sees more than its capacity — including after a node restart.
Losing a cache node must not take the database down.
Stale reads bounded in time (TTL) and cleared on write (invalidation).

Worked estimates

Read load
the database can take ~50k reads/s → needs ≥ 95% hit rate
1M reads/s peak at the application tier
Working set
≈ 100 GB of hot data
100M active objects × ~1 KB
Nodes
4 nodes by memory; 1M ops/s ÷ ~200k ops/s per node → 5; plan 8
100 GB ÷ 25 GB usable per node (64 GB box, headroom for fragmentation and replicas)
Losing one of 8 nodes
≈ 125k reads/s extra at the database — 2.5× its capacity unless misses are coalesced or the node is replaced warm
1/8 of keys miss at once × 1M reads/s
Network
≈ 1 GB/s across the tier — ~1 Gbit/s per node on 8 nodes
1M/s × 1 KB

API

get(key)

Request: key

Response: value | miss

set(key, value, ttl)

Request: key, value, TTL with jitter

Response: ok

delete(key)

Request: key

Response: ok

Writers delete after committing to the database (invalidation).

Data model

profiles — store: db

Keys are namespaced and versioned (profile:v3:{id}) so a schema change invalidates by changing the prefix.

Each node is an LRU hash table with slab or arena allocation; eviction happens per node.

The source of truth is the database; the cache holds disposable copies.

High-level design

Trace permitted calls in the architecture above, then open the reference canvas to inspect routing.

Deep dives

Partitioning: consistent hashing on the client

Clients (or a proxy such as mcrouter or twemproxy) map each key to a node with consistent hashing, so adding or removing one of n nodes remaps only about 1/n of the keys instead of nearly all of them with hash mod n. Virtual nodes even out the load. Redis Cluster uses 16,384 fixed hash slots assigned to nodes, which is a directory variant of the same idea.

Hot keys

A single key can exceed one node's capacity — a celebrity profile or a configuration blob. Options: replicate the hot key under several names (key#1..key#k) and read a random one; keep a tiny in-process L1 cache with a TTL of a second or two; or detect hot keys and pin them to dedicated replicas. All of them trade freshness for load spreading.

Invalidation races and leases

Cache-aside has a classic race: a reader misses and reads v1 from the database; a writer commits v2 and deletes the key; the reader then sets v1, which stays until TTL. Facebook's memcache paper fixes it with leases: a miss returns a token, a delete invalidates outstanding tokens, and a set with an invalid token is ignored. Leases also throttle the stampede, since only the token holder fills a key.

Surviving node loss

A replacement node starts empty. Gutter pools (a small set of spare nodes that take over failed nodes' keys with short TTLs), cold-cluster warm-up (new nodes read through from warm ones), request coalescing and TTL jitter keep the database from seeing the full miss rate. Size the database for the worst plausible hit rate, not the average.

Failure scenarios

The cache restarts empty

Scenario and expected result

At t = 1.5 s the cache tier loses its contents (restart, or a failed deploy that flushes it).

Expected: The hit rate drops to zero and the 8-worker database gets every read for a moment. Coalescing turns many concurrent misses per hot key into one database read each, so the hot set refills within a few hundred milliseconds and only the tail pays. Compare the alternative without coalescing.

Open this scenario

The cache restarts while the database is slow

Scenario and expected result

A deploy restarts the cache at t = 1.5 s while the database runs 2.5× slower because a migration is running. The database alone can now serve about 900 reads/s; the cold cache sends it four times that.

Expected: Most requests fail, and the system does not recover by itself while the database is slow. A database read that is rejected never fills the cache, so the cache stays cold and the database stays overloaded — a metastable failure. Coalescing cannot help much, because most misses are distinct long-tail keys. The fixes are on the load side: bounded queues and deadline propagation so abandoned requests are not served, warming the cache before taking traffic, and never restarting the cache during a database incident.

Open this scenario

The cache becomes slower than its timeout

Scenario and expected result

From t = 1.5 s to 2.0 s cache operations take 40× longer (~8 ms), exceeding the 5 ms client timeout — a swapping or CPU-starved cache node.

Expected: Every read waits 5 ms, gives up and goes to the database, which cannot take the full read rate: queues grow, p99 approaches the 250 ms deadline and a few percent of requests miss it. A slow cache is worse than a dead one — the database load is the same, but every request also pays the timeout first.

Open this scenario

Writes triple on popular keys

Scenario and expected result

The write share rises from 3% to 8% of requests while reads stay Zipf-skewed — every popular profile is being edited during an event. Each write deletes its key from the cache.

Expected: Invalidations knock hot keys out of the cache over and over, so the hit rate falls and the database takes the extra misses on top of more than twice the writes. Coalescing caps each invalidated key at about one refill, but the database now runs near saturation and latency climbs: write-heavy hot keys are the case where caching an object stops paying.

Open this scenario

Alternative designs

Reference

Inspect the architecture above and run the same scenario.

No request coalescing

Simpler client, and in this simulated cell — fills take ~4 ms and popularity is moderately skewed — it changes surprisingly little: most post-restart misses are distinct long-tail keys, which coalescing cannot merge (try it). It pays off when a few keys are very hot relative to fill time: overlapping misses per key ≈ request rate for that key × fill time, so a key read 10,000 times a second with a 50 ms fill sends 500 queries without coalescing and 1 with it.

Reference

Inspect the architecture above and run the same scenario.

Write-through (update the cache on write)

Reads after a write hit immediately. But two concurrent writers can set the cache in the opposite order to the database commits and leave the old value cached until TTL. Deleting is idempotent and order-safe; Facebook's memcache paper chose delete for that reason.

Reference

Inspect the architecture above and run the same scenario.

Replicated cache (every node holds every key)

Survives node loss with no misses and spreads hot keys perfectly, but capacity is one node's memory and every write goes to every node. Good for small, very hot data (feature flags, configuration); partitioning is the only option for a 100 GB working set.

Clarifying questions

What is the database's read capacity, and the peak read rate?
How stale may cached data be?
Value sizes and working-set size?
Is the cache a pure cache, or do some features rely on it as storage?

Common mistakes

hash mod n partitioning that remaps everything on resize.
Updating instead of deleting on write.
Sizing the database for the average hit rate.
No plan for hot keys or for a cold restart.
Client timeouts that are longer than a database read, so a slow cache adds latency to every request.

Self-assessment rubric

requirements / levels 1-4

1/4 'Cache things'.
2/4 get/set/delete with TTL.
3/4 Latency, hit-rate and staleness requirements.
4/4 States the database's capacity as the real constraint on hit rate.

estimates / levels 1-4

1/4 None.
2/4 Memory size.
3/4 Memory, node count and required hit rate.
4/4 Database load when a node is lost.

api / levels 1-4

1/4 get/set.
2/4 Adds delete and TTL.
3/4 Explains delete-on-write.
4/4 Leases or CAS for safe fills.

data model / levels 1-4

1/4 A map.
2/4 Key/value with TTL.
3/4 Namespaced, versioned keys; LRU per node.
4/4 Memory allocation and value-size limits.

high level / levels 1-4

1/4 One cache box.
2/4 Cache cluster beside the database.
3/4 Client-side consistent hashing.
4/4 Proxy tier, replication choices and failure paths.

deep dive / levels 1-4

1/4 None.
2/4 Eviction policy.
3/4 Stampede and hot keys.
4/4 Invalidation races and leases, gutter pools, warm-up.

wrap-up / levels 1-4

1/4 Stops.
2/4 Hit-rate metric.
3/4 Names cold start and hot keys as risks.
4/4 Alerts on hit rate and database headroom; runbook for node loss.