Advanced System Design Fundamentals
Vote

0% completed

​

Invalidation Strategies

  1. There Are Only Three Ways to Stop Serving a Stale Value
  1. Expiry Is a Promise About Time, and Nothing Else
  1. Writing Through the Cache
  1. Why Deleting Beats Updating
  1. Event-Driven Invalidation
  1. The Senior Decision

1. There Are Only Three Ways to Stop Serving a Stale Value

Cache invalidation has a reputation for being hard, and that reputation hides how few options there actually are. Once a value is in a cache and the underlying data changes, you have exactly three options.

  • Let it expire. Do nothing on write, and rely on the entry's expiry time to remove it.
  • Update it. Write the new value into the cache at the same time you write it to the store.
  • Delete it. Remove the entry on write, so the next read misses and repopulates.

Everything else in this lesson is a variation on those three, or a decision about who performs them and when. The difficulty is not in the mechanisms. It is that each one makes a different promise about what a reader can observe, and those promises are easy to assume, while a wrong assumption is hard to undo later.

So the question to carry through this lesson is not "which strategy is best." It is "what is the worst thing a reader can see under this strategy, and can the product tolerate it?"

The entire design space, and the promise each option makes to a reader.
The entire design space, and the promise each option makes to a reader.

2. Expiry Is a Promise About Time, and Nothing Else

An expiry time makes exactly one guarantee: no value is served more than that long after it stopped being true. It says nothing about what happens in between.

That sounds weak, and yet it is strangely powerful, for three reasons.

  • It is self-healing. Every other mechanism in this lesson can fail to run. A delete can be lost, an event can be dropped, a writer can crash between two steps. Expiry requires nothing of the writer at all, so it is the only mechanism that recovers from the others failing.
  • It bounds the damage from every bug you have not found yet. Whatever goes wrong with your invalidation logic, the window is capped.
  • It costs nothing to operate. No extra write path, no event stream, no ordering concerns.

Which is why the rule to carry out of this lesson is that every cached entry gets an expiry time, including entries you also invalidate explicitly. Invalidation is an optimization that shortens the window. Expiry is the guarantee underneath it. Teams that treat explicit invalidation as a replacement for expiry discover the difference during an incident, when something stops invalidating and a wrong value stays cached indefinitely.

The real decision with expiry is the length, and that is a product question rather than an engineering one. Sixty seconds of staleness is fine for a product catalog and unacceptable for a permission check.

Where the write goes, and what each arrangement costs when one of the two systems is unavailable.
Where the write goes, and what each arrangement costs when one of the two systems is unavailable.

3. Writing Through the Cache

The second family writes to the cache as part of the write path. Three arrangements come up.

  • Write-through. The write goes to the cache and the store together, synchronously, before the writer is told it succeeded. Reads after a write always see the new value, and every write now pays both latencies and depends on both systems being available.
  • Write-behind. The write goes to the cache immediately and to the store shortly afterward, asynchronously. Writes are fast and the cache is authoritative for a window, which means a cache failure in that window loses data that the application believes it has written. This is a durability decision disguised as a caching decision, and it belongs only where losing recent writes is genuinely acceptable.
  • Write-around. The write goes to the store only, and the cache entry is left alone or removed. Nothing is cached until something reads it, which suits data that is written far more often than it is read.

The first two share one difficulty, and it is the reason the next section exists. Writing to two systems is a dual write, and no ordering of two writes to two systems is safe under failure. Whichever you do first, a crash between them leaves the pair disagreeing. Write-through narrows that window without removing it. Write-around avoids it for the value itself, and still has to remove whatever is already cached, which is the same problem in a smaller form.

The same two writers, twice. Only one of these arrangements can end up permanently wrong.
The same two writers, twice. Only one of these arrangements can end up permanently wrong.

4. Why Deleting Beats Updating

Given a choice between writing the new value into the cache and simply removing the entry, remove it. The reason is concurrency, and it is worth working through because it is the most common source of permanently wrong cached data.

Two writers, updating. Writer A sets the value to 1. Writer B sets it to 2. Both write to the store and both write to the cache, but the two cache writes arrive in the opposite order to the store writes, which is entirely possible across a network. The store now holds 2 and the cache holds 1, and nothing will correct it until the entry expires.

The same two writers, deleting. Both remove the entry. The order does not matter, because both operations have the same effect. The next read misses and loads whatever the store currently holds. The worst outcome is one extra read.

That difference is the whole argument. Deletion is idempotent and does not care about order. Update is neither. Any mechanism that can deliver operations out of order or more than once, which includes every message queue and every retry, is far safer carrying deletions than values.

The race that deletion does not fix. There is one more sequence, and it catches careful teams:

  1. A read misses the cache and loads value 1 from the store.
  2. Before that reader writes to the cache, a writer stores value 2 and deletes the cache entry.
  3. The reader now writes value 1 into the cache, where it stays until expiry.

The cache now holds a value that the store never had after the write. Four fixes exist, in increasing order of effort.

  • Keep expiry times short, so the window in which this can happen is bounded.
  • Write to the cache only when the entry is still absent, rather than overwriting whatever is there.
  • Delete a second time after a short delay, so a late write is removed shortly after it lands.
  • Take a short lease on the key during a miss, so only the lease holder may populate it.

Most systems take the first two. The important part is knowing the race exists, because the symptom is one wrong value that persists while everything else behaves.

Every step here is correct, and the cache still ends up holding a value the store never had.
Every step here is correct, and the cache still ends up holding a value the store never had.

5. Event-Driven Invalidation

The arrangements above put the invalidation in the writer's code path, which means every writer must remember to do it. The alternative is to derive invalidation from the data change itself.

The usual form reads the database's own change stream, through change data capture, and turns each committed row change into a cache deletion. Several properties follow from that, and they are the reason this approach is worth the infrastructure.

  • The writer no longer has to participate. A change made by a migration, an administrative console, or a service you did not write still invalidates correctly, because the invalidation derives from the committed change rather than from the code that made it.
  • It fires after commit. Invalidating before a transaction commits is a classic source of a repopulated stale entry, and reading the committed stream removes that whole class of mistake.
  • Delivery is at least once, so a consumer that restarts can replay changes it has already applied. This is exactly why the previous section matters. Replaying a deletion is harmless, because deleting twice is deleting once. Replaying an older value over a newer one is not, which is why the stream carries deletions rather than values.

The costs are a system to operate, a lag between commit and invalidation measured in the hundreds of milliseconds or worse, and a new way for the cache to drift if the consumer stalls. The last of those is the strongest argument for keeping expiry underneath: a stalled consumer degrades you to the expiry guarantee rather than to serving a wrong value forever.

Deriving invalidation from the committed change rather than from the code that made it.
Deriving invalidation from the committed change rather than from the code that made it.

6. The Senior Decision

Work it in this order, because each question eliminates options rather than merely ranking them.

  • How wrong can a reader be, and for how long? This is a product question with a numeric answer. Without it you cannot choose, and most arguments about caching strategy are actually arguments about this unanswered question.
  • Is a stale read merely inconvenient, or is it incorrect? A slightly old view count is inconvenient. A slightly old permission or price is incorrect, and that moves you out of expiry-only immediately.
  • Who writes the data? If writes come from several services and from humans with database access, writer-side invalidation will be incomplete and the change stream is the honest answer.
  • What is the fallback when the mechanism fails? If the answer is not an expiry time, there is no fallback.

The default that survives scrutiny is cache-aside reads, deletion rather than update on write, and an expiry time on everything as the floor. Add the change stream when there are too many writers, or too many kinds of writer, to be trusted. Add write-through only where a read immediately after a write must see the new value, and accept that you have coupled the two systems to do it.

What the interviewer is scoring: "how would you invalidate this cache?" is testing whether you reach for a mechanism or for a requirement. Reaching for a mechanism immediately is the mid-level answer. The senior move is to ask how stale a read may be before anything is chosen, then to name deletion rather than update and to say why, which is the concurrency argument rather than a preference. Expect two follow-ups. "What happens if the invalidation is lost?" has one acceptable answer, which is the expiry time underneath. "Can a cache entry be wrong even after a correct delete?" is the stale-set race, and being able to describe that sequence unprompted is a strong signal that you have debugged a cache rather than only configured one.

Flashcards Review

The three options once a cached value goes out of date

1 / 22

Reading Progress

0%

Vote for new content

On This Page

  1. There Are Only Three Ways to Stop Serving a Stale Value
  1. Expiry Is a Promise About Time, and Nothing Else
  1. Writing Through the Cache
  1. Why Deleting Beats Updating
  1. Event-Driven Invalidation
  1. The Senior Decision