Flushing a MemTable to an SSTable

Why flush at all

The memtable is your fast path: writes land in an in-memory sorted structure (skip list, red-black tree, or similar) and can be acknowledged as soon as the WAL fsyncs, without ever touching a disk-resident file. But memory is finite — an LSM engine can't let the memtable grow forever, or it eventually exhausts RAM. The fix is the same one every LSM-based engine (LevelDB, RocksDB, Cassandra, and your Redis-adjacent WAL work) uses: once the memtable crosses a size threshold, freeze it and write its entire contents out as one immutable SSTable, then start a brand-new, empty memtable for subsequent writes.

This is also why the read path (a later lesson) has to check multiple places for a key — memtable, then however many flushed SSTables exist — each flush creates one more layer that a read might need to consult.

Sizing the memtable

A simple, workable estimate of memtable size is the sum of len(key) + len(value) over every currently live entry (last-write-wins on duplicates, exactly like the SSTable writer from two lessons ago):

Real engines usually track this incrementally (add the new entry's size, subtract the old value's size if overwriting) rather than recomputing the sum on every write — recomputation is O(n) per write and would defeat the whole point of a fast write path. For this exercise's scale, either approach passes, but it's worth internalizing the incremental version as the "real" technique.

When exactly does a flush trigger

The rule: after applying a PUT or DELETE, if the memtable's size has grown to reach or exceed the threshold, flush immediately — apply the write first, then check, then flush. This ordering matters: the write that pushes you over the threshold is still included in the SSTable that gets flushed, it's not held back for the next generation.

An explicit FLUSH command is a manual escape hatch — flush whatever's currently buffered (a no-op if the memtable happens to be empty). Real systems expose this too, e.g. to force a clean checkpoint before a graceful shutdown, or in tests that want deterministic SSTable boundaries rather than waiting for size-based triggers.

Tombstones: a preview

DELETE doesn't remove anything from the memtable — deleting in an LSM tree means writing a marker, because the actual value might already live in an older, immutable SSTable that this delete needs to shadow. This exercise represents that marker as the literal value <TOMB>. You'll do real tombstone handling (including eventually removing them during compaction) in a later chapter — for now, just treat a tombstone as a value like any other for flush-sizing and sorting purposes; it participates in "last write wins" exactly like a normal PUT would.

What a flush actually produces

Flushing is just: snapshot the current memtable, hand it to the SSTable writer you built earlier (sort by key, compute smallest/largest, emit), and reset the in-memory structure to empty:

Edge cases

• Threshold reached exactly, not exceeded — use >=, not >; a memtable that lands precisely on the threshold should still flush.
• Explicit FLUSH on an empty memtable — this must be a silent no-op, not an empty SSTable with zero entries (avoid emitting spurious empty SSTables into your output).
• A single write that both creates and immediately overflows the threshold — e.g., one large PUT alone pushes past the limit; it still gets included in the SSTable that flushes, then the next memtable starts genuinely empty.
• Duplicate keys across the whole input — only within a single memtable generation is "last write wins" resolved by overwrite semantics; once a key has already been flushed into an earlier SSTable, a later write to the same key creates a newer, separate entry in a later SSTable — reconciling which one is authoritative is exactly the read path's job, covered next.