What I am learning building a vector DB from scratch

Why I am writing this

I am building a small vector database in C++20 to learn the guts behind systems like Faiss. Not to ship a competitor. To understand memory layout, indexes, heaps, persistence, and recovery by implementing them.

This post is a learning log. I write about what clicked, what I coded, and where I got stuck. Exact in-memory search works. Snapshots round-trip. WAL open, replay, checkpoint, fsync, and crash injection work. Beside that live path I now have an LSM engine: memtable, immutable segments, a MANIFEST, newest-wins reads, and compaction. It is not wired into VectorDB yet. Next is metadata filters, then one storage path.

The contract came first

I kept wanting to jump into classes. That was a mistake. Until dimensions, ids, delete behavior, and metrics were locked, every design conversation drifted.

The biggest unlock was fixed dimensions. If every vector has the same length, storage is a flat problem. Offset math becomes i times d. Wrong-length inserts are an easy reject. Variable dimensions sounded flexible, but they would have made every later piece messier for almost no learning value.

I also chose tombstones instead of immediate erase. Delete flips a flag. Positions stay stable. Compaction can wait. That choice kept search and indexes simple, and it showed up again later when deletes had to hide rows in older segment files without editing them.

• float32 components, uint64_t ids
• duplicate insert fails; update is a separate path
• cosine default; dot and Euclidean also supported
• library first; HTTP later as a thin wrapper

built
  insert / get / update / remove
  exact search over live rows
  fixed-d float store
  .vdb snapshot save / load
  WAL open / replay / checkpoint
  fsync + fork crash matrix
  memtable → segment flush
  MANIFEST + compaction

still out of scope
  metadata filters          ← next
  SegmentStore wired into VectorDB
  HNSW
  HTTP server

Layout is the storage engine

First I built Version A: an array of records. Each record owns its own std::vector of floats. Append and at work by physical position. There is still no id lookup. That separation mattered. I finally understood that storage and indexing are different jobs.

Where I got stuck: cache locality. I could say the words, but I did not feel them until I drew Version A as scattered heap blocks. A full scan jumps to a new float allocation for every row. The CPU wants a straight line through memory. Version A does not give it one.

Version B, FlatVectorStore, made that concrete. Three arrays joined by the same position: ids, deleted flags, and one contiguous float slab. Append pushes id and flag, then inserts d floats at the end of values_. values_at(i) returns a span starting at i times dimensions.

Result

Result

std::optional<std::size_t> FlatVectorStore::append(
    std::uint64_t id, std::span<const float> values) {
  if (values.size() != dimensions_) return std::nullopt;
  const std::size_t position = ids_.size();
  ids_.push_back(id);
  deleted_.push_back(false);
  values_.insert(values_.end(), values.begin(), values.end());
  return position;
}

std::span<const float> FlatVectorStore::values_at(
    std::size_t position) const {
  if (position >= ids_.size())
    throw std::out_of_range("position out of range");
  const std::size_t start = position * dimensions_;
  return std::span<const float>(values_.data() + start, dimensions_);
}

Where the benchmark confused me

I expected Version B to crush Version A. My first timings said they were the same. That felt like a failed experiment.

Two bugs in the measurement: I was not on a Release build, so loop overhead hid layout. And if the scan checksum is discarded, -O3 can delete the whole loop. After I fixed both, the story got nuanced. At 128-d and 100k rows, A was about 32 percent slower. At 1M by 128, both were near DRAM bandwidth and the gap mostly vanished.

What I learned: layout matters, but only relative to the bottleneck. Cache-friendly work shows SoA. Bandwidth-bound work does not care as much. Also, never trust a benchmark until the build type and the kept side effects are honest.

Users speak ids, storage speaks positions

This was the conceptual gap I kept tripping on. VectorStore only knows positions 0, 1, 2. Callers want id 101. IdIndex is the bridge: uint64_t to size_t.

I skipped writing a custom open-addressing hash table. I already know that material, and unordered_map was enough to keep learning CRUD. The trap I hit instead was smaller and more embarrassing: map_[id] inserts a missing key. Lookup has to use find.

Another stuck point: update found the id, then forgot to copy the new floats into the store. The test failed until I wrote an explicit std::copy into values_at(*pos).

insert(101, vec)
  → append floats at position p
  → index[101] = p
  → active_count++

get(101)
  → pos = index.find(101)
  → if missing or deleted → empty
  → return values_at(pos)

Status VectorDB::update(std::uint64_t id,
                        std::span<const float> values) {
  if (values.size() != store_.dimensions())
    return Status::dimension_mismatch;
  auto pos = index_.find(id);
  if (!pos) return Status::not_found;
  if (store_.is_deleted(*pos)) return Status::not_found;
  auto dest = store_.values_at(*pos);
  std::copy(values.begin(), values.end(), dest.begin());
  return Status::ok;
}

One score convention, then a min-heap

Distance functions were straightforward once I forced one ranking rule: higher score is always better. Dot and cosine already work that way. Squared Euclidean is lower-is-better, so search stores the negated value. Same heap for every metric.

Exact search was where heaps finally made sense to me. I scan every non-deleted row. I push {id, score} into a size-k min-heap. The worst of the current best sits on top. If the heap grows past k, I pop. At the end I reverse so best comes first.

Stuck moment: priority_queue keeps the largest element on top by default. For a min-heap of scores, my comparator has to treat higher score as lower priority. The first version of WorseFirst felt upside down until I wrote it next to a tiny example on paper.

for each physical row i
  skip if deleted_[i]
  score = score_pair(query, values_at(i))
  push {id, score} into min-heap of size k
  if heap.size() > k: pop worst

complexity: O(n · d) distances + O(n log k) heap

float VectorDB::score_pair(
    std::span<const float> query,
    std::span<const float> candidate) const {
  switch (metric_) {
    case Metric::cosine:
      return cosine_similarity(query, candidate);
    case Metric::dot_product:
      return dot_product(query, candidate);
    case Metric::euclidean:
      return -squared_euclidean(query, candidate);
  }
}

std::priority_queue<SearchResult,
    std::vector<SearchResult>, WorseFirst> heap;

for (std::size_t i = 0; i < store_.size(); ++i) {
  if (store_.is_deleted(i)) continue;
  float score = score_pair(query, store_.values_at(i));
  heap.push({store_.id_at(i), score});
  if (heap.size() > k) heap.pop();
}
// pop into a vector, then reverse → best first

A file is a contract

Persistence was the first piece that felt foreign. In memory I can hold floats and bools however C++ likes. On disk, padding, bool width, and write order become part of the API forever.

I started in a format sandbox so I could write magic, version, counts, payload, and checksum by hand before touching VectorDB. The contract that finally worked is SoA, matching FlatVectorStore: header, all ids, all deleted bytes, all floats, checksum. Load rebuilds IdIndex. The hash table is not saved.

The broken first draft still thought in rows. It wrote id, deleted, floats, id, deleted, floats. That is AoS on disk. It also wrote two bytes for deleted and took addresses of temporaries. Three separate loops plus local variables before fwrite fixed it.

Result

Result

for (size_t i = 0; i < db.physical_size(); ++i) {
  fwrite(&db.id_at(i), 8, 1, file);          // temporary address
  fwrite(&db.is_deleted_at(i), 1, 2, file);  // 2 bytes, wrong
  fwrite(&db.values_at(i), 4, 16, file);     // AoS + hardcoded d
}

for (size_t i = 0; i < n; ++i) {
  uint64_t id = db.id_at(i);
  fwrite(&id, 8, 1, file);
}
for (size_t i = 0; i < n; ++i) {
  uint8_t d = db.is_deleted_at(i) ? 1 : 0;
  fwrite(&d, 1, 1, file);
}
for (size_t i = 0; i < n; ++i) {
  auto values = db.values_at(i);
  fwrite(values.data(), 4, values.size(), file);
}

A snapshot is a photo. The WAL is a notebook

A .vdb file is a full-state photo. If the process dies between mutations, the photo is stale. SQLite WAL and CMU-style recovery made the missing piece click: append intent to a log before you mutate RAM.

I built WalWriter / WalReader in a sandbox first, the same way I did for the file format. Then I wired log-before-mutate into insert, update, and remove. Failed ops write nothing. On open: load the snapshot if it exists, replay every WAL record, reopen the writer at max_lsn + 1.

Checkpoint is the cleanup step. Save a fresh photo, append a CHECKPOINT record, close the writer, truncate the WAL, reopen at LSN 1. That keeps replay short. Hard lessons: fread return value is not record_length; close the writer before truncating; store wal_path_ because the writer does not expose path().

[ record_length u32 ]  bytes of (lsn + op + payload + checksum)
[ lsn           u64 ]
[ op_type       u32 ]  1=INSERT 2=UPDATE 3=DELETE 4=CHECKPOINT
[ payload... ]
[ checksum      u32 ]  // lsn + op + payload only

Result

Status VectorDB::open(const std::string& snapshot_path,
                      const std::string& wal_path) {
  uint64_t out_max_lsn = 0;
  if (!snapshot_path.empty() && exists(snapshot_path)) {
    Status st = load(snapshot_path);
    if (st != Status::ok) return st;
  }
  if (!wal_path.empty()) {
    Status st = replay_wal(wal_path, out_max_lsn);
    if (st != Status::ok) return st;
    st = enable_wal(wal_path);
    if (st != Status::ok) return st;
    wal_->set_next_lsn(out_max_lsn);
  }
  return Status::ok;
}

Status VectorDB::checkpoint(const std::string& snapshot_path) {
  if (!wal_) return Status::ok;
  Status st = save(snapshot_path);
  if (st != Status::ok) return st;
  std::string path = wal_path_;
  wal_.reset();                 // close before truncate
  std::ofstream(path, std::ios::trunc).close();
  return enable_wal(path);      // reopen at LSN 1
}

fflush is not durability

A log in the kernel page cache is not a log on disk. fflush pushes the C library buffer into the OS. fsync asks the OS to push those pages to stable storage. If the machine dies between them, replay has nothing to read.

I added maybe_crash hooks at six points and a fork harness that kills the child there: before the WAL append, after append before flush, after fsync, after the memory apply, after the checkpoint snapshot, and after the snapshot but before WAL truncate. The parent then opens the files and checks what survived.

The CHECKPOINT record was the missing breadcrumb. Replay needs to know which photo the notebook was truncated against. Without it, a crash between save and truncate could leave a new snapshot plus an old log that looks like extra work, or worse, an ambiguous mix. Append CHECKPOINT, then truncate.

WAL flushed + fsync'd  →  op is committed
crash before fsync     →  op may vanish, DB still valid
crash after snapshot,
  before truncate      →  CHECKPOINT record + replay must be idempotent
do not truncate WAL while WalWriter is still open

enum class CrashPoint {
  None,
  BeforeWalAppend,
  AfterWalAppendBeforeFlush,
  AfterWalFlush,
  AfterMemoryApply,
  AfterCheckpointSnapshot,
  AfterCheckpointBeforeTruncateWal,
};

Rewriting the photo gets expensive

A checkpoint walks every row and rewrites the whole .vdb. That cost grows with total N, even if you only inserted a few vectors since the last save. LSM-style storage flips it: keep a small mutable memtable, and when it fills, flush only that batch into a new immutable segment file. Old files stay untouched.

I built that stack beside the live snapshot + WAL path so I would not break recovery while learning flush, manifests, and merge. VectorDB still serves v0.2. SegmentStore is the LSM engine next to it.

The measurement finally made the rewrite pain concrete. At 128-d and 100K vectors, a full .vdb checkpoint wrote about 52 MB in 0.079s. Flushing a 1K-row segment wrote 0.52 MB in 0.001s. About 76× faster and 100× fewer bytes for that batch.

Result

[ magic 8 ]  V E C S E G 0 1
[ version u32 ][ dims u32 ][ n u64 ][ metric u32 ]
[ ids u64×n ][ deleted u8×n ][ floats f32×n×d ]
[ checksum u32 ]

Newest-wins, then merge

Deletes were the LSM trap. After a flush, the id is gone from the memtable. Memtable::remove would return not_found. SegmentStore::remove has to tombstone(id) even when the live row only exists in an older file. A newer delete marker hides older values. The bytes stay until compaction reclaims them.

Reads walk memtable first, then segments newest to oldest. First sighting of an id wins. A tombstone means not found. The MANIFEST file is the source of truth for which .vec files are live. Globbing the directory after a crash would pick up orphans and half-written files. Publish is temp + fsync + rename.

compact() is merge, not keep-the-newest-N-files. Dropping old segments without merging would lose ids that exist only in older files. The merge walks newest to oldest, keeps live rows, writes one new segment, swaps MANIFEST, then deletes the old files. Manual API first. Auto policy later.

segment-001 has id 7
segment-002 has id 7 tombstone
segment-003 has id 9

drop 001+002, keep 003  →  id 7 gone, but also
                          id 7's history is wrong
                          and ids only in 001 vanish

merge newest→oldest     →  7 deleted, 9 live
                          write segment-004
                          MANIFEST = [004]
                          then delete 001/002/003

Status SegmentStore::remove(std::uint64_t id) {
  // Must tombstone even if the live row
  // only exists in an older segment.
  memtable_.tombstone(id);
  return Status::ok;
}

// 1) memtable present?
if (auto e = memtable_.find(id)) {
  if (e->is_deleted) return std::nullopt;
  return e->values;
}
// 2) segments newest → oldest
// first sighting of id wins; tombstone ⇒ not found

What I keep learning the hard way

Owning the code matters more than having the code. When the first store appeared fully written for me, I could not explain the invariants. Rewriting it myself was slower and useful.

Diagrams beat prose when the idea is layout. AoS versus SoA, id versus position, disk headers, WAL versus snapshot, and newest-wins across files only stuck after I drew them.

Benchmarks, serializers, and recovery paths all lie if you skip the boring details: build type, kept side effects, byte widths, write order, when the file handle is closed, and whether the OS has actually flushed pages.

What's next

Metadata storage and filtering are next. After that I want SegmentStore wired into VectorDB so there is one write path, not a live snapshot engine beside a learning LSM.

HNSW still waits. Exact search is the ground truth I will need when approximate indexes arrive. I will keep updating this post as I get unstuck.