Log-structured merge (LSM) trees optimize for write throughput by appending data to sequential log files rather than updating records in place. This design powers databases like Cassandra, RocksDB, and ScyllaDB. But the append-only model creates a subtle problem: deletes don’t actually remove data immediately. Instead, they leave behind tombstones that can accumulate and degrade performance over time.

Why Deletes Become Tombstones

In an LSM tree, data lives in sorted string table (SSTable) files that are immutable once written. When you delete a record, the database can’t simply remove it from an existing SSTable. Instead, it appends a deletion marker—a tombstone—to newer SSTables.

The tombstone is just another entry in the log, marked with a special flag indicating deletion. When a read operation searches for that key, it encounters the tombstone and knows the data has been deleted. The actual data from the original write still exists in older SSTables until compaction merges those files and reconciles the tombstone with the original record.

Compaction and Tombstone Lifecycle

Compaction is the background process that merges SSTables, removes superseded data, and reclaims disk space. When two SSTables merge, the compaction process encounters both the original record and its tombstone. At this point, the database can finally discard both.

But there’s a catch. Tombstones can’t be removed during compaction unless the database is certain no older SSTables contain the original data. In a tiered compaction strategy, where SSTables are organized by age and size, a tombstone might need to survive through multiple compaction cycles before it reaches the oldest tier where the original data resides.

In leveled compaction, the problem is more contained but still present. Tombstones must propagate through all levels before they can be safely removed. If the original data lives in level 4 and the tombstone starts in level 0, it needs to survive compactions through levels 1, 2, and 3 before merging with the data it marks for deletion.

The Read Performance Impact

Tombstones hurt read performance in two ways. First, they add noise to the search space. A query scanning multiple SSTables must check tombstones along with live data, increasing I/O and CPU overhead. Second, in range queries, tombstones for deleted records still appear in the scan path, forcing the database to skip over them.

The problem amplifies in workloads with high delete rates. A table that undergoes periodic purges or has frequent record turnover can accumulate tombstones faster than compaction can eliminate them. Databases like Cassandra expose metrics tracking tombstone counts per query precisely because this becomes a practical bottleneck.

Mitigation Strategies

Database operators have several levers to control tombstone accumulation. The most direct is tuning compaction frequency and strategy. More aggressive compaction reduces tombstone lifespan but increases I/O load and write amplification.

Time-to-live (TTL) settings can help in certain workloads. When records expire via TTL rather than explicit deletes, the database can drop entire SSTables that only contain expired data, bypassing the need to merge individual tombstones.

Some databases support tombstone compaction modes that specifically target SSTables with high tombstone density. RocksDB’s compaction filters allow custom logic to remove tombstones under specific conditions, such as when the database can prove no older data exists.

Partition-level operations offer another approach. If deletes cluster by partition—say, deleting all records for a specific user or time range—dropping the entire partition bypasses tombstone creation entirely.

Why This Matters

The tombstone problem illustrates a fundamental tension in LSM trees: optimizing for writes creates deferred costs on the read path. Understanding this tradeoff helps explain why LSM-based databases perform differently under various workloads, and why delete-heavy applications need careful schema design and compaction tuning.

For systems where deletes are rare, tombstones remain a background concern. But in analytics pipelines with frequent data expiration, multi-tenant systems with user churn, or time-series databases with rolling retention windows, tombstone accumulation becomes a first-order operational issue that shapes how you architect around the storage engine.