Skip to content

IMPLEMENTATION.md

Latest commit

 

History

History
220 lines (153 loc) · 8.76 KB

IMPLEMENTATION.md

File metadata and controls

220 lines (153 loc) · 8.76 KB
Raw

Implementation Plan - Out-of-Core Vector Database

Vision

Build a production-quality vector database that can run approximate nearest-neighbor (ANN) search over a 100GB dataset while consuming ≤8GB of RAM. The system must be competitive with DiskANN (Microsoft Research, NeurIPS 2019) on recall, QPS, and I/O efficiency.

This is an exploratory systems project. Architecture decisions are intentionally left open at the start of each stage and resolved through benchmarking, not upfront design.

Technology Stack

Layer Technology Why
Core engine C++17 Performance, SIMD, direct memory control
Build system CMake 3.20+ Industry standard, FetchContent for deps
Unit tests Google Test Industry standard
Microbenchmarks Google Benchmark Criterion-equivalent for C++
Logging spdlog Header-only, zero-overhead when disabled
Config/serialization nlohmann/json Header-only, ergonomic
Python bindings pybind11 Expose C++ index to Python eval harness
Evaluation Python 3.10+ numpy, h5py, matplotlib, faiss-cpu
Async I/O (optional) liburing (io_uring) Linux kernel 5.1+, zero-copy page I/O

C++ standard: C++17. Use std::filesystem, std::optional, std::string_view, structured bindings, if constexpr.

No external ANN libraries in the core engine - the whole point is to implement them. FAISS and hnswlib are used only as evaluation baselines.

Stage Overview

Stage Name Deliverable Est. Effort
1 Storage Engine Buffer pool + disk manager, all tests pass 1–2 weeks
2 Core Algorithms Distance functions (SIMD), k-means, flat index 1 week
3 HNSW (in-memory) Full HNSW build + search, recall ≥ 0.95 on SIFT-1M 2 weeks
4 Out-of-Core HNSW HNSW over buffer pool, RSS ≤ 512 MB on SIFT-1M 2 weeks
5 Product Quantization PQ codec, HNSW+PQ integration, 32× compression 1.5 weeks
6 IVF and IVF-PQ IVF index, IVF-PQ hybrid 1.5 weeks
7 Query Engine Unified API, planner, re-ranking 1 week
8 Evaluation Harness Python bindings, full ANN Benchmarks comparison 1 week

Total estimated time: 11–12 weeks for one engineer.

Stage 1 - Storage Engine

Goal: Build the I/O foundation everything else sits on. This is the most critical stage - a bug here will corrupt data in every subsequent stage.

Deliverables:

  • include/oocvdb/storage/page.h - page layout constants and types
  • include/oocvdb/storage/disk_manager.h + src/storage/disk_manager.cpp
  • include/oocvdb/storage/buffer_pool.h + src/storage/buffer_pool.cpp
  • tests/test_storage.cpp - full test coverage

Acceptance Criteria:

  1. Write 10,000 pages and read them back; checksums match.
  2. Buffer pool holds exactly capacity pages under random access.
  3. Eviction under Clock policy measurably outperforms random eviction on sequential scan benchmark.
  4. No memory leaks (Valgrind / AddressSanitizer clean).

See: docs/stages/STAGE_1_STORAGE.md for full spec.

Stage 2 - Core Algorithms

Goal: Implement the mathematical primitives that every index depends on. Validate against brute-force search for correctness.

Deliverables:

  • include/oocvdb/utils/distance.h - L2, inner product, cosine (scalar + AVX2)
  • include/oocvdb/utils/kmeans.h - Lloyd's algorithm k-means
  • include/oocvdb/index/flat.h - brute-force exact ANN (the correctness oracle)
  • tests/test_distance.cpp, tests/test_kmeans.cpp, tests/test_flat.cpp
  • benchmarks/bench_distance.cpp

Acceptance Criteria:

  1. L2 distance matches numpy.linalg.norm to float32 precision.
  2. k-means converges on SIFT-1M in < 60 s with 256 clusters.
  3. Flat index achieves Recall@10 = 1.0 on SIFT-1M (by definition).
  4. AVX2 L2 is ≥ 4× faster than scalar on 128-dim vectors.

See: docs/stages/STAGE_2_ALGORITHMS.md

Stage 3 - HNSW (In-Memory)

Goal: Build a fully correct, in-memory HNSW index. This is the core algorithm. Do not introduce disk I/O yet - keep this stage focused on correctness and recall.

Deliverables:

  • include/oocvdb/index/hnsw/graph.h - adjacency list
  • include/oocvdb/index/hnsw/build.h - insertion
  • include/oocvdb/index/hnsw/search.h - query
  • tests/test_hnsw.cpp
  • benchmarks/bench_hnsw.cpp

Acceptance Criteria:

  1. Recall@10 ≥ 0.95 on SIFT-1M with M=16, ef_construction=200, ef=100.
  2. Build time ≤ 300 s for SIFT-1M on a single thread.
  3. Recall curve (Recall vs. ef) matches hnswlib to within 2%.

See: docs/stages/STAGE_3_HNSW.md

Stage 4 - Out-of-Core HNSW

Goal: Serialize the HNSW graph to the buffer pool and page it in/out during search. This is the project's defining technical challenge.

Deliverables:

  • Extended include/oocvdb/index/hnsw/graph.h - on-disk adjacency list
  • include/oocvdb/index/hnsw/serializer.h - write/load graph to/from disk
  • Prefetch logic integrated into beam search
  • tests/test_ooc_hnsw.cpp
  • Memory usage benchmark comparing in-memory vs. out-of-core at same recall

Acceptance Criteria:

  1. Recall@10 ≥ 0.93 on SIFT-1M with buffer pool capped at 256 MB (20% of index).
  2. No regression in recall vs. Stage 3 when buffer pool is large enough to hold full index.
  3. I/O ops per query measured and logged; benchmark shows prefetch reduces stalls vs. no-prefetch.

See: docs/stages/STAGE_4_OOC.md

Stage 5 - Product Quantization

Goal: Implement PQ compression. A 128-dim float32 vector (512 bytes) should compress to 16 bytes with < 5% recall loss.

Deliverables:

  • include/oocvdb/index/pq/train.h - codebook training
  • include/oocvdb/index/pq/codec.h - encode/decode, ADC distance tables
  • HNSW+PQ integration: store PQ codes in graph nodes, re-rank top candidates with exact distance
  • tests/test_pq.cpp

Acceptance Criteria:

  1. 32× compression (512 → 16 bytes) on 128-dim float32.
  2. Recall@10 ≥ 0.90 on SIFT-1M (5% budget for compression loss).
  3. ADC distance computation ≥ 8× faster than exact float32 L2.

See: docs/stages/STAGE_5_PQ.md

Stage 6 - IVF and IVF-PQ

Goal: Add coarse-level partitioning via IVF and combine with PQ for the memory-efficient 100GB-scale index.

Deliverables:

  • include/oocvdb/index/ivf/index.h - inverted file index
  • include/oocvdb/index/ivf_pq.h - IVF-PQ hybrid
  • tests/test_ivf.cpp, tests/test_ivf_pq.cpp

Acceptance Criteria:

  1. IVF: Recall@10 ≥ 0.90 on SIFT-1M with nlist=1024, nprobe=32.
  2. IVF-PQ: Recall@10 ≥ 0.85 on SIFT-1M with memory ≤ 64 MB.
  3. IVF-PQ search QPS ≥ 10× flat-index QPS at same recall.

See: docs/stages/STAGE_6_IVF.md

Stage 7 - Query Engine

Goal: Unify all index types behind a single API with a query planner that automatically selects parameters.

Deliverables:

  • include/oocvdb/query/engine.h - unified search API
  • include/oocvdb/query/planner.h - parameter selection
  • C-compatible API (extern "C") for FFI
  • tests/test_engine.cpp

Acceptance Criteria:

  1. Single Search(query, k) call works for all index types.
  2. Planner selects correct index type given RAM budget constraint.
  3. Re-ranking reduces recall gap between PQ and exact to < 2%.

See: docs/stages/STAGE_7_QUERY.md

Stage 8 - Evaluation Harness

Goal: Benchmark against FAISS, hnswlib, and DiskANN. Produce publication-quality QPS vs. Recall curves.

Deliverables:

  • pybind11 bindings exposing Index.build(), Index.search(), Index.save(), Index.load()
  • eval/recall.py, eval/throughput.py, eval/compare.py, eval/plot.py
  • Results JSON in eval/results/

Acceptance Criteria:

  1. Recall@10 and QPS numbers reproducible with python eval/compare.py.
  2. Out-of-core HNSW within 2× QPS of DiskANN at Recall@10 ≥ 0.90.
  3. All plots auto-generated from results JSON.

See: docs/stages/STAGE_8_EVAL.md

Cross-Cutting Concerns

Error Handling

Use std::expected<T, Error> (C++23) or a simple Result<T> type wrapping std::variant. No exceptions in hot paths. Errors from disk I/O must be propagated, not swallowed.

Logging

Use spdlog. Log at DEBUG level: every page fault, every eviction. Log at INFO level: build progress, search latency. Production builds compile out DEBUG logs.

Configuration

All tunable parameters (buffer pool size, M, ef, nlist, nprobe) come from a JSON config file or programmatic Config struct - never hardcoded.

Testing Strategy

  • Unit tests: Google Test, one file per module.
  • Property tests: for correctness invariants (e.g., every inserted node is findable).
  • Regression tests: recall must not drop between commits (checked in CI).

Memory Budget Tracking

Every major allocation goes through a MemoryTracker that asserts we stay within the configured RAM budget. This is how we prove the out-of-core claim.