Caching fundamentals

Every cache is the same bet, made at a different distance

A cache exists because of exactly one wager: this answer will be asked for again before it changes. Every caching layer in every architecture is that same bet — the layers differ only in how far from the user the copy sits, who pays when the bet is wrong, and how hard it is to take the copy back. Interviewers ask about caching constantly, not because inserting a Redis is hard, but because it is the fastest way to find out whether you reason about a system in rates and distributions or in adjectives. A candidate who says "we'll add a cache" and a candidate who says "at a 90% hit rate this still sends 50k reads a second to the primary, so 90% isn't the goal" are two very different hires.

What each layer actually buys you

The buffer pool is the layer candidates forget exists, and it changes the conversation. A Postgres box with 64 GB of RAM and a 40 GB hot set is already serving nearly every read from memory. Adding Redis in front of it does not save you a disk seek — it saves you connection setup, query parsing, planning, MVCC visibility checks and result serialisation. That is often still a several-fold latency win (workload-dependent; measure it), but say why, because "the database reads from disk" is frequently wrong and an interviewer who runs databases will notice.

Read strategies: cache-aside vs read-through

Cache-aside (also "lazy loading") puts the application in charge: ask the cache, and on a miss go fetch and populate it yourself. This is the one you will be asked to write on a whiteboard, so write it well — the three-line version everyone produces has three real bugs in it.

async function getUser(id) {
  const key = `user:v3:${id}`;                // v3 = payload schema version; see invalidation
  const hit = await redis.get(key);

  // null is the miss signal. Test for it explicitly. The classic bug is testing
  // the *deserialised* value for truthiness (or a client that returns raw
  // values): a legitimately cached 0, "" or false then looks like a miss.
  if (hit !== null) return JSON.parse(hit);

  const row = await db.users.findById(id);    // the miss path — the expensive part

  if (row === null) {
    // Negative caching. Without it, a scraper hitting nonexistent ids
    // passes straight through the cache into the database, every time.
    await redis.set(key, "null", "EX", 30);
    return null;
  }

  // Jittered TTL: 300 s ± 30. A million keys populated in the same minute
  // must not expire in the same second. This one line prevents avalanche.
  const ttl = 300 + Math.floor(Math.random() * 61) - 30;
  await redis.set(key, JSON.stringify(row), "EX", ttl);
  return row;
}

Note what this function does not do: it never writes to the cache on the write path. The write path deletes the key and lets the next read repopulate it. That asymmetry is deliberate and we'll see why in the invalidation section.

Read-through moves that same logic behind the cache client, so the application only ever talks to the cache and the cache knows how to load a miss. Cleaner code, one place to implement coalescing and metrics — but the cache is now on the critical path for correctness, not just speed. With cache-aside, Redis being down can degrade to slow, because the application can fall through to the database; with read-through, Redis being down means down unless the cache layer itself has a bypass. But "degrades to slow" only holds while the database can absorb the full read load, and at a 99% hit rate it usually cannot (see the node-loss box below). So the real answer when an interviewer asks which you'd pick is: cache-aside gives you the option of failing open, and you still need load shedding to make that option survivable.

Write strategies, and when each is right

Write-behind is the one worth volunteering. A "like" counter taking 50k increments a second is 50k row updates a second with lock contention on a single hot row — a database will simply refuse. Buffer the increments in Redis, flush the delta every second, and 50k writes become one. You have traded "we might lose the last second of counts if a Redis node dies" for a 50,000× reduction in write load, and for a like counter that is obviously the right trade. Say the trade out loud; that is the whole point of the answer.

Eviction: what happens when memory runs out

TTL is expiry — the entry becomes invalid at a known time. Eviction is what the cache does when it is full and someone wants to write anyway. They are different mechanisms and conflating them is a tell.

Two implementation details worth knowing because they get asked. First, Redis does not implement true LRU: it samples a handful of keys (maxmemory-samples, default 5) and evicts the least recently used of the sample. Redis's docs describe it as a close approximation of true LRU (a sample size of 10 gets very close, at some extra CPU), and minimal or no difference on power-law access, for much less bookkeeping memory. It is a nice example of the approximate-is-fine reasoning these systems are built on. Second, Redis LFU counters are 8-bit probabilistic counters with logarithmic increment and time-based decay — you cannot store a true frequency for a billion keys, so you store something that ranks them well enough and costs one byte.

Dry run: an LRU cache, capacity 3, through five operations

Step 5 is the whole policy in one row: b was the least recently touched, not the oldest — a was inserted before it but survives because a hit re-promotes it. LRU tracks recency of access, not age, which is exactly why it breaks on a single cold scan: a query that touches a million rows once each promotes all of them ahead of your actually-hot keys.

Invalidation is hard, and here is exactly why

"There are two hard things in computer science" is a joke everyone repeats and almost nobody unpacks. The concrete reason is this: there is no transaction that spans your cache and your database. They are two independent systems, so any two operations against them can interleave, and one specific interleaving is permanently damaging.

Once you can draw that, the practical patterns stop being folklore and become answers to a specific question — how long can a stale entry survive?

• TTL. The honest answer. It does not prevent staleness, it bounds it. A 60-second TTL means the worst case above resolves in at most 60 seconds. Most systems are correct because of TTL, not because of clever invalidation, and saying so is a sign of experience rather than a concession.
• Delete, never update. On write, DEL the key; do not compute the new value and SET it. Two concurrent writers who both SET can land in either order and the loser's value sticks. Two concurrent writers who both DEL converge on "empty", and the next read repopulates from the committed source of truth.
• Versioned keys. The strongest pattern. Never mutate an entry — put the version in the key: user:42:v17, where 17 comes from a row counter, an ETag, or the row's updated_at. A write bumps the version, so new readers ask for a key nobody has written stale data into. The race above becomes harmless provided readers learn the current version from an authoritative source: A's stale SET lands on v16, which no reader asks for once they know the current version is 17. The catch is that "learn the current version" is itself a read of authoritative state (a cheap version-column or ETag lookup). If you cache that version pointer, you have moved the staleness problem up one level rather than removed it. Old entries cost memory until eviction reaps them.
• Explicit purge / surrogate keys. What CDNs give you: tag a response product:42 and purge every edge copy carrying that tag in one call. Essential at the CDN layer, but remember purge is itself a distributed system — it is fast on modern CDNs (sub-second to a few seconds) and it can still fail or lag.
• CDC-driven invalidation. Tail the database's write-ahead log (Debezium and friends) and emit invalidations from there. This is the only approach where invalidation is derived from committed state, in commit order, with no dual write. It costs you a pipeline; buy it when correctness matters more than simplicity. The principle behind it: treat the cache as derived data built from one authoritative write, not as a second place you also write (a dual write, which can diverge on any partial failure).
• Leases. Facebook's memcache fix for exactly the race above: a miss returns a lease token to the one reader allowed to repopulate, and a delete invalidates outstanding tokens, so the stale SET from reader A is rejected. The same token rate-limits stampedes (see the Facebook paper in the sources).

Thundering herd, and the five ways to stop it

A single key serving 50,000 requests a second expires. Recomputing it takes 20 ms. In that window 50,000 × 0.020 = 1,000 requests all miss, all decide independently to recompute, and all hit the database with the same query at the same instant. The database was comfortably serving one query per five minutes for that key; it now gets a thousand at once. Nothing was misconfigured. The cache working correctly produced the outage.

const inflight = new Map();                    // key → Promise, per process

function coalesce(key, loader) {
  const existing = inflight.get(key);
  if (existing) return existing;               // 999 callers join the same promise

  // finally() matters: on rejection the entry must clear, or one
  // transient error is cached as a permanent failure for that key.
  const p = loader().finally(() => inflight.delete(key));
  inflight.set(key, p);
  return p;
}

Be precise about the scope of that fix: it coalesces within one process. With 40 app servers you have gone from 1,000 queries to 40, which is usually enough. If it isn't, the cross-process version is a SET key NX EX 10 lock in Redis — one winner recomputes, the losers either wait briefly or serve the stale value — and you should say out loud that you have just introduced a distributed lock, with the lease expiry and fencing questions that come with it.

The probabilistic version is worth naming precisely because it sounds like an invented answer otherwise. XFetch: store how long the last recompute took as delta, and on every read refresh early if now − delta × beta × ln(random()) ≥ expiry, with beta around 1. Expensive-to-compute entries and entries close to expiry refresh sooner, probabilistically, so exactly one unlucky reader usually does the work before anyone has to wait for it (the technique is from Vattani et al., VLDB 2015, linked below).

Vocabulary you will hear, and which failure each word names: penetration is requests for keys that never exist (fix: negative caching, a Bloom filter); breakdown is one hot key expiring (fix: coalescing, refresh-ahead); avalanche is many keys expiring together, or the whole cache tier going away (fix: jittered TTLs, replicas, a gutter pool, load shedding). Two more operational notes: a freshly started or flushed cache is a 0% hit-rate cache, so warm it from replayed traffic or ramp traffic onto it gradually rather than cutting over cold; and a cache tier is a single point of failure unless you have sized the database for its absence.

Hit-rate arithmetic: why 90% is not a good number

This is the section that wins interviews, because almost nobody does the arithmetic. Take a read tier serving 500,000 reads/sec, backed by replicas that each sustain about 20,000 simple indexed point reads/sec. That is this course's conservative planning figure, not a limit: strong hardware does several times more, and OpenAI runs ChatGPT on one Azure PostgreSQL primary plus nearly 50 replicas at millions of aggregate queries per second. Measure your own.

Going from 90% to 99% is described in conversation as "nine percentage points". In load terms it is a 10× reduction and it takes you from three replicas to one. Going the other way is worse: a hit rate slipping from 99% to 98% doubles database load overnight, and no dashboard labelled "cache hit rate 98%" looks alarming. Always reason in miss rate. Hit rate is a vanity metric; miss rate is the thing that is actually multiplied by your traffic.

The same arithmetic explains the latency shape. With a 0.5 ms cache and a 20 ms database:

• 99% hit: mean = 0.99 × 0.5 + 0.01 × 20 = 0.695 ms
• 90% hit: mean = 0.90 × 0.5 + 0.10 × 20 = 2.45 ms — 3.5× worse from a number that "sounds fine"
• And the percentile that matters: at a 10% miss rate, every request above p90 is a cache miss by definition. Your p95 and p99 are not "the cache is a bit slower sometimes" — they are raw database latency, including its tail. At a 99% hit rate the miss tail begins exactly at p99, so p99 sits on the boundary between cache and database latency; you need roughly a 99.9% hit rate before p99 is a pure cache hit and only p99.9 is the database.

Sizing follows the same logic in reverse. Hit rate is a function of how much of the working set fits in memory, and real access distributions are Zipf-ish: often roughly the top 20% of keys serve 80% of requests. That means the first gigabyte buys you an enormous amount and the climb from 90% to 99% can cost several times the memory (workload-dependent; this is an illustrative shape, not a measured constant), because you are now paying to hold the long tail. Knowing where you are on that curve is what makes "should we double the cache?" a calculable question rather than an argument.

Recognizing it in an unseen problem

• Any prompt with a heavy read:write skew (news feed, product catalogue, URL shortener, profile service) is a caching problem before it is a database problem. State the ratio, then state the miss rate you're targeting and the load that leaves — do not just say "add Redis."
• A naive design adds a cache and stops there: no TTL policy, no invalidation story, no eviction policy, no stampede protection, and no answer for what happens when a cache node dies. Each of those is a follow-up question the interviewer already has queued.
• Distinguish caching from replication: a read replica is authoritative and eventually consistent; a cache is non-authoritative and arbitrarily stale. If the prompt needs "must reflect the last write", a replica with read-your-writes routing is the answer, not a cache.
• Distinguish it from a CDN question: if the payload is large, static and geographically distributed, the win is bandwidth and RTT at the edge, not query offload. Different layer, different invalidation story, same bet.
• Hot-key language ("a celebrity posts", "a flash sale", "one video goes viral") is the interviewer explicitly asking for stampede handling and hot-key mitigation — coalescing, a per-instance L1 in front of the shared tier, key splitting, or replicating the one hot key across several cache nodes so no single node carries it.
• Pitfall: caching writes. If the prompt is write-heavy or the data is read once and never again, a cache adds latency and memory cost for nothing. Say "I would not cache this, and here's why" at least once during a loop — knowing where a cache does not belong reads as strongly as knowing where it does.