greatitself.
Continue
advanced27 min studyLesson 329 in Engineering

Invalidation with versions and retained guards

Reason about duplicate, reordered, delayed, and missing events without turning best-effort notifications into a consistency proof.

Before you begin
On this page

The question for today

What you’ll understand

  • Use a monotonic per-key floor to reject outdated fills.
  • Separate idempotent event handling from complete delivery and strict consistency.
  • Explain why guard retention and restart behavior matter to a proof.

Deleting an entry is an action; ensuring that no old value can return is a protocol property. A distributed invalidation design must handle events arriving twice, out of order, late, or not at all, together with reads already in flight. Versioned rules can make some of those cases safe, but only if their metadata survives the failures and delays used in the argument. State both the invariant and its delivery assumptions.

A source version is not just any counter

Use versions whose ordering means something authoritative for the specific key. Independent client counters, unsynchronized wall clocks, and counters that restart at zero do not automatically order source updates. An epoch plus a sequence or a durable source-assigned revision can provide a comparable identity under a specified protocol. Decide whether equal versions must contain identical values and how deletes are represented. Per-key order does not create a transactionally consistent snapshot across several keys.

Suppose each cache maintains a minimum accepted version floor. An invalidation for version v atomically raises that floor and removes any resident value below it. A fill is accepted only if its source version is at least the floor at the instant of publication. The comparison and write must be atomic together; checking the floor and then writing later reintroduces a race. A version label that no storage rule checks is merely diagnostic metadata.

fnew=max⁡(fold,vevent),vfill≥fcurrentf_{\rm new}=\max(f_{\rm old},v_{\rm event}),\qquad v_{\rm fill}\geq f_{\rm current}
f and v are ordered authoritative per-key versions. The first rule is idempotent and monotonic; the second is an atomically enforced publication condition. It does not ensure delivery of future invalidations or freshness of an origin that returns versions above an insufficient floor.↔ Scroll wide equations horizontally.

Reordering is easier than missing information

A later delivery of version 11 after version 12 cannot lower a max-based floor. Duplicate version 12 events also have no further effect. Those properties help with reordering and at-least-once delivery, but a missing version 13 event can leave a version 12 value eligible. Best-effort Pub/Sub therefore cannot by itself establish that every cache promptly observes every source change. Add replay, reconciliation, authoritative validation, or a clearly bounded stale contract as required by the product.

Retaining the floor matters after the cached value disappears. If eviction, expiry, or restart discards all knowledge of the newer version, a delayed old fill can be accepted into an empty cache. A time-based tombstone is sufficient only under a justified bound on old work and message delay, or with another source-validation mechanism. Under arbitrary pauses no finite guessed timeout proves safety. Explain how a recovering cache obtains a current guard before accepting stale in-flight work.

Tguard>Dold,maxT_{\rm guard}>D_{\rm old,max}
This is a sufficient guard-retention inequality only for a model with a proven finite maximum old-work delay D_old, max and correctly scoped start times. Both quantities are seconds. Unbounded process pauses invalidate that finite-time argument and require a different safeguard.↔ Scroll wide equations horizontally.

Test the counterexample, not only the happy path

Build deterministic traces with a paused reader, a committed update, invalidation delivery, and a resumed old fill. Repeat with duplicate events, reversed events, subscriber disconnect, cache eviction, and a restart that loses volatile metadata. Verify accepted versions and returned values after each operation. Measure reconciliation lag separately from event-handler speed; processing every received event quickly does not show that no event was missed. Strict read-after-write may require synchronous validation rather than asynchronous invalidation alone.

The modular lab shows why a wrapping number is not automatically a monotonic version. Reset and set both modulus m=8 and additive step a=3. Predict period eight, then Step once to see residue three; eight Steps from reset return to zero. Playback advances additions rather than source commits. This additive orbit has no cache, invalidations, or atomic guard. Use the wrap to explain why a small sequence field needs an epoch or another valid comparison rule instead of a naive larger-number-is-newer check.

Work it through

Reordered events and a delayed fill

A cache starts with floor 10 and value version 10. It receives invalidation 12, then invalidation 11. A delayed fill proposes version 11, followed by a fill of version 12. Assume atomic floor/update rules and retained metadata.

  1. Invalidation 12 raises the floor to 12 and removes resident version 10. Invalidation 11 then leaves max(12,11)=12, so reordering cannot lower the guard.

  2. The delayed version 11 fill is rejected because 11<12. The version 12 fill is allowed because it meets the current floor, under the assumption equal source versions identify equivalent values.

  3. If a later version 13 invalidation is lost, these rules alone do not discover it. If the floor is forgotten before the old fill arrives, the earlier rejection proof also fails. Delivery and guard retention are separate requirements.

The result

Monotonic conditional handling tolerates duplicates and reordering, while missing events and lost metadata require additional mechanisms.

The living notebook

Explore the model

Interactive lab

Interactive lab · modular

A wrapping counter is not a monotonic version

Reset, set modulus m=8 and additive step a=3;predict period 8. Step once gives residue 3; eight Steps from reset return to 0. This additive modular orbit is not an invalidation protocol and has no epochs, source revisions, or atomic publication guard.

A wrapping counter is not a monotonic versionAddition modulo m starts at zero: rₙ = na mod m. Playback advances two additions per second. The orbit has period m/gcd(m,a), including period one for a = 0. This is not a cryptographic security test or a primality algorithm. Current readings: Residue r0: 0; Orbit period · m/gcd(m,a): 12; Distinct residues visited: 1 of 12. All parameters are adjustable with the labeled controls below.Repeated addition modulo 12: the current residue is 0, and the orbit period is 12.01234567891011+ 5mod 12An additive orbitn = 0rₙ = 0Period = 12Cycle starts at 0:0 → 5 → 10 → 3 →8 → 1 → 6 → 11 →4 → 9 → 2 → 7 → 0Exact residues · two additions per second
Additive orbitCurrent residue / next edge
Residue r0
0
Orbit period · m/gcd(m,a)
12
Distinct residues visited
1 of 12
t = 0 s

Addition modulo m starts at zero: rₙ = na mod m. Playback advances two additions per second. The orbit has period m/gcd(m,a), including period one for a = 0. This is not a cryptographic security test or a primality algorithm. Parameter changes pause playback and recompute the model at the current elapsed time. Reset restores both parameters and returns time to zero. Playback starts paused. Adjust either parameter, then choose Play or Step.

Look forVersion comparison needs an authoritative ordering rule that remains valid across wrap and restart.

Pause & reason

Check your understanding

What does a max-based version floor prove by itself?

Your turn

Try it yourself

A floor tombstone is retained for thirty seconds, but an old reader resumes after thirty-five seconds and publishes without authoritative revalidation once the floor has expired. Does the original floor rule prevent stale resurrection? Explain the failed assumption.

Take a moment to make a prediction or work it out on paper. Open a hint when you need one.

Give me a hint

The guard must still exist when the publication condition is evaluated.

Compare with the solution

No. Once the floor is forgotten, the empty cache can accept the delayed old value unless another rule rejects it. A thirty-second retention cannot prove safety for thirty-five-second old work. Either establish a real delay bound and longer retention with correct epochs, or use a stronger source/generation validation or persistent guard that survives the relevant delay and failure conditions.

Keep the idea

Take it with you

  • Version checks must be authoritative, monotonic, and atomic with publication.
  • Reordering tolerance does not prove event delivery or strict freshness.
  • Guard expiry and restart belong inside the stale-fill safety argument.

Read further

Original sources and deeper explanations to follow at your own pace.

Optional progress, saved in this browser when available. Revisit any lesson at any time.

Lesson not marked complete.