56. Capstone: a tiny embedded database engine (Bitcask-style)

Goal: the expert-tier capstone — an append-only log-structured key-value store with an in-memory index, the same core design as Bitcask/early LevelDB, built with nothing but the standard library. This pulls together file I/O (Ch. 22), binary encoding (Ch. 34.4), generics (Ch. 21/26), and sync (Ch. 17).

56.1 The design

Writes always append to a single log file (data.log) — never seek-and-overwrite — which makes writes fast (sequential disk I/O) and crash-safe (a half-written record at the tail is simply the last thing to recover, never corrupting earlier data). An in-memory map indexes each key to the byte offset of its most recent record in the log, so reads are one seek plus one read, not a scan.

package bitcask

import (
	"encoding/binary"
	"errors"
	"io"
	"os"
	"sync"
)

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

type entryHeader struct {
	KeyLen   uint32
	ValueLen uint32
	Tombstone uint8 // 1 = this record represents a delete
}

const headerSize = 4 + 4 + 1

type indexEntry struct {
	offset int64
	size   int64
}

type DB struct {
	mu    sync.RWMutex
	file  *os.File
	index map[string]indexEntry
}

func Open(path string) (*DB, error) {
	f, err := os.OpenFile(path, os.O_CREATE|os.O_RDWR|os.O_APPEND, 0o644)
	if err != nil {
		return nil, err
	}
	db := &DB{file: f, index: map[string]indexEntry{}}
	if err := db.rebuildIndex(); err != nil {
		_ = f.Close()
		return nil, err
	}
	return db, nil
}

func (db *DB) rebuildIndex() error {
	if _, err := db.file.Seek(0, io.SeekStart); err != nil {
		return err
	}
	var offset int64
	for {
		header := make([]byte, headerSize)
		if _, err := io.ReadFull(db.file, header); err != nil {
			if err == io.EOF || err == io.ErrUnexpectedEOF {
				break
			}
			return err
		}
		keyLen := binary.BigEndian.Uint32(header[0:4])
		valLen := binary.BigEndian.Uint32(header[4:8])
		tombstone := header[8]

		key := make([]byte, keyLen)
		if _, err := io.ReadFull(db.file, key); err != nil {
			return err
		}
		recordSize := int64(headerSize) + int64(keyLen) + int64(valLen)

		if tombstone == 1 {
			delete(db.index, string(key))
			if _, err := db.file.Seek(int64(valLen), io.SeekCurrent); err != nil {
				return err
			}
		} else {
			db.index[string(key)] = indexEntry{
				offset: offset + int64(headerSize) + int64(keyLen),
				size:   int64(valLen),
			}
			if _, err := db.file.Seek(int64(valLen), io.SeekCurrent); err != nil {
				return err
			}
		}
		offset += recordSize
	}
	return nil
}

func (db *DB) Put(key, value []byte) error {
	db.mu.Lock()
	defer db.mu.Unlock()

	offset, err := db.file.Seek(0, io.SeekEnd)
	if err != nil {
		return err
	}
	if err := writeRecord(db.file, key, value, 0); err != nil {
		return err
	}
	db.index[string(key)] = indexEntry{
		offset: offset + int64(headerSize) + int64(len(key)),
		size:   int64(len(value)),
	}
	return nil
}

func (db *DB) Get(key []byte) ([]byte, error) {
	db.mu.RLock()
	entry, ok := db.index[string(key)]
	db.mu.RUnlock()
	if !ok {
		return nil, ErrNotFound
	}

	db.mu.RLock()
	defer db.mu.RUnlock()
	value := make([]byte, entry.size)
	if _, err := db.file.ReadAt(value, entry.offset); err != nil {
		return nil, err
	}
	return value, nil
}

func (db *DB) Delete(key []byte) error {
	db.mu.Lock()
	defer db.mu.Unlock()
	if _, err := db.file.Seek(0, io.SeekEnd); err != nil {
		return err
	}
	if err := writeRecord(db.file, key, nil, 1); err != nil {
		return err
	}
	delete(db.index, string(key))
	return nil
}

func writeRecord(w io.Writer, key, value []byte, tombstone uint8) error {
	header := make([]byte, headerSize)
	binary.BigEndian.PutUint32(header[0:4], uint32(len(key)))
	binary.BigEndian.PutUint32(header[4:8], uint32(len(value)))
	header[8] = tombstone
	if _, err := w.Write(header); err != nil {
		return err
	}
	if _, err := w.Write(key); err != nil {
		return err
	}
	_, err := w.Write(value)
	return err
}

func (db *DB) Close() error {
	db.mu.Lock()
	defer db.mu.Unlock()
	return db.file.Close()
}

56.2 What this teaches, and where it stops being a toy

This gets you: O(1) writes (always append), O(1) reads (one map lookup + one ReadAt, no seek-and-scan), and crash recovery by replaying the log on startup. What it deliberately leaves out, and what real engines (LevelDB, RocksDB, Bitcask itself) add on top: compaction (the log grows forever otherwise — old, overwritten/deleted records are never reclaimed here), concurrent readers during compaction, checksums per record (to detect a torn write after an unclean shutdown, not just truncate at EOF), and a write-ahead-log + separate index snapshot to avoid replaying the entire log on every restart. Each of those is a natural next exercise once this base version passes its own tests.

func TestPutGetDelete(t *testing.T) {
	dir := t.TempDir()
	db, err := Open(dir + "/data.log")
	if err != nil {
		t.Fatal(err)
	}
	defer func() {
		if err := db.Close(); err != nil {
			t.Fatal(err)
		}
	}()

	if err := db.Put([]byte("k1"), []byte("v1")); err != nil {
		t.Fatal(err)
	}
	v, err := db.Get([]byte("k1"))
	if err != nil || string(v) != "v1" {
		t.Fatalf("got (%s, %v)", v, err)
	}

	if err := db.Delete([]byte("k1")); err != nil {
		t.Fatal(err)
	}
	if _, err := db.Get([]byte("k1")); !errors.Is(err, ErrNotFound) {
		t.Fatalf("expected ErrNotFound, got %v", err)
	}
}

func TestRecoversIndexOnReopen(t *testing.T) {
	dir := t.TempDir()
	path := dir + "/data.log"
	db, err := Open(path)
	if err != nil {
		t.Fatal(err)
	}
	if err := db.Put([]byte("k1"), []byte("v1")); err != nil {
		t.Fatal(err)
	}
	if err := db.Close(); err != nil {
		t.Fatal(err)
	}

	reopened, err := Open(path)
	if err != nil {
		t.Fatal(err)
	}
	defer func() {
		if err := reopened.Close(); err != nil {
			t.Fatal(err)
		}
	}()
	v, err := reopened.Get([]byte("k1"))
	if err != nil || string(v) != "v1" {
		t.Fatalf("index not rebuilt correctly: got (%s, %v)", v, err)
	}
}