What we're building: a log-structured key-value store

Step 1 of 12, and it runs nothing. This is the map: what tinylsm does when the track is finished, then the eleven steps between here and there. Read it once so every later article has a place to land — each one assumes the state the previous step left behind and adds one piece to it.

The finished store

tinylsm is a library crate, not a program — over the next eleven articles you build it yourself, file by file. By step 12 it does this: you open a store on a directory, put byte keys and byte values in, read them back by key, and delete them. All of it survives the process exiting. Kill it mid-write and the store still opens, minus at most the write that was in flight. Deleting a key takes effect immediately, and a later compaction pass reclaims the space its old values occupied. Point lookups touch one or two files instead of scanning every byte the store owns, and range scans walk the merged contents in key order.

It is honestly called a toy. There are no transactions, no concurrent writers, no MVCC — step 12 spells out what a real database adds and where to read about it. What the track buys you is the part of a database people usually never see: append bytes, keep an index, merge files occasionally. There is nothing magical underneath sled or SQLite either, and after twelve steps you will be able to point at the layer each of their ideas lives in.

It is also a deliberately good Rust exercise. A key-value store moves bytes around constantly — Vec<u8> against &[u8], lifetimes on borrowed slices, error types that have to survive file I/O going wrong — and it has to be correct, because “the tests pass but the data is gone” is not a state a storage engine is allowed to reach. Almost every step uses only the standard library; the benchmark step is the one that pulls in outside crates.

The one idea: writes are appends

The whole design falls out of one observation. On a disk, writing to the middle of a file is slow and appending to the end is fast — the gap is orders of magnitude on spinning rust, and real even on SSDs, where in-place updates mean read-modify-write cycles and flash wear. A B-tree, which is what SQLite and Postgres use, pays that cost on every write because it updates pages in place.

A log-structured store does not pay it. Every write is an append to a log. An in-memory index maps each key to the position of its newest value, so a read is an index lookup followed by one seek. Nothing is ever overwritten: an update appends a new record and the index moves to point at it, leaving the old one behind as garbage. A delete appends too — a marker called a tombstone that says “this key is gone” — because you cannot un-append what is already on disk.

That single decision generates everything else in the track, because the log grows forever unless you do something about it:

• The log is the truth, so opening the store means replaying it — that is step 4, along with what happens when the machine dies halfway through a write.
• Garbage accumulates, so old log files get rewritten and dropped — that is compaction, and it is where tombstones finally turn into reclaimed space.
• A pure append log makes reads scan from the newest record backwards, which does not scale, so the log gets sorted into immutable files with an index — SSTables, steps 6 and 7.
• Once there are ten files on disk, reads need a way to skip the nine that cannot contain the key — that is what a Bloom filter is for, step 9.

Real systems are built this way. Riak’s default engine, Bitcask, is step 5 of this track more or less verbatim; RocksDB and Cassandra are steps 6 through 9 with years of engineering on top. You are not building a simplified fake — you are building the small, complete version of a real design.

The route

Twelve steps, published in this order. Each ends at a state the next one picks up from: a store that compiles, does one more thing, and loses one more excuse to lose data.

#	Article	What lands
2	A key-value store in memory	get, put, delete in a BTreeMap
3	Appending writes to a log	one line per write, and a checksum
4	Replaying the log on startup	rebuilding state, and skipping the torn tail
5	Compacting the log	rewriting so deletions actually free space
6	Introducing SSTables	sorted files with a sparse index
7	Merging SSTables	compaction with tombstones
8	A write-ahead log and a memtable	the pair that makes writes durable and fast
9	Bloom filters to skip disk reads	and the false-positive rate you chose
10	Range scans and iterators	implementing Iterator over merged sources
11	Benchmarking against sled and RocksDB	honest numbers, and where we lose
12	What a real database does that we didn’t	transactions, MVCC, recovery

The shape of it: steps 2–5 stand up a working store built on a single log file, crash safety included. Steps 6–10 turn it into something that scales — sorted files, merged compaction, quick negative lookups, ordered iteration. Step 11 measures the result against mature engines and reports the numbers where it loses. Step 12 is the exit ramp: what was left out and where to go next.

Unlike the CLI track, there is no network here and no async — everything runs offline, and nearly all of it verifies with plain cargo test.

What you need first

• Rust, installed and current. Every step is written and tested against Rust 1.99.0 with edition 2024 — the default cargo new produces on a current toolchain. rustup.rs installs it or brings an old install up to date.
• Ownership and borrowing. The track moves Vec<u8> and &[u8] around constantly, and step 10 builds an iterator that borrows from several sources at once. The core chapters of Ownership and borrowing are the foundation.
• Result and ?. Storage fails in I/O ways — a missing directory, a truncated file, a checksum that does not match — and none of those may end in a panic. Error handling covers the pattern the track uses.
• Cargo, casually. If you have run cargo new and cargo test before, you are set; otherwise the Cargo chapter is short.

No async anywhere, no unsafe, and no third-party crates until the benchmark step.

Where the code lives

Steps that change the project commit the result to toy-database/ in the examples repository and tag it — one tag per article, starting with the next one, so after step 2 you can git checkout lsm-ch02 and stand exactly where that article ends. If your build misbehaves partway through, checking out that tag in your clone and diffing it against your own files shows which line drifted. This article commits nothing; the first commit lands with article 2.

Next

Step 2 starts the store for real: a BTreeMap behind get, put, and delete — the interface every later step keeps while the machinery underneath it changes completely. The track overview keeps the full list current as articles land.