Tombstone

In a single-node database, deleting a row is simple: you remove it and it is gone. In a distributed database with many replicas, a delete is not one action, it is many actions that happen at different times on different machines. If you just erased the row locally, a replica that never got the message would still hold the old value, and the next sync could copy it back. The deleted record would resurrect itself.

A tombstone solves this by treating a delete as a write. Instead of removing the row, the database writes a small marker that says this key was deleted at timestamp T. That marker carries a version, just like a normal value, so conflict resolution can compare it against any surviving copy of the data.

When two replicas later compare notes, the tombstone with the newer timestamp beats the older live value. The delete wins, the old data stays gone, and every replica eventually agrees that the key is absent.

You care about tombstones any time you delete or expire data in an eventually consistent, replicated store. The classic pain is a workload that deletes heavily, like a queue or a time series where rows are constantly removed. Each delete leaves a marker, and a read that scans a range has to wade through every tombstone in that range before returning live rows.

This is where tombstones bite. Cassandra warns at 1,000 tombstones scanned in a single query and aborts the query at 100,000 by default, because reading through millions of deletion markers can stall a node or trigger memory pressure. Teams hit this when they model a queue on a partition and delete entries one by one.

The fixes are about avoiding deletes rather than tuning the markers. Use TTLs so rows expire on a schedule, model data so whole partitions are dropped at once, or pick storage where deletes are cheap. The trade-off is fundamental: tombstones buy you correct deletes across replicas at the cost of read amplification and disk space until they are garbage collected.