Tombstone resurrection and causal stability: when deleted facts come back

The failure: a delete that doesn’t stay dead

You delete a fact. It disappears. Weeks later it is back, with its original timestamp, as if nothing happened. In a replicated store this is not a glitch — it is the predictable result of reclaiming a deletion before it finished propagating. The revived record has a name: zombie data, and the bug that produces it is tombstone resurrection.

The setup is covered in the tombstones and compaction deep-dive: a delete in an append-only store is itself an appended record, a tombstone that marks a prior entry dead. That article explains the mechanics of deletion broadly. This one is about a narrower and nastier question — when is it actually safe to throw the tombstone away — because getting that wrong is exactly how deleted facts come back.

Why early reclamation resurrects data

Walk the failure step by step. Node A writes a fact, then tombstones it. The tombstone has done its job locally: A knows the fact is gone. The tempting optimization is to free the space now — drop the original payload and the tombstone, since A no longer needs either.

But node B has been offline. It never received the tombstone; it still holds the original write. When B reconnects and the two replicas exchange state, B offers A a fact that, as far as B knows, is perfectly live. A has erased all evidence that the fact was ever deleted, so it accepts the write as new. The delete is silently undone.

This is the observed-remove problem made physical: a remove only wins if every replica has observed the remove. The tombstone is the proof of deletion. Discard it before it has reached everyone who holds the data, and you have discarded the only thing that could have out-voted the stale copy. The resurrection isn’t a race that sometimes happens — it is guaranteed the moment a lagging replica re-gossips an old value into a node that has forgotten the delete.

Causal stability: the property that makes GC safe

The fix is to refuse to act irreversibly until you can prove the action is safe. That property is causal stability. An operation is causally stable when it is known to have been delivered to every replica — when no replica can still be concurrent with it, holding state from before the operation that it might later replay.

Reclaiming a tombstone is the irreversible act. So the rule is: a tombstone may be collected only once it is causally stable. Until then it is load-bearing and must be retained, even though locally it looks like dead weight. Causal stability is the formal version of the intuition in the twin article, forgotten facts can return: a thing that merely left the working view can come back, and that is fine — but a delete you intend to make permanent must not, and stability is the line between the two.

The common mistake is to substitute time for knowledge — “the tombstone is a week old, surely everyone has it by now.” Elapsed time tells you nothing about a laptop that was shut in a drawer for a month. Premature compaction driven by a wall clock is the single most common cause of resurrection. Safety has to be derived from what replicas have actually observed.

Version vectors and anti-entropy

Two mechanisms turn causal stability from a definition into something you can compute.

A version vector (a per-replica vector of the highest update each replica has seen) lets a node answer “who has observed this delete?” without inspecting payloads. When every entry in the vector dominates the tombstone’s position, the tombstone is causally stable and reclaimable. This is the same machinery the CRDT deep-dive uses to detect concurrency — here it is repurposed to detect coverage.

Anti-entropy is the background gossip that actively closes the gap. Instead of hoping deletes reach lagging peers, replicas periodically compare summaries and ship whatever the other side is missing. Anti-entropy is what drives a tombstone toward stability; the version vector is what confirms it arrived. Together they replace “delete propagation by luck” with delete propagation as a tracked, completing process — see the peer-to-peer sync protocol deep-dive for how the exchange itself works. Reclamation then waits on a horizon computed from the slowest replica, not on a timer.

How HiveMind keeps deletes deleted

HiveMind is append-mostly: every machine holds a full local copy of the corpus, synced peer-to-peer, and a deletion must propagate to every replica. That last clause is the whole game. Because forgetting is deliberate, the system distinguishes a fact that merely faded — which is supposed to be recoverable — from one an owner chose to erase, which must stay gone. A tombstone for a deliberate erasure is held until it is provably everywhere; only then does compaction reclaim it.

The result is that the two ways a fact can “come back” are kept cleanly apart. A faded fact returning when new evidence arrives is a feature. A deleted fact returning because a stale replica out-shouted a prematurely-collected tombstone is a bug — and causal stability, backed by version vectors and anti-entropy, is what guarantees it never happens.

Frequently asked

Related