Writing an SSTable

The memtable fills up and has to go somewhere. That somewhere is a file written exactly once and never modified again — and the trick to reading it is the last eight bytes.

A full memtable gets written to disk as a sorted string table: one file, written once, never modified. Not updated in place, not appended to. Immutability is what makes the rest of the design tractable — a file that never changes can be read without locks and deleted without coordination.

Because the memtable is a BTreeMap, its iterator already comes out in key order, so writing the file is a linear walk with no sort step.

The layout

[entry][entry][entry]...     <- the data, in key order
[index entry][index entry]...<- key -> byte offset of its entry
[index_offset: u64]          <- 8 bytes, where the index begins

Entries are framed like log records — length-prefixed key, length-prefixed value, with the same tombstone marker standing in for the value length when the entry is a delete.

Then the index: every key again, paired with the byte offset where its entry lives. Then, right at the end of the file, a single u64 saying where that index started.

Why the offset goes last

You cannot put it first. The index lives after the data, and you do not know how long the data is until you have written all of it. Writing a header would mean either buffering the whole file in memory or seeking back to patch the header afterwards — and a seek-back-and-patch is precisely the kind of partial write that leaves a corrupt file behind after a crash.

So it goes at the end, where it can be written once, in order, forward-only. To read the file you seek to eight bytes from the end, read the offset, jump there, and load the index.

The index is in memory, the data is not

open() reads the index into a Vec<(String, u64)> and stops. The entries stay on disk. A get is then a lookup in the in-memory index followed by one seek and one read for the value — rather than a scan of the file.

That is fine at this size and will not stay fine. Every key of every table in RAM does not scale, which is what a sparse index fixes: keep every Nth key, binary search to the nearest one, scan a short block from there. Same idea, bounded memory. That is a later problem.

The file is sync_all()ed before flush_from_memtable returns. An SSTable that is not durable is not worth clearing the log for.