Tombstones: Deletes in an Immutable World

SSTables are immutable. You can't delete a key from an SSTable — it's a sealed file. So how does the LSM tree implement delete(k)?

By writing a special record called a tombstone: a marker that says "this key is dead." A tombstone is just another write, with a higher sequence number than the value it shadows.

The Lifecycle of a Delete

1. delete(k) writes a tombstone to the WAL and the memtable.
2. The memtable flushes; the tombstone is written into a new L0 SSTable.
3. A read sees the tombstone first (newest), returns "not found."
4. Over many compactions, the tombstone moves down the levels.
5. Eventually, in the bottommost level, the tombstone meets the original value and they're both dropped.

The tombstone is essential during steps 2-4: it's the only thing telling readers (and compaction!) that older versions of k are dead.

Tombstone vs Value

The encoding distinguishes them. A common scheme:

record_type: PUT | DELETE
seq:         monotonic
key:         bytes
value:       bytes (empty for DELETE)

In RocksDB the type byte is one of: kTypeValue, kTypeDeletion, kTypeSingleDeletion, kTypeRangeDeletion (next lesson).

When Can a Tombstone Be Dropped?

A tombstone can be removed when no older versions of its key exist anywhere below it in the LSM. That means:

• It's at the bottommost level (no levels below)
• AND no older version of its key exists in this level (already shadowed by this tombstone in this level's merge)
• AND no active snapshot needs to see it (rare; usually the snapshot logic handles this)

Until those conditions hold, the tombstone must be preserved during compaction. If you drop it too early, an old version of the key in a deeper level becomes "undead" — a deleted key reappears.

Single Deletes (RocksDB SingleDelete)

When you know the previous version was a single PUT (no updates), you can use a special SingleDelete that can drop both itself AND the previous PUT at the next compaction — much faster cleanup. RocksDB uses this for workloads like "insert once, delete once" (queues).

The risk: if there are actually multiple PUTs of the same key, SingleDelete may not delete all of them. Use only when the access pattern guarantees uniqueness.

Tombstone-Driven Bloat

If you have a delete-heavy workload (a queue, a session store), tombstones can dominate. They take real disk space until they're compacted away. Compaction is throttled by config; you may end up with 10 GB of tombstones for 100 MB of live data.

Cassandra users call this tombstone hell. Mitigations:

• gc_grace_seconds: how long to keep tombstones (must be longer than your replica timeout for delete consistency).
• More aggressive compaction strategies (Leveled instead of STCS for delete-heavy CFs).
• SingleDelete where applicable.

Why Not Just Skip the Key?

You can't. The key may exist in any SSTable in any level. The tombstone is the explicit signal that propagates the deletion. Without it, deeper-level data would resurrect.