S1 · Build Your Own Database (for real)

One file that only ever grows, and a small table in memory that remembers where the newest copy of each thing landed. That’s the whole project on one page.

Before you start. You can run a terminal command and write a little code, but you’ve never built a database - so far you’ve only read how real ones work, in the Data Systems track and the Database Internals set. This project makes it real: one Go file of about 240 lines (kv.go is 237) that stores data, survive a crash, and end up on your GitHub profile.

1974: three years before System R answers its first real query

In 1974, a team at IBM’s research lab in San Jose began building a database you could ask questions in a new language called SQL, typed almost like an English sentence. The project, System R, took three years to reach its first real customer, aircraft-engine maker Pratt & Whitney, in 1977. Most of those years went into that language and into answering fast. The rest went into one more problem: two people changing the same row at once without one wiping out the other’s change.

That’s what “build a database” sounds like, and building everything a real one needs genuinely takes years. But almost none of those years went into the one property that makes something a database instead of a file: what you wrote is still there after the machine crashes mid-write. That part is small, and it’s the only part this project builds.

Never touch an old byte. Only ever add a new one.

Say you store one thing: user:1 = Alice. The simplest way to remember it is to write those bytes - a byte is one small chunk of stored data, close to one character of text - to a file on disk.

Now user:1 changes to Alicia. The obvious move is to find the old Alice bytes and overwrite them. Don’t. Instead, write user:1 = Alicia at the end of the same file, right after whatever was already there, and leave Alice where it was. The file only ever grows. The picture shows both writes landing in the one file, the old value left behind:

flowchart LR
  W1["write: user:1 = Alice"] --> LOG["the file (only ever grows)"]
  W2["change: user:1 = Alicia"] --> LOG
  LOG --> NOTE["Alice is still in there, untouched, further back"]

That rule - never edit, only add to the end - is called an append-only log, and the reason to bother is speed: adding to the end of a file is the fastest thing a disk does, while overwriting a spot in the middle is one of the slowest.

The note that remembers where things are: the index

One append creates a new problem. user:1 now lives in the file twice, once as Alice, once as Alicia. How do you know which is current? A file with a million writes can’t be read end to end for every question.

The fix is a second, smaller thing kept in memory: one row per key, saying where its newest copy sits. Look up user:1, get back a spot, jump straight there, done - no scanning. That table is the index, and because it lives in memory, checking it costs almost nothing next to reading the file.

A process dies mid-write, and the database doesn’t blink

Now the worrying part. The program holding that in-memory table crashes, and the table is gone. The file still holds everything.

The fix is almost insultingly simple: on startup, read the file from the very first byte, one record at a time, and rebuild the table from scratch. Replayed in the order it was written, the newest copy of every key ends up pointed at again. This replay-on-startup is what a database calls crash recovery - nothing more exotic than reading everything again, in order.

You can’t erase from a log, so deleting writes something instead

Deleting is the same problem from the other side: you can’t reach into the file and erase bytes, since the whole point was never touching old ones. So a delete doesn’t remove anything: it appends one more record, a marker meaning “this key is gone,” called a tombstone. Replay sees it and drops the key from the index, as if it had never been written.

The log never stops growing, until compaction cleans it

Every overwrite and delete leaves old bytes sitting in the file, doing nothing. Given long enough, most of the file is dead weight. The fix, run occasionally, builds a brand-new file holding only the newest live copy of each key, no overwrites or tombstones, then swaps it in for the old one. That’s compaction, the only step that ever shrinks the file.

Five small rules - append only, keep an index, replay on startup, tombstone on delete, compact occasionally - are the entire mechanism behind storage engines that real companies run today; the second read names them. The rest of this lesson has you build them, byte by byte, in Go.

You now know

• A real database’s hard years go into its query language and into letting many people edit at once; keeping data safe through a crash is the small part, and it’s what this project builds.
• An append-only log never edits an old byte; every write and delete lands on the end, which is why writes are fast.
• An index is a small table kept in memory that maps each key to where its newest copy sits in the file, so a read never scans the file.
• Crash recovery is reading the file from its first byte, in order, and rebuilding the index from what is there.
• A tombstone is a written record meaning “delete this key,” because a log can’t erase anything.
• Compaction writes a fresh file holding only the newest copy of each key, then swaps it in for the old one.

Stop here if you want. What follows is the same five rules in Go: the record format, a log dumped byte by byte, a crash forced by hand, and the real numbers behind “durable” versus “fast.”

Second read: the record format, the log, and the trade nobody tells you about

This is a log-structured store - Bitcask’s own design, and the early layer inside LevelDB and RocksDB. Code: teaching/code/s1-kvstore/ (kv.go, kv_test.go).

Get the code

The cd teaching/code/... lines on this page point at a folder you do not have. Every file in it is printed in full under Run it, further down, so this is the whole setup on a machine with nothing but Go installed. Go 1.22 or newer; go version says which you have.

mkdir -p ~/portfolio/s1-kvstore && cd ~/portfolio/s1-kvstore
go mod init kvstore

Then save the seven files printed under Run it into that folder, each under its own name: kv.go, kv_test.go, and stage1_test.go to stage5_test.go. Now the tests pass:

$ go test ./...
ok  	kvstore	0.622s

go mod init kvstore is the step this page never used to say. It writes a small go.mod file that makes the folder a module named kvstore, Go’s word for one project with one name. Skip it and go test ./... stops at once:

pattern ./...: directory prefix . does not contain main module or its selected dependencies

Go has no project to look for ./... in. The name matters later, too: S3 imports this store by it, which is why every project on this shelf lives side by side in ~/portfolio.

Measured 2026-10-17: an empty folder, files pasted as printed, Go 1.27.1 on macOS. The same tests also pass on Go 1.22.12.

The five stages, each a commit

Build it in order; each stage is a green checkpoint to commit.

1. In-memory only. Put/Get/Delete on a Go map[string][]byte. No persistence yet.
2. Append to a log + index. Put encodes a record, appends it, stores index[key] = offset. Get looks up the offset, then ReadAt.
3. Rebuild the index on startup. Open replays the log from byte 0.
4. Delete via tombstone. Delete appends a “deleted” record; replay drops it from the index.
5. Compaction. Compact rewrites a fresh log with only the newest live value per key, then renames it in atomically.

The reference kv.go implements all five. Type it yourself, stage by stage.

Each stage has its own test file, so “this stage works” is a command that passes, not a feeling. Start with only stage1_test.go beside your own kv.go. When it passes, commit, add the next file, and run again; the earlier stages must stay green. stage1_test.go also holds the small helpers the other four use, so it stays to the end. kv_test.go is the reference’s original all-in-one test: add it last.

The tests only ever call Open(path), Put, Get, Delete, Close, Compact and ErrNotFound, so stage 1 can be a Go map behind those names, with Open ignoring its path. That map passes stage1_test.go and fails stage2_test.go with stat .../data.log: no such file or directory, which is the point: stage 2 is where the file appears. All five, run against the reference code on 2026-10-17:

$ go test -v -run Stage ./...
--- PASS: TestStage1InMemory (0.01s)
--- PASS: TestStage2AppendAndIndex (0.01s)
--- PASS: TestStage3Recovery (0.01s)
--- PASS: TestStage3TornTail (0.01s)
--- PASS: TestStage4Tombstone (0.02s)
--- PASS: TestStage5Compaction (0.03s)
ok  	kvstore	0.577s

The stage 3 test caught a real bug. Its last check, a write after a torn tail and then one more restart, failed against the reference code as it was first written. Replay stopped at byte 46, where the torn third record starts, but the 14 torn bytes stayed in the file. The next Put was appended after them, at byte 60, while the index recorded 46. On the restart after that, replay met the same torn bytes at 46 and stopped again, so the write at 60 was never read back: an acknowledged write, lost, with no error anywhere. The fix is one call at the end of load, db.f.Truncate(off), which cuts the file back to the last good record before anything else is appended. Real write-ahead logs do the same on recovery. Since the fix, kv.go is 242 lines, not the 237 quoted at the top of this page.

The record format

Read it left to right: each box is one field of a record, its size in bytes in brackets.

 crc32(4) | keyLen(4) | valLen(4) |  key bytes  |  val bytes
 └── everything little-endian ──┘

crc32 is a checksum, a 4-byte fingerprint computed from the rest of the record; it covers keyLen|valLen|key|val. A mismatch on replay means a torn tail write, a last record the crash cut off halfway, so you stop there and treat everything before it as durable. tombstone = valLen set to the sentinel 0xFFFFFFFF, no value bytes. Bitcask’s record adds an 8-byte timestamp after the crc for merge; the reference code skips it, so the header above is 12 bytes instead of 20. Byte strip: the board.

The log, byte by byte

Write four records with the reference code - two keys, an overwrite, a delete - and dump the file. The test’s own sequence (user:1 = Alice, cart:9 = socks, user:1 = Alicia, delete cart:9), run through a six-line main and then xxd. Each line shows the starting offset in hex on the left, sixteen bytes as hex pairs in the middle, and the same bytes as text on the right:

$ xxd demo.log
00000000: 91a4 81fd 0600 0000 0500 0000 7573 6572  ............user
00000010: 3a31 416c 6963 6519 a1ca 8206 0000 0005  :1Alice.........
00000020: 0000 0063 6172 743a 3973 6f63 6b73 cb67  ...cart:9socks.g
00000030: 3fea 0600 0000 0600 0000 7573 6572 3a31  ?.........user:1
00000040: 416c 6963 6961 1b78 5cf7 0600 0000 ffff  Alicia.x\.......
00000050: ffff 6361 7274 3a39                      ..cart:9

The table below reads one row per record: byte offset, crc32, keyLen, valLen, key, val, total size:

23 + 23 + 24 + 18 = 88 bytes, matching os.Stat after the four writes. Lengths are little-endian, so a key length of 6 is 06 00 00 00, backwards from how you’d write it - the same endianness lesson as Everything Is a Number (bits & bytes), here on disk. Alice at offset 0 survives the overwrite at 46; the index just points at 46 now. The tombstone’s valLen of ffffffff is the sentinel ^uint32(0) in the code.

One PUT, one GET, one crash

The sequence the test simulates: a write is acknowledged, the process dies, and the next Open must come back with the same answer.

sequenceDiagram
  participant App
  participant Index as index (memory)
  participant Log as log (disk)
  App->>Log: Put: append at offset 46, fsync
  Log-->>App: written
  App->>Index: index["user:1"] = 46
  App->>Index: Get "user:1"?
  Index-->>App: 46
  App->>Log: ReadAt(46)
  Log-->>App: "Alicia"
  Note over App,Index: process crashes, index gone
  App->>Log: Open: replay from 0, check every crc
  Log-->>Index: user:1 at 46, cart:9 deleted
  Note over Log: a torn record fails its crc, replay stops
  App->>Index: Get "user:1"
  Index-->>App: 46, same as before the crash

Run the reference test and the sequence above is what passes:

$ cd teaching/code/s1-kvstore && go test -v ./...
=== RUN   TestRoundTripAndRecovery
--- PASS: TestRoundTripAndRecovery (0.03s)
PASS
ok  	kvstore	0.511s

The torn-tail case, forced by hand: truncate 7 bytes off the 88-byte log (cutting the tombstone in half), reopen, and read both keys:

get user:1 -> Alicia
get cart:9 -> kv: key not found
log size after 4 writes: 88 bytes
after torn tail, get cart:9 -> <nil> (tombstone was the torn record, so the key is back)
after torn tail, get user:1 -> Alicia

cart:9 came back, correctly: the tombstone never fully reached disk, so Open stopped at the first record whose checksum didn’t match. That’s the whole crash-safety story, for one crc32 per record.

The number on the board, measured

The board’s resume line says “~50k writes/sec”; the measurements below show what that costs and how real stores reach it. The reference code calls f.Sync() after every append - an fsync, the call that forces a flush all the way to the flash - and here’s the honest measurement of that:

2000 puts with fsync each: 7.495s  = 267 writes/s, 3.75 ms per write

Remove the Sync() in append (marked in kv.go as the crash-safety knob) and the same loop reads:

2000 puts, no fsync: 10ms  = 203513 writes/s, 0.00 ms per write

2,000 puts in about 10 ms is roughly 200,000 a second (the timer read just under 10 ms, hence 203,513); 2,000 in 7.495 s is 267 a second. Three orders of magnitude apart, both true. With a sync per write, every acknowledged Put has reached the flash and survives a power cut, at 3.75 ms each. Without it, writes sit in the page cache: a process crash loses nothing, a power cut loses the last few milliseconds. Real stores reach the board’s 50k by group commit: batch the writes that land within a millisecond and fsync once for all of them. Shared by 100 writes that’s 37 µs each, 27,000 writes/s; by 200 it’s 19 µs, 53,000/s - so 50k needs batches of about two hundred, which a busy server fills in under a millisecond. Stage 6 if you want it, and the same durable-versus-fast trade Storage Engines describes for every write-ahead log.

Run it

cd teaching/code/s1-kvstore
go test ./...      # round-trip + crash-recovery + compaction all pass

// Package kv is a tiny persistent key-value store, Bitcask-style:
// every write appends one record to a single log file, and an in-memory
// map remembers the byte offset of each key's newest record. A read is
// one seek. This is the same core idea behind Riak/Bitcask, LevelDB, RocksDB.
//
// Companion lesson: teaching/lessons/portfolio-projects/0146-s1-build-your-own-database.md
package kv

import (
	"bufio"
	"encoding/binary"
	"errors"
	"hash/crc32"
	"io"
	"os"
	"sync"
)

// tombstone is a sentinel value-length meaning "this key was deleted".
const tombstone = ^uint32(0)

var ErrNotFound = errors.New("kv: key not found")

// Record on disk:  crc32(4) | keyLen(4) | valLen(4) | key | val   (little-endian)
// crc covers keyLen|valLen|key|val, so a torn/corrupt tail write is detectable.
type DB struct {
	mu    sync.RWMutex
	f     *os.File
	path  string
	off   int64            // current end-of-file offset (next append lands here)
	index map[string]int64 // key -> byte offset of its newest record
}

// Open opens (or creates) the log at path and rebuilds the index by replaying it.
func Open(path string) (*DB, error) {
	f, err := os.OpenFile(path, os.O_RDWR|os.O_CREATE|os.O_APPEND, 0o644)
	if err != nil {
		return nil, err
	}
	db := &DB{f: f, path: path, index: make(map[string]int64)}
	if err := db.load(); err != nil {
		f.Close()
		return nil, err
	}
	return db, nil
}

func (db *DB) Close() error { return db.f.Close() }

// encode builds one on-disk record. If del, valLen is the tombstone sentinel
// and val is ignored.
func encode(key string, val []byte, del bool) []byte {
	if del {
		val = nil
	}
	payload := make([]byte, 8+len(key)+len(val))
	binary.LittleEndian.PutUint32(payload[0:4], uint32(len(key)))
	if del {
		binary.LittleEndian.PutUint32(payload[4:8], tombstone)
	} else {
		binary.LittleEndian.PutUint32(payload[4:8], uint32(len(val)))
	}
	copy(payload[8:], key)
	copy(payload[8+len(key):], val)

	rec := make([]byte, 4+len(payload))
	binary.LittleEndian.PutUint32(rec[0:4], crc32.ChecksumIEEE(payload))
	copy(rec[4:], payload)
	return rec
}

// append writes one record and returns the offset it landed at.
func (db *DB) append(key string, val []byte, del bool) (int64, error) {
	rec := encode(key, val, del)
	off := db.off
	if _, err := db.f.Write(rec); err != nil {
		return 0, err
	}
	// ponytail: fsync-per-write is the crash-safety knob; batch fsyncs for
	// higher throughput. Left on for correctness (an acked write survives a crash).
	if err := db.f.Sync(); err != nil {
		return 0, err
	}
	db.off += int64(len(rec))
	return off, nil
}

func (db *DB) Put(key string, val []byte) error {
	db.mu.Lock()
	defer db.mu.Unlock()
	off, err := db.append(key, val, false)
	if err != nil {
		return err
	}
	db.index[key] = off
	return nil
}

func (db *DB) Delete(key string) error {
	db.mu.Lock()
	defer db.mu.Unlock()
	if _, err := db.append(key, nil, true); err != nil {
		return err
	}
	delete(db.index, key)
	return nil
}

func (db *DB) Get(key string) ([]byte, error) {
	db.mu.RLock()
	off, ok := db.index[key]
	db.mu.RUnlock()
	if !ok {
		return nil, ErrNotFound
	}
	hdr := make([]byte, 12)
	if _, err := db.f.ReadAt(hdr, off); err != nil {
		return nil, err
	}
	klen := binary.LittleEndian.Uint32(hdr[4:8])
	vlen := binary.LittleEndian.Uint32(hdr[8:12])
	if vlen == tombstone {
		return nil, ErrNotFound
	}
	val := make([]byte, vlen)
	if _, err := db.f.ReadAt(val, off+12+int64(klen)); err != nil {
		return nil, err
	}
	return val, nil
}

// load replays the log from the start to rebuild the index. It stops cleanly at
// EOF, and also stops (rather than erroring) at a torn or crc-mismatched tail
// record — the classic "crash mid-write" case — treating everything before it
// as durable.
func (db *DB) load() error {
	r := bufio.NewReader(db.f)
	var off int64
	hdr := make([]byte, 12)
	for {
		if _, err := io.ReadFull(r, hdr); err != nil {
			if err == io.EOF || err == io.ErrUnexpectedEOF {
				break
			}
			return err
		}
		crc := binary.LittleEndian.Uint32(hdr[0:4])
		klen := binary.LittleEndian.Uint32(hdr[4:8])
		vlen := binary.LittleEndian.Uint32(hdr[8:12])
		blen := klen
		if vlen != tombstone {
			blen += vlen
		}
		body := make([]byte, blen)
		if _, err := io.ReadFull(r, body); err != nil {
			break // torn tail: value never fully written -> stop replay here
		}
		h := crc32.NewIEEE()
		h.Write(hdr[4:12])
		h.Write(body)
		if h.Sum32() != crc {
			break // corrupt tail -> stop; everything before is durable
		}
		key := string(body[:klen])
		if vlen == tombstone {
			delete(db.index, key)
		} else {
			db.index[key] = off
		}
		off += 12 + int64(blen)
	}
	// Cut a torn tail off, or the next append lands after the garbage and the
	// restart after that stops replay at it again: an acked write, lost.
	if err := db.f.Truncate(off); err != nil {
		return err
	}
	db.off = off
	return nil
}

// Compact rewrites the log keeping only the newest live value per key, then
// atomically swaps it in. Reclaims space taken by overwritten/deleted records.
func (db *DB) Compact() error {
	db.mu.Lock()
	defer db.mu.Unlock()

	tmp := db.path + ".compact"
	nf, err := os.OpenFile(tmp, os.O_RDWR|os.O_CREATE|os.O_TRUNC, 0o644)
	if err != nil {
		return err
	}
	newIndex := make(map[string]int64, len(db.index))
	var noff int64
	for key := range db.index {
		val, err := db.getLocked(key)
		if err != nil {
			nf.Close()
			return err
		}
		rec := encode(key, val, false)
		if _, err := nf.Write(rec); err != nil {
			nf.Close()
			return err
		}
		newIndex[key] = noff
		noff += int64(len(rec))
	}
	if err := nf.Sync(); err != nil {
		nf.Close()
		return err
	}
	nf.Close()
	db.f.Close()
	if err := os.Rename(tmp, db.path); err != nil {
		return err
	}
	f, err := os.OpenFile(db.path, os.O_RDWR|os.O_CREATE|os.O_APPEND, 0o644)
	if err != nil {
		return err
	}
	db.f, db.index, db.off = f, newIndex, noff
	return nil
}

// getLocked reads a value assuming the caller already holds the lock.
func (db *DB) getLocked(key string) ([]byte, error) {
	off, ok := db.index[key]
	if !ok {
		return nil, ErrNotFound
	}
	hdr := make([]byte, 12)
	if _, err := db.f.ReadAt(hdr, off); err != nil {
		return nil, err
	}
	klen := binary.LittleEndian.Uint32(hdr[4:8])
	vlen := binary.LittleEndian.Uint32(hdr[8:12])
	val := make([]byte, vlen)
	if _, err := db.f.ReadAt(val, off+12+int64(klen)); err != nil {
		return nil, err
	}
	return val, nil
}

package kv

import (
	"bytes"
	"path/filepath"
	"testing"
)

// The one check the whole store must pass: writes survive an overwrite, a
// delete, AND a full close+reopen (crash recovery via log replay), plus
// compaction keeps only live keys.
func TestRoundTripAndRecovery(t *testing.T) {
	path := filepath.Join(t.TempDir(), "data.log")

	db, err := Open(path)
	if err != nil {
		t.Fatal(err)
	}
	must := func(e error) {
		if e != nil {
			t.Helper()
			t.Fatal(e)
		}
	}
	must(db.Put("user:1", []byte("Alice")))
	must(db.Put("cart:9", []byte("socks")))
	must(db.Put("user:1", []byte("Alicia"))) // overwrite
	must(db.Delete("cart:9"))                // tombstone
	must(db.Close())

	// Reopen -> index is rebuilt purely from the log (simulates a crash+restart).
	db, err = Open(path)
	must(err)

	if v, err := db.Get("user:1"); err != nil || !bytes.Equal(v, []byte("Alicia")) {
		t.Fatalf("user:1 = %q, %v; want Alicia", v, err)
	}
	if _, err := db.Get("cart:9"); err != ErrNotFound {
		t.Fatalf("cart:9 err = %v; want ErrNotFound", err)
	}

	must(db.Compact())
	if v, err := db.Get("user:1"); err != nil || !bytes.Equal(v, []byte("Alicia")) {
		t.Fatalf("after compact user:1 = %q, %v", v, err)
	}
	if _, err := db.Get("cart:9"); err != ErrNotFound {
		t.Fatalf("after compact cart:9 err = %v; want ErrNotFound", err)
	}
	must(db.Close())
}

package kv

import (
	"os"
	"path/filepath"
	"testing"
)

// The stage tests. Each file checks one stage of the lesson, and each stage
// adds a file: save stage1_test.go, make it pass, commit; then add
// stage2_test.go, and so on. `go test -run Stage3` runs one stage on its own.
// The helpers below are used by every stage, so this file stays.

// Stage 1: in memory only. Put, Get, overwrite, Delete and a key never set.
// Nothing here looks at the disk, so a map behind Open is enough to pass.
func TestStage1InMemory(t *testing.T) {
	db := open(t, logPath(t))
	defer db.Close()

	put(t, db, "user:1", "Alice")
	want(t, db, "user:1", "Alice")
	put(t, db, "user:1", "Alicia")
	want(t, db, "user:1", "Alicia")
	if err := db.Delete("user:1"); err != nil {
		t.Fatal(err)
	}
	wantMissing(t, db, "user:1")
	wantMissing(t, db, "never:set")
}

func logPath(t *testing.T) string { return filepath.Join(t.TempDir(), "data.log") }

func open(t *testing.T, path string) *DB {
	t.Helper()
	db, err := Open(path)
	if err != nil {
		t.Fatal(err)
	}
	return db
}

func put(t *testing.T, db *DB, k, v string) {
	t.Helper()
	if err := db.Put(k, []byte(v)); err != nil {
		t.Fatal(err)
	}
}

func want(t *testing.T, db *DB, k, v string) {
	t.Helper()
	got, err := db.Get(k)
	if err != nil || string(got) != v {
		t.Fatalf("Get(%q) = %q, %v; want %q", k, got, err, v)
	}
}

func wantMissing(t *testing.T, db *DB, k string) {
	t.Helper()
	if got, err := db.Get(k); err != ErrNotFound {
		t.Fatalf("Get(%q) = %q, %v; want ErrNotFound", k, got, err)
	}
}

func size(t *testing.T, path string) int64 {
	t.Helper()
	fi, err := os.Stat(path)
	if err != nil {
		t.Fatal(err)
	}
	return fi.Size()
}

package kv

import (
	"bytes"
	"os"
	"testing"
)

// Stage 2: every Put appends one record to the file and never touches an old
// one. A record is 12 header bytes (crc32, keyLen, valLen) plus key plus value,
// so "user:1" + "Alice" is 23 bytes, and the overwrite leaves Alice on disk.
func TestStage2AppendAndIndex(t *testing.T) {
	path := logPath(t)
	db := open(t, path)
	defer db.Close()

	put(t, db, "user:1", "Alice")
	if got := size(t, path); got != 23 {
		t.Fatalf("after one Put the log is %d bytes; want 23", got)
	}
	put(t, db, "cart:9", "socks")
	put(t, db, "user:1", "Alicia")
	if got := size(t, path); got != 23+23+24 {
		t.Fatalf("after three Puts the log is %d bytes; want 70", got)
	}

	raw, err := os.ReadFile(path)
	if err != nil {
		t.Fatal(err)
	}
	if !bytes.Contains(raw, []byte("Alice")) || !bytes.Contains(raw, []byte("Alicia")) {
		t.Fatal("the overwrite should append Alicia and leave Alice in the file")
	}
	want(t, db, "user:1", "Alicia") // the index points at the newest copy
	want(t, db, "cart:9", "socks")
}

package kv

import (
	"os"
	"testing"
)

// Stage 3: Open rebuilds the index by replaying the log from byte 0. Close
// and reopen stands in for a crash: the map is gone, the file is not.
func TestStage3Recovery(t *testing.T) {
	path := logPath(t)
	db := open(t, path)
	put(t, db, "user:1", "Alice")
	put(t, db, "cart:9", "socks")
	put(t, db, "user:1", "Alicia")
	db.Close()

	db = open(t, path)
	want(t, db, "user:1", "Alicia")
	want(t, db, "cart:9", "socks")
	db.Close()
}

// A crash mid-write leaves half a record at the end. Cut the 70-byte log to
// 60, inside the third record: replay must stop there and keep the first two.
// Then the next write must land where replay stopped, not after the torn
// bytes, or it is lost on the following restart.
func TestStage3TornTail(t *testing.T) {
	path := logPath(t)
	db := open(t, path)
	put(t, db, "user:1", "Alice")
	put(t, db, "cart:9", "socks")
	put(t, db, "user:1", "Alicia")
	db.Close()

	if err := os.Truncate(path, 60); err != nil {
		t.Fatal(err)
	}
	db = open(t, path)
	want(t, db, "user:1", "Alice") // the overwrite was the torn record
	want(t, db, "cart:9", "socks")

	put(t, db, "user:2", "Bob")
	db.Close()
	db = open(t, path)
	defer db.Close()
	want(t, db, "user:2", "Bob")
	want(t, db, "user:1", "Alice")
}

package kv

import (
	"os"
	"testing"
)

// Stage 4: Delete appends a tombstone (valLen = 0xFFFFFFFF, no value bytes),
// 12 + 6 = 18 bytes for "cart:9", and replay drops the key again.
func TestStage4Tombstone(t *testing.T) {
	path := logPath(t)
	db := open(t, path)
	put(t, db, "user:1", "Alice")
	put(t, db, "cart:9", "socks")
	put(t, db, "user:1", "Alicia")
	if err := db.Delete("cart:9"); err != nil {
		t.Fatal(err)
	}
	if got := size(t, path); got != 88 {
		t.Fatalf("after four writes the log is %d bytes; want 88", got)
	}
	wantMissing(t, db, "cart:9")
	db.Close()

	db = open(t, path)
	wantMissing(t, db, "cart:9")
	want(t, db, "user:1", "Alicia")
	db.Close()

	// Tear the tombstone in half: the delete never reached disk, so the key
	// comes back. The log must not invent a delete it does not hold.
	if err := os.Truncate(path, 81); err != nil {
		t.Fatal(err)
	}
	db = open(t, path)
	defer db.Close()
	want(t, db, "cart:9", "socks")
}

package kv

import "testing"

// Stage 5: Compact rewrites the log with only the newest live value per key.
// The 88-byte log holds one live record (user:1 = Alicia, 24 bytes), so that
// is all that should be left, and the store must still work afterwards.
func TestStage5Compaction(t *testing.T) {
	path := logPath(t)
	db := open(t, path)
	put(t, db, "user:1", "Alice")
	put(t, db, "cart:9", "socks")
	put(t, db, "user:1", "Alicia")
	if err := db.Delete("cart:9"); err != nil {
		t.Fatal(err)
	}

	if err := db.Compact(); err != nil {
		t.Fatal(err)
	}
	if got := size(t, path); got != 24 {
		t.Fatalf("after compaction the log is %d bytes; want 24", got)
	}
	want(t, db, "user:1", "Alicia")
	wantMissing(t, db, "cart:9")

	put(t, db, "user:2", "Bob") // lands after the compacted record
	db.Close()

	db = open(t, path)
	defer db.Close()
	want(t, db, "user:1", "Alicia")
	want(t, db, "user:2", "Bob")
	wantMissing(t, db, "cart:9")
}

Then wire a tiny main.go REPL (> put k v, > get k) or a TCP server that speaks a line protocol, turning the library into a “database server” you can telnet into. (Stage 6, optional, and a great README screenshot.)

Try it (five minutes, in order)

1. Write the four records and look at them. Put this in cmd/demo/main.go next to kv.go (module kvstore, so the import is "kvstore"), then run and dump the file:

package main

import (
	"os"

	"kvstore"
)

func main() {
	os.Remove("demo.log")
	db, _ := kv.Open("demo.log")
	db.Put("user:1", []byte("Alice"))
	db.Put("cart:9", []byte("socks"))
	db.Put("user:1", []byte("Alicia"))
	db.Delete("cart:9")
	db.Close()
}

go run ./cmd/demo && xxd demo.log        # the 88 bytes, four records, walk them with the table above

2. Break the tail and recover. truncate -s 81 demo.log (7 bytes short), reopen in the demo, Get("cart:9"): the tombstone is gone, so the key is back. Truncate to 60, inside the third record, and user:1 reads Alice again - the overwrite was the torn record this time.

3. Measure the fsync. Wrap 2,000 Puts in a timer, run, then comment out db.f.Sync() in append and run again. The ratio between the two numbers, on your disk, is the number to put in the README instead of “~50k”.

Steps 2 and 3, ready to run

The demo in step 1 deletes demo.log on its first line, so “reopen in the demo” cannot work as step 2 says. These two programs are the missing pieces. Save each as main.go in its own folder under cmd/, next to cmd/demo/.

cmd/reopen/main.go opens the log as it is, writes nothing, and reads both keys:

// reopen opens demo.log as it is (no delete, no writes) and reads both keys,
// so you can see what replay recovered after you cut the file short.
package main

import (
	"fmt"
	"log"
	"os"

	"kvstore"
)

func main() {
	fi, err := os.Stat("demo.log")
	if err != nil {
		log.Fatal(err)
	}
	fmt.Printf("demo.log is %d bytes\n", fi.Size())
	db, err := kv.Open("demo.log")
	if err != nil {
		log.Fatal(err)
	}
	defer db.Close()
	for _, k := range []string{"user:1", "cart:9"} {
		v, err := db.Get(k)
		fmt.Printf("get %s -> %q %v\n", k, v, err)
	}
}

$ go run ./cmd/demo && wc -c demo.log
      88 demo.log
$ truncate -s 81 demo.log && go run ./cmd/reopen
demo.log is 81 bytes
get user:1 -> "Alicia" <nil>
get cart:9 -> "socks" <nil>
$ truncate -s 60 demo.log && go run ./cmd/reopen
demo.log is 60 bytes
get user:1 -> "Alice" <nil>
get cart:9 -> "socks" <nil>

The first reopen also cut the file from 81 bytes back to 70, the end of the last whole record; that is the torn-tail fix above at work.

cmd/bench/main.go is step 3’s timer:

// bench times 2,000 Puts into a fresh bench.log. Run it once as is, then
// comment out the db.f.Sync() call in append (kv.go) and run it again.
package main

import (
	"fmt"
	"log"
	"os"
	"time"

	"kvstore"
)

func main() {
	const n = 2000
	os.Remove("bench.log")
	db, err := kv.Open("bench.log")
	if err != nil {
		log.Fatal(err)
	}
	defer db.Close()
	val := []byte("Alicia")
	start := time.Now()
	for i := 0; i < n; i++ {
		if err := db.Put(fmt.Sprintf("user:%d", i), val); err != nil {
			log.Fatal(err)
		}
	}
	d := time.Since(start)
	fmt.Printf("%d puts: %v = %.0f writes/s, %.3f ms per write\n",
		n, d.Round(time.Millisecond), n/d.Seconds(), d.Seconds()*1000/n)
}

Run it, then comment out the three lines of the if err := db.f.Sync() block in append and run it again:

$ go run ./cmd/bench
2000 puts: 7.939s = 252 writes/s, 3.970 ms per write
$ go run ./cmd/bench          # Sync() commented out
2000 puts: 20ms = 99294 writes/s, 0.010 ms per write

Measured 2026-10-17 on an Apple M4 laptop, internal SSD, with other jobs running. The fsync row lands within 6% of the 3.75 ms measured earlier on this page. The no-fsync row came out at half the earlier 203,513, and a row that short moves by that much between runs: 20 ms is a handful of scheduler ticks. That is one more reason to print your own numbers, with your machine and date, rather than anyone else’s.

Put it on GitHub (the resume payoff)

• Repo name: gokv or logdb. Pin it.
• README opens with the one-sentence trick + the board PNG.
• Badge the go test passing. Add a “How it works” section = stages 1–5.
• Resume line: “Built a persistent key–value store in Go - log-structured storage, WAL, in-memory hash index, crash recovery via log replay, and compaction.”

Ship it: the same four files for every project on this shelf

The bullets above say “badge the go test passing” and stop. Here is the whole step, the same for every project on this shelf (S1 to S6); only the repo name changes. YOU is your GitHub username, gokv the repo.

1. The test workflow. Save as .github/workflows/test.yml. GitHub runs it on every push and every pull request:

name: test
on: [push, pull_request]
jobs:
  test:
    runs-on: ubuntu-latest
    steps:
      - uses: actions/checkout@v7
      - uses: actions/setup-go@v7
        with:
          go-version-file: go.mod
      - run: go vet ./...
      - run: go test -race ./...

go-version-file: go.mod installs the Go version your go.mod names, so CI and your laptop agree. -race turns on Go’s race detector: a test that passes only because two goroutines happened not to collide fails here instead of in a demo. (actions/checkout@v7 and actions/setup-go@v7 were the current majors on 2026-10-17, read from each repo’s latest release.)

2. The badge. The first line under the README’s title. GitHub draws it green or red from the workflow’s last run on the default branch:

![test](https://github.com/YOU/gokv/actions/workflows/test.yml/badge.svg)

3. The README. Five parts, in the order a stranger’s questions come: what it is, a picture, how to run it, what you measured, what you’d do next.

# gokv

![test](https://github.com/YOU/gokv/actions/workflows/test.yml/badge.svg)

A key-value store in one Go file: every write is appended to a log, a map in
memory remembers where each key's newest copy is, and a restart replays the log.

## How it works

```mermaid
flowchart LR
  W[Put / Delete] --> LOG[(append-only log)]
  W --> IDX[index in memory: key -> offset]
  LOG -. replay on startup .-> IDX
  R[Get] --> IDX --> LOG
```

## Run it

    go test ./...

## What I measured

| | writes/s | ms per write |
|---|---|---|
| fsync every write | (your number) | (your number) |
| no fsync | (your number) | (your number) |

Machine, OS, date, and the exact command that printed these.

## What I'd do next

- one line per upgrade you did not build, and why it is next

GitHub draws a fenced mermaid block as a diagram in any Markdown file, README included (GitHub docs, “Creating diagrams”). That is the picture to use: the board on this page is chalk’s drawing, and the diagram on your repo should be one you wrote. Every lesson on this shelf already has a mermaid flowchart in its second read; start from it and redraw it in your own words.

4. The licence. Without one, nobody else may legally reuse your code, which is an odd thing for a portfolio piece to say. Add a file called LICENSE holding the MIT licence text from choosealicense.com/licenses/mit, with your name and the year filled in.

The numbers in “What I measured” are the point of the whole README. Anyone can paste a key-value store; the table says you ran yours, on a named machine, and know what each row bought.

Go deeper (primary sources)

• Bitcask design paper (10 pages, the exact model you built): https://riak.com/assets/bitcask-intro.pdf - the high-trust source here.
• Designing Data-Intensive Applications, Ch. 3 “Storage and Retrieval” - you’ve walked it: the Data Systems track. Reread the hash-index + SSTable/LSM section; S1-flagship turns this hash index into an LSM-tree.
• Next upgrade: sorted string tables + a memtable → range scans. The graduation from weekend banger to flagship.

There is no “S1-flagship” page on this site: the two lines above name an upgrade, not a lesson. That upgrade is built in two places you can read now. Storage Engines walks from this hash index to sorted string tables and LSM-trees, and the From Scratch database series (Build Your Own Database - From Scratch, starting at Database 01: The Append-Only File) grows this same append-only file into pages, a B-tree, a write-ahead log and SQL.

Related

• S3 · Build a Redis Server (that real clients can talk to) - imports this store by its module name, kvstore, as its persistence layer.
• The drawer that says it saved - what fsync does underneath the 3.75 ms, in How Computers Work, with a lab to move the interval yourself.
• Build Your Own Database - From Scratch - the slow build of the same file, through pages, a B-tree and SQL.
• Enough Go to read these builds - the Go this file leans on: errors as values, defer, a mutex.
• Storage Engines - hash indexes, sorted string tables and LSM-trees: the next upgrade, explained.
• S5 · Build a Message Log (Kafka-style) - this log again, with readers that each remember how far they got (later on this shelf).

Retrieval practice

9 questions. Answer each one before you open it.