System Design Masterclass · Module 27 · Extension of Week 1

Storage Engine Internals

Under every database decision from Modules 03–05 sits a storage engine making physical trade-offs: how writes reach disk (B-tree vs LSM), what makes them durable (WAL), and how readers and writers coexist without locking each other out (MVCC). This is the layer that explains why Cassandra loves writes, why Postgres tables bloat, and why your replication and CDC exist at all.

~3h study~1.5h exercise2 interactive simsFast track ~75 min

Fast track — tuned RocksDB or vacuumed Postgres before?

Fast track mode

Compresses to ~75 min. Motivation collapses; the LSM/B-tree trade (with the amplification vocabulary), WAL-as-the-source-of-everything, and MVCC's visibility rules stay mandatory.

§01 takeaway · 5 min
§02 both engines + sim, in full · 25 min · MANDATORY
§03 WAL, in full · 15 min · MANDATORY
§04 MVCC + sim, in full · 20 min · MANDATORY

STEP 01

Why the engine layer explains the database market

SKIM

Fast-track takeawayEvery engine juggles three amplifications — write amplification (bytes physically written ÷ bytes logically changed), read amplification (places checked per lookup), space amplification (disk used ÷ live data) — and no design wins all three. B-trees (Postgres, MySQL/InnoDB) favor reads; LSM-trees (Cassandra, RocksDB, and inside many "NewSQL" stores) favor writes; everything else is tuning between them. The practical payoff: when a vendor says "optimized for write-heavy workloads," you now know they mean LSM, and you can predict its costs (compaction CPU, read tails, tombstone problems) before the POC does.

The physical fact underneath: disks (even SSDs) love sequential IO and batch writes, and hate random small writes. Both engine families are strategies for converting the random writes your application generates into something the disk forgives — B-trees by updating in place with careful page management, LSMs by refusing to update in place at all.

STEP 02

B-tree vs LSM

MANDATORY

B-tree: data lives in fixed-size pages forming a balanced tree; writes find the page and update it in place (via the WAL first — §03). Reads are one tree descent: predictable, fast, index-friendly. Costs: a one-row change rewrites a whole page (write amplification), random page IO under write load, and page splits/latching under concurrency.

LSM-tree: writes append to a WAL and land in an in-memory memtable; when full, it flushes as an immutable sorted file (SSTable). Reads check memtable, then SSTables newest→oldest (bloom filters skip most). Background compaction merges SSTables, discarding overwritten versions and tombstones. Watch the write path:

LSM write path

Memory

memtable (empty)

Disk (SSTables, newest first)

— none —

Writes never touch existing files — pure sequential appends. That's the whole trick, and every cost flows from it.

	B-tree	LSM
Write path	random page updates (in place)	sequential appends — high sustained write throughput
Read path	one tree descent — predictable	memtable + N SSTables (bloom-filtered) — read amplification, tail risk during compaction backlog
Background cost	modest (checkpointing)	compaction: CPU/IO you must provision; falling behind = read cliff + space blowup
Deletes	immediate	tombstones until compacted — the Cassandra "queue anti-pattern" (scan wades through deletions)
Range scans	excellent	merge across files — fine when compacted, painful when not
Home turf	OLTP with rich queries, read-mostly: your entitlement/billing Postgres	write-heavy, key-value shaped: watch-event ingestion, QoE telemetry, time-series

Staff expectationUsing the amplification vocabulary in reviews: "this workload is 50k writes/s of 200-byte events, read rarely and by key — LSM territory; budget compaction headroom and cap tombstone-generating patterns" vs "this is 95% reads with secondary indexes and range queries — B-tree, and the write volume doesn't justify LSM's read tax." Also knowing the hybrid reality: many systems put an LSM under a SQL face, and Kafka itself (M15) is the degenerate LSM — append-only segments, no compaction except by policy — which is why its throughput looks the way it does.

STEP 03

The WAL: one log, four jobs

MANDATORY

Durability: before any commit is acknowledged, its changes are appended + fsynced to the write-ahead log. Crash recovery = replay the WAL from the last checkpoint. The data files can be arbitrarily stale; the log is the truth. Group commit batches many transactions' fsyncs into one — the knob behind commit-latency vs throughput tuning, and the reason commit latency has a floor (one device flush).
The durability dial is explicit: fsync-per-commit (safe, ~ms floor) vs delayed flush (fast, loses the last window on power loss) — Postgres synchronous_commit, Kafka's acks/flush settings, Redis AOF everysec are all the same dial. Know where each of your stores has it set; "we lost acked writes" incidents live here (M15's acks=1 lesson was this dial, distributed).
Replication feeds from it (M04): the replica stream is the WAL shipped over the network — which is why replication lag is measured in WAL positions/LSNs, and why a replica is just recovery-replay running continuously.
CDC taps it (M18): Debezium's logical decoding reads the same log — the WAL is simultaneously your durability mechanism, your replication transport, and your event source. One structure, three of this course's modules — and the disk-full-from-abandoned-slot warning (M18) is the WAL being pinned by a consumer that stopped reading.

STEP 04

MVCC: readers and writers, unblocked

MANDATORY

The naive engine takes read locks vs write locks — readers block writers and vice versa, and throughput dies at concurrency. MVCC's move: writes create new versions instead of overwriting; every transaction reads the snapshot of versions committed before it began. Readers never block writers, writers never block readers (writers still conflict with writers on the same row).

Row: subscription #42 · plan column · two concurrent transactions

version 1

plan = BASIC

committed @ txid 90

TX-A (long report query, txid 100) starts reading. TX-B (upgrade, txid 101) will update the same row mid-read.

Visibility is arithmetic: each version carries creator/deleter transaction IDs; a transaction sees versions created by committed txids ≤ its snapshot and not deleted by them. Isolation levels (read committed vs repeatable read/snapshot) differ only in when the snapshot is taken — per statement vs per transaction.
The bill — dead versions: old versions accumulate until no snapshot needs them; cleanup is Postgres VACUUM / InnoDB purge / LSM compaction (same job, §02). Operational corollaries: long-running transactions pin old versions — the analytics query that holds a snapshot for an hour makes every hot table bloat and every cleanup stall (the classic "why is the DB slow" whose culprit is a forgotten idle-in-transaction connection: set idle_in_transaction_session_timeout); update-heavy tables need autovacuum tuned to the write rate, not defaults.
MVCC meets the course: snapshot reads are why SELECT ... FOR UPDATE exists (you must opt into locking when read-then-write must be atomic — M16's check-then-act race at the row level); optimistic version-guard updates (M16/M19's fencing family) are application-level MVCC; and write-write conflicts under snapshot isolation are why serializable exists and costs what it costs (M03's coordination tax, in-engine).

STEP 05

Exercise

MANDATORY

Fast trackStep 2 (~30 min): watching your own long transaction bloat a table converts MVCC from theory to reflex.

Build a toy LSM. Java: TreeMap memtable + WAL file; flush to sorted SSTable files at a size threshold; reads check memtable then files newest-first; a compaction pass merging files and dropping shadowed versions. ~200 lines, and §02 is permanent. Measure write throughput vs a naive update-in-place file.

Bloat Postgres on purpose. Table with 1M rows; run an UPDATE loop on one hot subset while a second session sits in an open REPEATABLE READ transaction. Watch pg_stat_user_tables dead tuples climb and autovacuum stall; close the pinning transaction and watch cleanup proceed. Check your production for idle in transaction right now.

Race the read-then-act. Two threads doing SELECT-check-UPDATE on a counter under read committed — count lost updates; fix three ways: FOR UPDATE, atomic UPDATE ... SET x=x+1, and a version-guard CAS. Note which one you'd ship (M16 says the atomic update).

Paper. For your platform's stores (Postgres, Redis, Cassandra/anything LSM, Kafka): one line each — engine family, where its durability dial is set, what its cleanup process is, and the workload it's mismatched with today, if any.

Self-check

Cassandra ingestion is fine but p99 reads degrade every afternoon. Engine-level hypothesis?

Compaction falling behind the write rate: SSTable count grows, each read consults more files (read amplification), bloom filters help less, and compaction IO competes with reads. Check pending compactions; fixes: compaction throughput headroom, throttling ingest, or a compaction strategy matched to the workload (time-windowed for time-series). The afternoon pattern = peak writes outrunning background merge.

Why is "replication = WAL shipping" a useful mental model rather than trivia?

It collapses three topics into one: replica lag is WAL-apply lag (measurable in LSN bytes, not vibes); a replica promotion loses exactly the unshipped WAL tail (M11's RPO is a WAL position); and CDC/Debezium is just another WAL consumer — so slot monitoring, ordering guarantees, and the disk-pinning failure mode are shared machinery you reason about once.

An hour-long analytics query against the OLTP primary: name the two distinct damages and the standard fix.

(1) MVCC pinning: its snapshot blocks cleanup of every version created since it began — table/index bloat, vacuum stalls, degraded plans for everyone. (2) Resource contention on the hot path. Standard fix: run analytics on a replica (M04) — accepting its lag — or a CDC-fed warehouse (M18); and cap transaction age on the primary as a guardrail.

Your event-ingestion service deletes processed rows from a Cassandra table used as a queue. Why is the engine screaming?

LSM deletes are tombstone writes; the queue pattern means every scan reads past thousands of tombstones to find live rows until compaction catches up — read latency explodes, and tombstone thresholds may abort queries. Queues want a log (Kafka — M15's queue-or-log rule) or TTL'd time-bucketed tables; using an LSM as a mutable queue fights the engine's core design.