Caching: invalidation is the hard part

Adding a cache takes an afternoon. Keeping it correct takes the rest of the project. That asymmetry is the honest summary of the topic, and it is why "just add caching" is one of the more expensive sentences in software.

The mechanism is easy: keep a copy of an expensive answer somewhere fast, and use the copy. Everything difficult follows from one question that has no general answer — when does the copy stop being true, and how do you find out?

Read the miss rate, not the hit rate

Caching works because access is skewed. A small fraction of your data takes most of the traffic — the current front page, this week's products, the accounts that are actually logged in. If every key were equally likely you would need to cache nearly everything to help at all, and caching would be pointless.

The hit ratio is how that skew is usually reported, and it is the wrong number to reason with. What your origin experiences is the miss rate, and because misses are what remains after subtraction, equal-looking improvements in hit ratio are wildly unequal in effect. Ten thousand requests arriving:

  50% -> 55%:  origin   5,000 ->   4,500   = 10.0% less load  90% -> 95%:  origin   1,000 ->     500   = 50.0% less load  98% -> 99%:  origin     200 ->     100   = 50.0% less load

Every one of those is a five-point or one-point gain in hit ratio. The first shaves a tenth off backend load. The second halves it. The third halves it again, off a much smaller base, for a single percentage point.

Reframe it and the reason is obvious: going from 90% to 95% takes the miss rate from one in ten to one in twenty, which is a factor of two. Going from 50% to 55% takes it from one in two to roughly one in 2.2. Hit ratio is a number for dashboards; miss rate is the number that predicts whether your database survives.

This also tells you where effort pays. Below about 80%, small improvements are barely worth pursuing — you likely have the wrong keys cached or too little room. Above 95%, each further point is a genuine halving, which is why teams fight hard for the last few percent on hot paths. And it tells you what a cache failure means: at a 99% hit ratio your origin is sized for one percent of traffic, so losing the cache does not increase load by one percent, it multiplies it by a hundred. Cache loss is an outage, not a slowdown.

Latency follows the same shape. With a 1ms cache and an 80ms origin, the average is 80ms uncached, 8.9ms at 90%, and 1.79ms at 99% — and note that the average hides the tail. The unlucky one percent still waits the full 80ms, so a cache improves your median far more than your ninety-ninth percentile.

Where a cache can sit

Four places, each with a different failure mode.

In-process, on the heap of the application itself. Nothing is faster — no network hop, no serialisation. The catch is that every server has its own copy, so with eight servers you have eight independent views of the truth, and invalidating one leaves seven stale. Excellent for data that is immutable or nearly so; treacherous for anything that changes.

A shared cache tier that all servers talk to. One version of the truth, so invalidation actually works, at the cost of a network round trip. This is the default for most application caching, and the reason is coherence rather than speed.

The database's own buffer pool, which caches pages in memory whether you ask it to or not. Worth remembering because it means a query hitting warm pages is already far cheaper than one hitting disk — so a query you assumed was expensive may not be, and the honest first step is to measure rather than to add a cache in front of something already cached.

The HTTP or CDN edge, closest to the user and the only layer that can save you the request entirely. It only works for responses identifiable by URL and not specific to one user, but when it applies it is the largest win available, because the request never reaches your infrastructure at all.

These compose, and the composition is where staleness gets confusing. A value can be simultaneously fresh in the database, stale in the shared tier, staler in one server's local cache, and staler still at an edge node in another country. Each layer you add multiplies the places a wrong answer can hide, which is a real argument for having fewer of them than you technically could.

Four ways to combine reads, writes and the cache

Cache-aside is the common default. The application checks the cache, and on a miss loads from the origin and populates it:

def get_user(user_id, cache, db):    key = f"user:{user_id}"    cached = cache.get(key)    if cached is not None:        return cached    row = db.fetch_user(user_id)        # miss: go to the origin    if row is not None:        cache.set(key, row, ttl=300)    return row

Simple, and it has a race worth naming. Two requests miss simultaneously; both query the origin; both write. Usually harmless — they wrote the same value. It stops being harmless when interleaved with an update: reader A loads the old value, a writer updates the database and invalidates the cache, then reader A writes its stale value into the now-empty cache. The cache is now wrong, and will stay wrong until the TTL expires, with nothing to indicate it. This is the strongest practical argument for keeping TTLs finite even when you also invalidate explicitly — the TTL is what bounds how long a lost race can hurt you.

Read-through moves that logic behind the cache's own interface. Same semantics, less duplication, less visibility.

Write-through writes to cache and origin together, so the cache is never stale by construction. You pay on every write, and you cache data nobody may ever read.

Write-behind writes to the cache and flushes to the origin later. Fast, and the one option that can lose committed data: if the cache dies with unflushed writes, those writes are gone. Reasonable for view counters where approximation is acceptable, and not for anything a user believes they saved.

Invalidation, and the keys you cannot enumerate

Here is the actual difficulty. Three approaches, in increasing order of how much they cost you.

Expiry. Set a TTL and accept staleness up to that bound. Unreasonably effective, because it requires no coordination and self-corrects — every bug in your invalidation logic is capped at the TTL. Choose it from how stale the data may be from the user's point of view, not from how often it changes.

Explicit invalidation. Delete the key when the underlying data changes. Precise, and harder than it looks: the write and the invalidation are two operations that can interleave with readers, the invalidation can fail while the write succeeds, and in a multi-region setup the message takes time to arrive. Belt and braces — invalidate explicitly and keep a TTL — is the pragmatic default.

The enumeration problem is the one that defeats explicit invalidation. When a product's price changes, which keys are now wrong? The product itself, but also every search result that mentioned it, every category listing, every recommendation block, every cached page fragment. You cannot enumerate them, because they were derived by code that did not record what it consumed.

The way out is to stop enumerating and change the key instead. Keep a version number for the entity and include it in every derived key:

def search_key(query, product_version):    return f"search:v{product_version}:{query}"# Any write that could affect product-derived data:#   version = cache.incr("product:version")# Every old key becomes unreachable at once, without deleting anything.

Incrementing the version orphans every key derived from the old one in a single operation. Nothing is deleted; the old entries simply become unreachable and are evicted in due course. The cost is that a bump invalidates everything under that version, including entries that were still perfectly valid — you have traded precision for a guarantee of correctness. Scope the version narrowly enough that the bump is not constant, and this is the single most useful trick in cache design.

The failure that takes the site down

A popular key expires. Between its expiry and the moment a fresh value is written, every request for it misses. At two thousand requests per second on that key, two thousand identical queries hit the origin at once, all computing the same answer. The origin slows, so the recomputation takes longer, so more requests pile in behind it. That is a cache stampede, and it is how a working system fails without any change being deployed.

Two fixes, and you want both.

Single-flight. Let one request recompute while the others wait for its result, or serve them the stale value while it refreshes in the background. Serving stale during refresh is usually the better product behaviour — nobody waits, and the data is a few hundred milliseconds old.

def get_single_flight(key, cache, locks, compute, ttl=300):    value = cache.get(key)    if value is not None:        return value    if locks.acquire(key, ttl=5):        # exactly one winner        try:            value = compute()            cache.set(key, value, ttl=ttl)            return value        finally:            locks.release(key)    return cache.get_stale(key) or wait_for(key, cache)

TTL jitter. The stampede's evil twin is synchronised expiry. Populate ten thousand keys during a deploy with an identical 300-second TTL and they expire in the same second, five minutes later — a self-inflicted thundering herd, on a timer, that will reappear every deploy. Spreading the TTLs removes the correlation:

import randomdef jittered(base_ttl, spread=0.1):    """300s with 10% spread -> 270-330s, so keys do not expire in lockstep."""    return int(base_ttl * (1 + random.uniform(-spread, spread)))

Two related failures deserve naming. A hot key — one product on the front page — sends all its traffic to whichever cache node owns that key, so the tier is unevenly loaded no matter how many nodes you add; a small in-process cache in front of the shared tier fixes it precisely because every server wants the same answer. And cold start: an empty cache after a deploy or flush sends everything to an origin sized for one percent of traffic. If your cache is load-bearing, restarting it requires a warm-up or a staged rollout, not a restart.

Eviction, and the scan that empties your cache

When the cache is full, something must go. LRU evicts what was used least recently and is the sensible default. LFU evicts what is used least often and holds long-term favourites better, at the cost of adapting more slowly.

LRU has one failure mode worth knowing, because it arrives from outside your traffic. Fifty hot keys in a cache of a hundred, looped repeatedly, behave exactly as you would want:

LRU cap=100, 50 hot keys looped 20x: hits=950 misses=50 ratio=95.0%

Now something walks five hundred cold keys once — a nightly export, a crawler, an admin report:

  after a 500-key scan, the 50 hot keys give 0 hits of 50

Not degraded. Zero. The scan touched each cold key more recently than any hot key, so LRU dutifully evicted the entire working set for data that will never be requested again. Your hit ratio collapses and your origin absorbs full traffic, triggered by a batch job that has nothing to do with user activity.

This is what scan-resistant policies exist to prevent, and it is why bulk jobs should either bypass the cache or use a separate namespace. It also argues for measuring hit ratio per key class rather than globally — a single aggregate number would show this as a mysterious dip.

Staleness is a product decision

The question "how stale may this be" has no engineering answer. It is a question about what the user is doing.

An article view count can be minutes old and nobody is harmed. A product price shown at checkout cannot be wrong at all, because being wrong means charging the wrong amount. An account balance can lag a little on a dashboard and not at all during a transfer. Notice that the same value can have different requirements in different places — that is normal, and it means freshness belongs to the read path rather than to the datum.

Get this decided explicitly, with whoever owns the product, and write the answer down next to the TTL. The failure mode otherwise is an engineer picking five minutes because it sounded reasonable, and a customer support case six months later that nobody can explain.

What to watch

Four things, and the last is the one people miss.

Hit ratio per key class, never in aggregate. A healthy overall number routinely conceals one class of keys missing constantly, and the aggregate is precisely where the LRU scan problem hides.

Origin load, which is what the cache exists to reduce. If cache traffic rises and origin traffic does not fall, you are caching the wrong things.

Latency at the ninety-ninth percentile, since the mean is dominated by hits and tells you almost nothing about the experience of a miss.

Silent staleness. This is the hard one, because a cache serving a wrong answer looks identical to one serving a right answer — fast, successful, no error anywhere. Nothing in your monitoring will flag it. The only reliable detection is sampling: on a small fraction of requests, fetch from the origin as well, compare, and record disagreements. A rising disagreement rate is the earliest signal that your invalidation has a hole, and it is usually the difference between finding that hole yourself and having a customer find it for you.