Caching in Front of a Database: Invalidation Is the Easy Half

A cache is the only component you can add to a system that makes it faster and less reliable in the same commit. Everything about the happy path is obvious — put Redis in front of Postgres, read from Redis, fall back to Postgres, watch the p99 collapse. The part nobody sketches on the whiteboard is what the system does in the two seconds after that cache stops agreeing with the database, or the fifty milliseconds after a popular key expires.

Those two failures have names — staleness and the stampede — and they are the entire engineering content of caching. The hit ratio is arithmetic. The eviction policy is a config value you will change once and never think about again. This post is about the other part.

The arithmetic first, because it is short

Your origin load is (1 - hit ratio) × request rate. That expression is why cache work has such strange returns. Going from a 90% hit ratio to 95% halves your database load. Going from 95% to 99% cuts it by five times again. And going from 99% to 99.5% halves it a third time — every additional nine is worth as much as everything before it, which is why teams that are already at 99% keep finding it worth chasing.

It also explains the failure direction. A cache that quietly drops from 99% to 95% has not degraded by four percent; it has multiplied your database load by five. If your database was comfortable at 1% of traffic it is now at 5%, and 5% of peak was never a number anyone capacity-planned for. A cache node dying is a database incident, and the only reason it usually isn’t is that most people never test it.

Which sets up the rule the rest of this post is really about: you have to know, in advance and in writing, whether your system is correct without the cache or merely alive with it. Those are different systems.

Where the value gets written

There are three ways to keep a cache and a database in agreement, and they are usually drawn as three arrow diagrams that make them look like a matter of taste. They aren’t. They differ in exactly two observable ways: how long a reader can be served a value the database no longer holds, and what a crash destroys.

Cache-aside with invalidation is what almost everyone runs and what you should run. The application owns both stores: write the database, then delete the cache key. Delete, not update — if you update, two concurrent writers can land their updates in one order in the database and the other order in the cache, and the cache is then permanently wrong with no expiry to save it. A delete has no ordering to get wrong.

Write-through puts the cache in the write path and makes it responsible for the database write. It removes the stale window and adds a failure mode: the cache is now on the critical path for writes, so the cache being slow makes your writes slow.

Write-back acknowledges the write as soon as the cache has it and flushes to the database later. It is the fastest and it is the only one of the three where a node dying loses a write you already told the client had succeeded. This is fine for a view counter and unacceptable for anything a human would file a support ticket about.

Now the uncomfortable part. Even in cache-aside, the write-then-delete pair is not atomic, and there is a race that survives all the obvious fixes. A reader misses, loads the old value from the database, and stalls — GC pause, slow network, anything. A writer updates the database and deletes the key. Then the stalled reader wakes up and writes its stale value into the empty cache slot. The cache is now wrong, and nothing will correct it until the TTL expires, because no further write is coming.

You cannot close this race with ordering. The mitigations are: always set a TTL so the wrongness is bounded rather than permanent; delete again after a short delay if the data matters; or stop having the application write the cache at all and drive invalidation from the database’s replication log, which is what large systems end up doing. That last option is a real distributed system with its own on-call rotation, and it is the correct answer roughly when the cost of being wrong for 60 seconds exceeds the cost of running it.

The stampede

The other failure is not about correctness at all. Every key you cache has a TTL, and at the instant it expires the cache stops answering for it. If that key is popular, every request currently in flight for it misses simultaneously.

Set the strategy to cache-aside and the rate to 20,000 requests per second, and watch the tick where the TTL runs out. That is one expired key producing thousands of identical database queries inside a few milliseconds, all computing the same answer, most of which will be thrown away. The database was sized for 1% of traffic. It just got 100% of it, on one row, with no warning.

Three things make this worse than it looks. It scales with popularity, so it hits your most valuable key first. The queries are identical, so you are burning the entire budget to compute one value many times over. And the origin, now overloaded, gets slower — which widens the window in which more requests arrive and miss, which is a feedback loop rather than a spike.

There are two fixes and you probably want both.

Single-flight: the first request to miss takes a per-key lock and rebuilds; everyone else waits on its result. One origin query. The cost is that every waiting request now carries the full rebuild latency, so a slow origin becomes a latency spike instead of a load spike — better, but not free, and a lock with no timeout turns an origin failure into a permanent hang.

Stale-while-revalidate: keep the expired value in memory past its TTL and keep serving it while one background job refreshes it. Nobody waits and nobody misses. The cost is explicit, and it is the right cost to pay: everyone reads data that is knowingly a few hundred milliseconds out of date. For a product page that is obviously fine. For a permission check it obviously is not.

And whatever you do, jitter the TTLs. If you populate 10,000 keys during a deploy and give them all a flat 300-second TTL, they expire together 300 seconds later, and you have built a synchronised stampede across your entire keyspace on a timer. Write ttl + random(0, ttl * 0.1) and the problem disappears.

The parts nobody mentions

The negative result needs caching too. If a miss means “look it up in the database and find nothing”, then a request for a non-existent key hits the database every single time, and an attacker enumerating random IDs has a direct line to your origin with a 0% hit ratio. Cache the absence, with a short TTL. A bloom filter in front is the version of this that scales.

Your hot key is one key, and one key lives on one node. Sharding a cache spreads the keyspace, not the traffic — if a single celebrity row is 30% of your reads, 30% of your traffic is on one Redis node no matter how many you run. The fix is a small local in-process cache in front of the shared one, holding only the top keys for a second or two. It is also the point at which you have two caches and two invalidation problems.

Serialization is not free. Teams measure the cache round trip and forget that they are JSON-encoding a 200 KB object on every write and decoding it on every read. At high hit rates that CPU is your actual bottleneck, and the cache is blamed for it. Measure the decode, and cache the shape you will use rather than the shape you stored.

Thundering herds are not only about TTLs. A cache node restart empties everything at once, and a deploy that rolls your cache fleet is the same event repeated per node. If a cold cache cannot survive your traffic, then you have a system that cannot be restarted during peak, which is a thing worth knowing before peak.

The short version

Origin load is (1 - hit ratio) × traffic, so each additional nine of hit ratio is worth as much as all the ones before it — and a cache degrading from 99% to 95% is not a four percent regression, it is a five-times database load multiplier.

Use cache-aside and delete on write rather than updating, because a delete has no ordering to get wrong. Know that the read-stalls-then-writes-stale-value race survives all the obvious fixes, and that bounding it with a TTL is the answer until the data is valuable enough to justify driving invalidation off the replication log.

Then the one that actually pages you: a popular key expiring converts every in-flight request into an identical database query in the same millisecond. Single-flight turns that into one query and a latency spike; stale-while-revalidate turns it into one query and no spike, paid for with knowingly stale reads. Jitter every TTL, cache your negative results, and decide today whether your system is correct without the cache or merely alive with it — because the outage will ask you that question and will not wait for an answer.