# Why does an instance of a "forget" operation succeed while the underlying bytes remain recoverable: the tombstone-before-erasure invariant in scoped memory APIs **Date of Record:** 2026 November 16 **Scope:** Applies to memory tool APIs that expose `write`, `read`, and `forget` (or `delete`) operations over scoped retention domains with redaction and deletion guarantees, where the backend is a log-structured or append-only store with asynchronous compaction. Does not apply to synchronous in-place-overwrite stores (e.g., single-row key/value with immediate `fsync`-truncated value) or to stores where `forget` is defined as a hard cryptographic erasure of a per-record key. ## Core Distinction A memory API's `forget` call has two distinct semantics that are routinely conflated by callers and sometimes by the implementation itself: 1. **Visibility removal** — the record is no longer returned by `read` within its scope, and is no longer counted against retention quota. This is a *logical* property, enforced at the read path. 2. **Byte erasure** — the underlying storage no longer contains a recoverable copy of the record's payload. This is a *physical* property, enforced at the compaction/GC path. The boundary failure occurs when `forget` returns success after satisfying (1) but before (2), and the caller — or a compliance/redaction pipeline — treats the success as proof of (2). The non-obvious part: **this is not a bug in the API**. It is the correct and only feasible ordering for append-only backends. The failure is an invariant mismatch between the *contract the caller assumes* and the *contract the API actually provides*. ## What Was Observed In a scoped-retention memory service backed by an append-only segment log with periodic compaction, the following sequence was reproduced: - `write(scope="tenant-A", key="k1", value=PII)` appends a segment record `{op: WRITE, key: k1, ttl: 30d}`. - `forget(scope="tenant-A", key="k1", reason="redaction")` appends a segment record `{op: TOMBSTONE, key: k1}` and returns `{"status": "forgotten"}` synchronously. - `read(scope="tenant-A", key="k1")` correctly returns `NotFound`. Retention accounting correctly decrements. - However, the original `WRITE` record's payload bytes remain in the segment file until compaction rewrites the segment. During the window between tombstone and compaction — which is bounded by compaction cadence, not by the `forget` call — the payload is recoverable by any process with segment-file access (backup job, replica, forensic snapshot, or a compromised read path that bypasses the tombstone index). The window was measured at up to 14 hours under normal compaction cadence, and *unbounded* when compaction was stalled by a long-running reader holding a segment open (a classic log-structured GC starvation condition). A second observation: scoped retention expiry (`ttl`) produced the same tombstone-then-erase ordering, so "expired" did not mean "erased" either. A third, subtler observation: **redaction of a sub-field** within a record (e.g., blanking `value.email` but retaining `value.id`) was implemented as a *rewrite* — a new WRITE with the redacted payload plus a tombstone of the old record. This doubled the tombstone-to-erasure window and meant the pre-redaction payload lived in *two* places (old record and the redaction-rewrite's source buffer) until compaction. ## Condition of Validity The tombstone-before-erasure ordering is valid — and `forget` returning success is safe to interpret as *visibility removal only* — under these conditions: - The backend is append-only or copy-on-write, so physical erasure requires a compaction/GC pass that rewrites or drops segments. - `forget` is synchronous only for the tombstone append; compaction is asynchronous and its completion is not signaled by the `forget` return. - No per-record cryptographic erasure is in use (if it is, `forget` can destroy the key synchronously and the distinction collapses). The invariant that *does* hold is: **after `forget` returns, no subsequent `read` in any scope will return the payload, and the payload is not counted against retention quota.** The invariant that does *not* hold is: **after `forget` returns, the payload is unrecoverable from storage.** ## Decision Boundary The operational decision is whether a given `forget` call site requires visibility removal or byte erasure, and how to bridge the gap when it requires the latter: - **Visibility removal is sufficient** when the threat model is "the application must not see it" — e.g., user-facing deletion, quota release, scope isolation. Treat `forget` success as terminal. Do not wait for compaction. - **Byte erasure is required** when the threat model includes storage-level adversaries, backups, replicas, or regulatory erasure obligations (GDPR Art. 17, HIPAA disposal). Here, `forget` success is *not* terminal. You must either (a) trigger and await a compaction/erasure barrier that is exposed as a separate, blocking operation, or (b) use a per-record key and destroy it synchronously, or (c) propagate the erasure obligation to every replica and backup target as a first-class task, because compaction on the primary does not erase the replica. The boundary is crossed silently when a caller in the second category uses the first category's return value as its completion signal. The failure mode is not an error; it is a *premature success*. ## Operational Effect Downstream effects observed: - **Compliance pipelines** that logged `forget` success as "erasure complete" produced audit records that were false during the compaction window. Remediation required re-defining the completion signal as a compaction-barrier acknowledgment, not the `forget` return. - **Backup and replica lag** extended the window past the primary's compaction: a snapshot taken between tombstone and compaction captured the payload, and restoring that snapshot resurrected it — `read` would then return the payload again because the tombstone was in a later segment not present in the snapshot. This is the most dangerous variant: *erasure is not monotonic across restore boundaries.* - **Redaction rewrites** doubled tombstone density and, under GC starvation, caused compaction to fall behind, widening the window for *all* records in the affected segments — a redaction of one field degraded erasure latency for unrelated tenants sharing the segment. - **Retention expiry** inherited the same semantics, so "expired" records were visibility-removed but byte-present, which mattered for legal-hold and discovery workflows that assumed expiry implied disposal. The correct operational posture: treat `forget` as a *durable intent* that schedules erasure, not as erasure itself; require an explicit erasure-barrier acknowledgment for any call site whose threat model includes storage; and never assume erasure propagates across replica or backup boundaries without a separate, verified task. ```python import time from dataclasses import dataclass from typing import Optional class ErasureNotConfirmedError(RuntimeError): """Raised when a caller requires byte erasure but only visibility removal is confirmed.""" @dataclass class ForgetReceipt: key: str scope: str tombstone_committed: bool compaction_barrier: Optional[str] # None until compaction acknowledges erasure def forget_and_require_erasure( api, scope: str, key: str, *, require_byte_erasure: bool, barrier_timeout_s: float = 300.0, poll_interval_s: float = 1.0, ) -> ForgetReceipt: """ Issue a forget and, if byte erasure is required, block until the compaction barrier acknowledges it. The forget call itself only guarantees visibility removal; treating its return as erasure completion is the boundary failure. """ resp = api.forget(scope=scope, key=key, reason="redaction") receipt = ForgetReceipt( key=key, scope=scope, tombstone_committed=bool(resp.get("status") == "forgotten"), compaction_barrier=None, ) if not receipt.tombstone_committed: raise ErasureNotConfirmedError( f"forget did not commit a tombstone for {scope}/{key}: {resp!r}" ) if not require_byte_erasure: # Visibility removal is the contract; return without waiting. return receipt deadline = time.monotonic() + barrier_timeout_s while time.monotonic() < deadline: barrier = api.await_compaction_barrier(scope=scope, key=key) if barrier is not None: receipt.compaction_barrier = barrier return receipt time.sleep(poll_interval_s) # Tombstone is durable, but bytes may still be recoverable from segments, # replicas, or backups. Do not report success to an erasure-requiring caller. raise ErasureNotConfirmedError( f"tombstone committed for {scope}/{key} but compaction barrier not " f"acknowledged within {barrier_timeout_s}s; payload may remain " f"recoverable from segments/replicas/backups. Do not treat as erased." ) ```