Skip to main content
Lexicon
Lexicon

Tombstone (Distributed Systems)

Difficulty: Advanced
3 min read

In plain English

Plain definition

Instead of instantly erasing deleted data, the system writes a small 'this was deleted' marker called a tombstone. This marker gets copied around just like normal data, so that replicas which haven't heard about the delete yet don't accidentally bring the old value back to life.

In systems built on Log-Structured Merge (LSM) trees (Cassandra, ScyllaDB, HBase, RocksDB) or leaderless replication (Dynamo-style quorums), a DELETE cannot simply erase bytes from an immutable SSTable or a divergent replica. Doing so creates a causality problem: if Replica A deletes a key and Replica B never receives the delete (due to a partition), a subsequent read-repair or Merkle tree sync could see B’s older, present value and interpret it as “newer” data to propagate back to A, effectively resurrecting deleted data (a classic zombie problem). The tombstone solves this by writing a delete marker with its own timestamp/version, which participates in the same conflict-resolution logic (LWW, vector clocks) as regular writes.

Architecturally, a tombstone is not free—it is a small piece of metadata that must be stored, replicated, and eventually compacted away. Key implementation details include:

  • GC Grace Period: In Cassandra, a tombstone cannot be purged from disk until a configurable gc_grace_seconds (default 10 days) has elapsed. This window exists to give lagging or offline replicas time to receive the tombstone via repair before it disappears; purging too early reintroduces the zombie-data problem.
  • Compaction Interaction: Tombstones are only physically purged during compaction, and only if the tombstone and the data it shadows exist in the same compaction set post-grace-period. This makes tombstone removal non-deterministic in timing—it depends on when compaction happens to touch the relevant SSTables.
  • Range Tombstones: Deleting an entire partition or a range of clustering keys writes a single partition or range tombstone rather than one per row, which is far more efficient but still requires the same read-path filtering logic.

The most notorious operational failure mode is the tombstone accumulation (or “tombstone hell”) problem, common in queue-like or wide-row access patterns where entries are written and quickly deleted. Read paths must scan and filter past tombstones to find live data, and if a single read scans more of them than Cassandra’s tombstone_failure_threshold (default 100,000; a warning is logged from 1,000), the read is aborted entirely to protect the coordinator node, surfacing as a TombstoneOverwhelmingException. This is a direct architectural signal that the data model is misaligned with the storage engine’s delete semantics.

Beyond storage engines, tombstones are foundational to CRDTs (e.g., OR-Sets) where a delete must be commutative and idempotent across concurrent merges, and to gossip-based membership protocols where a node’s departure is propagated as a tombstone state to distinguish ‘left the cluster’ from ‘temporarily unreachable,’ preventing the node from being incorrectly resurrected by a stale gossip message. In all cases, the tradeoff is identical: durability of delete-intent versus storage/read overhead, mediated by a bounded retention window.

About this page

Credited to

Dates

Published

Corrections

No corrections are listed for this page. Some review sweeps corrected pages without naming each one; those are in the corrections log.

Was this useful?

Reports go to the site owner and are used to correct pages. Corrections are listed at /corrections.