VectorKV

A C++ in-memory vector database with WAL crash recovery and multi-layer HNSW approximate nearest neighbor search.

VectorKV implements the core mechanisms behind embedding-search systems: vector storage, top-k similarity search, persistence, and benchmark-driven evaluation. See PRD.md for the full design and roadmap.

Status: in-memory MVP with WAL + snapshot recovery + HNSW search. Vector storage, cosine similarity, exact brute-force top-k search, multi-layer HNSW ANN search, and a unified VectorDB API are implemented and tested, plus optional WAL replay, snapshot save/load, manual checkpoint, and automatic checkpoint every N writes.

Features

• insert / search / remove via a single VectorDB API
• Cosine similarity over std::vector<float>
• Exact brute-force top-k search (priority-queue based), used as the correctness baseline and Recall@K ground truth
• Multi-layer HNSW approximate nearest neighbor search with configurable M, efConstruction, and efSearch
• String IDs with arbitrary string metadata; dimension validation; soft delete
• Optional write-ahead log (WAL): operations are logged before mutating memory and replayed on restart (VectorDB(wal_path))
• Optional snapshot save/load for full-state persistence (save_snapshot / load_snapshot; recovery loads snapshot then replays WAL)
• Checkpoint: save snapshot then truncate WAL so the log stays bounded (checkpoint(); requires WAL + snapshot path)
• Automatic checkpoint every N insert/remove writes (set_auto_checkpoint_threshold; 0 = disabled)
• CLI benchmark reporting QPS, P50/P95/P99 latency, and Recall@K
• Unit tests (GoogleTest) covering every module

Requirements

• A C++20 compiler (Clang, GCC, or MSVC)
• CMake >= 3.20
• Git (used by CMake FetchContent to pull GoogleTest / Google Benchmark)
• Internet access for the first configure (dependencies are downloaded)

Project layout

VectorKV/
  CMakeLists.txt              # Root build: core library + options
  include/vectorkv/          # Public headers
    types.h                  #   VectorRecord, SearchResult
    distance.h               #   cosine_similarity
    vector_store.h           #   in-memory record storage
    brute_force_index.h      #   exact top-k search
    hnsw_index.h             #   multi-layer HNSW approximate search
    wal.h                    #   write-ahead log (append + replay)
    snapshot.h               #   full-state save/load
    vector_db.h              #   public insert/search/remove API
  src/                       # Core library sources (vectorkv_core)
  tests/                     # Unit tests (GoogleTest)
  bench/                     # CLI benchmark (vector_bench)
  examples/                  # Standalone example (basic_demo)

Build

# Configure (downloads test/bench dependencies on first run)
cmake -S . -B build

# Build everything
cmake --build build -j

Build options (toggle with -D<OPTION>=ON/OFF at configure time):

Option	Default	Description
VECTORKV_BUILD_TESTS	ON	Build unit tests (GoogleTest)
VECTORKV_BUILD_BENCHMARKS	ON	Build the CLI benchmark
VECTORKV_BUILD_EXAMPLES	ON	Build example executables

Example (library + tests only, faster configure):

cmake -S . -B build -DVECTORKV_BUILD_BENCHMARKS=OFF -DVECTORKV_BUILD_EXAMPLES=OFF
cmake --build build -j

Usage

#include "vectorkv/vector_db.h"

vectorkv::VectorDB db;

db.insert("doc1", {1.0f, 0.0f, 0.0f}, {{"title", "cpp notes"}});
db.insert("doc2", {0.9f, 0.1f, 0.0f}, {{"title", "systems design"}});

auto results = db.search({1.0f, 0.05f, 0.0f}, /*top_k=*/2);
for (const auto& r : results) {
    // r.id, r.score, r.metadata
}

db.remove("doc1");

To opt into HNSW search:

vectorkv::HnswOptions hnsw;
hnsw.max_neighbors = 16;
hnsw.ef_construction = 64;
hnsw.ef_search = 64;

vectorkv::VectorDB db(vectorkv::VectorDB::IndexKind::Hnsw, hnsw);

To enable crash recovery, construct VectorDB with a WAL file path. Every insert/remove is appended to the log before memory is mutated, and the log is replayed on construction, so the data is restored after a restart:

{
    vectorkv::VectorDB db("vectorkv.wal");
    db.insert("doc1", {1.0f, 0.0f, 0.0f}, {{"title", "cpp notes"}});
}   // process exits

// later / new process: same path replays the log and restores the data
vectorkv::VectorDB db("vectorkv.wal");
auto results = db.search({1.0f, 0.0f, 0.0f}, /*top_k=*/1);  // finds "doc1"

Persistence: snapshot + WAL + checkpoint

With both WAL and snapshot paths, recovery is snapshot first, then WAL tail:

vectorkv::VectorDB db("vectorkv.wal", "vectorkv.snapshot");
db.insert("doc1", {1.0f, 0.0f, 0.0f});
db.save_snapshot("vectorkv.snapshot");  // manual full-state dump

save_snapshot alone does not truncate the WAL; use checkpoint() when you want to reset the log after persisting full state. Recovery always loads the snapshot first, then replays only the WAL tail.

db.checkpoint();  // save snapshot, then truncate WAL (snapshot must finish first)

To checkpoint automatically without manual calls:

db.set_auto_checkpoint_threshold(1000);  // checkpoint after 1000 insert/remove ops

Both insert and remove count toward N; search does not. Threshold 0 (the default) disables automatic checkpoint. See PRD.md §6.5 for the full design.

Run

# Unit tests
ctest --test-dir build --output-on-failure

# Example demo (insert -> search -> remove)
./build/bin/basic_demo

# Benchmark (defaults: 10000 vectors, dim 128, 1000 queries, top_k 10)
./build/bin/vectorkv_bench --vectors 5000 --dim 128 --queries 500 --top_k 10

# HNSW benchmark with Recall@K against brute-force ground truth
./build/bin/vectorkv_bench --index hnsw --vectors 100000 --dim 384 \
  --queries 10000 --threads 8 --top_k 10 --hnsw_m 16 \
  --ef_construction 64 --ef_search 64

The benchmark prints progress every 10,000 items by default while building the index, generating queries, searching, and computing HNSW Recall@K. Override that with --progress_interval N.

Example demo output:

Query = [1.0, 0.05, 0.0], top_k = 2
Results:
  id=doc1  score=0.998752  title="cpp notes"
  id=doc2  score=0.998158  title="systems design"

Example benchmark output (numbers depend on hardware):

vectors: 5000
dimension: 128
queries: 500
threads: 1
top_k: 10
index: brute
QPS: 2482.78
P50 latency: 0.365958 ms
P95 latency: 0.59075 ms
P99 latency: 0.705084 ms
Recall@10: 1

For --index hnsw, the benchmark builds a brute-force ground-truth database and reports Recall@K for the approximate results.

HNSW benchmark results

The HNSW implementation evolved from a single-layer graph to multi-layer HNSW with diversified neighbor selection. On the medium-scale benchmark (20K vectors, 128 dimensions, 1K queries, M=32, efConstruction=200, efSearch=300), the current implementation reached 0.997 Recall@10 at about 1961 QPS. On the larger random-vector stress test (100K vectors, 384 dimensions, 10K queries, same HNSW parameters), Recall@10 was 0.58921 at about 512 QPS.

See docs/hnsw_experiments.md for the full experiment history, including the earlier single-layer HNSW results and the multi-layer improvements.

Roadmap

• CMake project, vectorkv_core library, GoogleTest setup
• Cosine similarity, VectorStore, brute-force top-k, VectorDB API
• CLI benchmark with QPS and latency percentiles
• WAL append/replay and crash recovery (VectorDB(wal_path))
• Snapshot save/load and snapshot + WAL recovery tests
• Checkpoint: truncate WAL after successful snapshot
• Automatic checkpoint every N writes
• HNSW approximate nearest neighbor index
• Recall@K and HNSW-vs-brute-force comparison
• Concurrent search