ChannelPulse
System design · The method — requirements, arithmetic, storage, caching

Caching, eviction, and stampedes

A cache is the cheapest way to hit a latency target and the easiest way to invent a new outage. This is where the caching patterns actually differ, why a stampede is arithmetic rather than bad luck, and the access pattern that separates LRU from LFU.

19 min read Free to read Patterns: cache-aside, single-flight, ttl-jitter

What you'll be able to do

Before this: picking-a-datastore

Two lessons ago the arithmetic said something specific: at a 99% hit rate, the database sees roughly 460 reads a second instead of 46,000. The entire read-scaling problem was solved by one component.

Which means the entire read path now depends on that component behaving. And caches have a particular failure personality: they work beautifully until a moment when they all stop working at once, and that moment is usually the moment traffic is highest. This lesson is about the four ways a cache is wired in, and the three ways the wiring goes wrong.

WatchprogrammerCave · 08:11

Eight minutes on the system where caching stops being an optimisation and becomes the architecture. Watch it here for the caching and fan-out material — what gets precomputed, what gets read through, and why the answer differs for an ordinary account and a very large one. The whole video is cued again in the news-feed case at the end of this track. No chapter markers.

The four patterns, by what each one sacrifices

The patterns are usually presented as a list to memorise. They are much easier to remember as answers to a single question: when a write happens, who writes to the cache, and does the user wait for it?

The read path a cache sits in
Client
App server
Cache
Origin database
where the request is now

Four hops, and the whole table below is about which of them a write has to touch. Cache-aside and read-through leave the write at the origin and let the next read repopulate; write-through makes the write travel all four; write-behind acknowledges at the cache and travels the last hop later. Follow the marker to the right and you are watching a miss — the slow path, which is the one worth putting a number on.

PatternWho fills the cacheOn writeSacrifices
Cache-asideThe application, on a missInvalidate (or update) the keyEvery first read is slow; app carries the logic
Read-throughThe cache itself, on a missInvalidate the keySame cold-miss latency, hidden in the cache layer
Write-throughOn write, synchronouslyWrite cache and origin before ackWrite latency: you pay both stores per write
Write-behindOn write, asynchronouslyWrite cache, ack, flush to origin laterDurability: an ack'd write can be lost

Cache-aside is the default, and should be your default answer, because the failure mode is the mildest: if the cache is down, every read is a slow read, but every read still works. That property is worth more than it sounds. A read-through cache sitting in the data path can take the whole read path down with it.

Write-through is what you reach for when a stale read is genuinely unacceptable and you are willing to pay for it on every write. Note what it does not give you: it is not transactional. The cache write and the origin write are two operations, and the process can die between them.

Write-behind is the one to propose carefully. It makes writes very fast by acknowledging before the data is durable, which is a real technique in metrics pipelines and view counters and a genuinely bad idea for anything a user would notice losing. If you propose it, name the data: "click counts can go write-behind — losing a few seconds of counter increments in a crash is acceptable. The link mapping itself cannot."

Invalidate, don't update

That last point deserves its own section because it is the single most common correctness bug in cached systems.

If two requests update the same row and both then write their new value into the cache, the writes can interleave: A writes the row, B writes the row, B writes the cache, A writes the cache. The cache now holds A's value, the database holds B's, and nothing will ever correct it. The value is wrong until the TTL expires — and if you were pleased with yourself for setting a long TTL, it is wrong for a long time.

Invalidation does not have this failure. DELETE key is idempotent, order-insensitive, and its worst outcome is a cache miss. Pay the miss.

A stampede is arithmetic

The classic cache outage: one very popular key expires, and every request that arrives before the first one finishes recomputing also misses, and all of them go to the origin together. This is usually described as a thundering herd, which makes it sound like weather. It is a multiplication.

JavaScript
// A stampede is arithmetic, not bad luck: it is however many requests arrive
// while the origin is still computing the value nobody has cached yet.
const RPS_FOR_KEY = 5_000;   // requests/s for one very popular key
const ORIGIN_MS = 80;        // how long the origin takes to build the value

const inflight = Math.round((RPS_FOR_KEY * ORIGIN_MS) / 1000);
console.log("arrive during one origin fetch :", inflight.toLocaleString("en-US"));
console.log("naive cache-aside origin calls :", inflight.toLocaleString("en-US"));
console.log("with single-flight             :", 1);
console.log("amplification avoided          :", inflight + "x");

// Now the version that takes the whole site down: many keys sharing a TTL.
const KEYS = 10_000;
const TTL_S = 300;
console.log("");
console.log("--- 10 K keys, 300 s TTL ---");
// All warmed by the same deploy => all expire in the same second.
console.log("same-instant expiry, worst second:", KEYS.toLocaleString("en-US"), "origin calls");
// Jitter the TTL over +/-10% and the same keys spread over 60 seconds.
const jitterWindow = 2 * 0.1 * TTL_S;
console.log("with +/-10% jitter, worst second :", Math.ceil(KEYS / jitterWindow).toLocaleString("en-US"), "origin calls");

Both halves of that cell are worth saying out loud in a round.

One key, 400× amplification. The fix is single-flight: the first request to miss takes a lock on the key; the rest wait for its result instead of duplicating its work. One origin call serves all four hundred. This is a small amount of code and it removes an entire class of outage.

Ten thousand keys, one shared expiry second. This is the failure that actually takes sites down, and it is caused by something innocent: a deploy, or a cache flush, warms every key at the same instant, so with a fixed TTL they all expire at the same instant too. The fix is smaller than the fix for the first problem — add random jitter to each TTL — and the cell shows the effect: ten thousand simultaneous origin calls become a steady trickle, because the same expiries are now spread across a window instead of stacked in one second.

There is a third technique worth naming for keys that are both expensive and permanently hot: recompute early. Rather than waiting for expiry, refresh the value in the background when it is, say, 90% of the way through its TTL. The hot key then never expires under load at all, and the stampede cannot happen because there is never a moment when the value is missing.

Eviction: the workload where LRU is wrong

When the cache is full, something has to go. LRU — evict the least recently used — is the default nearly everywhere, and for good reason: it is cheap, it needs no tuning, and it matches how most access patterns behave.

It has one well-known blind spot, and it is a blind spot you can trigger by accident with a nightly batch job. A big sequential scan touches thousands of keys exactly once. Every one of them is "recently used" the moment it is read, so LRU dutifully evicts the genuinely hot data to make room for keys that will never be requested again.

JavaScript
// LRU vs LFU on the access pattern that separates them: a small hot set, plus a
// batch job that scans a large cold key space once.
const CAPACITY = 100;

class LRU {
  constructor(cap) { this.cap = cap; this.m = new Map(); this.hits = 0; this.misses = 0; }
  get(k) {
    if (this.m.has(k)) { const v = this.m.get(k); this.m.delete(k); this.m.set(k, v); this.hits++; return; }
    this.misses++;
    if (this.m.size >= this.cap) this.m.delete(this.m.keys().next().value);
    this.m.set(k, 1);
  }
}

class LFU {
  constructor(cap) { this.cap = cap; this.m = new Map(); this.hits = 0; this.misses = 0; }
  get(k) {
    if (this.m.has(k)) { this.m.set(k, this.m.get(k) + 1); this.hits++; return; }
    this.misses++;
    if (this.m.size >= this.cap) {
      let worst = null, low = Infinity;
      for (const [key, freq] of this.m) if (freq < low) { low = freq; worst = key; }
      this.m.delete(worst);
    }
    this.m.set(k, 1);
  }
}

// Deterministic pseudo-random so this cell prints the same thing every run.
let seed = 42;
// Math.imul, not *, because the product exceeds 2^53 and a plain multiply
// would silently lose the low bits a generator depends on.
const rnd = () => (seed = (Math.imul(seed, 1103515245) + 12345) & 0x7fffffff) / 0x7fffffff;

const workload = [];
for (let round = 0; round < 20; round++) {
  for (let i = 0; i < 500; i++) workload.push("hot:" + Math.floor(rnd() * 50));  // hot set of 50
  if (round === 10) for (let i = 0; i < 5_000; i++) workload.push("scan:" + i);  // the batch job
}

const lru = new LRU(CAPACITY), lfu = new LFU(CAPACITY);
for (const k of workload) { lru.get(k); lfu.get(k); }

const rate = (c) => ((c.hits / (c.hits + c.misses)) * 100).toFixed(1) + "%";
console.log("requests :", workload.length.toLocaleString("en-US"));
console.log("LRU hit  :", rate(lru), `(${lru.hits.toLocaleString("en-US")} hits)`);
console.log("LFU hit  :", rate(lfu), `(${lfu.hits.toLocaleString("en-US")} hits)`);

// The interesting part: what happened to the hot set right AFTER the scan.
const after = workload.length - 500 * 9;
const l2 = new LRU(CAPACITY), f2 = new LFU(CAPACITY);
workload.slice(0, after).forEach((k) => { l2.get(k); f2.get(k); });
const [lh, fh] = [l2.hits, f2.hits];
workload.slice(after, after + 500).forEach((k) => { l2.get(k); f2.get(k); });
console.log("");
console.log("first 500 hot reads after the scan:");
console.log("  LRU:", l2.hits - lh, "hits /500");
console.log("  LFU:", f2.hits - fh, "hits /500");

Read the two halves of that output against each other, because the disagreement between them is the actual lesson.

The aggregate hit rates are almost identical — the scan is a small fraction of a long workload, so averaging over the whole run hides its effect almost completely. If your only instrument were a dashboard showing overall hit rate, you would conclude the policies were interchangeable.

The window right after the scan tells the truth. LRU takes exactly fifty misses there — one for each key in the hot set, because the scan evicted every one of them and each has to be faulted back in. LFU takes none: the hot keys have high frequency counts, so when the cache filled, the scan's once-touched keys were the ones evicted instead.

The practical answer is usually neither pure policy. Real caches offer variants that split the difference — Redis ships approximated-LRU and LFU policies precisely because exact LRU costs memory for bookkeeping that is better spent on data, and its documentation is explicit that the approximation is a deliberate accuracy-for-memory trade. Segmented approaches keep a probation area so a one-hit key cannot evict an established one. The interview-grade answer is to name the workload that breaks LRU, say that you would use an LFU or segmented policy if scans are part of the traffic, and add the operational fix that costs nothing: point the batch job at a read replica so it never touches the cache at all.

What to say about caching in a round

Compressed to the four sentences that carry the signal:

  1. Cache-aside, invalidate on write. The mildest failure mode, and an idempotent invalidation instead of a racy update.
  2. Single-flight the misses, jitter the TTLs. One sentence each, and between them they remove the two stampede failure modes.
  3. Name what the cache is allowed to lose. A cache holding the only copy of something is not a cache, it is an unreplicated database.
  4. Say what happens when it's down. "Reads fall through to the database, which at a 99% hit rate means fifty times the read load — so I'd shed non-essential reads and keep the redirect path alive." A candidate who has thought about the cache being gone is demonstrably rarer than one who has thought about it being full.

That fourth point is where this module ends and the rest of the track begins. You have a method, numbers, a datastore chosen for a reason, and a cache whose failure modes you can name. What comes next is the set of mechanisms those numbers keep demanding — replication and quorums, partitioning, queues, and the specific case studies where all of it gets assembled under time pressure.