Building a Distributed Key-Value Cache part 5/6: WAL and durability

Implementing crash safety with a write-ahead log, checkpointing, and atomic file operations.

This post follows part 4 of the series, in which I focus on fault tolerance through replication and leader election, and is followed by part 6 of the series.

All of the cache data currently exists in memory. If a node crashes, or even restarts gracefully, every key-value pair it held vanishes. Replication helps (another node has a copy), but relying solely on the network for durability feels like trusting your roommate to remember your Wi-Fi password.

Pull out your pen and paper, because it's time to write things down.

Decision 1: WAL vs. full write-on-every-mutation

The first question is how to persist. Two obvious approaches:

Option A — Write the full state on every mutation:

func (c *Cache) Create(key, value string) (bool, error) {
    c.mu.Lock()
    defer c.mu.Unlock()
    // ... insert into map ...
    return true, c.saveEntireStateToDisk() // serialize everything
}

This is simple but slow. If the cache holds 100,000 entries and someone writes one key, we'd serialize and flush all 100,000 entries. That's O(n) disk I/O per operation.

Option B — Append only the delta (write-ahead log):

func (c *Cache) Create(key, value string) (bool, error) {
    c.mu.Lock()
    defer c.mu.Unlock()
    if err := c.append(walRecord{Operation: walPut, Key: key, Value: value}); err != nil {
        return false, err
    }
    c.put(key, value)
    return true, c.checkpoint()
}

A write-ahead log appends a tiny record describing the operation before mutating in-memory state. Recovery replays the log. Each write is O(1) in terms of data size, just one JSON line no matter how large the cache is.

Decision: WAL. The append-only pattern gives us durability without tanking throughput. The tradeoff is that ressurecting the cache must take a bit of time to replay the log, but that's a cold-start cost we pay once.

Decision 2: Log format — binary vs. JSON lines

A WAL record can be encoded in many ways: Protocol Buffers, MessagePack, length-prefixed binary, or plain text. I chose newline-delimited JSON (JSONL):

type walRecord struct {
    Operation walOperation `json:"operation"`
    Key       string       `json:"key"`
    Value     string       `json:"value,omitempty"`
}

A binary format would be more compact and faster to parse. But JSON has a juicy advantage for a learning project: I can cat wal.jsonl and immediately see what happened. Let's assume our example from a couple blog posts ago in the series, where each cache entry is a blog post of mine. The log file can look like:

{"operation":"put","key":"my-embarassing-first-post","value":"{\"author\":\"Rohan\",\"date\":\"2026-07-14\"}"}
{"operation":"put","key":"cool-cache-deep-dive","value":"{\"author\":\"Rohan\",\"date\":\"2026-08-06\"}"}
{"operation":"delete","key":"my-embarassing-first-post"}

Tradeoff: ~2–3x larger on disk vs. binary, slightly slower to parse. Acceptable for a cache where entries are typically small strings and the log gets checkpointed periodically anyway.

Decision 3: `fsync` on every append

When you call file.Write() in Go (or most languages), the data doesn't necessarily hit the physical disk immediately. The operating system buffers it in memory — a kernel page cache — and flushes it to disk later, when it feels like it. This is fast, but if the machine loses power before that flush, the data is gone. file.Sync() (which calls the fsync syscall under the hood) forces the OS to flush all buffered data for that file to the actual storage device instantly, and blocks until the hardware confirms the write.

After writing a record, we immediately call file.Sync():

func (w *writeAheadLog) Append(record walRecord) error {
    w.mu.Lock()
    defer w.mu.Unlock()

    encoded, err := json.Marshal(record)
    if err != nil {
        return fmt.Errorf("encode write-ahead log record: %w", err)
    }
    if _, err := w.file.Write(append(encoded, '\n')); err != nil {
        return fmt.Errorf("append write-ahead log record: %w", err)
    }
    if err := w.file.Sync(); err != nil {
        return fmt.Errorf("sync write-ahead log: %w", err)
    }
    w.pending++
    return nil
}

The alternative is batching — buffer several records and sync periodically. That's faster (fewer syscalls,a dn) but introduces a durability window: if the process dies between writes and the next sync, those records are lost.

This is about durability versus performance.

Decision: Sync every record. This cache prioritizes correctness over raw throughput. A single fsync per mutation adds maybe 1–5ms of latency on spinning disk (much less on SSD), which is acceptable for our use case (I really don't write and edit my blog posts that often, sorry!). If we needed higher throughput (like if I hired a million ghost writers), we'd batch syncs and accept a small data-loss window.

Decision 4: Checkpointing to bound recovery time

By default, the WAL grows forever. On restart, we could end up replaying millions of records. The fix is periodic compaction: snapshot the full state, then truncate the log.

const defaultCheckpointEvery = 1_000

func (c *Cache) checkpoint() error {
    if c.wal == nil || !c.wal.ShouldCheckpoint() {
        return nil
    }
    entries := make([]snapshotEntry, 0, c.recent.Len())
    for element := c.recent.Back(); element != nil; element = element.Prev() {
        entry := element.Value.(cacheEntry)
        entries = append(entries, snapshotEntry{Key: entry.key, Value: entry.value})
    }
    return c.wal.Checkpoint(entries)
}

Every 1,000 mutations (the default), we write a full snapshot and reset the WAL. Recovery then loads the snapshot (one read) plus at most 999 subsequent WAL records. The default can be overridden with the CACHE_CHECKPOINT_EVERY environment variable.

Tradeoff: A lower interval means faster recovery but more frequent full-state writes. A higher interval means less I/O but slower restarts. 1,000 is a reasonable default — it bounds recovery replay to under a millisecond on most hardware while keeping checkpoint overhead infrequent.

Thinking more deeply about it, snapshot writes are dangerous. If the process crashes mid-write, the snapshot file is corrupted and the old WAL is already gone. The solution is the write-to-temporary-then-rename pattern:

func (w *writeAheadLog) Checkpoint(entries []snapshotEntry) error {
    w.mu.Lock()
    defer w.mu.Unlock()

    path := filepath.Join(w.dir, "snapshot.json")
    temporary := path + ".tmp"

    encoded, err := json.Marshal(entries)
    if err != nil {
        return fmt.Errorf("encode cache snapshot: %w", err)
    }
    file, err := os.OpenFile(temporary, os.O_CREATE|os.O_TRUNC|os.O_WRONLY, 0o600)
    if err != nil {
        return fmt.Errorf("open temporary cache snapshot: %w", err)
    }
    if _, err := file.Write(encoded); err != nil {
        file.Close()
        return fmt.Errorf("write cache snapshot: %w", err)
    }
    if err := file.Sync(); err != nil {
        file.Close()
        return fmt.Errorf("sync cache snapshot: %w", err)
    }
    if err := file.Close(); err != nil {
        return fmt.Errorf("close cache snapshot: %w", err)
    }
    if err := os.Rename(temporary, path); err != nil {
        return fmt.Errorf("publish cache snapshot: %w", err)
    }
    // ...truncate WAL...
}

os.Rename is atomic. Either the new snapshot fully replaces the old one, or it doesn't. There's no half-written state. The sequence is: write to .tmp → sync → rename → then truncate the WAL. If we crash at any point before the rename, the old snapshot + full WAL is still consistent.

Decision 5: Returning errors from mutations

Before the WAL, Create, Update, and Delete returned a simple bool. Now they return (bool, error):

func (c *Cache) Create(key, value string) (bool, error) {
    c.mu.Lock()
    defer c.mu.Unlock()

    if _, exists := c.items[key]; exists {
        return false, nil
    }
    if err := c.append(walRecord{Operation: walPut, Key: key, Value: value}); err != nil {
        return false, err
    }
    c.put(key, value)
    return true, c.checkpoint()
}

The alternative would be to log the error internally and proceed (best-effort durability). But that's dishonest — the caller thinks the write succeeded durably when it didn't. If the WAL fails, the HTTP handler returns 500:

created, err := cache.Create(key, req.Value)
if err != nil {
    http.Error(w, "cache persistence failure", http.StatusInternalServerError)
    return
}

Decision: Fail clearly. A cache that silently drops durability guarantees is worse than one that admits failure. The client can retry or fall back to another node.

Decision 6: How the WAL interacts with replication

In part 4, we added replication: the leader forwards writes to replica nodes. Now that each node has a WAL, an important question arises — does each node maintain its own WAL, or do they share one?

Consider each node having its own independent WAL. When the leader replicates a write to a follower, the follower receives it as an HTTP request and calls cache.Create() just like any other write. That call appends to the follower's own WAL on the follower's own disk. No node reads another node's WAL. The per-node data directories from Decision 7 (data/node-01/, data/node-02/) reinforce this — each node's durability is self-contained.

How does ordering work? In our implementation, the flow is:

Leader receives client write
Leader appends to its own WAL and mutates its in-memory cache
Leader responds to the client
Leader forwards the write to replicas (who each append to their own WALs)

The write is durable on the leader before replication happens. If the leader crashes after step 2 but before step 4, the data exists on the leader's disk but not on any replica. When the leader recovers, it replays its WAL and the data is back — but during the outage, replicas wouldn't have had it.

The alternative is to wait for at least one replica to confirm before responding to the client (synchronous replication). That's safer but slower — every write now requires a network round trip to a replica before the client gets a response. For this project, the local-first approach is acceptable: replication provides availability during leader failures, and the WAL provides durability for the leader itself.

An extension of this project could combine the best of both functionalities; what I chose, and what I didn't. We do this by implementing both, picking one as default, then letting the client choose! One real-world example is the WAIT command in Redis, a command the client can issue after a write to block until N replicas have acknowledged receiving it. This lets the client decide whether the durability is worth the delay, based on their specific circumstance.

Decision 7: Per-node data directories in a cluster

In a cluster, multiple nodes might run on the same machine (for development/testing). If they all write to the same data/ directory, their WALs collide. The fix:

config.dataDir = filepath.Join(config.dataDir, config.nodeID)

Each node gets its own subdirectory: data/node-01/, data/node-02/, etc.

Summary

The write-ahead log specifically accomplishes durability, bounded recovery, and crash safety. It comes with small impact to write speed by requiring disk writes, but still maintains O(1) writes.

The cache can now die then come alive again with all its data intact. Magical!