Cache-Aside Consistency: Prevent Stale Overwrites

Cache-aside is attractive because the application controls a simple protocol. A read checks the cache first. On a miss, it reads the database and places the result in the cache. A write updates the database and then invalidates or refreshes the cache.

Each step is easy to describe. Concurrency makes the combined behavior less obvious.

A delayed cache fill can publish an older database value after a newer write has already completed. The database remains correct, yet later readers can receive stale data from the cache. This article develops the race precisely and presents practical designs that keep an old fill from replacing a newer state.

Start with the basic protocol

A common cache-aside read looks like this:

get(key):
    cached = cache.get(key)
    if cached exists:
        return cached

    value = database.get(key)
    cache.set(key, value, ttl)
    return value

A common write path uses invalidation:

update(key, change):
    database.update(key, change)
    cache.delete(key)

The database is the source of record. The cache is disposable derived state.

That arrangement handles many workloads well, but the two protocols are not atomic with each other. A cache miss can overlap a database update.

The stale-fill race

Consider a product with price 100.

Request A begins a read:

  1. A misses the cache.
  2. A reads 100 from the database.
  3. A pauses before filling the cache.

Request B then updates the price:

  1. B writes 120 to the database.
  2. B deletes the cache entry.
  3. B completes successfully.

A resumes and stores the value it read earlier:

time --->

A: cache miss -- DB reads 100 ---------------- cache set 100
B:                    DB writes 120 -- delete cache

The final database value is 120, but the final cache value is 100.

The invalidation was correct at the instant it ran. The later stale fill undid its effect.

This is a concurrency bug, not merely a short time-to-live issue. A shorter TTL limits the duration of bad data but does not remove the race.

Treat a cache fill as a conditional publication

The unsafe protocol assumes that any value obtained from the database is suitable for publication later. That assumption stops being valid once concurrent writes can advance the record.

A stronger model is:

Publish a value only if the cache can establish that no newer state has superseded it.

There are several ways to provide that evidence. The best choice depends on the database, cache capabilities, update rate, and acceptable consistency level.

Option 1: Carry a monotonic version

If each database record has a version that increases on every committed update, cache entries can include it.

database row:
    value = 120
    version = 42

cache entry:
    value = 120
    version = 42

A fill writes only when its version is newer than the cached version, or when no entry exists.

put_if_newer(key, candidate):
    current = cache.get(key)

    if current does not exist:
        cache.set(key, candidate)
        return

    if candidate.version > current.version:
        cache.set(key, candidate)

The comparison and write must be atomic. A script, compare-and-set operation, transaction, or cache-specific conditional primitive can provide that property.

Now imagine A read version 41 and B committed version 42. If B places version 42 in the cache before A resumes, A cannot replace it with version 41.

Versioned values turn freshness into an ordering rule instead of a timing guess.

Invalidation needs a version too

A plain delete can still leave a gap. If B only deletes the entry, A may later see an empty cache and publish version 41.

One approach is to store a version marker even when the value itself is absent:

cache state:
    minimum_version = 42
    value = absent

A fill carrying version 41 is rejected. A later read can fetch version 42 and populate the value.

Another approach is for the write path to refresh the cache with the committed version rather than delete it. That removes the empty interval, though it adds cache work to the write path.

Option 2: Use generation tokens

Sometimes the cached object has no convenient database version. A separate generation token can guard fills.

Before loading, a reader captures the current generation:

generation = cache.get_generation(key)
value = database.get(key)

Before publishing, it checks that the generation has not changed:

if cache.get_generation(key) == generation:
    cache.set(key, value, ttl)

A writer advances the generation after committing its database change.

The check and cache set must again be atomic. Otherwise the generation can change between the check and the set.

Conceptually, the generation says, “This fill belongs to cache epoch 17.” Once a writer advances the key to epoch 18, work started in epoch 17 is no longer eligible to publish.

This technique is useful when the application needs ordering for cache work without exposing a database row version.

Option 3: Serialize fills for a key

A per-key lock can prevent several cache fills and updates from publishing in conflicting order.

A reader may:

  1. miss the cache;
  2. acquire a lock for the key;
  3. check the cache again;
  4. load the database if still absent;
  5. fill the cache;
  6. release the lock.

The second cache check matters. Another request may have filled the entry while this request waited for the lock.

If writers participate in the same coordination protocol, stale fills can be excluded.

This approach can be effective, but distributed locking adds failure cases: lock expiry, process pauses, network delays, and ownership mistakes. A lock with a lease also needs protection against an old holder acting after its lease has expired.

For that reason, ordering tokens are often safer than relying on lock ownership alone.

Fencing tokens strengthen leases

A fencing token is a monotonically increasing number issued when a participant obtains permission to act.

Suppose one worker receives token 51, pauses for a long time, and loses its lease. A second worker receives token 52 and completes. If the first worker later resumes, downstream state rejects token 51 because token 52 has already been observed.

The important property is enforced at the resource receiving the write. Merely checking that a lock appears valid before a cache set leaves a timing window.

Fencing converts “I think I still own the lock” into “the receiver can reject operations older than the newest accepted token.”

Refreshing after writes has trade-offs

Instead of deleting the cache entry after a database update, a writer can store the newly committed value.

update(key, change):
    committed = database.update(key, change)
    cache.put_if_newer(key, committed)

This can reduce immediate misses and makes a fresh version available to reject delayed fills.

It also creates a dual-write concern. The database commit can succeed while the cache update fails. Applications should therefore keep the database authoritative and treat cache refresh as repairable work.

A retry can be safe when the cache operation is version-aware. Repeating “store version 42 if newer” does not allow version 42 to overwrite version 43.

Do not use wall-clock timestamps as a casual substitute

It is tempting to attach a timestamp to each value and keep the value with the latest time. Across processes, wall clocks can differ. Clock adjustments can also move time unexpectedly.

A database sequence, row version, log position, generation counter, or another monotonic token gives a stronger ordering signal.

If timestamps are unavoidable, their semantics and clock assumptions must be explicit. They should not be treated as equivalent to a total commit order without supporting guarantees.

Define the consistency target

Not every cache requires the same guarantee.

For a catalog description, bounded staleness may be acceptable. A short TTL plus ordinary invalidation can be enough.

For inventory, authorization state, account limits, or workflow state, serving an older value after a completed update can cause incorrect decisions. Those cases often need stronger publication rules or may need to bypass caching for sensitive reads.

State the target in operational terms:

  • Can a completed write be followed by a read that returns the previous value?
  • For how long can an old value remain visible?
  • Must one client observe its own completed writes?
  • Is ordering required per key, per entity group, or globally?
  • What happens when the cache is unavailable?

These questions turn “cache consistency” into testable behavior.

Test the interleaving, not only the functions

Unit tests for get and update can both pass while the combined protocol remains unsafe.

A focused concurrency test can force the critical order:

A misses cache
A reads version 41
pause A
B commits version 42
B updates cache state
resume A
A attempts to publish version 41
assert cache does not contain version 41

Use barriers, latches, controlled fakes, or deterministic schedulers so the test creates the intended interleaving directly. Tests based only on sleeps are slower and can miss the race.

Also test cache-operation failures. The system should preserve database correctness when deletion, refresh, token advancement, or cache reads fail.

Keep repair paths available

Even a strong protocol benefits from repair mechanisms. Cache entries can be evicted, rebuilt, or compared with authoritative state. Metrics can track rejected stale fills, cache age, version gaps, and refresh failures.

A rejected stale fill is useful telemetry. A sudden increase can indicate slower database calls, longer request pauses, or higher write contention.

The cache should remain disposable. Consistency machinery should prevent bad derived state from becoming authoritative.

A practical decision guide

Use plain cache-aside with TTL and invalidation when temporary stale reads are acceptable and the consequence is small.

Add version-aware publication when a delayed fill must not replace newer state. Prefer a monotonic version already produced by the authoritative store.

Use generation tokens when cache work needs ordering but the domain record does not expose a suitable version.

Use per-key coordination when duplicate expensive work is also a concern, but pair leases with fencing or another receiver-enforced ordering mechanism when stale holders can act after expiry.

For strict decision-making paths, consider reading the authoritative store directly or using a storage design with the required consistency guarantee. A cache is an optimization, not an obligation.

Closing perspective

Cache-aside is simple at the level of individual steps and subtle at the level of concurrent histories. The central hazard is a read that starts before an update, finishes after it, and publishes old state after the writer has already invalidated or refreshed the cache.

The durable fix is to stop treating cache fills as unconditional writes. Give each fill evidence of its freshness and let the cache accept it only when that evidence is still current.

Once cache publication is ordered by versions, generations, or fencing tokens, correctness depends less on fortunate timing. That makes the protocol easier to test, operate, and reason about under real concurrency.

Software Engineering Caching Concurrency Consistency