← ~/projects

case study · rust · storage engines · databases

Storage Engine — where a key-value store actually keeps its data

A persistent LSM-tree key-value store built from first principles in Rust. It is the core design behind LevelDB, RocksDB, and Cassandra — rebuilt by hand to understand how a database turns slow random writes into fast sequential ones without losing data when the process dies.

View on GitHub ↗Read the blog post
roleSole engineer
stackRust 2024, skip lists, bloom filters, Criterion
typeLSM-tree key-value store
sourceG1DO/Storage-Engine ↗

The problem

A disk is happy writing in long sequential streams and slow when it has to jump between random locations. A B-tree keeps data sorted by updating pages in place, which is great for reads but means every write is a random write. The LSM-tree makes the opposite trade: it buffers writes in memory, appends them to a log, and only ever writes to disk in large sorted batches. Reads pay a little more; writes get dramatically faster. I built the whole machine by hand, in Rust, with almost no external crates, to understand exactly where that trade-off lives.

What I built

A skip-list memtable — the in-memory sorted write buffer — written from scratch rather than pulled from a crateA checksummed write-ahead log with three sync policies (every write, every N writes, every N milliseconds) to tune durability against throughputImmutable SSTables with a block-based layout: data blocks, a sparse index, a per-file bloom filter, and a footer of metadataBloom filters using double hashing over a 128-bit xxh3 hash to skip disk reads on keys that were never writtenTwo pluggable compaction strategies — leveled (RocksDB-style) and size-tiered — driven by an n-way merge iteratorA manifest and immutable version set for crash-safe recovery, plus point-in-time snapshots and bounded range scansAn LRU block cache and a stats layer tracking write amplification, cache hit rate, and compaction work

Engineering decisions

Log before you acknowledge. Every write goes to the write-ahead log before it is considered durable. A crash mid-write is recovered by replaying the log, so an acknowledged write is never lost.Make durability a dial, not a default. Fsync on every write is safest but slow; batching syncs is faster but risks the last few writes. Exposing the sync policy as an option makes that trade explicit instead of hidden.Spend memory to avoid disk. A bloom filter answers “this key is definitely not here” in a few bits, so a lookup for a missing key skips the SSTable entirely instead of reading and searching it.Treat compaction as the real engine. Leveled compaction keeps non-overlapping key ranges per level, so a point lookup touches at most one file per level; the strategy is pluggable because the right choice depends on whether the workload is read- or write-heavy.

What it taught me

The pieces of an LSM-tree only make sense together. The memtable exists because writes must be fast; the write-ahead log exists because the memtable is volatile; SSTables exist because memory is finite; bloom filters exist because SSTables accumulate; and compaction exists because SSTables would otherwise pile up forever. Each component answers a problem created by the one before it.

Building it in Rust also made the correctness bar concrete. Tombstones have to propagate through every level so a deleted key stays deleted after compaction; a snapshot has to keep seeing old data even as compaction rewrites the files underneath it. The repository leans on 269 tests and a Criterion benchmark suite across seven workloads — including crash-recovery time — because in a storage engine, “probably correct” is the same as broken.

← All projectsRead: Building an LSM-tree storage engine →