Why the write path hates B-trees

A B-tree engine writes a record in place: the leaf page, an index page, and a WAL record, all touched on a single logical write. On random workloads that is three or more page writes per operation, and every write is a random I/O with its own fsync. An LSM-tree inverts the problem. Writes are sequential appends into a memory table that occasionally spills to disk in sorted runs; reads pay a cost instead. If your workload is write-heavy and you can tolerate a read penalty, the LSM wins by an order of magnitude.

The four pieces

• Memtable. A sorted in-memory structure (skip list or red-black tree). All inserts land here and stay in memory.
• WAL. Every insert is appended to a log first, so the memtable can be rebuilt after a crash.
• SSTables. When the memtable is full it becomes immutable and is flushed to disk as a sorted run of blocks.
• Compaction. Background merges combine runs level by level so old data is eventually rewritten, deleted keys are reclaimed, and the number of levels stays bounded.

The write path, concretely

The WAL is where durability happens, and the fsync is where performance is won or lost. The key decision is group commit: funnel thousands of records through one fsync instead of one per operation.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
package kv

import (
	"encoding/binary"
	"os"
)

// AppendRecord writes a length-prefixed (key, value) pair to the WAL.
// Callers batch many records and call Sync once per batch.
func AppendRecord(f *os.File, key, value []byte) error {
	rec := make([]byte, 4+4+len(key)+len(value))
	binary.BigEndian.PutUint32(rec[0:], uint32(len(key)))
	copy(rec[4:], key)
	binary.BigEndian.PutUint32(rec[4+len(key):], uint32(len(value)))
	copy(rec[8+len(key):], value)
	_, err := f.Write(rec)
	return err
}

// CommitBatch persists a batch of appended records. One fsync for the whole
// batch: a single writer goroutine owns this file and syncs on a timer or
// after N records, whichever comes first.
func CommitBatch(f *os.File) error {
	return f.Sync()
}

The writer goroutine holds the pending records, flushes the user-space buffer, and calls Sync once. A single-op fsync on NVMe costs roughly 30-80µs, which caps you at 12-20k durable writes per second. Group-committing 512 records per sync amortizes that to a fraction of a microsecond per record, pushing toward 500k-1M writes per second before disk bandwidth becomes the limit. This is the single highest-leverage function in the whole engine.

Flush and compaction

When the memtable crosses its size threshold (we use 64MB), it is swapped to immutable, a new memtable takes over, and the old one is flushed to an SSTable in sorted key order while the WAL is rotated and truncated. Flushing is a sequential write, which is why the design stays fast.

Compaction is where the LSM earns its write amplification. Leveled compaction (as in RocksDB and LevelDB) typically amplifies writes 10-40x because each level is rewritten as data flows down. Size-tiered compaction is cheaper on write amplification but blows up read and space amplification. We run leveled and budget compaction like memory: a fixed number of worker goroutines at low priority, because the classic production failure is a compaction storm – background merges competing with foreground traffic and turning p99 latency into a sawtooth.

1
2
3
4
5
6
7
// A compaction worker, rate-limited to a share of a core.
func compactionWorker(tasks <-chan Compaction) {
	for t := range tasks {
		mergeAndWrite(t.inputs, t.output)
		// checkpoint + delete obsolete WALs after each level merge
	}
}

The read path

A point read checks the memtable, then walks each level from newest to oldest, searching SSTables. Without help, that is up to L+1 lookups. Each SSTable carries a Bloom filter, so a key that is not present is rejected after checking a bitmap instead of reading disk. At 10 bits per key the false-positive rate is around 1%, meaning the average point read does about one disk read regardless of how many levels exist. For range-heavy workloads, drop the Bloom filter or use a prefix variant – filters only pay for point lookups.

What we measured

On NVMe with group commit, a write benchmark holds ~600k inserts per second at a 1MB batch window, versus ~15k/s when syncing every record. Point reads with Bloom filters at 10 bits/key stay under 5µs in page cache and cost roughly one disk seek on a miss. Without the filter, the same miss cost 7 reads once the data grew past a few levels. The trade-offs, in one line each:

• WAL group commit buys write throughput; it is the first thing to tune.
• Compaction workers must be throttled and off the hot path or they become the latency problem they were meant to prevent.
• Bloom filters convert read amplification into memory; 10 bits/key is a sane default, and dropping to 5 is where range workloads should start.
• f.Sync() is fdatasync, not fsync – skip metadata when you can, and never call it per record.
• Keep the memtable sorted structure pointer-light; a naive skip list generates enough garbage to make the GC your second-most-important cost.