Caching
The fastest request is the one you never make. How caches keep copies close, how they go stale, what they evict, and how a cache that's meant to protect your database ends up knocking it over.
The whole idea
Why cache
Most systems read the same things over and over. The same product page, the same user profile, the same session, the same rendered feed, thousands of times a second. Computing each answer from scratch is wasteful when the answer hasn’t changed since a second ago.
A cache keeps a copy of a result somewhere cheaper to read than the original, usually memory, often closer to the reader. Asking the cache first turns an expensive operation (a disk read, a multi-table join, a call to another service, a request across an ocean) into a lookup in a hash table.
Caches are everywhere, at every layer: CPU caches in front of RAM, the operating system’s page cache in front of disks, a database’s buffer pool, an in-process map in your service, a shared Redis or Memcached tier, and a CDN in front of everything. The ideas in this lesson apply to all of them.
Two numbers describe a cache. The hit ratio is the fraction of reads it answers. The miss penalty is what a miss costs instead. The surprise is how much the last few percent of hit ratio matter.
What each extra nine buys
100,000 reads/s. How many reach the database?
Assumes a hit costs 0.5 ms and a miss 10 ms.
That’s why a cache in front of a database is more than a speed-up. Once the database is sized for the misses, the cache is load-bearing. Lose it, or lose its contents, and the database suddenly faces traffic it was never built for. That was the second half of the hero diagram, and it’s the root of most of the incidents in this lesson.
Cache-aside
The most common pattern puts the application in charge. The cache is a passive key-value store sitting beside the database, hence cache-aside (Facebook’s paper calls it a look-aside cache).
Cache-aside, read and write
- Read: look in the cache. On a hit, done. On a miss, read the database, put the result in the cache with a TTL, and return it.
- Write: update the database, then delete the cached key. The next read misses and fetches the new value.
Why delete instead of writing the new value into the cache? Deletes are idempotent: two concurrent deletes leave the same state, in any order. Two concurrent sets can land in the wrong order and leave the older value behind. Facebook’s memcache paper gives exactly this reason for choosing delete.
Cache-aside has real strengths. Only data that’s actually read gets cached. The cache can fail and reads still work (slowly). And any key-value store will do. Its weakness is that the cache and the database are two systems updated by separate, non-atomic steps, so there are windows where they disagree. We’ll make one of those windows visible in Invalidation.
Write-through and write-back
The alternatives put the cache in the write path, so the cache itself is responsible for the database.
Two ways to write through a cache
- Write-through: a write goes to the cache and the backing store together, and is acknowledged only when both have it. The cache is never behind the database, and a read right after a write hits fresh data. The costs are that every write waits for the slow store, and the cache fills with written data that may never be read. DynamoDB Accelerator (DAX) works this way: writes go through DAX to DynamoDB, and are cached once DynamoDB confirms them.
- Write-back (write-behind): the cache acknowledges as soon as it holds the write, and flushes dirty entries to the store later, often in batches. Writes are fast, and repeated writes to one key collapse into one. But anything acknowledged and not yet flushed is lost if the cache dies.
Write-back is less exotic than it sounds. Your operating system does it with every file write: by default, Linux
treats dirty page-cache data as old enough to flush after 30 seconds, and its flusher threads wake every 5
seconds. That’s why databases call fsync before telling you a transaction committed.
Eviction
Memory is finite, so a full cache must choose what to throw out. That choice is its eviction policy. Its job is to keep whatever will be read again soonest. Since nobody knows the future, every policy is a guess built from the past.
- LRU (least recently used) evicts whatever hasn’t been touched for longest. It’s the classic default, and it’s good when recent use predicts future use.
- LFU (least frequently used) evicts the least popular. It resists one-off reads, but needs to forget old popularity, or yesterday’s hits squat forever.
- FIFO evicts the oldest inserted. It’s cheap and lock-friendly, and once thought too naive.
- TTL-based expiry removes entries after a fixed lifetime. It isn’t really eviction, but in practice it bounds much of a cache’s working set.
LRU has a famous weakness. One sequential scan can wipe out everything that mattered.
How one scan flushes an LRU cache
The fix in every modern policy is some form of admission control: make a new key earn its place before it can push out an established one.
- Memcached has used a segmented LRU since 1.5: an item must be hit twice to move from the probationary queue to the protected one.
- Caffeine, the Java cache, uses W-TinyLFU. A tiny count-min sketch estimates every key’s recent frequency, and a newcomer is admitted only if it’s more popular than the item it would evict.
- S3-FIFO (SOSP 2023) uses three FIFO queues: a small probation queue of about 10% of the cache, a main queue, and a “ghost” queue that remembers keys recently evicted from probation. Across 6,594 production traces it had the lowest mean miss ratio on 10 of 14 datasets, and it scales far better than LRU, because a hit only bumps a tiny counter and never moves anything.
- SIEVE (NSDI 2024) is even simpler: one FIFO queue, a “visited” bit, and a hand that sweeps from old to new.Twitter’s 2020 study of 153 production cache clusters found FIFO matched or beat LRU on many workloads, that over a third of clusters were write-heavy, and that TTLs, not eviction, often bounded the working set. It upended a lot of received wisdom.
Redis takes a different route to cheap LRU. It doesn’t keep a global LRU list at all: on eviction it samples a few
keys (5 by default), merges them into a small pool of good candidates kept between evictions, and evicts the
oldest in the pool. Its LFU mode uses a tiny probabilistic counter that decays
over time. And its default policy is noeviction, which rejects writes when memory is full. That surprises people
who assumed it was a cache by default.
Invalidation
A cache holds copies, and copies go stale. Invalidation is how you bound that staleness. There are three basic tools:
- TTL: every entry expires after a fixed time. It’s simple and self-healing, and it guarantees staleness of up to one TTL.
- Explicit invalidation: the writer deletes or updates the cached key. It’s fresh, but every write path must remember to do it, including scripts, migrations and other services.
- Change-driven invalidation: tail the database’s change log and delete affected keys. Facebook’s
mcsquealreads the MySQL commit log and fans deletes out to every cache cluster. Because the log is durable, lost invalidations can be replayed.
Even with careful deletes, cache-aside has a race that bites at scale.
The stale-set race
A slow reader fetches the old value, a writer updates the database and deletes the key, and then the reader writes its old value into the cache. Facebook’s fix is the lease. On a miss, memcache hands the client a 64-bit token bound to that key. A delete voids any outstanding token. When the client tries to fill the key, a voided token means its value is stale, and the set is refused. It’s the same idea as a load-link/store-conditional instruction in a CPU.
Stampedes
The hit ratio is an average. It hides what happens to one very hot key at the moment it disappears.
A cache stampede
When a hot key expires or is evicted, every concurrent reader misses at once, and they all run the same expensive recomputation. That’s a cache stampede, also called a thundering herd or dog-piling. If the recomputation times out under the load, nobody fills the cache, so the misses continue. The overload sustains itself, a metastable failure.
The defences:
- One recomputes, the rest wait or go stale. Facebook’s leases do this too: memcache issues a token for a key at most once every 10 seconds, and other clients are told to wait briefly and retry. They usually find the fresh value within milliseconds. Over a week, on keys prone to herds, this cut the peak database query rate from 17,000/s to 1,300/s.
- Serve stale while refreshing. Keep the expired value and hand it out while one request rebuilds it. HTTP has
this built in as
stale-while-revalidate. - Refresh early, probabilistically. XFetch (VLDB 2015) has each reader recompute before expiry with a probability that rises as expiry approaches, weighted by how long the recomputation takes. One reader usually refreshes early, and nobody sees the cliff.
- Jitter TTLs so keys written together don’t all expire together.
The cold-cache version of a stampede is even worse, because every key misses at once. Slack’s outage of February 22, 2022 began when a routine Consul agent upgrade restarted agents on memcached nodes. Each restart briefly dropped a node from the service catalogue, and the cache’s control plane swapped in an empty replacement. As hit rates fell, a query run at client boot fell through to the database, and it fanned out across every shard. Load grew faster than the miss rate, queries timed out, and the cache never refilled. The fix was to throttle client boots and raise the limit slowly while the cache warmed.
Content delivery networks
A CDN is a cache you rent, spread across the planet. It keeps copies of your responses in hundreds of points of presence (PoPs), so users fetch from a server a few milliseconds away instead of your origin an ocean away. Cloudflare lists 348 cities on its network.
A CDN, step by step
The mechanisms map directly onto everything above:
- Freshness is HTTP headers.
Cache-Control: max-agesets the TTL, ands-maxageoverrides it for shared caches such as CDNs.privateforbids shared caches from storing a response, andno-storeforbids storing it at all.Varymakes the cache key include request headers. The rules live in RFC 9111 (2022). - Stampede protection is request collapsing. Cloudflare’s cache lock sends only the first request for an uncached asset to the origin, and the rest wait for that response.
- Tiered caching adds an upper layer. Lower-tier edges ask an upper-tier data center, and only upper tiers talk to the origin, so misses at hundreds of edges become roughly one origin request per object per upper tier.
- Serving stale via
stale-while-revalidateandstale-if-error(RFC 5861) hides both slow refreshes and origin outages.
The danger is the cache key. A CDN that caches a personalised page under a URL-only key serves one user’s page to everyone. On Christmas Day 2015, during a DoS attack, a second caching configuration deployed for Steam incorrectly cached pages for logged-in users. For about 90 minutes, store pages of roughly 34,000 users, account pages included, could be shown to other users, with billing addresses and the last two digits of card numbers.
Trade-offs
| Choice | Gains | Costs |
|---|---|---|
| Cache-aside | simple; caches only what’s read; cache failure isn’t fatal | stale windows; app owns fill and invalidation; cold misses |
| Write-through | cache never behind; fresh reads after writes | write latency; caches data nobody reads |
| Write-back | fast writes; coalesces repeated writes | data loss on crash; complex recovery |
| Short TTL | bounded staleness, self-healing | lower hit ratio; more stampede risk |
| Explicit invalidation | fresh data, long TTLs | every write path must comply; races |
| LRU | simple, good for recency-heavy loads | scan-vulnerable; lock-heavy at high concurrency |
| Admission (TinyLFU, S3-FIFO) | scan-resistant; often higher hit ratio | more moving parts; tuning |
| Shared cache tier | one copy for all servers; survives deploys | network hop; it’s now a critical dependency |
| In-process cache | nanoseconds; no network | duplicated per server; hard to invalidate everywhere |
In the real world
- Facebook memcache (NSDI 2013). It served “billions of requests per second” over “trillions of items” with
cache-aside and delete-on-write.
- Leases fix both stale sets and herds.
- Gutter is a spare pool of about 1% of the cache servers that takes over for failed ones. It cut client-visible failures by 99%.
- mcsqueal tails the MySQL commit log and broadcasts invalidations.
- Cold cluster warmup fills a new cluster from a warm one instead of the database, so it’s ready in hours rather than days.
- Facebook, September 23, 2010. A system that automatically “corrected” a configuration value treated database errors as invalid values and deleted the corresponding cache keys. Every miss caused more queries, which caused more errors. Breaking the feedback loop meant turning the site off. It was down about 2.5 hours.
- Slack, 2-22-22. A cache emptied by routine maintenance made an expensive boot-time query fall through to every database shard. The overload sustained itself until boots were throttled.
- Netflix EVCache. Netflix engineers described it in 2024 as about 200 Memcached clusters on 22,000 instances, serving around 400 million operations per second over about 2 trillion items (14.3 PB), replicated across regions.
- Fastly, June 8, 2021. A valid customer configuration change triggered a latent bug and made 85% of the CDN return errors. 95% of the network was back within 49 minutes. When everyone shares one cache layer, its failure is everyone’s outage.
- OpenAI, March 20, 2023. A bug in the redis-py client meant a request cancelled at the wrong moment left its response on a pooled connection, and the next user’s request read it. Some ChatGPT users saw other users’ chat titles, and payment details of about 1.2% of Plus subscribers active in a nine-hour window may have been visible. A cache can leak data, not just serve stale data.
- Redis and Valkey. Redis moved to source-available licences in March 2024. The Linux Foundation launched the BSD-licensed Valkey fork days later, backed by AWS, Google Cloud and others, and Redis 8 added AGPLv3 as an option in 2025. The protocol and data model are the same, so caching designs carry over.
Pitfalls
- Treating the cache as optional when it isn’t. If the database can’t serve your traffic with an empty cache, plan for cold starts: warm caches gradually, throttle, or keep a spare pool.
- No TTL. One missed invalidation or lost race, and a stale value lives forever.
- Set-on-write in cache-aside. Concurrent writers can leave the older value cached. Delete instead.
- Synchronized expiry. Keys loaded together expire together. Add jitter, and protect hot keys with leases or early refresh.
- Caching errors and empty results carelessly. Negative caching saves the database from repeated misses for absent keys, but a cached error page can outlive the error.
- The wrong cache key. Forgetting a header, cookie, locale or user ID in the key serves one user’s response to another.
- Measuring the average hit ratio only. One hot key with a miss storm can melt a database while the dashboard says 99%.
Recall
Go deeper
- Nishtala et al., Scaling Memcache at Facebook (NSDI 2013): leases, Gutter, regional pools and invalidation at billions of requests per second.
- Vattani, Chierichetti & Lowenstein, Optimal Probabilistic Cache Stampede Prevention (VLDB 2015): the XFetch algorithm in one line, with the proof that it’s optimal.
- Einziger, Friedman & Manes, TinyLFU: A Highly Efficient Cache Admission Policy: frequency sketches as an admission filter, as used by Caffeine.
- Yang et al., FIFO queues are all you need for cache eviction (SOSP 2023): S3-FIFO, and why quick demotion beats LRU.
- Yang et al., A large scale analysis of hundreds of in-memory cache clusters at Twitter (OSDI 2020): what real cache workloads look like.
- Slack Engineering, Slack’s Incident on 2-22-22: a cold cache, a fan-out query and a self-sustaining overload.
- RFC 9111, HTTP Caching and RFC 5861: the rules every CDN and browser cache follows, and stale-while-revalidate.
- Redis docs, Key eviction: sampled LRU, LFU and every
maxmemory-policy.
Keep going
The atomic notes for this lesson live in the knowledge graph:
Next on the map: Timeouts, Retries & Overload (why stampedes and cold caches turn into self-sustaining failures) and Storage Engines (the caches inside a database: memtables, buffer pools and Bloom filters).