An embeddable vector database written in Go, built from scratch on a Bitcask-style storage engine with a hand-implemented HNSW index for approximate nearest-neighbor search. It provides durable, crash-safe storage and fast similarity search, usable as a library in any Go project.
I wanted to understand what actually happens beneath a database like SQLite or a vector store like Pinecone, instead of treating them as black boxes. So I built one from scratch — the on-disk format, the indexing, crash recovery, and the approximate nearest-neighbor search — to learn how durability and fast similarity search really work.
Data is stored in an append-only log: every write appends a record; records are never modified in place. An in-memory hash index (the keydir) maps each key to the exact file and byte offset of its most recent record, so point lookups are a single seek — no scanning. Vectors are stored the same way, and an HNSW graph is layered on top to answer nearest-neighbor queries. On startup, both the storage indexes and the vector graph are rebuilt from the durable data on disk.
Each record is length-prefixed and carries a CRC checksum:
[ CRC (4) | timestamp (8) | key length (4) | value length (4) | key | value ]
The length prefixes let the reader walk records one at a time; the CRC lets recovery detect and skip a corrupt or partially written record at the tail of a file.
On Open, mydb replays every data file in order to rebuild its in-memory indexes, applying updates and tombstone deletes so the final state matches what's on disk. If a write was interrupted mid-record (for example, the process was killed), the torn record fails its CRC check and recovery stops cleanly at that point, preserving all valid records written before it. The active data file is rotated once it passes a size threshold, spreading data across multiple files.
Similarity search uses HNSW (Hierarchical Navigable Small World graphs), the approach behind production vector databases. Vectors live on multiple graph layers — sparse upper layers for coarse, long-range jumps and a dense bottom layer for fine-grained precision. A query descends from the top layer, greedily hopping toward closer vectors and refining as it drops down, so it inspects only a small fraction of the dataset instead of comparing against everything. Because the vectors are stored durably, the graph is treated as a derived structure and rebuilt from them on startup.
Two parameters control the speed/accuracy tradeoff:
- M — max neighbors per node per layer. Higher M means a denser, more navigable graph (better recall, slower to build).
- ef — search width. Higher ef explores more candidates per query (better recall, slower search).
db, err := mydb.Open("./data")
if err != nil {
log.Fatal(err)
}
db.PutVector("cat", []float32{1.0, 0.1, 0.0})
db.PutVector("kitten", []float32{0.9, 0.2, 0.0})
db.PutVector("car", []float32{0.0, 0.1, 1.0})
// find the 2 vectors most similar to the query
results := db.Search([]float32{1.0, 0.0, 0.0}, 2) // ["cat", "kitten"]The store also works as a plain key-value database:
db.Put("apple", "red")
db.Put("banana", "yellow")
db.Put("cherry", "darkred")
// Get reports presence with a bool, not an error
value, ok := db.Get("apple") // "red", true
_, missing := db.Get("durian") // "", false
// Scan returns the VALUES for keys in the inclusive range [start, end],
// ordered by key
values := db.Scan("apple", "banana") // ["red", "yellow"]
db.Delete("banana")
keys := db.Keys() // every live key, sortedNote that Open takes a directory path — mydb creates it and writes rotating
data.N files inside. There is no Close(): every Put appends and the file
handle is released before the call returns, so the store is durable as soon as a
write returns.
Measured on 128-dimensional vectors, 20,000 vectors, recall@10 averaged over 100 queries. Recall is measured against exact brute-force search as ground truth.
| Config | Recall@10 | HNSW latency | Brute-force latency | Speedup |
|---|---|---|---|---|
| Fast (M=16, ef=50) | 43% | 0.9 ms | 11.2 ms | 12.8x |
| Default (M=48, ef=125) | 89% | 5.1 ms | 9.8 ms | 1.9x |
The speed/accuracy tradeoff is tunable via M and ef: the fast configuration is ~13x faster but returns under half the true neighbors, while the default trades most of that raw speedup for 89% recall. The default favors accuracy.
The speedup at 20k is modest at high recall because HNSW's advantage is logarithmic — brute-force cost grows linearly with the dataset while HNSW stays nearly flat, so the gap widens with scale. Across sizes at the fast configuration, brute-force latency climbed from ~0.3 ms (1k vectors) to ~12 ms (20k) while HNSW barely moved, and the speedup grew from ~1x to ~13x. At the hundreds-of-thousands-to-millions scale where brute force becomes untenable, the margin is far larger; benchmarks stop at 20k for practical build times.
- How length-prefixed binary formats enable random-access reads without scanning
- How an in-memory index is rebuilt from an append-only log on startup, and why derived structures (the HNSW graph) can be rebuilt from durable data rather than persisted
- How HNSW achieves logarithmic-time approximate search, and the recall/latency tradeoff controlled by M and ef
- Debugging a 100x performance regression down to its root cause (per-comparison disk reads during search) and fixing graph over-connectivity via neighbor pruning
- Debugging byte-offset bugs and format-migration hazards firsthand
- Persist the HNSW graph to disk (with rebuild as a fallback) to avoid re-inserting every vector on startup — index build is currently the main cost
- Heap-based candidate lists in search, replacing sorted slices, to lower constant factors and allow benchmarking at larger scales
- Compaction — reclaim space from stale records and tombstones in sealed files
- Cached vector norms to speed up cosine-similarity computation
- A network/SQL layer to expose the store beyond an in-process library