Building an LSM-tree storage engine in Rust
Every database eventually faces the same fight: random writes are slow. The LSM-tree is one very good answer, and the only way I really understood it was to rebuild it by hand.
Why not just update the data?
The obvious way to store sorted key-value data on disk is a B-tree: find the right page, change it in place. Reads love this. Writes hate it, because every write becomes a small random write to a scattered location, and disks — even SSDs — are far happier writing long sequential streams than they are seeking around.
The log-structured merge-tree flips the priority. Instead of updating in place, it buffers writes in memory, appends them to a log for safety, and periodically flushes them to disk as large, immutable, sorted files. Writes become sequential and fast. The cost is paid later, on reads and in the background, and managing that cost is what the rest of the engine is about.
Writes land in memory first
A write goes into the memtable — an in-memory sorted structure. I backed mine with a hand-written skip list rather than reaching for a crate, because the skip list is the part most people treat as a black box and I wanted to see the probabilistic balancing up close. It keeps keys sorted, supports fast inserts and lookups, and iterates in order, which is exactly what a flush needs later.
The memtable is fast because it is in RAM. It is also volatile because it is in RAM — which is the whole reason the next piece has to exist.
The log is what makes it safe
Before a write is acknowledged, it is appended to a write-ahead log on disk. If the process crashes with data still sitting in the memtable, recovery replays the log and rebuilds it. Each record carries a CRC32 checksum so a torn or corrupted tail can be detected rather than silently trusted.
Durability is not free, though, so I made it a dial. The sync policy can fsync on every write, every N writes, or every N milliseconds:
Memory fills up, so it spills to SSTables
When the memtable crosses a size threshold, it is flushed to disk as an SSTable — a sorted, immutable file — and the corresponding log is retired. Immutability is the quiet superpower here: because an SSTable never changes after it is written, it can be read without locks, cached freely, and reasoned about safely.
The file is laid out in blocks: a series of sorted data blocks, a sparse index that maps key ranges to block offsets, a bloom filter, and a footer holding metadata like the magic number, key range, and entry count. A point lookup binary-searches the index to find one block, then searches within it — no scanning the whole file.
Bloom filters skip the reads that would find nothing
Over time, a key might live in the memtable, or in any one of several SSTables, or nowhere at all. Checking every file for a key that was never written would be a lot of wasted disk reads. A bloom filter per SSTable answers a cheaper question first: “is this key definitely not in this file?”
Mine sizes itself from a target false-positive rate and uses double hashing derived from a split 128-bit xxh3 hash. At the default of roughly ten bits per key it rejects about 99% of misses outright, so miss-heavy workloads stop paying for reads that were always going to come back empty.
Compaction is the real engine
Flushing steadily produces more and more SSTables. Left alone, every read would have to consult all of them, and deleted or overwritten keys would linger forever. Compaction runs in the background, merging overlapping SSTables through an n-way merge iterator, dropping shadowed values and honoring tombstones — the empty markers a delete leaves behind.
I implemented two strategies because there is no single right answer. Leveled compaction keeps non-overlapping key ranges within each level, so a point lookup touches at most one file per level — great for reads. Size-tiered compaction merges files of similar size and writes less often — friendlier to write-heavy workloads. Making the strategy pluggable turns “how should this database behave?” into a configuration choice instead of a rewrite.
Recovery, snapshots, and staying honest
Which SSTables exist at each level is tracked in a manifest and an immutable version set. Recovery becomes mechanical: load the manifest, rebuild the current version, and replay any write-ahead logs newer than the last flush. Sequence numbers give every write an order, which is what makes a snapshot possible — a consistent point-in-time view that keeps seeing old data even while compaction rewrites the files beneath it.
None of this is trustworthy without proof, so the engine leans on 269 tests and a Criterion benchmark suite across seven workloads, including one that measures crash-recovery time by populating the store, dropping it without a clean close, and timing the reopen. In a storage engine, “probably correct” and “broken” are the same sentence.
The lesson
What stuck with me is how tightly the components depend on one another. The memtable exists because writes must be fast; the log exists because the memtable is volatile; SSTables exist because memory runs out; bloom filters exist because SSTables accumulate; compaction exists because they would otherwise never stop accumulating. Each piece is the answer to a problem the previous piece created. You cannot really understand any one of them in isolation — which is exactly why building the whole thing was worth it.
Read the Storage Engine case study or explore the source on GitHub ↗.