Skip to content

Safe Tombstone Garbage Collection

Deletion-retention policy — instantiates Asynchronous Replica Convergence

Records deletions as dated tombstones and reaps them only once every replica has surely seen the delete, so removed data cannot rise from the dead.

Safe Tombstone Garbage Collection governs the one operation that convergence handles worst: deletion. Instead of erasing a record, a delete writes a tombstone — a dated marker that says "this key was deleted as of version T" — which propagates and wins over any older live copy during merge. The mechanism's real subject is when it is safe to reap those tombstones: remove one too early and a replica that never saw the delete will, on reconnect, treat the item as simply "missing here" and helpfully re-add it. Its defining rule is therefore a timing rule — retain each tombstone until the deletion has provably reached every replica, then, and only then, reclaim the space. It is the mechanism that stops deleted data from resurrecting.

Example

A team shares a CRM address book synced across phones and laptops. Someone deletes a stale contact, "Dana Ruiz," on their phone. A laptop that happened to be offline during the delete still holds Dana; if the phone had simply dropped the row, the laptop would reconnect, notice Dana "missing," and re-add her — the classic zombie contact. Instead the delete writes a tombstone for Dana, versioned. When the laptop syncs, the tombstone is newer than its live copy, so it removes Dana too.

The tombstone is then retained for a grace window — say ≈10 days, comfortably longer than any device stays offline — and reaped only after the system is confident every replica has seen it. During that window the delete is still reversible; after it, the tombstone is gone and the removal is permanent. Dana stays deleted everywhere, and no reconnecting device brings her back.

How it works

Its distinctive move is to treat a delete as durable evidence of removal rather than an absence, and to make reaping the carefully-gated step. A delete becomes a versioned tombstone that merges like any other update, dominating older live values. The tombstone is retained for at least the maximum plausible divergence — the longest a replica might be offline or partitioned — and reaped only when convergence on the deletion is confirmed (a fixed grace period, or, better, evidence that every replica has acknowledged it). The reap is the dangerous act, because it is the moment the system forgets the item was ever deleted; everything else in the mechanism exists to make sure that moment comes after the news has fully spread.

Tuning parameters

  • Grace / retention period — how long tombstones live before reaping. Longer is safer against resurrection but accumulates tombstones that bloat storage and slow reads; shorter reclaims space sooner but narrows the safety margin.
  • Reap trigger — a fixed timer versus evidence-gated (reap only once every replica has acknowledged the delete). Evidence-gated is safer but needs a way to confirm all replicas converged; a timer is simpler but blind to a replica still down past the window.
  • Tombstone granularity — per-key markers versus a summarized range or threshold. Coarser summaries save space but lose the ability to resurrect-proof individual keys.
  • Restore window — how long a mistaken delete stays reversible before the tombstone is reaped and the removal becomes final.

When it helps, and when it misleads

Its strength is making deletion converge as reliably as any update, killing the resurrection bug that otherwise plagues eventually-consistent stores where an offline replica quietly re-adds removed data. The whole safety lives in the timing.[1] Reap before a slow or long-offline replica has seen the delete and the item comes back from the dead; retain forever and tombstones pile up, dragging read performance — a real and well-known cost of tombstone-heavy workloads. The classic misuse is setting the grace period from a hopeful guess rather than the true worst-case offline window, or reaping on a fixed timer while a replica is still down past it — both silently reintroduce deleted data. The discipline is to derive the retention window from the actual maximum divergence, prefer evidence-gated reaping over a blind timer, and monitor tombstone accumulation as its own health signal.

How it implements the components

Safe Tombstone Garbage Collection fills the deletion-lifecycle components — the ones a retention-and-reaping policy can fill:

  • deletion_retention_and_garbage_collection_rule — its core: represent deletes as retained, versioned tombstones and define exactly when they may be safely reaped.
  • rollback_or_restore_path — through the retention window the delete stays reversible (the tombstone can be lifted to restore the record); reaping is what forecloses that undo, so the policy also governs the restore window.

It does not rebuild a whole divergent replica from a good source (that is Replica Repair Job) or route an unresolvable delete-versus-update conflict to a human (that is Exception Queue Review). It governs only the delete-and-reap lifecycle.

Notes

Safe reaping is only as safe as the convergence evidence behind it: the tombstone can be dropped once, and only once, every replica has surely seen the delete. That makes this mechanism a consumer of whatever confirms replicas have converged — a version-frontier check or a completed background sweep. Reaping "blind" on a timer that assumes convergence, rather than confirming it, is the single trap that turns safe tombstone GC back into the resurrection bug it exists to prevent.

References

[1] A tombstone is a marker written in place of a deleted record so the deletion itself replicates and outlives any stale copy; systems such as Apache Cassandra retain tombstones for a configured grace period (gc_grace_seconds) before garbage-collecting them, precisely so a delete has time to reach every replica before its evidence is discarded. Reaping too early is the standard cause of "deleted data coming back." ↩