Cache invalidation is a distributed systems problem (revision 1)

Every team I have joined has had a cache, and every team has eventually been surprised by it. The surprise is always the same shape: something was correct, then it was not, and nothing in the logs said why.

Comment

nothing in the logs said why

The logs never say why because "why" is a semantic question and logs are a syntactic record. We eventually added a stale-read counter to the read path specifically so that this question had an answer.

Mira Okonkwo3 years agolink

Was this worth reading?

Reply

Report

The single-machine version

On one machine, cache invalidation is a function call and you can stop thinking about it. You hold a reference to the map, you call delete, and the next reader either sees the new value or blocks until it is written. There is a happens-before edge and it is obvious.

Correction · accepted

There is a happens-before edge

Small correction: this is only true if the reader and the map are actually ordered. Under a per-key lock you have the edge; under a striped lock you have an edge only for keys in the same stripe, which is a weaker guarantee than it looks.

Mira Okonkwolast yearlink

Was this worth reading?

Reply

Report

typescript

                      
                          class LocalCache {
  private entries = new Map<string, Entry>();
  private hits = 0;
  private misses = 0;

  get(key: string): Entry | undefined {
    const entry = this.entries.get(key);
    if (!entry) { this.misses++; return undefined; }
    if (entry.expiresAt < Date.now()) { this.entries.delete(key); this.misses++; return undefined; }
    this.hits++;
    return entry;
  }

  invalidate(key: string) { this.entries.delete(key); }
}
                          class LocalCache {
  private entries = new Map<string, Entry>();
  private hits = 0;
  private misses = 0;

  get(key: string): Entry | undefined {
    const entry = this.entries.get(key);
    if (!entry) { this.misses++; return undefined; }
    if (entry.expiresAt < Date.now()) { this.entries.delete(key); this.misses++; return undefined; }
    this.hits++;
    return entry;
  }

  invalidate(key: string) { this.entries.delete(key); }
}

A cache with an explicit invalidation call. Correct, and trivially so.

This works because the map and the reader are in the same process, ordered by one thread or guarded by one mutex. When invalidate returns, every subsequent get sees the new value. You can reason about it locally.

Where it stops being local

Now put the cache in Redis and the reader in fifty pods, and the guarantee quietly evaporates. DEL returns. The writer moves on. But a pod that read the key eight milliseconds ago still has it in a local LRU with a five-minute TTL, and that pod will happily serve the stale value for five more minutes.

You have not fixed a bug. You have introduced a distributed systems problem and given it a friendly name. The tell is that nobody can now state what the system is allowed to get wrong — and that was the entire value of the local version.

Extension

a friendly name

This is also why the local-cache version survives in so many codebases: it is the only version where correctness is *obvious*, and obviousness is a real engineering property that people will trade performance to keep.

Sam Reyes2 years agolink

Was this worth reading?

Reply

Report

Staleness against TTL, for a key changing every 10s

TTL20s

39% of reads can be served stale at a 20s TTL.

Assumes independent (Poisson) changes and exponential decay on read. Real change is burstier, so expect worse than this.

Three strategies, and what each one costs

There are exactly three coherent answers, and every production cache is some mixture of them. Knowing which mixture you are running is most of the work.

Strategy	Freshness	Cost	Fails when
Write-through	Immediate on the writer side	Write latency doubles	The reader cannot see the writer's write — you need a barrier
Invalidate + TTL	Bounded by TTL	Cheapest to run	You accept staleness and must say so out loud
Push to all readers	Immediate	O(replicas) per write	A replica is down, or lagging, or you forgot to subscribe

The third strategy is the one people reach for and then discover is a distributed system with a fan-out and no backpressure. If you push invalidations, you are building a broadcast protocol. You now have to think about what a subscriber does when it reconnects and has missed forty messages.

The honest answer

The interactive above assumes a key whose value changes on a Poisson-ish process. Real change is bursty — deploys, backfills, a customer uploading in bulk. Under bursty load the expected staleness is far worse than the TTL suggests, and the only defence is to make invalidation a first-class write-path event rather than hoping the timer covers you.

Pick invalidate-plus-TTL, set the TTL from the rate of change of the data, and write the TTL down next to the data. Then tell the people reading through the cache what window of staleness they are inside, because they will otherwise assume they are looking at truth.

The TTL is not a cache policy. It is a promise about how wrong you are willing to be, made in a config file that nobody reads.

The corollary, which cost me a very long week: a TTL is not a cache policy, it is a documented error budget. If you cannot write down the number, you do not have a cache, you have a source of intermittent lies.

Everything else is a way of deferring that conversation.

Cache invalidation is a distributed systems problem

The single-machine version

Where it stops being local

Three strategies, and what each one costs

The honest answer

How deep do you want this?

Revision history

Marginalia

Ask this article

Try to break this argument

Where this sits

When this changes