VeloxVector

An ultra-fast, concurrent, in-memory vector database built from scratch in C++17. Supports concurrent read-write access with a two-phase locking protocol, high-dimensional L2 (Euclidean) distance query execution, a multi-threaded execution queue, and real-time performance metrics collection.

What This Is

VeloxVector is a high-performance database engine designed to store high-dimensional floating-point vectors and perform nearest-neighbor (k-NN) queries in sub-millisecond latencies. High-dimensional vector searches are critical for modern machine learning systems, serving as the core retrieval mechanism for retrieval-augmented generation (RAG), embedding similarity checks, recommendation engines, and neural search. This database implements a Hierarchical Navigable Small World (HNSW) graph index to navigate high-dimensional spaces efficiently, alongside a brute-force Flat Index used as a recall validation baseline and ground-truth correctness oracle.

From a systems engineering perspective, this project implements operating-system-level concurrency primitives to support high-throughput concurrent reads and writes. The database supports two synchronization models: a global shared-exclusive read-write locking mechanism (Phase 1) and a highly optimized fine-grained per-node latching protocol (Phase 2). By removing the global write lock during graph navigation and connections, the system scales search and insertion throughput concurrently under heavily contested write-heavy workloads.

Architecture

+-----------------------------------------------------------+
|                      Client Application                   |
+-----------------------------------------------------------+
                              |
                              v
+-----------------------------------------------------------+
|                          VeloxVector                         | (Owns ThreadPool, HNSWIndex, and MetricsCollector)
+-----------------------------------------------------------+
                              |
               +--------------+--------------+
               | (Async Search Requests)     | (Sync Writes / Search)
               v                             v
+-----------------------------+   +-------------------------+
|         ThreadPool          |   |        HNSWIndex        | (Owns global index_lock_ shared-exclusive lock)
+-----------------------------+   +-------------------------+
               |                             |
               | (Worker Threads)            v
               |                  +-------------------------+
               +----------------->|          Node           | (Owns per-node neighbour_lock mutex and deleted atomic flag)
                                  +-------------------------+

• API / VeloxVector: The entry point exposing synchronous and asynchronous insertion, deletion, and query APIs. It coordinates execution between the index and the worker pool.
• ThreadPool: A fixed-size worker pool utilizing a bounded task queue protected by condition variables to prevent memory overflow and thread-starvation.
• HNSWIndex: The graph index structure managing HNSW layers. It maintains the global node registry and index mappings, using a read-write lock (std::shared_mutex) to protect the node registry during dynamic allocation.
• Node: Individual data nodes containing the raw vector, a multi-layer adjacency list, and a per-node mutex (std::mutex) protecting neighbor lists during Phase 2 concurrent graph modifications.

Concurrency Design

Two-Phase Locking Strategy

• Phase 1 (Global Locking): The database is synchronized using a global std::shared_mutex index_lock_. Readers (search queries) acquire a shared lock (std::shared_lock), allowing multiple searches to run concurrently. Writers (insertions/removals) acquire an exclusive lock (std::unique_lock), blocking all concurrent queries.
• Phase 2 (Fine-grained Latching): To maximize concurrency, inserts acquire the global index_lock_ as a unique_lock only for the brief duration required to append the new node to the contiguous array (preventing reallocation data races). The writer then demotes the lock to a shared_lock to perform the expensive graph navigation and connection updates concurrently with other insertions and queries. Adjacency lists for each node are individually guarded by a per-node neighbour_lock mutex.

Deadlock Prevention

During Phase 2, establishing bidirectional connections requires acquiring locks on both the new node and its neighbors. To prevent deadlocks, locks are always acquired in ascending order of their node indices. Because index indices are monotonically increasing, this guarantees a strict lock ordering across all thread insertions.

Thread Pool Coordination

The fixed-size thread pool maintains a task queue bounded to 8 * num_threads tasks. The queue is protected by a mutex and two condition variables: cv_not_empty_ blocks worker threads when there are no tasks, and cv_not_full_ blocks submitting threads when the queue is saturated, preventing unbounded memory growth under slow consumers.

Lock-Free Metrics Collection

Performance statistics (search and insert counts, latencies, and histograms) are collected without locking. Write operations modify metrics using atomic additions with std::memory_order_relaxed to eliminate thread synchronization bottlenecks. Read operations (taking a metrics snapshot) use std::memory_order_seq_cst to load values, guaranteeing a consistent global view.

Benchmark Results

Hardware Specifications

• CPU: Intel(R) Core(TM) Ultra 9 185H (16 Cores, 22 Threads)
• RAM: 32 GB LPDDR5
• OS: Windows 11 (compiled via MSYS2 GCC 15.2.0 with -O2)

Benchmark 1: Single-threaded Search Latency vs Index Size (D=128, k=10, ef=50)

Index Size (N)	HNSW Mean Latency (us)	HNSW p50 (us)	HNSW p95 (us)	HNSW p99 (us)	Flat Index Mean Latency (us)
10,000	1173.00	902.00	2406.00	3467.00	20160.30
50,000	769.71	756.00	1021.00	1486.00	16206.30
100,000	1115.57	1092.00	1367.00	1597.00	N/A (skipped)
250,000	1280.73	1138.00	2368.00	3292.00	N/A (skipped)

Benchmark 2: Search Throughput vs Thread Count (N=50k, D=128, k=10, ef=50)

Threads	Throughput (QPS)	Speedup Ratio
1 thread	817.86	1.00x
2 threads	1848.52	2.26x
4 threads	4000.80	4.89x
8 threads	8552.85	10.46x

Benchmark 3: Recall vs ef_search Trade-off (N=20k, D=128, k=10)

ef_search	recall@10	Mean Search Latency (us)
10	0.2660	110.23
20	0.3870	144.61
50	0.5980	409.57
100	0.7520	562.83
200	0.8800	1126.09

Benchmark 4: Insert Throughput (N=10k, D=128, ef_construction=40)

Threads	Phase 1 Global Lock (inserts/sec)	Phase 2 Fine-grained Lock (inserts/sec)
1 thread	5747.13	5321.98
2 threads	5711.02	5364.81
4 threads	5527.92	5461.50
8 threads	5561.74	5353.32

Benchmark 5: Mixed Workload (80% search, 20% insert, N=5k preloaded, D=128)

Locking Phase	Search Throughput (QPS)	Insert Throughput (inserts/sec)	Mean Search Latency (us)
Phase 1 (Global Lock)	6619.48	1668.07	926.13
Phase 2 (Fine-grained Lock)	9434.15	2372.14	627.99

Build and Run

Configure, compile, and execute the tests and benchmarks:

mkdir build && cd build
cmake .. -DCMAKE_BUILD_TYPE=Release
make -j$(nproc)
./tests/test_hnsw
./benchmarks/bench_search

Parameter Tuning Guide

Parameter Name	What It Controls	Increase When	Decrease When
M	Max neighbors per node per layer	Indexing higher-dimensional vectors or when high graph connectivity is required for search recall.	Low-memory constraints are active or faster indexing speed is preferred.
ef_construction	Candidate exploration size during insert	Higher search recall is desired on the constructed graph.	Indexing speed is the primary bottleneck.
ef_search	Candidate exploration size during query	High accuracy/recall is needed at runtime.	Query latency must be minimized.
num_threads	Bounded execution queue size	High concurrent search throughput is needed to utilize multicore CPUs.	System CPU resources are shared/constrained.

Design Decisions and Trade-offs

• HNSW Index over IVF: Choosing HNSW over Inverted File (IVF) index offers logarithmic query scaling and higher search recall without requiring a cluster-training step. The trade-off is higher memory overhead for storing the multi-layer neighbor graphs.
• Bounded Task Queue: Restricting the thread pool task queue prevents memory exhaustion from uncontrolled client requests. The trade-off is that submission calls will block once the queue depth limit is reached.
• Lazy Deletion: Nodes marked as deleted are retained to act as routing vectors rather than immediately rebuilding the graph layers. The trade-off is a slight increase in index size and search overhead.
• Per-Node Latching: Using individual mutexes per node instead of a striped mutex array reduces locking conflicts. The trade-off is increased memory usage for storing a std::mutex per node.