Tombstones: Deletes in an Immutable World

Tombstones: Deletes in an Immutable World

SSTables are immutable once written — you can never go back and erase a key from a file on disk. So how does an LSM tree support DELETE? It can't remove anything; it can only write more data. The answer is the tombstone: a special marker record that says "this key was deleted as of this sequence number," which behaves like a write but means the opposite.

A delete is a write

PUT k v      -> entry (k, seq, PUT, v)
DELETE k     -> entry (k, seq, DELETE, <TOMB>)

Both go through the exact same path as a normal write: appended to the WAL, inserted into the memtable, and eventually flushed to an SSTable. The only difference is the op tag. This is what makes deletes just as fast as writes in an LSM tree — no seek-and-erase, no read-modify-write, just another sorted append.

Reads must resolve tombstones

Because a key can have multiple entries scattered across memtable + SSTables (a put, then later a delete, or a put-delete-put cycle), a lookup for key k must:

1. Find every entry for k across all sources (newest sources first, in a real system — memtable before SSTables, newer SSTables before older ones).
2. Take the entry with the highest seq — that's the most recent operation.
3. If that entry is a PUT, return its value.
4. If that entry is a DELETE (a tombstone), report the key as not present — even though older PUT entries for the same key still physically exist somewhere on disk.

This is exactly the same "keep only the max-seq version" logic from k-way merge and the merge iterator — tombstones don't need special-cased read logic beyond "if the winning version is a delete, treat it as missing."

Compaction is where tombstones actually get removed

A tombstone is metadata about an absence — but that metadata itself takes up space forever unless something reclaims it. That "something" is compaction at the bottommost level. The key insight: once you know a tombstone has reached the last level a key could possibly exist in (nothing below it, no older version of this key can be lurking in a level compaction hasn't reached yet), the tombstone has done its job and both it and every older shadowed version of that key can be dropped for good.

for each key, after collapsing to (latest seq, op, value):
    if op == DELETE:
        drop this key entirely (tombstone + all older versions)
    else:
        keep only this one PUT entry

Notice the asymmetry: a surviving PUT still collapses down to a single entry (all older versions of a live key are redundant and can be dropped — only the newest matters), but a surviving DELETE at the bottom drops everything, including itself — there's no reason to keep a marker for "this doesn't exist" once you're certain no older, shadowed copy remains anywhere in the system.

The classic pitfall: dropping tombstones too early

If you dropped a tombstone at a level that isn't bottommost, you'd create a correctness bug: an older PUT for that key sitting in a lower, not-yet-compacted level would "reappear" on a future read, because the delete that was supposed to shadow it is gone. This is why real systems (RocksDB, LevelDB) track, per compaction, whether the output level is truly the last one a key's history could reach before deciding a tombstone is safe to drop — and why "bottommost" is a specific, checked condition in your exercise's PHASE 2, not just "whatever level we happen to be compacting."