jonnify·persistence /echo-persistence/rust/fjall-and-the-lsm-tree

Module 8 · Dive 8.1

Fjall & the LSM-tree.

The Rust engine stores its pages in Fjall, a log-structured merge-tree. Writes land in an in-memory memtable; when it fills, it flushes whole to an immutable SSTable on disk; and compaction reclaims space by merging SSTables and dropping superseded versions. It is a different shape from CubDB’s copy-on-write B-tree (Module 4), but it keeps the same promise: files are written once and never mutated. Write, flush, and compact.

§1

Memtable, flush, merge

interactive
The write path of an LSM-tree. Writes fill the memtable in RAM; a full memtable flushes to an immutable L0 SSTable; compaction merges L0 SSTables into one L1, dropping superseded keys. Nothing on disk is ever overwritten.
memtable · RAM, sorted 0 / 4 flush L0 · flushed SSTables (immutable) compact (merge) L1 · compacted SSTable reads check, in order: memtable → L0 newest-first → L1 on-disk SSTables never rewritten
readout · Write keys to fill the memtable (some keys repeat at higher versions). At 4, flush it to an immutable L0 SSTable. Stack a few, then compact: they merge into L1, keeping the latest version of each key and dropping the rest.
§2

Two shapes, one immutability

graft.engine-split.design.md

CubDB and Fjall solve the same problem from opposite directions. The B-tree writes a new copy of the path on every change and keeps the tree balanced as it goes, so reads are a single descent but each write touches several nodes. The LSM-tree batches writes in memory and flushes them sequentially, so writes are cheap and append-only, but a read may have to check the memtable and several SSTables, and space is reclaimed later by compaction rather than immediately. What matters for the Volume contract is that both are immutable on disk: a flushed SSTable, like a written CubDB block, is never overwritten, so old versions stay readable and a crash can only ever lose the un-flushed memtable tail — which the commit log replays (Module 6). The engine picks the LSM shape for write-heavy page churn; the guarantees the rest of the platform depends on are unchanged. Next, how those SSTables and segments reach a remote that could be anything.

§3

References & sources