Tombstones: Why Deleting Data in a Distributed Store Is Harder Than Writing It

In a single-node database, DELETE removes a row and you are done. In a leaderless, eventually consistent store with three replicas, simply erasing the row would be a bug. This note explains why, how tombstones fix it, and the operational problems they bring.

The resurrection problem

Suppose key user:42 lives on replicas A, B and C. A client deletes it with quorum 2, so A and B drop the row while C is briefly offline. Later, anti-entropy repair compares the replicas. C still has user:42; A and B have nothing. With no record of the delete, repair can't tell "deleted" from "never received", so it copies the old value back to A and B. The deleted data has come back to life.

The fix: write the delete

Instead of removing the value, the store writes a special marker, a tombstone, carrying the key and a timestamp. A tombstone is just another write: it replicates, it wins conflict resolution against older values (last-write-wins by timestamp), and repair spreads it to C. Reads that meet a tombstone return "not found".

value(user:42, ts=100)   vs   tombstone(user:42, ts=180)
=> tombstone wins, read returns nothing

When can a tombstone be forgotten?

Tombstones can't live forever, or storage fills with markers for data that no longer exists. Cassandra keeps them for gc_grace_seconds (10 days by default) and purges them during compaction after that. The contract: every replica must be repaired at least once inside that window. If a node is down longer than the grace period and then rejoins, it may still hold the old value after everyone else has purged the tombstone, and the zombie row returns. That's why the usual guidance is to rebuild a node that has been offline past the grace period rather than just restarting it.

Why tombstones hurt read performance

Design patterns that avoid the pain

How to bring this up in an interview

If you design a replicated key-value store, interviewers often ask "how do deletes work?" A strong answer covers: deletes are writes (tombstones); they win by timestamp; they're kept for a grace period that has to be longer than your repair interval; and they cost read performance, which shapes data modelling. Mentioning the zombie-data failure mode shows you understand why the mechanism exists, not just its name.

If you'd like to rehearse explaining trade-offs like this out loud, Linkjob AI offers mock interviews and real-time answer suggestions for system design rounds.

Summary

Tombstones turn deletes into replicated writes so they survive partial failures and repair. The cost is extra storage until compaction, slower scans over deleted ranges, and a hard operational rule: repair every replica inside the grace window.

Published on htmlkin.io