The Grand Imperial Treasury of the Northern Capital governed the wealth of the entire empire. Tributary silks and silver ingots from thirty provinces arrived at its water gates day and night, an unbroken torrent of commercial accounting.

In earlier reigns, the treasury scribes followed a comfortable, intuitive habit: when a caravan of bullion wagons rolled into the courtyard, porters unloaded the heavy silver chests into deep underground vaults. Only after the brass locks clicked shut and the vault wax hardened did the scribe draw forth his leather master ledger, dipping his brush in ink to record the transaction. Then came the bitter winter of the Great Fire. Sparks from a subterranean brazier ignited dry timber, engulfing the counting house in a roaring inferno. The cedar roof collapsed, reducing half of the master ledgers to soot, while shattered silver chests and overturned wagons scattered across the burning snow.

When the embers cooled, the treasury found itself paralyzed in an irrecoverable swamp of contradictions: Dozens of unlabeled silver chests lay in the muddy courtyard. Some had been stored safely in the vaults, yet the soot-stained ledgers held no mention of them; other ledger pages recorded large tributes as “Safely Sealed,” yet not a single ingot could be found in the vaults—the porters had dropped the boxes on the snow, the scribes had inked the entry, and the roof had collapsed before the chests ever touched the cellar floor. No man alive could discern which transactions had finalized and which were half-done. Imperial payrolls and border military rations were frozen solid, and the Grand Minister contemplated taking his own life.

The newly appointed Chief Scribe, Master Mo, stood before the blackened ruins and proclaimed two eternal statutes: “From this dawn forward, the Treasury operates under the Rule of Write-Ahead, and we shall resurrect the ashes through the Three Passes of Restoration!”

Rule One: “Ink Before Ingot” (The Write-Ahead Logging Protocol). Upon the granite masonry of the treasury gateway, Mo chiseled an aperture leading to an iron fireproof chute. Inside lay a continuous roll of asbestos-woven fireproof parchment. Master Mo declared: Before a single porter touches a chest, the scribe must write an entry upon the fireproof scroll, stamped with a strictly monotonic sequence number, the merchant’s name, the chest’s unique number, and the before-and-after disposition of silver. Only after the ink dried and the parchment rolled into the fireproof chute were porters permitted to budge the chest. Even if a carriage broke down midway in the muddy courtyard, though the ledger on the table burned to cinders, the record in the fireproof chute remained eternal.

Rule Two: “Three Passes of Resurrection” (The ARIES Recovery Phases). Years later, lightning struck the west wing of the treasury, unleashing another sudden fire. When the smoke cleared, Master Mo retrieved the intact fireproof scroll and the soot-darkened vault ledgers, guiding his scribes through the three rigorous passes:

The First Pass: The Analysis Pass. Starting from the previous month’s certified seal of balance—the Audit Checkpoint—Master Mo scanned the scroll forward to the very last stroke of ink made before the flames. In this pass, not a single chest of silver was moved. Mo charted the wreckage upon a sand table: Which silver chests had been modified in the vaults without ledger confirmation? And at the precise heartbeat when the roof fell, which transactions remained active and incomplete?

The Second Pass: The Redo Pass (Repeating History). Having mapped the unsettled chests, Master Mo turned back to the earliest recorded modification that had not yet been sealed in stone. Following the scroll’s chronology, he commanded his men to replay every single logged action forward right up to the spark of the fire—even replaying the actions of merchants whose business had been cut short! His juniors protested: “Why waste sweat restoring transactions that were never completed?” Master Mo chided them: “Without knowing the exact truth of what transpired, how can one judge what is broken? To purge chaos, one must first resurrect the world exactly as it stood at the instant of destruction!”

The Third Pass: The Undo Pass (Rolling Back Unfinished Transactions). With the treasury restored to the exact physical state it occupied the microsecond before the disaster, Master Mo reversed his course. Focusing on the transactions flagged as incomplete, he scanned backward from the end of the scroll, rolling back uncommitted steps and returning silver chests to their rightful owners. Crucially, for every step reversed, Master Mo inked a distinctive vermillion slip into the scroll—a Compensation Slip (Compensation Log Record / CLR). He instructed his scribes: “In the turbulence of calamity, a secondary fire may strike while we rebuild. Should the roof collapse again today, the next scribe will see this red slip, skip the reversed work, and never undo the same chest twice!”

When the three passes concluded, twenty million taels of imperial bullion balanced to the grain of silver. The Imperial Court sang in enduring admiration: “Write the scroll before moving gold; through fire and storm, truth holds its mold. Analyze the ruins to know the dead; repeat all history where the living tread. Roll back the severed in reverse design; with scarlet tallies, keep the future fine.”

— — —

What it is

By now the architecture is unmistakable: this is the bedrock of database durability (Durability) and atomicity (Atomicity) across modern relational and transactional systems (PostgreSQL, MySQL InnoDB, SQLite, Oracle): Write-Ahead Logging (WAL) and the crowning masterpiece of recovery theory—the ARIES (Algorithm for Recovery and Isolation Exploiting Semantics) algorithm.

In high-performance database engines, modified data pages cannot be written to disk synchronously on every transaction commit without strangling throughput in random disk I/O bottlenecks. Instead, modifications occur in an in-memory buffer pool as “dirty pages.” If the system crashes, unwritten dirty pages evaporate from RAM. Without a deterministic recovery protocol, committed data would vanish, and uncommitted transactions would leave corrupted, partial writes on disk.

WAL and ARIES resolve this dilemma through mathematical elegance:

1. The WAL Protocol: Before any dirty in-memory data page can be written back to durable disk storage, the corresponding log record describing the modification must be flushed to append-only disk storage first. An update transaction is declared “committed” the moment its small commit log record is flushed sequentially to disk, decoupling commit latency from large random page writes. Every log record carries a globally monotonic Log Sequence Number (LSN). Each disk page also records the pageLSN of the latest update applied to it, creating a verifiable chronological anchor.
2. The Three Passes of ARIES Recovery: When a database reboots after an unexpected crash or power failure, it executes ARIES’s canonical three-phase recovery:
   • The Analysis Pass: Scans the log forward starting from the most recent Checkpoint. It reconstructs the in-memory state as of the crash: the Dirty Page Table (DPT, tracking which pages were dirty and their earliest unwritten recLSN) and the Transaction Table (TT, identifying active, uncommitted transactions);
   • The Redo Pass (Repeating History): Scans forward from the smallest recLSN across all dirty pages up to the end of the log. ARIES adheres strictly to the philosophy of Repeating History: it reapplies all logged modifications—for both committed and uncommitted transactions—bringing the database to the exact physical state it occupied the microsecond before the crash. If a page already has pageLSN >= logLSN, the redo operation is skipped, guaranteeing idempotency;
   • The Undo Pass: Scans backward through the log, rolling back the actions of all active, uncommitted transactions identified in the Transaction Table. For every undone action, ARIES writes a Compensation Log Record (CLR). The CLR contains an UndoNextLSN pointer bypassing the reversed action. If the database crashes again during recovery, subsequent restarts inspect the CLR, skip already-undone actions, and prevent catastrophic infinite recovery loops.

Why it matters

WAL and ARIES constitute the foundational grammar of dependable computing:

1. Transforming Random I/O into Blazing Sequential Throughput: WAL allows database engines to buffer gigabytes of dirty random writes in RAM while guaranteeing ACID durability through lightweight, sequential append-only logging.
2. Repeating History Decouples Recovery from Concurrency: By restoring the exact physical state of the database before attempting logical rollbacks, ARIES decouples crash recovery from complex application-level lock models, enabling granular row-level locking without risking recovery corruption.
3. Provable Idempotency under Cascading Crashes: The genius of Compensation Log Records (CLRs) ensures that crash recovery itself is fully crash-resilient. A database can lose power ten times consecutively midway through recovery, yet resume and finish without human intervention or data corruption.

Metaphor mapping

• Twenty million taels of silver in courtyard wagons vs. underground vaults → In-memory dirty pages in the buffer pool vs. persistent disk data pages
• Moving chests before logging leading to post-fire paralysis → Violating WAL causing irrecoverable database corruption upon sudden crash
• Fireproof stone chute and continuous asbestos scroll → Append-only Write-Ahead Log (WAL file) on durable storage
• Ink drying in chute before lifting chests → The WAL protocol: log records must flush to disk before dirty data pages can be written
• Ascending brush serial numbers on slips and chest tags → Globally monotonic Log Sequence Numbers (LSN) and pageLSNs
• First Pass: Surveying the ruins without moving gold → The Analysis Pass reconstructing the Dirty Page Table and Transaction Table
• Second Pass: Replaying every action up to the blaze → The Redo Pass (Repeating History) bringing the database to the exact pre-crash state
• Third Pass: Rolling back incomplete transactions backward → The Undo Pass rolling back uncommitted transactions
• Inking a vermillion compensation slip upon each reversal → Writing Compensation Log Records (CLRs) to prevent infinite loops during recovery crashes