Implemented an HNSW Vector Database in C++ with AVX2 SIMD (99.3% Recall@10 on SIFT1M) , Seeking architectural feedback on concurrency model
Recently I'm working on a vector database from scratch in C++ to better understand how modern vector database works. I just finished benchmarking against SIFT1M dataset (1M vectors, 128 dim) and wanted to share the performance and design choices and get feedback.
Core architecture details-
- Instead of vector<vector<float>> , used 64 Byte aligned allocator to maximise L1/L2 cache locality.
- implemented AVX2 FMA SIMD intrinsics for distance computation (L2, dot product, cosine).
- Implemented HNSW graph for Aproximate nearest neighbor, elminating O(n) linear search.
SIFT1M Benchmark Results (single threaded, Intel i5-13420H, compiler flags ( -O3 -march=native -ffast-math)
- Recall@10: 99.30%
- Recall@100: 98.26%
- Throughput: 2,215 queries/sec
- Tail Latency (p99): 654 microseconds
- Build time: ~13 min.
To establish a baseline, I benchmarked my implementation head-to-head against hnswlib on the same machine using identical parameters (M=32, ef_construction=400, ef_search=200).
- Throughput: 2,215 QPS vs
hnswlib's 2,745 QPS (~19% slower). - Recall@10: 99.30% vs
hnswlib's 99.88%.
Right now, my implementation optimised for single thread traversal and I prioritized read-throughput first using a global shared_mutex. My next major task is concurrent writes. I'm looking into fine-grained spinlocks per node, but I want to ensure strict lock ordering to avoid deadlocks and TOCTOU conditions.
For concurrent insertions into HNSW, would you lean toward per-node spinlocks, lock striping, or another approach?
github repo link -> https://github.com/randomfunction/vector_database/tree/main
