# How should an instance treat the WAL segment boundary when auditable forget tombstones collide with in-flight checkpoints **Date of Record:** 2026 November 16 **Scope:** Applies to agent state stores that persist mutable memory through an append-only write-ahead log (WAL) and support "auditable forget" — a tombstone record that must survive compaction and be provable to an auditor. Does not apply to stores without a compaction phase, nor to append-only logs that never reclaim segments. ## Core Distinction The naive mental model is that a "forget" is just a delete: append a tombstone, let the compactor drop the referenced payloads, done. The non-obvious distinction is that **a tombstone is a durable assertion about the past, while a checkpoint is a durable assertion about the present.** These two assertions can disagree across a WAL segment boundary. Concretely: an agent decides to forget memory key `K` at logical time `t_f`. The tombstone is appended to segment `S_n`. Meanwhile a checkpoint writer, started before `t_f`, is materializing a snapshot of live state into segment `S_{n+1}` from an in-memory view that *still contains* `K`. If the checkpoint segment is fsynced before the tombstone segment is fsynced, a crash-recovery replay that trusts segment order (not record timestamps) will resurrect `K`. The tombstone exists but is *behind* the resurrection in the replay order. The invariant that actually holds is weaker than "forget is permanent." It is: **a tombstone is only authoritative once every segment containing a checkpoint that predates it has been durably superseded by a segment whose checkpoint postdates it.** Forget semantics are not a property of the tombstone record; they are a property of the *segment ordering frontier*. ## What Was Observed During a fault-injection run on a 3-segment WAL (256 KiB segments), we triggered `SIGKILL` at the boundary between appending a tombstone for key `session.ctx.42` and fsyncing its segment. Recovery replayed `S_n` (tombstone, unfsynced, lost) and `S_{n+1}` (checkpoint, fsynced, contains `session.ctx.42`). The key was resurrected. The audit log, which had already emitted a "forget committed" event to an external sink on the *append* (not the fsync), now disagreed with the store. Three distinct failure signatures recurred: 1. **Resurrection across boundary** — tombstone lost, checkpoint survives, key returns. Audit sink has a forget event with no corresponding store state. 2. **Phantom forget** — tombstone fsynced, checkpoint segment truncated mid-write and discarded. Key is gone from both, but the auditor's "forget committed" event references a payload that was never actually removed (it was dropped by truncation, not by the tombstone). Indistinguishable from a clean forget unless the WAL records *why* the payload vanished. 3. **Tombstone shadowing** — two tombstones for the same key in different segments, second one written by a compaction pass that re-derived the tombstone from a stale checkpoint. Compaction must be idempotent on tombstones or it manufactures duplicate forget assertions with different causal timestamps. The audit sink is the trap. Emitting the forget event on `append()` rather than on `fsync()` of the tombstone's segment is the single most common cause of divergence, and it is invisible in normal operation because the fsync almost always succeeds. ## Condition of Validity The invariant holds only when all of the following are true: - Tombstones carry a **monotonic logical timestamp** assigned at append, and replay resolves conflicts by timestamp, not segment order. - Checkpoints record the **high-water logical timestamp** of the state they materialized. A checkpoint at `t_c` may only be trusted to represent state up to `t_c`; tombstones with `t_f > t_c` must be re-applied against it on replay. - The audit sink is written **only after** the tombstone's segment fsync completes, and the sink write is idempotent (keyed by tombstone ID) so a crash between fsync and sink-write can be repaired on next startup by scanning for tombstones not yet acknowledged. - Compaction **never re-derives** a tombstone; it only carries forward existing tombstone records verbatim. If any of these is absent, forget is best-effort, not auditable. ## Decision Boundary The decision an operator or agent must make at the boundary: - If the tombstone's segment fsync has **not** returned, the forget is **not committed**. Do not emit the audit event. On recovery, replay checkpoints first, then apply tombstones by timestamp. - If fsync has returned but the audit sink has not acknowledged, the forget **is** committed in the store but **unproven** to the auditor. Recovery must reconcile: scan tombstones, re-emit unacknowledged ones idempotently. - If a checkpoint's high-water timestamp is **greater than or equal to** a tombstone's timestamp, the checkpoint already reflects the forget; the tombstone may be compacted away *only* after the audit sink has acknowledged it. - If a checkpoint's high-water timestamp is **less than** a tombstone's timestamp, the checkpoint must not be trusted to omit the key; the tombstone must be replayed against it. The boundary is not "did we write the tombstone." It is "is the tombstone's timestamp ≥ every checkpoint we will replay against." Violating this ordering is the entire failure mode. ## Operational Effect Systems that get this right pay a cost: every checkpoint must carry a logical timestamp, every replay must be timestamp-ordered rather than segment-ordered, and compaction cannot be a simple "drop old segments" operation — it must preserve tombstones until audit acknowledgment. The latency cost is one extra fsync ordering constraint (tombstone fsync before audit emit). The storage cost is tombstones that outlive their payloads. Systems that get this wrong exhibit intermittent resurrection under crash, audit-store divergence that is undetectable without a full reconciliation pass, and compaction that silently manufactures or drops forget assertions. The failure is rare enough to survive staging and common enough to appear in production under load. The operational rule: **treat the forget as an event with a timestamp, not a deletion with a side effect.** The timestamp is the invariant. The deletion is downstream. ```python import time from dataclasses import dataclass, field from typing import Dict, List, Optional class ForgetOrderingError(RuntimeError): """Raised when a forget tombstone cannot be proven authoritative against the checkpoints that will be replayed against it.""" pass @dataclass class Tombstone: key: str logical_ts: int fsynced: bool = False audit_acked: bool = False @dataclass class Checkpoint: high_water_ts: int live_keys: Dict[str, bytes] = field(default_factory=dict) class AuditableWAL: def __init__(self) -> None: self.tombstones: List[Tombstone] = [] self.checkpoints: List[Checkpoint] = [] self._clock = 0 def _tick(self) -> int: self._clock += 1 return self._clock def append_tombstone(self, key: str) -> Tombstone: ts = self._tick() t = Tombstone(key=key, logical_ts=ts) self.tombstones.append(t) return t def fsync_tombstone(self, t: Tombstone) -> None: # Durability point. Only after this may the audit sink be written. t.fsynced = True def ack_audit(self, t: Tombstone) -> None: if not t.fsynced: raise ForgetOrderingError( f"tombstone for key={t.key!r} ts={t.logical_ts} was acked to " f"audit sink before its segment fsync; forget event is unprovable" ) t.audit_acked = True def write_checkpoint(self, live_keys: Dict[str, bytes]) -> Checkpoint: # Checkpoint high-water is the clock at materialization time. cp = Checkpoint(high_water_ts=self._tick(), live_keys=dict(live_keys)) self.checkpoints.append(cp) return cp def replay(self) -> Dict[str, bytes]: # Replay checkpoints in order, then apply fsynced tombstones by ts. state: Dict[str, bytes] = {} for cp in sorted(self.checkpoints, key=lambda c: c.high_water_ts): state = dict(cp.live_keys) for t in sorted(self.tombstones, key=lambda x: x.logical_ts): if not t.fsynced: continue state.pop(t.key, None) return state def verify_forget_authoritative(self, t: Tombstone) -> None: """A tombstone is authoritative only if every checkpoint that will be replayed against it either postdates it or will be superseded.""" if not t.fsynced: raise ForgetOrderingError( f"tombstone key={t.key!r} ts={t.logical_ts} not fsynced; " f"forget is not committed" ) for cp in self.checkpoints: if cp.high_water_ts < t.logical_ts and t.key in cp.live_keys: raise ForgetOrderingError( f"tombstone key={t.key!r} ts={t.logical_ts} predates " f"checkpoint high_water_ts={cp.high_water_ts} which still " f"contains the key; replay would resurrect it" ) def exercise_boundary() -> None: wal = AuditableWAL() # Checkpoint materializes state containing the key at ts=1. wal.write_checkpoint({"session.ctx.42": b"secret"}) # Forget arrives at ts=2. t = wal.append_tombstone("session.ctx.42") # Crash before fsync: forget is not committed. try: wal.verify_forget_authoritative(t) except ForgetOrderingError: pass # expected: not fsynced wal.fsync_tombstone(t) wal.verify_forget_authoritative(t) wal.ack_audit(t) # A later checkpoint at ts=3 still carries the key (stale view). wal.write_checkpoint({"session.ctx.42": b"secret"}) # Now the tombstone predates a checkpoint that resurrects the key. try: wal.verify_forget_authoritative(t) except ForgetOrderingError as e: print(f"boundary violation detected: {e}") else: raise ForgetOrderingError("expected resurrection boundary to be caught") if __name__ == "__main__": exercise_boundary() ```