Day 3: Persist Data to Disk with a Write-Ahead Log — and Corrupt It

In Day 2, we built an in-memory key-value engine capable of handling concurrent client requests safely using synchronized memory structures. It was fast, but it had a fatal flaw: if you pulled the power cord on your machine, every byte of data vanished.

Today, we transition our engine from a volatile cache to a durable database. We will implement a Write-Ahead Log (WAL). By the end of this lesson, your engine will survive unexpected process crashes, rebuild its state on startup, and actively defend itself against disk corruption. In Day 4, we will build on this foundation by introducing idempotent operations to handle the duplicate client retries that inevitably occur after crash recoveries.

The Illusion of Durability

Many backend engineers believe that calling file.Write() in their language of choice guarantees their data is safe on disk. It does not.

When you write to a file, the operating system intercepts that data and stores it in an in-memory buffer called the page cache. The OS does this to avoid slow physical disk operations. If your application crashes, the OS will eventually flush this cache to disk, and your data is saved. But if the server loses power or the kernel panics while that data is still in the page cache, that data is gone forever.

To force the operating system to actually write the data to non-volatile physical storage, you must issue an fsync system call.

[Application Write] ---> [OS Page Cache] --(fsync)---> [Disk Controller Cache] ---> [Physical NAND/Platter]

Even then, hardware lies. Many consumer-grade Solid State Drives (SSDs) report that data has been safely written to disk as soon as it hits the drive’s internal volatile DRAM cache, ignoring the actual write to flash memory. Under power loss, these drives suffer from torn writes—where only a portion of a sector is written, leaving behind corrupted garbage.

To build a system that survives, we must assume:

1. 1.Every write is buffered and volatile until we explicitly call fsync.

2. 2.fsync is extremely expensive because it forces physical disk synchronization.

3. 3.The disk will eventually corrupt our files or write them partially.

The Write-Ahead Log (WAL) Pattern

The golden rule of database storage engines is simple: Never mutate the state of your database without first appending the operation to an append-only, durable log.

Instead of writing directly to a complex database file structure (which is slow and prone to corruption), we append every write operation (Set or Delete) to a simple, sequential log file. Because sequential writes are orders of magnitude faster than random database updates, we can afford to fsync this log on every transaction.

Once the log is safely flushed to disk, we update our fast in-memory map. If the system crashes, we can reconstruct the exact state of our database by reading the log from the beginning and replaying every operation in order. This process is called recovery.

The Anatomy of a WAL Record

To detect torn writes and disk corruption, we cannot rely on the file system. We must append a checksum to every record. We will design a binary record format:

+------------------+------------------+------------------+--------------------+----------------+--------------------+------------------+
| Length (4 bytes) |  CRC32 (4 bytes) |  Type (1 byte)   | KeyLen (4 bytes)   | Key (variable) | ValLen (4 bytes)   | Value (variable) |
+------------------+------------------+------------------+--------------------+----------------+--------------------+------------------+

• Length: The total size of the payload (Type + KeyLen + Key + ValLen + Value). This allows us to jump from record to record.

• CRC32: A cyclic redundancy check checksum calculated over the payload. If a single bit flips on disk, or if a write is cut short by a power failure, the calculated checksum will not match this value, signaling corruption.

• Type: Identifies the operation (e.g., 0x01 for Set, 0x02 for Delete).

Inline Placement Marker: Diagram 1 (Component Architecture) shows how the WAL sits between the Client and the Memory Map.

Real-World Anchor: PostgreSQL's "Fsyncgate"

In 2018, the PostgreSQL community discovered a terrifying behavior in how the Linux kernel handled fsync failures. When a database calls fsync and the underlying disk fails to write (perhaps due to a temporary hardware issue), the kernel marks those memory pages in the page cache as "clean" anyway and discards them.

When PostgreSQL retried the fsync, the kernel returned success because there were no more "dirty" pages to write. However, the data had never actually made it to physical disk! This silent data loss vulnerability, dubbed fsyncgate, forced database engineers worldwide to rethink how they handle system-level IO errors. It proved that you cannot blindly trust the operating system; you must verify your data's integrity yourself.

Trade-off Honesty: WAL vs. Shadow Paging

While Write-Ahead Logging is the standard for engines like InnoDB (MySQL) and RocksDB, it is not the only way to achieve durability.

An alternative is Shadow Paging (used by LMDB and CouchDB). Instead of appending to a log and modifying a memory map, shadow paging writes new data to unused pages on disk and then updates the page pointers atomically.

• Why choose WAL: WAL wins on write throughput. It turns random database writes into fast sequential appends.

• Why choose Shadow Paging: Shadow paging completely avoids the recovery phase on startup. Since the database files are always kept in a consistent state on disk, recovery is instantaneous. However, it suffers from high write amplification and fragmentation.

Capacity Math: The Cost of Fsync

Let's look at the raw physical limits of your laptop's storage.

If your SSD has an average write latency of 0.5 milliseconds, and you execute writes sequentially (one at a time, waiting for each to complete), your maximum synchronous write throughput is:

$$text{Throughput} = frac{1 text{ second}}{0.0005 text{ seconds}} = 2,000 text{ IOPS (Operations Per Second)}$$

This is a hard physical ceiling. No amount of Go optimization can bypass this limit if you call fsync on every single write. To scale beyond this, production systems use Group Committing (batching multiple concurrent writes into a single fsync call) or Asynchronous Logging (flushing the log every 10-100ms at the risk of losing the last few milliseconds of data on crash). Today, we will implement synchronous logging to guarantee absolute durability, but keep this performance ceiling in mind.

Inline Placement Marker: Diagram 2 (Flowchart) illustrates the synchronous write path and the durability boundary.

Core Implementation Insights

Below is how we implement the checksum-validated record writing in Go. Notice how we calculate the CRC32 checksum only over the payload bytes, and write both the length and checksum as fixed-size big-endian integers before the payload.

func (w *WAL) Write(recType RecordType, key, value string) error {
    keyBytes := []byte(key)
    valBytes := []byte(value)
    
    payloadLen := 1 + 4 + len(keyBytes) + 4 + len(valBytes)
    totalLen := 4 + 4 + payloadLen
    
    buf := make([]byte, totalLen)
    binary.BigEndian.PutUint32(buf[0:4], uint32(payloadLen))
    
    buf[8] = byte(recType)
    binary.BigEndian.PutUint32(buf[9:13], uint32(len(keyBytes)))
    copy(buf[13:13+len(keyBytes)], keyBytes)
    
    valOffset := 13 + len(keyBytes)
    binary.BigEndian.PutUint32(buf[valOffset:valOffset+4], uint32(len(valBytes)))
    copy(buf[valOffset+4:valOffset+4+len(valBytes)], valBytes)
    
    // Calculate CRC32 over the payload (everything after the length and checksum fields)
    checksum := crc32.ChecksumIEEE(buf[8:])
    binary.BigEndian.PutUint32(buf[4:8], checksum)
    
    if _, err := w.file.Write(buf); err != nil {
        return err
    }
    return w.file.Sync() // The critical fsync call
}

During recovery, we read the log sequentially. If we encounter a checksum mismatch, it indicates disk corruption or a torn write. Our engine will deliberately halt or truncate the log at the last known valid record to prevent corrupting our memory state.

Inline Placement Marker: Diagram 3 (State Machine) visualizes the recovery process and corruption transition states.

func (w *WAL) Recover() ([]WALRecord, error) {
    var records []WALRecord
    if _, err := w.file.Seek(0, io.SeekStart); err != nil {
        return nil, err
    }
    
    for {
        lenBuf := make([]byte, 4)
        _, err := io.ReadFull(w.file, lenBuf)
        if err == io.EOF || errors.Is(err, io.ErrUnexpectedEOF) {
            break // Clean end of file
        }
        
        payloadLen := binary.BigEndian.Uint32(lenBuf)
        checksumBuf := make([]byte, 4)
        if _, err := io.ReadFull(w.file, checksumBuf); err != nil {
            return records, ErrTornWrite // Record header cut short
        }
        expectedChecksum := binary.BigEndian.Uint32(checksumBuf)
        
        payload := make([]byte, payloadLen)
        if _, err := io.ReadFull(w.file, payload); err != nil {
            return records, ErrTornWrite // Record payload cut short
        }
        
        if crc32.ChecksumIEEE(payload) != expectedChecksum {
            return records, ErrCorruptRecord // Data corruption detected!
        }
        
        // Parse payload safely into WALRecord...
    }
    return records, nil
}

The Laptop vs. Production Gap

Our engine is now highly durable, but to run on a laptop inside a single process, we made a few trade-offs:

1. 1.Unlimited Log Growth: Our WAL grows indefinitely. In production systems (like RocksDB or Spanner), once the WAL reaches a certain size, the system writes an in-memory snapshot to disk (an SSTable or Checkpoint) and discards the old WAL records.

2. 2.Single-Threaded Disk Syncs: We fsync on every single write request. In a high-scale production system, this would bottleneck your performance to a few thousand requests per second. You would implement a lock-free ring buffer to gather concurrent writes and execute group commits.

Assignment: Implement Log Truncation on Corruption

When our engine detects a torn write (e.g., a crash occurred halfway through writing a record), it currently stops reading and returns the successfully recovered records. However, the corrupted "tail" remains in the file. If we append new records now, they will be written after the corruption, rendering the file unparseable.

Your assignment is to implement Active Log Truncation:

1. 1.Modify the recovery logic so that if ErrTornWrite is detected, the engine automatically truncates the WAL file to the byte offset of the last valid record.

2. 2.Verify that after truncation, the engine can successfully append new writes to the WAL and recover them on a subsequent restart.

Hints

• Keep track of the exact file offset before you read each record using w.file.Seek(0, io.SeekCurrent).

• Use w.file.Truncate(lastValidOffset) to discard the corrupted bytes at the end of the file.

• Remember to reset the file write pointer to the end of the truncated file before writing any new records using w.file.Seek(0, io.SeekEnd).

Solution Guide

To solve the assignment, update the Recover method in wal.go to track the file offset before each record read. If a torn write is encountered, truncate the file to that offset:

func (w *WAL) RecoverAndClean() ([]WALRecord, error) {
    var records []WALRecord
    var lastValidOffset int64 = 0
    
    if _, err := w.file.Seek(0, io.SeekStart); err != nil {
        return nil, err
    }
    
    for {
        currentOffset, err := w.file.Seek(0, io.SeekCurrent)
        if err != nil {
            return nil, err
        }
        
        lenBuf := make([]byte, 4)
        _, err = io.ReadFull(w.file, lenBuf)
        if err == io.EOF {
            break
        }
        if errors.Is(err, io.ErrUnexpectedEOF) {
            // Torn write at length boundary, truncate here
            _ = w.file.Truncate(currentOffset)
            break
        }
        
        payloadLen := binary.BigEndian.Uint32(lenBuf)
        checksumBuf := make([]byte, 4)
        if _, err := io.ReadFull(w.file, checksumBuf); err != nil {
            // Torn write at checksum, truncate
            _ = w.file.Truncate(currentOffset)
            break
        }
        
        payload := make([]byte, payloadLen)
        if _, err := io.ReadFull(w.file, payload); err != nil {
            // Torn write at payload, truncate
            _ = w.file.Truncate(currentOffset)
            break
        }
        
        expectedChecksum := binary.BigEndian.Uint32(checksumBuf)
        if crc32.ChecksumIEEE(payload) != expectedChecksum {
            // Corruption detected, truncate to keep only valid prefix
            _ = w.file.Truncate(currentOffset)
            break
        }
        
        // Parse payload and append to records...
        lastValidOffset = currentOffset + 8 + int64(payloadLen)
    }
    
    // Seek to the end of the file to prepare for future writes
    _, _ = w.file.Seek(lastValidOffset, io.SeekStart)
    return records, nil
}

This ensures your WAL remains perfectly structured and clean, even after surviving abrupt power cuts and system failures!