Build an LSM-tree storage engine (LevelDB / RocksDB style) (11 scenes)
Scene 04

Newest wins — and the reads get slower — the memtable-first read path across SSTables

A get walks the memtable first, then every SSTable from newest to oldest, returning the first hit it finds — which is correct, but means every flush makes reads slower because there is one more file to consult.

Previously

Disk now holds one or more sorted SSTables — but a single get has to know which one to read. The rule is simple, but its cost grows with every flush.

Scene 04

Newest wins — and the reads get slower

  1. Watch
  2. Try it
  3. Predict
  4. Capture
RAMmemtable (empty)emptyDISKSSTable shelf — newest at topL0L0/000007.sst[k … z]immutableL0L0/000006.sst[g … n]immutableL0L0/000005.sst[a … m]immutableOPERATIONidle — no operation in flightThree SSTables on the shelf. Watch a few GETs walk the read path.
What to watch for

Three SSTables on the shelf. Two GETs run: one whose key is in the newest file, one whose key is only in the oldest. Watch the cursor descend; watch the counter climb.

Continue unlocks when the animation finishes.
Implementation

Highlighted lines are the ones running in the diagram right now.

lsm.get (newest-first walk)
memtable, then SSTables newest-to-oldest; first hit wins
def get(key):
    if key in memtable:
        return memtable[key]
    for sst in sstables_newest_first():     # sorted by recency
        if key not in sst.key_range: continue
        v = sst.read(key)                   # block index + 1 block
        if v is FOUND:
            return v                        # may be an absence marker
    return not_found                        # missed every file
Why first-hit-wins is correct
newer writes ALWAYS sit above older — cursor stops fresh
# invariant the flush + WAL pipeline maintains:
#   sst[i].max_seqno < sst[j].max_seqno  for newer j
# so:
#   if a key has a live record in sst[i] AND sst[j] (j newer),
#   the cursor sees sst[j]'s record first and returns IT.
# older shadowed records are correct to ignore.
# they are NOT correct to delete — see scene 9.
Sources

Where this sits in Build an LSM-tree storage engine (LevelDB / RocksDB style)

Scene 04 of 11, in the Read side act — Newest wins; bloom filters skip the misses.. A get walks memtable → SSTables newest-first; first hit wins. Cost grows linearly with file count, especially for misses.

Up next. Reading every file on every miss is unsustainable. We need a way to say 'definitely not here' without paying a disk read — and we need it to be cheap enough to keep on every file.

All 11 scenes in Build an LSM-tree storage engine (LevelDB / RocksDB style) · Every curriculum

Designs that use this

Built with Arqly
Every scene in Build an LSM-tree storage engine (LevelDB / RocksDB style) builds on the one before it.All 11 Build an LSM-tree storage engine (LevelDB / RocksDB style) scenes