Cache Invalidation That Survives Replication Lag

Problem statement: the code deletes the cache key immediately after every write, and users still see pre-write data for a full TTL afterwards — reproducibly under load, never in a quiet environment.

The delete is not the problem. The problem is that between the delete and the replica catching up, another request can repopulate the key with the old value and a fresh TTL. This page fixes that race and explains why the obvious alternatives do not. It is the correctness half of caching and materialized reads for stale-tolerant workloads.

Symptom Identification

The race has a distinctive fingerprint:

  • Stale data persists for approximately one full TTL after a write, not for the replication lag.
  • It is intermittent and load-dependent: reproducible under concurrency, never in a single-user test.
  • The key was definitely deleted — the invalidation code path has logging that confirms it ran.
  • The stale value is the immediately preceding version, not an arbitrarily old one.
  • Setting a shorter TTL reduces the duration of the symptom but not its frequency.

That last point is diagnostic. If shortening the TTL reduces how long the wrong value is served but not how often it happens, the entry is being written after the invalidation rather than surviving from before it. A bug in the invalidation code itself would show the opposite pattern.

Root Cause Analysis

The sequence is precise and entirely ordinary.

  1. A write commits on the primary at time t.
  2. The application deletes the cache key. The cache is now empty and correct.
  3. At t + 5 ms, a concurrent request for the same key misses the cache.
  4. It queries a replica that has not yet replayed the write at t.
  5. It receives the pre-write value and writes it into the cache with a full TTL.
  6. At t + 40 ms, the replica replays the write. The database is now consistent; the cache is not.

Nothing in that sequence is a bug in isolation. The delete happened. The read was served by a healthy replica within its lag budget. The cache write followed the read. The defect is emergent: the repopulation path can observe a version older than the one that triggered the invalidation.

Two properties make it worse than it first appears. The stale entry has a full TTL, so a 5 ms race window produces 30 seconds of wrong data. And the write path believes it succeeded, so nothing anywhere logs a problem.

A change feed on a replica cannot fix it. This is the most common proposed solution and it is structurally unable to work: an event emitted when the replica replays the change arrives at step 6, after the stale repopulation at step 5. The invalidation is always later than the thing it must prevent. Invalidation has to be driven from where the write is authoritative — the primary.

The six-step invalidation race and where the second delete lands Three lanes: primary, cache and replica. A write commits on the primary and the cache key is deleted. Before the replica has replayed the write, a concurrent request misses the cache, reads the pre-write value from the replica, and writes it back with a full time to live, undoing the invalidation. The replica then replays the write, leaving the database consistent and the cache wrong. A second delete scheduled at commit time plus the lag budget lands after the replay and removes the stale entry. primary cache replica 1 commit 2 DELETE 3 miss 4 reads the PRE-write value 5 SET old value, full TTL the invalidation is now undone lag window 6 replayed — DB consistent, cache wrong second DELETE at commit + lag budget lands after step 6 — removes the stale entry Every step is individually correct. The defect only exists in the ordering, which is why code review does not catch it.

Step-by-Step Resolution

Step 1 — Confirm the race rather than assuming it

python
# Instrument the repopulation path to record what it saw, so the race
# is observable rather than inferred.
def repopulate(key, uid):
    row, lag_s = replica.query_with_lag(
        "SELECT *, xmin::text AS version FROM profiles WHERE id = %s", uid)
    last_write = write_log.get(key)          # commit time of the last known write
    if last_write and time.time() - lag_s < last_write:
        RACE_LOST.labels(key_prefix="profile").inc()
        log.warning("repopulating %s with a value older than the last write", key)
    cache.set(key, {"value": row, "as_of": time.time() - lag_s}, ttl=TTL)

Inline verification: under production load, RACE_LOST is non-zero. If it is flat zero, the stale data has a different cause — most likely a missed invalidation path rather than a lost race.

Step 2 — Add the second delete

python
def invalidate(key: str, lag_budget_s: float = 2.0) -> None:
    """Delete now, and again once the replication lag window has passed."""
    cache.delete(key)
    # A delayed job, a timer, or a message with a visibility delay — any
    # mechanism that reliably fires later. It must not depend on this process
    # surviving, so an in-process timer is the weakest acceptable option.
    delayed_queue.enqueue(cache.delete, key, delay=lag_budget_s)

The second delete is unconditional and idempotent: deleting an absent key costs nothing. Sizing lag_budget_s above your p99 replication lag closes the window for essentially all writes.

Inline verification: after deploying, the duration of observed staleness drops from a full TTL to at most lag_budget_s.

Step 3 — Refuse to cache a value known to be behind

The second delete narrows the window; this closes it for the cases you care most about.

python
# Compare the replica's replay position against the write watermark for
# this key. If the replica has not caught up, serve the value but do NOT
# cache it — a stale value served once is a much smaller problem than a
# stale value cached for a full TTL.
def read_profile(uid: int):
    key = f"profile:{uid}"
    if (e := cache.get(key)) is not None:
        return e["value"]

    watermark = write_log.get(key)               # LSN of the last write, if any
    row, replay_lsn = replica.query_with_lsn(
        "SELECT * FROM profiles WHERE id = %s", uid)

    if watermark is None or replay_lsn >= watermark:
        cache.set(key, {"value": row, "as_of": time.time()}, ttl=TTL)
    else:
        SKIPPED_CACHE_WRITE.inc()                # observable, not silent
    return row

Inline verification: SKIPPED_CACHE_WRITE is non-zero during write bursts and near zero at other times — the expected shape.

Step 4 — Give every entry a TTL

python
# Even with perfect event invalidation, a TTL is the bound of last resort.
# An invalidation system will eventually miss an event; a TTL turns
# "stale forever" into "stale for at most TTL".
cache.set(key, value, ttl=TTL)          # never cache.set(key, value)

Choose the TTL from the read path’s freshness budget minus the replica lag already present, not from a convenient round number — the arithmetic is in serving bounded-staleness reads with an explicit freshness budget.

Inline verification: redis-cli --scan --pattern 'profile:*' | head -100 | xargs -n1 redis-cli ttl returns positive values for every key, never -1.

Step 5 — Keep measuring

promql
# How often the race is being lost. Should fall to near zero after step 2
# and to zero after step 3.
rate(cache_repopulate_race_lost_total[5m])

# How often a cache write was skipped because the replica was behind.
# A rising trend means lag is growing, not that the cache is broken.
rate(cache_write_skipped_stale_total[5m])

Inline verification: the first series trends to zero; the second tracks write volume and replica lag rather than growing without bound.

Configuration Snippet

python
# cache_invalidation.py — the complete pattern in one place.
import time
from dataclasses import dataclass

LAG_BUDGET_S = 2.0     # above p99 replication lag, measured not guessed
TTL_S        = 30.0    # bound of last resort

@dataclass
class Entry:
    value: object
    as_of: float       # commit time this value reflects — NOT the time it was cached

def invalidate(key: str) -> None:
    """Called immediately after the write commits on the primary."""
    cache.delete(key)
    write_log.set(key, time.time(), ttl=LAG_BUDGET_S * 2)   # remember the write
    delayed_queue.enqueue(cache.delete, key, delay=LAG_BUDGET_S)

def read(key: str, loader) -> object:
    if (e := cache.get(key)) is not None:
        return e.value

    value, lag_s = loader()                # returns (value, replica lag at read)
    as_of = time.time() - lag_s

    last_write = write_log.get(key)
    if last_write is not None and as_of < last_write:
        # This value predates a write we know about. Serve it, do not cache it.
        return value

    # TTL is the REMAINING budget after the lag already spent.
    cache.set(key, Entry(value, as_of), ttl=max(TTL_S - lag_s, 1.0))
    return value

The write_log is doing the essential work and is easy to under-specify. It must outlive the lag window (hence ttl=LAG_BUDGET_S * 2) and it must be shared across all application instances — an in-process dictionary defeats the whole mechanism, because the request that repopulates is usually on a different instance from the one that wrote. In practice it is a small set of keys in the same cache, with short TTLs, and it costs one extra round trip per miss.

Exposure window and cost for three invalidation strategies Three horizontal bars showing worst-case staleness exposure after a write. A single delete leaves up to a full thirty second time to live of exposure at the cost of one cache operation. Adding a second delete after the lag budget reduces the exposure to about two seconds for the cost of one extra operation. Adding a version gate that refuses to cache values older than the last known write removes the exposure entirely, at the cost of one extra lookup per cache miss. 0 s 15 s 30 s worst-case staleness after a write delete only 1 cache op up to a full TTL — the race is unmitigated + second delete 2 cache ops ≈ lag budget (2 s) — covers all lag below the budget + version gate 2 ops + 1 lookup/miss none — a value older than the last write is never cached Most workloads stop at the second row. Go to the third only when a two-second window is genuinely unacceptable.

Verification and Rollback

Reproduce the race deliberately, then confirm it is closed:

bash
# Drive a write and a concurrent read at the same key, repeatedly.
# Before the fix this produces stale reads; after it, none.
for i in $(seq 1 500); do
  ( curl -sX POST "http://app/profile/42" -d 'name=v'$i >/dev/null ) &
  ( sleep 0.005; curl -s "http://app/profile/42" | jq -r .name ) &
  wait
done | sort | uniq -c | sort -rn | head

Any value appearing far more often than it should is a stale entry that survived. A clean run shows each version appearing roughly once.

Confirm from the metrics rather than only from the reproduction:

promql
# Both should be near zero in steady state after the fix.
rate(cache_repopulate_race_lost_total[5m])
histogram_quantile(0.99, sum by (le) (rate(db_read_served_age_ms_bucket[5m])))

Rollback. The two mechanisms revert independently, which is deliberate:

python
INVALIDATION = {
    "second_delete": True,     # cheap; leave on unless it causes queue pressure
    "version_gate":  False,    # costs a lookup per miss; first to turn off
}

The version gate is the one to disable if cache miss latency becomes a problem, since it adds a round trip to every miss. The second delete is nearly free and should stay on permanently. If you must revert both, shorten the TTL as compensation — it does not fix the race but it bounds the damage, which is the same reasoning behind having a TTL at all.

Edge Cases and Gotchas

The write log must be shared, not per-process

If write_log is an in-process dictionary, the instance that repopulates the key is usually not the instance that performed the write, so the watermark is absent and the gate never fires. It must live in the shared cache or another shared store. This is the single most common way the version gate is implemented and silently does nothing.

Deleting is safer than updating

It is tempting to have the write path SET the new value into the cache rather than deleting it. That reintroduces a different race: two concurrent writes can apply their SET operations in the opposite order to their commits, leaving the cache holding the older value permanently. Deleting is idempotent and order-independent; setting is neither. Delete, and let the next read repopulate.

Multi-key invalidation multiplies the window

A write that invalidates five derived keys performs five deletes, and each has its own race. Because they are not atomic, a concurrent read can repopulate key three from a stale replica after key three was deleted but before keys four and five were. Where several keys derive from one write, consider a version stamp on a single namespace key instead of deleting each one — bumping one version invalidates the whole family atomically.

FAQ

Why does deleting the cache key after a write not work?

It works, and then it is undone. Between the delete and the replica replaying the write there is a window in which a concurrent request misses the cache, reads the pre-write value from the lagging replica, and writes it back with a full TTL. The invalidation happened; the stale value survived it anyway. Nothing about the delete is wrong — the problem is that the repopulation path can still see old data.

Is a second delete after the lag window enough?

For almost every workload, yes. Scheduling a second delete at commit time plus your lag budget closes the window for any lag below that budget, and costs one extra cache operation per invalidation. It fails only when lag exceeds the budget, which is exactly when your freshness gate should already be routing those reads to the primary anyway.

Can I drive invalidation from a change feed on a replica?

No, and it is a tempting mistake. A change feed reading from a replica emits an event only after the replica has replayed the change, which is after the lag window has already passed — so the invalidation arrives later than the stale repopulation it was meant to prevent. Drive invalidation from the primary, either from application code at commit time or from logical decoding on the primary.

Should every cache entry have a TTL even with event invalidation?

Yes. Event-based invalidation is the freshness mechanism; the TTL is the bound of last resort. Any invalidation system will eventually miss an event — a dropped message, a crashed worker, a code path nobody wired up — and without a TTL that entry is stale forever. A TTL turns permanent staleness into bounded staleness, which is the difference between an incident and a degradation.

← Back to Caching & Materialized Reads for Stale-Tolerant Workloads