Making the layers behave like one database

By now there is a log, a memtable and a growing pile of immutable files. Each works. None of them is a database until a single read can walk all three and give one answer.

Three components, three storage media, one question: what is the current value of this key?

The rule is newest wins, and the layers are already in age order. The memtable holds the most recent writes. SSTables are older, and among them the most recently flushed is the newest. So a read walks them in that order and stops at the first definite answer.

Where the three-state Lookup pays off

"First definite answer" is doing the work, and it is only expressible because Lookup has three variants:

memtable.get(key)
  Found(v)  -> return Some(v)      // stop
  Deleted   -> return None         // stop — deliberately absent
  NotFound  -> fall through to the newest SSTable, then the next...

A tombstone is a stopping condition, not a miss. If Deleted fell through like NotFound does, the search would continue into an older table, find the value from before the delete, and return it. The delete would silently undo itself. The enum from the memtable post is what prevents that, three layers later.

Scanning is harder than getting

A range scan cannot stop at the first answer — it has to produce every live key in order, across all the layers at once. That is a k-way merge: hold an iterator over each source, repeatedly take the smallest key across all of them, and when several sources have the same key, take the one from the newest layer and discard the rest.

Tombstones get dropped at the very end of the pipeline, not in the middle, which is why the merge iterator exposes live() as a separate step. The merge has to see the tombstone in order to know it should suppress the older copies of that key; only once it has won does it disappear.

One handle on the front

LsmTree puts put, get, delete, scan and flush over the three layers, and handles the flush sequence: write the SSTable, fsync it, and only then clear the log. That order is not negotiable — clear the log first and a crash in between loses everything the memtable was holding.

Engine then wraps that in an RwLock, so many readers can share it and writers take it exclusively. Single writer, many readers, which is the shape the LSM design wants anyway.