Storage Engine Architecture Overview¶

What we are building¶

A single-process, embedded LSM-tree key-value store in Go — architecturally LevelDB, simplified to two levels so that every line fits in a few pages. It supports Put, Delete, Get, atomic write batches, ordered iteration, consistent snapshots, crash recovery, and background flush and compaction. The theory is in LSM Tree and Storage Engines; this series turns it into about 2,100 lines of working, tested code.

The engine exercises binary encoding, checksums, fsync ordering, lock-free reads, goroutine design, reference counting, iterators, crash testing, profiling, and benchmarking in one codebase. The full, runnable source is in labs/kv in this repository. Pebble (CockroachDB's engine) and Badger are production Go engines of the same family; reading their code after building this one is far easier.

All code in the series compiles and passes its tests with -race (Go 1.26.4). Numbers: Apple M1 Pro, internal NVMe SSD.

Components¶

The series ends with the other main engine design, a page-based Buffer Pool and B+Tree.

Files in the database directory¶

/data/mydb/
├── LOCK               # flock'd while open: a second process cannot open the DB
├── CURRENT            # one line: the active manifest, e.g. "MANIFEST-000012"
├── MANIFEST-000012    # log of version edits (tables added/removed per level)
├── 000013.log         # WAL for the current memtable
├── 000009.sst         # SSTables
└── 000011.sst

All files share one counter (nextFile), so each name is unique and a larger number is newer. CURRENT is replaced with the write-temp-fsync-rename-fsync-directory sequence from Files and Durability in Go.

Keys, sequence numbers, and internal keys¶

Every write gets a sequence number, a monotonically increasing 56-bit counter. Internally, a user key is stored with an 8-byte trailer:

internal key = user key | trailer (8 bytes, little-endian)
trailer      = sequence << 8 | type        (type: 1 = value, 0 = deletion)

func makeIKey(dst, ukey []byte, seq uint64, t ValueType) []byte {
    dst = append(dst, ukey...)
    return binary.LittleEndian.AppendUint64(dst, seq<<8|uint64(t))
}

// Order: user key ascending, then trailer DESCENDING (newest first).
func compareIKey(a, b []byte) int {
    if c := bytes.Compare(ukey(a), ukey(b)); c != 0 {
        return c
    }
    ta, tb := trailer(a), trailer(b)
    switch {
    case ta > tb:
        return -1
    case ta < tb:
        return 1
    }
    return 0
}

This one ordering is what makes everything else work: all versions of a key are adjacent, newest first, so a lookup for "key as of sequence S" is a single seek to (key, S) — the first entry at or after it is the newest version visible at S. Deletes are tombstones: entries of type deletion that shadow older values until compaction can drop both. Snapshots are just sequence numbers.

The life of a write¶

The life of a read¶

1. Under the mutex, pin the state: the memtable, the immutable memtable, the current version (increment its reference count), and the sequence number to read at (latest, or a snapshot's). Release the mutex — the rest of the read takes no locks.
2. Look in the memtable, then the immutable memtable, then L0 tables newest first, then the single L1 table whose key range covers the key. Stop at the first entry for the key: a value or a tombstone.
3. Unpin the version.

Reference counting is what lets compaction delete a table while an earlier read or iterator still uses it: a table file is removed only when no version references it.

Concurrency design¶

type DB struct {
    mu        sync.Mutex // protects mem, imm, cur, nextFile, logNum, snapshots, bgErr
    cond      *sync.Cond // signalled when imm is flushed or L0 shrinks (write stalls wait on it)
    mem, imm  *MemTable
    cur       *version
    lastSeq   atomic.Uint64 // highest sequence visible to readers
    writes    chan *writeReq
    bgWork    chan struct{}
    // ...
}

Making the memtable's single writer a dedicated goroutine is the Go-idiomatic version of LevelDB's writer queue: the skip list's one-writer rule is enforced by construction, and the channel is the queue that makes group commit work. The mutex is held only for pointer swaps and bookkeeping, never across I/O. Write stalls — when the immutable memtable has not been flushed yet, or L0 has too many files — are a cond.Wait() in the commit goroutine, which naturally applies backpressure to all writers.

Package layout¶

kv/
├── batch.go      # Batch encoding
├── wal.go        # LogWriter, LogReader
├── ikey.go       # internal keys and comparator
├── skiplist.go   # lock-free-read skip list
├── memtable.go
├── block.go      # prefix-compressed blocks with restart points
├── bloom.go
├── table.go      # TableWriter, Table, two-level iterator
├── cache.go      # LRU block cache
├── merge.go      # merging iterator (heap)
├── manifest.go   # version edits
├── version.go    # ref-counted versions and table files
├── iter.go       # DBIter: snapshot view over all sources
├── txn.go        # optimistic transactions
├── db.go         # Open, recovery, write path, read path, flush, compaction
└── kv_test.go, txn_test.go, fuzz_test.go, bench_test.go

What is deliberately simplified¶

Each simplification is called out on its page, with what the real engines do instead.

Common pitfall¶

Treating a bug that appears during compaction as a compaction bug. Compaction is the only operation that exercises every other component at once — it reads through table iterators, merges with the internal key comparator, consults snapshots, writes new tables, and commits through the manifest — so a defect anywhere first becomes visible as data that "disappears" after a merge. When that happens, test the lower layers in dependency order (encoding → block → table → iterator → version edit) before suspecting the merge logic itself. The test suite in Testing and Benchmarking is structured exactly in that order for this reason.

Review questions¶

1. Why are internal keys ordered by user key ascending but sequence number descending?
2. How is a snapshot represented, and why is that enough?
3. Why does the engine use a dedicated commit goroutine instead of letting each writer insert into the memtable under a lock?
4. What prevents compaction from deleting a table that an in-progress read is using?
5. Where does backpressure on writers come from when the background goroutine falls behind?