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

Flush — pay the IOU once

When the memtable fills, it is frozen and written out as a single immutable, key-sorted file on disk — that file is called an SSTABLE (the new term — short for 'Sorted String Table', meaning a file whose key-value records are stored in key order); the WAL that fed it is then deleted, because the SSTable is now the durable record and the WAL's IOU is paid.

Previously

The memtable can't grow forever, and the WAL it dragged along grows with it. Once the memtable crosses a threshold, we have to do something with what we've collected.

Scene 03

Flush — pay the IOU once

  1. Watch
  2. Try it
  3. Predict
  4. Capture
RAMmemtable (sorted)emptyDISKWAL — append-onlyemptySSTable shelf — disk (empty)shelf is emptyOPERATIONidle — no operation in flightMemtable empty, WAL empty, shelf empty.
What to watch for

New term this scene: SSTABLE (Sorted String Table) — an immutable, key-sorted file on disk. Watch the memtable fill, freeze, stream to disk in sort order as one new SSTable, and the WAL get deleted. Four beats.

Continue unlocks when the animation finishes.
Implementation

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

lsm.flush
freeze, sequential sorted write, fsync, delete WAL
def flush(memtable, wal):
    memtable.freeze()                # no more writes accepted
    sst = open_new_sstable(next_id())
    for (k, v) in memtable.iter_sorted():
        sst.append_block(k, v)       # sequential write
    sst.write_block_index()          # first key of each block
    sst.fsync()                      # the SSTable is durable
    wal.delete()                     # IOU paid; WAL no longer needed
    return sst                       # immutable forever
SSTable on disk
sorted blocks + a tiny index — binary-searchable
# SSTable layout (logical):
  block_0: [key, value]+   # smallest keys
  block_1: [key, value]+
  ...
  block_n: [key, value]+   # largest keys
  block_index: [(first_key_in_block, offset)]
  footer: [block_index_offset, ...]
# read: load index → binary-search → read 1 block
Sources

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

Scene 03 of 11, in the Write side act — Sort in RAM, log on disk, flush to immutable SSTables.. Frozen memtable streams sequentially to disk as a single immutable sorted file (an SSTable); the WAL is then deleted.

Up next. Disk now holds an immutable sorted file — but a single get has to know to look there. And as flushes pile up, the shelf fills with files. The read path needs a rule.

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