Case study: Distributed cache
Design a Memcached or Redis cache tier: partitioning, hot keys, invalidation races, and surviving a node that restarts empty.
35 min9 steps
By the end you can
- Size a cache tier from the database's capacity and predict the load when a node is lost
- Partition keys across cache nodes and handle hot keys
- Keep cached data correct with delete-on-write and leases
- Predict what a cold restart, a slow cache and write-heavy hot keys do to the database
Requirements
Operations
- get, set with TTL, delete; keys <=250 B; values <=1 MB
Guarantees
- Sub-ms p99; database remains below capacity after node loss
Estimates
Peak reads
1M/s
DB capacity 50k/s -> >=95% hits
Working set
100 GB
100M * 1 KB
Nodes
8 planned
Memory needs 4; throughput needs 5 at 200k ops/s/node
Node loss
125k extra reads/s
1/8 of keys; 2.5x DB capacity before mitigation
Database load
Within capacity: 40%
- Mean read latency
- 1 ms
- If hit rate drops 1 point
- DB load +10%
Assumes a 500 µs cache lookup and a 5 ms database read; a miss pays both.
API
Read
get(key) -> value or miss
Fill
set(key, value, ttl); jitter expiration
Write
Commit DB, then delete(key)
Evolve
Version namespace: profile:v3:{id}
Partitioning the keys
Consistent hashing
About 1/n keys move on membership change
Modulo hashing
Almost all keys move
Redis Cluster
16,384 fixed slots mapped to nodes
High-level design
Order a profile update so that readers cannot keep an old value indefinitely.
- 1That reader sets profile:42 in the cache
- 2Commit the new profile to the database
- 3The next reader misses and reads the new row
- 4Delete profile:42 from the cache
Deep dive: races, leases and hot keys
Lease race defence
- Miss reads v1; writer commits v2 and invalidates token; reject stale fill
Hot keys
- Replicate names, tiny local TTL cache, or dedicated replicas
Alternatives
Coalescing
- Overlapping misses = key rate * fill time; small benefit for distinct tail keys
Write-through
- Immediate hits; concurrent writers can cache older values
Full replication
- Survives node loss; capacity limited to one node
Failure scenarios you can run
Inject
Cache empty
Observe
Database receives all misses
Recover
Hot set refills in hundreds of ms
Inject
DB overloaded fourfold
Observe
Rejected reads cannot refill cache
Recover
Shed load and warm gradually; metastability persists unaided
Inject
8 ms vs 5 ms timeout
Observe
Every read pays timeout then hits DB
Recover
Bypass or fail fast; preserve DB headroom
Inject
Popular-key writes triple
Observe
Repeated invalidations
Recover
Database approaches saturation
Wrap up
Protect
Leases, jitter, coalescing, hot-key replicas, gutter pools
Size
Worst plausible hit rate; warm replacements
Watch
Per-node hit rate, DB headroom, evictions
Then score each stage from 1 to 4.
Answer this step to continue.