Scaling to a billion vectors: lessons from building on object storage

1 million vectors is easy. Any vector database handles it. 100 million vectors requires some thought — HNSW graphs take real time to build and real RAM to serve. 1 billion vectors reveals architectural problems that don’t exist at smaller scales.

This post is about what happens at the high end: the engineering challenges specific to billion-scale vector search, and how an object-storage-native architecture addresses them differently (and in some cases better) than traditional approaches.

The numbers at 1B vectors

1 billion 768-dimensional float32 vectors:

• Raw storage: 1B × 768 × 4B = 3TB of vector data
• HNSW graph (M=16, with neighbor lists): ~1.5TB of graph structure
• Total index size: ~4.5TB

At RAM prices ($6.79/GB/month), storing this in memory costs $30,555/month just for the hardware — before amortization, operations, replication, or profit margin. At S3 prices, it costs $103.50/month.

This cost gap is why object-storage-native vector search exists. But “store it in S3” doesn’t automatically solve the engineering challenges of serving a 4.5TB index at production latency. Let’s go through what changes at billion scale.

Problem 1: HNSW build time

Building an HNSW graph at 1B vectors is slow. The insert operation is O(log N) amortized, but the constant is not small — each insert involves an ef_construction candidate search that can touch thousands of nodes.

Benchmarks:

• 1M vectors, M=16, ef_construction=200: ~30 seconds
• 10M vectors: ~8 minutes
• 100M vectors: ~90 minutes
• 1B vectors: ~15-20 hours

15-20 hours to build an index is a problem if you need to rebuild from scratch (disaster recovery, index corruption, format migration). It’s also a problem if you want to incrementally add vectors — each insert is fast individually, but the graph needs periodic compaction to remove deleted nodes and rebalance structure.

Approaches:

Segment-based indexing. Instead of one monolithic 1B-vector HNSW graph, maintain multiple smaller HNSW graphs (segments). Each segment contains 1-10M vectors. When inserting new vectors, write to a new segment. Periodically merge segments.

ManyVector uses segments of 5M vectors by default. Building a 5M-vector segment takes ~15 minutes. Serving a billion-vector namespace means managing ~200 segments. At query time, the query goes to all segments in parallel, results are merged.

Hierarchical merging. Small segments (5M) merge into medium segments (25M) when there are 5 small segments. Medium segments merge into large segments (100M). This tiered structure limits the number of active segments to O(log N) rather than O(N/segment_size).

Incremental compaction. Rather than rebuilding the entire index, compact only the segments that have accumulated significant deletions (fragmentation above 20%). This limits the compaction window to a fraction of the total index.

Problem 2: HNSW traversal complexity

HNSW search time is O(log N) for the entry-point-finding phase and O(ef_search) for the beam search within layer 0. At 1B vectors, log N ≈ 30, so the entry-point phase is 30 hops through the upper layers.

The latency problem: each hop in the HNSW traversal is a random memory access. For an in-memory index, this is a cache miss — typically 100-200ns per hop. For 30 upper-layer hops plus the ef_search=80 beam search in layer 0: roughly 30 × 150ns + 80 × 150ns = 16.5ms just for memory access overhead, before any computation.

At 100M vectors, the upper-layer traversal is shorter (log 100M ≈ 25 hops) and the index may partially fit in L3 cache if the working set is small enough. At 1B vectors, the index definitely doesn’t fit in L3 cache.

What this means in practice:

Measured p50 latency for in-memory HNSW at billion scale: 25-60ms depending on hardware and working set locality. This is measurably worse than the sub-10ms you see in vendor benchmarks — because vendor benchmarks typically measure 10-100M vector datasets, not 1B.

Object storage approach:

ManyVector’s segment-based indexing means that any individual query searches against segments, not against a monolithic 1B-vector graph. A namespace with 200 segments of 5M vectors each has much better cache locality than a monolithic 1B graph, because the working set for any hot segment fits in L3 cache.

Hot segments are 5M vectors × 768 dims × 4B = 15.4GB. L3 cache on modern server CPUs: 64-128MB. The segment doesn’t fit in L3 either, but it’s a smaller random access pattern than a 4.5TB graph, and hot segments can be memory-mapped with readahead hints that improve effective cache hit rates.

The practical result: p50 latency for hot segments at 5M scale: 8-12ms. Even with 200-segment fan-out and result merging, total query latency is 15-25ms — competitive with in-memory monolithic HNSW at billion scale.

Problem 3: Deletions

Deletions in HNSW are hard. The graph structure doesn’t support true deletion — you can mark a vector as deleted and skip it during search, but the node remains in the graph, consuming memory and degrading search efficiency over time.

At 1B vectors with a high-churn workload (e.g., time-windowed document expiry), deletion accumulation degrades query quality. A namespace where 30% of vectors are “soft deleted” but still in the graph wastes 30% of traversal work visiting dead nodes.

Compaction. The fix is rebuilding segments that have high deletion rates. ManyVector monitors deletion rates per segment and triggers compaction when a segment exceeds 20% soft-deleted vectors. Compaction rebuilds only the affected segment (5M vectors, 15 minutes) — not the full 1B-vector namespace.

Copy-on-write advantage. Because segments are immutable content-addressed files, compaction doesn’t modify existing files. It writes a new segment file with deleted vectors excluded, then updates the namespace manifest to point to the new segment. Old segment files are garbage collected. This is safe to run concurrently with production queries.

Problem 4: Multi-namespace serving at scale

A production multi-tenant system doesn’t have one 1B-vector namespace — it has millions of smaller namespaces that sum to 1B vectors. Serving 100,000 customer namespaces with 10,000 vectors each is a different problem than serving one namespace with 1B vectors.

The in-memory approach fails here: you can’t keep 100,000 HNSW graphs in RAM simultaneously. Each 10,000-vector namespace takes ~60MB of graph structure. 100,000 × 60MB = 6TB of RAM just for namespace overhead, before the vectors themselves.

The object-storage approach works naturally: namespace segments live in S3. Only queried namespaces occupy RAM cache. LRU eviction ensures that inactive namespaces don’t consume cache. The working set in cache at any time is proportional to the number of concurrently active namespaces, not the total namespace count.

At 100,000 namespaces with a 5% active rate at any time: 5,000 active namespaces × 60MB = 300GB of cache. Much more tractable.

Problem 5: Backup and restore

Backing up a 4.5TB in-memory index is operationally painful. Typical approaches:

• Snapshot RAM to disk: requires the servers to be quiesced or have snapshot hardware support
• Export vectors: re-export all 1B vectors, store on disk, rebuild index from scratch to restore

At ManyVector, backup and restore have a fundamentally different implementation:

Backup: The index is already on S3. Backup = point-in-time snapshot of the namespace manifest. Creating the snapshot is a single lightweight API call. The underlying data is already durable (S3 has 11 nines of durability).

Restore: Point the namespace manifest at a previous snapshot version. The restoration is instantaneous from the query layer’s perspective. Old segment files are still on S3 (retention policy determines how long they’re kept).

For disaster recovery, ManyVector’s recovery point objective is determined by S3’s durability guarantees (essentially infinite, given 11 nines). Recovery time objective is seconds — just update the manifest pointer.

Practical scale guidance

Dataset size	Architecture recommendation
< 5M vectors	Any vector database works, cost is not the issue
5M - 50M vectors	Object storage starts to win on cost; in-memory fine on latency
50M - 500M vectors	Object storage significantly cheaper; latency comparable
> 500M vectors	In-memory becomes operationally painful; object storage is the right choice
Multi-tenant (many small namespaces)	Object storage wins at any scale due to idle capacity

The billion-vector threshold is where the architectural advantages of object-storage-native systems compound: lower storage cost, simpler disaster recovery, no capacity planning, and natural multi-namespace serving.

Conclusion

Building for billion-scale vector search reveals that the “just put it in RAM” approach is a scaling cul-de-sac. The costs compound, the operational complexity grows, and the latency improvements diminish as the dataset size exceeds what fits comfortably in cache.

The object-storage-native approach solves billion scale by:

• Segmented HNSW with hierarchical compaction instead of monolithic graphs
• LRU caching of hot segments instead of all-in-RAM serving
• S3-backed snapshot and restore instead of RAM-to-disk exports
• Per-namespace isolation at zero overhead for cold namespaces

If you’re designing a system today that will need to scale to hundreds of millions or billions of vectors, build the architecture for the destination, not the starting point.