execution/cache: evaluate change-diff tombstones for selective unwind invalidation

[yperbasis]

Goal

#23095 gives StateCache and BranchCache one coherence rule: a cache view is
usable only while its exact database-and-files generation is published. A
canonical unwind revokes the old generation, commits the database unwind,
clears both caches, and publishes the new generation.

The full clear is the conservative baseline. It has a small correctness proof
and does not depend on unwind-diff completeness, but even a one-block reorg
discards the complete hot working set.

Evaluate whether a complete unwind diff can instead produce cache-eviction
tombstones after commit. This could retain unaffected entries without restoring
the per-entry unwind metadata removed by #23095.

This proposal does not replace generation gating. Tombstones remove existing
entries; only generation revocation prevents old transactions from reading or
refilling the new cache. Foreign immutable-files publication also remains a
separate invalidation boundary.

Related: #22463, #23028, #22120, #23005, #23047, #23095.

Designs being compared

The main baseline here is 23a86a7198. Bare main is not a viable option:
#22463 requires either #23005 or #23095.

Current main plus #23005

Current main stamps entries with (txNum, epoch). Unwind advances each
cache's epoch and lowers its floor in O(1); stale entries are rejected and
removed lazily on lookup. BranchCache also eagerly removes known diff keys, but
does not depend on that diff for correctness.

#23005 retains this model and adds a StateCache readViewEpoch. Unwind revokes
fill authority from older views while still allowing them to read the
latest-wins cache. It also rejects bounded in-progress unwind reads and old
database transactions first attached after unwind. This fixes #22463 without
changing the cache-hit path and retains unaffected entries.

The cost is a layered model: per-entry epochs and floors, domain frontiers, a
separate read-view epoch, and different StateCache and BranchCache rules.
#23005 does not cover immutable-files identity or #23028; this path also needs
#23047 or an equivalent files-publication fix.

#23095 with full clearing

#23095 replaces those mechanisms with one immutable generation token per cache,
identifying the durable PlainStateVersion and relevant values-file ends. Both
caches use the same publication protocol for commits, unwinds, reset, and file
changes. Revoked views lose reads and fills; failed publication restores the
previous generation.

A canonical unwind clears both caches because the diff is not assumed to cover
every entry populated from the discarded fork. This fixes #22463 and #23028 and
removes per-entry transaction numbers, epochs, floors, and cache/coherence.

#23095 with selective tombstones

This issue keeps #23095's generation identity and publication protocol. It
changes only canonical-unwind reconciliation: evict affected logical keys from
a proven-complete diff and retain the rest. Missing, incomplete, or untrusted
plans fall back to #23095's full clear. Measurements may justify using the same
fallback for large plans.

#23095 with a shadow generation (lazy revalidation)

Selective eviction inverted. A canonical unwind still clears the live cache,
but retains the pre-unwind contents as a read-only shadow together with the
deduplicated logical-key diff set. A miss in the new generation may consult the
shadow: a key absent from the diff set is promoted through normal fill
admission; a key present in it is ignored. The shadow is dropped at the next
publication boundary of any kind — commit, unwind, files change, reset — and
whenever diff completeness cannot be proved, degrading to exactly #23095 full
clearing.

The completeness proof is identical to eager tombstones. The differences are
operational: the publication blackout does not grow with the plan size (no
eviction walk under the publication lock), retention work is paid lazily and
only for keys actually re-requested, and deep reorgs degrade naturally by
dropping the shadow. The cost is one additional lifetime to govern: the shadow
itself, which must obey the same lineage rules as file provenance.

End-state simplicity

Patch size and final-design simplicity point in opposite directions:

• Current main plus execution/cache: prevent dead-fork StateCache fills across unwind #23005 and db/state, execution: reconcile StateCache and BranchCache at the file-publication boundary #23047 is the smallest migration but the
  least simple end state. Maintainers must understand entry epochs and floors,
  domain frontiers, readViewEpoch, database-state checks, file-extension
  watermarks, and different StateCache and BranchCache rules.
• execution, db: bind cache views to state versions and file views #23095 with full clearing is the largest migration but the simplest end
  state. One generation identity and one publication protocol cover both
  caches and every durability boundary. Publication and abort handling remain
  non-trivial, but that complexity is centralized; unwind reconciliation is
  simply revoke, commit, clear, and publish.
• Selective tombstones keep execution, db: bind cache views to state versions and file views #23095's simple cache identity, entry layout,
  and hit path, but add an unwind planner with completeness, key-normalization,
  derived-entry, provenance, and fallback rules. Its overall complexity is
  between the other two designs and stays off the steady-state path if the
  planner is isolated.
• A shadow generation keeps execution, db: bind cache views to state versions and file views #23095's identity, entry layout, and
  publication protocol, and needs no eviction work inside the publication
  window. It adds one shadow lifetime and a promotion rule on the miss path;
  after the shadow is dropped, nothing remains on the steady-state path. Its
  complexity also sits between full clearing and eager tombstones, but the
  runtime cost profile is better: constant-size publication work and
  pay-per-re-request retention.

Therefore, #23095 full clearing is the preferred end state when clarity and
proof simplicity are the priority. Tombstones are justified only by measured
reorg-performance gains.

Required invariants

Any selective design must preserve these #23095 properties:

• A cache represents one exact PlainStateVersion and compatible immutable
  values-files view.
• Speculative or locally rewound SharedDomains cannot affect shared caches.
• Publication revokes old views and drains admitted fills before the durable
  boundary; cache mutation occurs only after a successful commit.
• A failed commit restores the previous generation without partial cache
  mutation.
• Old transactions cannot read or fill a newer generation.
• Missing or untrusted reconciliation data causes a full clear.
• Whole-state replacement and foreign file publication remain full
  invalidation boundaries.
• A retained shadow is read-only and revoked like any old generation; it
  promotes entries only through fill admission with the diff filter, and it is
  dropped at the next publication boundary or on any completeness doubt.

Proposed unwind protocol

Treat merged DomainEntryDiff records as an affected-key set. A tombstone means
evict this cache key, not cache absence:

• Value == nil removes the current-step row and reveals an older value; it
  does not mean the logical key is absent.
• A non-nil empty value means the key was previously absent.
• A non-empty value contains a previous value, but eviction is simpler and
  handles all three cases uniformly.

A canonical unwind would:

1. Merge the complete unwind range and deduplicate logical keys after removing
   each diff key's eight-byte inverse-step suffix.
2. Detach the rewound SharedDomains from shared-cache reads and fills, stage
   the eviction plan, and flush the database unwind.
3. Begin cache publication in the established lock order, revoke old views, and
   wait for admitted fills.
4. Commit the database transaction.
5. On success, lower file-provenance coverage, apply tombstones and retained
   forward updates, then publish the new generation. On failure, restore the
   old generation without applying tombstones.

If completeness or safe provenance cannot be proved, step 5 clears the affected
cache instead.

Domain rules

For StateCache:

• Evict account, storage, and address-keyed code entries by logical domain key.
• Account eviction must also remove its derived address-to-code-hash binding.
• Content-addressed code and code-size entries may remain because a hash always
  identifies the same bytes; focused tests must enforce this assumption.

For BranchCache:

• Map commitment-domain logical keys to BranchCache.Invalidate, including
  root, trunk, pinned, and tail tiers; handle commitment metadata explicitly.
• Prove that diffs cover observable changes from read-through, trie preload,
  and adaptive pinning, not only direct writes.
• Define whether adaptive topology and scores remain. No discarded-fork bytes
  may survive.

For file provenance, lower each coverage watermark to a proven safe boundary,
normally no later than the unwind transaction number. Execution cannot unwind
into immutable snapshot state. If that rule is insufficient to prove a safe
watermark, reset provenance and clear the cache.

Comparison

Property	main + #23005	#23095 full clear	Selective tombstones	Shadow generation
Coherence model	Entry epochs/floors, StateCache frontiers and readViewEpoch; separate cache rules	One database-and-files generation rule	Same generation rule as #23095	Same generation rule as #23095
#22463	Fixed; old views keep reads but lose fills	Fixed; old views lose reads and fills	Same as #23095	Same as #23095
#23028	Needs #23047 or equivalent	Fixed at the files-publication boundary	Same as #23095	Same as #23095
Stored dead-fork entries	Rejected lazily by entry stamp	Both caches cleared after commit	Affected logical keys evicted after commit	Retained in a revoked shadow; diff-filtered out on promotion
Unwind work	O(1) authoritative invalidation; known branch diff keys also removed eagerly	Reset both cache structures	Build, deduplicate, and apply O(changed keys); full-clear fallback	Retain shadow and diff-key set; O(1) staging, promotion paid per miss
Shallow-reorg warmth	Unaffected entries remain	Complete cache becomes cold	Unaffected entries remain	Unaffected entries recover on first re-request
Hit path and metadata	Per-hit stamp validation and per-entry txNum/epoch; #23005 adds no hit check	Two token checks, no per-entry unwind metadata	Same as #23095	Same as #23095; the miss path gains one shadow probe while a shadow exists
Long-lived old readers	Continue to get latest-wins hits	Miss after a newer generation publishes	Same as #23095	Same as #23095
Diff completeness	Not required for stored-entry invalidation	Not required	Required, with explicit full-clear fallback	Required for promotion, with shadow-drop fallback
Temporary unwind memory	No StateCache key plan	No diff-sized key plan	Deduplicated logical-key set, potentially large	One retained cache generation plus a small diff-key set
End-state simplicity	Lowest: several overlapping coherence mechanisms	Highest: one identity, publication protocol, and conservative unwind rule	Middle: same simple core as #23095 plus an unwind planner and domain mappings	Middle: same core as #23095 plus a shadow lifetime and promotion rule
Where complexity lives	Entry metadata, cache hits, and several cache-specific boundaries	Centralized generation publication and abort handling	Centralized generation publication plus isolated unwind reconciliation	Centralized generation publication plus an isolated shadow/promotion path
Main trade-off	Least churn and best retention, but most layered model	Simplest proof, but full re-warm	Better retention with a larger correctness proof and unwind cost	Tombstone retention at constant publication cost, but one more lifetime

Measurement plan

Compare main plus #23005, #23095 full clearing, selective eviction, a
shadow generation with lazy promotion, and a
hybrid that selectively evicts StateCache while clearing BranchCache. Include
#23047 or equivalent in the #23005 configuration when testing full correctness.

Cover 1, 2, 8, and 64 unwound blocks; varied changed-key counts and cache
warmth; realistic domain mixes; short and long-lived readers; and AMD64 and
ARM64. Record:

• steady-state hit latency and throughput;
• tombstone staging time, publication blackout, allocations, and peak memory;
• post-unwind hit rate, database/snapshot reads, and time to recover the prior
  hit rate;
• end-to-end execution latency after reorg.

Add a full-clear size threshold only if measurements justify the extra policy.

Required tests

• Pre-unwind transactions racing publication, and old transactions first
  attached after unwind.
• Nil, empty, and non-empty diff values, including one logical key across
  several steps or blocks.
• Account eviction and derived code-hash invalidation while safe
  content-addressed code remains.
• Branch entries from read-through, preload, every tier, and adaptive pins.
• A cache-only discarded branch cannot be republished by a later commit.
• Failed commit restoration and missing/incomplete-diff full-clear fallback.
• File publication immediately after unwind cannot retain false provenance.
• Race-detector coverage for fills against commit, abort, and unwind
  publication.
• Shadow variant: promotion admission with the diff filter, shadow drop at
  every boundary type, and no shadow reads after the drop.

Decision

• For the smallest execution/cache: stale-fill admission is one-sided — pre-unwind read views refill dead-fork values, and unwound keys bypass the flush cache-apply #22463 fix, adopt execution/cache: prevent dead-fork StateCache fills across unwind #23005 and address StateCache: fills can go stale when a snapshot download extends file visibility with never-applied state #23028 through db/state, execution: reconcile StateCache and BranchCache at the file-publication boundary #23047
  or an equivalent hook.
• For the simplest consistent end state across both caches and all publication
  boundaries, use execution, db: bind cache views to state versions and file views #23095 with full clearing.
• Treat tombstones only as a measured optimization of execution, db: bind cache views to state versions and file views #23095. Keep full clearing
  unless completeness is documented, all tests pass, shallow reorgs improve
  materially on AMD64 and ARM64, and large plans do not cause an unacceptable
  publication blackout.

The lowest-risk experiment is selective StateCache retention with a full
BranchCache clear — via either eager tombstones or the shadow generation. The
shadow variant shares the same completeness proof but keeps publication work
constant-size and pays retention lazily, so it is the preferable first
experiment if the diff-key set or blackout budget is a concern. Add selective
BranchCache retention only after diff coverage is proved for every population
tier.

[VBulikov]

yperbasis added Imp2 as Importance

[VBulikov]

yperbasis changed Importance from Imp2 to Imp1

[VBulikov]

yperbasis changed Importance from Imp1 to Imp2