Appearance
11.4 — Distributed Cache
A team puts a cache in front of their database. The median response time drops from 80 ms to 4 ms and everyone is delighted. Six weeks later, one cache node is restarted for a routine kernel update at two in the afternoon. Eleven minutes later the database is unresponsive, the site is down, and nobody can work out why a cache — which is supposed to be an optimisation — took the whole product with it.
What happened is the subject of this study. The cache had quietly stopped being an optimisation and become a dependency, and nobody noticed because a dependency and an optimisation look identical while they are working.
9.7.30 built an LRU inside one process, where the whole thing was a hash map and a linked list. This study designs the service: a cluster answering millions of operations a second, and — more useful than the cluster itself — the caching discipline that every other study in this Part depends on. Invalidation, stampedes, hot keys, and honest accounting of what a cache buys and what it costs.
1. Requirements
Functional. get, set with a time-to-live, and delete. Atomic increment, so counters do not need read-modify-write from the client. Compare-and-set, so a client that must do read-modify-write can detect that someone else got there first. Cluster membership that survives losing a node. Clients discover the topology without a deploy.
Non-functional, with numbers.
- p99 under 1 millisecond inside one datacentre. A cache that is sometimes slow is worse than no cache, because the application now pays the cache's latency and the database's.
- At least 1 million operations a second cluster-wide.
- Hit rate of 95% or better for the workload it was sized for.
- The cache may lose data. This is stated as a requirement rather than a caveat, because it is the property that everything else hangs off: no correctness in the system above may depend on a cache hit.
Out of scope today: durability, transactions spanning multiple keys, and cross-region replication — though section 8 says what changes when regions appear.
The clarifying questions, and what each answer changes
"Can the database serve production traffic with the cache completely empty?" This is the first question and the most important one in the entire design. If the answer is yes, the cache is an optimisation and can be treated casually. If the answer is no, the cache is a tier-1 dependency wearing an optimisation's clothes, and it needs replication, monitoring, a warm-up procedure and a rehearsed failure drill. Most teams have never asked, which is why the story at the top of this page keeps happening.
"How stale may a value be?" A number, in seconds. This single answer decides whether you can rely on a time-to-live alone or need explicit invalidation, and explicit invalidation is where the bugs live.
"What is the working set — how much data is actually hot?" Not the size of the database. A cache smaller than the working set does not give you a partial benefit, it thrashes: every entry is evicted before it is used again, so you pay the cache's latency on every request and still go to the database. That is worse than having no cache at all.
"Is any cached value written by more than one path?" Batch jobs, admin tools, database migrations, and other services writing directly are the four usual sources of permanently stale cache entries, and none of them are visible from the application code that reads the cache.
"What is the biggest value we will store?" Large values change the design. At 2 KB, network bandwidth is a background concern. At 2 MB, one popular key can saturate a network interface on its own, and the answer is compression or, more often, not caching that thing at all.
2. Estimation
Working set and memory. 10 million hot objects averaging 2 KB = 20 GB. Add roughly 30% for keys, per-entry metadata and allocator fragmentation, and the real requirement is about 26 GB. What that forces: four nodes of 16 GB gives 64 GB, which holds the working set with room to grow and — the part that matters — enough spare that losing one node does not immediately push the survivors into eviction. Size a cache cluster so that N−1 nodes still hold the working set, or a single node failure turns into an eviction storm on top of the reassignment storm.
Throughput per node. 1 million operations a second across four nodes = 250,000 per node. That is achievable for an in-memory store doing hash lookups.
Network, which is the real limit. 1 million operations × 2 KB = 2 GB per second, or 16 gigabits. Spread over four nodes that is 4 gigabits each, comfortable on a 10 gigabit interface — until traffic concentrates. What that forces: the binding constraint on a cache cluster is usually the network interface, not the CPU and not the memory. And it explains the hot-key problem exactly: one key receiving 200,000 requests a second for a 2 KB value is 3.2 gigabits through a single node's interface, and no amount of cluster capacity helps, because the key lives on one machine.
Latency budget. A round trip inside a datacentre is roughly 0.5 ms, and the store's own work on a hash lookup is tens of microseconds. What that forces: the p99 target of 1 ms is mostly network, which means the ways to improve it are to make fewer round trips (batch reads, or an in-process tier in front), not to make the store faster.
The number this estimation actually exists to produce is the working set, because it decides whether caching helps at all. If the hot data is 200 GB and you provision 26 GB, you have not built a 13%-effective cache, you have built a machine that adds a network round trip to every request and still misses. That is the one estimation in this study whose answer can be "do not do this".
3. API and client behaviour
GET key → value | MISS
SET key value ttl → OK
DEL key → OK
INCR key delta → newValue (atomic; no read-modify-write from the client)
CAS key value version → OK | CONFLICT (optimistic concurrency when you must read first)The interesting design here is not the server's five verbs, it is the client library, which carries more of the reliability story than the cluster does.
ts
type CacheResult<T> = T | typeof MISS; // (1)
async function get<T>(key: string): Promise<CacheResult<T>> {
try {
return await withTimeout(node(key).get(key), 20); // (2)
} catch (err) {
metrics.increment('cache.error', { op: 'get' }); // (3)
return MISS; // (4)
}
}(1) the return type has three inhabitants that matter — a value, a cached null, and MISS — and conflating the last two is a classic bug, because "we looked and there is nothing" and "we could not look" require different behaviour. (2) node(key) picks the node from the consistent hash ring, and the timeout is deliberately tiny. Twenty milliseconds is already twenty times the p99 target. A cache client with a 500 ms timeout turns a degraded cache into something strictly worse than no cache, because every request now waits half a second before doing the database work it was always going to do. (3) cache errors are counted, not swallowed silently, or you will never learn that the cache has been broken for a week. (4) every error is a miss. This one line is the whole reliability story: a cache failure degrades latency and never correctness. The application above cannot tell the difference between "not cached" and "cache unreachable", and it should not need to.
The client also pools connections (opening a socket per request costs more than the lookup), batches multi-key reads into one round trip where the keys land on the same node, and holds the ring so that routing is a local computation rather than a lookup.
4. Data placement: consistent hashing
The obvious way to spread keys across four nodes is hash(key) % 4. It is correct, it is one line, and it causes outages.
The problem is what happens when the node count changes. Go from 4 nodes to 5 and the modulus changes from 4 to 5, so almost every key now maps to a different node — roughly 80% of them. Every one of those keys is absent on its new node, so every one of those requests misses, so the entire read load of the system arrives at the database at once, cold. Adding capacity to the cache is a routine operation that should be invisible; with modulo hashing it is an outage (10.6).
Consistent hashing fixes this. Place both nodes and keys on a ring of hash values; a key belongs to the first node found walking clockwise from its position. Adding or removing a node changes ownership only for the arc that node covers — about 1/N of keys — and every other key stays exactly where it was.
Virtual nodes fix the second-order problem. With four nodes placed at four points, the arcs are wildly uneven and one node ends up owning half the ring by chance. Placing each physical node at ~150 pseudo-random points on the ring makes the arcs small and numerous, so the law of large numbers evens the load out, and removing a node scatters its share across all the survivors instead of dumping it all on its single clockwise neighbour.
Who holds the ring? Two answers, and the choice matters. If clients hold it, routing costs nothing at request time but every client must be told about membership changes, and clients with a stale ring send requests to the wrong node. If a proxy holds it, clients stay simple and membership changes are instant, at the cost of an extra network hop on every operation — which against a 1 ms budget is a large fraction. Most high-throughput deployments put the ring in the client and accept the propagation problem, because the hop is too expensive.
5. Architecture and the read path
Three placements, chosen per workload.
Cache-aside is the default. The application reads the cache; on a miss it reads the database and populates. It is explicit, every call site can see what is happening, and it survives total cache loss because the application always knows how to get the real answer. Its cost is duplicated logic at call sites, which you solve by wrapping it in one helper rather than by changing the pattern.
Read-through and write-through put the cache inline, so the application talks only to the cache and the cache talks to the database. Application code gets simpler. The cost is that the cache is now on the correctness path — if it is down, you cannot read at all — which contradicts the requirement that the cache may lose data.
Write-behind lets the cache absorb writes and flush them to the database later. It is the fastest, and it is the only pattern that can lose a write the user was told succeeded. That makes it right for view counts and metrics, and wrong for anything a person would file a complaint about.
Here is cache-aside with the three hazards handled, which is the helper every call site should use:
ts
const NULL_SENTINEL = Symbol('cached-null'); // (1)
async function getUser(id: string): Promise<User | null> {
const key = `user:v3:${id}`; // (2)
const hit = await cache.get<User | typeof NULL_SENTINEL>(key);
if (hit !== MISS) return hit === NULL_SENTINEL ? null : hit; // (3)
return singleflight(key, async () => { // (4)
const row = await db.users.findById(id);
await cache.set(key, row ?? NULL_SENTINEL,
jitter(row ? 300 : 30)); // (5)(6)
return row;
});
}(1) a distinct sentinel for "we looked and there is nothing", so that a cached absence is not confused with a cache miss. Without this, every request for a non-existent identifier reaches the database forever. (2) the version segment in the key. When the shape of a User changes in a deploy, bumping v3 to v4 invalidates the whole namespace instantly, with no coordinated delete and no flush — the old entries simply expire unread. (3) the three-way branch that the sentinel makes possible. (4) single-flight: the first request for this key does the database read and every other concurrent request for the same key waits on that same in-flight promise. Without it, a popular key expiring sends every simultaneous request to the database at once. The implementation is a Map<string, Promise<T>> with the entry removed in a finally, and the finally is not optional — if a failed load leaves the entry behind, every future request for that key waits forever on a rejected promise (3.6.8). (5) the absence is cached too, with a shorter time-to-live than a real value, so that a record created a moment ago becomes visible in 30 seconds rather than five minutes. (6) jitter: multiply the time-to-live by a random factor between 0.9 and 1.1. Thousands of keys written together by a deploy or a bulk import otherwise expire in the same second, producing a synchronised miss storm every five minutes forever.
6. Deep dives
6.1 Invalidation, and why it is famously hard
The difficulty is not the delete. It is that every code path that changes data must know which cached representations that change affects, and that knowledge is invisible to the compiler, spread across the codebase, and grows as the product does. Miss one path — a nightly batch job, an admin tool, a database migration, another service writing to the same table — and the cache serves a wrong answer indefinitely. The failure is silent, it is not local to the code that caused it, and it is usually reported by a confused customer rather than by a monitor.
Three strategies, each with a real failure, which is why the answer is to use all three.
Time-to-live only. Every entry expires after N seconds. Simple, self-healing, and impossible to forget. Its failure is that it serves stale data for up to N seconds by design, and lengthening N to improve the hit rate lengthens the staleness in exact proportion.
Explicit delete on write. Whenever data changes, delete the affected keys in the same request. Fresh, and its failure is the missed path described above — which is not an occasional bug, it is the single most common cache defect in production systems.
Versioned keys. Put a version in the key prefix so a deploy invalidates a whole namespace at once. Its failure is that it only handles schema changes, not data changes, and it leaves the old entries occupying memory until they expire.
The recommended combination: time-to-live on everything as the safety net, explicit deletes on the paths where a five-minute stale window would embarrass you, and version prefixes for schema changes. Each covers the others' failure. Two supporting habits make it work: build every cache key in one module, so the mapping from an entity to its keys is greppable rather than scattered, and measure staleness with a background job that samples cached values against the source of truth and alarms on divergence. Without that measurement, the way you find out about stale data is a customer.
6.2 Delete, do not update — and the exact interleaving that proves it
When data changes, the tempting move is to write the new value into the cache. It is one operation instead of two, and the next reader gets a hit instead of a miss. It is also wrong, and the reason is worth walking slowly because it is the sharpest small argument in caching.
Two requests update the same record. Request A sets the value to 10; request B sets it to 20. The database serialises them and ends with 20, which is correct. But the cache write is a separate operation, and nothing forces the two cache writes into the same order as the two database writes:
A: write DB = 10 ──┐
B: write DB = 20 │ database ends at 20 ✓
B: write cache = 20 │
A: write cache = 10 ─┘ cache ends at 10 ✗ — and stays wrong until the TTLA was slow between its database write and its cache write — a garbage collection pause, a scheduler hiccup, one extra network retry — and that is all it takes. The cache now disagrees with the database, nothing errored, and the wrong value survives until it expires.
Deleting instead of updating removes the failure. Both requests delete the key. Whichever delete lands last, the key is absent, and the next reader loads the current value from the database. The cost is one extra database read after every write, which is a real cost and a small one, and you pay it to eliminate a silent-wrong-answer class of bug (10.14.1).
The residual race, worth naming because a sharp interviewer will: a reader can load a stale value from the database just before a writer commits, and then populate the cache just after the writer's delete. The window is microseconds, the fix is to delete again after a short delay if you truly cannot tolerate it, and the honest answer for most systems is that the time-to-live bounds it and that is enough.
6.3 Stampedes, in three shapes
A stampede is what happens when a cache miss becomes a load spike. There are three distinct shapes and each needs its own defence, which is why "we cache it" is not an answer.
Many concurrent requests, one key. A popular key expires and five thousand in-flight requests all miss simultaneously, so five thousand identical queries hit the database in the same millisecond. Single-flight collapses them into one.
Many keys, one moment. A deploy warms ten thousand keys with an identical five-minute time-to-live. Five minutes later, all ten thousand expire together, and the pattern repeats every five minutes forever. Jitter on the time-to-live spreads them.
Keys that do not exist. A request for a non-existent identifier misses, goes to the database, finds nothing, and caches nothing — so the next identical request does it all again. A scan of invalid identifiers, whether from a bug or an attacker, bypasses the cache entirely and turns straight into database load. Negative caching closes it.
There is a fourth mechanism for the very hottest keys: early recomputation. Rather than waiting for expiry, each read has a small probability of refreshing the value, rising as expiry approaches, so a hot key is refreshed by one unlucky request before it ever actually disappears. The value is never absent, so there is never a moment for a stampede to form.
6.4 Hot keys, and why the cluster cannot help
One key receiving 200,000 requests a second lives on one node, and consistent hashing does not change that — the ring distributes keys, and a hot key is one key. From section 2, that node's network interface is the ceiling: at 2 KB a value, 200,000 requests a second is 3.2 gigabits through one interface.
Two cures. Replicate the hot key across several nodes by appending a small random suffix on read (article:99:r3), so reads spread across replicas while writes must update all of them — which is fine because hot keys are usually read-hot and write-cold. Or put a small in-process tier in front: an L1 holding a few hundred entries with a one-second time-to-live absorbs a celebrity key's traffic entirely, because at 200,000 requests a second across 50 instances, a one-second local time-to-live means each instance makes one network call per second instead of four thousand. That is the same two-tier shape as the rate limiter in 11.3, and it is the cheapest fix available.
The cost of the local tier is a second staleness window stacked on the first: an update now takes up to one second to become visible even after the shared cache is invalidated. State it, bound it, and only use the tier for keys where a second of staleness is harmless.
6.5 Eviction, and why the policy debate is decidable
When memory fills, something must go.
Least recently used is the default and usually right, because most access patterns have temporal locality — the thing you touched a minute ago is likely to be touched again. Its weakness is a scan: a batch job that reads a million records once walks through the cache and evicts the genuinely valuable working set, replacing it with data nobody will ever ask for again.
Least frequently used survives scans, because a one-time read never accumulates enough frequency to displace a persistently popular item. Its weakness is the opposite: yesterday's popular item keeps its high count and refuses to leave, so the cache is slow to adapt when what matters changes.
Time-to-live driven eviction fits data with natural expiry, where the answer to "what should go" is "whatever is oldest by intent rather than by access".
The point worth making is that this is not an argument to be won on elegance. Every mature cache reports hit rate per key prefix, so you can measure which policy performs better on your actual access trace. The question "LRU or LFU?" has an experimental answer, and treating it as a matter of opinion is how teams spend a week debating something a day of measurement would settle.
6.6 Memory, which behaves differently from what you expect
Two facts about the memory of a cache node surprise people.
Fragmentation is real and it is not small. A cache storing values of many different sizes into fixed-size blocks wastes the difference. Storing a 1.1 KB value in a 2 KB slab wastes 900 bytes, and at 10 million objects that is 9 GB of nothing. This is why the estimation added 30% overhead rather than treating 20 GB of data as a 20 GB requirement, and it is why some caches deliberately round value sizes into classes and report the waste as a metric.
Memory pressure changes behaviour before it causes errors. As the working set approaches capacity, eviction rate rises, hit rate falls, and the miss traffic to the database rises — smoothly, with nothing failing. The signal to watch is therefore eviction rate, not memory usage, because eviction rate starts moving while there is still apparently plenty of headroom.
7. Decision Ledger
| Decision | Alternatives | Why this | What it costs |
|---|---|---|---|
| Consistent hashing with ~150 virtual points per node | hash % N; a routing proxy | a node change moves ~1/N of keys instead of ~80% | clients must hold and refresh the ring |
| Ring in the client | ring in a proxy | no extra network hop against a 1 ms budget | membership changes propagate slowly; stale rings misroute |
| Cache-aside as the default | read-through; write-behind | explicit, and survives total cache loss | duplicated logic unless wrapped in one helper |
| Every error treated as a miss | propagate cache errors | a cache outage degrades latency, never correctness | the database must be able to absorb it — capacity-plan for it |
| Delete on write, never update | update the cached value | removes a silent reorder that leaves the cache wrong until expiry | one extra database read after each write |
| TTL + explicit delete + version prefix | any one alone | each covers the others' failure mode | a staleness window, and key hygiene to maintain |
| Single-flight, jitter, negative caching | populate naively on miss | closes the three distinct stampede shapes | a little machinery in one shared helper |
| Size for N−1 nodes | size for N | losing a node does not also trigger an eviction storm | ~25% more memory bought than strictly needed |
8. Scale and failure
Losing a node reassigns about 1/N of keys to other nodes, where they are absent. Those requests miss, and the database sees a step change in load — instant, with no ramp, equal to one quarter of total read traffic in a four-node cluster. If the database has headroom, latency rises for a minute and the cache refills. If it does not, the database saturates, application threads pile up waiting on it, timeouts start, retries multiply the load, and the cache node's death becomes a full outage (10.9).
This is why capacity planning must assume a cold cache. The honest question, asked in section 1 and worth repeating here because it is the study's central point: can the database serve production traffic at a 0% hit rate for the minutes it takes to warm? If not, the cache is not an optimisation, it is a part of the system everything else rests on, disguised as one, and it needs replication, gradual warming, and request throttling during a cold start.
Cross-region. Caches are per-region, because a cross-region cache hit costs more than a local database read and therefore is not a cache at all. That means invalidation has to be broadcast to every region, usually over a publish-subscribe topic (10.8.1), and broadcast invalidation is best-effort — a region that misses a message serves stale data until the time-to-live saves it. Which is one more reason there is no key without a time-to-live.
At 10×. Add nodes to the same ring, which is exactly what consistent hashing was for. Add in-process tiers to cut network operations for hot keys. Compress large values. And before buying any hardware, measure the hit rate per prefix, because a cache running at a 60% hit rate is far more often mis-keyed than undersized, and hardware does not fix a keying mistake.
| What breaks | Blast radius | How you find out | What keeps it running | Recovery |
|---|---|---|---|---|
| One node lost | ~1/N of keys miss; database step-load | hit rate drop; database QPS step | single-flight, jitter, N−1 sizing, load shedding | ring rebalances; cache refills in minutes |
| Whole cluster down | 0% hit rate; full load on the database | cache error counter; database saturation | errors are misses, so nothing is wrong, only slow | warm before restoring full traffic |
| Cache slow, not down | every request pays the extra latency | cache p99 measured separately | short client timeout turns slow into a miss | fix the node; the timeout contains it meanwhile |
| Hot key | one node's network interface saturates | per-key operation counts | in-process tier, or replicate the key with suffixes | keep the tier; the key stays hot |
| Missed invalidation path | one entity is silently wrong | staleness sampler comparing cache to source | TTL bounds it to the window | delete the key; add the path to the delete helper |
| Deploy expires all keys at once | periodic synchronised miss storms | sawtooth in hit rate at a fixed interval | jitter on every TTL | add jitter; the pattern disappears |
| Memory pressure | rising evictions, falling hit rate, no errors | eviction rate, not memory usage | add capacity or shrink values | resize; verify the working set estimate |
The two rows that never error are the ones to dwell on. A slow cache and a missed invalidation path both produce a system that appears healthy: no exceptions, no failed requests, a normal-looking dashboard. The first is caught only by measuring the cache's own latency separately from the endpoints in front of it, and the second only by actively sampling cached values against the truth. Neither will ever page anyone on its own (10.10).
What the interviewer will push on
"Why not hash(key) % N?" They are checking whether you know what happens during a routine operation. Adding a fifth node changes the modulus and remaps roughly 80% of keys, so the cache empties and the database takes full production load cold — turning capacity expansion into an outage. The tell is that you frame it as a maintenance problem rather than a correctness one; modulo hashing is perfectly correct, it just makes an ordinary Tuesday afternoon dangerous.
"On a write, why delete the cached value instead of updating it?" This is the sharpest small question in caching. Walk the interleaving: two writers, database ends at 20 correctly, cache writes land in the opposite order and it ends at 10, and nothing errors — the wrong value survives until expiry. Deleting removes the ordering dependency entirely because the absence of a key is not order-sensitive. Then name the residual race (a reader repopulating just after a writer's delete) and say honestly that the time-to-live bounds it.
"Your hit rate is 95%. Is the cache doing its job?" They want to see whether you can read a metric. A hit rate is a capacity signal, not a success signal — and the arithmetic is worth doing out loud: going from 95% to 90% doubles the traffic reaching the database, because the miss rate went from 5% to 10%. Small changes in hit rate are large changes in database load, which is why the alarm should be on the hit rate and not on the database.
"A cache node reboots at peak. Walk me through it." The strong answer gives the order: 1/N of keys reassign, those requests miss, database load steps up instantly with no ramp, and then the two aggravators — clients retrying misses multiply the surge, and hot keys among the reassigned set stampede unless single-flight is in place. Then say what should have been true beforehand: sizing for N−1, single-flight and jitter in the shared helper, load shedding as a valve, and a rehearsed drill so the shape of this failure was learned in a load test rather than in production.
"How do you know when the cache has stale data?" Most candidates have no answer, and it is the question that separates people who have run a cache from people who have configured one. The answer is a background sampler that reads values from the cache and from the source of truth and reports divergence, plus the observation that without it the discovery mechanism is a customer complaint — because a stale cache entry produces no error, no log line and no latency change.
"One key is 20% of your traffic. Does adding nodes help?" No, and the reason is the tell: the ring distributes keys, and this is one key, so it lives on one node whose network interface is the ceiling. The cures are an in-process tier in front (which turns 200,000 requests a second into one per instance per second) or replicating the key across nodes with a random suffix on read. Both add a staleness window, and naming that cost unprompted is the senior move.
Volunteer this, because nobody asks: the single question that determines how much care this cache deserves is whether the database can serve production traffic at a 0% hit rate. If it can, everything here is an optimisation and can be run casually. If it cannot, the cache is a tier-1 dependency and should be replicated, monitored, capacity-planned and drilled like a database — and the dangerous state is not knowing which of the two you have, because a dependency and an optimisation look exactly alike right up until the moment they do not.
Next: 11.5 — every study so far has assumed identifiers that are unique across the whole system without a central authority handing them out. That assumption is doing a lot of work, and the next study is what it takes to make it true.
Recall
- Placements: cache-aside as the default (explicit, survives total cache loss), read/write-through (cache becomes a correctness dependency), write-behind (fastest, can lose an acknowledged write — counters, never money).
- Consistent hashing with ~150 virtual points per node. A node change moves ~1/N of keys;
hash % Nremaps ~80% and empties the cache into the database. Ring in the client (no extra hop) or in a proxy (instant membership, one more hop against a 1 ms budget). - Every cache error is a miss, with a client timeout of ~20 ms. A cache failure must degrade latency, never correctness — and a slow cache is worse than no cache.
- Delete on write, never update. Two writers can land their cache writes in the opposite order to their database writes, leaving the cache wrong until expiry with nothing erroring.
- Three stampede shapes, three defences: concurrent misses on one key → single-flight (remove the in-flight entry in a
finally); many keys expiring together → TTL jitter; requests for keys that do not exist → negative caching with a shorter TTL. Plus early recomputation for the hottest keys. - Invalidation is TTL + explicit delete + version prefix, because each covers the others' failure. Build keys in one module; run a staleness sampler, or your detector is a customer.
- Hot key = one node's network interface. Sharding cannot help. Cures: in-process tier with a 1 s TTL, or replicate the key with a random read suffix. Both add staleness.
- Sizing: working set + ~30% for fragmentation, and provision so N−1 nodes still hold it. Watch eviction rate, not memory usage, because eviction moves first.
- The decisive question: can the database serve production traffic at a 0% hit rate? If not, the cache is a tier-1 dependency wearing an optimisation's clothes.
Self-test: Why does modulo hashing cause outages during routine maintenance? Give the interleaving that makes update-on-write wrong. Name the three stampede shapes and their defences. What does going from 95% to 90% hit rate do to database load? Which metric moves first under memory pressure?
Quiz Bank
FoundationalExplain cache stampede and the mechanisms that prevent it.
A stampede is what happens when a cache miss turns into a load spike on the thing the cache was protecting. It has three distinct shapes, and each needs its own defence — which is why "we put a cache in front of it" is not, on its own, an answer.
Shape one: many concurrent requests, one key. A popular key expires while five thousand requests are in flight. All five thousand miss in the same millisecond and all five thousand issue the same query. The database receives a spike precisely on its hottest data, usually at peak traffic. Single-flight fixes it: the first miss starts the load and every other request for that key waits on the same in-flight promise, so five thousand misses become one query. Implementation is a map from key to promise with the entry removed in a finally — and the finally matters, because a failed load that leaves its entry behind wedges that key forever (3.6.8).
Shape two: many keys, one moment. A deploy, a warm-up script or a bulk import writes ten thousand keys with the same time-to-live. Five minutes later they all expire together, and the storm repeats on a fixed cycle forever, showing up as a sawtooth in the hit-rate graph. Jitter fixes it: multiply each time-to-live by a random factor between 0.9 and 1.1 so expiry is spread across a window instead of an instant.
Shape three: keys that do not exist. A request for a missing identifier misses, queries the database, finds nothing, and caches nothing — so the identical next request repeats the whole thing. A scan of invalid identifiers, from a bug or from an attacker, therefore bypasses the cache completely and becomes pure database load. Negative caching fixes it: store a sentinel meaning "there is nothing here", with a deliberately shorter time-to-live than a real value, so a newly created record becomes visible in 30 seconds rather than five minutes.
And a fourth mechanism for the hottest keys: early recomputation. Instead of waiting for expiry, each read has a small chance of refreshing the value, rising as expiry approaches. One unlucky request refreshes it early, so the key is never actually absent and there is no moment for a stampede to form.
InterviewWhy is cache invalidation famously hard, and what is your concrete strategy?
Why it is hard. Invalidation requires every code path that mutates data to know which cached representations that mutation affects. That knowledge is not checked by a compiler, it is spread across the whole codebase, and it grows every time someone adds a feature. Miss one path — a nightly batch job, an internal admin tool, a database migration, another team's service writing to the same table — and the cache serves a wrong answer indefinitely. The failure is silent, it is not local to the code that caused it, and it is normally reported by a confused customer rather than by any monitor you own.
Layer one: a time-to-live on everything, always. This is the safety net that bounds staleness to a known window even when the invalidation logic is wrong, forgotten, or written by someone who has since left. There is no key without a time-to-live, and there is no exception to that rule.
Layer two: explicit delete on the paths that matter. For user-visible changes where five minutes of staleness would be embarrassing, delete the affected keys inside the same request that made the change. Delete rather than update, because updating races with other concurrent writers and can leave the cache holding an older value than the database — the interleaving is in section 6.2.
Layer three: version prefixes in the key. user:v3:42. When a schema or serialisation format changes, bumping the version invalidates the entire namespace at deploy time, with no coordinated flush, no downtime and no risk of missing a key. Old entries simply expire unread.
Two supporting habits. Build every cache key in one module, so the mapping from entity to keys is greppable rather than scattered through the codebase — this is what makes it possible to answer "what caches does changing a user affect?" in thirty seconds. And measure staleness with a background job that samples cached values against the source of truth and alarms on divergence, because otherwise you have no detector at all.
The philosophy to state out loud: treat stale data as inevitable and bound it, rather than treating perfect invalidation as achievable and being silently wrong. Every layer here exists because the layer above it will eventually be forgotten by somebody.
InterviewOn a write, should you update the cached value or delete it?
Delete it. The reason is a specific interleaving, and it is worth walking through because it is short and decisive.
Two requests update the same record concurrently. A sets it to 10, B sets it to 20. The database serialises them and ends at 20, which is correct. But each request also writes the cache, and that is a separate operation with no ordering relationship to the database write. So this order is possible:
A writes DB = 10
B writes DB = 20 → database ends at 20 ✓
B writes cache = 20
A writes cache = 10 → cache ends at 10 ✗All it takes is for A to be slow between its two operations — a garbage collection pause, a scheduler hiccup, a single network retry. The cache now holds a value the database never ends at, nothing errored, no request failed, and the wrong value survives until the time-to-live expires it.
Deleting removes the failure by removing the ordering question. Both requests delete the key. Whichever delete happens last, the outcome is identical: the key is gone. The next reader loads the current value from the database and populates the cache with it. There is no interleaving of two deletes that produces a wrong result, because absence has no version.
What it costs: one extra database read after each write, since the next reader misses. That is a real cost, it is small, and you are buying the elimination of a class of silent wrong answers with it.
The residual race, which a sharp interviewer will raise: a reader can fetch a stale value from the database just before a writer commits, and then populate the cache just after that writer's delete — leaving the stale value cached. The window is microseconds wide. If you genuinely cannot tolerate it, the standard answer is to delete again after a short delay, so the second delete lands after any in-flight repopulation. For almost every system the honest answer is that the time-to-live bounds the damage and that is sufficient (10.14.1).
StaffYour cache cluster loses a node at peak. Walk through what happens, and what should have been true beforehand.
What happens, in order. The ring reassigns that node's arcs, so roughly 1/N of all keys now map to different nodes where they are absent. Every request for those keys misses. The database sees a step change in load equal to (1/N × total read QPS), arriving instantly with no ramp — in a four-node cluster that is a quarter of all reads appearing at once.
If the database has headroom, latency rises for a minute or two while the cache refills, and nobody outside the on-call channel notices. If it does not, the sequence is: the database saturates, its latency climbs, application threads and connections pile up waiting on it, request timeouts begin, and clients retry — which increases the load (10.9). The cache node's death has become a full-system outage, which is exactly the story at the top of this page.
Two aggravators to name. Retry amplification: every layer that retries a slow request multiplies the surge. Stampedes on the reassigned hot keys: many concurrent requests for the same newly-missing key, all issuing the same query, unless single-flight is already in the shared helper.
What should have been true beforehand.
Capacity planned for a cold cache. The honest question is whether the database can serve production traffic at a 0% hit rate for the warm-up window. If the answer is no, the cache is a dependency and must be run like one: replicated, monitored as a first-class service, with a documented recovery procedure and an owner.
Consistent hashing, so that this event moves 1/N of keys rather than nearly all of them.
Sizing for N−1 nodes, so that the survivors can hold the working set without immediately starting to evict — otherwise the reassignment storm is compounded by an eviction storm and the hit rate falls further than the arithmetic suggests.
Single-flight, jitter and negative caching in the shared client helper, so the miss surge is the smallest it can be rather than the largest.
A load-shedding valve. Under database saturation, shed or queue low-priority reads rather than letting every request degrade equally. Serving 90% of traffic well beats serving 100% of it badly, and a fast rejection does not hold a connection open.
A rehearsed drill. Kill a cache node during a load test and watch what the database does. This failure is certain to happen eventually; the only variable is whether you learned its shape on a Tuesday morning with a rollback ready or at peak with customers watching.
The framing that makes this a staff-level answer: a cache does not only change the system's latency, it changes the system's failure profile. It introduces a mode in which the database receives traffic it has never seen in its life, and the design is not finished until that mode has a written plan.
Flashcards
FlashCache placements
Cache-aside (default; explicit; survives total loss) · read/write-through (cache becomes a correctness dependency) · write-behind (fastest; can lose an acknowledged write — counters only).
FlashConsistent hashing, and the failure it prevents
Ring plus ~150 virtual points per node: a node change moves ~1/N of keys. hash % N remaps ~80% on any node-count change, emptying the cache into a cold database.
FlashDelete, do not update
Two writers can land cache writes in the opposite order to their database writes, so the cache ends wrong and stays wrong until expiry, with nothing erroring. Deletes have no ordering problem.
FlashThree stampede shapes
Concurrent misses on one key → single-flight (clear the entry in finally). Many keys expiring together → TTL jitter ±10%. Requests for missing keys → negative caching with a shorter TTL. Hottest keys → early recomputation.
FlashHot key
One key lives on one node, so its network interface is the ceiling and sharding cannot help. Fix with an in-process tier (1 s TTL) or read-replicated keys with a random suffix. Both add a staleness window.
FlashThe question that classifies your cache
Can the database serve production traffic at a 0% hit rate? Yes ⇒ optimisation. No ⇒ tier-1 dependency needing replication, warm-up and drills. Not knowing is the dangerous state.
Scenario Drill
DrillA team reports their cache is not helping: 60% hit rate, p99 unchanged, the database still the bottleneck. Diagnose it systematically.
Do not add nodes first. A 60% hit rate is far more often a keying problem than a capacity problem, and hardware buys nothing if the design is wrong. Four numbers turn "it isn't helping" into a specific defect, and collecting them takes an afternoon.
Step 1 — break the hit rate down by key prefix. A 60% aggregate hides everything. Almost every time, this reveals one prefix at 98% and another at 5%. The 5% prefix is the entire problem, and the aggregate was never going to tell you which one it was.
Step 2 — diagnose the low prefix against four causes.
The working set exceeds capacity. Check whether eviction rate is high and whether keys are being evicted well before their time-to-live expires. If so the cache is thrashing, and this genuinely is a sizing problem — go back to section 2's arithmetic, working set plus 30%, and see how far off you are.
The keys are too specific. Caching search:q=shoes&page=1&sort=price&filter=red&user=8821 produces a key that will never be requested a second time, because no two users produce the same query string. The fix is to cache the reusable part — the result set for q=shoes — and apply user-specific filtering and pagination after the cache. This is frequently a 5% to 90% change and costs nothing but a refactor of one function.
The time-to-live is shorter than the request spacing. If a key is requested every 60 seconds and its time-to-live is 30, every single request misses and the cache is doing pure harm. Measure inter-arrival time per prefix and set the time-to-live above it, as far as the staleness budget allows.
Over-invalidation. An aggressive delete-on-write path that clears a whole namespace on any write means entries never survive long enough to be used. Compare the delete rate against the write rate: if they are within a factor of a hundred of each other on a read-heavy workload, invalidation is eating the cache.
Step 3 — question whether p99 should have moved at all. This is the step most teams skip and it is often the actual answer. Even a 95% hit rate leaves 5% of requests going to the database, and p99 is by definition the slow tail. If a miss costs 200 ms, a 95% hit rate can leave p99 essentially unchanged while p50 improves enormously. That is not a broken cache, it is a misread metric. The fix for tail latency is to make the miss path faster — an index, a smaller payload, a simpler query — or to eliminate misses specifically for the expensive keys with early recomputation and longer time-to-live values. A bigger cache does not help, because the problem was never capacity.
Step 4 — check the client, where several silent faults live. Errors being counted as hits (so the hit rate is a lie). A timeout so generous that a degraded cache makes every request slower than not caching at all. Connection pool exhaustion adding queueing delay in front of a store that is answering in 200 microseconds. All three present as "the cache isn't helping" while the server-side metrics look perfectly healthy.
The report to write: hit rate by prefix, eviction rate, miss-path latency, and inter-arrival time by prefix. Four numbers, one afternoon, and they convert an argument into a defect with a fix. Buying capacity before collecting them is guessing with a budget attached — and if the answer turns out to be step 2's second cause, the capacity would not have helped at any price.