Caching: Correctness First

Caching: Correctness First is the discipline of writing down what a cache is allowed to serve before measuring how often it serves anything. A cache is not a performance layer bolted onto a correct system; it is a second copy of your data with weaker guarantees, and the guarantees are the design, which is why Chapter 3's vocabulary comes first.

Key takeaways

• Write the staleness contract before the cache. It names the key class, the maximum acceptable staleness in seconds, who is harmed by staleness, and what happens when the origin is unavailable.
• RFC 9111 states that a cache must not generate a stale response unless it is disconnected or doing so is explicitly permitted by the client or origin server. Permission is a decision, not a default.
• RFC 5861 makes stale an availability tool: stale-while-revalidate returns stale immediately and refreshes in the background, and stale-if-error returns stale instead of a hard error.
• A stampede is a cascading failure. The VLDB 2015 paper computes that an item accessed ten times a second, taking three seconds to recompute, is recomputed thirty times at expiry.
• Eviction policy is an assumption about your access distribution. Redis documents noeviction plus allkeys and volatile variants of LRU, LRM, LFU, random and TTL, and picking one is a claim about how your keys are read.

Read this after Chapter 3, whose guarantee vocabulary is what a staleness contract is written in, and after Chapter 5, since a cache usually sits exactly on the boundary that chapter drew. Chapter 9 handles what happens when the origin behind the cache is gone entirely, so this chapter stops at what the cache may serve rather than at how much of the system it can hold up.

A cache goes in to relieve a hot query. Hit rate reaches 94 percent by the second day and the origin load drops by an order of magnitude.

A month later a customer changes their billing address, sees the old one on the invoice preview, and calls support. Nobody can say how long the wrong value was visible, because nobody wrote down how long it was allowed to be visible.

The cache worked exactly as configured. Its configuration was never a decision.

A staleness contract is a written promise

The artifact this chapter exists to produce is short and it has four fields.

The key class, meaning which data this applies to. The maximum acceptable staleness, in seconds, as a number somebody outside engineering has agreed to. Who is harmed if the value is stale, named as a role rather than as the system. And the behaviour when the origin is unavailable, which is a separate decision from the freshness one and is usually forgotten.

Four fields per key class. Six or eight key classes in a normal product. It fits on one page, and that page is what turns a support ticket from a mystery into an expected behaviour.

Note that this is Chapter 3's guarantee sentence applied to a copy. Same discipline, same reason: an unstated guarantee is not a guarantee, it is a hope with a hit rate.

Freshness lifetime is computed, not guessed

For anything travelling over HTTP, the rules are already written down, and reading them saves inventing a worse version.

RFC 9111, published by the IETF in June 2022 and obsoleting RFC 7234, specifies how a cache computes freshness lifetime. It uses s-maxage if present, otherwise max-age, otherwise the Expires field minus the Date field, and otherwise a heuristic the cache chooses. That precedence order is the whole mechanism. Most misconfigured caches set a directive that a later rule overrides.

The specification is equally precise about staleness. A cache must not generate a stale response unless it is disconnected, or unless doing so is explicitly permitted by the client or the origin server. The must-revalidate directive goes further. Once a response is stale it may not be reused until validation succeeds.

Read that as a design contract rather than as protocol trivia. The standard already assumes that serving stale is a permission somebody grants, and your internal cache should work the same way even when it is not speaking HTTP.

Stale becomes an availability tool when you say so

There are two directives whose entire purpose is to convert staleness from a defect into a resilience mechanism, and they are underused inside private systems.

RFC 5861, published in May 2010 as an informational document, defines stale-while-revalidate and stale-if-error. The first lets a cache return a stale response immediately while revalidating in the background. The user never waits for the recomputation. The second lets a cache return stale content instead of a hard error, which improves availability when the origin is unreachable.

Those two directives answer the fourth field of the staleness contract. When the origin is down, is a five-minute-old value better than an error page. For a product catalogue the answer is almost always yes. For an account balance it is almost always no. That difference is a business decision and it belongs in the record.

The important part is that both are opt-in. A cache does not get to decide it prefers availability, and neither does an engineer at two in the morning without a written contract to point at.

The stampede is a cascading failure

Expiry is the dangerous moment, and the standard reference makes the cost calculable rather than vague.

Vattani, Chierichetti and Lowenstein, in Optimal Probabilistic Cache Stampede Prevention, published in the Proceedings of the VLDB Endowment in 2015, describe the failure as cascading and give the arithmetic. If the cache item is accessed ten times per second, and recomputation of the item takes three seconds, then thirty requests will recompute the item.

Redo that with your own numbers first. An item read 400 times a second whose recomputation takes 800 milliseconds produces 320 concurrent recomputations at the instant it expires. The origin sees a step change from nearly zero load to 320 identical expensive queries. That is the shape that saturates a connection pool.

The mechanism is worse than the arithmetic suggests. Saturation slows the recomputation, which extends the window, which admits more duplicate requests. That is the positive feedback loop Chapter 9 treats properly.

Locking is not the fix

The instinctive answer is a lock: the first request recomputes, everybody else waits. The paper is specific about why this is unsatisfying.

Its critique of locking is threefold. Locking doubles the number of writes, because the lock itself has to be written. It leaves the other requests with nothing to return while they wait. And it is not fault tolerant. A holder that dies mid-recomputation leaves everybody blocked on a lock nobody will release.

Their recommended approach is probabilistic early expiration. Each read has a small chance of recomputing the value slightly before it actually expires, so recomputations spread out rather than colliding. The paper shows an exponential distribution is optimal for this, and that its controlling parameter need not depend on the request rate. That is what makes it practical to configure once.

The design instruction that follows is one line. Never let a hot key expire at a single instant. Spread the recomputation rather than serialising it.

Eviction policy is a claim about your access pattern

The last correctness question is what leaves the cache when it is full, and the answer encodes an assumption most teams have never stated.

Redis documents the choice explicitly. Its key eviction page, fetched on 29 July 2026, lists noeviction plus allkeys and volatile variants of LRU, LRM, LFU, random and TTL. Under noeviction the server returns an error rather than dropping data. Its LRU is an approximation that samples a small number of keys at random, tunable with maxmemory-samples. Its LFU uses a probabilistic counter with a decay period, so a key that was hot last month does not stay protected forever. Least recently modified, added in Redis 8.6, updates its timestamp only on writes rather than on reads.

Each is a different bet. LRU bets that recency predicts future access, which holds for a power-law read distribution. LFU bets that long-run frequency predicts it, which holds better for a stable hot set with occasional scans through cold data. LRM bets that modification recency matters more than read recency, which suits a read-heavy set where stale-by-age is the real concern.

Choosing noeviction is also a choice. It is a defensible one. It converts a silent correctness risk into a loud capacity error, which is frequently the trade you want.

A worked example, composited and labelled

The details here are composited from ordinary production shapes rather than one system, and the shape is exact.

An invoicing product caches four things. A currency conversion table, a customer's billing profile, a rendered invoice preview and a permissions lookup used on every request.

The contracts differ sharply, which is the point. The conversion table tolerates an hour of staleness and harms nobody at that scale. It should serve stale on origin error, since a one-hour-old rate beats a failed page. The billing profile tolerates zero staleness for the customer who just edited it and sixty seconds for everybody else, so it is invalidated on write and read through afterwards. The invoice preview is derived from both, so its staleness is the sum of theirs. That is the calculation teams skip. The permissions lookup tolerates thirty seconds and must never serve stale on error, because a stale allow is a security decision.

Two things fall out. The preview cannot promise better freshness than its worst input, and the permissions cache needs noeviction with an alert rather than silent LRU pressure. Both constraints go in the record, along with the reversal signal: any key class whose observed staleness exceeds its contract for a full day.

The objection: our data changes too often to cache

This is the most common objection and it is usually a description of a missing contract rather than of the data.

Data that changes every second can still be cached for one second. At 2,000 requests per second that single second removes 1,999 origin reads. The question was never whether the data is stable. It is whether anybody is harmed by a value up to one second old, and for most reads in most products the honest answer is no.

The genuine version of the objection is narrower and worth respecting. Some values must never be stale by any amount, because a stale read authorises something: a permission, a credit limit, a stock level being sold from. Those do not belong behind a time-based expiry. The contract is what identifies them.

So the objection resolves into the artifact. Write the four fields per key class and the uncacheable classes name themselves. What remains is the majority of your read traffic. Nishtala and colleagues reported at NSDI in April 2013 that a memcache tier can be scaled to handle billions of requests per second, holding trillions of items in front of a database of record. That is the upper bound on what this technique is worth.

Chapter summary

A cache is a second copy of your data with weaker guarantees, so the design artifact is a staleness contract with four fields per key class: which data, the maximum acceptable staleness in seconds, who is harmed by a stale value, and the behaviour when the origin is unavailable. RFC 9111, published in June 2022, computes freshness lifetime from s-maxage, then max-age, then Expires minus Date, then a heuristic, and states that a cache must not generate a stale response unless it is disconnected or doing so is explicitly permitted, with must-revalidate forbidding reuse until validation succeeds. RFC 5861 turns staleness into an availability tool through stale-while-revalidate, which serves stale and refreshes behind the request, and stale-if-error, which serves stale rather than failing, and both are opt-in permissions rather than defaults. Expiry is the dangerous instant: the VLDB 2015 stampede paper computes thirty recomputations for an item read ten times a second that takes three seconds to rebuild, and its critique of locking is that locking doubles writes, leaves other requests with nothing to return, and is not fault tolerant, so probabilistic early expiration with an exponential distribution is preferred and its parameter need not depend on the request rate. Eviction policy encodes an unstated assumption about the access distribution, and Redis documents noeviction plus allkeys and volatile variants of LRU, LRM, LFU, random and TTL, with approximated LRU tuned by maxmemory-samples. The chapter's decision is one contract per key class with an observed-staleness threshold that reverses it.

Caches absorb read load and do nothing for writes that arrive faster than they can be finished. That is a queueing problem with its own vocabulary, its own signals and its own failure mode, and it is where the design either sheds work deliberately or falls over. Chapter 7 is Queues, Backpressure, and Fair Scheduling.