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, PostgreSQL Heap Storage) use B+ Trees organized into fixed-size disk pages (typically 8 KB or 16 KB). 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 severe write amplification due to NAND flash block-erase constraints (data must be read, erased in blocks of 2–8 MB, and re-written). On mechanical hard drives, random seeks incur a $5\text{--}10\text{ ms}$ mechanical penalty per operation, capping throughput at several hundred operations per second.

In contrast, Sequential Disk I/O streams data continuously, bypassing head seeks and maximizing SSD controller parallelism to achieve bus saturation ($> 3,500\text{ MB/s}$ on PCIe Gen 4 NVMe).

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 on disk before being acknowledged, providing ACID Durability ($D$).
2. MemTable: Concurrently, 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, maintaining logarithmic search performance.

Interactive Architecture Diagram
100%Fit100%
Synthesizing vector architecture diagram...

---

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}}$

Interactive Architecture Diagram
100%Fit100%
Synthesizing vector architecture diagram...

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

Interactive Architecture Diagram
100%Fit100%
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):

Interactive Architecture Diagram
100%Fit100%
Synthesizing vector architecture diagram...

---

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

---

3. Data Migration, Anti-Entropy & Consistency Protocols

1. Compaction Strategies Compared

Interactive Architecture Diagram
100%Fit100%
Synthesizing vector architecture diagram...

---

2. WAL Group Commit & Fsync Durability Protocols

Calling fsync() on a storage drive forces the mechanical or solid-state controller to flush its volatile write cache to persistent storage, capping throughput at a few hundred operations per second. Modern LSM engines implement Group Commit:

• Incoming client threads append their mutations to a lock-free concurrent staging buffer.
• A single background sync worker issues fdatasync() once per micro-batch (e.g., every $1\text{ ms}$ or whenever $64\text{ KB}$ accumulates).
• All client requests in that batch are acknowledged simultaneously, delivering $100,000+\text{ ACID writes/second}$ with full hardware durability.

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 background 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 missing immutable SSTables across nodes via zero-copy network transfer.
• 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 CRC32 checksums per record. If power loss caused a torn write at the file tail, the engine truncates the corrupted uncommitted trailing bytes up to the last valid transaction boundary, restoring consistent state.

---