Lesson 24 · Honoring tombstones on read - Build an LSM Storage Engine

Honoring tombstones on read

A tombstone only means something if reads obey it. Today you make Get treat a tombstone as not-found, so a deleted key stays deleted even when an older SSTable still holds its old value.

The goal

Make Get return not-found when the newest entry for a key is a tombstone.

Start here - the target

TO DO

Scenario: A deleted key stays deleted despite an older value

Givena store where Put("apple","red") was flushed to an SSTable, then Delete("apple") wrote a tombstone into the memtable

WhenGet("apple") is called

Thenit returns not-found - the tombstone is the newest entry and it means "gone"

Andthe older "apple" -> "red" in the SSTable does not resurface

Background

A tombstone is only a delete if the read path stops at it. Walking sources newest-first, the first entry you find for a key is authoritative regardless of its kind: a Put means “here is the current value,” a Delete means “this key is gone, stop.” The critical bug to avoid is treating a tombstone as a miss and continuing into older tables - that would resurrect the deleted value from the SSTable underneath.

Today this only has to hold for point lookups; the same rule extends to range scans

the merged scan must drop a key whose newest entry is a tombstone - but that lands once the whole-store scan exists, a couple of lessons from now. With point-read deletes working, the store already behaves as a user expects, even though nothing was ever physically removed - the removal happens later, during compaction.

Make it work

func (d *DB) Get(key string) ([]byte, bool) {
  // walk sources newest-first as before, but stop at the FIRST
  // entry for the key whichever kind it is:
  //   Put    -> return its value, found
  //   Delete -> return not-found  (do NOT keep looking in older tables)
}

CheckpointDONE

A deleted key reads as not-found, shadowing older values. Commit and stop here.