Write-Ahead Log (WAL)

Metadata

1. Overview

What problem does it solve?

When you execute an INSERT statement in a database like PostgreSQL, the database updates its in-memory data structures (like a B-Tree index). Updating a B-Tree is slow. It involves moving data around, splitting nodes, and rebalancing the tree.

If the database tried to write these complex B-Tree updates directly to the Hard Drive (Disk) for every single user request, it would be incredibly slow (Disk Random I/O is slow). Therefore, the database keeps the B-Tree in RAM (Memory) because RAM is 100,000x faster than Disk.

The Problem: What happens if you insert data, the DB updates RAM, returns "Success", and then the server loses power? RAM is volatile. The data is gone forever. You lost the Durability guarantee of ACID.

The Solution: The Write-Ahead Log (WAL). Before modifying the complex structures in RAM, the database takes the raw command (e.g., INSERT user 5) and immediately appends it to a simple, sequential text file on Disk (The WAL).

What breaks without it?

• Data Loss on Crash: Any data that was acknowledged as "Success" but hasn't yet been flushed from RAM to the permanent Disk files will be permanently lost if the server reboots.
• Corrupted Databases: If a database crashes in the middle of updating a complex B-Tree on disk, the B-Tree is corrupted.

2. Motivation

In the 1970s, database pioneers at IBM (System R) realized that disk heads take a long time to physically move (seek time). Writing data randomly across a disk is very slow (Random I/O). Writing data in one continuous, straight line is incredibly fast (Sequential I/O).

They invented the WAL so that every write could be instantly saved to disk via Sequential I/O (fast), while the actual database data files could be updated lazily in the background later (asynchronously).

3. Real-World Usage

4. Prerequisites

5. Visual Explanation

The Write Path

%%{init: {'theme': 'base', 'themeVariables': { 'primaryColor': '#ffcc00', 'edgeLabelBackground':'#ffffff'}}}%%
graph TD
    classDef client fill:#f9f9f9,stroke:#333,stroke-width:2px;
    classDef ram fill:#cce5ff,stroke:#007bff,stroke-width:2px;
    classDef disk fill:#d4edda,stroke:#28a745,stroke-width:2px;
    classDef process fill:#f8d7da,stroke:#dc3545,stroke-width:2px;

    C[Client]:::client --> |"1. INSERT (x=5)"| DB[Database Engine]
    
    DB --> |"2. Append 'INSERT x=5'"| WAL[(Write-Ahead Log<br/>Disk - FAST Sequential)]:::disk
    
    WAL -.-> |"3. fsync (Force to physical disk)"| WAL
    
    WAL --> |"4. Update Memory"| Mem[B-Tree Buffer<br/>RAM - FAST]:::ram
    
    Mem --> |"5. Return OK"| C
    
    Mem -.-> |"6. Background Flush<br/>(Every 5 mins)"| DataFiles[(Data Files<br/>Disk - SLOW Random)]:::disk
    
    style DB fill:#fff,stroke:#333,stroke-width:0px

Crash Recovery

If the server loses power at Step 5, the Data Files were never updated. When the server boots back up:

1. It reads the Data Files into RAM (missing x=5).
2. It opens the WAL.
3. It replays the WAL from the last checkpoint, executing INSERT x=5.
4. The RAM is now perfectly restored to the state it was in right before the crash.

6. Internal Working

The Magic of fsync

When you tell an operating system to write a file (fwrite), the OS doesn't actually write it to the physical hard drive immediately. It puts it in the "OS Page Cache" (RAM) to optimize disk I/O. If the server loses power, the OS Page Cache is lost, and your WAL entry is lost!

Databases must explicitly call a system function called fsync(). fsync blocks the program and forces the OS and the Hard Drive hardware controller to physically write the bits to the magnetic platter or SSD chips. The database cannot return "Success" to the user until fsync completes.

Group Commit

fsync is slow (a few milliseconds on an SSD). If you have 1,000 users inserting data per second, and you fsync for every single one, your database will bottleneck. Group Commit solves this. The database holds 100 user transactions in memory for a few milliseconds, writes them to the WAL together, and issues a single fsync command for all 100 transactions at once.

7. Implementation

Why C? High-level languages hide file I/O buffering. To truly understand a WAL, you must understand the difference between writing to a file buffer, flushing to the OS, and fsyncing to physical hardware. C exposes this perfectly.

/*
038 - Write-Ahead Log (WAL)
A C implementation demonstrating how a database guarantees durability
using an append-only log and fsync().
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <fcntl.h>

// Mock in-memory database (B-Tree)
int memory_database = 0;

// The WAL file descriptor
int wal_fd;

void init_database() {
    // Open the WAL file in APPEND mode. Create if it doesn't exist.
    // O_APPEND guarantees all writes go to the absolute end of the file.
    wal_fd = open("database.wal", O_WRONLY | O_CREAT | O_APPEND, 0644);
    if (wal_fd < 0) {
        perror("Failed to open WAL");
        exit(1);
    }
}

void recover_from_wal() {
    printf("--- CRASH RECOVERY INITIATED ---\n");
    FILE *f = fopen("database.wal", "r");
    if (!f) return;

    char line[256];
    int operations_replayed = 0;
    
    // Read the log sequentially and replay the operations
    while (fgets(line, sizeof(line), f)) {
        if (strncmp(line, "ADD ", 4) == 0) {
            int value = atoi(line + 4);
            memory_database += value;
            operations_replayed++;
        }
    }
    fclose(f);
    printf("Replayed %d operations from WAL.\n", operations_replayed);
    printf("Recovered Database State: %d\n\n", memory_database);
}

void execute_transaction(int value) {
    printf("Client: Add %d to database.\n", value);
    
    // 1. Format the WAL Entry
    char log_entry[256];
    snprintf(log_entry, sizeof(log_entry), "ADD %d\n", value);
    
    // 2. Write to WAL (This goes to the OS Page Cache in RAM)
    write(wal_fd, log_entry, strlen(log_entry));
    
    // 3. FSYNC: Force the OS to write physically to the SSD/HDD.
    // This blocks until the hardware confirms the data is saved.
    // If the power goes out after this line, the data is safe.
    fsync(wal_fd);
    printf("  [WAL] Synced to disk: %s", log_entry);
    
    // 4. Update the actual in-memory database (FAST)
    memory_database += value;
    printf("  [RAM] Memory updated. Current state: %d\n", memory_database);
    
    // 5. Return Success to client
    printf("  [API] Returning 200 OK to client.\n\n");
}

// ── Test Harness ──

int main(int argc, char *argv[]) {
    // Simulate booting up
    recover_from_wal();
    init_database();

    if (argc > 1 && strcmp(argv[1], "crash") == 0) {
        // We were just testing recovery. Exit immediately.
        close(wal_fd);
        return 0;
    }

    // Accept new transactions
    execute_transaction(50);
    execute_transaction(100);
    
    printf("🔥 SIMULATING SUDDEN POWER LOSS 🔥\n");
    printf("The RAM (Current state: %d) is wiped clean!\n", memory_database);
    
    // We intentionally DO NOT save the memory_database to disk before exiting.
    close(wal_fd);
    
    printf("\nRun the program again to see the WAL recover the lost data.\n");
    return 0;
}

Sample Output

Run 1:

--- CRASH RECOVERY INITIATED ---\
Replayed 0 operations from WAL.
Recovered Database State: 0

Client: Add 50 to database.
  [WAL] Synced to disk: ADD 50
  [RAM] Memory updated. Current state: 50
  [API] Returning 200 OK to client.

Client: Add 100 to database.
  [WAL] Synced to disk: ADD 100
  [RAM] Memory updated. Current state: 150
  [API] Returning 200 OK to client.

🔥 SIMULATING SUDDEN POWER LOSS 🔥
The RAM (Current state: 150) is wiped clean!
Run the program again to see the WAL recover the lost data.

Run 2 (Reboot after crash):

--- CRASH RECOVERY INITIATED ---
Replayed 2 operations from WAL.
Recovered Database State: 150

Notice how Run 2 perfectly restored the RAM to 150 without us ever saving the actual "database" to disk, entirely by replaying the log.

8. Complexity

9. Trade-offs

10. Production Evolution

11. Common Bugs

12. Interview Questions

1. What is a Write-Ahead Log (WAL) and why do databases use them? Hint: An append-only file used to record transactions before they are applied to the main database. Used to guarantee durability (Crash Recovery) while providing fast write performance via Sequential I/O.

2. What is the difference between Sequential I/O and Random I/O? Hint: Sequential writes data in a straight line (extremely fast for HDDs, very fast for SSDs). Random writes data all over the disk (slow). WALs use Sequential. B-Trees use Random.

3. What is the role of fsync()? Hint: It flushes the OS file buffers to the physical hardware disk. Without it, data is vulnerable to OS crashes or power failures.

4. How do databases prevent the WAL from growing infinitely large? Hint: Checkpointing. The DB flushes its RAM to the permanent data files. Once confirmed, it deletes the WAL entries older than the checkpoint.

13. Used By (Downstream Blocks)

• 039 SSTable & LSM Tree — LSM trees (used by Cassandra) are built almost entirely on the concept of Append-Only Logs combined with in-memory buffers.

14. Used In (Case Studies)

15. Related Blocks

16. Try It Yourself

Exercise 1: Implement Checkpoints

Modify the C code. Add a checkpoint() function that writes the current memory_database value to a new file called database.data. Once written, truncate/delete the database.wal file. Modify the startup routine to read database.data first, then replay whatever small amount is left in the WAL.

Exercise 2: Group Commit

Modify the C code so that execute_transaction doesn't call fsync. Instead, create a commit_batch() function. Call execute_transaction 10 times in a loop, then call commit_batch() to fsync all 10 entries at once.

Website Metadata