Walkthrough: Designing a Vector Database

The problem

You’re asked to design a vector database — the specialized storage engine behind semantic search, recommendation systems, and RAG pipelines. The interviewer says something like: “Design a system that stores billions of high-dimensional vectors and returns the nearest neighbors for a query vector in under 50ms.”

Sounds like “a database with cosine similarity.” It isn’t. This is the canonical approximate-nearest-neighbor problem at scale, and what makes it non-trivial is that exact nearest-neighbor search in high dimensions is fundamentally intractable (the curse of dimensionality makes brute-force and tree-based indexes useless past ~20 dimensions). Every design decision is a trade-off between recall (did you find the actual nearest neighbors?), latency (how fast?), and memory (how much RAM per vector?). The interviewer is watching for whether you treat this as a storage problem or an approximation problem.

Below is how I’d walk through this, roughly in the order I’d speak the words.

1. Clarify before you design

First 3–5 minutes. Resist the urge to start drawing.

Questions I’d ask:

• Dimensionality and count. How many vectors, and what dimension? 1 billion 768-dim vectors is a very different system from 10 million 1536-dim vectors.
• Query latency SLO. p50 and p99 targets. 10ms vs 100ms changes the index choice and whether we can afford disk-based solutions.
• Recall target. 95% recall@10 vs 99.5% recall@10 changes the index parameters dramatically. Higher recall = more computation.
• Write pattern. Batch ingest (index rebuild nightly) or real-time upserts (searchable within seconds of write)?
• Metadata filtering. Do queries combine vector similarity with attribute filters (“nearest neighbors where category = X”)? This is where most vector databases struggle.
• Multi-tenancy. Shared index or per-tenant isolation? Tenant size variance matters for sharding.
• Hybrid search. Do we also need keyword/BM25 search, or pure vector similarity?

Say the interviewer confirms: 1 billion vectors, 768 dimensions, p99 < 50ms, recall@10 ≥ 95%, real-time upserts (searchable within 5s), metadata filtering required, multi-tenant with per-tenant isolation, hybrid search (vector + keyword).

2. Capacity estimate

Brief. The point is to check what drives the architecture.

• 1B vectors × 768 dims × 4 bytes (float32) = ~3TB raw vector data.
• With HNSW index overhead (~1.5x raw data for graph edges at M=16), total index memory ≈ ~4.5TB.
• A single node with 256GB RAM holds ~57M vectors in-memory. Need ~18 shards minimum just for the index.
• Query rate: assume 10K queries/sec at peak.
• Write rate: 100K upserts/sec (real-time index updates).

I’d say out loud: “This tells me two things. One — the entire index must be in memory for the 50ms SLO; disk-based approaches won’t work at this latency target. Two — at 1B vectors, the system is shard-heavy, so the sharding strategy and query fan-out pattern are the architecture. Three — real-time upserts into an HNSW graph require careful concurrency control, because HNSW is not append-only.”

3. API design

Three operations carry the load:

POST /v1/vectors/upsert
  body: { id, vector: float[768], metadata: { ... }, namespace }
  returns: { status: "ok" }

POST /v1/vectors/search
  body: {
    vector: float[768],
    top_k: int,
    filter: { field: value, ... },
    namespace: string,
    include_metadata: bool
  }
  returns: { results: [{ id, score, metadata }] }

POST /v1/vectors/search/hybrid
  body: {
    vector: float[768],
    query_text: string,
    top_k: int,
    alpha: float,  // vector vs keyword weight
    filter: { ... },
    namespace: string
  }
  returns: { results: [{ id, score, metadata }] }

Decisions worth saying out loud:

• Namespace as a first-class concept. Multi-tenancy is at the API level. Each namespace is an isolated index — queries never cross namespaces. This is simpler than row-level filtering and prevents data leaks between tenants structurally.
• Filter is in the search request, not a separate step. The naive approach (search first, filter results) destroys recall — if 90% of vectors don’t match the filter, you need to over-retrieve 10x to get enough filtered results. The index must support filtered search natively, not post-hoc.
• Hybrid search has an explicit alpha parameter. The caller controls the vector-vs-keyword weight. No magic auto-blending — the optimal alpha varies by use case (semantic search vs keyword-heavy search vs a mix), and the caller knows their use case.

4. Core design: the ANN index

This is the question. It’s where SDE II and SDE III answers diverge.

Exact nearest-neighbor search at 768 dimensions requires comparing the query against every vector — O(N) per query. At 1B vectors, that’s seconds. Approximate nearest neighbor (ANN) indexes trade a small amount of recall for orders-of-magnitude speedup.

Three families:

(a) IVF (Inverted File Index). Partition vectors into K clusters (via k-means). At query time, search only the nprobe nearest clusters.

• Pros: Simple. Low memory overhead (just the cluster assignments). Good for batch workloads.
• Cons: Recall depends heavily on nprobe tuning. Real-time updates are awkward (which cluster does the new vector belong to?). Cluster imbalance hurts.

(b) HNSW (Hierarchical Navigable Small World). Build a multi-layer graph where each vector is a node and edges connect it to its approximate nearest neighbors. Query traverses the graph greedily from an entry point, hopping to closer nodes at each step.

• Pros: Best recall/latency trade-off in practice. Real-time inserts are natural (add the node, connect to neighbors). No clustering step.
• Cons: High memory overhead (graph edges stored alongside vectors). Build time is O(N log N). The graph is the index and must be in memory.

(c) ScaNN / Product Quantization. Compress vectors via quantization (PQ, OPQ), then search the compressed space. Decompress only the top candidates for re-ranking.

• Pros: Much lower memory (8–16x compression). Enables disk-based indexes for huge corpora.
• Cons: Recall drops with compression. Requires careful parameter tuning. Not as good as HNSW at the high-recall operating point.

The SDE III answer is: HNSW as the primary index, with the parameter choice driven by the recall/latency trade-off:

• M (max connections per node): 16 is the standard default. Higher M = better recall, more memory.
• ef_construction (beam width during build): 200. Higher = better graph quality, slower build.
• ef_search (beam width during query): tuned to hit the 95% recall@10 target at <50ms.

HNSW wins for our requirements because (a) we need high recall at low latency (HNSW’s sweet spot), (b) we need real-time upserts (HNSW supports incremental inserts natively), and (c) we can afford the memory (our capacity estimate already accounted for the graph overhead). If memory were the binding constraint, we’d trade recall for compression with IVF+PQ.

5. Algorithm deep-dive: HNSW search

Worth walking through, because the interviewer is checking whether you understand why this works — not just that it exists.

HNSW is a multi-layer skip-list analog for graph search:

1. Build the graph. When a vector is inserted, it’s assigned a random layer (higher layers are exponentially less likely — like a skip list). At each layer it participates in, it’s connected to its M approximate nearest neighbors in that layer. The top layer has very few nodes; the bottom layer has all nodes.
2. Search. Start at the entry point (a fixed node in the top layer). At each layer, greedily traverse the graph — hop to whichever neighbor is closest to the query vector. When you can’t improve at the current layer, drop to the next layer (which has more nodes and finer-grained neighborhoods). At the bottom layer, maintain a priority queue of the ef_search best candidates seen so far. Return the top-k from the priority queue.
3. Why it works. The upper layers provide long-range “highways” — coarse navigation through the vector space. The lower layers provide fine-grained local search. This gives O(log N) hops on average to reach the neighborhood of the true nearest neighbor, then a local search of ef_search candidates for recall.

Worked example: 1B vectors, 5 layers. Top layer has ~100 nodes. Query enters at the top, traverses 2–3 hops to find the approximate region. Drops to layer 4 (~10K nodes), refines. Drops to layer 3, 2, 1. At the bottom layer, explores ef_search=128 candidates. Total distance computations: ~500–1000 (vs 1B for brute force). That’s the logarithmic magic.

Real-time inserts. When a new vector arrives, compute its neighbors at each layer (same greedy search), connect it. The graph is modified in place. This requires a lock on the neighbor nodes being connected — in practice, fine-grained per-node locks with compare-and-swap on the neighbor lists. HNSW is designed for concurrent reads and writes; the structure is append-friendly at the node level.

6. Data model and storage

vector_store (in-memory, per shard):
  vector_id (PK)
  vector: float32[768]
  hnsw_node: { layer, neighbors_per_layer[] }

metadata_store (per shard):
  vector_id (PK)
  namespace
  metadata: { field: value, ... }
  created_at, updated_at

wal (per shard, on disk):
  sequence_number
  operation (upsert | delete)
  vector_id, vector, metadata

Storage choices:

• Vector + HNSW graph: in-memory (mmap’d). The latency SLO demands it. Backed by a write-ahead log on disk for durability — every upsert is logged before being applied to the in-memory index. On node restart, replay the WAL to rebuild the index.
• Metadata: in-memory inverted index per shard. Metadata fields are indexed for filtered search (like a traditional DB’s secondary indexes). This is the piece that makes filter + vector search fast — the filter narrows the candidate set before the HNSW traversal, not after.
• WAL: local SSD. Append-only, sequentially written. Periodically snapshotted (the entire HNSW graph serialized to disk) to bound recovery time.

I’d say explicitly: “The durable state is the WAL + periodic snapshots. The in-memory index is derived state — it can be reconstructed from the WAL. This means node failures cost recovery time (replay the WAL) but not data loss, which is the right trade-off for a system where the latency budget is 50ms and the data can always be re-derived from the embedding source.”

7. The search path

At 10K queries/sec across 18+ shards, the query must fan out to the right shards and merge results.

flowchart LR
  Client[Client] --> Router[Query router]
  Router --> S1[(Shard 1 · HNSW)]
  Router --> S2[(Shard 2 · HNSW)]
  Router --> SN[(Shard N · HNSW)]
  S1 --> Router
  S2 --> Router
  SN --> Router
  Router --> Client

The search flow:

1. Query router receives the search request. Determines which shards to query based on the namespace (tenant). Fans out the query to all shards for that namespace in parallel.
2. Each shard runs HNSW search locally (with metadata filter applied), returns its local top-k results with scores.
3. Router merges the per-shard results, re-ranks by score, returns the global top-k.

For hybrid search, each shard also runs a keyword search (BM25 on an inverted text index) and returns both score vectors. The router combines them using the alpha weight: final_score = alpha * vector_score + (1 - alpha) * bm25_score, then returns the merged top-k.

The fan-out is the latency concern: p99 is dominated by the slowest shard. Mitigations: request hedging (send the query to shard + replica, take the first response), adaptive timeouts, and keeping shards balanced so no single shard is significantly larger.

8. Sharding and replication

Two decisions: how to partition vectors across shards, and how to replicate for availability.

Sharding strategy. Two options:

• By namespace (tenant). All vectors for one tenant on one shard (or a small set of shards). Queries never fan out beyond the tenant’s shards. Simple, but large tenants become hot shards.
• Random/hash-based across all shards within a namespace. Vectors are distributed uniformly. Every query fans out to all shards in the namespace. Better load balance, higher fan-out.

I’d pick namespace-aware sharding with splitting for large tenants. Small tenants (< 10M vectors) live on a single shard — no fan-out, lowest latency. Large tenants are split across multiple shards (hashed by vector_id). This gives the best of both: no fan-out for the common case, horizontal scaling for the few tenants that need it.

Replication. Each shard has one primary and one replica (in a different AZ). The primary handles writes; both handle reads. On primary failure, the replica promotes. Replication is at the WAL level — the replica replays the primary’s WAL with a short lag (~100ms). Queries against the replica may miss the most recent writes; this is acceptable because our “searchable within 5s” SLA allows it.

Extended architecture:

flowchart LR
  Client[Client] --> Router[Query router]
  Router --> S1[(Shard 1 · primary)]
  Router --> S2[(Shard 2 · primary)]
  Router --> S1R[(Shard 1 · replica)]
  Router --> S2R[(Shard 2 · replica)]

  S1 -.->|WAL replication| S1R
  S2 -.->|WAL replication| S2R

  WriteClient[Write client] --> WriteRouter[Write router]
  WriteRouter --> S1
  WriteRouter --> S2

  classDef new fill:#eef2f1,stroke:#2c5f5d,stroke-width:2px,color:#1f2937;
  class S1R,S2R,WriteClient,WriteRouter new

Reads are load-balanced across primary and replica. Writes go only to the primary. The router is aware of which shards own which namespaces via a metadata service (similar to the ZooKeeper pattern in the distributed cache walkthrough).

9. Failure modes

I’d proactively walk through what breaks.

• A shard node crashes. The replica promotes to primary (~seconds). Writes are briefly unavailable for that shard (until promotion completes). Reads continue against the replica. Recent writes (last ~100ms of WAL lag) may be lost — acceptable for a derived index (re-embed from source if needed).
• HNSW index corruption. A bug in the concurrent insert path creates a broken edge. Symptoms: recall drops silently on that shard. Mitigation: periodic recall health checks (run a known query set, verify expected results appear). On detection, rebuild the shard from the WAL or from the source embedding pipeline.
• Hot tenant saturates a shard. One tenant submits 5K queries/sec against a single shard. Mitigation: per-tenant rate limiting at the router, read replicas for hot shards, and the splitting strategy (move the tenant to multi-shard mode).
• Recall degrades after many updates. HNSW graph quality degrades over time as vectors are deleted (leaving “holes” in the graph) and inserted (connecting to non-optimal neighbors). Symptom: recall drifts below the 95% target. Mitigation: periodic background re-indexing (rebuild the HNSW graph from the current vector set). Schedule during off-peak. This is the maintenance story most vector databases hide.
• Filtered search returns too few results. The metadata filter is so selective that HNSW doesn’t encounter enough matching vectors during traversal. Mitigation: over-retrieve (increase ef_search dynamically when filter selectivity is high), or maintain separate sub-indexes per high-cardinality filter value.

The pattern to notice: name what fails, name what degrades gracefully, name what doesn’t. HNSW fails silently (recall drops, not errors) — which is worse than a crash in many ways.

10. What I’d skip, and say I’m skipping

• Quantization details. Scalar quantization, product quantization, binary quantization — real levers for memory reduction. Worth mentioning as a knob. Not designing for it given our memory budget fits.
• GPU-accelerated search. FAISS on GPU can do brute-force over 100M vectors in milliseconds. Different architecture (batch-oriented, not real-time-upsert friendly). Worth naming; not the right tool here.
• Multi-modal vectors. Images, video, text in the same index. Architecturally the same (they’re all just float arrays), but the embedding pipeline changes. Out of scope.
• Cross-namespace search (federated search). A user searching across multiple tenants. Security and isolation implications. Real product concern, not an infrastructure one.

11. Wrap-up

One crisp sentence:

This design treats the vector database as an approximate index with durability guarantees — the HNSW graph is derived state reconstructible from the WAL, and every design decision optimizes for the recall/latency trade-off at the cost of memory, which is the fundamental tension in high-dimensional search.

That framing — naming the recall/latency/memory triangle as the architectural center of gravity — is what lands.

What separates SDE II from SDE III on this question

• SDE II names HNSW or FAISS, sketches a sharded index with a query router, mentions cosine similarity.
• SDE III walks through HNSW at re-implementation depth (the multi-layer graph, the greedy traversal, why it’s O(log N)), names filtered search as the hard problem (not just similarity), addresses recall degradation over time as a maintenance concern, separates derived state (the index) from durable state (the WAL), and commits to namespace-aware sharding with a specific rationale.
• Staff/Principal names the recall/latency/memory triangle explicitly and makes the trade-offs visible: this design chooses high recall and low latency at the cost of ~4.5TB RAM, and explains what would have to change (quantization, disk-based IVF, tiered storage) if the memory budget were halved. Proactively identifies the scaling inflection points: at 10B vectors, single-node HNSW shards become impractical and the query fan-out pattern changes; at 100K QPS, the router becomes a bottleneck and the sharding model needs a read-cache tier. Asks “how does on-call debug a recall regression?” — which surfaces the need for per-shard recall health checks, query latency histograms broken down by filter selectivity, and graph fragmentation metrics as operational requirements. Surfaces the missing requirement of SLA differentiation: a system serving both RAG pipelines (batch, recall-sensitive) and recommendation serving (latency- sensitive, recall-tolerant) may need different HNSW parameter profiles per namespace. Reasons about build vs buy for the vector index layer in terms of the team’s ability to operate and tune a distributed HNSW cluster vs the cost and lock-in of a managed vector database — not just which one benchmarks better today. Asks “when does this break?” for the WAL-based recovery model: at what WAL size does replay time exceed acceptable RTO, and what does that imply for snapshot frequency?

The difference isn’t knowing that HNSW exists. It’s understanding why high-dimensional search is hard and showing how every decision resolves one axis of the recall/latency/memory triangle.

Further reading

• Designing Data-Intensive Applications — Kleppmann. Chapter 3 (storage and retrieval) provides the index- design mental model that extends to vector indexes.
• HNSW paper — Malkov & Yashunin. The primary reference for the algorithm. Worth reading the first 8 pages.
• FAISS wiki — Meta’s ANN library. Best documentation of IVF, PQ, and HNSW implementation trade-offs.
• Pinecone’s HNSW explainer — the clearest visual walkthrough of the algorithm.
• calm.rocks: Designing a RAG System — the canonical consumer of a vector database. The retrieval layer there sits on top of the system designed here.
• calm.rocks: Cache Access and Invalidation Patterns — the WAL + derived-index pattern here follows the same durability-vs-speed trade-off as write-behind caching.