Skip to content

Spec: Tombstone Referential Cascade (Append-Only)

File: .ai/specs/core-engine/2026-07-02-tombstone-cascade.md Status: Draft — for peer review before PR-019 opens Owners: Storage lane Related: PR-019, PR-014/015 (version semantics), PR-016 (indexes), PR-017 (adjacency), F3 corrected resolution

1. Overview

Defines the complete, atomic, strictly append-only write-set for tombstoning a node or edge, and the ghost-edge invariant that every historical snapshot must satisfy. This spec is the normative encoding of the corrected F3 resolution: the cascade appends tombstone versions and their index/adjacency entries in a single batch_write; it never deletes historical rows.

2. Problem Statement

Two failure modes threaten tritemporal correctness:

  • Forward ghosts: tombstoning only the node (or node + edge versions, but not their adjacency/index entries) lets post-tombstone snapshots traverse into supposedly dead structure.
  • Backward ghosts (the F3 correction): implementing the cascade as deletion of adjacency or secondary-index rows blinds queries at coordinates before the tombstone — edges that genuinely existed vanish from history. This failure is invisible to current-state tests and surfaces only during historical audits, which is fatal for a product whose core promise is trustworthy time travel.

Both must be impossible by construction.

3. Proposed Solution

tombstone_node(scope, logical_id, valid_end, provenance) produces one RocksDB WriteBatch containing only puts (zero deletes) covering:

  1. A new node tombstone version (tombstone: true, validTime capped at valid_end, txTimeStart = now).
  2. For every live edge touching the node (discovered via both adjacency CFs at current coordinates): a new edge tombstone version per edge.
  3. For each edge tombstone version: its adjacency_out and adjacency_in entries (new rows keyed by the tombstone version's temporal coordinates).
  4. For every new version in (1)–(3): its valid_time_index and tx_time_index entries.

Temporal windows are capped by new facts, not erased. Readers determine liveness exclusively via end-boundary validation of version records — never via row absence.

4. Architecture

tombstone_node(scope, id, valid_end)
  ├─ collect: adjacency_out prefix scan (live-filtered)   ┐ read phase
  ├─ collect: adjacency_in  prefix scan (live-filtered)   ┘ (consistent snapshot)
  ├─ build write-set: 1 node TS + N edge TS + 2N adjacency + 2(N+1) index entries
  └─ StorageEngine::batch_write(all puts)                 ← single atomic batch

Reads for collection run against a StorageSnapshot taken at operation start so a concurrent edge write cannot be half-observed; concurrent writers to the same node serialize on a per-logical-id write lock (already required by PR-014's txTime total-order guarantee).

5. Data Models

No new key layouts (all defined in the composite-key-layout spec). New semantics:

  • EdgeVersion.tombstone = true versions carry cascade_of: Option<Uuid> in properties-metadata, recording the node tombstone that caused them (provenance for audit).
  • Cascade journal (large-cascade case, §10): jobs CF entry kind=cascade, payload = node id + collected edge-id list + chunk watermark. Exists only when the write-set exceeds max_batch_ops (default 100_000 ops ≈ node with >~12k edges).

6. API Contracts

pub fn tombstone_node(&self, scope: &TenantScope, id: Uuid, valid_end: Ts, prov: Provenance)
    -> Result<CascadeReceipt>;   // { node_id, edges_tombstoned: u64, tx_time: Ts, journaled: bool }

pub fn tombstone_edge(&self, scope: &TenantScope, edge_id: Uuid, valid_end: Ts, prov: Provenance)
    -> Result<TombstoneReceipt>;

REST: DELETE /v1/records/:id?validEnd=T maps to tombstone_node (soft, temporal — the PRD has no hard delete). gRPC: folded into BatchWrite op kinds.

7. UI/UX

Not applicable. Operator surface: telha debug cascade-check <tenant> <node> verifies invariant I1–I3 (§12) for a given node — ships with PR-019 for forensic use.

8. Configuration

  • max_batch_ops (default 100_000): threshold above which the cascade journals + chunks (§10).
  • WAL sync on cascade batches is always sync=true regardless of global WAL policy — a cascade is a user-visible destruction event and must survive power loss the instant it is acknowledged.

9. Alternatives Considered

  • Deletion of adjacency/index rows (original F3 wording) — rejected: destroys backward history; the exact failure this spec exists to prevent.
  • Lazy cascade (tombstone node only; filter edges at read time by joining node liveness) — rejected: every traversal would pay a node-liveness lookup per edge, and "no ghost edges in historical snapshots" (PRD Task 4) becomes a query-time promise instead of a storage-time fact.
  • Background async cascade — rejected for the common case: a window where the node is dead but edges are live violates atomic referential integrity. Retained only as the journaled recovery mechanism for oversized cascades (§10), where the journal makes the intermediate state principled and repair deterministic.
  • RocksDB transactions (pessimistic) — unnecessary: single-writer-per-logical-id + one WriteBatch already yields atomicity; transactions add overhead without strengthening the guarantee.

10. Implementation Approach

Per PR-019 commits: spec → tombstone_node (single-batch path) → tombstone_edge → ghost-edge invariant tests (both directions) → large-cascade journal path.

Large cascades (write-set > max_batch_ops): write journal entry (sync) → apply chunked batches, node tombstone version in the final chunk (edges die first; node-last ordering means any crash leaves a state where the node is still visibly live and the journal deterministically resumes) → clear journal. Reaper (PR-030) replays incomplete journals on startup. Chunk replay is idempotent: puts are byte-identical, re-application is a no-op.

11. Migration Path

Greenfield. The cascade_of metadata field is additive under PR-013's value-version byte; older readers ignore it.

12. Success Metrics — the ghost-edge invariants (all CI-gated)

  • I1 (forward): for all (vT, tT) with tT ≥ cascade tx_time and vT ≥ valid_end: no query or traversal returns the node or any cascaded edge.
  • I2 (backward): for all (vT, tT) strictly before the cascade coordinates: queries and traversals return the node and edges exactly as they did pre-cascade (asserted against recorded pre-cascade query results — byte-identical).
  • I3 (atomicity): there exists no observable coordinate where the node is tombstoned but any of its edges is live (property-tested across randomized histories; crash-injection tests on the journaled path).
  • Scale: 50k-edge cascade completes, journal replay after kill-9 at every chunk boundary converges to the identical end state.

13. Open Questions

  • OQ-1: Should valid_end be allowed in the past (retroactive tombstone)? Proposed: yes — it is just another valid-time fact; requires no mechanism change. Confirm product intent.
  • OQ-2: Un-tombstone (resurrection)? Append-only makes it natural (new live version post-tombstone) but the PRD is silent. Defer; forbid at API level in v1 to avoid unplanned semantics.
  • OQ-3: Does GDPR erasure (physical) interact with cascade journals? Cross-reference with composite-key-layout spec OQ-2 — one erasure spec should own both.

14. Changelog

  • 2026-07-02 — v0.1 initial draft encoding the corrected F3 resolution (append-only cascade, backward-ghost invariant added).