Storage engines: B-trees, LSM trees & WAL

An electricity utility has 3 million smart meters, each reporting every 30 seconds: 3,000,000 ÷ 30 = 100,000 writes a second. Every acknowledged reading must survive a power cut. The slow way would be to find each reading's place in the data files and force that page to disk before answering. Pages are scattered across the disk, so that is one random write, and one wait, per reading.

Instead, almost every database writes a write-ahead log (WAL) first: an append-only file recording each change. The rule is strict: a change may reach the data files only after the log record describing it is safely on disk. A commit waits only for that log flush:

Under load, the log flush is shared: one flush can commit many small transactions that arrived together, called group commit. The same log also feeds replicas and point-in-time backups (Database replication).

The billing database next to the meters is a classic relational database, so its tables and indexes are B-trees: trees of fixed-size pages, 8 KB in PostgreSQL and 16 KB in MySQL's InnoDB (Database indexing covers how lookups walk them). To change a value, the engine finds the leaf page holding the key, changes it in memory, and later writes the whole page back to the same place on disk.

When a leaf page has no room for a new key, it splits:

Two costs follow from rewriting pages:

• Write amplification. Changing one 100-byte row eventually rewrites its whole 8 KB page: up to 8,192 ÷ 100 ≈ 80 times the bytes, when nothing else on the page changed.
• Torn pages. A crash halfway through writing a page can leave half old and half new data. PostgreSQL therefore logs a full copy of each page the first time it changes after a checkpoint, which adds to the log's size.

In return, reads are predictable. Every key lives in exactly one place, a lookup walks one path from root to leaf, and a range scan reads neighboring leaves in order. Pages are rarely full: InnoDB leaves 1/16 free, and random inserts leave pages between half and fifteen-sixteenths full.

100,000 meter readings a second, almost never updated and read mostly by meter and time range, suit a different design: the log-structured merge tree (LSM tree), used by RocksDB, LevelDB and Cassandra. It never modifies a file on disk:

The pieces:

• Writes append to the WAL and insert into the memtable, a sorted structure in memory. Nothing on disk is searched or rewritten.
• Flushes write a full memtable out as an immutable, sorted file, called an SSTable or SST file, in one sequential pass.
• Deletes and updates are new records too. A delete writes a tombstone saying "this key is gone", and the newest record for a key wins.

Reads pay for this. A lookup checks the memtable, then the files from newest to oldest until it finds the key. Each file has a Bloom filter that says "definitely not here" for most files, so the engine skips them without touching the disk (Bloom filters). Range scans must merge matching keys from every level at once.

Left alone, files pile up: reads check more and more of them, and overwritten readings and tombstones waste disk. Compaction runs in the background, merging sorted files into new sorted files and dropping every value that has been overwritten or deleted. Two main strategies trade differently:

The levels grow geometrically, which keeps them few. As an illustration, with a first level of 1 GB and the default size ratio of 10, levels hold 1 GB, 10 GB, 100 GB, 1 TB and 10 TB. A year of readings is 100,000 × 100 bytes × 86,400 × 365 ≈ 315 TB; spread over 100 nodes that is about 3.2 TB each, which fits within five levels.

Compaction also shares the disk with live traffic. When writes outrun it, level 0 fills with overlapping files and pending work piles up, so the engine protects itself with a write stall: it slows each write down, or stops writes entirely until compaction catches up. That makes LSM write latency less predictable than a B-tree's, especially at the high percentiles. Leave disk bandwidth and space headroom for compaction, and watch its backlog as a health metric (Observability: metrics, logs & traces).

Three numbers describe a storage engine's costs:

• Write amplification: bytes written to disk per byte the application wrote.
• Read amplification: disk reads per lookup.
• Space amplification: disk used per byte of live data.

No design minimizes all three. The usual comparison:

The usual summary, that LSM trees are faster for writes and B-trees for reads, is a tendency, not a law. Caching, compression, the size of values and how well compaction is tuned can each outweigh it, so benchmark your own workload before switching engines.

The utility ends up with both:

For durability, whichever engine you run:

• Keep commits synchronous unless losing the last fraction of a second of writes is explicitly acceptable; never turn fsync off for data you can't rebuild.
• Use disks that honor flushes. A disk cache that acknowledges a flush it hasn't made breaks the WAL's promise.
• Replication is not a substitute for the log: a power cut can hit every replica in the same building.

For each kind of engine:

• For LSM stores, budget for compaction: spare disk bandwidth, spare space for merges, and alerts on pending compaction and stalls.
• For B-trees, watch write amplification from random-key inserts and wide rows, and keep hot indexes in memory.
• Delete in bulk with care in LSM stores: millions of tombstones slow reads until compaction removes them.