# What happens when an instance tombstones a memory key while a concurrent reader holds a stale snapshot under scoped-retention TTL eviction

**Date of Record:** 2026 November 14

**Scope:** Applies to memory tool APIs exposing read/write/forget with per-scope retention windows, TTL-based eviction, and right-to-forget (RTF) tombstones, where reads may be served from a snapshot or cache layer that is not linearly ordered with respect to writes and forgets. Does not apply to single-writer, strongly-consistent stores with synchronous tombstone propagation to all readers.

## Core Distinction

The critical distinction is between **TTL eviction** and **right-to-forget deletion**. They look identical at the read path (both cause a key to become unreadable), but they carry different invariants:

- **TTL eviction** is a *liveness* operation. The key is no longer served because its retention window closed. Re-materializing an unexpired snapshot of the value is a correctness bug only if the snapshot is *older than the TTL boundary*; a snapshot taken within the window is still a legal read.
- **Right-to-forget** is a *safety* operation. The key must never be served again, regardless of snapshot age, cache warmth, replica lag, or backup restore. Any read that returns the forgotten value — even one derived from a snapshot taken *before* the forget — is a violation.

The non-obvious boundary failure is that many memory tool implementations collapse these two into a single "key absent" signal. When a reader holds a snapshot acquired before the tombstone was applied, the read path cannot tell whether the absence is "expired, snapshot still legal" or "forgotten, snapshot now illegal." The system returns the cached value and reports success, and the RTF guarantee is silently broken. The failure is invisible because the read looks healthy.

## What Was Observed

In a scoped-retention memory tool with a read-through cache, the following sequence produced a leaked forgotten value:

1. Reader R issues `read(scope="user:42", key="ssn")` at t=0. The backing store returns the value; R's local snapshot is stamped `snapshot_epoch=E1`.
2. At t=5, a forget request `forget(scope="user:42", key="ssn", reason="RTF")` is accepted. The store writes a tombstone with `tombstone_epoch=E2 > E1` and marks the key `FORGOTTEN`.
3. At t=6, R re-reads from its snapshot without re-validating the epoch. The read path sees a non-empty cache entry, checks only TTL freshness (`now < snapshot_ttl`), and returns the value.
4. The caller receives a value that was subject to a valid right-to-forget request.

The failure was intermittent: it occurred only when the reader's snapshot TTL had not yet elapsed at the moment of the forget, and only for readers whose cache layer validated TTL but not tombstone epoch. Under load, cache-warm readers were the *most* likely to leak, because they never re-consulted the backing store.

A second observed variant: TTL eviction and forget were assigned the same internal state (`ABSENT`). A subsequent `write` to the same key after a forget succeeded, because the store could no longer distinguish "absent due to expiry, safe to rewrite" from "absent due to RTF, rewrite must be refused or quarantined." This allowed a forgotten key to be resurrected by a well-meaning writer.

## Condition of Validity

The correct behavior holds only when all of the following are true:

- Every snapshot and cache entry carries the **tombstone epoch** (or a monotonic forget-generation counter) of the store at the time it was materialized, not merely a TTL timestamp.
- The read path rejects any snapshot whose `snapshot_epoch < tombstone_epoch(key)` for that key, treating the read as a miss that must be re-resolved against the backing store.
- TTL eviction and RTF deletion are represented by **distinct states** (`EXPIRED` vs `FORGOTTEN`), and only `EXPIRED` permits automatic re-materialization or rewrite.
- The forget operation is **monotonic**: once a key is `FORGOTTEN` at epoch E, no read, write, or restore may lower the tombstone epoch or transition the key back to a readable state without an explicit, audited un-forget path.
- Replica and backup restores replay tombstones forward; a restore that predates a tombstone must not resurrect the key.

If the reader's snapshot layer does not carry the epoch, or if the store cannot cheaply answer `tombstone_epoch(key)` on the read path, the guarantee is not enforceable and the system should be treated as best-effort RTF.

## Decision Boundary

The decision boundary is the **read-path validation point**. Two implementations are defensible:

- **Epoch-checked reads (safe):** every read validates the snapshot epoch against the current tombstone epoch. Cost: one tombstone-epoch lookup per read (cacheable, but must itself be invalidated on forget).
- **Forget-invalidates-cache (safe):** the forget operation synchronously broadcasts an invalidation to all reader caches before returning success. Cost: forget latency scales with reader count; a slow or partitioned reader blocks the forget or must be fenced.

The unsafe boundary is **TTL-only validation**: the read path trusts snapshot freshness and never consults the tombstone epoch. This is correct for TTL eviction and incorrect for RTF. It must not be used when the scope is subject to right-to-forget.

A subtler boundary: if `forget` returns before cache invalidation completes (async invalidation), there is a window in which the forget is "accepted" but not "effective." The API must distinguish these. A forget that returns `ACCEPTED` but not `EFFECTIVE` does not satisfy RTF; callers relying on the return value will believe the data is gone while it is still being served.

## Operational Effect

When the boundary is crossed, the observable effects are:

- **Silent RTF violation.** No error is raised; the read returns the forgotten value and reports success. Detection requires an out-of-band audit that replays forget events against read logs.
- **Resurrection via rewrite.** If `EXPIRED` and `FORGOTTEN` share a state, a post-forget write re-creates the key, and the forget is undone by ordinary application traffic.
- **Load-correlated leakage.** Warm caches leak more than cold ones, so the violation rate rises with hit rate — the opposite of the usual cache-failure intuition, which makes it easy to miss in capacity planning.
- **Restore amplification.** A backup taken before the forget, restored after, reintroduces the key for every reader that had a snapshot at restore time.

The operational consequence is that RTF cannot be verified from the read path alone. It requires either synchronous invalidation with a returned `EFFECTIVE` status, or an epoch-checked read path that makes the leak structurally impossible. The following guard encodes the invariant that a read must never serve a snapshot older than the key's tombstone:

```python
class ForgottenKeyLeakError(RuntimeError):
    """Raised when a read would serve a value subject to a right-to-forget tombstone."""
    pass


class ExpiredSnapshotError(RuntimeError):
    """Raised when a snapshot is older than the key's TTL boundary (liveness, not safety)."""
    pass


FORGOTTEN = "FORGOTTEN"
EXPIRED = "EXPIRED"
LIVE = "LIVE"


def read_memory(store, scope, key, snapshot):
    """
    Read a key from a snapshot, enforcing the RTF invariant.

    store: object exposing state(scope, key) -> (state, tombstone_epoch)
    snapshot: object exposing value, snapshot_epoch, ttl_deadline
    """
    state, tombstone_epoch = store.state(scope, key)

    # RTF safety: a snapshot taken before the tombstone must never be served,
    # regardless of how fresh the snapshot is.
    if state == FORGOTTEN and snapshot.snapshot_epoch < tombstone_epoch:
        raise ForgottenKeyLeakError(
            f"refusing read of forgotten key scope={scope!r} key={key!r}: "
            f"snapshot_epoch={snapshot.snapshot_epoch} < tombstone_epoch={tombstone_epoch}"
        )

    if state == FORGOTTEN:
        # Snapshot was taken at or after the tombstone: the key is gone for this
        # reader too. Treat as absent, never as a cache hit.
        raise ForgottenKeyLeakError(
            f"refusing read of forgotten key scope={scope!r} key={key!r}: tombstoned"
        )

    if state == EXPIRED:
        # TTL eviction is a liveness boundary, not a safety one. A snapshot taken
        # within the window is still legal; one taken after the deadline is not.
        if snapshot.snapshot_epoch >= tombstone_epoch and snapshot.ttl_deadline >= store.now():
            return snapshot.value
        raise ExpiredSnapshotError(
            f"snapshot for scope={scope!r} key={key!r} is past TTL and must be re-resolved"
        )

    return snapshot.value


def forget_memory(store, scope, key, reason):
    """
    Apply a right-to-forget tombstone and return only after it is EFFECTIVE.
    Returns 'EFFECTIVE'; raises if the tombstone could not be made durable.
    """
    if not reason:
        raise ForgottenKeyLeakError(
            f"forget of scope={scope!r} key={key!r} requires an auditable reason"
        )
    result = store.apply_tombstone(scope, key, reason=reason, synchronous=True)
    if result.status != "EFFECTIVE":
        raise ForgottenKeyLeakError(
            f"forget of scope={scope!r} key={key!r} returned {result.status!r}, "
            f"not EFFECTIVE; RTF guarantee is not satisfied"
        )
    return "EFFECTIVE"
```