Cellular Anatomy of PostgreSQL: Write-Ahead Logging (WAL) & Crash Recovery¶

1. Introduction: The Thermodynamic Law of Durability (ACID)¶

In physical systems, entropy increases and systems tend toward chaos (power outages, OS kernel panics, hardware failures). In database engineering, the Write-Ahead Log (WAL) is the mathematical apparatus that enforces Durability and Crash Consistency.

The fundamental rule of Write-Ahead Logging is: $$\text{No dirty data block in } \texttt{shared\_buffers} \text{ may be written to physical disk until the WAL record describing that change is flushed to physical disk first.}$$

If a database writes a dirty table block to disk before the WAL record is persistent, and the server loses power midway through, the table page is corrupted (a torn write), and recovery is physically impossible.

2. Anatomical Blueprint: The 64-Bit Log Sequence Number (LSN)¶

Every single byte ever written to WAL in the lifetime of a PostgreSQL cluster is assigned a monotonically increasing 64-bit unsigned integer: the XLogRecPtr (LSN).

Located in src/include/access/xlogdefs.h:

typedef uint64 XLogRecPtr;

The Anatomy of an LSN String (e.g., `0/16B3748`):¶

When formatted as text in PostgreSQL, the 64-bit integer is split into two 32-bit hexadecimal words separated by a forward slash:

                      LSN = 0/16B3748
                     /               \
      [Logical Segment ID: 0]   [Byte Offset: 0x16B3748 = 23,803,720]

Mapping an LSN to a Physical 16MB WAL File:¶

WAL is subdivided into physical 16MB files located in $PGDATA/pg_wal/: * File naming convention: 24 hexadecimal characters: [TimelineID (8 hex)] [LogSegmentID (8 hex)] [SegmentNumber (8 hex)] e.g., 000000010000000000000001 * Mathematical Translation Formula: $$\text{Segment Number} = \frac{\text{LSN}}{\text{16MB (16,777,216 bytes)}}$$ $$\text{Offset within File} = \text{LSN} \pmod{\text{16MB}}$$

3. Dissecting the Physical WAL Record (`XLogRecord`)¶

Located in src/include/access/xlogrecord.h. Every WAL record has a binary header followed by block references and payload data:

typedef struct XLogRecord
{
    uint32          xl_tot_len;     /* Total length of entire record in bytes */
    TransactionId   xl_xid;         /* Transaction ID that produced this record */
    XLogRecPtr      xl_prev;        /* LSN pointer to previous WAL record (Reverse Chain) */
    uint8           xl_info;        /* Resource-manager specific flags */
    RmgrId          xl_rmid;        /* Resource Manager ID (Heap, Btree, Transaction, etc.) */
    pg_crc32c       xl_crc;         /* 32-bit CRC checksum for bit-rot detection */
} XLogRecord;

The 16 Resource Managers (`RmgrId`):¶

Postgres does not store raw SQL text ("UPDATE orders...") in WAL. It stores structured binary delta records processed by specialized Resource Managers: * RM_XLOG_ID (0): Core checkpoints, parameter changes. * RM_XACT_ID (1): Transaction commit, abort, and subtransaction records. * RM_HEAP_ID (9): Heap inserts, updates, deletes, and HOT pruning. * RM_BTREE_ID (11): B-Tree page splits, vacuuming, and key insertions. * RM_GIN_ID (13): Inverted index posting list updates.

4. The Full Page Write (FPW) Torn-Page Defense Mechanism¶

The Hardware Pathology:¶

The Linux/macOS filesystem writes data in 4,096-byte (4KB) sectors.
PostgreSQL writes data in 8,192-byte (8KB) pages.
If a power outage occurs midway through writing an 8KB page, the drive writes the first 4KB and loses power before writing the second 4KB.
The Result: A Torn Page. The page header and lower data do not match the upper data. The page checksum (pd_checksum) fails, rendering the entire database unbootable!

The Cellular Immunity Protocol:¶

PostgreSQL solves this with Full Page Writes (full_page_writes = on):

                  +----------------------------------------------+
                  |         Checkpoint Completes at LSN X        |
                  +----------------------------------------------+
                                         |
                                         v
                  First time Page 42 is modified AFTER Checkpoint:
                                         |
                                         v
                  +----------------------------------------------+
                  | Engine writes the ENTIRE 8KB PAGE IMAGE      |
                  | into the WAL record payload!                 |
                  +----------------------------------------------+
                                         |
                                         v
                  Subsequent modifications to Page 42:
                  Engine writes only small delta records (e.g. 50 bytes)

During Crash Recovery: If Page 42 was torn during the crash, Postgres simply reads the full 8KB image from WAL, overwrites the torn page on disk completely, and then replays subsequent deltas on top of it. 100% crash immunity.

5. The Cellular Physiology of a Checkpoint (`CheckPointGuts`)¶

The Checkpointer process (src/backend/postmaster/checkpointer.c) is the organ responsible for bounding crash recovery time.

Without Checkpoints:
Replay WAL from the very beginning of the database (hours/days of reboot time).

With Checkpoints:
Replay WAL only from the last Checkpoint LSN forward (seconds of reboot time).

The 7 Stages of Checkpoint Execution:¶

Identify Starting LSN: Checkpointer records current WAL write location as checkPoint.redo.
Flush WAL Buffers: Forces all unwritten WAL records in wal_buffers to physical disk.
Scan Shared Buffers: Inspects all $N$ descriptors in shared_buffers. Any buffer with BM_DIRTY set is tagged for flushing.
Sort Dirty Pages: Sorts dirty pages physically by (RelationFileNode, BlockNumber) so the disk controller can write them using optimal sequential elevator scheduling.
Smooth Write Throttling (checkpoint_completion_target = 0.9): Rather than saturating disk I/O immediately, the Checkpointer sleeps between writes, spreading the I/O evenly across 90% of the checkpoint duration.
Physical fsync(): Issues fsync() calls on all modified OS file descriptors.
Update the Brain: $PGDATA/global/pg_control: Writes a binary ControlFileData struct to disk containing the new Checkpoint LSN. This is the atomic moment the checkpoint becomes officially persistent.

6. The Recovery State Machine (Replaying the Past)¶

When PostgreSQL boots up after a hard kill (kill -9) or power failure:

stateDiagram-v2
    [*] --> ReadControlFile
    ReadControlFile --> FindCheckpoint: Read control file
    FindCheckpoint --> ReadWAL: Locate last Checkpoint LSN
    ReadWAL --> ValidateCRC: Open WAL at REDO LSN

    state REDO_LOOP {
        ValidateCRC --> DispatchRmgr: Valid CRC-32C
        DispatchRmgr --> ComparePageLSN: Match RmgrId
        ComparePageLSN --> ApplyChange: Record LSN is newer
        ComparePageLSN --> SkipChange: Page already up to date
        ApplyChange --> AdvanceLSN: Applied delta
        SkipChange --> AdvanceLSN: Skipped delta
        AdvanceLSN --> ValidateCRC: More records exist
    }

    AdvanceLSN --> PromoteCluster: Reached End of WAL
    PromoteCluster --> [*]: Postmaster operational