Day 10: The Hands-on Task: Implement a Write-Ahead Journal (WAJ) for your graph update operations. Before modifying the adjacency list on disk, write the intended changes to an append-only journal file and call fsync. Write a test that forcibly terminates your process mid-transaction, restarts it, parses the journal, and rolls back or completes the interrupted transaction to restore 100% consistency.

Day 10: Crash Consistency and the Write-Ahead Journal (WAJ)

In Day 9, you built a PageRank ranking engine that iterated over an in-memory web graph until it converged to a stable rank distribution of $10^{-5}$. It worked flawlessly because the graph lived in a pristine, uninterrupted memory space.

But in production, memory is volatile, and processes are mortal.

If your server loses power, or if an administrator issues a kill -9 while your engine is writing new edges to the adjacency list on disk, you do not just lose the updates—you corrupt the database. A half-written 8-byte pointer or an unaligned binary record will cause your parser to throw segmentation faults or read garbage data on reboot.

Today, we implement a Write-Ahead Journal (WAJ)—often called a Write-Ahead Log (WAL)—to guarantee crash consistency. Before we modify a single byte of our primary graph file on disk, we will write our intent to an append-only journal, force those bytes to physical storage using the fsync system call, and only then apply the modification to the database.

The Production Stakes: Why Naive Writes Fail

Consider a binary adjacency list file (graph.db) where each edge is represented by two 4-byte integers: [source_node_id, target_node_id].

If you append a new edge, the operating system does not immediately spin the disk platter or charge the flash cells. Instead, it writes the data to the kernel's page cache—a pool of physical memory managed by the OS. The write() system call returns almost instantly, claiming success.

At some point later (up to 30 seconds on standard Linux configurations), the kernel threads flush these dirty pages to disk.

If the power fails 5 seconds after your write call:

1. Your application believes the write succeeded.

2. The data is entirely lost because it only existed in volatile RAM.

3. If the crash happened during a page flush, the disk might contain a partial write—for instance, the 4-byte source_node_id is written, but the target_node_id contains random garbage or zeros.

Real-World Post-Mortem: Fsyncgate (2018)

In 2018, the PostgreSQL community discovered a systemic issue in how the Linux kernel handled fsync() failures. When a dirty page failed to write to disk (e.g., due to a temporary hardware error), the kernel cleared the "dirty" flag and marked the page as clean, but kept the error state in the file descriptor.

If PostgreSQL retried fsync(), the kernel returned success because the page was no longer marked dirty, even though the data was never written to physical media. This led to silent, unrecoverable database corruption.

We avoid this by using a strict, single-direction redo protocol, treating any write or sync failure as a fatal event that requires process termination and journal replay.

Component Architecture

To guarantee durability, we split our storage engine into three distinct layers:

The 4-Step Write Protocol (The Commit Barrier)

To add an edge safely: