Tombstone
A marker that indicates a deleted record in a distributed database. Since replicas may not see the delete immediately, the tombstone prevents deleted data from being resurrected.
What is Tombstone?
In short
A tombstone is a special marker a distributed database writes in place of a deleted record, recording that the row was removed and when, instead of erasing it right away. It exists so that the delete can propagate to every replica and win over older copies, which stops deleted data from coming back to life during replication or anti-entropy repair.
What a tombstone actually is
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.
How it works under the hood
A tombstone is stored with the same machinery as a regular cell: a key, a deletion marker instead of a value, and a timestamp or version number. In Cassandra, for example, the timestamp is microsecond precision and last write wins, so a delete at a higher timestamp shadows any value written earlier. Reads that hit both a live value and a tombstone return nothing if the tombstone is newer.
Tombstones spread the same way data does: through replication on write, through read repair when a read finds disagreeing replicas, and through background anti-entropy processes like Merkle tree repair. The point is to give every replica a fair chance to learn about the delete before the marker is removed.
Tombstones cannot live forever or they would pile up and slow scans. Each one carries a grace period, often called gc_grace_seconds (10 days by default in Cassandra). After that window, and only after compaction runs, the database physically reclaims the space. The grace period must be longer than the time it takes for repair to reach every replica, otherwise a replica that was down could miss the delete and resurrect the row.
When to care, and the trade-offs
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.
A concrete example
Imagine a three replica Cassandra cluster holding a user profile. The user asks to delete their account. Replica A and B receive the delete and write a tombstone for the key. Replica C is rebooting and misses it entirely.
Without tombstones, when C comes back and a read-repair runs, C would offer its live copy of the profile and the cluster could copy it back to A and B, undeleting the user. With tombstones, A and B hold a deletion marker timestamped after C's value. During repair, the marker wins, C learns the row is deleted, and the account stays gone.
Ten days later, assuming repair has run and every replica has seen the tombstone, compaction physically drops both the old value and the marker. The space is reclaimed, and the delete is now permanent everywhere.
Where it is used in production
Apache Cassandra
Writes tombstones for every delete and TTL expiry, governed by gc_grace_seconds with read warning and failure thresholds at 1,000 and 100,000 scanned markers.
Amazon DynamoDB
Internally marks deleted items pending replication across replicas, and surfaces the same idea to users through Streams REMOVE records and TTL deletes.
Riak
Uses tombstones with vector clocks so deletes converge across replicas, and exposes delete-mode tuning to control how long markers persist.
Apache Kafka
In log-compacted topics a record with a key and a null value is a tombstone that tells the compactor to remove all prior records for that key.
Frequently asked questions
- Why does a deleted record still take up disk space?
- Because the delete is stored as a tombstone, not as an actual removal. The marker and often the old value both sit on disk until the grace period passes and a compaction runs, at which point the space is reclaimed.
- What is data resurrection and how do tombstones prevent it?
- Resurrection is when a deleted row reappears because a replica that missed the delete copies its stale value back to others. The tombstone carries a newer timestamp than that stale value, so during replication or repair the delete wins and the row stays gone.
- Why do too many tombstones slow down reads?
- A range read must scan past every tombstone in that range before it can return live rows. If you delete many rows in one partition, a query reads thousands or millions of markers, causing latency spikes, memory pressure, and in Cassandra an aborted query past 100,000 tombstones.
- How do I avoid tombstone problems?
- Delete less. Prefer TTLs so rows expire on a schedule, model data so you drop whole partitions at once instead of individual rows, and avoid using a partition as a delete-heavy queue. These reduce how many markers a single read has to scan.
- What is gc_grace_seconds and why is the default 10 days?
- It is how long a tombstone is kept before compaction can purge it. The default of 10 days gives operators a wide window to run repair so every replica, including ones that were down, learns about the delete before the marker disappears and resurrection becomes possible.
Learn Tombstone hands-on
This page explains the idea. The full lesson lets you step through the ring as servers join and leave, read the implementation, and check yourself with a quiz. It is one of 760+ lessons in the System Design Masterclass, from your first API call to distributed consensus. Eleven Foundation lessons are free, no signup. Lifetime access is ₹499 in India or $7.99 worldwide, one payment, no subscription.
Related lessons
Lessons that touch on Tombstone as part of a larger topic.
See also
Related glossary terms you might want to look up next.
Eventual Consistency
A consistency model where updates propagate asynchronously and all replicas will eventually converge to the same value. Trades immediacy for availability.
LSM Tree
Log-Structured Merge Tree: a write-optimized data structure that buffers writes in memory and periodically flushes sorted runs to disk. Used by Cassandra, RocksDB, and LevelDB.
Anti-Entropy
A background process that compares data between replicas and fixes differences. Uses Merkle trees to efficiently identify which data ranges are out of sync.
Strong Consistency
A guarantee that after a write completes, all subsequent reads will return the updated value. Safer but slower than eventual consistency.
Linearizability
The strongest consistency guarantee: every operation appears to take effect atomically at some point between its invocation and completion. As if there's a single copy of the data.
Serializability
A guarantee that concurrent transactions produce the same result as if they were executed one at a time in some serial order. The gold standard for database transaction isolation.