Caching without lying: invalidation, stampedes and cold starts

A cache is the cheapest performance win in most systems and the most common source of data that is quietly wrong. Adding one takes an afternoon. Keeping it consistent with the database, stopping it from collapsing the database when it empties, and knowing what happens when it goes down takes considerably longer.

This article covers the main caching patterns and what each one promises, why invalidation is hard even when you delete on every write, how a single expiring key can take down a database, and what happens when a system can no longer survive without its cache.

What a cache buys, and what it costs

A cache trades freshness for latency and load. A Redis or Memcached lookup takes a fraction of a millisecond inside a data centre; the query it replaces might take tens of milliseconds and use a database connection. With a hit rate h, the database sees only the misses:

That formula is the whole case for caching, and also the warning. At a 99% hit rate the database serves 1% of reads. If the hit rate drops to 90%, its load goes up tenfold. The hit rate is not a performance metric to watch casually; it is a capacity input.

The cost is that every cached value is a second copy of the truth, and second copies drift. The question to answer for each cache is not “is it consistent?” (it isn’t) but “how stale can this be, for how long, and who notices?”. A product description that is a minute out of date is fine. A permission check that is a minute out of date means a revoked user still has access.

Cache-aside, read-through, write-through

The patterns differ in who talks to the database and when the cache is updated:

• Cache-aside (lazy loading). The application checks the cache; on a miss it reads the database and fills the cache. On a write it updates the database and then deletes the cached key. This is the most common pattern, and the cache stays small, holding only what was actually read.
• Read-through. The same thing, but the cache library or service does the loading. The application only ever talks to the cache.
• Write-through. Every write goes to the cache and the database together, so the cache is always warm for recently written data. It costs write latency and fills the cache with data nobody may read.
• Write-behind (write-back). Writes go to the cache and are flushed to the database later, in batches. It is fast and absorbs write bursts, but a cache node that dies before flushing loses acknowledged writes. It is rarely the right choice for data you can’t afford to lose.

On a write, cache-aside deletes the key rather than setting it to the new value. With two concurrent writers, “set” can leave the older value in the cache: A writes the database, B writes the database, B sets the cache, A sets the cache. Deleting is idempotent and order-insensitive, and the next read reloads whatever the database now holds.

Invalidation and its races

Deleting on write narrows the window but doesn’t close it. The remaining race needs a slow reader: it misses, reads the old value from the database, stalls, and then writes that old value into the cache after the writer has already deleted the key.

The window is small, but at scale small windows happen every day. The defences, roughly in order of how often they are used:

• A TTL on everything. Expiry is the backstop that bounds how long any bug, race or missed invalidation can last. A cache without TTLs has no upper bound on staleness.
• Leases. Facebook’s memcache (Nishtala et al., NSDI 2013) gives a client a lease token when it misses. A delete invalidates outstanding leases, and a set is only accepted with a valid token, so the stale set in step 5 is rejected. Leases also limit how often a key can be rebuilt, which helps with the next section’s problem.
• Versioned values. Store a version or update timestamp with each value, and only accept a set that is newer than what is there. Redis can enforce this with a short Lua script.
• Delete twice. Some teams delete again a second or two after the write, catching most slow readers. It is a probabilistic patch, not a fix.

A second class of bug comes from the delete never happening at all. The application commits the database write, then crashes or times out before deleting the key. That is the dual-write problem: two systems updated without a transaction spanning them. The robust answer is to drive invalidation from the database’s own change log. Facebook’s mcsqueal daemons tail the MySQL commit log and issue the deletes; a change-data-capture pipeline with Debezium does the same with Postgres or MySQL. Every committed write then produces an invalidation, whatever happened to the process that made it.

Stampedes

A cache stampede (also called dogpiling or a thundering herd) happens when a popular key expires. Every request that arrives before someone refills it misses, and every miss queries the database for the same value. A key read 2,000 times a second with a rebuild that takes 800 ms produces 1,600 identical queries per expiry, and those queries make the database slower, so the rebuild takes longer and the window grows.

Three techniques, often combined:

• Request coalescing (single-flight). Within a process, concurrent misses for the same key share one in-flight load; Go’s singleflight package is the reference implementation. The database sees one query per process instead of one per request. To get down to one query in total, add a short distributed lock or lease, and have the losers wait briefly or serve a stale value.
• Serve stale while revalidating. Keep values past their soft expiry and refresh them in the background while serving the old value. HTTP has this as a standard directive, stale-while-revalidate (RFC 5861), and most CDNs support it.
• Probabilistic early expiration. Each reader independently decides to refresh a little early, with a probability that rises as expiry approaches. Vattani, Chierichetti and Lowenstein (VLDB 2015) showed that this rule, called XFetch, is optimal in their model:

Here δ is how long the last rebuild took and β (default 1) tunes how eager the refresh is. Since ln(rand()) is negative, the left side is “now plus a random exponential head start”. Slow-to-rebuild values start refreshing earlier, and at high request rates one request almost always refreshes before the key actually expires.

Stampedes also happen without any single hot key, when many keys expire together. A cache warmed in bulk after a deploy, with every TTL set to exactly one hour, will expire all at once an hour later. Add jitter to every TTL, for the same reason retries need jitter.

When the cache becomes load-bearing

Caches are usually introduced as an optimisation: if it’s down, things get slower. Over time the database is sized for the load that gets past the cache, and the optimisation becomes a dependency. If the cache empties, the database receives its full uncached load, which it was never sized for, and falls over.

This is a textbook metastable failure. A cache cluster restart, a deploy that changes the key format, or a failover to a cold replica empties the cache. The database slows down under the miss traffic, so cache fills take longer, so the hit rate stays low. The system can stay in that state long after whatever emptied the cache has recovered.

Mitigations that help: replicate cache nodes so losing one doesn’t empty a shard; use consistent hashing so adding or removing a node only moves a fraction of keys (see the sharding article); version key names so a deploy can switch gradually rather than flipping every key at once; and cap concurrent database queries from the cache-fill path, so a cold cache degrades to slow responses rather than a dead database.

Hot keys, negative caching and other details

• Hot keys. A distributed cache shards keys across nodes, so one very popular key lands on one node and can saturate it: the celebrity’s profile, the homepage configuration. Keep a small in-process cache with a short TTL in front of the shared one, or replicate the key under several names (key#0 to key#7) and read one at random.
• Negative caching. Cache “not found” too, with a shorter TTL. Otherwise requests for IDs that don’t exist, whether from a bug or an attacker, miss every time and go straight to the database.
• Cache keys must include everything the value depends on. Locale, permissions, feature flags, API version. A response cached without the user’s role in the key will eventually serve an admin view to someone who isn’t one.
• Measure the right things. Hit rate per key prefix, not just overall; eviction rate, which tells you the cache is too small; and the latency of misses, which is what users feel when it goes wrong.

A careful cache-aside read

A cache-aside helper with the protections from this article: single-flight per process, XFetch early refresh that keeps serving the current value while one caller rebuilds, jittered TTLs, and a cache outage treated as a miss rather than an error.

// Cache-aside reads with three protections: single-flight (one rebuild per key per
// process), probabilistic early refresh (XFetch), and jittered TTLs. The cache is
// any key-value store; values are stored with how long they took to compute.
type Entry<T> = { value: T; delta: number; expiresAt: number }; // delta: rebuild time, ms
interface Store {
  get<T>(key: string): Promise<Entry<T> | undefined>;
  set<T>(key: string, entry: Entry<T>, ttlMs: number): Promise<void>;
}

const inflight = new Map<string, Promise<unknown>>();

export async function cached<T>(
  store: Store, key: string, ttlMs: number, load: () => Promise<T>, beta = 1,
): Promise<T> {
  const entry = await store.get<T>(key).catch(() => undefined); // a cache outage is a miss, not an error
  // XFetch: refresh early with a probability that rises as expiry nears, scaled by
  // how slow the rebuild is. -log(rand) is exponential, so one caller usually goes first.
  const early = entry && Date.now() - entry.delta * beta * Math.log(Math.random()) >= entry.expiresAt;
  if (entry && !early) return entry.value;

  // Single-flight: concurrent misses for the same key in this process share one load.
  let pending = inflight.get(key) as Promise<T> | undefined;
  if (!pending) {
    pending = (async () => {
      const start = Date.now();
      const value = await load();
      const ttl = ttlMs * (0.9 + Math.random() * 0.2); // ±10% jitter so keys filled together don't expire together
      await store.set(key, { value, delta: Date.now() - start, expiresAt: Date.now() + ttl }, ttl).catch(() => {});
      return value;
    })().finally(() => inflight.delete(key));
    inflight.set(key, pending);
  }
  if (!entry) return pending;
  // During an early refresh, serve the current value rather than wait for the new one;
  // a failed refresh is harmless, since the value is still valid until it expires.
  pending.catch(() => {});
  return entry.value;
}

References

1. Nishtala, R. et al. (2013). Scaling Memcache at Facebook. NSDI. usenix.org
2. Vattani, A., Chierichetti, F. & Lowenstein, K. (2015). Optimal Probabilistic Cache Stampede Prevention. VLDB. vldb.org
3. Nottingham, M. (2010). RFC 5861: HTTP Cache-Control Extensions for Stale Content. IETF. rfc-editor.org/rfc/rfc5861
4. Bronson, N., Aghayev, A., Charapko, A. & Zhu, T. (2021). Metastable Failures in Distributed Systems. HotOS. doi:10.1145/3458336.3465286
5. Go. golang.org/x/sync/singleflight. pkg.go.dev/golang.org/x/sync/singleflight
6. AWS. Caching Best Practices and Database Caching Strategies Using Redis (whitepaper). aws.amazon.com/caching/best-practices
7. Kleppmann, M. (2017). Designing Data-Intensive Applications, ch. 11: Stream Processing (change data capture). O’Reilly. dataintensive.net