# Why does an instance of a memory record survive its own forgetting: the tombstone-write ordering invariant in scoped retention APIs

**Date of Record:** 2026 November 9

**Scope:** Applies to memory tool APIs that expose write/read/forget operations with per-record TTL and scope-based retention (tenant, session, subject). It does not apply to append-only logs without deletion semantics, nor to systems where forget is implemented as a synchronous physical purge of the underlying store before the call returns.

## Core Distinction

There are two distinct notions of "forgotten" in a scoped memory API, and they diverge precisely at the boundary of a record's TTL expiry:

1. **Logical forgetting** — the record is marked unreachable for reads. A forget call flips a visibility bit, advances a generation counter, or writes a tombstone. Subsequent reads in the declared scope return nothing.
2. **Physical forgetting** — the bytes are removed from the backing store. This is what a right-to-be-forgotten (RTBF) audit actually checks, and what a TTL sweeper eventually performs.

The non-obvious failure is that these two are not ordered by the API contract. A record can be *logically forgotten but physically present*, and — the dangerous inverse — *physically expired by TTL but logically resurrectable* if a concurrent write re-inserts the same key under a stale generation. The invariant that must hold, and that most implementations only accidentally satisfy, is:

> For any key `k`, once a forget operation for `k` returns successfully at logical time `t_f`, no read at logical time `t > t_f` may return a value for `k`, regardless of TTL state, regardless of any concurrent write whose acceptance decision was made before `t_f`.

This is a **linearizability boundary on the forget operation**, not on the write operation. Most engineers reason about write linearizability and assume forget inherits it. It does not, because forget is usually implemented as a *negative write* (tombstone) that races with positive writes in a different code path.

## What Was Observed

In a multi-tenant memory service with per-record TTL (default 24h, scope-overridable) and a `forget(scope, key)` call, the following sequence reproduced a resurrection:

1. Agent A issues `write(scope=S, key=k, value=v, ttl=3600)`. The write is accepted, assigned generation `g=7`, and stamped with `expires_at = now + 3600`.
2. At `now + 3599`, a TTL sweeper begins a scan. It reads the record, sees `expires_at` in the near future, and enqueues a physical delete. The enqueue is asynchronous.
3. At `now + 3599.5`, a compliance job issues `forget(scope=S, key=k)`. The forget handler writes a tombstone at generation `g=8` with `expires_at = +inf`. The call returns success. The audit log records the forget.
4. At `now + 3600.1`, the sweeper's queued delete executes. It deletes by key, not by generation. It removes the tombstone at `g=8` (because the tombstone shares the key) along with the expired value.
5. At `now + 3600.2`, a read for `k` in scope `S` finds no tombstone and no value — returns empty. Correct by accident.
6. But at `now + 3600.3`, Agent B retries a delayed write from a queue: `write(scope=S, key=k, value=v', ttl=3600)`. The write handler checks the tombstone — gone — and accepts at `g=9`. The forgotten key is now live again with new content.

The audit trail says the key was forgotten at step 3. The store says the key exists at step 6. Both are true under their respective definitions. The RTBF obligation is violated because the *tombstone* was collected by a sweeper that had no concept of generation, and the subsequent write had no way to know a forget had ever occurred.

A second, quieter variant: the sweeper deletes by `(scope, key)` and a *concurrent* write at the same key lands between the sweeper's read and its delete. The sweeper deletes the fresh write. This is a lost-write, not a resurrection, but it shares the root cause: **the sweeper's delete predicate is key-based while the forget's guarantee is generation-based.**

## Condition of Validity

The resurrection is only possible when all of the following hold simultaneously:

- Forget is implemented as a tombstone (negative write) rather than a synchronous purge.
- TTL expiry and forget share the same key namespace and the same physical deletion path.
- Physical deletion is key-addressed, not generation- or version-addressed.
- Writes are accepted based on tombstone presence at acceptance time, not on a monotonic forget-watermark per key.
- There exists any asynchronous or delayed write path (retry queues, agent replays, batch imports) that can reissue a write after the forget returns.

If any one of these is absent, the failure does not reproduce. In particular, a system that deletes by `(key, generation)` and rejects writes whose generation is below the highest observed forget generation is immune, even with asynchronous sweepers.

## Decision Boundary

The operational decision is not "should we use tombstones" — tombstones are necessary for linearizable forget under concurrency. The decision is **what the sweeper is allowed to delete, and what the write path is allowed to ignore.**

- A sweeper may delete a record only if the record's generation is strictly less than the current forget-watermark for that key, OR the record is a value (not a tombstone) whose `expires_at` has passed AND no forget has been recorded for that key since the value was written.
- A write may be accepted only if its proposed generation exceeds the forget-watermark for the key. The watermark must be durable and must survive tombstone collection. Collecting the tombstone must not collect the watermark.
- The forget-watermark is the actual RTBF artifact. The tombstone is an optimization. Conflating them is the bug.

The boundary condition to test explicitly: **forget followed by TTL-sweep followed by delayed write.** If your test suite only covers forget-then-read and TTL-then-read, you will not see this.

## Operational Effect

The effect is a compliance-visible resurrection window whose length equals the maximum delay of any asynchronous write path in the system — unbounded in practice, because retry queues and agent replay buffers have no upper bound unless you impose one. The audit log will show a successful forget; the store will show live data; and the discrepancy will only surface during a right-to-be-forgotten audit or a data-residency review, typically months later.

Mitigation is to make the forget-watermark a first-class, durable, per-key monotonic value that outlives the tombstone, and to make the sweeper generation-aware. The cost is that watermarks accumulate; they must be compacted by scope-level epochs, not per-key, or the watermark store becomes the new unbounded growth problem. The correct compaction unit is the scope: a scope-level forget epoch advances only when all keys in the scope are known-forgotten, which is rare, so per-key watermarks within an active scope are the practical compromise.

The following guard encodes the write-acceptance check and the sweeper predicate as a single invariant, raising on violation rather than silently resurrecting.

```python
class ForgetInvariantViolation(RuntimeError):
    """Raised when a write or sweep would violate the forget-watermark invariant."""
    pass


class MemoryRecord:
    def __init__(self, key, generation, value, expires_at, is_tombstone=False):
        self.key = key
        self.generation = generation
        self.value = value
        self.expires_at = expires_at
        self.is_tombstone = is_tombstone


class ScopedMemory:
    def __init__(self):
        # key -> highest generation for which a forget has returned successfully
        self.forget_watermark = {}
        # key -> MemoryRecord (value or tombstone)
        self.records = {}

    def forget(self, key, generation):
        if generation <= self.forget_watermark.get(key, -1):
            raise ForgetInvariantViolation(
                f"forget for {key!r} at gen {generation} does not advance watermark "
                f"{self.forget_watermark.get(key)}"
            )
        self.forget_watermark[key] = generation
        self.records[key] = MemoryRecord(key, generation, None, float("inf"), is_tombstone=True)

    def write(self, key, generation, value, expires_at):
        watermark = self.forget_watermark.get(key, -1)
        if generation <= watermark:
            raise ForgetInvariantViolation(
                f"write for {key!r} at gen {generation} is at or below forget "
                f"watermark {watermark}; refusing to resurrect forgotten key"
            )
        self.records[key] = MemoryRecord(key, generation, value, expires_at)

    def sweep(self, key, now):
        rec = self.records.get(key)
        if rec is None:
            return
        watermark = self.forget_watermark.get(key, -1)
        if rec.generation <= watermark:
            # Safe to collect: the watermark outlives the record.
            del self.records[key]
            return
        if not rec.is_tombstone and rec.expires_at <= now:
            # TTL expiry with no forget above this generation: collect value,
            # but never collect past the watermark.
            if rec.generation > watermark:
                del self.records[key]
                return
        raise ForgetInvariantViolation(
            f"sweeper refused to touch {key!r}: gen {rec.generation} "
            f"vs watermark {watermark} (tombstone={rec.is_tombstone})"
        )
```