Caching: Eviction, Invalidation and the Stampede

Cache-aside to write-behind, what Redis 8 really does when it fills up, the invalidation race and the lease that closes it, three fixes for a stampede measured against doing nothing, and the HTTP caching headers most people misread.

A cache is a copy. Every hard problem in caching is a problem with copies. Which copy is right when two disagree? What happens when the copy is thrown away? And what happens when many people need the copy at the moment it disappears?

This part measures all three. A real Redis gets filled until it has to throw things away. A cache-aside race gets forced on purpose so we can see what it leaves behind. And one hot key expires under 3,000 requests, four different ways.

Try this first

One popular key is cached. Requests for it arrive steadily, about 1.1 every millisecond. At some moment the entry expires, and rebuilding it from the database takes 120 milliseconds.

Write down two numbers before you scroll:

1. With no protection at all, how many requests go to the database?
2. Now add a lock, so only one request rebuilds the entry and everyone else waits for it. How many clients now wait for the database?

The stampede, measured four ways

The lab sent 3,000 requests at one hot key over 2.7 seconds, with the entry expiring at 1.8 seconds, and tried four strategies. Each saw the same arrivals and the same 120-millisecond origin, seven runs each. The table shows the medians.

Strategy	Calls to the origin	Clients who waited	Their average wait	Answers served after expiry
No protection	135	135	120.55 ms	0
One fill, others wait	1	135	59.75 ms	0
Early refresh (XFetch)	4	4	120.54 ms	0
Serve stale, refresh	1	0	—	133

If you guessed a number near 135 for the first question, you’ve understood the stampede. The entry expires. For the next 120 milliseconds the database is busy rebuilding it, and every request that arrives in that window finds the cache empty and goes to the database too. At 1.1 requests per millisecond, about 133 of them land in 120 milliseconds. The lab’s seven runs counted between 120 and 152, because arrivals are random, with a median of 135.

That’s a cache stampede, also called a thundering herd or a dog-pile. Every one of those 135 requests did exactly the right thing on its own. And this lab is the gentle version. Its origin takes 120 milliseconds however many requests hit it at once. A real database slows down under a burst like this, which makes the rebuild slower, which lets more requests pile in behind it.

The second answer is the one people get wrong. The lock spared the database, but not the clients. One request rebuilt the entry, and the others that arrived during those 120 milliseconds waited for it. In every run, the number of clients who waited with the lock was within two of the number without it, because they’re the same clients: the ones who arrived while the value was missing. The lock halved their average wait, since a client arriving late in the window only waits for the rest of the rebuild. The first one to arrive still waited the full 120 milliseconds. It didn’t change how many people waited.

That’s the thing to take from the figure. Each fix moves the cost somewhere:

• One fill, others wait (request coalescing) moves it from the database to the clients’ queue. One call, 135 waits. It also has a failure mode of its own: if that one rebuild is slow or fails, every waiter is stuck behind it.
• Early refresh moves it earlier in time. Each request close to expiry rolls a die, and with a probability that grows as expiry approaches, it rebuilds the entry before it runs out. The lab used the XFetch rule from a 2015 VLDB paper, with its default setting, β = 1. The median run had 4 early rebuilds, only those 4 requests waited, and nobody saw an empty cache. Counting only rebuilds of this expiry, the median run had 3; other runs also refreshed the new entry early again before the run ended, a cost the other strategies never pay inside this window. The worst run had 12.
• Serve stale, refresh moves it into correctness. The expired value is served at once while a single background request rebuilds it. No client waited at all. The price is 133 answers served after the entry’s expiry. The stalest, across all seven runs, was 121.69 milliseconds past it.

That last number is only small because the rebuild succeeded. How stale a served answer can get is bounded by how long the cache is allowed to serve stale: Varnish’s grace period, or the N in stale-while-revalidate=N. If the rebuild keeps failing, that bound is what you get.

So you don’t choose a stampede fix by asking which one works. They all work. You choose by asking which cost you can afford: database load, client latency, or staleness.

One setting of this lab that mattered

The first version of this lab started its traffic only 300 milliseconds before the expiry, and XFetch made 18 calls. The lab still runs that case and records when each early rebuild fired. Every one, across seven runs, came between 2.69 and 142.71 milliseconds after the first request arrived. XFetch refreshes early with a probability that depends on how close expiry is, measured in rebuild times, and 300 milliseconds is only two and a half rebuilds. So every client arrived already inside the early-refresh zone, and they stampeded at the start. With 1.8 seconds of steady traffic before the expiry, no early rebuild came sooner than 1,007.5 milliseconds into the run, well before the expiry and driven by steady traffic, and the median dropped to 4. If you test a stampede fix, test it on traffic that was already flowing.

Using XFetch

XFetch needs two things stored next to the value: the expiry time, and Δ, how long the last rebuild took. On every read, the request computes now − Δ·β·log(random()) and rebuilds if that’s past the expiry. Since log of a number between 0 and 1 is negative, that’s the current time plus a random head start, one that’s usually small and scales with the rebuild cost. The paper’s advice on β:

The parameter β defaults to 1 and already provides effective prevention against cache stampedes. It can be increased for even better guarantees against stampedes, if earlier expirations are not a concern.

The code behind “one fill, others wait”

This is the coalescing strategy from the lab, as it ran. The first request to find the entry expired marks it as filling and goes to the origin. Everyone after it waits on a condition variable until the fill lands.

			case "locked":
				// One recompute; everyone else blocks until it lands. This is coalescing.
				c.mu.Lock()
				for {
					if time.Now().Before(c.e.expiry) {
						c.mu.Unlock()
						break
					}
					if c.e.filling {
						c.cond.Wait() // the herd gathers here, and is released together
						continue
					}
					c.e.filling = true
					atomic.AddInt64(&misses, 1)
					c.mu.Unlock()
					start := time.Now()
					v := o.get()
					took := time.Since(start)
					c.mu.Lock()
					c.e = &entry{value: v, expiry: time.Now().Add(ttl), delta: took}
					c.cond.Broadcast()
					c.mu.Unlock()
					break
				}

Look at the comment on c.cond.Wait(). The herd isn’t gone. It’s gathered in one place and released together. In a real proxy those waiters are threads or connections, and releasing them all at once is a small herd of its own.

Building these on Redis

The lab’s lock is a condition variable inside one process, which is the cheapest possible case. Across many servers sharing one Redis, each strategy needs a little more machinery. None of what follows was measured here.

• Coalescing across servers is usually a lock key: SET lock:k <unique-token> NX PX 5000. The winner rebuilds; the losers poll the cache or wait for a notification. The PX expiry is the lock’s timeout, for the case where the winner dies, and the unique token stops a slow winner from deleting a lock that has since passed to someone else, as long as the release checks the token and deletes in one atomic step, usually a short Lua script. A GET followed by a DEL has the same race. The lease from the invalidation section below is the same shape.
• Serving stale from Redis needs a trick, because EX deletes the key at its expiry and there’s nothing left to serve. Store the logical expiry inside the value, give the key a longer real TTL, and treat a value past its logical expiry as one to serve while triggering a single refresh. The gap between the two expiries is your grace window.
• XFetch needs Δ and the expiry stored with the value, as above.
• An evicted key is a miss, not a stale hit. Serving stale only helps with expiry. If the cache is full and evicts a hot key, every strategy starts from an empty entry.

What the proxies and CDNs actually do

Caching proxies and CDNs each pick one of these, and their documentation is candid about the costs.

Varnish coalesces automatically, and its own guide names the herd that coalescing creates:

If you are serving thousands of hits per second the queue of waiting requests can get huge. There are two potential problems – one is a thundering herd problem – suddenly releasing a thousand threads to serve content might send the load sky high. Secondly – nobody likes to wait.

Its answer is grace, which is our “serve stale, refresh” row:

Setting an object’s grace to a positive value tells Varnish that it should serve the object to clients for some time after the TTL has expired, while Varnish fetches a new version of the object.

The default grace is 10 seconds.

nginx doesn’t coalesce unless you ask. Its reference lists Default: proxy_cache_lock off;, and even when it’s on, the lock only covers populating “a new cache element”. For an entry that has expired, the directive for serving it while one request refreshes is proxy_cache_use_stale updating, which is also off by default. And the lock leaks on purpose: after proxy_cache_lock_timeout, five seconds by default, a waiting request goes to the origin anyway and its response isn’t cached. A lock without that timeout would let one slow origin call hold every waiter.

Fastly coalesces by default, and warns about the case where it backfires. If the response comes back uncacheable, and Fastly also can’t create what it calls a hit-for-pass marker, the queue can’t be served from it:

In this situation the next request in the queue will be sent to origin and the remaining requests will form a new queue, resulting in the requests being sent consecutively, not concurrently. In some cases this can create extreme response times of several minutes.

That’s the “one fill, others wait” row at its worst: the waiters take turns. Fastly’s advice is to let such requests skip the cache entirely.

CDNs coalesce per location, not globally. Cloudflare’s cache lock means Cloudflare “only sends one request at a time to the origin for a given asset from a single location in Cloudflare’s network”. CloudFront collapses requests that reach one edge location with the same cache key, and says what widens the herd: “CloudFront only collapses requests that share a cache key.” A CDN with hundreds of locations can still send hundreds of requests for one expired object. Cloudflare’s Tiered Cache and Fastly’s shielding exist to narrow that, by making lower tiers ask an upper tier instead of the origin.

ASP.NET Core’s output caching locks by default: “By default, resource locking is enabled to mitigate the risk of cache stampede and thundering herd.”

What about adding jitter to TTLs?

You’ll often hear “add some randomness to your TTLs”. AWS does recommend it, on its caching best-practices page:

If you use the same TTL length (say 60 minutes) consistently, then many of your cache keys might expire within the same time window, even after prewarming your cache. One strategy that’s easy to implement is to add some randomness to your TTL:

Notice which problem that solves. It’s many keys expiring together, for example after you warm a cache all at once. Jitter spreads their expiry out. It does nothing for the problem in our figure, which is one hot key. A single key has one expiry time, and however randomly you chose it, every request that arrives during the rebuild still misses. For one hot key you need one of the four strategies above.

We found AWS describing the many-keys case but no published measurement of it. Every stampede measured in the sources we read is a single popular key: the VLDB paper’s Goodreads item, Facebook’s hot keys, Fastly’s popular object.

The VLDB paper does compare random approaches, but not this one. It shows that choosing the early-refresh moment from a uniform distribution per request is “far from being optimal”, and an exponential one is close to optimal. That’s the result behind XFetch. It isn’t an argument about TTL jitter.

What a cache does when it fills up

A cache has less room than the data behind it, or it wouldn’t be a cache. So sooner or later it’s full, and it has to decide what to throw away. That decision is the eviction policy.

The first thing to know is what your cache does when you haven’t decided. We started Redis 8.10.1 with no configuration and asked it:

Setting	What Redis 8.10.1 reported
maxmemory	0
maxmemory-policy	noeviction
maxmemory-samples	5

maxmemory 0 means no limit. The Redis docs say so: “Set maxmemory to zero to specify that you don’t want to limit the memory for the dataset. This is the default behavior for 64-bit systems”. An unconfigured Redis grows until the machine, the container or the operating system stops it.

The default policy is harder to find. The eviction page recommends one (“allkeys-lru is a good default option if you have no reason to prefer any others”), which is advice, and doesn’t say what you get if you don’t choose. The shipped redis.conf has the line commented out, next to “The default is: maxmemory-policy noeviction”. And the compiled-in default in Redis’s config.c is MAXMEMORY_NO_EVICTION.

Managed services change this. Amazon ElastiCache’s parameter reference lists volatile-lru as the default policy in its Redis OSS parameter tables, and it reserves 25% of a node’s memory by default, so maxmemory is set for you. That combination has a trap in it, measured below: if a cache’s keys carry no TTLs, volatile-lru behaves exactly like noeviction. Whatever you run, read the setting off the running server.

Then we gave it an 8 MB limit and offered it 20,000 keys of about a kilobyte each, under four settings:

Policy	Keys offered	Keys held	Keys evicted	What the writer saw	Reads
noeviction	20,000	5,193	0	OOM command not allowed when used memory > 'maxmemory'.	still work
volatile-lru, no key has a TTL	20,000	5,164	0	OOM command not allowed when used memory > 'maxmemory'.	still work
volatile-lru, every key has a TTL	20,000	5,068	14,932	no error	still work
allkeys-lru	20,000	5,174	14,826	no error	still work

Two rows deserve a second look.

Under the default, a full cache refuses writes. It doesn’t throw anything away. It keeps the 5,193 keys it has and answers new writes with an error: after the first one, the lab offered 100 more and all 100 were refused. Reads still work, so a dashboard that checks “is Redis up” by reading a key stays green. Meanwhile the application’s writes fail. If the code treats a failed cache write as fatal, the cache has just taken the application down. If it ignores the error, the cache silently stops learning anything new.

volatile-lru with no TTLs behaves exactly like noeviction. The volatile- policies only ever evict keys that have an expiry set. If nothing has one, nothing is a candidate, and the server refuses writes. It’s a common trap, because volatile-lru sounds like “LRU, but careful”.

For a cache, the setting you almost always want is an allkeys- policy, which considers every key.

LRU, approximately

LRU means “least recently used”: when you need room, throw out the entry nobody has touched for the longest. Part 15 built an exact one, with a hash map and a doubly linked list. Redis doesn’t keep that list, because two extra pointers on every key is a lot of memory at Redis’s scale.

Instead, it samples. When it needs room, it picks a handful of keys at random and evicts the one that’s gone longest without being touched. maxmemory-samples is how many it picks.

The Redis docs describe it plainly:

The Redis LRU algorithm uses an approximation of the least recently used keys rather than calculating them exactly. It samples a small number of keys at random and then evicts the ones with the longest time since last access.

And the reason: “The reason Redis does not use a true LRU implementation is because it costs more memory.” The shipped config says what the knob buys: “The default of 5 produces good enough results. 10 Approximates very closely true LRU but costs more CPU. 3 is faster but not very accurate.” Candidates that lose one round aren’t forgotten, either. Redis keeps a pool of the best 16 it has seen so far.

How close is that to real LRU? We gave the lab a test with a known right answer. Write 4,000 keys. Touch the first 2,000. Wait a few seconds. Touch the other 2,000. Cap the memory, then write more keys to force evictions. A true LRU takes every eviction from the 2,000 old keys. Any eviction of a recently touched key is a mistake.

The result depends on something you might not expect: how many of the old keys have to go. Choose the depth in the figure.

Old keys that had to go	3 samples	5 (the default)	10	64	Evicting at random
26%	0%	0%	0%	0%	54.51%
51%	7.03%	0%	0%	0%	56.4%
76%	18.74%	6.09%	0%	0%	57.94%
96%	27.5%	15.78%	6.54%	0.1%	60.96%

Each cell is the median of seven runs: the share of evictions that took a key a true LRU would have kept.

While old keys are plentiful, Redis at its default makes essentially no mistakes. A handful of random keys almost always includes an old one, and the pool of 16 remembers good candidates between rounds. As the old keys run out, a random sample contains fewer of them. With 96% of them needed, the default got 15.78% of its evictions wrong, and it took 64 samples to get back to near zero.

That’s the real shape of sampled eviction. It’s close to exact when there’s plenty of cold data to choose from, and it degrades when almost everything left in the cache is warm. Whether that matters on real traffic is the next section’s question, and the answer turned out to be about something else.

This test was wrong three times first

The lab got this result on its fourth design. The first three are worth knowing, because each one produced a clean, repeatable, wrong number.

First, it reported the same error rate at every sample size, even 64, and that rate was no better than chance. It didn’t move when the setting moved. The test had touched all 4,000 keys in one quick burst, and Redis records “when was this last touched” on a clock that ticks once a second. Keys touched in one burst mostly share a tick, so there was nothing to rank them by. The flat result was the symptom: sampling more candidates can’t help when they all look the same age. The pause between the two halves is the whole experiment.

Second, it reported a large error rate at the default, with tight ranges over eleven runs. It looked like a finding. But the test forced slightly more evictions than there were old keys, so even a perfect LRU would have had to take some recent ones. And it asked for all of the old keys, which, as the table shows, is exactly where sampling is at its worst. The headline number was a property of the test’s setting, not of Redis.

Third, it had a few runs that looked unusually accurate. In those runs Redis had evicted some of the newly written keys instead, and the test hadn’t counted those as mistakes.

If you turn a knob and the result doesn’t move, suspect the test before the knob. And if a result is clean, ask which of your own settings produced it.

The one-second resolution is in the source. In Redis 8.10.1’s object.h:

#define LRU_CLOCK_RESOLUTION 1000 /* LRU clock resolution in ms */

A thousand milliseconds. Two keys used within the same tick of that clock have the same age as far as eviction is concerned.

Does the approximation matter?

That test counts mistakes. The question an operator has is different: on real traffic, how much reaches the database?

Real traffic is usually skewed. A few keys are wildly popular and most are rarely touched. We modelled that with a Zipf distribution over 20,000 keys, exponent 1.07, and sent 120,000 requests through Redis. On a miss, the client writes the key back, which is how cache-aside behaves. Popularity doesn’t change during the run, which suits LFU; a workload whose hot keys drift would suit it less.

The lab ran three cache sizes, each policy three times, alongside three yardsticks computed on the same requests at the size Redis actually held: an exact LRU, the optimal policy (Belady’s, which evicts whichever key will next be asked for furthest in the future, and needs to know the future to do it), and the floor. 10.28% of the requests were for a key never seen before, and no cache can hit those.

The miss rate is what the database feels, so that’s what the table shows. Lower is better.

Cache holds	allkeys-random	allkeys-lru	allkeys-lfu	Exact LRU	Optimal
about 1,000 keys	34.44%	34.12%	26.08%	30.29%	18.78%
about 3,100 keys	22.28%	20.95%	17.55%	19.25%	12.11%
about 7,300 keys	13.54%	12.41%	12.02%	12.25%	10.28%

Read across a row, then down a column.

• Size beats policy. Going from about 1,000 keys to about 7,300 cut LRU’s misses from 34.12% to 12.41%. The biggest gap between two real policies at any one size was 8.36 points. Cache size is a capacity decision, and it’s worth more than any setting.
• Policy matters most when the cache is small. Random against LFU is 8.36 points at 1,000 keys and 1.52 at 7,300. When the cache holds nearly everything that’s asked for twice, it barely matters what you throw out.
• Redis’s LRU falls furthest behind an exact LRU when the cache is small: 3.83 points at 1,000 keys, 1.70 at 3,100 and 0.16 at 7,300. In the small cache, most of that turned out to be the clock, not the sampling. It gets its own section below.
• LFU beats LRU on this workload at every size. LFU means “least frequently used”: it keeps keys that are asked for often, not just recently. On skewed, stable traffic, frequency is the better signal. It even beat an exact LRU at every size, so its win isn’t only Redis’s LRU being handicapped. In the small cache, some of its lead over Redis’s LRU does come from the clock problem below.
• Points of hit rate understate what the database feels. At 3,100 keys, random’s 77.72% hit rate against LFU’s 82.45% looks like a small gap. In misses it’s 22.28% against 17.55%, so random sends 27% more requests to the database.

Two details of how this was measured. The client sent one command at a time, as a real application does. That detail cost us a rerun: Redis evicts before it runs each command, and a Lua script counts as one command, so our first version, which batched 2,000 requests per script, let memory run 13% past the limit inside a script before anything was evicted. It also changes what recency means, since every key a script touches gets the same tick of the clock. And the keys held are measured, not the sizes we asked for, because Redis’s own fixed overhead means fewer keys fit than a byte budget suggests.

The clock, again

Redis’s LRU trailed an exact LRU by 3.83 points in the small cache. The obvious suspect is sampling. The measurements pointed somewhere else.

The lab’s client sent about 25,000 requests a second, and the small cache evicted about 8,500 keys a second: as many keys as it holds, about nine times every second. Nearly all of those evictions come from the cold tail, so a cold key rarely stays resident for a full second. And Redis measures idle time in whole seconds. At the end of the run, every resident key under LRU reported the same idle time. A snapshot catches one moment, and just after the clock ticks there would be two ages rather than one, but either way Redis was choosing among keys it couldn’t tell apart.

To test that, the lab ran the first 40,000 of the same requests into the same small cache twice, changing only the pace:

Pace	Distinct idle ages among resident keys	Redis LRU hit rate	Exact LRU, same requests
25,464 requests a second	1	65.84%	69.59%
391 requests a second	18	69.44%	69.59%

On those 40,000 requests, slowing down closed 3.60 of the 3.75 points. Slowed, the cold keys lived for several seconds, Redis had ages to rank by, and its LRU came within 0.15 points of exact. So in the small cache, most of the gap is the one-second clock, not the sampling. We only ran this test on the small cache. The same effect probably explains some of the gap at 3,100 keys, but we didn’t test that.

It’s the same trap as the first accuracy test, and this time it isn’t a mistake in a harness. A busy cache whose cold keys come and go within a second gives Redis’s LRU almost nothing to rank by. Raising maxmemory-samples won’t help, because more samples of keys with the same age are still tied, and the clock’s resolution is fixed when Redis is compiled. LFU counts accesses instead of timing them, so it doesn’t have this problem, though it has coarse ties of its own: new keys start at a count of 5. In the small cache, LFU led Redis’s LRU by 8.04 points. At most 3.83 of that is the clock, since LFU beat even an exact LRU by 4.21. If your cache is small against its traffic and popularity is stable, that’s a reason to look at allkeys-lfu, or at a bigger cache.

Four ways to put a cache in the path

Before invalidation, the vocabulary. There are four common ways to wire a cache to the database behind it, and the names get used loosely.

Pattern	Who reads the database on a miss	What happens on a write	The failure it invites
Cache-aside (lazy loading)	The application	The application writes the database, then deletes or updates the cache entry	Stale entries from races between readers and writers
Read-through	The cache, through a loader you give it	Usually combined with one of the two below	The same as cache-aside, hidden inside a library
Write-through	—	The write goes to the cache, and the cache writes the database before returning	Every write pays for both; the cache fills with data nobody reads
Write-behind (write-back)	—	The write goes to the cache and returns; the cache writes the database later	Writes the cache accepted can be lost before they reach the database

Two notes on those definitions.

Write-through done by the application is not a consistency guarantee. In AWS’s version the application writes the database and then the cache, and its ElastiCache guide says: “Data in the cache is never stale.” That’s true for one writer. With two writers whose cache updates arrive in a different order from their database writes, the cache holds the loser. A cache that writes the database itself, as in Coherence’s version, can order the writes to one key, which is a real advantage of the library form. Facebook’s memcache paper describes the same kind of failure in a look-aside cache: “This can occur when concurrent updates to memcache get reordered.”

Write-behind trades durability for speed. Oracle Coherence says the database write happens “after a configured delay, whether after 10 seconds, 20 minutes, a day, a week or even longer”, and that this “implies that the database transactions must never fail; if this cannot be guaranteed, then rollbacks must be accommodated.” Apache Ignite says it more bluntly: “some updates could be lost due to node failures or crashes.” If a write matters, write-behind means the cache is now your database, and it had better be as durable as one.

Cache-aside is the default in most systems, because the cache can fail without taking writes with it. It’s also where the most interesting bug lives.

The invalidation race

The usual rule for cache-aside writes is: update the database, then delete the cache entry. The next reader misses and loads the new value. Deleting is preferred over writing the new value into the cache, for reasons the race below makes clear.

But there’s an ordering where even delete-after-write goes wrong. We forced it on a real Redis, step by step:

Step	Who	What	Reply
1	reader	GET user:1 from the cache	(nil) — a miss
2	reader	read the database	v1
3	writer	update the database	v2
4	writer	DEL user:1 from the cache	deleted
5	reader	SET user:1 v1 EX 3600	OK
6	anyone	GET user:1 from the cache	v1

The reader read the database before the update, and wrote its result to the cache after the delete. The delete had nothing to delete yet. The old value then sits in the cache with a full hour to live, while the database holds v2. No retry fixes it and no error was raised. Everyone did the right thing.

This is forced, so it tells you the ordering is possible and what it leaves behind. It tells you nothing about how often it happens. That depends on how long a reader takes between its database read and its cache write. Under a slow database, or a garbage-collection pause at the wrong moment, it’s longer than you’d think.

Leases

The fix that’s documented at scale is a lease. On a miss, the cache gives the reader a token. A delete for that key invalidates the token. When the reader comes back to write, the cache accepts the write only if the token is still valid.

Facebook’s memcache paper introduced leases for exactly two problems, “stale sets and thundering herds”, and describes the race above as a stale set: “A stale set occurs when a web server sets a value in memcache that does not reflect the latest value that should be cached. This can occur when concurrent updates to memcache get reordered.”

Leases also limit how often tokens are handed out, one per key every 10 seconds by default, and other clients who miss are told to wait briefly and retry. That’s the thundering-herd half. The paper measured it over a week of cache misses for “a set of keys particularly susceptible to thundering herds”:

Without leases, all of the cache misses resulted in a peak database query rate of 17K/s. With leases, the peak database query rate was 1.3K/s.

That number is the herd protection, not the stale-set protection. The paper doesn’t give a number for stale sets prevented.

The same paper explains why a write deletes the entry rather than setting the new value: “We choose to delete cached data instead of updating it because deletes are idempotent.” A delete can be retried and replayed in any order and still end in the same state. Two sets of different values can’t.

Redis has no leases built in, but they take one key and a few lines of Lua. We ran the same interleaving with one:

Step	Who	What	Reply
1	reader	GET user:1 from the cache	(nil) — a miss
2	reader	take the lease: SET lease:user:1 reader-1 NX PX 10000	OK
3	second reader	also misses, asks for the lease	(nil) — refused
4	reader	read the database	v1
5	writer	update the database	v2
6	writer	DEL user:1 lease:user:1	deleted
7	reader	write back only if the lease is still mine	refused
8	anyone	GET user:1 from the cache	(nil) — the next reader loads v2

Look at step 3 as well. The lease does double duty. The second reader who misses doesn’t get a token, so it doesn’t go to the database. In the paper, it waits briefly and retries; our lab stops at the refusal and doesn’t model the retry. That’s coalescing again, from the same mechanism: one lease per key limits how many requests rebuild it at once.

One detail our demonstration simplifies. Its token is a fixed string, reader-1. A real lease token must be unique per miss; the memcache paper’s is a 64-bit token issued by the server. If tokens can repeat, a delete followed by a new miss can hand out the same token again, and the old reader’s stale write gets through.

The other common fixes, and what each actually buys:

• A short TTL on everything. It doesn’t prevent the race. It caps how long the wrong value lives. Often that’s enough, and it’s the cheapest thing on this list.
• Versioned values. Store a version number with the value and refuse a write that carries an older version than the one stored. That needs the database to hand out versions, and it makes every cache write a compare-and-set.
• Delete twice (“delayed double delete”): delete, update, wait a moment, delete again. It narrows the window rather than closing it, because how long to wait is a guess about how slow the slowest reader is.
• Change the key instead of the value. If the cache key includes a version (user:1:v7), a write creates a new key and old readers write to a key nobody asks for any more. This is the same idea as the versioned file names below. It makes the stale entry unreachable rather than unlikely, as long as readers learn the current version from somewhere that isn’t itself a cache with the same race, such as the database row or the page that links to the asset. Versioned values with compare-and-set also refuse every stale write. The other fixes only make one less likely.

HTTP caching: the headers everyone misreads

Everything above is a cache you run. HTTP caching is a cache other people run: the browser, a corporate proxy, a CDN. You don’t control them. You send them instructions in the Cache-Control header, and the instructions mean something precise. Here’s what RFC 9111 says each one does:

Directive	What it actually means
max-age=N	The response is fresh for N seconds; after that it’s stale
s-maxage=N	The same, for shared caches (proxies, CDNs) only, overriding max-age. It also forbids a shared cache from serving the response stale without revalidating
no-cache	May be stored, but must be revalidated with the origin before every reuse
no-store	Must not be stored at all
private	Must not be stored by a shared cache; a browser may store it
public	May be stored even if it otherwise wouldn’t be
must-revalidate	Once stale, never serve it without revalidating, even if the origin is down

no-cache does not mean “don’t cache”

This is the most common misreading in the whole subject. The RFC’s definition:

The no-cache response directive, in its unqualified form (without an argument), indicates that the response MUST NOT be used to satisfy any other request without forwarding it for validation and receiving a successful response; see Section 4.3.

It says nothing about storing. The response can be kept. It just can’t be reused without checking with the origin first. The directive that forbids storing is no-store.

That check is cheap when it works. The cache sends the stored response’s validator, usually an ETag, in an If-None-Match header. If nothing changed, the origin answers 304 Not Modified with no body. RFC 9110 calls conditional GET “the most efficient mechanism for HTTP cache updates”.

The misreading isn’t only in people’s heads. It’s in vendor documentation. Cloudflare’s own two pages disagree. The overview of default cache behaviour says:

Cloudflare does not cache the resource when: The Cache-Control header is set to private, no-store, no-cache, or max-age=0.

The page on Cache-Control directives says:

When setting no-cache with Origin Cache Control off, Cloudflare does not cache. When setting no-cache with Origin Cache Control on, Cloudflare caches and always revalidates.

And the same page says Origin Cache Control is on for Free, Pro and Business customers, who “cannot disable it”. So for most Cloudflare zones, the overview page is wrong about its own product.

Other vendors split both ways:

• Google Cloud CDN follows the RFC: “A response with no-cache is cached but must be revalidated with the origin before being served.”
• Akamai doesn’t, when it’s set to honour the origin’s headers: “Akamai servers don’t cache objects when the no-store or no-cache directives are present in the Cache-Control header, or when the private directive is present and Honor private option is enabled.”
• CloudFront’s CachingOptimized managed policy has a one-second minimum TTL, and says it will cache for at least that long “even if the Cache-Control: no-cache, no-store, or private directives are present in the origin headers.”

In fairness, the RFC is loose about this too. Its section on heuristic freshness advises origins to send Cache-Control: no-cache “if they wish to prevent caching”, meaning unvalidated reuse. The definitions are precise. The prose around them isn’t always.

So: no-cache for “check with me first”, no-store for “don’t keep this”. And then check what your CDN actually does with each, because they don’t agree.

no-store and private are not privacy

Both look like privacy controls. The RFC says plainly that they aren’t. Of no-store: “This directive is not a reliable or sufficient mechanism for ensuring privacy.” Of private: it “only controls where the response can be stored; it cannot ensure the privacy of the message content.” A cache that ignores the header, or a network someone is listening to, isn’t stopped by either. Privacy comes from TLS and from not sending the data. Part 37 comes back to this.

The cache key is a decision, and CDNs make it differently

A cache stores responses under a key. Two requests with the same key get the same response. What goes into the key decides both your hit rate and whether one user can ever see another user’s response.

• Query strings. CloudFront’s default cache key is the domain plus the URL path: “Other values from the viewer request are not included in the cache key, by default.” Cloudflare’s default includes the whole query string. So /app.js?v=2 is a new object on Cloudflare and the same object as /app.js?v=1 on a default CloudFront setup. Move a site between them without checking and the cache-busting in your URLs stops working.
• Vary. A response with Vary: Accept-Language tells caches the right answer depends on that request header. RFC 9111 says a cache “MUST NOT use that stored response without revalidation unless all the presented request header fields nominated by that Vary field value match”. Cloudflare’s docs say that “By default, Cloudflare does not consider vary values in caching decisions”, with three named exceptions (a Cache Rules setting, Vary for Images, and Vary: accept-encoding). Relying on Vary behind that CDN, without configuring it, can serve one language to everyone.

Invalidating a CDN: change the name instead

Every CDN has a purge or invalidation API. AWS, which charges for invalidation beyond “The first 1,000 invalidation paths that you submit per month”, recommends not relying on it:

If you want to update your files frequently, we recommend that you primarily use file versioning for the following reasons:

The first reason is the one that matters: “If you invalidate the file, the user might continue to see the old version until it expires from those caches.” Purging the CDN doesn’t reach the browser’s cache or a company’s proxy. A new file name does, because nothing has cached it yet. That’s why built assets get names like app.3f9a1c.js. Their content can be cached for a year, and the page that references them is cached briefly or not at all.

It’s the same idea as versioned cache keys earlier. When you can’t reliably remove the old copy, make sure nobody asks for it.

Serving stale on purpose

RFC 5861 adds two directives. stale-while-revalidate=N lets a cache serve a stale response for N seconds while it revalidates in the background. That’s the grace strategy, requested by the origin. stale-if-error=N lets it serve stale content when the origin returns an error. Two cautions. RFC 5861 is an Informational RFC, not part of the HTTP standard proper. And support is uneven: Google Cloud CDN supports stale-while-revalidate and says it “doesn’t support the stale-if-error directive”; Cloudflare’s Cache API doesn’t support stale-while-revalidate; and on Cloudflare some directives sent alongside it switch it off, including must-revalidate and s-maxage. That last one catches people, because s-maxage is the directive you’d naturally pair it with for a CDN.

The .NET building blocks

ASP.NET Core ships four caching layers, and they differ on exactly the questions this part is about:

• IMemoryCache is an in-process cache. It has no memory limit of its own: “The ASP.NET Core runtime doesn’t limit cache size based on memory pressure. The developer is responsible for limiting the cache size.” The same page’s advice is to use expirations and SizeLimit; without them it grows like an unconfigured Redis.
• IDistributedCache is a byte-array get, set, refresh and remove interface over Redis, SQL Server and others. It’s plain cache-aside. Stampede protection is up to you.
• HybridCache combines the two and adds stampede protection: “A HybridCache instance ensures that only one concurrent caller for a given key calls the factory method, and all other callers using the same instance wait for the result of that call.” The same page states the limit: “This coordination doesn’t extend to other HybridCache instances, even if they use the same secondary distributed cache.” Twenty servers means up to twenty rebuilds of one key. That’s the “one fill, others wait” row per server, with the CDN problem from above in miniature.
• Output caching caches whole HTTP responses on the server, with the lock on by default, a one-minute default expiry, and rules that skip authenticated requests and responses that set cookies.

Explain it like I’m ten

A school has one noticeboard by the front door with today’s lunch menu. It’s quicker to read than walking to the kitchen and asking.

• When the board is full, someone has to take a notice down. Take down the one nobody has read for a while (LRU), or the one hardly anyone reads (LFU). Or pin nothing new at all and tell people “no room” (Redis’s default).
• When the menu changes, the kitchen tears the old notice down. But if a pupil copied the old menu, walked to the board slowly, and pinned their copy back up just after the kitchen tore it down, the board is now wrong. Nobody lied. They were just slow. A lease is a ticket from the kitchen saying “you may pin a copy”. Changing the menu cancels all the tickets.
• When the notice falls off at lunchtime, a hundred pupils run to the kitchen at once. You can send one pupil and make the rest wait. You can leave yesterday’s notice up until the new one arrives. Or you can have someone replace it a little early, before it falls.

The precise version

• The board is the cache, the kitchen is the database, and taking a notice down to make room is eviction.
• The slow pupil is a stale set: a cache write carrying a value read before an update, landing after that update’s invalidation.
• The ticket is a lease, and cancelling tickets on a write is what makes a late write-back safe to refuse.
• A hundred pupils running is a stampede. One pupil going is coalescing, leaving yesterday’s notice up is grace or stale-while-revalidate, and replacing it early is probabilistic early refresh.
• Where the analogy breaks: a real cache has thousands of boards, one per server or per CDN location, and fixing the stampede on one board does nothing for the others.

Trade-offs

• Coalescing spares the database and not the clients. Measured: one origin call instead of 135, and 135 clients still waited, 59.75 ms each on average. A slow or failing fill holds everyone behind it.
• Serving stale spares everyone and costs freshness. Measured: no client waited, and 133 answers were served after their expiry. How stale they can get is set by the grace window, not by the lab. Fine for a product page. Not fine for a balance.
• Early refresh spreads the cost thinly but not to zero: 4 origin calls and 4 waiting clients in the median run, 12 in the worst, against 135. And only on traffic that was already flowing before the expiry.
• Eviction policy matters less than cache size. Measured on skewed traffic: growing the cache from about 1,000 keys to about 7,300 cut LRU’s misses from 34.12% to 12.41%. The widest gap between two policies at one size was 8.36 points.
• More maxmemory-samples buys accuracy with CPU. At the default, sampling made no mistakes in the median run while about half the old keys or fewer had to go, and 15.78% when 96% of them did; 64 samples brought that to 0.1%. On a busy, small cache the one-second clock costs more than the sampling does, and more samples don’t fix that.
• Deleting on write is simple and has a race. Leases or versioned keys close it, at the cost of a round trip or a compare-and-set on every fill.
• Write-through keeps the cache warm and pays twice on every write. Write-behind makes writes fast and puts them at risk until they reach the database.
• Purging a CDN is fast and incomplete. Browser and proxy caches keep the old copy. Versioned names are complete, and need a build step.

Common mistakes

• Running Redis as a cache with its default policy. noeviction refuses writes when full. Measured: 5,193 keys held, every later write refused, reads still working, so health checks stay green.
• Choosing volatile-lru for keys that have no TTL. It behaves exactly like noeviction. Measured: 5,164 keys held, and the same error.
• Treating a failed cache write as a failed request. A cache is allowed to be empty. It isn’t allowed to take the application down.
• Adding a lock and calling the stampede fixed. Count the clients who waited, not only the calls to the origin.
• A lock without a timeout. If the one request doing the refill hangs, everyone waits for it. nginx times its lock out after five seconds by default.
• Assuming CDN coalescing is global. It’s per location and per cache key.
• Adding TTL jitter to fix a hot key. Jitter spreads many keys’ expiry. One key has one expiry.
• Reading no-cache as “don’t store”. It’s “revalidate before reuse”. Use no-store for sensitive responses, and don’t rely on either for privacy.
• Assuming two CDNs build the same cache key. CloudFront drops the query string by default. Cloudflare keeps it, and ignores Vary by default.
• Invalidating instead of versioning static assets. The CDN forgets the file and the browser doesn’t.
• Benchmarking a cache with commands batched into scripts. Redis doesn’t evict in the middle of a script, so memory runs past the limit inside each one (13% in our first attempt), and every key a script touches shares one tick of the LRU clock. You’re no longer measuring the cache you configured.

Interview questions

Try to answer each one before opening the model answer.

1. What is a cache stampede and how do you prevent it?

Show a strong answer

• What it is: a popular entry expires, and every request that arrives before the rebuild finishes misses and rebuilds it too. Our lab: about 1.1 requests per millisecond, a 120 ms rebuild, 135 calls to the database.
• The fixes, each with its cost:
• coalescing, which sends one call while everyone else waits;
• serving stale while one request refreshes, so nobody waits but some answers are past their expiry;
• probabilistic early refresh (XFetch), where a few requests rebuild the entry before it expires;
• refresh-ahead, where the cache reloads recently used entries in the background before they expire (Oracle Coherence’s name for it; our lab didn’t measure it).
• A strong answer prices them. Measured: coalescing made 1 origin call but 135 clients waited; serving stale made 1 call, nobody waited, and 133 answers were served after expiry; XFetch made 4 calls and 4 clients waited.
• And names the scope: in-process coalescing only protects one server. HybridCache, Cloudflare and CloudFront all coalesce per instance or per location.

Likely follow-up: “What if the one request doing the rebuild fails?” Then everyone behind it fails or waits. The lock needs a timeout, and the waiters need a fallback. nginx sends waiters to the origin after proxy_cache_lock_timeout, five seconds by default.

2. Cache-aside, read-through, write-through, write-behind: when would you use each?

Show a strong answer

• Cache-aside is the default: the application loads on a miss and deletes on a write. The cache can fail without taking writes with it.
• Read-through is cache-aside moved into a library or the cache itself. It’s cleaner code with the same behaviour.
• Write-through when reads right after writes must hit the cache, for example a profile page right after an edit. Every write pays twice.
• Write-behind when write latency matters more than durability, such as counters or analytics. Vendors name the risk: Apache Ignite says “some updates could be lost due to node failures or crashes”.

Likely follow-up: “Is write-through always consistent?” No. With concurrent writers, cache updates can land in a different order from database writes. Facebook’s memcache paper calls these stale sets.

3. You update the database and then delete the cache key. Can the cache still end up stale?

Show a strong answer

• Yes. A reader misses and reads the old value. The writer updates the database and deletes the key. Then the reader writes its old value into the cache. We forced this on a real Redis: the cache held v1 for 3,600 seconds while the database held v2.
• Deleting first is worse, and Microsoft’s cache-aside guidance says so: a reader can refill the old value between the delete and the update.
• Fixes: a lease, where a miss takes a token and a delete cancels it, so a late write-back is refused; versioned values with compare-and-set; versioned keys; or a short TTL that bounds the damage.
• Why delete rather than set the new value: deletes are idempotent, which the memcache paper gives as its reason.

Likely follow-up: “How often does this happen?” It depends on the gap between a reader’s database read and its cache write, and on how often a write lands inside that gap. Anything that lengthens the gap, like a slow database or a GC pause, widens the window. We didn’t measure a rate, and a forced test can’t give you one.

4. Your Redis cache is full. What happens?

Show a strong answer

• It depends on maxmemory-policy, and the default is noeviction. Writes fail with OOM command not allowed when used memory > 'maxmemory'. Reads keep working.
• volatile-* policies only evict keys with a TTL. With none, they behave like noeviction. We measured exactly that.
• For a pure cache, choose an allkeys- policy. Either LRU or LFU. On skewed traffic at about 3,100 keys, LFU measured 82.45% hits against LRU’s 79.05%.
• maxmemory 0 means no limit at all on 64-bit systems, so an unconfigured Redis grows until something outside it stops it.
• Managed services differ: ElastiCache’s parameter reference lists volatile-lru in its Redis OSS tables, and reserves 25% of memory by default.

Likely follow-up: “How does Redis choose what to evict?” It samples 5 keys and evicts the one idle longest, keeping a pool of 16 good candidates. In our test that made no mistakes in the median run while old keys were plentiful, and got 15.78% of evictions wrong when 96% of the old keys had to go. The bigger surprise was the clock: idle time is kept in whole seconds, so a small cache under heavy traffic has keys it can’t tell apart, and its LRU fell 3.75 points behind an exact one until we slowed the traffic down.

5. LRU or LFU?

Show a strong answer

• LRU keeps what was used recently. It’s good when popularity shifts quickly, and it’s cheap.
• LFU keeps what’s used often. It’s good when popularity is stable and skewed.
• Measured on Zipf traffic with about 3,100 of 20,000 keys cached: LFU 82.45%, LRU 79.05%, random 77.72%. LFU won at every size we tried, on traffic whose popularity never changed.
• LFU needs decay, or yesterday’s hits keep a key forever. Redis decays its counters every minute by default, and starts new keys at a count of 5 so they aren’t evicted immediately.

Likely follow-up: “What would move the hit rate more than the policy?” The cache size relative to the hot set. Going from about 1,000 keys to about 7,300 moved LRU’s miss rate by more than 20 points; the widest policy gap at any one size was 8.36.

6. What’s the difference between no-cache and no-store?

Show a strong answer

• no-cache: the response may be stored, but must be revalidated with the origin before every reuse. Revalidation is cheap with an ETag and a 304 Not Modified.
• no-store: don’t store it at all.
• Neither is a privacy control. RFC 9111 says no-store “is not a reliable or sufficient mechanism for ensuring privacy”.
• Vendors disagree in practice: Google Cloud CDN stores and revalidates no-cache, Akamai doesn’t cache it, and Cloudflare’s own two pages contradict each other.

Likely follow-up: “What would you send for a page with a user’s account details?” Cache-Control: private, no-store, and then rely on TLS and authentication for the actual privacy, not on the header.

7. How do you invalidate content on a CDN?

Show a strong answer

• Prefer versioned names for anything built: app.3f9a1c.js with a year-long max-age. Nothing has cached the new name, so it’s never stale. AWS recommends this over its own invalidation API.
• Purge for content you can’t rename, like HTML pages or API responses. Purge by tag where the CDN supports it, such as Fastly’s surrogate keys.
• Know what purge can’t reach: browsers and corporate proxies. Keep the TTL on HTML short.
• Check the cache key: CloudFront drops query strings by default, so ?v=2 isn’t a new object there unless you configure it.

Likely follow-up: “Why not just set short TTLs on everything?” Then every expiry is a trip to the origin and a stampede opportunity, and you’ve given up most of what the CDN was for.

8. Where would you put caches in a typical web system, and what goes wrong at each layer?

Show a strong answer

• Browser: free and fast. You can’t purge it, so version asset names.
• CDN: absorbs global read traffic. Watch the cache key, Vary handling and per-location stampedes.
• Reverse proxy (Varnish, nginx): whole responses. Coalescing and grace settings decide stampede behaviour, and nginx’s lock is off by default.
• Application cache (Redis, memcached, HybridCache): objects and query results. Watch eviction policy, invalidation races and hot keys.
• In-process: fastest, but one copy per server. Invalidation must reach every copy, and memory must be bounded.
• Database buffer pool: already there. A cache in front can hide a missing index rather than fix it.
• The principle: each layer is a copy, and every copy needs an answer to “how does it learn about a change?”

Likely follow-up: “When would you not add a cache?” When the data changes faster than it’s read, when stale answers are unacceptable and revalidation costs as much as the read, or when the real problem is a slow query that an index would fix.

Sources

• Labs: system-design/checks/part22_caching/redis.py runs against Redis 8.10.1 in a container, pinned by digest. It measures:
• the defaults, read off the running server;
• what each eviction policy does when memory runs out;
• the LRU clock’s resolution and the sampled LRU’s accuracy at four sample sizes;
• miss rates on a Zipf workload at three cache sizes, against an exact LRU, the optimal policy and the first-touch floor;
• the cache-aside race, forced, with and without a lease.

go/ runs the stampede comparison: 3,000 requests at one hot key, four strategies, seven runs each, plus XFetch on traffic that starts only 300 ms before the expiry. – Fielding, Nottingham and Reschke, RFC 9111: HTTP Caching, for the directive definitions, Vary, heuristic freshness, serving stale and invalidation; RFC 9110 §13 for conditional requests, ETag and 304; and Nottingham, RFC 5861, for stale-while-revalidate and stale-if-error – Vattani, Chierichetti and Lowenstein, Optimal Probabilistic Cache Stampede Prevention, PVLDB 8(8), 2015. It gives the stampede definition, the XFetch algorithm and β, and the result that a uniform early-expiry gap is far from optimal. – Nishtala et al., Scaling Memcache at Facebook, NSDI 2013. It covers look-aside caching, delete-on-write and why, and leases for stale sets and thundering herds, with the production numbers. – Redis 8.10.1 source at the tag: config.c for the compiled-in defaults, object.h for the LRU clock, evict.c for the sampling pool and the LFU counter, and redis.conf. Redis docs: key eviction and EXPIRE. – Varnish: grace mode and the varnishd reference. nginx: ngx_http_proxy_module for proxy_cache_lock, proxy_cache_use_stale and proxy_cache_background_update. – CDNs: – Cloudflare: default cache behavior, Cache-Control directives, cache keys and revalidation. – Amazon CloudFront: the cache key, managed cache policies, invalidation versus versioned names, invalidation pricing and request collapsing. – Fastly: request collapsing. – Google Cloud CDN: caching and serving stale content. – Akamai: caching behavior. – Patterns: – Microsoft’s Cache-Aside pattern. – AWS’s ElastiCache caching strategies and caching best practices. – Oracle Coherence 14.1.2 caching data sources. – Apache Ignite external storage. – The ElastiCache parameter reference. – .NET: HybridCache, the caching overview, output caching, IMemoryCache and IDistributedCache

What to remember

• A cache stampede is one popular key expiring under load. Measured: 135 database calls for one expiry.
• Every fix moves the cost. Coalescing: 1 call, 135 clients still waited. Serving stale: 1 call, nobody waited, 133 answers past expiry. Early refresh: 4 of each, on traffic that was already flowing.
• Redis’s default is noeviction. A full cache refuses writes and keeps serving reads.
• volatile- policies do nothing to keys without a TTL.
• Redis’s LRU is sampled on a one-second clock. The sampling is near exact while cold keys are plentiful. In a small, busy cache the clock is the bigger limit: cold keys that come and go within a second all look the same age.
• Cache size moves the hit rate more than the eviction policy does. Count misses, not hits: that’s what the database feels.
• Update the database, then delete the key, and know that a slow reader can still put the old value back. Leases close that gap.
• no-cache means revalidate, not don’t store. Neither no-cache nor no-store is a privacy control.
• When you can’t reliably remove an old copy, change the name so nobody asks for it.

A cache is a copy, and every copy needs an answer to one question: how does it find out that it’s wrong?