Flushing a MemTable to an SSTable

When a memtable fills, it is sealed (becomes immutable) and a fresh memtable replaces it. A background thread then flushes the sealed memtable to a new SSTable on disk.

The Flush Algorithm

Because the memtable is already sorted, this is a single linear walk. No sorting cost.

After the Flush

When the flush completes:

1. Update the MANIFEST: add the new SSTable to L0, record its key range and sequence range.
2. fsync the MANIFEST entry.
3. Delete the WAL whose entries are now safely in the new SSTable.
4. Drop the sealed memtable from RAM.

Steps 1-2 are the atomic commit: until the MANIFEST update is durable, the new SSTable is invisible. After the MANIFEST update, recovery will see the SSTable and the WAL is redundant.

Why "Level 0" Is Special

In leveled compaction, the first level (L0) is the only level where SSTables can have overlapping key ranges. That's because L0 SSTables come directly from memtable flushes, each covering whatever keys happened to be hot during that window of time.

L0:  [a..z][a..z][a..z][a..z]   <- overlapping flushes; recent writes
L1:  [a..f][g..m][n..z]         <- non-overlapping after L0->L1 compaction
L2:  [a..b][c..d][e..f]...      <- non-overlapping, 10x larger total than L1

A point lookup at L0 must check every L0 SSTable (because any of them could contain the latest version of a key). Below L0, at most one SSTable per level can contain a given key — much faster lookup. Bloom filters help mitigate the L0 cost.

Stalls and Throttles

If writes outpace flushes, L0 grows large and reads slow down. Engines defend with write stalls: once L0 has more than, say, 8 files pending compaction, incoming writes are throttled. Once it has more than 20, writes are blocked entirely until compaction catches up.

This is the classic LSM "compaction debt" failure mode. Tuning memtable size, flush concurrency, and compaction throughput is most of LSM operational tuning.

Sequential Throughput Hot Path

Flushes and compactions are both sequential reads and sequential writes — perfect for spinning disks and great for SSDs. The whole architecture is designed so that no thread, ever, does a random write to a live file.