Vector Database System Design Template

System Design: [Vector database name]

Reference design for a vector database that stores embeddings with metadata and answers approximate nearest neighbour (ANN) queries with filters: index choice between HNSW (Malkov and Yashunin, IEEE TPAMI 2020) and IVF with product quantization (Jégou, Douze and Schmid, IEEE TPAMI 2011), filtered search, inserts and deletes on a live index, sharding, replication, and the recall versus latency trade-off. It follows the structure of the System Design Document template, adds a 45-minute interview path, access-pattern and failure-mode tables and a cited "How real systems do it" box, and is pre-filled with a worked design to adapt. Replace every [bracketed] value and every row marked Example; values marked Example are assumptions, not benchmarks. Recall and latency figures must come from your own measurements on your own data.

Document control

Approvals

Revision history

Contents

1. Overview
2. Requirements
3. Capacity estimation
4. API design
5. Data model
6. High-level design
7. Detailed design
8. Scalability and performance
9. Reliability, security and operations
10. Trade-offs and alternatives
11. Delivery plan and risks
12. Appendices

1. Overview

1.1 Problem statement

[Example: Our document assistant stores 500 million passage embeddings in a general-purpose database extension with an HNSW index on one large machine. Memory is at 92%, index rebuilds take two days, and a query filtered to one customer's documents often returns fewer than 10 results because the filter runs after the index search. Deleted documents keep appearing in answers for hours, which is a privacy problem.]

1.2 Proposed solution

[Example: A dedicated vector service shards collections by vector ID across 8 shards with 2 replicas each. Large collections use an IVF index with product-quantized codes in memory and full vectors on local NVMe for re-ranking; small collections use HNSW in memory. Inserts go to a write-ahead log and an in-memory buffer that is searched exactly, then merge into the main index every hour. Deletes are tombstones applied at query time and removed by compaction. Each query picks a filter strategy from the estimated selectivity of its filter. Tenants are separate partitions, so a tenant filter never scans other tenants' data. Recall is measured continuously against exact search on sampled queries.]

1.3 Decisions requested from reviewers

1.4 45-minute interview path

Use this order when the document serves an interview or a short design review. The written sections below are the long form of each step.

Start the default deep dive with the naive answer, exact search (compare the query with every vector). Show its cost: 500 million x 768 multiply-adds per query. Then introduce HNSW, compute its memory, and move to IVF-PQ with re-ranking when the memory does not fit.

2. Requirements

2.1 Core functional requirements

2.2 Non-functional requirements

2.3 Below the line (out of scope)

Name these explicitly so reviewers and interviewers do not pull the design toward them.

• [Example: generating embeddings (the caller sends vectors)]
• [Example: keyword search and rank fusion (see Full-Text Search Engine System Design (system-design/design-full-text-search))]
• [Example: document chunking and prompt assembly (see Enterprise RAG Search System Design (system-design/design-enterprise-rag-search))]
• [Example: GPU-based search]
• [Item deferred, with the release that will take it]

3. Capacity estimation

3.1 Assumptions

3.2 Memory by index family

Raw vectors:

HNSW, using the Faiss wiki estimate of $d \times 4 + M \times 2 \times 4$ bytes per vector:

IVF-PQ codes plus an 8-byte ID:

PQ compresses each vector $3\,072 / 96 = 32$ times. The full vectors stay on NVMe (192 GB per shard) for re-ranking. Consequence: HNSW for this collection would need 20 large-memory nodes with two replicas; IVF-PQ fits in a fraction of one node's memory per shard, so the cost moves from RAM to NVMe reads.

3.3 Work per query

Each shard holds $62.5$ million vectors and an IVF with $K = 262\,144$ lists (the Faiss wiki suggests this list count for 10 to 100 million vectors). Probing $n_{probe} = 64$ lists scans:

Each code is scored with a lookup table of $96 \times 256 \times 4$ bytes (about 98 KB per query per shard). Each shard then re-ranks its best 100 candidates with full vectors read from NVMe: 100 reads of 3 KB, one 4 KB page each. With 2 replicas sharing the 2 000 queries/s:

That is within one data-centre NVMe drive's random-read capability, but not with much headroom, which is why re-rank depth is a tuning knob in 7.3.

3.4 Writes

Inserts average $5 \times 10^{6} / 86\,400 \approx 58$ per second (about 7.2 per shard) and deletes about 12 per second. An hour of inserts per shard is about 26 042 vectors (80 MB), which an exact scan covers in about 2 ms at an assumed 20 GFLOP/s, so a flat buffer is enough for fresh data (7.5).

3.5 Summary

4. API design

4.1 Endpoints

Errors use problem details (RFC 9457). A query with a vector of the wrong dimension returns 400; a query against a collection whose model version differs from the caller's declared version returns 409.

4.2 Query example

{"vector": [0.0132, -0.0871, 0.0419], "k": 10, "filter": {"and": [{"tenant": {"eq": "t_2207"}}, {"lang": {"in": ["en", "de"]}}, {"created_at": {"gte": "2026-01-01"}}]}, "params": {"nprobe": 64, "rerank": 100}, "min_seq": 88412093, "include": ["score", "metadata"]}

The vector is shortened here to three values; a real request carries all 768.

{"results": [{"id": "doc-7731#p4", "score": 0.8412, "metadata": {"lang": "en"}}, {"id": "doc-0918#p1", "score": 0.8377, "metadata": {"lang": "de"}}], "strategy": "filtered_traversal", "shards": 8, "took_ms": 23}

5. Data model

5.1 Entities

A collection is split into partitions (one per tenant), each partition into shards, and each shard into segments: one growing buffer and several sealed, indexed segments.

5.2 Storage choices

5.3 Access patterns

6. High-level design

7. Detailed design

The deep dives in this section, each with options, choice and reason:

7.1 Exact search as the baseline

Exact search compares the query with every vector. For one shard of 62.5 million vectors at $d = 768$ that is about $62.5 \times 10^{6} \times 768 \times 2 \approx 96$ GFLOP per query, seconds of CPU time. It stays in the design for two jobs: searching the small growing buffer, and producing the ground truth that recall is measured against (NFR-01).

7.2 Index families

HNSW in brief (Malkov and Yashunin, 2020): each vector gets a random top layer drawn with an exponentially decaying probability; with the usual normalisation $m_L = 1/\ln M$, the share of vectors that reach layer 1 or above is $1/M$ (about 3.1% for $M = 32$), and the number of layers grows with $\ln N / \ln M$, about 5.2 for one shard of 62.5 million vectors. Search starts at the top layer and descends greedily, then explores efSearch candidates on the bottom layer. Larger efSearch gives higher recall and higher latency.

Product quantization in brief (Jégou, Douze and Schmid, 2011): the vector is split into $m$ sub-vectors, each replaced by the index of its nearest centroid in a 256-entry codebook, so a 768-dimension float vector becomes 96 bytes. Distances to a query are computed from a per-query lookup table (asymmetric distance computation), which is why the codes never need to be decompressed. PQ distances are approximate, so the best candidates are re-ranked with the full vectors.

Choice: the 500-million-vector collection uses IVF with $K = 262\,144$ lists per shard, PQ with 96 bytes per vector, and re-ranking of 100 candidates per shard from NVMe. Collections under about 20 million vectors (about 67 GB in HNSW) use HNSW in memory. Training needs at least $30 \times K \approx 7.9$ million sample vectors per shard (Faiss wiki guidance of 30 to 256 times the list count); the codebooks are trained once per collection version.

7.3 Recall versus latency

Three knobs move the trade-off: $n_{probe}$ (lists scanned), re-rank depth, and for HNSW efSearch. Fill the measured columns from your own benchmark with the exact path as ground truth:

Pick the smallest setting that meets NFR-01 on the 5th percentile of per-query recall, not only the mean: average recall can hide a class of queries (for example short queries or a rare language) that fail badly. Re-check after every embedding model change, every codebook retrain and every large shift in the data.

7.4 Filtered search

With filter selectivity $s$ (the share of vectors that pass), a post-filter must fetch about $k/s$ candidates to keep $k$ results. For $N$ = 500 million and 8 shards:

The planner estimates $s$ from per-segment field statistics and picks the strategy; the response reports which one ran so slow queries can be explained. Graph indexes lose connectivity when most nodes fail the filter, which is why research such as Filtered-DiskANN (WWW 2023) and ACORN (SIGMOD 2024) builds filter awareness into the graph. Tenants are never a filter: each tenant is a partition, so the most common and most important filter costs nothing and cannot leak (NFR-06).

The thresholds 0.002 and 0.3 are Example values; set them from a benchmark on your data.

7.5 Inserts, deletes and freshness

1. An upsert is written to the shard's WAL and acknowledged with its sequence number.
2. Each replica applies the WAL to its growing buffer (flat, searched exactly) within 1 s. A replaced ID gets a tombstone in its old segment.
3. Every hour the builder encodes the buffer (about 26 000 vectors per shard) with the existing codebooks and appends the codes to their IVF lists in a new segment version; the buffer is then cleared. Queries switch to the new version atomically.
4. A delete sets a tombstone bit immediately, so the vector disappears from results within 1 s (NFR-04). Compaction rewrites a segment when its deleted share passes 20%; at 1 million deletes a day spread evenly over 500 million vectors that takes about 100 days, but deleting a tenant drops its partition at once.
5. Codebooks are retrained when recall on the sampled queries drifts below target, by building a new collection version in the background.

min_seq gives read-your-writes: a replica that has not applied that sequence number waits up to 200 ms or the router tries another replica.

7.6 Sharding and replication

Vectors are assigned to shards by hash of their ID inside each tenant partition, so every shard holds a similar slice of every large tenant and queries fan out to all shards. Fan-out multiplies the work per query, but it keeps shard sizes even and lets any shard answer for any query. Each shard has 2 replicas behind the router; the router sends each query to one replica per shard, hedges after the shard's p95 latency, and merges the top-k lists. The tail latency of a query is the slowest shard's latency, so per-shard p99 must sit well below the end-to-end target.

7.7 How real systems do it

How real systems do it (paraphrased, not copied). The Milvus paper (Wang and others, "Milvus: A Purpose-Built Vector Data Management System", SIGMOD 2021) describes inserts held in memory and flushed as immutable segments when a size threshold is reached or every second, small segments merged into larger ones under a tiered policy, deletes handled out of place and removed at merge time, and indexes built only for large segments. Each query runs on a snapshot of the current segments, so writes do not disturb running queries. For attribute filters the paper compares attribute-first scans, attribute bitmaps checked during vector search, vector-first search followed by an attribute check, and a cost-based choice between them, and adds a partition-based method on frequently filtered attributes that its experiments found faster than the cost-based one. The Faiss wiki "Guidelines to choose an index" gives the memory estimate used in 3.2 and list-count guidance by dataset size. Read the originals in 12.3; this box keeps only the general ideas.

8. Scalability and performance

Latency budget for a query (target p99 50 ms):

9. Reliability, security and operations

9.1 Failure modes

9.2 Security and privacy

9.3 Observability

9.4 Cost estimate

10. Trade-offs and alternatives

11. Delivery plan and risks

11.1 Milestones

11.2 Rollout and rollback

[Example: Dual-write to the old and new stores, compare top-10 overlap on shadow queries for 14 days, then move read traffic per tenant in steps. Rollback points reads back to the old store while dual writes continue.]

11.3 Risks

12. Appendices

12.1 Open questions

12.2 Glossary

12.3 References

Standard and licence note

Based on the published research cited in 12.3 (HNSW, product quantization, filtered ANN search, the Milvus and Faiss papers) and on common industry practice for vector search services. No standard governs this design. The papers and the Faiss wiki are paraphrased only; no text, figures or code were copied. Capacity figures are computed from the stated example inputs, and recall and latency must be measured on your own data. Original text written for this collection. Template licence: MIT.