Design a Vector Database

Teams across the company are building semantic search, recommendations and retrieval-augmented chat. All of them need to store embeddings and ask "which stored vectors are closest to this one?" in a few milliseconds. Design a managed vector database they can share.

A single collection can hold a billion 768-dimensional vectors. Exact nearest-neighbour search over that is far too slow, so you will trade a little accuracy for a lot of speed, and you need to explain that dial. Users also want to filter ("only documents in German from this tenant"), to update and delete vectors and see the change within seconds, and to keep serving while indexes rebuild.

In 45 minutes, cover the index structure, how data is sharded and replicated, how queries with filters are executed, how writes and deletes reach an index that is expensive to modify, and how you balance recall, latency and memory cost.

Sketch on the HLD board, write your answer in the Design doc, and size it with the Estimator. Start the mock interview from the timer for a 45-minute run.

Design Path · AI & ML Systems · problem 53 of 70

Ask before you design. Try answering each yourself, then compare.

1. How large are collections and vectors?
   Typical answer

   The largest is ~1 B vectors of 768 float32 dimensions; most are 1–50 M. Each vector carries a few metadata fields.

2. What query load and latency?
   Typical answer

   ~5,000 queries/s peak across the cluster for the large collection, top-10, p99 under 50 ms.

3. What accuracy is acceptable?
   Typical answer

   Recall@10 of at least 0.95 against exact search by default; callers can ask for faster and less accurate.

4. How often do vectors change?
   Typical answer

   ~10 M upserts or deletes a day, peaking at ~1,000/s. A write should be searchable within ~5 s.

5. Which distance metrics?
   Typical answer

   Cosine and dot product; L2 as well. Vectors are usually normalized.

6. Is multi-tenancy needed?
   Typical answer

   Yes: many small tenants share a collection, and a tenant must only ever see its own vectors.

Requirements

Functional

• Create collections with a dimension, metric and metadata schema.
• Upsert and delete vectors by id with metadata.
• Query top-k nearest neighbours with optional metadata filters.
• Per-query accuracy/latency knob; tenant isolation.

Non-functional

• 1 B vectors per collection; 5,000 QPS; p99 < 50 ms at recall@10 >= 0.95.
• Writes visible to queries within 5 s; acknowledged writes are durable.
• 99.95% query availability; node loss must not lose data or stop queries.
• Memory cost per vector kept within a stated budget (quantization allowed).

Out of scope

• Generating embeddings (callers send vectors).
• Full SQL or joins over metadata.
• Cross-collection transactions.

Back-of-the-envelope estimates

• Raw vectors: 1 B × 768 × 4 B ≈ 3 TB. With an HNSW graph (~32 neighbours at the base layer × 4 B ≈ 128–256 B per vector) it is ~3.3 TB.
• Memory plan A, full precision in RAM: ~3.3 TB / ~200 GB usable per node ≈ 17 shards, ×3 replicas ≈ 51 large-memory nodes.
• Plan B, compressed: int8 scalar quantization cuts vectors to ~770 GB; product quantization to 96 B/vector gives ~100 GB, with full vectors kept on SSD to re-rank the top ~100. Roughly 4–6 shards × 3 replicas.
• Queries: 5,000 QPS scattered to every shard. If one HNSW search at ef=128 costs ~2 ms of a core, each shard does 5,000 × 2 ms = 10 core-seconds per second, i.e. ~10 busy cores per shard, spread over its replicas.
• Writes: 10 M/day ≈ 115/s average, 1,000/s peak: easy for a log, hard for a graph index that is slow to mutate.

Memory per vector is the number that drives cost, and the write/delete path into immutable index segments is what drives the architecture.

API

PUT    /collections/{c}            {dim, metric, index: hnsw|ivf_pq, schema}
POST   /collections/{c}/upsert     {items:[{id, vector, metadata}]}   -> {seq}
POST   /collections/{c}/delete     {ids[] | filter}                   -> {seq}
POST   /collections/{c}/query      {vector, k, filter?, tenant,
                                    ef? | nprobe?, consistency: eventual|after_seq}
       -> {matches:[{id, score, metadata}]}

Writes return a sequence number, and a query can pass after_seq to get read-your-writes on demand, so most queries stay fast and eventual while the few that need freshness can ask for it.

Data model

A collection is split into shards by hash of vector id (or by tenant for very large tenants). Each shard is an LSM-like set of segments: one small mutable segment searched by brute force, and many sealed, immutable segments each with its own HNSW or IVF-PQ index, a column store of metadata, bitmap indexes on filterable fields, and a tombstone bitmap for deletes.

The per-shard write-ahead log is the source of truth for recent writes. Sealed segments and their built indexes are persisted to object storage, so replicas and replacements load files instead of rebuilding. Cluster metadata (collections, schemas, shard → node assignments, segment lists) lives in a small consensus-backed key-value store because it must be strongly consistent and is tiny.

High-level design

Write path: a client sends an upsert to the write API, which validates dimension and schema, picks the shard from the id hash, appends to that shard's replicated write-ahead log and acknowledges with a sequence number. Shard replicas tail the log and add the vector to their mutable segment, usually within a second. When the mutable segment reaches a size threshold (say 1 M vectors), it is sealed and flushed to the segment store; the index builder builds an HNSW graph for it off the serving nodes, and the shards load the finished index. The builder also merges small segments and drops tombstoned vectors during compaction. A delete is just a log entry that sets a tombstone bit.

Read path: the query router fetches the collection's shard map from the control plane (cached), sends the query vector and filter to one replica of every shard, and waits. Each shard searches all its segments in parallel, applies the filter and tombstones during traversal, and returns its local top-k with scores. The router merges these into the global top-k. Replicas multiply query throughput; shards bound memory per node and per-query latency. Tenant id is a mandatory filter added by the router, never trusted from the caller.

Open the HLD board and press Reference to see the architecture diagram.

Deep dives

Choosing the index: HNSW vs IVF-PQ

HNSW builds a layered proximity graph; a query greedily walks from a sparse top layer down to dense neighbours. It gives excellent recall at low latency and tolerates inserts, but needs the vectors and graph in RAM and is costly to build (hours for hundreds of millions). IVF clusters vectors with k-means and searches only the nprobe nearest clusters; combined with product quantization, each vector shrinks to tens of bytes, so billions fit in memory, at lower raw recall that you recover by re-ranking the top few hundred with full vectors from SSD. Offer both: HNSW for latency-critical collections up to hundreds of millions, IVF-PQ for very large or cost-sensitive ones. The dial is ef_search or nprobe, settable per query.

Filtering without killing recall

Post-filtering (search top 100, then filter) collapses when the filter is selective: a 0.1% filter leaves nothing. Pre-filtering (compute the matching id set, then search only it) is exact, but a graph walk restricted to a sparse subset gets disconnected and slow. A small planner decides per segment using the filter's estimated selectivity from bitmap indexes: very selective (under ~1–2%) means brute-force the matching vectors directly, which is cheap because there are few; moderately selective means traverse the graph while skipping non-matching nodes but still using them for navigation, with a larger ef. For tenants, physically partition large tenants into their own segments so filters become routing, not scanning.

Updates and deletes on immutable indexes

Treat indexes like an LSM tree. New writes land in a small mutable segment that is searched exhaustively (1 M vectors brute force is a few ms with SIMD), so writes are visible within seconds without touching big graphs. An update is a delete plus an insert. Deletes set a bit in each segment's tombstone bitmap, checked during search. When tombstones in a segment exceed ~10–20%, recall and speed degrade, so compaction rebuilds the segment without them. Because building is CPU-heavy, the builder runs on separate machines and publishes finished segment files; serving nodes swap them in atomically by updating the segment list in cluster metadata.

Sharding, fan-out and tail latency

Hash sharding by id balances data and load evenly but forces every query to visit every shard, so p99 is set by the slowest shard. Keep shard count modest (tens, not hundreds), use replicas for throughput, and hedge: if a shard has not answered by the p95 time, send the same request to another replica. Each shard returns a slightly larger local k (for example 2k) to keep the merged result accurate. Semantic partitioning (route queries only to shards whose centroids are near) cuts fan-out but skews load toward popular regions of the space, so it fits archival or batch use better than interactive search.

Failure modes

• If a shard replica dies, the router uses another replica; a replacement loads segments from object storage and replays the log tail, without rebuilding indexes.
• If the index builder falls behind, mutable and small segments accumulate and queries slow down; cap the number of unindexed segments and throttle writes before latency breaches the SLO.
• If a whole shard is unavailable, return partial results with a flag (or fail, per collection setting) instead of hanging.
• If a bad index build degrades recall, keep the previous segment set and roll back the segment list; recall is checked on a sample before publishing.

Core algorithm in code

import random


def dist2(a, b):
    return sum((x - y) ** 2 for x, y in zip(a, b))


class IVFIndex:
    def __init__(self, nlist):
        self.nlist = nlist
        self.centroids = []
        self.lists = []                 # per centroid: list of (vid, vec, tags)
        self.tombstones = set()

    def train(self, sample, iters=6, seed=1):
        rng = random.Random(seed)
        self.centroids = rng.sample(sample, self.nlist)
        for _ in range(iters):
            groups = [[] for _ in range(self.nlist)]
            for v in sample:
                groups[self._nearest(v, 1)[0]].append(v)
            for i, g in enumerate(groups):
                if g:
                    self.centroids[i] = [sum(c) / len(g) for c in zip(*g)]
        self.lists = [[] for _ in range(self.nlist)]

    def _nearest(self, v, n):
        order = sorted(range(len(self.centroids)), key=lambda i: dist2(v, self.centroids[i]))
        return order[:n]

    def add(self, vid, vec, tags):
        self.lists[self._nearest(vec, 1)[0]].append((vid, vec, tags))

    def delete(self, vid):
        self.tombstones.add(vid)

    def search(self, q, k, nprobe, tag=None):
        cands, work = [], len(self.centroids)
        for li in self._nearest(q, nprobe):
            for vid, vec, tags in self.lists[li]:
                if vid in self.tombstones or (tag and tag not in tags):
                    continue                  # filter applied during the scan
                work += 1
                cands.append((dist2(q, vec), vid))
        cands.sort()
        return [vid for _, vid in cands[:k]], work


rng = random.Random(42)
DIM, NUM, K = 16, 4000, 10
centers = [[rng.gauss(0, 4) for _ in range(DIM)] for _ in range(40)]
data = {}
for i in range(NUM):
    c = rng.choice(centers)
    data[i] = ([x + rng.gauss(0, 1) for x in c], {"lang:en" if i % 4 else "lang:de"})

idx = IVFIndex(nlist=64)
idx.train([v for v, _ in list(data.values())[:1500]])
for vid, (v, tags) in data.items():
    idx.add(vid, v, tags)

queries = [[x + rng.gauss(0, 1) for x in rng.choice(centers)] for _ in range(30)]


def exact(q, tag=None):
    ok = [(dist2(q, v), vid) for vid, (v, t) in data.items()
          if vid not in idx.tombstones and (tag is None or tag in t)]
    return [vid for _, vid in sorted(ok)[:K]]


for tag in (None, "lang:de"):
    print("filter:", tag or "none")
    for nprobe in (1, 4, 16):
        rec = work = 0
        for q in queries:
            got, w = idx.search(q, K, nprobe, tag)
            rec += len(set(got) & set(exact(q, tag))) / K
            work += w
        print("  nprobe=%2d  recall@10=%.2f  distance computations/query=%5d (brute force %d)"
              % (nprobe, rec / len(queries), work // len(queries), NUM))

victim = idx.search(queries[0], 1, 16)[0][0]
idx.delete(victim)
print("deleted", victim, "-> still returned?", victim in idx.search(queries[0], K, 16)[0])

Trade-offs

• HNSW gives the best recall and latency but costs several KB of RAM per vector and slow builds.
• Product quantization cuts memory 10–30× but costs recall unless you re-rank with full vectors from SSD.
• A larger ef or nprobe raises recall but costs latency and CPU nearly linearly.
• Hash sharding keeps load even but costs a fan-out to every shard on every query.
• Searching a brute-force mutable segment makes writes visible in seconds but costs a bit of latency on every query until it is sealed.

What a strong answer shows

• Sizes memory per vector and uses it to pick index type, quantization and shard count.
• Explains how HNSW and IVF-PQ work and when each fits.
• Has a real strategy for selective filters, not just post-filtering.
• Handles writes and deletes with segments, tombstones and compaction.
• Explains scatter-gather and tail latency and how replicas and hedging help.
• Treats recall as a measured, tunable SLO.

Mistakes to avoid

• Assuming exact nearest-neighbour search scales, or never mentioning recall.
• Ignoring memory: putting 3 TB of float32 vectors on a single node.
• Post-filtering only, so selective filters return empty results.
• Mutating a large HNSW graph in place on every write and delete.
• Trusting the caller to pass the tenant filter.

Follow-ups to expect

• How would you support hybrid keyword + vector search? (Add an inverted index per segment; fuse ranks.)
• How would you change the embedding model for a collection? (Build a new collection in parallel, dual-write, switch an alias.)
• How do you measure recall in production? (Shadow-run exact search on a small sample of queries.)
• How would you offer a serverless tier for many tiny collections? (Store on object storage, load on demand, cache hot ones.)

Practice next