Write-Ahead Logging & ARIES: The Foundations of Database Durability and Crash Recovery

In transactional database management systems (DBMS), volatile RAM is used to cache modified disk pages for high write performance. However, because RAM is volatile, a sudden operating system crash or hardware power outage wipes out all in-memory modifications.

Flushing every modified data page directly to its random disk location before committing would cause catastrophic I/O bottlenecks. To provide the ACID guarantees of **Atomicity** (all-or-nothing transactions) and **Durability** (committed transactions survive power loss), modern databases use **Write-Ahead Logging (WAL)** combined with C. Mohan's landmark **ARIES (Algorithms for Recovery and Isolation Exploiting Semantics)** crash recovery algorithm.

Buffer Pool Management: Steal/No-Steal and Force/No-Force

How a database engine coordinates in-memory buffer pages and disk storage depends on two fundamental architectural policies:

1. Steal vs. No-Steal (Affects Atomicity / Undo)

• Steal Policy: The buffer manager is allowed to flush dirty pages belonging to an active, uncommitted transaction to disk to free up RAM. Requires **Undo logging** to roll back changes if that transaction subsequently aborts or crashes.
• No-Steal Policy: Dirty pages modified by uncommitted transactions are never written to disk before commit. Eliminates undo logging but severely restricts memory capacity.

2. Force vs. No-Force (Affects Durability / Redo)

• Force Policy: At commit time, the DBMS must synchronously flush all pages modified by the transaction to disk before acknowledging success. Eliminates the need for redo logging but results in heavy random I/O write amplification.
• No-Force Policy: The DBMS acknowledges commit as soon as log records are safely persisted sequentially, leaving data pages in RAM to be written asynchronously. Requires **Redo logging** to reapply changes during crash recovery.

Modern high-performance storage engines (such as PostgreSQL, MySQL InnoDB, and SQLite) use a **Steal / No-Force** policy because it maximizes throughput, relying on WAL and ARIES to ensure correctness.

The WAL Protocol & Log Sequence Numbers (LSNs)

The Write-Ahead Logging protocol enforces two mandatory ordering rules:

1. Write-Ahead Invariant: Before any dirty data page is written from RAM to disk, all log records describing modifications to that page must already be written to non-volatile log storage.
2. Commit Invariant: A transaction is not officially committed until its `COMMIT` log record has been synchronously flushed to disk (`fsync`).

Tracking State with Log Sequence Numbers

Every log record is tagged with a monotonically increasing integer called a **Log Sequence Number (LSN)**:

• pageLSN: Written into the header of every individual data page on disk/memory, recording the LSN of the latest log record applied to that page.
• flushedLSN: Tracks the largest LSN written and persisted to disk in the append-only log file.
• The WAL rule mathematically ensures: $\text{pageLSN} \le \text{flushedLSN}$ before writing the page to disk.

The ARIES Three-Phase Recovery Algorithm

When a database restarts following an abrupt system crash, the ARIES algorithm executes a three-phase recovery procedure across the log:

Phase 1: The Analysis Phase

Scans the log forward from the most recent checkpoint to the end of the log to reconstruct the internal memory state at the moment of the crash. It rebuilds the **Dirty Page Table (DPT)** (which pages were in RAM and need flushing) and the **Transaction Table (TT)** (which transactions were active/uncommitted).

Phase 2: The Redo Phase (Repeating History)

Scans forward starting from the lowest `recLSN` in the Dirty Page Table to the end of the log, reapplying all logged operations—including those of transactions that were later aborted. If a page's on-disk `pageLSN >= logLSN`, the page already contains the change and the I/O write is skipped. This restores the database to the exact state it was in right before the crash.

Phase 3: The Undo Phase

Scans backward from the end of the log, rolling back changes made by all transactions that were active (uncommitted) at the time of the crash (the 'losers'). For every undone modification, ARIES writes a **Compensation Log Record (CLR)** containing an `undoNextLSN` pointer, ensuring that if the system crashes again *during* recovery, previously undone actions are never rolled back twice.

C++ Conceptual Simulation Blueprint (WAL Record Engine)

#include <iostream>
#include <vector>
#include <string>
#include <cstdint>

enum RecordType { BEGIN, UPDATE, COMMIT, ABORT, CLR };

struct LogRecord {
    uint64_t lsn;
    uint64_t prevLsn;
    uint32_t txnId;
    RecordType type;
    uint32_t pageId;
    std::string undoData;
    std::string redoData;
    uint64_t undoNextLsn; // Used for Compensation Log Records (CLRs)
};

class WALEngine {
private:
    uint64_t currentLsn = 1;
    uint64_t flushedLsn = 0;
    std::vector<LogRecord> logBuffer;
    std::vector<LogRecord> diskLog;

public:
    uint64_t appendLog(uint32_t txnId, RecordType type, uint32_t pageId,
                       const std::string& undo, const std::string& redo, uint64_t prevLsn) {
        uint64_t lsn = currentLsn++;
        LogRecord record{lsn, prevLsn, txnId, type, pageId, undo, redo, 0};
        logBuffer.push_back(record);
        return lsn;
    }

    void flushLog() {
        for (const auto& rec : logBuffer) {
            diskLog.push_back(rec);
            flushedLsn = rec.lsn;
        }
        logBuffer.clear();
    }

    bool canFlushPage(uint64_t pageLsn) const {
        // Enforces core WAL Invariant: pageLSN <= flushedLSN
        return pageLsn <= flushedLsn;
    }
};

Real-World Database Systems & Production Engines

1. PostgreSQL: Relies on WAL segments (`pg_wal`) and Checkpoints for point-in-time recovery (PITR) and physical streaming replication to standby nodes.
2. MySQL InnoDB: Implements the redo log (`ib_logfile`) combined with undo log segments to support Multi-Version Concurrency Control (MVCC) and doublewrite buffer crash recovery.
3. SQLite: Utilizes rollback journals or Write-Ahead Log (`.wal`) mode to provide atomic multi-statement transactions across mobile devices and embedded systems.
4. LSM-Tree Engines (RocksDB, LevelDB): Employs append-only WAL files on disk to guarantee durability for in-memory MemTable updates before writes are acknowledged to the client.