Cheat Sheet
The architecture to reproduce
Draw it in this order: cache vs store → consistent hashing → the node internals → eviction/invalidation → thundering herd.
The definition that does work ⭐
A cache is a store you can afford to lose. The data exists elsewhere.
| Cache | Key-value store | |
|---|---|---|
| Losing it means | Degraded latency | Data loss |
| Eviction | A feature | A bug |
| Durability | Optional | Mandatory |
Same API — get, set, delete — opposite failure semantics. That question decides everything else.
Why memory, why distributed
RAM because the entire value is being an order of magnitude faster than what's behind it, and that gap comes from avoiding disk. Cost: memory is expensive and finite, which is what forces eviction.
Distributed for two independent reasons — separate them:
- Capacity — the working set exceeds one machine's RAM.
- Availability — one node holding everything is a single point of failure whose loss lands entirely on the database.
The second is why you replicate, not just shard.
Consistent hashing ⭐
hash(key) % N -> lose one node of ten, ~90% of keys remap
-> not "10% of the cache lost" but a near-total WIPE
-> mass miss storm onto the database, at the worst moment
consistent hash -> only the departed node's range moves
virtual nodes -> even load; without them a small ring is lumpy
Justify it by the failure case, not by elegance. The client resolves key → node itself, from a server list kept current by a configuration service — which keeps a proxy hop off the read path.
Eviction ≠ invalidation ⭐
Eviction asks what do I drop to make room? — a capacity question. Invalidation asks what is no longer true? — a correctness question.
| Policy | Evicts | Fits when |
|---|---|---|
| LRU | Untouched longest | Recent access predicts future access — usually true |
| LFU | Fewest total accesses | Popularity stable long-term. Cache pollution: last year's hit keeps its slot forever unless aged |
| MRU | Just used | Sequential scans, read-once data |
| FIFO | Oldest | Simplicity over hit rate |
Invalidation: TTL as baseline. Active expiry sweeps in the background; passive expiry checks on read. Passive alone means an untouched expired entry holds memory indefinitely — you need both.
Read and write patterns
Cache-aside (look-aside, lazy loading) — the application checks the cache, falls back to the store, and populates it. The cache never talks to the database.
- Only requested data is cached, not everything written.
- A cache failure is survivable — every read already has a path to the database. Contrast read-through, where a cache outage is a total outage.
- Cost: the first read of anything is always a miss.
Write policies: write-through (consistent, slower writes) · write-back (fast, risks loss on node failure) · write-around (avoids polluting the cache with write-once data).
🔴 Thundering herd
hot key expires -> every in-flight request misses at once
-> all hit the database for the SAME value
-> spike proportional to how popular the key was
The better the cache was working, the worse the spike. Three composable fixes:
- Request coalescing (single-flight) — first miss fetches, concurrent misses wait on it. Caps origin load at one query per key, regardless of arrival rate. Highest value.
- Probabilistic early expiry — each read may refresh early, with probability rising as the TTL nears. Refreshes stagger; the cliff never forms.
- Serve stale while revalidating — return the expired value, refresh in the background.
Same shape as synchronized retries after an outage: stagger the timing, or elect one actor to do the work for everyone.
Hot keys — two different problems
Resharding does not help. Sharding splits key ranges; a single key is the atom of the scheme and lives on one node however you slice the ring.
| Hot read | Hot write | |
|---|---|---|
| Replicas | Help — spread reads. But a fixed multiple (~3×), not scalable | Do not help — every replica applies every write |
| Beyond that | Client-side replication to key_1..key_N, pick at random | Batch at the client — buffer 50–100 ms, apply one consolidated update |
| Precondition | — | Only the final value matters (counters, metrics) |
Performance at scale
The in-memory lookup is already the cheapest thing in the request. Latency lives in the network round trip and serialization.
So the wins are pooled connections, batching many keys per round trip, and co-location — not a faster hash table.
The honest limit
Cross-data-center consistency. Within one DC, synchronous replication gives strong consistency. Across DCs, synchronous writes are too slow → asynchronous → eventual consistency, so a read in one region can return what another already invalidated.
Most systems accept it, because a stale entry is a correctness problem for the application, not for the cache — which is why short TTLs are the pragmatic backstop.
The five sentences to have ready
- "A cache is a store you can afford to lose — that's what makes eviction a feature rather than a bug."
- "Modulo hashing turns one dead node into a near-total cache wipe; consistent hashing bounds it to that node's range."
- "Eviction is a capacity question; invalidation is a correctness question. They get conflated constantly."
- "When a hot key expires, every request misses at once — the better the cache was working, the worse the spike."
- "Replicas fix hot reads and do nothing for hot writes, because every replica applies every write."