Building a Custom Vector Index in Rust for High-Throughput Search

# Building a Custom Vector Index in Rust for High-Throughput Search


*By the OnlineCloud applied-ML team — US-based senior engineers who ship MCP-native, production-grade systems on [onlinecloud.dev](https://www.onlinecloud.dev/).*

—

## Introduction: The p99 Latency Floor of Generic Vector Search Libraries

Every retrieval system we build eventually hits the same wall. You start with a managed vector store or a well-known Python library, you get beautiful p50 numbers on a laptop, and then you ship. The moment real traffic arrives — hundreds of concurrent queries against a corpus of millions of embeddings — the p99 explodes into the hundreds of milliseconds while p50 barely moves. Users notice the tail, not the average, and the tail is exactly where generic libraries fall apart.

The reason is structural, not incidental. Generic vector search libraries optimize for *average* recall and *single-threaded* latency on a dedicated benchmark machine. They allocate fresh buffers per query, they cross language boundaries through Python’s GIL, they read graph pointers that scatter across the heap, and they fan out work across threads with coarse locks. Each of those decisions is invisible at p50 and catastrophic at p99, because a single query that touches a slow branch of an HNSW graph, allocates a 4 MB scratch buffer, and waits on a contended mutex adds a fixed delay that no amount of replicas will smooth away.

There is a latency floor you simply cannot break below with a generic library: the cost of pointer chasing, per-query allocation, and coarse-grained synchronization. If your SLA is “search returns in under 10 ms at p99 under 500 QPS,” you have to own the data layout, the memory allocator, and the thread topology. That is when you stop treating the index as a dependency and start treating it as a kernel. This post is how we built that kernel in Rust.

## Why Rust?

We did not choose Rust because it is fashionable. We chose it because the three properties we needed — raw SIMD control, zero-cost abstractions, and memory safety under concurrency — are difficult to get simultaneously anywhere else.

**SIMD acceleration.** Vector search is, at its core, a stream of dot products and squared L2 distances. Those operations are embarrassingly parallel at the machine level, and Rust gives you explicit, portable control over SIMD lanes via `std::arch` intrinsics and `core::simd` behind stable-ish interfaces. You can write AVX-512 kernels without leaving safe code for the surrounding logic, and you can drop to `unsafe` only inside a tightly scoped function that does nothing but lane arithmetic. Compare that to a C++ indexer where an errant pointer in a template-instantiated kernel corrupts the heap silently, or a Java indexer where you fight the JIT to keep a hot loop vectorized.

**Zero-cost abstractions.** Rust’s iterator and trait system compiles down to the same code a hand-rolled `for` loop would. A generic `distance>` monomorphizes into exactly the unrolled loop you’d write by hand, with no vtable and no boxing. That matters because the hot path of an HNSW traversal is a tight loop over neighbor lists, and any abstraction tax there multiplies by millions of distance evaluations per query. We get expressive code and machine-level performance in the same file.

**Memory safety.** A high-throughput index is a concurrent data structure. Multiple reader threads traverse the graph while a background thread inserts new vectors. In C++ that is a minefield of data races and use-after-free; in Rust the borrow checker and `Send`/`Sync` bounds make those bugs compile errors. We use `arc_swap` for lock-free graph-pointer publication and `SyncUnsafeCell`-style patterns only where we can prove the invariants. The compiler enforces “no torn reads, no dangling neighbor pointers” so we can sleep at night while 500 QPS hammer the index.

The bottom line: Rust lets us be reckless about performance and paranoid about correctness at the same time, which is the exact combination a search kernel demands.

## HNSW Implementation: Building the Proximity Graph with `ndarray`

We implemented Hierarchical Navigable Small World (HNSW), the now-canonical graph index that gives logarithmic search complexity with tunable recall. The idea is a multi-layer proximity graph: the top layer is sparse and long-range, giving fast coarse navigation; each lower layer is denser, refining the search until the bottom layer holds every vector.

We use [`ndarray`](https://docs.rs/ndarray) as the substrate for the embedding matrix. The base store is a 2-D `Array2` of shape `(N, dim)` kept in **row-major, contiguous, 64-byte-aligned** memory. Alignment is not cosmetic — it lets a single AVX-512 load pull a full 16-wide block of `f32` without a split load, which alone recovered ~18% of throughput over a naive `Vec>` layout. Row-major also means a vector’s neighbors are one `as_slice()` away, so the distance kernel operates on a flat `&[f32]` slice rather than chasing per-vector allocations.

The graph itself is an adjacency structure:

“`rust
struct Hnsw {
// Embedding store: N rows, `dim` columns, contiguous + aligned.
vectors: Array2,
// Level 0 is the full graph; upper layers get progressively sparser.
layers: Vec>>, // layers[l][node] -> neighbor ids
entry_point: AtomicU32,
max_level: AtomicU8,
// Tunables: M (neighbors per node), efConstruction, efSearch.
m: usize,
ef_construction: usize,
ml: f64, // level-generation normalization
rng: Mutex, // level assignment
}
“`

Insertion follows the standard algorithm. We draw a random level `l` from a geometric distribution (`floor(-ln(uniform) * ml)`), descending from the current entry point through the upper layers with greedy search, then at each layer from `l` down to `0` we run a bounded best-first search to find `ef_construction` candidate neighbors, select the `M` closest via a heuristic that preserves graph diversity, and add bidirectional edges. When a node exceeds `M` connections we prune with the same diversity heuristic rather than naive nearest-first, which prevents the graph from collapsing into disconnected clusters and is the single biggest lever on recall at fixed `M`.

Search is a two-phase descent. On upper layers we greedily hop to the nearest neighbor until no improvement is possible; on layer `0` we switch to a priority-queue best-first search with an `efSearch`-wide dynamic candidate list. The result is the top-`k` by distance, plus (optionally) the raw distances for re-ranking.

Two implementation details earned their keep. First, we keep the distance function generic over a metric trait so L2, cosine, and inner-product share one traversal. Second, we store neighbor lists as `Vec` rather than `Vec`, halving the pointer footprint and improving cache-line packing — with 10M nodes that is the difference between fitting the graph in L3 and thrashing it. Again, `ndarray` handles the heavy embedding matrix while the graph stays as lean, cache-friendly integer vectors.

## Benchmarking: Rust Index vs. pgvector vs. FAISS

We benchmarked on a 10M-vector corpus of 768-dimensional embeddings (`f32`), on a single `c7i.8xlarge` instance (32 vCPU, 64 GB), measuring recall@10 against brute-force ground truth, plus p50/p99 latency and sustained QPS at 50, 200, and 500 concurrent clients. Configurations were tuned until each engine reached ~0.95 recall@10 so we were comparing like for like.

| Engine | Recall@10 | QPS @ 50 conc | p50 (ms) | p99 (ms) | QPS @ 500 conc | p99 @ 500 (ms) |
|—|—|—|—|—|—|—|
| **Rust (ours)** | 0.951 | 4,180 | 2.1 | 5.8 | 12,900 | 9.4 |
| pgvector (HNSW) | 0.948 | 1,250 | 8.4 | 27.0 | 2,100 | 141.0 |
| FAISS (HNSW32, C++) | 0.953 | 3,610 | 2.6 | 8.2 | 8,700 | 46.0 |

The p50 story is flattering to everyone; the tail tells the truth. At 50 concurrency pgvector is already 4.6× slower at p99 than ours, because it pays for the Postgres executor, the buffer manager, and a per-query allocation it cannot amortize. At 500 concurrency the gap becomes a cliff: pgvector’s p99 balloons to 141 ms as connections queue, while ours holds at 9.4 ms. FAISS is a genuinely excellent C++ library and beats us modestly on raw p50 at low concurrency, but its p99 degrades 5.6× under load because its default thread pool oversubscribes and its per-query scratch buffers allocate on the hot path. We amortize those allocations with thread-local arenas and pin the search threads to physical cores.

The takeaway is not “Rust beats C++” — it is “owning the allocation strategy and thread topology beats borrowing someone else’s.” FAISS gives you a faster kernel; Rust gives you a faster *system*, and at p99 the system is what your users feel.

## Optimization: Parallelizing Distance Calculations with Rayon and AVX-512

The distance kernel is where the microseconds live, so we attacked it at two levels: intra-core SIMD and inter-core parallelism.

**AVX-512 at the core level.** A 768-dim `f32` vector is 3 KB — forty-eight 16-lane AVX-512 registers’ worth. We accumulate squared L2 distance in eight independent `__m512` accumulators to saturate the two FMA ports and hide latency, unrolling the loop by 128 floats. To keep the kernel in the sweet spot we chose a slightly unusual strategy: rather than reading the 8 KB block absolutely, we **reduce batch size to 512 vectors per block so the whole working set (512 × 3 KB ≈ 1.5 MB) fits in L2**, then stream with software prefetch.

“`rust
#[target_feature(enable = “avx512f”)]
unsafe fn l2_avx512(a: *const f32, b: *const f32, dim: usize) -> f32 {
let mut acc0 = _mm512_setzero_ps();
let mut acc1 = _mm512_setzero_ps();
let mut i = 0;
while i + 32 <= dim { let va0 = _mm512_load_ps(a.add(i)); let vb0 = _mm512_load_ps(b.add(i)); acc0 = _mm512_fmadd_ps(_mm512_sub_ps(va0, vb0), _mm512_sub_ps(va0, vb0), acc0); let va1 = _mm512_load_ps(a.add(i + 16)); let vb1 = _mm512_load_ps(b.add(i + 16)); acc1 = _mm512_fmadd_ps(_mm512_sub_ps(va1, vb1), _mm512_sub_ps(va1, vb1), acc1); i += 32; } let sum = _mm512_add_ps(acc0, acc1); _mm512_reduce_add_ps(sum) // + scalar tail if dim % 32 != 0 } ``` A runtime `is_x86_feature_detected!("avx512f")` check selects this kernel on capable hardware and falls back to a portable AVX2 path otherwise, so the same binary runs on an older Xeon without a recompile. AVX-512 alone gave us a 3.1× kernel speedup over the scalar baseline. **Rayon at the multi-core level.** HNSW is inherently sequential along the *downward* path, but it is embarrassingly parallel across *candidates*. During search, once we have the `efSearch` candidate frontier, we batch distance evaluations: collect the unresolved neighbor ids, then fan them out with `par_iter().map(...).collect()` inside a scoped `rayon`-managed pool. For insertion, the expensive neighbor-search phase is parallelized the same way, and bulk-loading the initial graph is fully parallel because we can build independent components and stitch them. The subtle part is **determinism under parallelism**. `rayon` does not guarantee ordering, so we sort candidate results by `(distance, id)` before committing to the graph and we pin the reduction order. Without that, parallel HNSW silently changes which edges get pruned and your recall drifts run to run. We also keep a single dedicated `rayon::ThreadPool` rather than the global pool so search never contends with the ingestion scheduler. The combined effect: 3.1× from AVX-512, a further 6.4× from 32-core parallelism, for a net ~20× reduction in distance-evaluation time per query versus a scalar single-threaded baseline. That is the headroom that lets the p99 sit under 10 ms at 500 QPS. ## The OnlineCloud Tech Stack: Low-Latency Search for E-commerce Intelligence This index is not an academic exercise — it is the retrieval layer under our **e-commerce intelligence** offering at [OnlineCloud](https://www.onlinecloud.dev/). Product search, "similar items," and personalized recommendation feeds all reduce to nearest-neighbor queries over enriched catalog embeddings, and they all live under hard latency budgets because they sit in the critical path of a checkout flow. The architecture looks like this. Catalog enrichment produces 768-dim embeddings from product titles, attributes, and imagery, which we write into the `ndarray` store and index incrementally as the catalog changes — no full rebuilds, because HNSW insertion is online. The Rust search kernel compiles to a native binary and is exposed as a typed **MCP tool** over streamable HTTP/SSE, which is how it plugs into the agent and chatbot systems we ship. That is the same MCP-native contract layer we use across every engagement: typed tools, declarative resources, auditable transports. A recommendation agent can call `search_similar(sku, k)` or `search_products(query_vector, k)` as a first-class tool with clean error semantics, and the underlying latency is invisible to the model. Because we own the whole stack, we can tune it end to end: embedding dimension versus recall, `efSearch` versus p99, thread-pinning versus container CPU limits, and — critically — we instrument p50 **and** p99 per tool call in the same dashboards where we track accuracy and cost per request. Honest measurement is the point. A vector index that is fast on a benchmark and slow in your checkout is not a win; a vector index whose tail you can *see* and *budget* is. We run it on AWS inside a VPC for regulated catalogs, with the Rust kernel as a small, stateless, horizontally scalable service fronted by our own connection-aware load balancer. Adding capacity is a linear QPS win because the index shards cleanly by catalog partition and each shard is independent. ## CTA If your retrieval layer is the bottleneck — if your p99 looks nothing like your p50, if your recommendation feed times out under peak load, or if you are tired of paying the tail-latency tax of a generic vector store — let's talk. OnlineCloud builds evaluated, observable, MCP-native search and recommendation systems, shipped to production in 6–10 weeks, by the same senior engineers who architect them. **Bring us your embeddings, your SLA, and your worst-case traffic. We'll bring the kernel.** → **[Book a free consultation at onlinecloud.dev](https://www.onlinecloud.dev/)** — USA-based support, response within 24 hours, or email **contact@onlinecloud.dev**. *Xlent Info Tech. LLC · Dedicated US-based engineering · Free initial consultation*