Lesson 5: Caching: Cache-Aside, TTL & Invalidation

Lesson 4 finished building the entry layer. From here on we move to what sits behind it, and the first thing we run into is the layer with the best benefit-to-effort ratio in the whole series: caching. This lesson's lab measures 26.5x throughput and a 20x drop in p99 just from turning on caching for one hot key.

But the part actually worth learning isn't that number — it's too easy to predict. Three things are more surprising: dropping the hit ratio from 99.45% to 95.47% (just four percentage points) makes p99 jump from 4.46 ms to 42.11 ms while p50 barely moves at all; single-flight — the classic defense against thundering herd — makes p50 and p99 slightly worse, not better; and jitter on the TTL doesn't cut a single database query, yet still raises throughput by 31%.

5.1 Why caching wins, and by how much

Lesson 1 built the latency order-of-magnitude table. What caching exploits is exactly the gap between two rows in that table: reading from RAM costs hundreds of nanoseconds, while a database query over the network costs milliseconds — roughly a 10,000x gap. Caching doesn't make the database faster; it makes most requests never have to ask it at all.

The average latency of a layer with a cache:

$$T = h \cdot T_{cache} + (1-h) \cdot T_{db}$$

where $h$ is the hit ratio. Plugging in the lab's numbers ($T_{cache} \approx 1.4$ ms, $T_{db} \approx 43$ ms), $h = 0.9$ gives $T \approx 5.6$ ms, and $h = 0.99$ gives $T \approx 1.8$ ms. But this formula hides the part that matters more. The number of database queries the system generates is:

$$Q = (1-h) \cdot N$$

Meaning database load depends on $(1-h)$ — the part that doesn't hit. Going from $h = 90\%$ to $h = 99\%$ sounds like "a 9-point improvement", but $(1-h)$ goes from $0.1$ down to $0.01$: database load drops 10x. One more 9, up to $99.9\%$, and it drops another 10x. Every 9 you add to the hit ratio divides database load by 10.

This isn't paper reasoning. I swept the working-set size (the number of distinct keys traffic touches) and measured the real hit ratio and real database query count:

The third column matches the formula digit for digit: $1 - 0.9992 = 0.0008$, $1 - 0.9547 = 0.0453$, $1 - 0.2380 = 0.7620$. The formula $Q = (1-h) \cdot N$ isn't an approximation — it's the definition of hit ratio written a different way.

But the surprising row is the third one. Going from 99.45% to 95.47% is only four percentage points, and p50 barely even moves (1.54 → 1.48 ms). Meanwhile p99 jumps from 4.46 ms to 42.11 ms — a 9.4x jump. Exactly Lesson 1's lesson: the average hides the tail, and the tail is what the user feels.

5.2 Cache patterns: who writes where, in what order

Every cache pattern answers two questions: whose job is it to load the cache on a miss, and on a write, does the cache or the database get written first. That's the entire difference between the patterns.

Cache-aside in the lab, exactly as the code that's actually running:

const cacheKey = `demo:${key}`;

let hit = null;
try {
  hit = await redis.cmd('GET', cacheKey);
} catch {
  // IMPORTANT: if Redis is down, the app must still serve the request. The cache is
  // a SPEED-UP, not a hard dependency. Catching the error here is exactly the
  // difference between "the system got slower" and "the system fell over" (Lesson 17).
  hit = null;
}
if (hit !== null) {
  cacheHits++;
  return json(res, 200, { ...JSON.parse(hit), from: 'cache' });
}

cacheMisses++;
const fresh = await readFromDb(key);
try {
  // SET ... EX: always set a TTL. A key with no TTL lives forever, and by the time
  // the underlying data changes nobody remembers where to delete it from.
  await redis.cmd('SET', cacheKey, JSON.stringify(fresh), 'EX', String(ttl));
} catch {
  // Couldn't write the cache — ignore it, don't fail the request over that.
}
return json(res, 200, fresh);

5.3 Cache invalidation — the hardest part

Loading the cache is easy. The hard question is: when the source data changes, how does the cached copy know to go away? Three ways, from simplest to cleanest:

A versioned key is usually the cleanest solution, because it turns a synchronization problem (delete at exactly the right time, in exactly the right place) into a naming problem:

// EXPLICIT DELETE: you have to remember every related key. Miss one line and you get
// the bug "I fixed it but the page still shows the old number" — a bug that's very
// hard to reproduce.
async function updateProductOld(id, data) {
  await db.update(id, data);
  await redis.del(`product:${id}`);
  await redis.del(`product:${id}:reviews`);
  await redis.del(`category:${data.categoryId}:products`);   // easy to forget this line...
  await redis.del(`search:featured`);                        // ...and this one
}

// VERSIONED KEY: delete nothing. Bump the version, and EVERY derived key changes with
// it. Old keys turn into garbage nobody reads, and vanish on their own once their TTL
// expires or they get evicted.
async function updateProductNew(id, data) {
  await db.update(id, data);
  // INCR is atomic in Redis => safe even when multiple replicas write at once.
  await redis.cmd('INCR', `ver:product:${id}`);
}

async function readProduct(id) {
  const v = (await redis.cmd('GET', `ver:product:${id}`)) || '0';
  return cacheAside(`product:${id}:v${v}`, () => db.read(id));
}

Synchronized TTLs, and what jitter does about it

If many keys get loaded at nearly the same time — this happens on every deploy, every time the cache gets flushed, every time you scale up a replica — and they all share the same TTL, they'll expire in one batch. The fix is to add a random amount to the TTL:

// TTL 5s with jitter 0.6 => every key gets a random TTL somewhere in [2s, 8s].
// The expected value is still 5s, but the expiry moments get SPREAD OUT instead of
// piling up at one point.
function ttlWithJitter(baseSec, ratio) {
  if (!(ratio > 0)) return baseSec;
  const delta = baseSec * ratio * (Math.random() * 2 - 1);
  return Math.max(1, Math.round(baseSec + delta));
}

Real measurement: 300 keys, base TTL 5 seconds, 32 connections, 30 seconds, database pool 2 connections/replica, single-flight on in both configurations, three repeats each:

Throughput went up 31% and the average database queue wait nearly halved. But look at the last row: database queries per request stayed almost exactly the same (0.0105 vs. 0.0102). Jitter doesn't reduce the amount of work at all — it just spreads that work out over time. The queue got shorter not because there was less work, but because the work stopped arriving all at once.

5.4 Thundering herd — and a counter-intuitive measurement

A hot key expires. At that exact moment, $N$ requests are asking for it. All $N$ see a miss, all $N$ call the database. The database receives $N$ identical queries at once for exactly one piece of data — that's thundering herd (also called cache stampede).

The worst case is a self-closing loop: the herd overloads the database, the overload slows down requests, the slowdown means nobody gets around to writing the cache back, the empty cache means the next batch of requests becomes another herd. The system can't recover on its own even though the original trigger was just one key expiring.

The first measurement showed nothing at all

I set up an experiment: one hot key, TTL 1 second, 100 connections, 15 seconds. Without single-flight there were 1,600 database queries; turning it on brought that down to 54 — 30x fewer. But latency didn't change at all: the p50, p95, and p99 of both configurations matched within run-to-run noise.

The reason: the lab's "database" at that point had a pool of 10 connections per replica, i.e. 30 concurrent queries, each taking 40 ms — a capacity of roughly 750 queries/second. The herd generated about 89 queries per expiry. It never even touched that limit. The herd was real, measurable in query count, but it never caused any damage.

So I shrank the pool down to 2 connections per replica — a database under real pressure, which is exactly the normal state during an incident. Same experiment, three repeats:

One thing worth explaining before you read on: the "No single-flight" database-query count here (1,100) is lower than the 1,600 measured in the pool=10 experiment above, despite being the same herd scenario. That's not because the herd got smaller — the load generator runs in closed-loop mode (covered in Lesson 2): each connection only sends its next request after receiving a response, so when a narrower pool makes every request wait longer, fewer requests complete within that same 15 seconds, which means fewer misses and fewer database queries. The 1,600 and 1,100 come from two experiments with different pools, not one single measurement.

Read this table carefully. Single-flight cuts database queries by 20x, wipes out the queue entirely (depth 33 down to 0, wait 312 ms down to 0), and cuts the max latency from ~730 ms down to ~66 ms — 11x.

But p50 and p99 got slightly worse: p50 from 5.00 up to 5.57 ms, p99 from 13.17 up to 14.02 ms. If I'd only measured p50 and p99 — the exact two metrics most dashboards show — the conclusion would have been "single-flight doesn't help, it's even slightly harmful", and I would have thrown it away.

The single-flight implementation, exactly the code running in the lab:

const inFlightLoads = new Map();

function singleFlight(key, loader) {
  const pending = inFlightLoads.get(key);
  if (pending) return pending;              // join the load that's already in flight

  // MUST delete from the map inside `finally`. Otherwise one failure leaves the key
  // stuck forever with a rejected promise, and EVERY later request gets that same error.
  const promise = loader().finally(() => inFlightLoads.delete(key));
  inFlightLoads.set(key, promise);
  return promise;
}

// Used on the read path:
const fresh = useSingleFlight
  ? await singleFlight(cacheKey, load)
  : await load();

Three anti-herd mechanisms, and when to use each:

The first two mechanisms defend against different problems and don't substitute for each other — that's why the lab turns both on at once in the jitter measurement in section 5.3.

5.5 Eviction and cache key design

A cache is always smaller than the source data, so something eventually has to go. Redis decides what to drop using maxmemory-policy, and this choice changes system behavior far more than its size suggests:

The lab's Redis deliberately sets maxmemory 64mb with allkeys-lru so you can trigger eviction yourself and watch it happen. Once memory runs out, INFO stats tells you how many keys got dropped:

docker compose --profile cache up -d

# Push a very large key space to blow past 64mb, then see how many keys Redis dropped
docker compose run --rm loadgen loadgen.js \
  --url "http://lb:8080/cached?ttl=300" -c 32 -d 20 --key-space 200000

docker compose exec redis redis-cli INFO stats | grep evicted_keys
docker compose exec redis redis-cli INFO memory | grep -E 'used_memory_human|maxmemory_human'

# Key count and hit ratio as seen by Redis itself (different from the app-side hit ratio)
docker compose exec redis redis-cli DBSIZE
docker compose exec redis redis-cli INFO stats | grep keyspace

A badly designed key makes the cache useless

The most expensive pitfall in this lesson isn't picking the wrong eviction policy — it's getting the key wrong. If the key contains something that changes on every request, every request creates a new key: the cache writes constantly, never reads anything back, hit ratio sits near 0 — and it still "works", with no error at all.

// ===== BAD: a new key on every request, hit ratio ~ 0 =====
`page:${req.url}`                     // includes ?utm_source=... => each share creates a new key
`user:${id}:${Date.now()}`            // timestamp => never matches
`search:${JSON.stringify(filters)}`   // property order varies => key differs for the same filters
`cart:${sessionId}`                   // one key per session => the cache serves exactly one person

// ===== GOOD: keep only what ACTUALLY decides the result =====
const CACHE_PARAMS = ['page', 'sort', 'category'];   // allowlist, not a blocklist

function cacheKeyFor(url) {
  const u = new URL(url, 'http://x');
  const parts = CACHE_PARAMS
    .filter((k) => u.searchParams.has(k))
    .sort()                                    // SORT: ?a=1&b=2 and ?b=2&a=1 must map to the same key
    .map((k) => `${k}=${u.searchParams.get(k)}`);
  return `page:${u.pathname}|${parts.join('&')}`;
}

// cacheKeyFor('/products?utm_source=fb&sort=price&page=2')
//   -> 'page:/products|page=2&sort=price'      utm_* dropped, order normalized

Two more problems worth knowing by name. Hot key: one key gets hit so hard it skews load onto a single Redis shard — every other shard sits idle while one is overloaded; the fix is to replicate that key into several copies (hot:v1#0…hot:v1#7) and pick one at random on each read. Cache pollution: a cold-data scan (a report job, a backup, a bot) pushes all the hot data out of the cache — LFU tolerates this better than LRU, or you route the scan down a path that skips the cache entirely.

Reproducing the measurements yourself

cd blog/sysdesign/sysdesign-lab
docker compose --profile cache up -d

# --- Section 5.1: no cache vs. a hot cache ---
docker compose exec redis redis-cli flushall && ./tools/cache-stats.sh reset
docker compose run --rm loadgen loadgen.js --url "http://lb:8080/uncached?key=hot" -c 32 -d 10 -w 3 --json
./tools/cache-stats.sh

docker compose exec redis redis-cli flushall && ./tools/cache-stats.sh reset
docker compose run --rm loadgen loadgen.js --url "http://lb:8080/cached?key=hot&ttl=300" -c 32 -d 10 -w 3 --json
./tools/cache-stats.sh

# --- Section 5.4: thundering herd. MUST shrink the DB pool to 2 first, otherwise you
# --- will see exactly the surprise I ran into: 30x more queries with latency unchanged.
# Change DB_MAX_CONCURRENCY to '2' in docker-compose.yml, then:
docker compose --profile cache up -d --force-recreate app1 app2 app3

docker compose exec redis redis-cli flushall && ./tools/cache-stats.sh reset
docker compose run --rm loadgen loadgen.js --url "http://lb:8080/cached?key=hot&ttl=1" -c 100 -d 15 -w 3 --json
./tools/cache-stats.sh                    # check dbQueries + queue depth

docker compose exec redis redis-cli flushall && ./tools/cache-stats.sh reset
docker compose run --rm loadgen loadgen.js --url "http://lb:8080/cached?key=hot&ttl=1&flight=single" -c 100 -d 15 -w 3 --json
./tools/cache-stats.sh                    # compare: dbQueries, qDepth, and the MAX latency

Summary

Database load is proportional to $(1-h)$, so every 9 you add to the hit ratio divides that load by 10 — and all the value sits in those last few 9's, not in going from 0% to 90%. Cache-aside is the default because it's the only pattern where a dead cache just makes the system slower, not broken. Cache invalidation is the hardest part, and a versioned key is usually the cleanest solution because it makes the write race harmless instead of trying to prevent it.

But the biggest lesson in this one is about how you measure. Three times while writing this, the numbers said the opposite of what I expected, and all three times the cause was the measurement, not the mechanism: jitter "did nothing" because the system was bottlenecked the whole time so there was no batch to smooth out; thundering herd "caused no harm" because the database pool was far wider than the herd; single-flight "made things slower" because p50 and p99 don't contain the 0.39% group that got hurt. In all three, the data was correct — the question was wrong.

Lesson 6 takes this exact idea further out — to the edge layer, right next to the user — where the limit is no longer CPU or memory but the speed of light, and where one cache-key misconfiguration makes origin load jump 251x while not a single client-side metric changes.