Write-Ahead Log

Role in the engine

Every write is appended to the log before it is inserted into the memtable. If the process or machine crashes, the memtable is gone, but reopening the database replays the log and rebuilds it. Once a memtable has been flushed to an SSTable, its log file is deleted. The general theory is in WAL; this page builds the concrete pieces in Go: the Batch format, the log record format, the writer, the reader, and group commit.

Batch: the unit of atomicity

A Batch collects puts and deletes that must be applied atomically — all or none survive a crash. A single Put is a batch of one. The batch is serialized into one byte string, and that string is what the log stores:

+----------------+-------------+-----------------------------------+
| sequence (8 B) | count (4 B) | records...                        |
+----------------+-------------+-----------------------------------+
record := 0x01 uvarint(len(key)) key uvarint(len(value)) value   (put)
        | 0x00 uvarint(len(key)) key                             (delete)

type Batch struct{ rep []byte }

func (b *Batch) Put(key, val []byte) {
    b.init() // 12-byte header on first use
    b.setCount(b.Count() + 1)
    b.rep = append(b.rep, byte(TypeValue))
    b.rep = appendBytes(b.rep, key)
    b.rep = appendBytes(b.rep, val)
}

func appendBytes(dst, b []byte) []byte {
    dst = binary.AppendUvarint(dst, uint64(len(b)))
    return append(dst, b...)
}

Entry i of a batch with base sequence s gets sequence s + i. Iterate decodes the records with bounds-checked reads and returns ErrCorrupt if the bytes are malformed or the number of records does not match the count — a batch read back from disk is untrusted input:

func readBytes(p []byte) (b, rest []byte, ok bool) {
    n, w := binary.Uvarint(p)
    if w <= 0 || uint64(len(p)-w) < n { // varint invalid, or length beyond the buffer
        return nil, nil, false
    }
    p = p[w:]
    return p[:n:n], p[n:], true // full slice expression: callers can't append into p
}

The log file format

The log does not know about batches; it stores opaque records and guarantees each is read back exactly or detected as damaged. The format is LevelDB's, and worth copying:

  • The file is divided into 32 KB blocks.
  • A record is written as one or more fragments, each with a 7-byte header, so records can span blocks:
fragment := crc32c (4 B) | length (2 B) | type (1 B) | data (length B)
type     := FULL | FIRST | MIDDLE | LAST
  • If fewer than 7 bytes remain in a block, they are zero-filled and the next fragment starts in the next block.
  • The CRC covers the type byte and the data.

Why blocks? A reader that hits a corrupted fragment can resynchronize at the next 32 KB boundary instead of losing the rest of the file, and a torn write can only damage the final block's tail.

The writer

const (
    blockSize  = 32 << 10
    headerSize = 7
)

type LogWriter struct {
    w           io.Writer
    blockOffset int
    buf         []byte
}

func (lw *LogWriter) AddRecord(rec []byte) error {
    lw.buf = lw.buf[:0]
    first := true
    for {
        left := blockSize - lw.blockOffset
        if left < headerSize { // no room for a header: pad the block
            lw.buf = append(lw.buf, make([]byte, left)...)
            lw.blockOffset, left = 0, blockSize
        }
        frag := min(len(rec), left-headerSize)
        last := frag == len(rec)
        var t recType
        switch {
        case first && last:
            t = recFull
        case first:
            t = recFirst
        case last:
            t = recLast
        default:
            t = recMiddle
        }
        lw.buf = appendFragment(lw.buf, t, rec[:frag])
        lw.blockOffset += headerSize + frag
        rec, first = rec[frag:], false
        if last {
            break
        }
    }
    _, err := lw.w.Write(lw.buf) // one write syscall per record
    return err
}

func appendFragment(dst []byte, t recType, data []byte) []byte {
    var h [headerSize]byte
    c := crc32.Update(0, castagnoli, []byte{byte(t)})
    c = crc32.Update(c, castagnoli, data)
    binary.LittleEndian.PutUint32(h[0:], c)
    binary.LittleEndian.PutUint16(h[4:], uint16(len(data)))
    h[6] = byte(t)
    dst = append(dst, h[:]...)
    return append(dst, data...)
}

castagnoli is crc32.MakeTable(crc32.Castagnoli): CRC32-C has hardware instructions on both amd64 (SSE4.2) and arm64, and Go's hash/crc32 uses them, so checksumming runs at many GB/s. The whole record is assembled in a reused buffer and written with one Write, so a record is never interleaved with another and costs one syscall.

The reader: torn writes vs. corruption

The reader must classify every way a log can end:

Situation Meaning Reader returns
Clean end of file after a complete record Normal io.EOF
File ends in the middle of a fragment or record The last write was torn by a crash; it was never acknowledged ErrTornWrite
Checksum mismatch, impossible length, bad fragment sequence The file was damaged ErrCorrupt 
func (lr *LogReader) Next() ([]byte, error) {
    var rec []byte
    inRecord := false
    for {
        if len(lr.block) < headerSize {
            if lr.eof {
                if inRecord || len(lr.block) > 0 {
                    return nil, ErrTornWrite
                }
                return nil, io.EOF
            }
            // ... read the next 32 KB block (short read → lr.eof = true)
            continue
        }
        h := lr.block[:headerSize]
        length := int(binary.LittleEndian.Uint16(h[4:]))
        t := recType(h[6])
        if t == 0 && length == 0 { // zero padding at the end of a block
            lr.block = nil
            continue
        }
        if headerSize+length > len(lr.block) {
            if lr.eof {
                return nil, ErrTornWrite // fragment cut off by end of file
            }
            return nil, ErrCorrupt // a length that can't fit in a block
        }
        data := lr.block[headerSize : headerSize+length]
        want := binary.LittleEndian.Uint32(h[0:])
        if crc32.Update(crc32.Update(0, castagnoli, h[6:7]), castagnoli, data) != want {
            return nil, ErrCorrupt
        }
        lr.block = lr.block[headerSize+length:]
        switch t {
        case recFull:
            return append([]byte(nil), data...), nil
        case recFirst:
            rec, inRecord = append(rec[:0], data...), true
        case recMiddle:
            rec = append(rec, data...)
        case recLast:
            return append(rec, data...), nil
        }
        // (fragment-sequence validation omitted here; it returns ErrCorrupt)
    }
}

Recovery treats ErrTornWrite at the end of the last log as the normal result of a crash — stop replaying, the torn record was never acknowledged to its writer — and ErrCorrupt as a real error that fails Open. A production engine offers recovery modes (LevelDB's paranoid_checks, RocksDB's WALRecoveryMode) to choose between failing, skipping corrupted records, or truncating at the first error. The tests write records of sizes 0, 1, 100, exactly one block, and several blocks, then truncate the file and flip a bit to check each classification.

Group commit

fsync is expensive (Files and Durability in Go measured 4.4 ms per f.Sync() on this laptop). If each writer synced its own record, the engine would be limited to ~220 durable writes per second regardless of core count. Group commit lets writers that arrive while a commit is in progress share the next one:

func (db *DB) commitLoop() {
    defer db.wg.Done()
    var group []*writeReq
    var merged Batch
    for {
        select {
        case w := <-db.writes: // block until at least one writer
            group = append(group[:0], w)
        case <-db.closed:
            return
        }
    drain: // take everyone else who is already waiting, without blocking
        for len(group) < maxGroupSize {
            select {
            case w := <-db.writes:
                group = append(group, w)
            default:
                break drain
            }
        }
        err := db.commit(group, &merged) // one WAL record, at most one fsync
        for _, w := range group {
            w.done <- err
        }
    }
}

func (db *DB) commit(group []*writeReq, merged *Batch) error {
    if err := db.makeRoomForWrite(); err != nil { // may rotate the memtable or stall
        return err
    }
    merged.Reset()
    merged.init()
    sync := false
    for _, w := range group {
        merged.rep = append(merged.rep, w.b.rep[batchHeader:]...)
        merged.setCount(merged.Count() + w.b.Count())
        sync = sync || w.sync
    }
    first := db.lastSeq.Load() + 1
    merged.setSeq(first)
    if err := db.logw.AddRecord(merged.rep); err != nil {
        return err
    }
    if sync {
        if err := db.log.Sync(); err != nil {
            return err
        }
    }
    seq := first
    merged.Iterate(func(t ValueType, k, v []byte) {
        db.mem.Add(seq, t, k, v)
        seq++
    })
    db.lastSeq.Store(seq - 1) // readers see the whole group at once, or none of it
    return nil
}

The group forms naturally: while the commit goroutine is inside an fsync, new writers pile up in the channel, and the next iteration takes all of them. Under light load groups are size 1 and latency is minimal; under heavy load groups grow and the fsync cost is amortized. No timers, no tuning.

Measured (100-byte values, Sync: true means the write is durable before Put returns):

Benchmark Time per Put Durable writes/s
Sync: false, one goroutine 5.2 µs ~190,000 (not durable)
Sync: true, one goroutine 3,936 µs 254
Sync: true, 128 concurrent goroutines 76 µs ~13,100

Concurrent durable writes are 51x faster per operation than sequential ones, with the same disk, because each fsync now covers dozens of writes. This is how every serious database gets durable throughput, and why a database benchmark with one client thread says little about its throughput.

Durability options, honestly

Setting A crash can lose Typical use
Sync: true on every write Nothing acknowledged Financial records, metadata
Sync: false Writes since the last OS flush (seconds); a process crash alone loses nothing — the data is in the page cache — only an OS crash or power loss does Caches, rebuildable indexes, most analytics
Periodic sync (every N ms in the background) Up to N ms of writes A common middle ground

Whatever the setting, the log format guarantees that recovery sees a prefix of the acknowledged writes, never a reordered or corrupted set — because records are checksummed and replay stops at the first torn record.

Common pitfall

Acknowledging a write before its group's fsync. An optimization attempt moves the memtable insert and the reply to writers before db.log.Sync(), "because the data is already in the log". Throughput improves, all tests pass — tests don't cut power. After a power loss, writes that clients were told were durable are missing, and some clients may have already acted on them (e.g. read their own write from the memtable before the crash). The order is the contract: append, fsync, then make visible and acknowledge. A crash test that drops unsynced data (copy only the synced prefix of the log, as the test suite does) catches the reordering immediately.

Review questions

  1. Why is the log divided into 32 KB blocks instead of being a plain sequence of length-prefixed records?
  2. How does the reader distinguish a torn write from corruption, and why is one normal and the other fatal?
  3. Why does group commit need no timer to form groups?
  4. Why were concurrent synced writes 51x faster per operation than sequential ones on the same disk?
  5. With Sync: false, which kinds of crash lose data, and which do not?