Write-Ahead Log (WAL) & LSM-Trees

1. What It Is & Why It Exists

The Core Problem: The B+ Tree In-Place Update Penalty

Traditional relational database storage engines (e.g., MySQL InnoDB's clustered B+ tree, PostgreSQL's heap pages with B-tree indexes) use B+ Trees and page files organized into fixed-size disk pages (8 KB in PostgreSQL, 16 KB in InnoDB). When an application updates or inserts a record:

1. The engine traverses the B+ Tree index, loads the target page into memory (the buffer pool), and modifies the record.
2. The dirty page is eventually written back to disk in-place at its fixed physical address.
3. In high-velocity write workloads with random keys (such as UUIDs, user sessions, or sensor events), modifications scatter across thousands of disparate pages. Writing these pages forces the underlying storage controller to perform massive Random Disk I/O.

On modern NVMe Solid-State Drives (SSDs), random writes trigger extra internal write amplification due to NAND flash constraints (flash is written in pages but erased only in much larger blocks, so the drive's garbage collection copies live data around). On mechanical hard drives, random seeks incur a $5\text{--}10\text{ ms}$ mechanical penalty per operation, capping throughput at about 100 to 200 random operations per second.

In contrast, Sequential Disk I/O streams data continuously, bypassing head seeks and maximizing SSD controller parallelism to reach the drive's full bandwidth.

The Breakdown: The In-Place Page Rewrite Cliff

Concrete Proof: B+ Tree Random Page Rewrites vs. LSM-Tree Sequential Appends

Consider a distributed storage system ingesting $100,000\text{ writes/second}$ with $1\text{ KB}$ record payloads ($100\text{ MB/s}$ raw data ingestion):

---

The First-Principles Solution: Append-Only LSM-Trees & WAL

The Log-Structured Merge-Tree (LSM-Tree), designed by Patrick O'Neil et al. in 1996, resolves the random write bottleneck by converting all incoming mutations (inserts, updates, and deletes) into strictly sequential disk appends:

1. Write-Ahead Log (WAL): The mutation is immediately appended to an append-only log before being acknowledged. It provides ACID Durability ($D$) against power loss only if the log is synced (fsync/fdatasync) before the acknowledgement; RocksDB's default (WriteOptions.sync = false) hands the record to the OS without syncing it (see the section Durability modes: what "acknowledged" means of Write-Ahead Log, fsync & Group Commit).
2. MemTable: Then the record is inserted into an in-memory sorted data structure (typically a Concurrent SkipList or Red-Black Tree), allowing immediate $O(\log N)$ search and range scans.
3. Immutable SSTable Flush: When the MemTable reaches its capacity threshold (e.g., 64 MB), it is frozen into a read-only MemTable and flushed sequentially to disk as a sorted, immutable Sorted String Table (SSTable).
4. Background Compaction: Background threads periodically merge overlapping SSTables, discard obsolete versions, and remove tombstoned records (a tombstone only once nothing older can exist below it), maintaining logarithmic search performance.

Synthesizing vector architecture diagram...

Follow one PUT from the top. In the "Sequential Ingest Path" panel, the write is appended to the WAL on disk (for durability, once the log is synced) and then inserted into the in-memory MemTable, then acknowledged, so there are no random disk writes on the critical path. In the "Immutable SSTable Flush Tier" panel, once the MemTable reaches 64 MB it is frozen and written sequentially to disk as a Level 0 SSTable, whose key ranges may overlap with other L0 files. In the "Asynchronous Leveled Compaction Tier" panel, background merges push data down into levels about 10 times larger (256 MB, 2.5 GB, 25 GB) where files never overlap. Writes are fast because they are only appends; the cost is paid later by compaction, and by reads that may have to check several levels.

---

2. Core Mechanics & Algorithmic Architecture

The Fundamental Distributed Storage Triangle: R-W-S Amplification

Every persistent storage engine operates within the boundaries of the R-W-S Amplification Trade-off:

$$\text{Write Amplification (WA)} = \frac{\text{Total Bytes Written to Physical Storage}}{\text{Bytes Ingested by Application}}$$ $$\text{Read Amplification (RA)} = \frac{\text{Total Bytes Read from Physical Storage}}{\text{Bytes Requested by Application}}$$ $$\text{Space Amplification (SA)} = \frac{\text{Total Disk Space Occupied on Drive}}{\text{Size of Active De-duplicated Dataset}}$$

Synthesizing vector architecture diagram...

Each corner is one cost, and each arrow means that reducing one cost raises another. Write amplification (WA) counts how many bytes hit the disk per byte you write: lowest in LSM-trees (append now, merge later), high in B+ trees (rewrite a whole page for a small change). Read amplification (RA) counts bytes read per lookup: lowest in B+ trees (one path of pages), higher in LSM-trees (check several levels). Space amplification (SA) counts disk used per byte of live data: low in B+ trees (update in place), higher in LSM-trees (old versions wait for compaction). No engine wins all three corners, so choose by workload: write-heavy leans LSM, read-heavy leans B+ tree.

Leveled Compaction Sizing Mathematics

In Leveled Compaction (LCS) (used by RocksDB and TiKV), disk storage is organized into discrete exponential levels ($L_0, L_1, L_2, \dots, L_{\max}$):

• Level 0 holds SSTables flushed directly from MemTables. Because they are flushed independently, Level 0 SSTables have overlapping key ranges.
• Levels $L_1$ and higher are strictly sorted such that no two SSTables in the same level share overlapping key ranges.
• Each level has a maximum capacity that grows exponentially by a multiplier $T$ (typically $T = 10$):

$$\text{Capacity}(L_i) = C_{\text{base}} \times T^{i - 1}$$

If $C_{\text{base}} = 256\text{ MB}$ and $T = 10$:

• $L_1 = 256\text{ MB}$
• $L_2 = 2.56\text{ GB}$
• $L_3 = 25.6\text{ GB}$
• $L_4 = 256\text{ GB}$

The total worst-case Write Amplification in Leveled Compaction is bounded by:

$$\text{WA}_{\text{leveled}} \approx O\left(T \times \log_T \left(\frac{D}{C_{\text{base}}}\right)\right)$$

Where $D$ is the total database size.

---

Step-by-Step Deterministic Write & Read Pipelines

Synthesizing vector architecture diagram...

---

In-Memory & On-Disk State Structures

1. In-Memory SkipList Architecture

The MemTable is backed by a lock-free Concurrent SkipList. Elements are arranged in linked lists with probabilistic multi-level forward pointers, providing $O(\log N)$ search, insertion, and range iterations without global lock contention.

2. Immutable SSTable File Anatomy

When a MemTable flushes to disk, it produces an immutable SSTable file structured into fixed-size blocks (typically 4 KB):

Synthesizing vector architecture diagram...

The file is written left to right, but read from the right. A reader first opens the fixed-size Footer at the end of the file, which points to the Meta Index and Index Block. For a lookup, the Filter Block's Bloom filter answers first: if the key is definitely absent, the read stops without touching data. Otherwise the sparse Index Block gives the one 4 KB data block that could hold the key, and only that block is read and decompressed. So a lookup costs about one small block read per file, because the filter and index are usually cached in RAM.

---

Scenario Execution Matrix: LSM Read, Write, and Compaction Dynamics

---

3. Data Migration, Anti-Entropy & Consistency Protocols

1. Compaction Strategies Compared

Synthesizing vector architecture diagram...

Both panels show one merge step. In the "Size-Tiered Compaction" panel, the engine waits until there are four similar 100 MB SSTables and merges them into one 400 MB file; each byte is rewritten only a few times, but files within a tier can overlap, so a read may have to check several. In the "Leveled Compaction" panel, each level is a set of files with non-overlapping key ranges: a file from L1 covering A-M is merged into the L2 files that overlap it, producing A-D, E-H and I-M. Leveling rewrites data more often (higher write amplification) but lets a read check at most one file per level; choose size-tiered for write-heavy workloads and leveled for read-heavy ones.

---

2. WAL Group Commit & Fsync Durability Protocols

Calling fsync() (or fdatasync()) forces the data through the page cache and the drive's volatile write cache to persistent storage. One log does one sync at a time, so with one write per sync it caps at $1 / L$ writes a second for a sync latency $L$: $1,000$ at $1\text{ ms}$, and "a few hundred" only at $2\text{--}5\text{ ms}$. Modern engines implement Group Commit:

• Incoming client threads queue their mutations. The first writer that finds no sync in progress becomes the leader: it writes every queued record to the log and issues one fdatasync() (RocksDB's write-group leader does exactly this).
• Writers that arrive during that sync queue up and form the next batch. No timer is needed: the batch is whoever arrived during the last sync. (A window variant waits on purpose, e.g. up to 2 ms or 64 KB, trading latency for fewer syncs.)
• All client requests in that batch are acknowledged once the sync returns. At $100,000$ writes a second and $L = 1\text{ ms}$, about 100 writes share each sync ($1,000$ syncs a second) and each write waits between $L$ and $2L$. That is durable against a crash or power loss of this node, if every layer honours the flush; it doesn't survive losing the disk (see the sections What fsync really guarantees, Group commit and Durability modes: what "acknowledged" means of Write-Ahead Log, fsync & Group Commit).

3. Distributed Anti-Entropy, Merkle Trees & Crash Recovery

• Merkle Tree Anti-Entropy Repair: In distributed LSM databases (e.g., Apache Cassandra, ScyllaDB), node replicas detect out-of-sync data without transferring entire datasets. Replicas construct hierarchical Merkle trees over token ranges. During operator-run anti-entropy repairs (nodetool repair), nodes exchange tree roots ($O(1)$) and traverse diverging child branches ($O(\log N)$) to isolate diverging key ranges, streaming only the data in the mismatched ranges. (Cassandra 4.0+ can send a whole SSTable with zero-copy streaming when every partition in that file has to be transferred.)
• WAL Checkpointing & Crash Recovery Protocol: On unexpected process termination, the engine reconstructs volatile MemTables deterministically from the on-disk Write-Ahead Log:
  1. Parse the most recent Checkpoint Marker: retrieves the last flushed Log Sequence Number ($\text{LSN}_{\text{flush}}$).
  2. Sequential Scan: Replay WAL log records starting strictly from $\text{LSN}_{\text{flush}} + 1$.
  3. Tail Truncation on CRC Mismatch: Validate a checksum per record (CRC32C in RocksDB and PostgreSQL). If power loss caused a torn write at the file tail, the engine stops at the first bad record and discards the trailing bytes, restoring consistent state; when the engine syncs before acknowledging, those bytes belong only to writes that were never acknowledged. Damage followed by valid records is not a torn tail: what happens then is the engine's recovery mode (RocksDB's wal_recovery_mode, kPointInTimeRecovery by default, stops at the first corruption).

---