Part 9 · 2 chapters · ~20 min

M9: Database Storage Engine

An LSM tree that survives crashes: a CRC-checked write-ahead log, a skip-list memtable, tombstones, immutable SSTables with sparse indexes and bloom filters, newest-first reads, k-way merged range scans, compaction, a MANIFEST, and a small query planner with EXPLAIN.

How an LSM tree works

random writes made sequential

Write: WAL plus fsync, then the memtable, then acknowledge.
Delete writes a tombstone.
Flush to an immutable SSTable, swapped in atomically.
Point reads go newest first, with bloom filters skipping files.
Range scans are a k-way merge where the newest version wins.
Compaction merges files, reclaims space and keeps reads fast.

	LSM tree (RocksDB, Cassandra, tiny-lsm)	B+tree (Postgres, InnoDB, SQLite)
writes	sequential appends; fast, high throughput	in-place page updates; random I/O
reads	may check several files (bloom filters help)	one root-to-leaf path
space	old versions until compaction	pages partly empty after splits
write amplification	data rewritten at each compaction level	whole page rewritten per small change
good for	write-heavy: events, logs, time series, ledgers' history	read-heavy, transactional, range-heavy OLTP

TINY-LSM: WRITE, FLUSH, READ, COMPACT

a write made durable in the log, sorted in memory, frozen to disk, found again through bloom filters, and merged away

swipe the figure sideways, or tap expand for full screen

1/6

write

Write: put("tx:0042", "₦4,200") appends a record to the WAL ([CRC32][length][op][key][value]) and fsyncs it, then inserts into the memtable, a skip list kept in key order. Only then is the write acknowledged. A crash now loses nothing: the WAL is replayed on startup.

Building it: tiny-lsm

Repo: repos/storage. WAL, skip list, SSTable, the LSM itself, a query planner and a REPL.

code

// src/wal.ts: a CRC per record; replay stops at the first torn or corrupt record
while (i + 8 <= b.length) {
  const crc = b.readUInt32BE(i), len = b.readUInt32BE(i + 4);
  if (i + 8 + len > b.length) break;                 // torn tail: the crash happened mid-append
  const body = b.subarray(i + 8, i + 8 + len);
  if (crc32(body) !== crc) break;                    // corrupt: stop at the last good record
  // … decode op, key, value …
  i += 8 + len;
}

code

// src/lsm.ts: the k-way merge behind range scans
*scan(from = '', to = ''): Generator<[string, string]> {
  const sources = [this.mem.entries(from), ...[...this.tables].reverse().map(t => t.scan(from))];   // newest first
  const heads = sources.map(s => s.next());
  for (;;) {
    let min: string | null = null;
    for (const h of heads) if (!h.done && (min === null || h.value[0] < min)) min = h.value[0];
    if (min === null || min > to) return;
    let winner: string | null | undefined;
    heads.forEach((h, i) => { if (!h.done && h.value[0] === min) { if (winner === undefined) winner = h.value[1]; heads[i] = sources[i].next(); } });
    if (winner !== null && winner !== undefined) yield [min, winner];   // a tombstone yields nothing
  }
}

code

$ npm run repl
lsm> PUT 'tx:2026-10-05' '₦500'
OK
lsm> EXPLAIN SELECT * WHERE key LIKE 'tx:2026-10-%'
RANGE SCAN ['tx:2026-10-', 'tx:2026-10-'] LIMIT 1000 (k-way merge of memtable and SSTables)
lsm> FLUSH
tables: 1

Run it. In repos/storage: npm test, then npm run repl. Put some keys, FLUSH, put more, delete one, FLUSH, then COMPACT and query. Kill the REPL with Ctrl-C between a PUT and a FLUSH, restart it, and the WAL replay brings the key back.

exercises

1. Leveled compaction (L0 → L1 → L2 with size ratios and non-overlapping ranges per level). 2. A block cache with LRU for hot SSTable blocks. 3. Snapshots: sequence numbers on every write, so a reader sees a consistent view during writes. 4. A B+tree engine with the same API, benchmarked against this one on write-heavy and read-heavy workloads.