Caching Strategies — Algorithmics

A cache is a bet: this will be asked for again, and recomputing it costs more than storing it.

Everything else — eviction policy, write strategy, invalidation — is detail around that bet. But the detail is where systems fall over.

What the hit rate actually buys

cache hit rate 90%cache latency 1 msorigin latency 120 ms

average latency: 13 ms
load reaching origin: 10%
vs no cache: 9.3×

Going from 90% to 99% hits looks like a small change and nearly halves the average (13 ms → 2 ms) — because the misses dominate the mean, not the hits. It also cuts origin load tenfold, which is usually the real reason the cache exists.

Read strategies

Cache-aside (lazy loading). The application checks the cache, and on a miss loads from the database and populates it.

async function getUser(id: string) {
  const cached = await cache.get(id);
  if (cached) return cached;

  const user = await db.users.find(id);
  await cache.set(id, user, {ttl: 300});
  return user;
}

Most common, and the default. Only requested data is cached, and the cache going down degrades performance rather than availability. The costs: every miss pays three round trips, and the cache can go stale relative to writes it never saw.

Read-through. The cache itself loads on a miss. Same behaviour, but the loading logic lives in one place instead of at every call site.

Write strategies, and the one that surprises people

Write-through — write to cache and database together. The cache is never stale; every write pays both latencies.

Write-behind — write to cache, flush to the database asynchronously. Very fast writes, and you will lose data if the cache dies before the flush.

Write-around — write only to the database and invalidate the cache entry.

Invalidate, do not update

await db.users.update(id, changes);
await cache.set(id, changes);         // racy
await db.users.update(id, changes);
await cache.delete(id);               // correct

Two concurrent writers can interleave so that the cache keeps the older value permanently: A writes v1, B writes v2, B sets cache v2, A sets cache v1. The database says v2 and the cache says v1, forever.

Deleting has no such race — the next read repopulates from the source of truth. This is the single most common caching bug in production systems.

Eviction

LRU — evict the least recently used. The default, and it is right most of the time.

LFU — evict the least frequently used. Better for stable popularity, worse at adapting.

TTL — expire on a clock. Simplest, and the only one that bounds staleness.

W-TinyLFU — what Caffeine and modern caches actually use: an LRU window in front of a frequency filter. It beats both, and it exists because plain LRU is destroyed by a scan.

The three failure modes

Stampede (or dog-piling). A popular key expires, a thousand requests miss simultaneously, and all thousand hit the database. Fix with a lock so one request recomputes while the others wait, or by refreshing before expiry.

Penetration. Requests for keys that do not exist are never cached, so every one reaches the database. Cache the negative result, or put a Bloom filter in front.

Avalanche. Everything populated at the same time expires at the same time. Add jitter — ttl * (0.8 + Math.random() * 0.4) — so expiry spreads out.

Where the copy lives

Each layer is faster and less consistent than the one below it:

Layer	Latency	Invalidation
CPU cache	~1 ns	hardware
In-process	~100 ns	none — every instance differs
Redis / Memcached	~1 ms	one place, shared
CDN	~10 ms	purge API, minutes
Browser	0	you cannot. Version the URL.

That last row is worth taking seriously. Once a resource is in a user’s browser with a long TTL, it is out of your control until it expires. This is why every build tool emits app.4f3a2b.js — the only reliable invalidation is a different name.