How do you safely garbage-collect AI-agent memory tombstones after cross-region replication and failback?

Safe tombstone garbage collection (GC) means removing obsolete memory-invalidation metadata only when no eligible replica, agent checkpoint, replay stream, or derived index can reintroduce the superseded content. A fixed time-to-live or an empty queue is not proof. When convergence cannot be demonstrated, retain minimal invalidation metadata or force a stale replica to rebootstrap from an authoritative snapshot before accepting its writes.

Why this comes after Question 262

Question 262 explains *how delayed replication resurrects stale compacted memory* and the need for revision checks and tombstones. This lesson designs a specific, auditable GC eligibility protocol, its evidence requirements, backpressure strategy, and the conditions under which retired replica history may safely be discarded. Question 234 covers general retention and deletion of versions; this focuses on *cross-region causal stability* after failback. No prior topic specifically addresses the replica-acknowledgement GC gate.

Beginner-friendly numerical production example

A LangGraph + Celery support platform runs 10,000 workflows in regions A, B and C. After failback, 12,000 obsolete memory summaries have been invalidated by newer authoritative revisions. Each logical invalidation is identified by a tenant-scoped memory key, invalidated revision, superseding revision, and a source-log sequence number (LSN/offset). Region A and B have applied and verified all 12,000; region C has only 11,940 applied, leaving 60 invalidations unknown.

A timer-based cleanup purges all 12,000 markers, then C reconnects and replays an older summary. Without durable revision authority, stale context might be served again. Instead, the GC gate checks acknowledgements for each key (or a *contiguous, verified* per-partition watermark), committed lineage, downstream consumer state and any offline replicas. 11,940/12,000 = 99.5% coverage is *not* enough to purge markers for the 60 missing invalidations. The other 11,940 are only candidates after all their own safety conditions pass.

If C cannot catch up in the approved recovery window, de-register and fence it, rebuild it from a trusted current snapshot including the latest invalidations, and prevent import of pre-rebootstrap files/events. After rebootstrap and complete downstream validation, the full 12,000 can become eligible. The numbers are illustrative, and *eligible* does not mean automatically deleted; legal retention and engine-specific safety rules still apply.

What is a safe GC certificate?

For each memory scope or bounded partition, record:

• Authority: tenant, memory ID, original and superseding revision, invalidation operation ID, writer epoch, canonical checkpoint and source offset.
• Replica membership: exact active replicas and any decommissioned/offline nodes. Prove no removed replica may rejoin with old state; membership changes require durable fencing and rebootstrap rules.
• Replication progress: contiguous per-partition applied/validated watermark *beyond* the invalidation, not merely a maximum seen offset. Acknowledged message delivery is insufficient without materialized-state validation.
• Downstream progress: vector indexing, caches, agent retrieval projections, replay consumers, backup restores and long-paused workflows must either enforce authoritative revision validity or be rebuilt/invalidated.
• Deletion obligations: retention rules, user erasure requests, audit policy and encryption-key handling. Keep only metadata essential to reject stale data; do not retain sensitive payloads in a 'tombstone' to bypass deletion requirements.
• Decision: immutable, redacted GC eligibility record with checks, owner, policy version, evidence hashes, and a final approval or hold reason.

Step-by-step GC algorithm

1. Emit an immutable invalidation event when revision 17 is superseded by 18. Keep the current revision pointer in authoritative storage; invalidate cached and vector-indexed revision-17 entries.
2. Advance verified watermarks separately for each replica and consumer. A watermark of 900 cannot imply that event 899 was applied if messages can arrive out of order; maintain gap tracking.
3. Check stable membership. If region C is offline, pause GC for affected keys or formally exclude/fence and rebootstrap it. Do not interpret no heartbeat as an acknowledgement.
4. Block source replay resurrection. Old snapshots, Celery retries, LangGraph paused checkpoints and backup-restore pipelines must validate canonical revision pointers when resuming. If they cannot, retain anti-resurrection metadata or disable their replay paths.
5. Verify end-to-end state. Compare hashed current revisions and protected canonical facts across regions; confirm vector search cannot serve superseded versions. Record any mismatches as GC blockers.
6. Evaluate safety and policy hold conditions. Only approved partitions with complete evidence, no unresolved gaps and satisfied engine/retention constraints enter the eligible set.
7. Reclaim in small batches, rate-limit storage/compaction pressure and pause on reconciliation failures. Keep durable current-revision authority independent of reclaimable transient markers; otherwise a sufficiently old event may become 'new' after metadata deletion.
8. Exercise rollback and recovery. Inject old-region reconnection, delayed replay, snapshot restoration and malformed index updates. Verify zero accepted invalid revisions and zero agent retrievals of invalidated summaries.

GC eligibility as a simple numerical test

For a particular invalidation at offset 840, suppose A reports contiguous verified progress 920, B 905 and C 815. A and B alone cannot authorize collection. With C at 815, minimum verified watermark = 815, below 840; hold. If C reaches 870, the minimum becomes 870, which crosses 840, but GC must still verify cache/index safety, branch/checkpoint replay protections and applicable retention restrictions. An offset by itself does not prove the same memory object exists in every partition: use correct per-stream membership and lineage mapping.

Important distinction: database-engine tombstones versus application markers

Apache Cassandra has its own tombstone/repair/compaction rules, including gc_grace_seconds (commonly ten days by default); application-level acknowledgement certificates do not override the storage engine's safe purge conditions. Cassandra documents that nodes offline beyond the grace period can reintroduce deleted data unless repairs are managed appropriately. PostgreSQL and DynamoDB use different replication and deletion semantics; do not copy Cassandra configuration into them. This article's proposed GC certificate is an application design pattern, not a built-in Supabase or Celery feature.

Failures, monitoring and trade-offs

• Timer-only deletion: unknown offline replicas can resurrect memory. Gate on verified convergence and engine-specific constraints.
• Incorrect max-offset metric: event gaps remain even though the largest offset passed the boundary. Require contiguous progress and proof of application.
• Forget an external index: relational memory is correct but retrieval exposes old summaries. Version-gate all retrievals and audit index repair receipts.
• Keep tombstones indefinitely: storage/cost rises and privacy obligations may be violated if tombstones retain content. Use minimal metadata, cryptographic or versioned invalidation controls, constrained retention, and audited cleanup.
• Global stall from one replica: quarantining an offline region may allow progress for unaffected partitions, but only if membership fencing and key-range isolation are enforced.
• Re-bootstrap with an old backup: reopening a historical replica without new revision authority undoes GC. Validate a durable, monotonic authority and current snapshot before read/write admission.

Monitor candidate tombstone count, age distribution, GC-blocked-by-replica count, minimum contiguous watermark, replay gap count, consumer/index lag, bytes reclaimed, stale write attempts, accepted invalid revisions (target zero) and retrieved invalid summaries (target zero). Run fault-injection tests with missing acknowledgements, delayed region C, stale snapshots, expired operational leases and long-paused workflows. Zero observed failures is not mathematical proof of safety.

Sources and further reading

• Apache Cassandra, Tombstones: https://cassandra.apache.org/doc/stable/cassandra/managing/operating/compaction/tombstones.html
• Apache Cassandra, Repair: https://cassandra.apache.org/doc/stable/cassandra/managing/operating/repair.html
• Apache Cassandra, ALTER TABLE gc_grace_seconds: https://cassandra.apache.org/doc/stable/cassandra/reference/cql-commands/alter-table.html
• LangGraph persistence and checkpoint resumption: https://docs.langchain.com/oss/python/langgraph/persistence
• PostgreSQL logical replication conflicts: https://www.postgresql.org/docs/current/logical-replication-conflicts.html