No. 05Storage
Tombstones
Delete has filed the paperwork.
Published
Suppose an older file contains tea=hot. Deleting the key doesn't necessarily erase that old file immediately. A newer deletion marker, a tombstone, tells a current read to stop and report “not found”.
Try it: delete the value, then the delete
Delete the value. Then see why deleting the delete is a problem.
Older file
- tea = hot @1
Newer file
- tea = DEL @2
Current readNot found
The tombstone is newer than tea=hot, so a current read stops there and reports not found.
Older file
- tea = hot @1
Newer file
- (empty)
Current readtea = hot
Wrong: the old value resurfaced. Removing only the tombstone let the read fall through to tea=hot.
Compacted file
- (empty)
Current readNot found
Safe compaction saw both records together, so the hidden value and its tombstone could go at once.
One key and two versions. Range deletion and a real engine’s full cleanup rules are separate topics.
Why?
A read takes the newest applicable record. The tombstone is that record after a delete, so it hides everything older. Take it away without also removing what it hides and the older value is newest again.
Now remove only the tombstone. The older value is still sitting there, delighted to be employed again. Your deleted key has returned.
Try that unsafe removal, then compare it with compaction that considers the relevant old data too. A valid cleanup must preserve what readers are supposed to see. If an old snapshot still needs an earlier version, that adds another reason some history must remain.
So a tombstone is useful information, not merely rubbish waiting for collection. It records that an older value must no longer be visible to a newer read. Deletion can be logically complete while physical cleanup still has work to do.