Phase 3: WiredTiger Storage Engine Cellular Anatomy¶

Audience: Principal Database Kernel Engineer & Storage Systems Architect
Source References: src/third_party/wiredtiger/, src/mongo/db/storage/wiredtiger/

1. B-Tree Cellular Architecture: In-Memory vs. On-Disk¶

WiredTiger does not read or write fixed-size 8KB pages like PostgreSQL. Instead, it maintains a stark structural divide between its in-memory tree nodes and its compressed on-disk physical blocks:

┌────────────────────────────────────────────────────────────────────────┐
│ In-Memory B-Tree Page (wt_page_t in WiredTiger Cache)                  │
├────────────────────────────────────────────────────────────────────────┤
│ - Completely UNCOMPRESSED raw memory                                   │
│ - wt_row_t: Array of in-memory keys and pointers                       │
│ - wt_update_t: Singly-linked list of MVCC versioned updates            │
│ - Dynamic memory footprint (Can grow up to several megabytes in RAM)   │
└───────────────────────────────────┬────────────────────────────────────┘
                                    │ Eviction / Checkpoint
                                    │ (Snappy / Zstandard Compression)
                                    ▼
┌────────────────────────────────────────────────────────────────────────┐
│ On-Disk Physical Block (collection-*.wt)                               │
├────────────────────────────────────────────────────────────────────────┤
│ - Variable length: 4 KB to 128 KB (Block Allocation)                   │
│ - High-density compressed byte stream                                  │
│ - Checksummed (CRC32C)                                                 │
│ - Free-list aligned on 4KB physical disk boundaries                    │
└────────────────────────────────────────────────────────────────────────┘

1.1 In-Memory Page Anatomy (`wt_page_t`)¶

struct __wt_page {
    uint8_t type;            /* WT_PAGE_ROW_INT (Internal), WT_PAGE_ROW_LEAF */
    uint8_t flags;           /* WT_PAGE_DISK_ALLOC, WT_PAGE_MODIFIED */
    wt_page_modify_t *modify;/* Pointer to dirty state & update chains */
    union {
        wt_row_int_t int_page;  /* Array of child page pointers */
        wt_row_leaf_t leaf_page;/* Array of key/value cells */
    } u;
};

2. Lock-Free Concurrency: Hazard Pointers¶

Classical database buffer managers use shared read/write latches (pthread_rwlock_t) on memory pages. Under thousands of concurrent reads, latch acquisition creates intense cache-line invalidation storms on the CPU bus.

WiredTiger completely eliminates reader locks on B-Tree pages using Hazard Pointers:

┌────────────────────────────────────────────────────────────────────────┐
│ Thread Local Hazard Array (Global wt_hazard_t registry)               │
├────────────────────────────────────────────────────────────────────────┤
│ Worker Thread 1: HazardSlot[0] ──► Points to Page 0x7FFF00 (Reading)   │
│ Worker Thread 2: HazardSlot[0] ──► Points to Page 0x7FFF80 (Reading)   │
│ Worker Thread 3: HazardSlot[0] ──► NULL (Idle)                         │
└────────────────────────────────────────────────────────────────────────┘

Lock-Free Read Traversal via Hazard Pointer:
1. Reader Thread obtains candidate child page pointer: wt_page_t *p = ...
2. Reader atomically publishes pointer into its private hazard slot:
   thread->hazard_ptr = p;
3. Reader performs atomic memory barrier (mfence) to ensure visibility.
4. Reader validates that the page was not marked dead by an eviction thread:
   if (p->flags & WT_PAGE_DEAD) {
       thread->hazard_ptr = NULL; // Back off and retry from parent
   }
5. Page is guaranteed safe! Eviction server cannot free memory while hazard active.
6. When read completes:
   thread->hazard_ptr = NULL;

Architectural Benefit: Readers navigate millions of B-Tree nodes in parallel without acquiring a single mutex or spinlock!

3. In-Memory MVCC: Update Chains (`wt_update_t`)¶

When a document is updated, WiredTiger does not overwrite the base data in place. Instead, it prepends an update delta node to the leaf cell:

Cellular MVCC Update Chain:
[wt_row_t Leaf Cell]
        │
        ▼
[wt_update_t (Txn ID: 105, ts: 1716382020)] ──► { "status": "SHIPPED" }  (Newest)
        │
        ▼
[wt_update_t (Txn ID: 101, ts: 1716382010)] ──► { "status": "PROCESSING" }
        │
        ▼
[wt_cell_t Base On-Disk Value (ts: 1716382000)] ──► { "status": "PENDING" } (Oldest)

3.1 Snapshot Isolation Traversal¶

When a transaction reads with a snapshot timestamp ts = 1716382015: 1. It navigates down the update chain. 2. Skips Txn 105 because its timestamp is greater than the snapshot timestamp. 3. Reads Txn 101 ("status": "PROCESSING"). 4. Commits read with complete snapshot isolation without blocking concurrent writers!

4. The Checkpoint Server & Free-List Management¶

WiredTiger runs a background Checkpoint Server that wakes up periodically (default: every 60 seconds or 2 GB of journal logs).

Checkpoint Lifecycle:
1. Open a consistent transaction snapshot across all collections.
2. Scan all dirty pages in the WiredTiger cache modified before the checkpoint timestamp.
3. Reconcile in-memory update chains:
   - Squash committed update chains into base leaf values.
   - Compress the page via Snappy or Zstd.
   - Allocate new physical blocks on disk.
4. Out-of-Place Writes:
   - WiredTiger writes modified pages to NEW blocks on disk (never overwrites old blocks).
5. Update Metadata Ledger:
   - Writes the new root pointers to WiredTiger.wt.
   - Atomically updates WiredTiger.turtle using fsync.
6. Free List Reclamation:
   - The old blocks that were replaced by the checkpoint are marked reusable in the internal Free List.

5. The Eviction Server & The 20% Dirty Cache Stall¶

The WiredTiger Eviction Server is responsible for ensuring that the uncompressed in-memory cache does not exceed its configured ceiling.

5.1 The Four Eviction Thresholds¶

WiredTiger continuously evaluates cache consumption against four critical boundaries:

WiredTiger Cache Thresholds:
0% ────────────────────────────────────────────────────────── 100%
                ▲                    ▲           ▲
                │                    │           └── eviction_trigger (95%)
                │                    └────────────── eviction_target (80%)
                └─────────────────────────────────── eviction_dirty_trigger (20%)

eviction_target (default 80%): Eviction server starts pushing clean pages out of RAM to bring cache down to 80%.
eviction_trigger (default 95%): Maximum allowable memory usage before aggressive multi-threaded eviction kicks in.
eviction_dirty_target (default 5%): Eviction server seeks to keep dirty modified memory below 5% of cache.
eviction_dirty_trigger (default 20%): THE EMERGENCY BOUNDARY.

5.2 The 20% Dirty Cache Stall Trap¶

If the application write rate exceeds disk write bandwidth, dirty pages cannot be compressed and flushed fast enough: 1. tracked dirty bytes crosses 20% of cache. 2. The background eviction threads cannot keep up. 3. WiredTiger recruits APPLICATION WORKER THREADS to perform synchronous eviction! 4. Every client thread trying to execute insertOne or updateOne is hijacked to compress pages and issue disk writes before continuing.

The Symptom: Application query latency spikes instantly from \(1\text{ ms}\) to \(> 5,000\text{ ms}\), and database throughput collapses.

6. The Write-Ahead Journal (WAL) Engine¶

While checkpoints occur every 60 seconds, data durability is maintained via the Write-Ahead Journal (WiredTigerLog.*):

[Write Operation] ──► [WiredTiger Cache Update] ──► [Appended to In-Memory Journal Buffer]
                                                                    │
                                                                    ▼
                                                     [WiredTigerLog.0000000001 (NVMe Disk)]

Commit Interval: Flushes journal buffer to disk every 100 milliseconds (commitIntervalMs).
j: true Guarantee: Overrides the 100ms timer and forces an immediate, synchronous fsync of the journal buffer before acknowledging the client write.
Crash Recovery: On restart following a sudden power failure, WiredTiger restores the last 60-second checkpoint snapshot, then replays log records from WiredTigerLog.* to recover all transactions committed up to the last journal sync.