minikv — a mini log-structured key/value store

A persistent key/value storage engine built from scratch in Go to understand database internals: durable writes, crash recovery, compaction, and indexing. No external database or storage libraries — only the Go standard library.

It follows the Bitcask model (an append-only log + an in-memory index), and in later phases evolves toward an LSM-tree to support range scans.

Status: all 5 phases complete. Durable, crash-safe, compacting, range-capable, and benchmarked against SQLite.

Phases

• Phase 1 — Append-only log storage, in-memory hash index, startup replay
• Phase 2 — fsync durability + crash-safe recovery + per-record checksums
• Phase 3 — Compaction (reclaim space from overwritten/deleted keys)
• Phase 4 — Range queries via a sorted index (skip list)
• Phase 5 — Throughput benchmarks vs SQLite + this write-up

How it works (Phase 1)

Every write is appended to a single log file; the engine never edits data in place. An in-memory map (key -> byte offset) points at each key's most recent record. On startup the engine replays the whole log to rebuild that map, which is how data survives a restart.

        SET k v                                  GET k
          │                                        │
          ▼                                        ▼
  ┌─────────────────┐                     ┌─────────────────┐
  │ encode record   │                     │ index[k] -> off  │  (RLock)
  │ kind|klen|vlen  │                     └────────┬────────┘
  │   |key|value    │                              │ offset
  └────────┬────────┘                              ▼
   (Lock)  │ append to end                 ┌─────────────────┐
           ▼                               │ ReadAt(off)     │  positioned
  ┌─────────────────┐   update index       │ decode record   │  read on disk
  │  log file (disk)│◀─── index[k]=offset  └────────┬────────┘
  │  ...|rec|rec|rec│                              │
  └─────────────────┘                              ▼  value
                                              return value

  startup: replay log front-to-back → rebuild index (last write wins)

On-disk record format

+----------+--------+-----------+-----------+-------------+---------------+
| crc32    | kind   | keyLen    | valLen    | key bytes   | value bytes   |
| uint32BE | 1 byte | uint32 BE | uint32 BE | (keyLen)    | (valLen)      |
+----------+--------+-----------+-----------+-------------+---------------+
 \__ 4 __ /\______________ CRC32 covers every byte to the right __________/

Length-prefixed (not delimiter-based) so keys/values can be arbitrary bytes. kind is set or tombstone (a delete). The leading CRC32 is recomputed on every read and every replay; a mismatch raises ErrCorruptRecord so damaged data is never silently served.

Durability & crash safety (Phase 2)

• fsync per write. Set/Delete call file.Sync() before returning, so an acknowledged write is on the physical disk, not just in the OS page cache. The index is updated only after the record is durable.
• Crash recovery on Open. Writes are synchronous and one-at-a-time, so a crash can only damage the last record. replay stops at the first record that fails to decode (torn write) or fails its checksum (corruption), truncates the log back to the last good offset, fsyncs the repair, and carries on. Store.RecoveredBytes() reports how much was discarded.
• Checksums detect bit rot and partial writes (see record format above).

The durability cost is real — one disk round-trip per write (~hundreds to a few thousand writes/sec depending on the disk). Phase 5 adds a knob to batch syncs for bulk loads.

Compaction (Phase 3)

Every overwrite and delete leaves a dead record behind in the append-only log, so the file grows without bound. Store.Compact() reclaims that space:

1. Walk the in-memory index (which already points only at live keys) and copy each key's latest record into a fresh temp file in the same directory. Tombstoned keys aren't in the index, so they're naturally dropped.
2. fsync the temp file, then os.Rename it over the old log. Rename is atomic on POSIX, so a crash mid-swap leaves either the whole old log or the whole new log — never a corrupt mix. The directory is fsynced so the rename itself is durable.
3. Swap the in-memory index/offsets to the new file and close the old one (which frees its disk space).

demo: 300 records across 5 live keys  ->  7733 bytes
                       after Compact()  ->   130 bytes   (99% reclaimed)

Tradeoff: compaction is stop-the-world — it holds the write lock for its duration, so it's simple and obviously correct but pauses writes. The standard way to remove the pause (and a good "how would you scale this?" answer) is to keep new writes in a small active segment and merge only older, sealed segments in the background, so the live write path is never blocked. That multi-segment design is intentionally left as future work here.

Range queries & the index tradeoff (Phase 4)

The index is now an interface with two implementations, chosen at Open:

Index	Point get	Range scan	Notes
skip list (default)	O(log n)	✅ ordered	keys kept sorted
hash map (WithHashIndex())	O(1) avg	❌ ErrRangeUnsupported	no ordering

Store.Range(start, end) returns every pair with start <= key <= end in ascending order. The skip list does this by jumping to start via its upper "express lanes" in O(log n), then walking the sorted bottom list to end. A hash map can't: it scatters keys by hash with no order, so it honestly returns ErrRangeUnsupported.

The skip list (engine/skiplist.go) is implemented from scratch — no rotations or rebalancing, just probabilistic levels. It's the same structure LevelDB and Redis use for ordered in-memory data.

Hash vs skip list (Apple M2, go test -bench)

BenchmarkHashIndexGet     12.85 ns/op     # O(1)
BenchmarkSkipListGet     129.0  ns/op     # O(log n): ~10x slower
BenchmarkHashIndexPut    148.2  ns/op
BenchmarkSkipListPut     527.6  ns/op
BenchmarkSkipListRange  2012    ns/op     # 100-key window of 100k keys
                                          # (no hash equivalent — can't be done)

The takeaway you can explain in an interview: ordering isn't free. Point lookups get ~10x slower, but in exchange you gain range scans, sorted iteration, and prefix queries — none of which a hash index can do at any price. Pick the index to match the workload.

Throughput vs SQLite (Phase 5)

scripts/bench.sh measures minikv throughput and runs a sqlite3 CLI baseline for a sanity check. Both are configured for the same durability barrier (F_FULLFSYNC — minikv via Go's File.Sync, SQLite via PRAGMA fullfsync=ON), so the durable-write comparison is apples-to-apples.

Apple M2, macOS, 50,000 keys (go build ./cmd/bench && bench):

Benchmark	minikv	sqlite3 (baseline)
durable writes (fsync per write)	~0.37k ops/s	~1.1k ops/s
batched writes (one sync at end)	~440k ops/s	~530k ops/s
reads	~1.0M ops/s	~120k ops/s*

How to read this honestly:

• Durable single writes are fsync-bound, and on macOS F_FULLFSYNC is expensive (a real drive-cache flush). Both engines are slow here; SQLite — a mature, decades-tuned engine — is ~3x faster. minikv keeps its durable path deliberately simple (one append + one barrier per write).
• Batched writes amortize the barrier over many records, and there minikv (~440k/s) lands in the same order of magnitude as SQLite (~530k/s) — i.e. the fsync was the bottleneck, not the engine. That's the sanity result we want.
• *The SQLite read number is not a fair comparison. It runs through the sqlite3 CLI, which parses 50,000 individual SELECT statements; that parse/process overhead dominates. minikv's reads are measured in-process. The honest claim is only that minikv reads are fast (index lookup + one positioned disk read), not that it "beats SQLite" at reads.

The point of the exercise is a sanity baseline: minikv is in the same ballpark as a real database for bulk writes and reads, and is not pathological. Beating SQLite was never the goal — clarity was.

bash scripts/bench.sh                      # defaults: n=50000, durable-n=2000
bash scripts/bench.sh -n 100000 -durable-n 5000

Key design tradeoffs

• Append-only → writes are sequential (disk-friendly, fast) and old records are immutable, which makes concurrent reads safe. The cost is wasted space from overwritten keys — reclaimed by compaction in Phase 3.
• Hash index in RAM → O(1) point lookups, but it holds every key, so memory scales with key count, and it cannot do range scans (no order). Phase 4 adds an ordered skip-list index for ranges (see below).

Project layout

engine/             the storage engine (library)
  record.go         on-disk record encode/decode + CRC32 checksums
  store.go          Store: Open/Set/Get/Delete/Keys/Range/Compact + replay
  index.go          index interface + hash-map implementation
  skiplist.go       ordered skip-list index (from scratch)
  store_test.go     unit tests (set/get/delete/restart/concurrency)
  recovery_test.go  crash-safety + checksum tests
  compaction_test.go  compaction + atomic-swap tests
  skiplist_test.go  skip-list unit + fuzz-vs-reference tests
  range_test.go     Store.Range + index-selection tests
  options_test.go   WithSync / Sync durability-mode tests
  index_bench_test.go  hash-vs-skip-list benchmarks
cmd/minikv/         command-line tool (one-shot commands + REPL)
cmd/crasher/        write-until-killed helper for the real-SIGKILL demo
cmd/bench/          throughput benchmark + sqlite3 baseline
scripts/            per-phase demo scripts + bench.sh

Run it

Requires Go 1.26+.

# Run the unit tests (includes a restart-recovery test).
go test ./...

# Run with the race detector to exercise the concurrency safety.
go test -race ./...

# Run the Phase 1 demo (proves data survives a process restart).
bash scripts/phase1_demo.sh

# Run the Phase 2 demo (fsync, torn-write recovery, checksums, real SIGKILL).
bash scripts/phase2_demo.sh

# Run the Phase 3 demo (compaction: file size before/after).
bash scripts/phase3_demo.sh

# Run the Phase 4 demo (range queries + hash-vs-skiplist perf).
bash scripts/phase4_demo.sh

# Run the Phase 5 throughput benchmark (minikv vs sqlite3 baseline).
bash scripts/bench.sh

# Run the index micro-benchmarks directly.
go test -bench=. -benchmem -run='^$' ./engine/

# Use the CLI directly.
go run ./cmd/minikv -db my.data set greeting hello
go run ./cmd/minikv -db my.data get greeting
go run ./cmd/minikv -db my.data range a m  # all keys in [a, m]
go run ./cmd/minikv -db my.data            # interactive REPL

Limitations & what I'd build next

Deliberately out of scope (this is a learning engine, not a product) — but the natural next steps, and good interview discussion points:

• All keys live in RAM. The index holds every key; memory scales with key count. Real Bitcask accepts this; LSM trees push keys to disk via SSTables + bloom filters. This is the single biggest scaling limit.
• Single-file, stop-the-world compaction. Compaction pauses writes. The standard fix is multiple log segments — an active segment for new writes and sealed segments merged in the background — so the write path never blocks.
• No multi-key atomicity / transactions. Each Set/Delete is atomic on its own; there's no way to commit several as a unit. A WAL with begin/commit markers would add this.
• One writer. Writes are serialized by the write lock. Sharding the keyspace (with per-shard logs) would parallelize writes.
• Mid-log corruption is not repaired. Recovery trusts that only the tail can be damaged (true for synchronous single-writer appends). Detecting and isolating corruption in the middle of a log would need per-segment checksums and a manifest.
• No compression, no value log separation, no background GC scheduling.

What this project demonstrates

Log-structured storage, durability via fsync (and the F_FULLFSYNC nuance), crash recovery, checksums, atomic file replacement via rename, the hash-vs-ordered-index tradeoff, a skip list built from scratch, and an honest benchmark methodology — each with the why documented in the code.