Tombstone cascade¶

Architecture

Deleting a node in a tritemporal store is not one write, it is a referential cascade: the node and every live edge touching it must die together, atomically, without erasing a single byte of history. This page describes the protocol that makes that true.

Overview & purpose¶

CascadeOps implements tombstone_node and tombstone_edge: the only supported way to delete a node or edge in Telha. Both are soft, temporal deletes. A tombstone is a new version, not a removed row: it caps the entity's valid-time window at the delete instant and marks tombstone: true. Nothing that existed before the cascade is rewritten or dropped.

The problem this subsystem exists to solve is specifically referential integrity across a delete that fans out. Tombstoning a node in isolation is easy. Tombstoning a node and keeping every one of its edges from becoming a "ghost" (a live edge pointing at a dead node, or an edge visible in a snapshot that its node's tombstone should have concealed) is the hard part, and it has to hold at every (validTime, txTime) coordinate, including ones nobody has queried yet.

Design¶

Why cascading deletion needs its own protocol¶

The append-only write path (see The version record model) already knows how to cap a single entity's valid-time window. What it does not know how to do safely is touch a node and an unbounded number of edges as one indivisible unit. Two failure modes are possible if the cascade is implemented naively, and the spec calls both out by name (spec §2):

• Forward ghosts. Tombstoning only the node (or the node and its edge versions, but not their adjacency and index entries) lets a post-tombstone reader traverse into structure that should read as dead.
• 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 is invisible to current-state tests. It only surfaces during a historical audit, which is exactly the promise this product cannot break.

Both failure modes must be impossible by construction, not merely untested.

Why puts-only¶

The fix the spec commits to is that a cascade is one WriteBatch containing only puts. Zero deletes. Tombstoning an edge does not remove its adjacency row, it appends a new adjacency row keyed at the tombstone version's own temporal coordinates. Liveness at any coordinate is decided by end-boundary validation of version records, never by whether a row is present or absent:

A deletion writes a tombstone version (valid time opens at the delete instant). Past snapshots stay whole; the entity simply reads as absent from the tombstone forward.

Because the write-set is pure addition, a snapshot taken before the cascade's transaction time cannot observe it at all, by construction, not by query-time filtering. This is what makes invariant I2 (backward correctness) a storage-time fact instead of a promise the query layer has to keep.

The spec considered and rejected two alternatives (spec §9):

Data model¶

No new key layouts are introduced (adjacency and index keys are the same layouts used by ordinary writes; see Storage engine & key layout). What is new is the code surface and two runtime records.

CascadeOps methods¶

pub struct CascadeOps {
    engine: Arc<dyn StorageEngine>,
    clock: Arc<TxClock>,
    /// Threshold above which the journaled chunked path engages
    /// (config `storage.max_batch_ops`; spec default 100_000).
    max_batch_ops: usize,
}

impl CascadeOps {
    pub fn tombstone_node(
        &self,
        scope: &TenantScope,
        node_id: Uuid,
        valid_end: Ts,
        provenance: Provenance,
    ) -> Result<CascadeReceipt, CascadeError>;

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

    /// Resume every incomplete cascade journal in `scope`. Called by the
    /// reaper on startup; exposed for forensic use and crash-recovery tests.
    pub fn resume_journals(&self, scope: &TenantScope) -> Result<u32, CascadeError>;
}

tombstone_node tombstones a node and every live edge touching it, atomically. tombstone_edge is the standalone, non-cascading form: it tombstones one edge and leaves both endpoints alive, used directly by the REST/gRPC edge-delete path. The receipts returned:

pub struct CascadeReceipt {
    pub node_id: Uuid,
    pub edges_tombstoned: u64,
    pub tx_time: Ts,
    pub journaled: bool,
}

pub struct TombstoneReceipt {
    pub edge_id: Uuid,
    pub tx_time: Ts,
}

CascadeError covers NotFound, AlreadyTombstoned (resurrection is forbidden in v1, spec OQ-2, so a second tombstone on an already-dead entity is refused rather than silently accepted), Decode, and Storage.

Journal record and the state byte¶

Large cascades (write-set larger than max_batch_ops) durably record a journal entry before doing anything else, so a crash mid-cascade has a deterministic recovery path:

struct CascadeJournal {
    node_id: Uuid,
    valid_end: Ts,
    tx: Ts,
    edge_ids: Vec<Uuid>,
    provenance: Provenance,
}

The journal is a row in the jobs column family, keyed by KeyCodec::job_key(scope, state, priority, created_at, job_id), where state is a reserved one-byte discriminant:

/// Reserved `jobs` CF state byte for cascade journals. PR-030's job
/// queue spec inherits and formalizes this discriminant.
pub(crate) const CASCADE_JOURNAL_STATE: u8 = 0xC0;

The state byte is what lets resume_journals find incomplete cascades without scanning the whole jobs CF: ScanRange::jobs_in_state(scope, CASCADE_JOURNAL_STATE) prefix-scans exactly the rows whose state byte is 0xC0, in (state, priority, created_at) order. The job key's created_at field carries the cascade's own transaction time, so journals are naturally ordered by when the cascade started.

Everything needed to replay the cascade byte-identically is in the journal, including the original transaction time tx, not a freshly minted one. That single fact is what makes replay idempotent: re-applying the same puts with the same tx produces the same bytes, so a chunk that already landed is simply overwritten with itself.

Algorithms & invariants¶

The cascade algorithm¶

tombstone_node runs in four phases:

1. Snapshot read phase. Take a StorageSnapshot at operation start. Look up the node's latest open (non-superseded) version; if it is already a tombstone, refuse with AlreadyTombstoned. Collect every live edge touching the node by prefix-scanning both adjacency_out and adjacency_in, resolving each hit against edge_versions, and keeping only the latest-recorded (highest tx_time.start) version per edge, discarding the ones whose winner is already a tombstone. This read runs against one consistent snapshot so a concurrent edge write cannot be half-observed.
2. Build the write-set. For every live edge: an edge tombstone version, its adjacency_out and adjacency_in rows, and its valid_time_index / tx_time_index entries. Then, last, the node tombstone version and its two index entries.
3. Decide small vs. journaled. If the total op count is at or under max_batch_ops, write everything in a single batch_write_durable call. Otherwise take the journaled path (below).
4. Return the receipt, reporting how many edges were tombstoned and whether the journaled path was taken.

Node-tombstone-last ordering¶

The write-set is always assembled edges first, node last. This is not incidental; it is the crash-safety invariant the whole recovery story depends on:

// Build the full puts-only write-set: edges first, node LAST
// (crash mid-chunk ⇒ node still visibly alive, spec §10).

Because the node's tombstone version is always the final entry, any crash during application (single-batch or chunked) leaves the store in a state where the node is still visibly alive. There is no intermediate state where the node reads as dead while some of its edges are still live: the node cannot die before every edge that was going to die already has. That ordering is what lets resume_journals treat "node not yet tombstoned" as an unambiguous signal that the cascade is still in flight.

Latest-tx-wins liveness check¶

Liveness, both for deciding which edges are "live" during collection and for deciding what a reader sees afterward, is resolved by the same rule everywhere in the engine: among versions whose valid and transaction intervals both cover the queried instant, the latest-recorded version (highest tx_time.start) wins, and a winning tombstone reads as absent:

// Latest-recorded (highest txTimeStart) open-tx edge version. When a
// tombstone has landed it IS the latest — callers use that to refuse
// double-tombstones and to skip already-replayed journal chunks. When
// the crash hit before the tombstone chunk, the pre-tombstone version
// wins and replay re-emits byte-identical puts.
fn latest_open_edge(...) -> Result<EdgeVersion, CascadeError> {
    ...
    if version.tx_time.is_open()
        && winner.as_ref().is_none_or(|w| version.tx_time.start > w.tx_time.start)
    {
        winner = Some(version);
    }
    ...
}

This single rule does triple duty: it is the ordinary bitemporal read path (NodeReads::get_as_of), it is how collect_live_edges decides which edges belong in the cascade, and it is how resume_journals decides which parts of an interrupted cascade already landed.

Tombstone valid-time semantics¶

A tombstone version's valid time is built with Interval::open(valid_end), which sets start = valid_end and end = OPEN_END. In other words the tombstone's valid window is [valid_end, ∞): open-ended forward, closed only in the sense that it begins at the delete instant. It is not "closed" by any special end marker; like every other version, it would only ever be capped by a later version superseding it (for example a future correction), which is exactly the same append-only mechanism used for ordinary corrections. The same shape applies to tx_time: Interval::open(tx), open-ended from the cascade's transaction time forward.

Ghost-edge invariants I1, I2, I3¶

These are the spec's CI-gated success metrics (spec §12), reproduced precisely, and each one maps directly onto a test in core-engine/tests/cascade_invariants.rs.

Crash-at-chunk-boundary recovery via resume_journals¶

When the write-set exceeds max_batch_ops, tombstone_node takes the journaled path instead of one batch_write_durable call:

1. Write the CascadeJournal row (durable, sync=true) under CASCADE_JOURNAL_STATE. This alone is the commit point: once this row is durable, the cascade will complete, eventually, even across restarts.
2. Apply the write-set in chunks of max_batch_ops (floor 7, so a chunk boundary can never split a single version's atomic op group; each version's puts are 3 ops for a node and 5 for an edge, both under 7) via repeated batch_write_durable calls.
3. Delete the journal row once every chunk has landed.

If the process dies between any two of these steps, the jobs CF is left holding a journal row whose cascade is incomplete. On startup (or on demand, for forensic use), resume_journals(scope):

1. Prefix-scans jobs for CASCADE_JOURNAL_STATE rows in this scope.
2. For each journal found, rebuilds the identical write-set: the edge ID list and the transaction time come from the journal, never re-derived from a fresh clock read or a fresh adjacency scan. For each journaled edge ID, it looks up the latest open version; if that version is already a tombstone, the edge's chunk already landed and it is skipped. Otherwise its full tombstone write-set (edge version, both adjacency rows, both index entries) is rebuilt.
3. If the node itself is not yet tombstoned, its write-set is appended last, exactly as in the original pass.
4. The rebuilt ops are applied through the same chunked apply_chunked path.
5. The journal row is deleted.

Because step 2 always re-derives puts keyed by the same journaled tx, a chunk that already landed before the crash is simply overwritten with byte-identical data: replay is idempotent. Because of node-tombstone-last ordering, if resume_journals finds zero journals to resume (the crash landed before the journal write itself even committed), the node is guaranteed to still be fully alive: the cascade genuinely never started.

This is exercised directly by journaled_cascade_recovers_after_crash_at_every_chunk_boundary, which builds a 40-edge hub node (203 total ops at max_batch_ops = 50: journal write, 5 chunks, journal clear, 7 durable calls total), injects a crash at every one of those 7 call indices in turn, then calls resume_journals and asserts the end state converges to the same reference outcome regardless of where the crash landed, and that a second resume_journals call afterward resumes zero journals (no residue).

sequenceDiagram
    autonumber
    participant C as CascadeOps
    participant J as jobs CF (journal)
    participant E as edge_versions + adjacency + index
    participant N as node_versions + index

    C->>C: snapshot read: latest live node + live edges
    alt write-set <= max_batch_ops
        C->>E: batch_write_durable (edge tombstones)
        Note over E,N: single atomic batch, edges then node
        C->>N: (same batch) node tombstone last
    else write-set > max_batch_ops (journaled path)
        C->>J: put CascadeJournal (sync=true), commit point
        loop each chunk (edges first)
            C->>E: batch_write_durable (chunk)
        end
        C->>N: batch_write_durable (final chunk: node tombstone)
        C->>J: delete journal row
        rect rgba(200,80,80,0.15)
            Note over C,J: crash may occur after ANY durable call above
        end
    end
    Note over C: --- process restarts ---
    C->>J: scan jobs_in_state(CASCADE_JOURNAL_STATE)
    alt journal found
        C->>E: rebuild + re-apply edge chunks (skip already-tombstoned)
        C->>N: re-apply node tombstone if not yet landed
        C->>J: delete journal row
    else no journal
        Note over C: cascade never started, node still fully alive
    end

stateDiagram-v2
    [*] --> NoJournal: node & edges live
    NoJournal --> JournalWritten: put CascadeJournal (sync)
    JournalWritten --> ChunksApplying: begin chunked batch_write_durable
    ChunksApplying --> ChunksApplying: chunk N applied (edges before node)
    ChunksApplying --> Complete: final chunk applied (node tombstone)
    Complete --> [*]: delete journal row

    JournalWritten --> Crashed: process dies
    ChunksApplying --> Crashed: process dies
    Crashed --> JournalWritten: resume_journals rescans jobs CF
    JournalWritten --> ChunksApplying: replay (idempotent, same tx)

Configuration¶

Tests exercise the journaled path with a deliberately small max_batch_ops (CascadeOps::with_max_batch_ops, set to 50 in the crash-recovery test) rather than the production default of 100,000.

As-built notes¶

The spec's status line reads Draft, for peer review before PR-019 opens. The changelog (spec §14) has exactly one entry: v0.1, the initial draft encoding the corrected F3 resolution (append-only cascade, backward-ghost invariant added). There are no later changelog entries recording deviations, which means everything above should be read as the spec's first cut, not a design that has since been revised in the field. Two things worth flagging precisely because the spec leaves them open rather than resolved:

• OQ-1 (retroactive valid_end): the spec proposes allowing a valid_end in the past with no mechanism change, but says this needs product-intent confirmation. The code does not reject a past valid_end; it is treated as just another valid-time fact, consistent with the proposal, but this is not yet a confirmed product decision.
• OQ-2 (resurrection): un-tombstoning is deliberately forbidden at the API level. tombstone_node and tombstone_edge both return CascadeError::AlreadyTombstoned if the target's latest version is already a tombstone, which the test suite checks directly (standalone_edge_tombstone_keeps_endpoints_alive asserts a second tombstone_edge call on the same edge fails).
• OQ-3 (interaction with GDPR physical erasure) is explicitly deferred in the spec to a future erasure spec; nothing in cascade.rs addresses physical deletion.

The reaper that is supposed to call resume_journals automatically on startup is attributed to PR-030 in both the spec and the code's doc comments; the method itself is implemented and tested directly in this module, but its automatic startup wiring is out of scope here.

Related¶

• The version record model
• Global temporal scan
• Traversal semantics
• The tritemporal model