Tombstones Preserve Deletes Across Replicas Until Safe Garbage Collection
Deleting a value from one copy of replicated data is not enough to delete it from the system. Another replica may be offline, delayed, or partitioned when the delete occurs. If the active replica simply removes the record, it also removes the evidence that a deletion happened. A stale replica can later return with an older value and make that value visible again.
A tombstone turns deletion into replicated state. Instead of immediately erasing every trace of a record, the system stores a marker that says the record was deleted at a particular logical point. That marker can travel through the same replication and repair paths as ordinary data.
The difficult part comes later: deciding when the marker itself is safe to remove.
Absence carries no version
Suppose replicas A and B both contain version 7 of key k. Replica B goes offline, then A receives a delete.
If A physically removes k, its local state becomes:
A: k is absent
B: k = value, version 7When B returns, a repair process sees a value on one side and nothing on the other. Plain absence does not say whether A deleted version 7 or simply never received it. Without extra metadata, the stale value can win by accident.
A tombstone gives the absence a version:
A: k = tombstone, version 8
B: k = value, version 7Now reconciliation has comparable state. Version 8 supersedes version 7, so the delete can propagate to B.
The exact metadata differs by storage engine. Systems may use timestamps, sequence numbers, vector-like versions, epochs, log positions, or another ordering mechanism. The essential property is that the delete participates in conflict resolution.
A delete becomes a write
Treating deletion as a write has useful consequences. The normal replication path can carry it, anti-entropy can repair it, and conflict resolution can compare it with stale values.
A simplified merge rule might be:
local = value@7
remote = tombstone@8
choose remote because 8 supersedes 7This model also means a delete consumes storage and replication bandwidth. A workload with heavy churn can create many tombstones even when the number of live keys remains stable.
Tombstones are therefore not free cleanup metadata. They are part of the replicated data model until the system proves they are no longer needed.
Removing a tombstone too early can resurrect data
Consider three replicas:
A: tombstone@8
B: tombstone@8
C: value@7 (offline)If A and B garbage-collect the tombstone while C is still unreachable, the surviving state later becomes:
A: absent
B: absent
C: value@7When C rejoins, version 7 may look like the only concrete value in the system. The deleted record can reappear.
This failure is often called data resurrection. It is not caused by the original delete. It is caused by forgetting the delete before every relevant stale copy has been superseded or made irrelevant.
A safe garbage-collection rule must therefore connect tombstone lifetime to replication guarantees.
Time-based retention encodes an outage assumption
One practical design retains tombstones for a configured grace period. The system assumes replicas will recover and complete repair within that interval.
For example:
delete at T0
retain tombstone until T0 + grace_period
repair replicas during the interval
collect tombstone after the intervalThis approach is operationally simple, but the grace period is a correctness parameter, not merely a storage tuning knob. If a replica remains offline longer than the retention window and later rejoins with stale data, resurrection becomes possible unless another mechanism prevents it.
Increasing the grace period reduces that risk but keeps more tombstones and can increase read, compaction, and storage cost. Reducing it saves space sooner while narrowing the tolerated repair window.
The configured value should match actual failure detection, repair cadence, backup restoration procedures, and maximum supported replica absence.
Progress metadata can make collection more precise
Some replicated systems can determine that every relevant replica has advanced beyond the delete. A replicated log, per-replica watermark, acknowledged sequence, or compaction frontier can provide stronger evidence than elapsed wall-clock time alone.
Conceptually:
tombstone position = 812
replica A applied through 940
replica B applied through 901
replica C applied through 877
minimum applied position = 877If membership is stable and position 812 is guaranteed to be included in each replica’s history, the system has evidence that all three have crossed the deletion point.
Real implementations need more care. Replica replacement, restored backups, membership changes, lost progress metadata, and partitions can invalidate a simple minimum calculation. The garbage collector must use the same membership and durability model as replication.
Replica membership changes the safety boundary
A node that has been permanently removed should not block tombstone collection forever. A node that is merely unavailable may still hold stale data that can return.
The system needs an explicit distinction between those states. Membership protocols, decommission procedures, epochs, or generation identifiers can establish that an old replica is no longer allowed to rejoin with historical state.
A replacement replica should normally bootstrap from an authoritative current snapshot or log position rather than presenting an old local disk as valid current data.
This is one reason operational shortcuts around failed nodes can become correctness bugs. Reintroducing an old data directory after the cluster has forgotten tombstones can bypass assumptions used by garbage collection.
Compaction must preserve delete semantics
Storage engines based on immutable files often remove obsolete versions during compaction. A tombstone may appear to be the newest record for a key, with older values stored in other files or levels.
Compaction cannot discard the tombstone merely because no live value is visible in the current input set. An older value may still exist elsewhere in the storage hierarchy or on another replica.
A safe compaction decision needs enough scope to prove that no older local version can surface and that distributed retention rules permit deletion metadata to disappear.
This makes local storage cleanup and distributed replication policy related concerns. A locally redundant marker may still be globally necessary.
Reads must treat tombstones as authoritative state
A read path that queries several replicas may receive a mixture of values, tombstones, and missing responses:
replica A -> tombstone@8
replica B -> value@7
replica C -> timeoutReturning version 7 because it is the only live value would violate the version order. The tombstone must participate in reconciliation just like a newer ordinary value.
Read repair can use the result to push the tombstone to stale replicas. Quorum schemes can reduce exposure to stale copies, but quorum size alone does not remove the need for versioned deletion when replicas can diverge.
Caches need similar care. A database tombstone does not automatically invalidate an external cache. Cache invalidation, expiry, or version checks remain a separate consistency boundary.
Metrics should expose tombstone pressure and age
A system can remain available while deletion propagation quietly falls behind. Operational signals should make that state visible.
Useful measurements include:
tombstone count
oldest tombstone age
tombstones created per interval
tombstones collected per interval
replica repair lag
replica offline duration
compaction backlog
stale-version conflictsA rising tombstone count may reflect normal delete volume, delayed compaction, slow repair, or an unreachable replica. Age distributions are often more useful than a total count because they show whether markers are surviving beyond the expected repair window.
Alerts should connect retention limits with replica health. A replica approaching the maximum tolerated offline interval is a data-consistency risk even if client traffic still succeeds.
Deletion has a lifecycle
In replicated storage, deletion is not a single physical erase. It is a lifecycle: create deletion state, replicate it, reconcile stale copies, retain evidence across the supported failure window, then reclaim that evidence when the system can safely forget it.
Tombstones make that lifecycle explicit. They prevent plain absence from being mistaken for missing history and give repair mechanisms something concrete to propagate.
Garbage collection closes the lifecycle, but only under the assumptions encoded by replication, membership, and recovery policy. The storage saved by early collection is rarely worth violating those assumptions, because a forgotten delete can return as live data long after the original operation appeared complete.