LSM Read Path

Write-optimized storage scatters the truth: the newest version of a key may sit in the memtable, in the file flushed a second ago, or in one flushed last week. The read path is the discipline that reassembles a single correct answer:

1. Check the active memtable.
2. (Real engines: check immutable memtables that are mid-flush.)
3. Check SSTables newest-first.
4. The first layer that knows the key wins — where "knows" includes knowing it is deleted.

The subtle clause is the tombstone. A tombstone is not a miss — it is a definitive answer: "this key was deleted after anything the older layers say." Code that treats a tombstone as not-found keeps searching, finds a stale value in an older file, and resurrects deleted data. Stop at the first layer holding any entry for the key, tombstone included.

Read amplification is the price of this design: a point lookup may probe every file. Bloom filters (lesson 2.2) attack it by skipping files that provably lack the key; compaction (next lesson) attacks it by shrinking the file count.

Range scans: an N-way merge

SCAN start end cannot binary-search its way to one answer — every layer may contribute keys. The general technique is a merging cursor over all the sorted sources, always advancing the smallest key, with the newest layer winning duplicates. At our scale, the same semantics fit in a few lines:

Overwriting oldest-to-newest is the mirror image of reading newest-to-oldest — both encode "newest wins." Tombstones are filtered after the merge, so a tombstone in the memtable correctly erases a live value from an old file. This N-way merge is why LSM range scans cost more than B-tree range scans — and it is exactly the machinery compaction will reuse.

Your exercise

Implement PUT, DELETE, FLUSH, GET, SCAN. The grader-caught mistakes, from the real tests: (1) tombstone shadowing across files — PUT a 1, FLUSH, DELETE a, FLUSH, GET a must print <nil>; skipping the tombstone and reading file 0 prints 1; (2) SCAN respecting a memtable tombstone — PUT a 1, PUT b 2, FLUSH, DELETE b, SCAN a z prints a=1 then one blank line, never b=2; (3) the terminator — SCAN's output is its matching key=value lines followed by exactly one blank line (just the blank line when nothing matches), and nothing before it: in the visible test, GET c printing 3 is followed immediately by b=222 — no separator line in between.