I Built LSM Trees for a Storage Engine

I have started building a storage engine in Rust. It now has a name too: pocket-lsm, published as an experimental 0.1.0 crate with the source on GitHub.

This project is still in progress. The current version is not a finished database, and I do not want to pretend it is. It is the first usable slice: enough of an LSM-tree write and read path to make the next problems visible.

The goal is not to wrap RocksDB, or to hide the hard parts behind a crate, or to build an API that looks impressive before the internals exist. The goal is to make the storage path explicit enough that I can point at each moving piece and say:

this is why writes are fast, this is why reads are more complicated, and this is where the next set of problems begins.

So the first milestone was an LSM-shaped engine.

Not a production LSM yet. There is no compaction policy, block cache, or async I/O path. But the core shape is there:

put/delete
  -> append to WAL
  -> update active memtable
  -> rotate full memtable into immutable queue
  -> flush immutable memtable to SSTable
  -> read active, immutable, and disk tables newest-first

That is enough machinery for the design to stop being abstract. The newer checkpoint adds the pieces that make the engine restartable: WAL replay, manifest records, and a CURRENT file for durable ids.

Why Start With An LSM Tree?

A log-structured merge tree is built around a tradeoff that feels almost too simple:

make writes cheap now, pay organization costs later.

Instead of updating random pages on disk for every write, the engine accepts writes into memory and later flushes sorted runs to disk. Reads then have to search multiple places: the current memtable, older immutable memtables, and one or more SSTable files.

That tradeoff is the entire project in miniature.

If writes are append-friendly, reads need structure. If disk files are immutable, deletes need tombstones. If there are many disk files, compaction eventually becomes unavoidable. If misses are common, Bloom filters stop the engine from touching files it can prove do not contain the key.

I wanted the first version to expose those pressures instead of skipping straight to optimizations.

The Write Path

The engine has a small synchronous API:

engine.put(b"alpha".to_vec(), b"one".to_vec())?;
engine.delete(b"alpha".to_vec())?;

Each write first receives a sequence id and is appended to a write-ahead log:

record length
checksum
record type
sequence id
key length
value length
key bytes
value bytes

There are two record types today: Put and Delete.

The checksum matters because a WAL is only useful if replay can distinguish a complete record from corrupt or partial bytes. The log code can replay records and verify checksums, and engine startup now uses that path for crash recovery.

After the WAL append succeeds, the engine updates the active memtable.

That order is intentional:

WAL first, memory second

Crash recovery depends on that ordering. The WAL is the source that rebuilds memory after a restart. Writing to the memtable first would make the fast path feel nicer while making the durability story dishonest.

The MemTable Is A Skip List

The active memtable is implemented as a skip list.

It stores keys in sorted order, supports point lookups, and can produce an ordered iterator when it is time to flush to disk. The important API is deliberately small:

trait MemTable {
    fn put(&mut self, key: Key, value: Value);
    fn get(&self, key: &Key) -> Option<&Value>;
    fn delete(&mut self, key: Key);
    fn iter(&self) -> Box<dyn Iterator<Item = (&Key, &Value)> + '_>;
    fn approximate_size(&self) -> usize;
}

The Value type is either real bytes or a tombstone:

enum Value {
    Put(Vec<u8>),
    Tombstone,
}

That tombstone is what lets deletion fit the LSM model. A delete is not a random rewrite of every older table that might contain the key. It is a newer record saying:

for this key, absence wins.

Older values can remain in older SSTables until compaction eventually removes them.

Rotating Into Immutable MemTables

When the active memtable crosses a configured size threshold, the engine rotates it:

active memtable -> immutable memtable queue
new empty active memtable
new WAL segment

The WAL segment rotates at the same time as the memtable. That gives recovery a useful boundary: one WAL segment can rebuild one recovered memtable.

The immutable queue matters because flushing to disk should not make recently written keys unreadable.

Reads check:

1. the active memtable
2. immutable memtables, newest first
3. SSTables, newest first

That newest-first ordering is the simplest way to preserve overwrite and delete semantics. If alpha = one exists in an older SSTable and alpha = two exists in a newer memtable, the read must stop at the newer value. If the newest entry is a tombstone, the engine returns None.

This is the first place where the LSM stops feeling like “write sorted files” and starts feeling like a versioned data structure.

Managers, Manifest, And CURRENT

The engine started as a single owner of many vectors and paths. That worked for the first version, but it made recovery and future compaction feel too tangled.

The current shape splits ownership into managers:

• WALManager owns WAL segment creation, rotation, and replay
• MemTableManager owns the active memtable and immutable memtable queue
• SSTableManager owns table files and table metadata in memory
• ManifestManager owns manifest records for durable SSTable metadata

The engine coordinates those managers instead of directly pushing SSTables into a vector.

There is also a CURRENT file. It stores the ids that have to survive restarts:

next_sstable_id
next_wal_id
next_manifest_id
next_sequence_id

That file is small, but it is important. Without it, recovery can reconstruct data and still accidentally reuse an id that was already written before the crash.

Flushing To SSTables

An immutable memtable flush becomes an SSTable file.

The file layout currently looks like this:

data block
data block
...
block index
Bloom filter
footer

Each data block contains sorted entries. Each entry stores:

key length
value kind
value length
key bytes
value bytes

The block index maps the first key of each block to a file offset and length:

first key -> { offset, len }

The footer stores where the block index and Bloom filter live, plus a magic number so the reader can reject files that do not match the expected format.

That footer is a small thing, but it changed how I thought about the file. Before the footer, the SSTable was “some bytes I wrote.” After the footer, it became a self-describing object:

open file
read footer from the end
load index and filter
use index to find one block
read only that block

That is a much better boundary.

Bloom Filters Make Misses Cheap

Every SSTable gets a Bloom filter built while writing the file.

On read, the engine asks the filter first:

if filter says definitely not present:
    skip this SSTable
else:
    consult block index and read candidate block

A Bloom filter can lie in one direction. It can say “maybe present” when the key is absent. It should not say “absent” when the key was added. That makes it perfect for avoiding miss-heavy disk reads.

The current filter is intentionally simple: a bitset, several xxHash3 hash functions, and serialization into the SSTable file. It is not tuned yet. The important thing is that the read path now has the right shape.

Crash Recovery

The latest checkpoint has engine-level recovery.

Startup does three things:

1. read CURRENT so future ids continue from the recovered state
2. replay manifest records so the live SSTable set comes back into memory
3. replay WAL files in id order and rebuild memtables from those records

The WAL replay preserves segment boundaries. If the engine had rotated from one memtable to the next before the crash, recovery creates the same kind of active/immutable layout instead of merging every WAL record into one giant table.

There is also an external smoke test that starts a writer process, terminates it, reopens the database, and checks that acknowledged writes are still readable. It is not a replacement for a serious fault-injection suite, but it catches a more realistic failure than a normal unit test.

What Works Now

This is the in-progress state of the project today, not the final architecture.

The current engine supports:

• put, get, and delete
• file-backed WAL records with length and checksum
• WAL segment rotation with memtable rotation
• engine startup recovery from WAL files
• active and immutable memtables
• memtable rotation by approximate size
• flushing immutable memtables into SSTable files
• manifest-backed SSTable metadata
• a CURRENT file for durable id allocation
• block-indexed SSTable reads
• tombstones across memory and disk
• Bloom-filter checks before touching SSTable blocks
• newest-value-wins reads across memtables and SSTables

The tests cover the first set of invariants:

• read from the active memtable
• flush a full memtable and read from the SSTable
• let the newest value win across SSTables
• let deletes hide older values
• keep immutable memtables readable before flush
• write, reopen, get, miss, tombstone, and iterate SSTable files
• round-trip WAL records and reject checksum corruption
• compact manifest records into a fresh manifest file
• recover memtables and SSTables after reopening the engine
• run an external crash-recovery smoke test that kills and restarts the process

This is the point where the project is no longer just a collection of modules. The modules have started putting pressure on each other.

What Is Missing

The honest next list is longer than the completed list. That is expected at this stage: the current engine proves the basic shape, but the serious database work starts after that shape exists.

The engine still needs:

• atomic SSTable install
• compaction
• background compaction jobs
• async APIs and async I/O
• sorted merge iterators
• block cache
• benchmarks
• more fault-injection tests
• performance optimizations

Compaction is the big one.

Without compaction, an LSM tree is mostly a write path with accumulating debt. Every flush creates another sorted run. Reads get more expensive as more files pile up. Tombstones keep hiding values, but they do not reclaim anything. Overwritten values remain on disk.

That is the next real systems problem:

merge sorted runs
drop obsolete values
preserve newest tombstones when needed
write new SSTables
atomically retire old SSTables

It is also where the project should become more interesting.

For now, I am treating this post as the first checkpoint in a longer storage-engine series. The next posts should be about turning this baseline into something more durable and measurable: compaction, background jobs, block caching, and eventually benchmarking it against existing engines.

The Lesson

The main lesson from this first milestone is that an LSM tree is not just “memtable plus SSTable.”

It is the set of rules that makes those layers agree:

• WAL before memory
• memory before disk on reads
• newer tables before older tables
• tombstones before stale values
• indexes before block reads
• filters before unnecessary file reads

Each rule is small. Together they make the storage engine coherent.

That is why I like building these systems from scratch. The architecture diagram gives you the nouns. The implementation teaches you the ordering constraints.

Related Notes

rust / animation Building Broadsheet, a Rust Animation Engine for Systems Explainers How I built a deterministic Rust animation engine with stateless timelines, camera-aware rendering, newspaper styling, and ffmpeg export. rust / grep Building grep in Rust Taught Me to Think in State Machines Notes from building a grep clone with a custom regex engine: tokenization, Shunting Yard, Thompson-style NFAs, epsilon transitions, and line-by-line matching. redis / rust Building a Redis Clone in Rust, Then Making It 49x Faster With Profiling Benchmarking a Redis-compatible Rust server against Redis, profiling the slow paths, and using indexes to remove pathological scans.