Write-Ahead Log & LSM Trees

Tier 1 — Building Block

1. What Is It?

Write-Ahead Log (WAL): A WAL is a sequential, append-only file that records every database write before applying it to the main data structure. "Write-ahead" means the log entry is durably written to disk before the operation is considered committed. On crash recovery, the database replays the WAL to restore any writes that were logged but not yet applied to the main files — guaranteeing durability (the D in ACID) without requiring every write to sync the entire database file.

LSM Tree (Log-Structured Merge-Tree): An LSM tree is a write-optimized data structure that takes the WAL concept further — all writes are only appended to sequential files; reads are served from a merge of multiple sorted files. LSM trees convert random-write workloads (which are slow on disk) into sequential-write workloads (which are fast), achieving write throughput 10–100× higher than B-trees for write-heavy workloads.

The core problem both solve: spinning disks (HDDs) are ~1000× slower for random writes than sequential writes. Even SSDs are 10–20× slower for random writes vs. sequential writes at sustained throughput. Sequential, append-only writes are the fastest possible I/O pattern.

2. How It Works

Write-Ahead Log (WAL) Mechanics

-+ResetFullscreen

On crash:

Recovery:
1. Load last consistent checkpoint (data file state)
2. Replay WAL from checkpoint LSN (log sequence number) onward
3. All logged writes are re-applied → database is consistent

WAL is used by:

• PostgreSQL: WAL files in pg_wal/. Also used for streaming replication (replicas are WAL consumers).
• MySQL InnoDB: Redo log (similar to WAL) + binary log (for replication).
• Kafka: The Kafka log is a WAL — every message is an append to a sequential file.
• Raft/Paxos: Distributed consensus protocols persist a WAL before committing entries.

B-Tree: The Write Problem

Traditional databases use B-trees. A B-tree is a balanced tree stored on disk; each node is a fixed-size page (a 4–16KB block of data — the smallest unit the disk reads or writes). An update to a row in the middle of the B-tree requires:

1. Read the page from disk (random read)
2. Modify the row in memory
3. Write the page back to disk (random write to an arbitrary location)

Random writes to arbitrary disk locations are slow. At high write throughput, the B-tree checkpoint (writing dirty pages to disk) becomes the bottleneck.

LSM Tree: The Write Solution

LSM trees replace the random-write B-tree update pattern with a pipeline of sequential writes:

-+ResetFullscreen

SSTable (Sorted String Table): An immutable, sorted file on disk. Keys are sorted; values follow. A sparse index (every N-th key) enables binary search. Once written, never modified.

MemTable: An in-memory sorted data structure (red-black tree or skip list). All writes go here first. When it reaches ~64MB, it is flushed to disk as a new Level 0 SSTable.

Compaction: Background process that merges SSTables from lower levels into fewer, larger SSTables at higher levels. This is a k-way merge sort of sorted files — purely sequential reads and writes. Compaction:

1. Removes deleted keys (tombstones — special markers written when a key is deleted, since you can't remove data from an immutable SSTable directly)
2. Resolves duplicate keys (keeps the latest version)
3. Merges small files into large files for efficient reads

-+ResetFullscreen

Bloom Filter: A probabilistic data structure that answers "is key X in this SSTable?" with zero false negatives and a small false positive rate (~1%). Before reading any SSTable, check its Bloom filter — if it says "no," skip the file. This avoids reading files that don't contain the key, making reads much faster.

Read amplification vs. Write amplification:

3. Variants & Comparisons

Compaction Strategies

Technologies Using LSM Trees

4. When to Use It (and When NOT To)

Use LSM-Based Stores When:

• Write throughput is the primary constraint: LSM converts random writes to sequential — often 10–100× faster write throughput than B-tree databases for sustained workloads.
• Time-series / event log data: Append-only insert patterns are perfectly suited for LSM.
• High cardinality key-value data: IoT sensor readings, user events, log records — each insert is a new key, rarely updated.
• Large datasets with limited SSD budget: LSM's sequential I/O pattern is more efficient on SSD than random B-tree page writes.

Decision triggers:

• "If write QPS is the bottleneck and data is append-mostly → use Cassandra or RocksDB"
• "If you're storing time-series events (metrics, IoT, logs) → LSM tree (Cassandra, InfluxDB TSM engine)"
• "If you read the same keys repeatedly → B-tree (PostgreSQL/MySQL) is better due to lower read amplification"

Do NOT Use LSM When:

• Read-heavy with random key access: LSM read amplification (multiple SSTable lookups) is worse than a B-tree's O(log N) single-pass lookup.
• Strong ACID transactions with complex queries: B-tree databases (PostgreSQL) have decades of SQL optimization, JOIN support, and MVCC. LSM stores typically lack this.
• Frequent updates to the same key: Each update adds a new version to the LSM; compaction must eventually merge them. Many updates to the same key amplify compaction work. B-trees do in-place updates more efficiently.

Anti-patterns:

• Neglecting compaction: If compaction falls behind write throughput, read performance degrades severely (more SSTables to check per read). Monitor compaction throughput and pending bytes.
• Ignoring tombstone accumulation: Deletes in LSM write a tombstone marker, not an actual deletion. Until compaction runs, tombstones accumulate — queries must scan past them. Heavy delete workloads can severely degrade performance.
• No Bloom filters: Reading LSM without Bloom filters requires checking every SSTable for a miss. Always configure Bloom filters for read-heavy LSM workloads.

5. Real-World Usage

Facebook/Meta (RocksDB everywhere): Meta open-sourced RocksDB in 2013 as a fork of LevelDB optimized for SSD and high-concurrency workloads. Today RocksDB is used as the storage engine for: ZippyDB (Meta's distributed key-value store), MyRocks (MySQL with RocksDB storage engine — 2× compression vs. InnoDB for Meta's production MySQL), Logdevice (Meta's log storage system), and the TiKV key-value store inside TiDB. Meta runs millions of RocksDB instances globally.

Apache Cassandra (Facebook, Netflix, Uber): Cassandra's write path is a pure LSM implementation: CommitLog (WAL for durability) → MemTable (in-memory) → SSTable (flushed to disk). Netflix uses Cassandra for viewing history (write-heavy: every view event is a write), storing trillions of events. Cassandra handles millions of writes/sec per cluster by virtue of LSM's sequential write pattern. Netflix stores 1+ trillion events in Cassandra clusters.

PostgreSQL WAL for replication: PostgreSQL's WAL is not just for crash recovery — it's the foundation for streaming replication. Replicas are WAL consumers: the primary ships WAL segments to replicas in real time. This is why adding a PostgreSQL replica is easy (just point it at the primary's WAL stream) and why replicas are byte-identical to the primary. The WAL is the single source of truth for all state changes.

6. Interview Cheat Sheet

Key sentences to demonstrate depth:

1. "WAL provides crash recovery by writing intent before action — on crash, replay the WAL from the last checkpoint. It also enables replication: replicas are just WAL consumers receiving the same change stream."
2. "LSM trees trade read amplification for write amplification — all writes are sequential appends, converting the random-write problem into a sequential-write problem, achieving 10–100× higher write throughput than B-trees under sustained write load."
3. "The MemTable → Level 0 SSTable → compaction pipeline is the key mechanism: writes go to memory (fast), overflow to immutable sorted files, and background compaction merges files — all sequential I/O."
4. "Bloom filters are critical for LSM read performance — a small probabilistic structure that says 'this key is definitely NOT in this file' with zero false negatives, eliminating unnecessary SSTable reads."
5. "Cassandra's LSM trade-off: it's an AP system built for write throughput. Every Cassandra table design question starts with the query pattern, because LSM reads are efficient only if you hit the right partition — scatter-gather across partitions is expensive."

Common follow-up questions:

Connections to other building blocks:

• Replication (Read Replicas): WAL is the transport mechanism for PostgreSQL and MySQL streaming replication. Replicas replay the WAL from the primary.
• Message Queues (Kafka): Kafka's log storage is essentially a WAL — every message is appended sequentially. Kafka partitions are immutable append-only log segments, analogous to SSTables.
• Cassandra / Wide-Column Store: Cassandra's entire write path is LSM. Understanding LSM is prerequisite to understanding Cassandra's performance characteristics (write-optimized, read amplification on non-partition-key queries).
• Consistent Hashing: Cassandra distributes partitions across nodes using consistent hashing; each node stores its partition's LSM tree locally.
• Sharding: RocksDB is typically embedded in each shard of a distributed database (CockroachDB, TiKV). Each shard is a self-contained LSM tree.