Day 92: LSM trees vs B-trees; replication internals
LSM trees: the other major storage engine design
B-trees (used by Postgres, MySQL's InnoDB) update in place, which means random disk writes for scattered updates. LSM trees (Log-Structured Merge trees) — used by Cassandra, RocksDB, and many time-series/write-heavy databases — take a different approach: writes always go to an in-memory structure (memtable) plus an append-only log, and are only later merged into sorted files on disk (SSTables) in the background.
Why this trade-off exists
LSM trees turn random writes into sequential ones, making them exceptionally fast for write-heavy workloads. The cost shows up on reads: a value might exist across the memtable and several SSTables, so a read may need to check multiple places — this is why LSM-based systems 'write fast and read weird' compared to B-trees, which read predictably but pay more for scattered writes.
Bloom filters
To avoid checking every SSTable on every read, LSM systems use a bloom filter per SSTable — a compact, probabilistic structure that can say "definitely not in this file" (skip it) or "maybe in this file" (check it) — never a false negative, occasionally a false positive, but cheap enough to check before an expensive disk read.
Replication internals: streaming vs logical
Streaming replication ships the raw WAL byte-for-byte — fast and simple, but the replica must be the same major Postgres version and typically replicates the whole database. Logical replication decodes WAL into a stream of row-level changes (inserts/updates/deletes), enabling replication between different Postgres versions, selective table replication, and even replicating into a different kind of system entirely.
A replication slot ensures the primary retains WAL until a specific replica has confirmed receiving it — preventing data loss if a replica temporarily disconnects, at the cost of the primary's disk filling up if a slot's replica never reconnects. Replication lag is how far behind a replica is; reading from a lagging replica is exactly the eventual-consistency trade-off from Phase 7, Day 45, made concrete.
The Four Questions: LSM trees (Cassandra/RocksDB-style storage)
Worked example for Docker: dependency hell → consistent runtime environments → VMs too heavy → shared kernel, weaker isolation. Apply it to LSM trees: what problem (slow random writes on B-trees at very high write volume) did they solve, why couldn't B-trees solve it directly, and what trade-off (more complex, multi-location reads) do they introduce?
Key terms
- LSM tree
- A write-optimized storage structure using an in-memory memtable and background-merged sorted files (SSTables).
- Bloom filter
- A probabilistic structure that cheaply rules out "definitely not here" before an expensive lookup.
- Replication slot
- Ensures the primary retains WAL until a specific replica confirms receiving it.
Phase 15 complete — you should now be able to
Why might Cassandra (LSM-based) outperform Postgres (B-tree-based) on a very high-volume write workload?
