Foundations · 5 of 7

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.

≈ 25 min

The whole idea

Press ← → to step, or Space to play and pause, whenever a diagram has focus.

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?

hit ratiodatabase reads/savg latency
90%10,0001.45 ms
95%??
99%??
99.9%??

Assumes a hit costs 0.5 ms and a miss 10 ms.

Load on the database is set by the miss ratio, not the hit ratio. Going from 99% to 99.9% looks like a rounding error, and it's a tenfold cut.

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

The cache never talks to the database. The application fills it on reads and invalidates it on writes.
  • 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 pays latency to stay consistent. Write-back pays durability to go fast.
  • 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

LRU cache · newest firstprobationmain
LRU can't tell a key read once from a key read every second. A probation stage makes new keys prove themselves first.

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 mcsqueal reads 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

Every step was correct. The interleaving wasn't. Without a TTL, the stale value lives forever.

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

The cache was hiding a thousand identical queries per second. When the key expired, it stopped hiding them.

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.
17K/speak database queries on herd-prone keys, without leases
1.3K/sthe same, with leases (Facebook, 2013)

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

Edges absorb repeat reads, collapse concurrent misses, and an upper tier shields the origin from edges that all miss at once.

The mechanisms map directly onto everything above:

  • Freshness is HTTP headers. Cache-Control: max-age sets the TTL, and s-maxage overrides it for shared caches such as CDNs. private forbids shared caches from storing a response, and no-store forbids storing it at all. Vary makes 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-revalidate and stale-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

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).

Done with this lesson?

Mark it learned and the concepts it teaches will light up in your galaxy.

Next in FoundationsTimeouts, Retries & Overload