Day 2: Persist the Key-Value Store with a Write-Ahead Log — and Fake the Disk

Day 2: Persist the Key-Value Store with a Write-Ahead Log — and Fake the Disk

In Day 1, we designed and shipped a high-performance, in-memory key-value store. It was fast, elegant, and thoroughly unit-tested. But it possessed a fatal flaw common to all purely memory-backed systems: a single power outage, kernel panic, or process termination wipes out every byte of data.

To build a resilient distributed system, we must make our data survive crashes. Today, we will introduce durability to our engine using a Write-Ahead Log (WAL) while maintaining clean, fast, and deterministic test suites by faking the underlying storage layer.

The Continuity Contract

• Where we started: In Day 1, we built an in-memory key-value store using Test-Driven Development (TDD). It exposed a clean API (Get, Set, Delete) but kept all state in volatile RAM.

• Where we are going: Today, we will wrap that memory store with a Write-Ahead Log. Every write will be appended to a sequential log on disk and flushed to physical media before we acknowledge success to the client. To test this without destroying our laptops' SSDs or introducing flaky, slow I/O tests, we will design and swap in a simulated disk layer.

• Where this leads: In Day 3, we will use this durable foundation to explore the TDD cycle further, refactoring our storage engine to handle log compaction and garbage collection without breaking our durability guarantees.

The Production Stakes: The Fsyncgate Outage

In 2018, the PostgreSQL community was rocked by a revelation regarding how modern operating systems handle the fsync system call. For decades, database engines assumed that if a write to a file failed (for instance, due to a transient disk error or a bad block), calling fsync again later would retry flushing that dirty data to physical media.

Instead, developers discovered that on many versions of Linux, when a buffered writeback fails in the background, the kernel marks the page as clean and throws away the modified data. A subsequent call to fsync would return success, even though the data was lost forever. This behavior led to silent data corruption in production deployments worldwide.

To defend against such catastrophic failures, production storage engines like RocksDB, SQLite, and Spanner must be extremely deliberate about how they write to disk. They cannot simply trust the operating system's default buffering. They must:

1. 1.Write updates sequentially to an append-only log.

2. 2.Explicitly force physical disk synchronization (fsync).

3. 3.Handle I/O errors immediately, crash-aborting if durability guarantees cannot be met to avoid serving corrupted state.

Component Architecture

To safely transition from an in-memory store to a durable database, we introduce three core components:

+--------------------------------------------------------+
|                      DB Engine                         |
|  (Coordinates writes to WAL and reads from MemTable)  |
+--------------------------------------------------------+
        |                                        |
        v (Append Entry)                         v (Read/Write)
+-------------------+                    +---------------+
|  Write-Ahead Log  |                    |   MemTable    |
|   (WAL Parser)    |                    |  (In-Memory)  |
+-------------------+                    +---------------+
        |
        v (I/O Operations)
+--------------------------------------------------------+
|                    Disk Interface                      |
|  (Abstracts file system operations for testability)    |
+--------------------------------------------------------+
   /                                                
  v (Real OS Calls)                                  v (In-Memory Simulation)
+-------------------+                            +-------------------+
|   Physical Disk   |                            |     MemDisk       |
| (os.File / fsync) |                            | (Injected Errors) |
+-------------------+                            +-------------------+

1. The Disk Interface

Instead of calling the operating system's file APIs directly, we decouple I/O operations behind a clean interface. This interface defines sequential appending, reading at arbitrary offsets, and explicit synchronization.

2. The Write-Ahead Log (WAL)

The WAL is an append-only file containing a sequence of binary frames. Each frame represents a state-mutating operation (Set or Delete). Because appending to a file is a sequential operation, it is highly efficient, avoiding the random-access seek overhead of updating a complex index on disk.

3. The MemTable

The MemTable is our volatile, in-memory index (the key-value map from Day 1). It acts as a read cache. When the database boots, it replays the WAL from start to finish, reconstructing the MemTable state.

Core Concepts: Why Append-Only?

Why write to a sequential log instead of updating the database file directly?

Consider the mechanics of a modern SSD or a traditional spinning disk. Modifying a random byte in the middle of a 10 GB file requires the operating system to locate the correct block, read it into memory, modify the byte, and write the entire block back to storage. Under high write loads, this causes massive write amplification and disk head movement (or flash block wear), degrading throughput.

An append-only log bypasses this. Writes always target the end of the file. This allows us to group writes, utilize sequential disk bandwidth, and achieve predictable latencies.

The Durability Math

Let's look at the capacity math of synchronous disk writes.

A standard consumer NVMe SSD might claim 100,000 random write IOPS. However, when you invoke fsync, the drive must flush its volatile onboard controller cache to non-volatile flash cells. This physical process is constrained by the speed of the flash controller and the physical bus latency.

• Unbuffered Write (Buffered by OS): Latency $approx 10,mutext{s}$ to $100,mutext{s}$. Throughput is extremely high, but a power loss destroys any unwritten data in the OS page cache.

• Synchronous Write (fsync): Latency $approx 1,text{ms}$ to $5,text{ms}$ depending on hardware. This limits a single-threaded writer to a maximum of:

  $$text{Throughput} = frac{1}{0.001,text{s}} = 1,000text{ writes/second}$$
  

To scale beyond this limit in production, systems use group committing (batching multiple concurrent transactions into a single fsync call). For our single-node engine, we will focus on making individual synchronous writes perfectly safe.

Implementation Intuition

Let's look at the key abstractions that make our system testable and resilient.

The Disk Abstraction

To test crash recovery and write failures without writing slower integration tests, we define a Disk interface:

type Disk interface {
    Append(data []byte) (offset int64, err error)
    ReadAt(b []byte, off int64) (n int, err error)
    Sync() error
    Size() int64
    Close() error
}

By implementing this interface with a memory-backed structure (MemDisk), we can simulate disk-full conditions, block corruption, and fsync failures in our unit tests.

Binary Frame Layout

To prevent partial writes from corrupting our database during a crash, we write data in structured binary frames:

+------------------+-----------------+-------------------+-------------------+-------------------+-------------------+
|  Length (4B)     |  Op Type (1B)   |  Key Length (4B)  |  Key (Variable)   |  Val Length (4B)  |  Value (Variable) |
+------------------+-----------------+-------------------+-------------------+-------------------+-------------------+

Each frame starts with its total length, making it easy to parse and validate during recovery.

func EncodeFrame(op byte, key, value []byte) []byte {
    kl, vl := len(key), len(value)
    buf := make([]byte, 4+1+4+kl+4+vl)
    
    binary.BigEndian.PutUint32(buf[0:4], uint32(len(buf)))
    buf[4] = op
    binary.BigEndian.PutUint32(buf[5:9], uint32(kl))
    copy(buf[9:9+kl], key)
    binary.BigEndian.PutUint32(buf[9+kl:13+kl], uint32(vl))
    copy(buf[13+kl:], value)
    
    return buf
}

The Recovery Loop

On startup, the engine opens the WAL and reads frames sequentially. If a frame is incomplete or corrupted (e.g., due to a crash mid-write), the engine truncates the log to the last valid frame, guaranteeing a consistent state.

func (db *DB) Recover() error {
    offset := int64(0)
    size := db.disk.Size()
    
    for offset < size {
        // Read length prefix
        lenBuf := make([]byte, 4)
        if _, err := db.disk.ReadAt(lenBuf, offset); err != nil {
            break // EOF or partial write
        }
        length := binary.BigEndian.Uint32(lenBuf)
        
        // Read full frame
        frameBuf := make([]byte, length)
        if _, err := db.disk.ReadAt(frameBuf, offset); err != nil {
            // Unfinished write detected, truncate to last valid offset
            return db.disk.Truncate(offset)
        }
        
        // Apply to MemTable
        db.applyFrame(frameBuf)
        offset += int64(length)
    }
    return nil
}

Trade-off Honesty: Append-Only vs. In-Place Updates

We choose the Append-Only Log because it is the foundational pattern for modern high-performance databases (including Bigtable, Cassandra, and RocksDB). The space inefficiency is addressed in production systems via a background process called Compaction, which we will implement in a later lesson.

Designing the Failure Demo

To prove the resilience of our implementation, we will simulate a system crash using our custom MemDisk.

We will:

1. 1.Write several key-value pairs to the database.

2. 2.Enable "Fault Injection Mode" on our simulated disk to make all subsequent disk writes fail.

3. 3.Attempt to write a new key. The write must fail, and the in-memory index must remain unchanged.

4. 4.Simulate a hard crash (discarding the volatile memory state).

5. 5.Re-initialize the database using the same simulated disk.

6. 6.Verify that all keys written before the fault injection are successfully recovered, while the failed write is absent and has left no corrupt remnants in the log.

Assignment: Add Integrity Validation via CRC Checksums

Real disks do not just fail by refusing to write; they fail by silently corrupting blocks due to electromagnetic interference, firmware bugs, or fading flash cells.

Your Task

Modify the WAL frame format to include a 4-byte CRC32 checksum of the payload. During recovery, recalculate the checksum for each frame. If a checksum mismatch is detected, halt recovery and return a clear error indicating data corruption.

Success Criteria

1. 1.The frame format must append a 4-byte CRC32 IEEE checksum at the end of the byte array.

2. 2.Your test suite must include a test where a single byte of a valid WAL file is corrupted, and the database successfully rejects the corrupted frame during startup.

Hints

• Use Go's built-in hash/crc32 package.

• Compute the checksum over the operation type, key, and value fields combined.

• When writing tests, write a valid entry to a MemDisk, manually flip a bit at a known offset in the memory buffer, and attempt to initialize a new DB instance with that disk.

Solution Walkthrough

To complete the assignment, you will need to:

1. 1.Update the Encoder:

   goCopy

   import "hash/crc32"
   
   func EncodeFrameWithChecksum(op byte, key, value []byte) []byte {
       // Calculate payload sizes
       kl, vl := len(key), len(value)
       payloadSize := 1 + 4 + kl + 4 + vl
       totalSize := 4 + payloadSize + 4 // Length (4B) + Payload + CRC (4B)
       
       buf := make([]byte, totalSize)
       binary.BigEndian.PutUint32(buf[0:4], uint32(totalSize))
       buf[4] = op
       binary.BigEndian.PutUint32(buf[5:9], uint32(kl))
       copy(buf[9:9+kl], key)
       binary.BigEndian.PutUint32(buf[9+kl:13+kl], uint32(vl))
       copy(buf[13+kl:], value)
       
       // Calculate CRC32 of the payload (from byte 4 to end of payload)
       checksum := crc32.ChecksumIEEE(buf[4 : totalSize-4])
       binary.BigEndian.PutUint32(buf[totalSize-4:], checksum)
       
       return buf
   }
   

2. 2.Verify during Recovery:

   When reading the frame, read the CRC bytes from the end of the frame buffer. Calculate the checksum of the payload bytes, and compare them. If they do not match, return ErrCorruptFrame.
   

Now, let's proceed to the execution scripts and the implementation guide to build and run this engine on your laptop.