10.14.1 — Caching Strategies and Eviction

A product page takes 400 ms to build. Eleven database queries: the product, its images, its stock, its reviews, its price, the seller's rating. The traffic pattern is the usual one — 90 percent of requests hit 1 percent of the products, because that is what a homepage and a search ranking do to a catalogue.

Put the assembled page in memory for sixty seconds and the same page takes 2 ms. The database load drops by roughly 90 percent. Nothing about the product changed; you just stopped asking the same question over and over.

That is the whole idea, and it is also where the trouble starts. A cache is a second copy of data, kept somewhere faster. The moment a second copy exists, it can disagree with the first one, and every decision on this page is about controlling how it disagrees and for how long.

1. The two questions every caching design answers

How does data get into the cache? and how does it get out?

Everything with a name — cache-aside, write-through, LRU, TTL — is an answer to one of those two. Getting the vocabulary right matters because an interviewer will ask "which caching strategy?" and the useful answer names a read pattern and a write pattern and an eviction policy, since those are three independent choices.

2. Read patterns: how data arrives

Cache-aside, also called lazy loading

The application is in charge. It looks in the cache, and on a miss it loads from the database and puts the value in the cache itself.

async function getProduct(id: ProductId): Promise<Product> {
  const cached = await cache.get(`product:${id}`);            // (1)
  if (cached) return cached;                                   // hit

  const product = await db.products.findById(id);              // (2) miss: go to the source
  if (product) {
    await cache.set(`product:${id}`, product, { ttl: 60 });     // (3) fill it for next time
  }
  return product;
}

(1) Ask the cache first. (2) On a miss the application knows to go to the database — that knowledge lives in your code, which is the defining feature of this pattern. (3) The application also writes it back, with a lifetime.

Why this is the default everywhere. Only data that is actually requested ever occupies memory, so a catalogue of ten million products with a hot set of ten thousand only ever caches ten thousand. And if the cache goes down entirely, the application still works — every request becomes a miss and goes to the database. That resilience is the reason cache-aside is the safe default: the cache is an optimisation, not a dependency.

What it costs. Every distinct key pays a slow first request. And the miss path is written by hand in every place that reads, so a new endpoint that forgets the cache is a silent performance regression nobody notices until load.

Read-through

The application asks the cache and the cache asks the database. The application never sees the difference between a hit and a miss.

const product = await productCache.get(id);   // the cache loads from the database on a miss

Same shape as cache-aside, but the loading logic lives inside the cache layer rather than in every caller. That is the entire distinction, and candidates often blur them. The practical benefit is that there is exactly one implementation of "how do I load a product", so no endpoint can forget it. The practical cost is that the cache is now on the critical path: if it is down, reads fail rather than degrading, unless you build a bypass.

3. Write patterns: how updates get in

This is where the real decisions are, because a write is where the two copies can start disagreeing.

Write-through

Write to the cache and the database together, before returning to the caller.

async function updatePrice(id: ProductId, price: Money): Promise<void> {
  await db.products.updatePrice(id, price);                   // (1) source of truth first
  await cache.set(`product:${id}`, await db.products.findById(id), { ttl: 60 });  // (2)
}

(1) The database is updated first, always. If you write the cache first and the database write fails, the cache now holds a value that never existed. (2) Then the cache is refreshed.

What you get: the cache is never stale for data written through this path, and the next reader gets a hit rather than a miss.

What it costs: every write pays the cache write too, and — the part people miss — you are caching data that may never be read again. A write-heavy system with a long tail of rarely-read records fills its cache with junk this way.

And the failure mode to name: those two operations are not atomic. If the process dies between them, the database is correct and the cache holds the old value until its lifetime expires. That is why the TTL on line (2) matters even in a write-through design — it is the backstop that bounds how long any inconsistency can survive.

Write-around

Write to the database only, and let the cache find out on its next miss.

async function updatePrice(id: ProductId, price: Money): Promise<void> {
  await db.products.updatePrice(id, price);
  await cache.delete(`product:${id}`);           // ← invalidate rather than update
}

Deleting is usually better than updating, and the reason is worth knowing. If two writers update the same product concurrently and each then writes its own version into the cache, the cache can end up holding the older of the two even though the database holds the newer — because the two cache writes can land in the opposite order to the two database writes. Deleting has no such problem: whichever delete lands last, the next reader misses and loads whatever the database currently says, which is by definition correct.

Write-around suits write-heavy data that is rarely read. Audit logs, event records, anything that is written constantly and read occasionally.

Write-behind, also called write-back

Write to the cache, acknowledge the caller immediately, and flush to the database later in batches.

This is the fastest option and the most dangerous. Writes become memory-speed, and many updates to the same key collapse into one database write, which is a genuine win for something like a view counter being incremented ten thousand times a minute.

The cost is data loss. If the cache node dies before the flush, those writes are gone. There is no recovering them, because the only copy was in memory. So write-behind is correct for data you can afford to lose — counters, analytics, last-seen timestamps, recommendation signals — and wrong for anything a customer would notice. Never for money.

Figure 1 — The three write patterns. Pick one per kind of data, not one for the whole system. A price uses write-through; a view counter uses write-behind; an audit log uses write-around.

Refresh-ahead

Before a hot key expires, refresh it in the background so no reader ever experiences the miss.

This is the answer to a specific problem: a key that is read constantly and takes 400 ms to rebuild causes a visible latency spike every time it expires. Refresh-ahead removes the spike by predicting the expiry.

The cost is that you refresh keys that nobody was going to ask for again, so it earns its place only for a small set of genuinely hot keys — a homepage, a top-sellers list, a configuration blob. Applying it to everything is wasted work.

4. Choosing, in one table

Data	Read pattern	Write pattern	Why
Product page	Cache-aside	Write-around + delete	Read-heavy, occasional edits
User session	Read-through	Write-through	Must be fresh, always read
View counter	—	Write-behind	Loss-tolerable, huge write volume
Audit log	—	Write-around	Written always, read rarely
Config blob	Refresh-ahead	Write-through	Hot, expensive, must not spike

The row that matters most is the first one, because "cache-aside plus delete on write" is the correct default for the overwhelming majority of application data, and being able to say why — it survives a cache outage, it only caches what is read, and deleting avoids the concurrent-write ordering problem — is a complete answer to "how would you add caching".

5. Eviction: how data leaves

Memory is finite, so something has to go. There are two separate mechanisms and confusing them is a common mistake.

Expiry removes data because it is too old to trust. That is a correctness decision.

Eviction removes data because the cache is full. That is a capacity decision.

A cache needs both. Expiry without eviction grows until it runs out of memory. Eviction without expiry serves stale data forever as long as it stays popular.

The policies

LRU — least recently used. Evict whatever has gone longest without being touched. It matches the way real access patterns behave, because something used a second ago is likely to be used again. It is the default in nearly every cache for good reason. Its implementation — a hash map plus a doubly linked list, giving O(1) get and put — is built line by line in 9.7.30.

Its weakness is a scan. One batch job reading a million rows once each will walk through the cache and evict the entire hot set, replacing it with a million things nobody will ever ask for again. Hit rate collapses and stays collapsed until the hot set is rebuilt.

LFU — least frequently used. Evict whatever has been used least often. This resists scans well, because a one-time read has a count of one and gets evicted immediately.

Its weakness is the mirror image: it never forgets. Yesterday's viral article has a count of two million and will outlive today's genuinely hot content forever. The cure is ageing: periodically halve every counter, so old popularity decays and recent popularity can catch up. An LFU without ageing is a cache that gradually fills with history.

FIFO evicts the oldest inserted, regardless of use. It is cheap and it is usually wrong, because the thing you inserted first is often the thing everybody wants.

Random picks a victim at random. It sounds terrible and performs surprisingly close to LRU on many workloads, at a fraction of the bookkeeping. Redis defaults to an approximated LRU that samples a handful of keys and evicts the least-recently-used of the sample, precisely because exact LRU costs more than the accuracy is worth.

TTL-based evicts whatever is closest to expiring. Useful when everything has a natural lifetime.

The modern compromise, worth naming because it is what high-end caches actually use: keep a small, cheap sketch of how often each key has been requested recently, and use it to decide whether a new arrival deserves to displace the victim LRU has chosen. A scan's one-time reads never earn their way in, so the hot set survives. This is the idea behind W-TinyLFU, and the sketch it uses is a Count-Min Sketch (10.18).

Policy	Good at	Bad at
LRU	Normal traffic	Scans wipe it
LFU	Resisting scans	Never forgets, without ageing
FIFO	Being cheap	Evicting popular items
Random	Being very cheap	Nothing in particular
Sketch + LRU	Both	More memory and complexity

6. Invalidation, the actually hard part

The old joke is that there are two hard problems in computing, and cache invalidation is one of them. The reason it is hard is that the cache does not know when the underlying data changed unless somebody tells it.

There are three ways to tell it, and real systems use all three at once.

A time limit. Every entry expires after N seconds. This is not really invalidation; it is a bound on how wrong you are willing to be. Its enormous virtue is that it requires no coordination and cannot be forgotten. Almost every cache entry should have one, even in designs that also invalidate explicitly, because the TTL is what limits the damage when the explicit path fails.

Explicit deletion on write. Whoever changes the data deletes the key. Precise and immediate, and fragile in exactly one way: it only works if every writer remembers. A data migration, an admin tool, or a second service writing to the same table will all leave stale entries behind. This is the same "every caller must remember" weakness that 9.5.1 warns about for locks, and it has the same cure — push the responsibility down to one place, which here means invalidating from a change-data-capture stream off the database (10.8.4) rather than from application code.

Versioned keys. Put a version in the key itself, so a change makes the old key unreachable rather than wrong.

const key = `product:${id}:v${product.updatedAt.getTime()}`;   // (1)

(1) The key changes when the data changes, so nothing ever needs deleting. This is beautiful for content that has a natural version — a deployed asset, a rendered template, an image derivative — and its cost is that the old entries linger until eviction, wasting memory. It is also the only one of the three that is safe across many cache nodes with no coordination at all, which is why every asset pipeline in the world puts a hash in the filename.

The rule that resolves most arguments: use a TTL always, add explicit invalidation where staleness is expensive, and use versioned keys where the data has an obvious version. And decide the TTL from the business, not from a feeling — ask "how stale can this be before somebody complains?" A product description can be an hour stale. A price cannot be more than a few seconds stale. A permission check should not be cached at all.

7. The arithmetic that justifies the effort

Two numbers make the case, and both are worth being able to produce on demand.

Effective latency. With a hit rate h, a hit costing H and a miss costing M, the average is h × H + (1 − h) × M. With a 2 ms hit and a 400 ms miss:

Hit rate	Average latency
0%	400 ms
90%	41.8 ms
95%	21.9 ms
99%	6.0 ms
99.9%	2.4 ms

The shape of that column is the lesson. Going from 0 to 90 percent removes 90 percent of the latency. Going from 95 to 99 percent removes another 73 percent of what was left. The last few percent of hit rate are worth as much as the first ninety, which is why serious systems fight hard over small hit-rate improvements that look trivial on a dashboard.

Load reduction. At 10,000 requests per second and a 95 percent hit rate, the database sees 500 per second. Now imagine the hit rate drops to 90 percent — a change that looks minor. The database now sees 1,000 per second, which is double. Cache hit rate is not a performance metric; it is a capacity metric, and a small dip in it is a large spike in load on the thing least able to absorb one. This is exactly why a cache restart can take down a database that was comfortably idle a minute earlier, which is 10.14.2's subject.

8. What not to cache

Anything you must not serve stale. A permission check, an account balance at the moment of a transfer, a stock level at the moment of a sale. If being wrong for two seconds is unacceptable, the answer is not a shorter TTL, it is no cache.

Data with no reuse. Caching something read once per key wastes memory and adds a write for no benefit. The question to ask is not "is this slow" but "is this asked for repeatedly".

Per-user data with a huge key space and low repeat rate. A million users each with a personalised feed read once a day will evict everything useful and hit almost never.

Anything where a wrong answer is silent. If a stale value produces a visibly broken page, somebody reports it. If it produces a slightly wrong number in a report, nobody notices for months.

9. What the interviewer will push on

"Which caching strategy would you use?" They are checking whether you know these are three independent choices. A complete answer names a read pattern, a write pattern and an eviction policy, and attaches them to a specific kind of data — "cache-aside with delete-on-write and LRU for product pages; write-behind for view counters." A candidate who says "I'd use Redis" has named a product, not a strategy.

"Why delete the key on write instead of updating it?" The tell for real experience. The answer is the concurrent-write ordering problem: two writers updating the cache can land in the opposite order to their database writes, leaving the cache holding the older value permanently. A delete cannot get this wrong, because the next reader loads whatever the database currently says.

"Your cache restarts. What happens?" They want to hear that hit rate goes to zero and the database receives the full, unabsorbed load — often many times what it normally sees — and that this is how caches take down the systems they were protecting. Good follow-up answers: warm the cache before taking traffic, restart nodes one at a time rather than together, and put a concurrency limit in front of the database so the recovery is slow rather than fatal.

"How do you pick the TTL?" The wrong answer is a number. The right answer is a question back: how stale can this be before somebody complains? Then note that the TTL is also your safety net for invalidation you forgot, so even a design with explicit deletion keeps one.

"When does LRU fail?" Scans. One batch job reading everything once evicts the entire hot set. Mentioning ageing for LFU in the same breath — that LFU fails in the opposite direction because it never forgets — shows you understand both as trade-offs rather than as a ranking.

The thing to volunteer that nobody asks for: hit rate is a capacity metric, not a performance metric. Show the arithmetic — 95 percent to 90 percent doubles the database load — and then say that you would alert on hit rate dropping, not on latency rising, because hit rate moves first and latency is the symptom.

Next: 10.14.2 takes this from one process to a cluster, where the interesting failures live: hot keys, stampedes, and the cache that takes down the database it was protecting.

Recall

• A cache is a second copy, so the whole design is about controlling how and for how long it can disagree with the first one. Three independent choices: read pattern, write pattern, eviction policy.
• Cache-aside — your code handles the miss. Only caches what is read; survives a cache outage because a miss just means a slow request. The correct default.
• Read-through — the cache handles the miss. One implementation, but the cache is now on the critical path.
• Write-through — both, before returning. Fresh, but every write pays and you cache things nobody reads. Write-around — database only, then delete the key. Write-behind — acknowledge now, flush later; fastest, and it loses data on a node death, so never for money.
• Delete, do not update, on write. Two concurrent cache writes can land in the opposite order to their database writes; a delete cannot be wrong.
• Expiry is a correctness decision (too old to trust); eviction is a capacity decision (cache is full). You need both.
• LRU matches real access patterns and is destroyed by a scan. LFU resists scans and never forgets without ageing. High-end caches use a frequency sketch to decide whether a new arrival deserves to displace LRU's victim.
• Invalidation: a TTL always (it bounds how wrong you can be, and it is the backstop when explicit invalidation is forgotten), explicit deletion where staleness is expensive, versioned keys where the data has a natural version.
• Hit rate is a capacity metric. 95% → 90% doubles the load reaching the database.

Self-test: Name the three independent choices in a caching design. Why is cache-aside safer than read-through when the cache dies? Why delete rather than update on a write? What is the difference between expiry and eviction? What kills LRU, and what kills LFU? What happens to your database when the cache restarts?

Quiz Bank

FoundationalExplain cache-aside, read-through, write-through, write-around and write-behind, and say which combination you would default to.

They split into two groups, and keeping the groups separate is most of the answer.

Read patterns. In cache-aside, your application asks the cache, and on a miss it loads from the database and writes the value back itself. The knowledge of how to load lives in your code. In read-through, the application only ever asks the cache, and the cache knows how to load on a miss. The difference is purely where the loading logic lives, and it has one important consequence: with cache-aside, a dead cache means every request becomes a slow miss and the system still works, whereas with read-through a dead cache means reads fail unless you build a bypass.

Write patterns. Write-through updates the database and then the cache before returning, so the cache is never stale for that path — at the cost of a second write on every update and of caching values nobody will read. Write-around updates the database and deletes the cache key, letting the next reader repopulate it, which suits data written constantly and read rarely. Write-behind writes to the cache, returns immediately, and flushes to the database later in batches, which is by far the fastest and loses data outright if the cache node dies before the flush.

The default I would reach for is cache-aside plus delete-on-write, with LRU eviction and a TTL on every entry, and each part of that has a reason.

Cache-aside because only requested data occupies memory, and because a cache outage degrades performance rather than causing failure.

Delete rather than update because two concurrent writers updating the cache can land in the opposite order to their database writes, leaving the cache permanently holding the older value; a delete cannot get this wrong.

A TTL always, because it bounds how long any inconsistency can survive and because it is the safety net for the invalidation somebody forgot to add in a migration script or an admin tool.

And the qualification that makes the answer complete: this is a default per kind of data, not per system. The same application will use write-behind for a view counter, write-around for an audit log, and no cache at all for a permission check.

AppliedYour cache cluster restarts during a deploy and the database falls over even though it was at 20 percent CPU a minute earlier. Explain the mechanism and give the fixes.

The mechanism is that the cache was absorbing far more load than the numbers suggested.

Take a realistic set of figures. Ten thousand requests per second, a 95 percent hit rate, so the database sees 500 per second and sits comfortably at 20 percent. The cache restarts and the hit rate goes to zero. The database now sees ten thousand per second — twenty times its normal load — and it does not degrade gracefully, it collapses.

Then it gets worse, in two ways that are worth naming because they turn a spike into an outage.

Queries take longer under load, so each connection is held longer, so the connection pool saturates, so requests queue, so requests time out. Clients retry the timed-out requests, adding still more load to a database that is already failing. This is the retry amplification from 10.9.

Every one of those ten thousand requests is a cache miss that will also try to populate the cache. So on top of the read storm, the empty cache receives ten thousand writes per second, many of them for the same few hot keys, which is 10.14.2's stampede problem arriving at the worst possible moment.

The fixes, in the order I would apply them.

Never restart the whole cache at once. Restart nodes one at a time, so only a fraction of the key space is lost and the database sees a proportionate rather than total increase. If the cache is sharded with consistent hashing (10.6), losing one node of ten costs you ten percent of the hit rate, not all of it.

Warm before serving. Bring a new node up, populate it with the known hot set from a snapshot or by replaying recent keys, and only then add it to the rotation. Many teams already have the hot key list from their own metrics.

Put a concurrency limit in front of the database. A bounded pool (9.5.4) means the database receives the load it can handle and the rest queues or is rejected cleanly. A slow recovery is enormously better than a dead database, and this single change converts an outage into a degradation.

Deduplicate concurrent misses. When a hundred requests miss on the same key, only one should go to the database and the other ninety-nine should wait on its result. That is the single-flight pattern from 9.5.5, and during a cold start it is the difference between ten thousand queries and a few hundred.

Break the retry storm. Exponential backoff with jitter, plus a circuit breaker so clients stop hammering a database they already know is failing.

And the monitoring change that matters more than any of the fixes: alert on hit rate dropping, not on latency rising. Hit rate moves first and moves sharply, latency is the downstream symptom, and by the time latency alerts fire you are already in the incident rather than ahead of it.

InterviewWhy is deleting a cache key on write better than updating it? Give the failure case precisely.

Because updating can leave the cache permanently holding an older value than the database, and deleting cannot.

Here is the interleaving, step by step. Two writers update the same product. Writer A sets the price to £10, writer B sets it to £12.

1. A writes £10 to the database.
2. B writes £12 to the database. The database now correctly holds £12.
3. B writes £12 to the cache.
4. A writes £10 to the cache.

The database says £12 and the cache says £10, and nothing will ever fix it until the entry expires or is written again. The two writers did their database writes in one order and their cache writes in the other, which is entirely possible because the two operations are separate calls with independent timing — A may have been descheduled, or its cache node may have been briefly slower.

Now the same interleaving with delete.

1. A writes £10 to the database.
2. B writes £12 to the database.
3. B deletes the key.
4. A deletes the key.

The key is absent. The next reader misses, loads from the database, and gets £12, which is correct. No ordering of deletes can produce a wrong value, because a delete carries no data. That is the whole argument, and it is why "invalidate, do not update" is standard advice.

The remaining hole, which a strong answer names unprompted. There is still a race between a reader and a writer. A reader misses, loads £10 from the database, and is then descheduled. A writer updates to £12 and deletes the key. The reader wakes up and writes its stale £10 into the cache. Now the cache is wrong again.

This window is much narrower than the write-write one, and there are three standard responses. Keep a TTL so it self-corrects quickly. Delete the key a second time a short delay after the write, which is sometimes called delayed double delete and which covers readers that were in flight. Or, if the data genuinely cannot be stale, drive invalidation from the database's own change stream (10.8.4), so the invalidation is ordered by the same system that ordered the writes.

The general principle worth stating: an operation that carries no data cannot be applied out of order incorrectly. Wherever you can replace "write the new value into the second copy" with "mark the second copy invalid", you remove a whole class of ordering bugs.

StaffDesign the caching layer for an e-commerce product page end to end, and justify a different decision for each kind of data on it.

The point of this question is that a page is not one cache decision, it is six, and treating it as one is what produces either a stale price or a useless hit rate.

Product description, images, specifications. Changes maybe monthly. Read constantly. This is the ideal cache candidate: cache-aside, a TTL of an hour, delete on write from the admin tool. LRU eviction. The hit rate here will be very high because the hot set is small, and a stale description for a few minutes harms nobody.

Price. Read as often as the description and far less tolerant of staleness, because showing a price you will not honour is a legal and trust problem, not a performance one. Two options and I would name both. A very short TTL — five to ten seconds — is simple and bounds the exposure. Better, cache the price with explicit invalidation driven from the pricing service's change stream, so a price change propagates in milliseconds and the TTL is only a backstop. Either way the price is cached separately from the description, because their staleness budgets differ by three orders of magnitude, and combining them forces the whole page down to the price's TTL.

Stock level. The interesting one, because the instinct is to treat it like the price and that is wrong. Exact stock is not needed for the page; "in stock", "only 3 left", or "out of stock" is. So cache a derived, coarse value with a short TTL, and — this is the design point — never let the cached value be the thing that decides a sale. The purchase path reads the real stock with a conditional decrement (9.5.1). The cache is for display; the database is for truth. Conflating them is how a site oversells.

Reviews and ratings. Read-heavy, changes slowly, and expensive to aggregate. Cache the aggregate with a longer TTL and recompute on a schedule rather than on every write, because a new review shifting an average from 4.31 to 4.32 is not worth an invalidation.

Personalised recommendations. Per-user, so the key space is enormous and the repeat rate low. This is the one where caching may be actively harmful: a million users each with a distinct key will evict everything useful. Either do not cache it, or cache it in a separate namespace with its own memory budget so it cannot displace the shared hot set. Naming that isolation is worth a point, because sharing one cache between a small hot set and a large cold set is a classic self-inflicted wound.

The session and permissions. Session, yes — read-through with write-through, because it is read on every request and must be fresh. Permissions, no. A cached permission is a security bug with a delay on it, and the correct answer is that a revoked access must take effect immediately.

Two structural decisions on top of the six.

Cache the fragments, not the page. A fully assembled page has to be invalidated when any of its six inputs changes, which means it is invalidated constantly and its hit rate is poor. Caching each fragment separately means a price change invalidates the price and nothing else. The composition cost is small; the hit-rate difference is large.

Put a short-lived local cache in front of the shared one. One or two seconds in process memory absorbs the repeated reads within a single burst and takes the pressure off the shared cache's hot keys. The cost is that two servers can briefly disagree by a second, which is acceptable for everything on this list except price — so the price fragment skips the local layer, and saying that explicitly is the difference between a design and a diagram.

Flashcards

FlashThe three independent choices

Read pattern (cache-aside or read-through) · write pattern (through, around, behind) · eviction policy (LRU, LFU, sketch). Naming all three answers "which caching strategy".

FlashDelete, don't update

Two concurrent cache writes can land in the opposite order to their database writes, leaving the cache permanently stale. A delete carries no data, so it cannot be applied wrongly out of order.

FlashExpiry versus eviction

Expiry = too old to trust (correctness). Eviction = cache is full (capacity). Need both: expiry alone runs out of memory, eviction alone serves stale data forever.

FlashLRU versus LFU

LRU matches real access and is wiped by a scan. LFU resists scans and never forgets without ageing. Modern caches use a frequency sketch to decide if a new arrival deserves to displace LRU's victim.

FlashHit rate is capacity

At 10k rps, 95% → 90% hit rate doubles database load. Alert on hit rate dropping, not latency rising — hit rate moves first.

FlashNever cache

Permission checks, balances at the moment of transfer, stock at the moment of sale. If two seconds of wrongness is unacceptable, the answer is no cache, not a shorter TTL.