customLSM

An LSM-tree key/value store in Rust — MemTable, write-ahead log, immutable SSTables, size-tiered and leveled compaction, block index, Bloom filters — built to be measured, benchmarked head-to-head against SQLite and RocksDB, with the amplification metrics reported rather than assumed.

Headline finding: three phases of careful A/B benchmarking hid two large bugs — a 7x one on the read path and a 171x one on the write path — because a controlled comparison against yourself cannot see a constant factor you always pay. Every configuration paid them identically, so they cancelled out of every ratio. Comparing against RocksDB exposed both in an afternoon, and one of them retracted a Phase 1 finding that had already been "verified" by a probe that shared the same wrong assumption.

The rigour was what hid them. Every configuration was identical except the variable under test, so the shared overhead cancelled perfectly, every time.

A full validity audit then re-derived every claim and found the pattern repeating: both invalidating bugs it caught (seven more F_FULLFSYNC sites; a space-amp denominator) were causes that had already been found and fixed once, in one place, and never swept. Three published conclusions were corrected there, including one whose write-side "strategy trade" was really a barrier-per-file artifact.

Roadmap

• Phase 1 — Working KV store: MemTable, WAL with a 4-point durability dial, flush to immutable SSTables, put/get/delete surviving restart
• Phase 1b — Crash recovery: SIGKILL a real subprocess mid-write and verify what survived, per sync mode
• Phase 2 — Actually an LSM: manifest, k-way merge, size-tiered compaction, tombstone dropping
• Phase 3 — Optimizations, each measured: block-based SSTable with index, hand-written Bloom filters, hand-written skip list, key-range filtering
• Phase 4 — Measurement study: vs SQLite and RocksDB, size-tiered vs leveled, at matched durability
• Phase 5 — Concurrency (optional): reads and writes that don't block on flushes

Results — vs SQLite and RocksDB

Apple M3 Pro, 18 GB RAM, macOS 26.2, APFS/NVMe, rustc 1.95.0. 200,000 keys × (16 B key + 100 B value), median of 3 runs, single op per call (no batching), incompressible values, matched durability. ops/s:

workload	customLSM (size-tiered)	customLSM (leveled)	RocksDB	SQLite
sequential fill	879,630	880,453	444,054	156,575
random fill	906,744	899,967	305,981	132,219
random read, hit	771,231	815,249	731,770	409,476
random read, miss	4,228,404	4,561,593	711,412	404,539
mixed 95r/5w	720,574	759,902	569,233	380,844

(Audit-corrected tables — structural F_FULLFSYNC removed, misses interspersed rather than outside the keyspace, RocksDB compactions drained before sampling. Read-miss caveat: stock RocksDB ships without Bloom filters, so that column compares our tuned miss path against its untuned default. The two customLSM strategies are now statistically indistinguishable on fills — the previously published 1.74x write gap was a barrier-per-file artifact, not the strategies' trade.)

And it loses on the metrics that describe the design:

engine	write amp	space amp (seq / rand)
customLSM (size-tiered)	3.64x	1.09x / 1.18x
customLSM (leveled)	3.96x	1.09x / 1.09x
RocksDB	2.12x	1.00x / 1.00x
SQLite	not instrumented	1.22x / 1.21x

RocksDB writes 1.7x fewer bytes per byte of user data. That is the more meaningful of the two tables: at this scale throughput is a CPU measurement, while write amplification is a property of the compaction design and does not improve when the dataset grows.

The caveat that matters most: the working set is 22 MiB on a machine with 18 GB of RAM, so every engine runs entirely out of the page cache. This is a benchmark of CPU and syscall efficiency wearing a storage benchmark's clothes. Nothing here measures the regime LSM-trees were designed for — data that doesn't fit in memory — which is exactly where RocksDB's block cache, prefetching and compression start to matter.

Internal progress, Phase 1 → Phase 4

workload	Phase 1	Phase 4	change
sequential fill	243,941 ops/s	544,572 ops/s	2.2x
random read, hit	1,376 ops/s	782,693 ops/s	569x
random read, miss	72 ops/s	4,105,104 ops/s	57,015x
read amplification (miss)	23.7 MiB/read	108 B/read	−99.9996%
write amplification	2.09x	3.64x	+74% (the price of compaction)

Optimization scorecard — full detail in benchmarks/:

change	measured	verdict
Block index (vs full scan)	reads 147–256x	✅ the load-bearing one
Bloom filters, 10 bits/key	misses 79x beyond the index	✅ biggest single win on the miss path
Hold file handle open + pread	reads 6.9x	✅ found only by external comparison
Raw fsync(2) instead of sync_all()	fsync'd writes 113x	✅ found only by external comparison
Size-tiered compaction	space 1.67x → 1.26x, writes −18%	✅ the trade, priced
Audit: structural-sync sweep	fills ~2x, dial's none tier 4.6x	✅ the same bug, five more homes
Key-range filter	−13% size-tiered, +122% leveled	⚪ strategy-dependent
Block size 4 KiB vs 1 KiB	8% claim retracted; 1 KiB +10% at 7 runs, 2.7x index memory	⚪ default kept on memory grounds
Leveled vs size-tiered	write gap was an artifact (now 1.00x); write amp +9% real	⚪ audit-corrected; wrong scale to judge
Skip list vs BTreeMap	0.85x (skip list loses)	❌ honest loss, single-threaded
Compaction's effect on reads (pre-index)	read amp −11x, throughput 1.00x	❌ the metric was wrong
Phase 1's fsync vs F_FULLFSYNC finding	same call measured twice	❌ retracted

Six findings the numbers taught

1. A controlled A/B against yourself cannot find a constant factor you always pay. BlockTableReader::get_scanned called File::open on every probe — three syscalls against RocksDB's one. It cost 7x on the read path and survived three phases of benchmarking, including the A/Bs that "proved" the block index and the Bloom filter worked. Those conclusions were correct; every absolute read number in Phase 3 was ~7x too slow. phase4.md

2. Verifying a suspicious result is worthless if the verification shares the suspect assumption. Phase 1 reported that fsync and F_FULLFSYNC cost the same (~4 ms), found it surprising, and wrote a probe to check. The probe compared File::sync_all() against explicit fcntl(F_FULLFSYNC) and found them equal — because on macOS Rust's sync_all() is F_FULLFSYNC. It was the same call measured twice. Raw fsync(2) is 0.019 ms, 214x cheaper. The finding is retracted in place in phase1.md, and the corrected version is better than the wrong one: any Rust program calling sync_all() in a write path on macOS is silently buying a power-loss guarantee it may not know it is paying for.

3. A proxy metric is a hypothesis about the cost model, and this one was false. Phase 2's compaction cut tables-probed per miss from 33.00 to 3.00 and throughput went 80 → 80 ops/s. Bytes-probed was identical to three significant figures, which is exactly why. "Tables probed" assumes constant cost per table; that only holds once tables have an index. phase2.md

4. Minimizing bytes read does not minimize latency. 1 KiB blocks read 3.8x fewer bytes than 4 KiB and ran 8% slower: below a page there is nothing left to save, while the index grows to 1.8 MiB and costs cache misses on every search. The RUM conjecture in miniature — read cost and memory cost trade, and the optimum is interior.

5. A conclusion is only as general as the configuration it was measured on. Phase 3 measured the key-range filter against size-tiered, found it −42% on the honest miss workload, and defaulted it off. Against leveled it is +122%, because leveled's tables never overlap within a level so a range check picks exactly one table where the Bloom filter must be consulted for all of them. The Phase 3 conclusion wasn't wrong, it was incomplete — and stated as though it were general. The option is now resolved from the strategy.

6. The skip list lost. LevelDB's MemTable structure is 12–17% behind Rust's BTreeMap single-threaded, even implemented with a u32-indexed arena and flat link array to avoid a strawman. But this benchmark does not test what LevelDB picked a skip list for — lock-free concurrent reads — so the accurate claim is untested, not disproved.

Durability is demonstrated, not claimed

tests/crash_recovery.rs spawns the writer as a real subprocess and SIGKILLs it. Every recovery checks two invariants: no wrong values, and no holes (recovered writes must form a prefix of the acknowledged sequence — losing write 40 but keeping 41 would mean the log replays out of order).

sync mode	throughput	p50	guarantee	lost to SIGKILL
none	167,282 ops/s	541 ns	buffered in userspace	100 of 100
flush	160,204 ops/s	1.50 µs	write(2) per append	0
fsync	27,542 ops/s	18.50 µs	fsync(2) per append	0
fullfsync	234 ops/s	4.00 ms	F_FULLFSYNC	0

The buffered row asserts loss. "We have a write-ahead log" gets read as "writes are durable"; the log only helps once it reaches something that survives. And F_FULLFSYNC costs 118x more than fsync(2) — the single largest performance decision in the store is a one-line choice about what you are willing to lose.

Run

cargo test                      # 116 unit + 7 crash-recovery tests
cargo build --release

./target/release/lsmbench --workload all --ops 200000 --runs 3

Every optimization is a runtime toggle, so each measurement is an A/B in one binary against one workload:

./target/release/lsmbench --workload read-miss --format scan --range-filter off
./target/release/lsmbench --workload read-miss --format blocked --bloom-bits 10
./target/release/lsmbench --workload fill-rand --memtable skiplist
./target/release/lsmbench --workload fill-rand --strategy leveled
./target/release/lsmbench --workload durability --ops 20000

The head-to-head needs the compare feature (builds SQLite and RocksDB from source, ~90 s):

cargo build --release --features compare
./target/release/lsmcompare --ops 200000 --read-ops 50000 --runs 3 --durability both

Flags that change conclusions rather than just numbers: --read-fill seq|rand (disjoint vs overlapping table key ranges), --miss-mode outside|interspersed (whether absent keys can be rejected by a key range at all), and --value-pattern random|compressible (whether the space comparison measures a data structure or a codec).

Layout

src/
  db.rs          write path, read path, flush, compaction driver, all counters
  wal.rs         CRC-framed log, 4-point durability dial, torn-tail recovery
  memtable.rs    BTreeMap and skip-list MemTables behind one enum
  skiplist.rs    hand-written, arena-backed
  sstable.rs     format v1: sorted scan table (the honest baseline)
  blocktable.rs  format v2: block index + Bloom filter
  table.rs       format dispatch, detected from the file's magic
  bloom.rs       hand-written filter + hash
  manifest.rs    the atomic commit point for a compaction
  merge.rs       k-way merge, newest-wins
  compaction.rs  size-tiered and leveled policies + the tombstone rule
  bin/lsmbench.rs    internal benchmarks
  bin/lsmcompare.rs  head-to-head vs SQLite and RocksDB
  bin/crashtest.rs   the process that exists to be SIGKILLed
benchmarks/      phase1-4.md, audit.md + the fsync probes
tests/           crash_recovery.rs

The core library is dependency-free: the CRC, the hash, the Bloom filter, the PRNG and the skip list are all part of the study, so importing them would skip the lesson. SQLite and RocksDB are optional, behind --features compare.

Design notes

A delete is a write. An LSM cannot delete in place — the key may live in any number of older immutable tables, and rewriting those is the work the design exists to defer. So a delete appends a tombstone, and the space is reclaimed only by compaction.

Dropping a tombstone too early resurrects deleted data. No error, no corruption — a row simply returns from the dead long after its delete was acknowledged. A tombstone is dropped only when no older table's key range contains the key, conservatively.

The two compaction strategies need different correctness arguments. Recency is tracked per table, not per entry. Size-tiered relies on contiguity — inputs must be a contiguous run in recency order, or a merged table would be both newer and older than one it skipped. Leveled relies on the level invariant instead: data only moves downward, and tables never overlap within a level, so its inputs are deliberately non-contiguous and that is safe.

A compaction commits when the manifest is renamed. Write the merged table and rename it (the manifest still lists the inputs, so nothing has changed); rewrite the manifest atomically (the commit point); delete the inputs (pure GC). Orphans from an interrupted compaction are swept on open.

Scope

• Done: working store, demonstrated crash recovery, size-tiered and leveled compaction with correct tombstone handling, block-based tables with index and Bloom filters, and an A/B for every optimization including the ones that lost.
• Rejected on evidence: the skip-list MemTable as a default (loses single-threaded); the key-range filter as a global default (strategy- dependent, now resolved from the strategy).
• Known gaps, measured or named: write amplification 1.7x worse than RocksDB's; no block cache; no compression (RocksDB stores compressible data in 7.4x less space); no per-block checksums; single-threaded throughout.
• Not yet: concurrent reads and writes without blocking on flushes (Phase 5) — which is both where the mixed-workload loss to SQLite comes from and the only setting where the skip list's actual advantage could appear. A dataset larger than RAM would also be needed to judge leveled vs size-tiered properly, since 22 MiB only builds two levels.

Reference material

The original LSM-tree paper (O'Neil et al., 1996) for the theory; RocksDB's design documents for how it's done in production; Database Internals (Petrov) for the storage-engine half; and the RUM Conjecture paper — read, update and memory optimality are fundamentally in tension, which is the frame the block-size and compaction-strategy results fall straight out of.