Memtables and SSTables, Explained by Building Them

If you've spent any time reading about how Cassandra, RocksDB, LevelDB, or ScyllaDB store data, you'll keep running into the same two words: memtable and SSTable. They show up in different databases, written by different teams, decades apart, converging on the same shape. That's not a coincidence, it's a genuinely good answer to a hard problem, and the best way I found to actually understand why is to build a small version myself.

I've been writing VellumDB, an LSM-tree key-value store in Rust, specifically for this reason. This post is the part of that build where the two structures show up and the reasons that were previously just words in a blog post became things I had to actually decide.

The problem: writes and storage want different things

A database write needs to be fast. Ideally, appending a new key should cost roughly the same whether your dataset has a hundred keys or a hundred million. A database's on-disk storage needs to be efficient to search and scan: if reads have to check data in sorted order, or find a key without touching every byte on disk, the data has to actually live in some kind of order.

Those two goals pull in different directions. Keeping data perfectly sorted at all times means every single write potentially has to shift things around to keep that order, which gets slower as the dataset grows. Optimizing purely for write speed usually means appending blindly, which produces an unsorted mess that's expensive to search later.

The memtable and SSTable pair is the answer LSM-trees settled on: don't try to do both at once, split the problem into two stages with two different structures, each optimized for what it's actually responsible for.

The memtable: fast, sorted, in memory

The memtable is the "recent writes" buffer. In VellumDB it's just a BTreeMap:

pub struct Db {
    data: BTreeMap<Vec<u8>, Entry>,
    // ...
}

Every put and delete goes here first. Two things make this the right structure for the job:

It's in RAM, so there's no disk I/O on the hot path, an insert is fast regardless of how large the map gets.

It's sorted, and that's the part that's easy to skip past if you haven't had to think about what happens next. A plain HashMap would also be fast to insert into, but a HashMap has no order. The moment you need to write this data out to a file that you'll later want to scan in key order, or merge with other files, an unsorted structure means sorting it at that moment, which is exactly the expensive operation the memtable exists to defer. A BTreeMap keeps every insert in sorted position from the start, so writing it out later is just "walk it in order," no separate sort step required.

The memtable alone would work as a database, right up until the process restarts and everything in RAM is gone. That's a different problem (a write-ahead log solves it, and I've written about that separately), but it's worth naming here because it's exactly why the memtable can't be the whole story: RAM is fast but not durable, and it's also not unlimited. Eventually it has to become something else.

The SSTable: immutable, sorted, on disk

"SSTable" stands for Sorted String Table, and the name is almost the whole design: it's a file, its entries are sorted by key, and once written, it is never modified again. Not "rarely," never. If a key needs to change, you don't edit the file, you write a new file.

That last part sounds like a strange thing to be proud of, until you consider what it buys you. A file that's never modified in place doesn't need locking to protect concurrent readers from a writer changing it underneath them, since there's no such writer. It doesn't need to worry about a crash leaving it half-updated, since "updating" isn't a thing that happens to it. And because the memtable it came from was already sorted, writing an SSTable is a single sequential pass, appending records in order, the cheapest kind of disk write there is:

pub fn write<'a>(
    id: u64,
    path: impl AsRef<Path>,
    entries: impl Iterator<Item = (&'a Vec<u8>, &'a Entry)>,
    expected_items: usize,
) -> io::Result<Self> {
    // walk the already-sorted memtable once, write each entry in order
}

The moment the memtable crosses some size threshold, this is what happens: its contents get written out as a brand-new, immutable SSTable, and the memtable is cleared to make room for the next batch of writes. This is called a flush, and it's the hinge the whole design turns on: RAM stays bounded, because it never has to hold more than one flush's worth of recent writes, and disk storage accumulates as a sequence of sorted, append-only files instead of one structure that has to be kept sorted under constant modification.

The read path gets more interesting

Here's the part that isn't obvious until you've actually built it: once there's a memtable and potentially many SSTables on disk, a single get(key) isn't a lookup in one place anymore, it's a search across several.

The rule VellumDB uses, which is the same rule every LSM engine uses, is: check the memtable first, then check SSTables from newest to oldest, and stop at the first place the key turns up:

fn lookup(data: &BTreeMap<Vec<u8>, Entry>, sstables: &[SsTable], key: &[u8]) -> io::Result<Option<Vec<u8>>> {
    if let Some(entry) = data.get(key) {
        return Ok(entry_to_value(entry));
    }
    for sstable in sstables.iter().rev() {
        if let Some(entry) = sstable.get(key)? {
            return Ok(entry_to_value(entry));
        }
    }
    Ok(None)
}

"Newest to oldest" matters because the same key can legitimately exist in several places at once. If you write a key, it flushes to disk, and you write that same key again, the memtable now has a newer value while an older, stale copy is still sitting in an SSTable from before. Checking newest-first is what makes the stale copy irrelevant instead of a bug: you find the current value before you ever reach the outdated one.

This is also where deletes get interesting in a way that isn't obvious at first. If deleting a key just removed it from the memtable, and that key had already been flushed to an older SSTable, the delete would have nothing left to act on, the memtable never had the key to remove. Reading afterward would walk right past the now-empty memtable and find the old, supposedly-deleted value still sitting in the SSTable. The fix is that a delete doesn't remove anything, it writes a special marker (a tombstone) that says "this key is gone" and gets checked the same way a real value would, shadowing whatever's underneath it until compaction eventually cleans it up for good.

The cost this introduces, and how it's paid for

Splitting storage across many files instead of one obviously has a cost: a lookup for a key that doesn't exist anywhere has to check the memtable, then potentially every single SSTable, before it can conclude "not found." In a database that's been running a while and accumulated a hundred SSTables, that's a hundred file opens for a single missing key.

This is exactly why Bloom filters exist, sitting in front of every SSTable, a tiny, cheap-to-check structure that can say "definitely not in here" without ever opening the file, and only falls back to actually reading it when the answer might be yes. When I benchmarked this in VellumDB, the difference was a 40x-plus speedup on missing-key lookups. That number isn't a coincidence either, it's the direct, measurable cost of the memtable/SSTable split, being paid back by the next layer built on top of it.

And accumulating many SSTables in the first place is its own problem, eventually you have redundant, overlapping, and stale data spread across dozens of files. That's what compaction solves, merging SSTables back together and reclaiming the space. That part of the story, and the real write-amplification cost it exists to manage, is worth its own post.

Why this is worth building instead of just reading about

I'd read the words "memtable" and "SSTable" in database internals posts for years before any of this actually clicked. It's one thing to read "SSTables are immutable," it's a different thing to write the code that assumes it, and feel exactly which problems that assumption quietly makes disappear (no locking, no partial-write states, no in-place corruption) and which new ones it creates (recency across multiple files, stale tombstones, the cost of checking many files for one key). The design isn't clever for its own sake. Every piece of it is a direct answer to a problem the previous piece created.

The full source, including the WAL, compaction, and crash recovery hardening built on top of this, is on GitHub if you want to see how the rest of it fits together.