SSTable Anatomy: Sorted Strings on Disk

From memtable to disk: what makes it "sorted" and "immutable"

Everything you've built so far lives in memory: writes go into a memtable, an in-memory sorted structure (think a skip list or balanced tree) that's fast to insert into and fast to iterate in key order. But memory is finite and volatile — eventually the memtable has to become a durable, disk-resident file. That file is the SSTable (Sorted String Table), and its two defining properties are right there in the name:

• Sorted — every key/value pair is written in key order, once, and never reordered again.
• Immutable — once written, an SSTable is never edited in place. Later writes to the same key go into a newer SSTable; reconciling which one wins happens at read time (a topic for the read-path lesson), not by mutating old files.

Sortedness is what makes everything downstream possible: a sorted file supports binary search, range scans, and — crucially, as you'll see in later lessons — building a sparse index over it instead of indexing every single key.

Anatomy: data, index, footer

A real SSTable (as in LevelDB, RocksDB, or Cassandra) is laid out in three logical sections, and this exercise mirrors that shape in a plain-text format so you can inspect it by eye:

DATA
<key>=<value>
<key>=<value>
...
INDEX
NUM_ENTRIES=<n>
SMALLEST=<key>
LARGEST=<key>
END

• The DATA section is the payload — every key/value pair, sorted, one per line.
• The INDEX/footer section is metadata about the data: how many entries, and the key range covered. In production systems the footer typically also stores block offsets and a pointer to a bloom filter (both coming in later lessons) — but the core idea is the same: cheap-to-read summary information that lets a reader decide whether it's even worth opening the DATA section at all.

SMALLEST/LARGEST might look like a small detail, but they're doing real work: a read path checking dozens of SSTables across several levels needs to reject files with a single string comparison (key < SMALLEST or key > LARGEST → skip) rather than scanning every file's contents. You'll build exactly that skip-check in the Block Index lesson.

Building the writer

The mechanics are simple, and simplicity is the point — an SSTable writer's whole job is: collect everything, sort it, and write it out in order.

"Last write wins" here mirrors exactly how a memtable itself behaves — if a key is written twice before a flush, only the most recent value should ever reach disk. Using a plain dict for staging (rather than writing pairs out as they arrive) is what makes "last write wins" trivial: later assignments simply overwrite earlier ones in the same dict slot, and you only serialize once you're ready to sort and emit.

Edge cases

• Zero entries — a flush of an empty memtable is a degenerate but legal case. NUM_ENTRIES=0, and SMALLEST/LARGEST become the sentinel NONE rather than crashing on an empty list's min()/max().
• Duplicate keys in the input — don't assume the input arrives pre-deduplicated; the last occurrence in arrival order must win, not the lexicographically last one.
• Lexicographic vs. numeric sort — keys sort as strings ("10" sorts before "2"), which is a source of confusion if you're used to numeric ordering; SSTables (and Redis-like stores generally) sort byte-wise unless you build a custom comparator.

This lesson is the "shape of the file" — later lessons build blocks, indexes, and bloom filters inside this same three-part skeleton, so get comfortable with DATA/INDEX/END as the mental model for everything that follows.