Testing and Benchmarking a Storage Engine

Why storage engines need different tests

A storage engine's bugs rarely show up as a failing function call. They show up as a value that disappears after the third compaction, a deleted key that comes back after a crash, a corruption error on the one-in-a-million torn write, or a deadlock between the commit and background goroutines under load. Example-based unit tests miss these because they check the cases the author thought of. This page covers the techniques that found real bugs in this handbook's engine: layered unit tests, a model-based test, crash simulation, fuzzing, the race detector, and benchmarks that measure what matters. Everything here runs with go test and nothing else.

Layer the tests in dependency order

When a high-level test fails, you want to know which layer is wrong. Test each layer against its own contract before testing the layers that use it:

Layer Test
Encoding (varints, internal keys, batch) Round trip, malformed input → ErrCorrupt
WAL Records of sizes 0, 1, 100, exactly one block, many blocks; truncation → ErrTornWrite; a flipped bit → ErrCorrupt
Block, table 10,000-key round trip, lookups at start/middle/end, full iteration, bloom false-positive rate
Skip list, memtable Ordering, newest-version lookups, concurrent readers
Merging iterator, DBIter Versions, tombstones, snapshots
DB Model test, crash test, concurrency test, transactions

Model-based testing

Run thousands of random operations against the engine and against a trivially correct model — a Go map — and compare them, repeatedly, including across close and reopen:

func TestModel(t *testing.T) {
    dir := t.TempDir()
    opts := Options{MemTableSize: 64 << 10, TargetFileSize: 32 << 10} // tiny: force many flushes and compactions
    db, _ := Open(dir, opts)
    model := map[string]string{}
    rng := rand.New(rand.NewPCG(1, 2)) // fixed seed: failures are reproducible

    for phase := 0; phase < 6; phase++ {
        for i := 0; i < 20000; i++ {
            k := fmt.Sprintf("k%05d", rng.IntN(5000)) // small key space: many overwrites and deletes
            if rng.IntN(5) == 0 {
                db.Delete([]byte(k), WriteOptions{})
                delete(model, k)
            } else {
                v := fmt.Sprintf("%s-%d-%d", k, phase, i)
                db.Put([]byte(k), []byte(v), WriteOptions{})
                model[k] = v
            }
        }
        check(phase) // every model key via Get; full scan equals the sorted model
        db.Close()
        db, _ = Open(dir, opts) // recovery path
        check(phase)
    }
    // No leaked files: every .sst on disk belongs to the current version.
}

Choices that make it effective:

  • Tiny limits (64 KB memtables, 32 KB tables) so 120,000 operations trigger dozens of flushes and compactions — the code paths where bugs live.
  • A small key space so the same keys are overwritten and deleted many times, exercising version shadowing and tombstone dropping.
  • Reopen between phases so recovery is tested against the same model.
  • Check both Get and a full scan: they use different code (Table.Get with the bloom filter vs. the merging iterator).
  • Check for leaked files — a reference-counting bug shows up as .sst files that no version references. Check after Close: the first version of this check ran while the DB was open and failed intermittently (8 live tables, 10 on disk) — but only without -race. Reopening had left 4 tables in L0, so Open immediately started a compaction, and the check saw its half-written outputs. The race detector slowed everything enough to hide the window. The same investigation found a real gap: Open did not delete orphan tables left by a crashed flush or compaction; it does now, with TestOrphanTableDeleted. Run concurrency-heavy tests both with and without -race — different timing finds different bugs.
  • Fixed seeds, so a failure can be replayed exactly, and, in CI, a loop over many seeds.

Simulating crashes

Durability bugs only appear after a crash. A cheap, deterministic simulation: while the DB is running, copy its directory — as if the process died at that instant — damage the copy the way a crash would, and open it:

func TestCrashTornTail(t *testing.T) {
    dir := t.TempDir()
    db, _ := Open(dir, Options{})
    for i := 0; i < 1000; i++ {
        // Writes 0..899 are synced by the Sync on write 899; 900..999 are not.
        db.Put(fmt.Appendf(nil, "k%04d", i), []byte("v"), WriteOptions{Sync: i == 899})
    }
    crash := t.TempDir()
    for _, e := range readDir(dir) {
        b := readFile(dir, e)
        if filepath.Ext(e) == ".log" {
            b = b[:len(b)-5] // the last record was torn mid-write
        }
        writeFile(crash, e, b)
    }
    db.Close()
    db2, err := Open(crash, Options{})
    // Every write before the torn one is recovered; the torn one is gone.
}

Extensions that a production engine needs:

  • Drop unsynced data: copy only the bytes that were fsynced. This requires a file-system interface that records sync points — Pebble's vfs.NewStrictMem() does exactly this — and it is the test that catches "acknowledged before fsync" bugs (Write-Ahead Log).
  • Crash at every step: inject a failure at the Nth file operation, for every N, during a flush and a compaction, and check recovery each time.
  • Kill -9 and power-cut tests in a VM for the final word (Files and Durability in Go).

Fuzzing the decoders

Every decoder in the engine — WAL records, blocks, table footers and handles, version edits — parses bytes from disk, which can be corrupted. Go's built-in fuzzer runs a function with mutated inputs, coverage-guided, and saves any input that panics:

func FuzzBlock(f *testing.F) {
    var b blockBuilder
    for _, k := range []string{"a", "ab", "abc", "b"} {
        b.add(makeIKey(nil, []byte(k), 1, TypeValue), []byte("v"))
    }
    f.Add(b.finish(), []byte("ab")) // seed: one valid block
    f.Fuzz(func(t *testing.T, block, target []byte) {
        it := newBlockIter(block, bytes.Compare)
        for it.First(); it.Valid(); it.Next() {
        }
        it = newBlockIter(block, bytes.Compare)
        it.Seek(target) // must return or report corruption, never panic
    })
}

go test -run='^$' -fuzz=FuzzBlock -fuzztime=60s ./kv

The engine already had round-trip tests for blocks and tables, and they all passed. The fuzzer found two crashing bugs in the block decoder, and fixing the first exposed a third by code review:

Found by Input Bug Fix
Fuzzer, in 0.3 s A 1-byte block newBlockIter recorded ErrCorrupt, but Seek ignored the error and indexed an empty restart array First/Seek return immediately if the iterator is already in error
Review while fixing it A restart offset pointing past the data decodeAt sliced data[off:] without checking off Bounds-check every restart offset
Fuzzer, after ~28 s Huge unshared and value length varints rest < unshared+vlen — the sum overflowed uint64, wrapped to a small number, passed the check, and the slice expression panicked Compare each length separately: unshared > rest \|\| vlen > rest-unshared

After the fixes, FuzzBlock ran 34.8 million inputs, FuzzLogReader over 30 seconds, and a new FuzzOpenTable — which also covers footer and block-handle validation, after readBlock gained a check that a handle lies inside the file before allocating h.size bytes — 29.8 million inputs, all without a failure. The failing inputs are saved under testdata/fuzz/ and rerun by plain go test forever after, as regression tests.

The integer-overflow bug is worth remembering beyond this engine: never validate untrusted lengths by adding them. a + b > limit is wrong for attacker- or corruption-controlled a and b; a > limit || b > limit - a is right.

Concurrency testing

func TestConcurrent(t *testing.T) {
    db, _ := Open(t.TempDir(), Options{MemTableSize: 32 << 10}) // frequent rotations
    var wg sync.WaitGroup
    for w := 0; w < 8; w++ {
        wg.Add(2)
        go writer(w) // 3,000 puts of key == value
        go reader(w) // 3,000 random gets: a found value must equal its key
    }
    wg.Wait()
    // then: every written key is readable
}

Run with go test -race. Small memtables make the commit goroutine rotate while readers are pinning state and the background goroutine is flushing — the interleavings where pointer handoffs go wrong. The race detector checks every memory access in those interleavings for missing happens-before edges (Concurrency Bugs); the assertions check the logic. Neither is sufficient alone: the protocol server's flush deadlock had no data race at all and was only found by load.

Benchmarks that answer real questions

Measured on an Apple M1 Pro, 100-byte values:

Question Benchmark Result
Raw write path cost Put, Sync: false 5.2 µs/op
Durable write latency Put, Sync: true, 1 goroutine 3.9 ms/op
Does group commit work? Put, Sync: true, 128 goroutines 76 µs/op — 51x better
Point read cost, cache mostly cold Get, 200 K keys, 8 MB cache 2.96 µs/op, 8% hit rate
Point read cost, cache warm Get, 200 K keys, 64 MB cache 1.09 µs/op, 99.5% hit rate
Write amplification 1 M random writes, 3 key-space sizes 2.2x → 3.7x → 6.6x

Each row answers a question a user of the engine would ask, and each number came with an explanation: group commit amortizes fsync, the block cache hit rate dominates reads (Profiling with pprof), compaction cost grows with L1 size in a two-level design (Compaction and Recovery).

Benchmark design points for engines:

  • Report domain metrics with b.ReportMetric: hit rate, bytes written per user byte, stall time. A latency number without them can't be explained.
  • Separate setup from measurement: loading 200,000 keys is setup; b.Loop excludes it from the timing — but not from a CPU profile of the whole run, which you must keep in mind when reading the profile.
  • Measure under realistic sizes: a benchmark whose data fits in the block cache measures the cache.
  • Steady state, not the first minute: LSM performance changes as levels fill and compaction debt accumulates. A serious engine benchmark (like RocksDB's db_bench or Pebble's ycsb and nightly benchmarks) runs long enough to reach steady state and reports throughput over time, not one number.

A CI recipe

go vet ./...
go test -race -count=1 ./...                    # all tests, race detector
go test -run='^$' -fuzz=FuzzBlock -fuzztime=60s ./kv      # each fuzzer, briefly
go test -run='^$' -fuzz=FuzzLogReader -fuzztime=60s ./kv
go test -run='^$' -fuzz=FuzzOpenTable -fuzztime=60s ./kv
go test -run='^$' -bench=. -count=10 ./kv > new.txt && benchstat base.txt new.txt

Long fuzzing runs and multi-seed model tests belong in a nightly job; the saved corpus makes every PR rerun all previously found crashers in milliseconds.

Common pitfall

Trusting a test suite because it is green. Before fuzzing, this engine had passing tests for every layer, a model test over 120,000 random operations, crash tests, and race-detector runs — and input-dependent crashes in the block decoder that any corrupted block on disk would have triggered, turning a detectable corruption into a process crash. The model test could never find them because it only ever produced valid blocks. Tests check the inputs their author imagined; fuzzers and model-based tests explore inputs nobody imagined. A storage engine needs both, plus an explicit list of the untrusted inputs (everything read from disk or the network) and a fuzzer for each one.

Review questions

  1. Why does the model-based test use tiny memtables and a small key space?
  2. How does copying the data directory while the DB is running simulate a crash, and what can this simple version not catch?
  3. Explain the integer-overflow bug the fuzzer found. Why is a + b > limit an unsafe check for untrusted lengths?
  4. Why are the race detector and assertions on results both needed in the concurrency test?
  5. Which domain metrics would you report alongside ns/op for a storage engine benchmark, and why?