Bird
Raised Fist0

Design a Vector Database - Embedding Storage, ANN Search, HNSW Index

HLDhardInterview freq: medium
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🏗️
Design a Vector Database - Embedding Storage, ANN Search, HNSW Index
Scalable vector embedding storage and approximate nearest neighbor search using HNSW index
hardAI and ML System DesignFreq: medium
Prerequisites:Inverted IndexElasticsearch
⚙️
Functional Requirements
  • Store high-dimensional vector embeddings (e.g., 128-1024 dimensions) for billions of items.
  • Support approximate nearest neighbor (ANN) search queries with low latency (sub-100ms P99).
  • Build and maintain a Hierarchical Navigable Small World (HNSW) graph index for efficient ANN search.
  • Support incremental updates: insertions, deletions, and updates of embeddings with index maintenance.
  • Provide APIs for vector insertion, deletion, and similarity search with configurable top-K results.
  • Support metadata filtering (e.g., filter by category) alongside vector search.
📊
Non-Functional Requirements
  • Handle 2 billion daily active users generating embeddings at 40 embeddings/user/day.
  • Achieve 99.99% availability for search and write APIs.
  • Ensure 100ms P99 latency for ANN search queries at peak load.
  • Store and serve petabytes of embedding data with replication for durability.
  • Scale horizontally to handle 10x growth in data and query volume.
❓
Clarifying Questions to Ask
  • What is the typical dimensionality and data type of embeddings (float32, float16)?
  • What is the expected query QPS and write QPS at peak times?
  • Are embeddings immutable after insertion or do they require frequent updates?
  • What is the retention period for embeddings and index data?
  • Is metadata filtering required to be tightly integrated with ANN search?
  • What consistency guarantees are expected for search results after writes?
Out of Scope
✗ Embedding model training and feature extraction from raw data.
✗ Complex query ranking or re-ranking beyond ANN search results.
✗ User authentication and authorization mechanisms.
✗ Real-time streaming analytics on embedding usage.
📌
Assumptions
  • 2 billion daily active users (DAU).
  • Each user generates 40 embeddings per day on average.
  • Each embedding vector is 512 dimensions, float32 (4 bytes per dimension) = 2048 bytes.
  • Retention period of 30 days for embeddings and index data.
  • Replication factor of 3 for durability.
⚡
QPS Calculation
write qps2B users × 40 embeddings/day ÷ 86400 sec/day ≈ 925,926 writes/sec
peak write qpsAssuming 2× peak factor: 1,851,852 writes/sec
read qpsAssuming 10 queries per user per day: 2B × 10 ÷ 86400 ≈ 231,481 reads/sec
peak read qpsAssuming 2× peak factor: 462,962 reads/sec
💾
Storage Estimate
daily storage2B × 40 × 2048 bytes = 163,840,000,000,000 bytes ≈ 149 TB/day
retention storage149 TB/day × 30 days = 4.47 PB
with replication4.47 PB × 3 = 13.41 PB total storage
🖥️
Server Estimate
embedding storage nodesAssuming 2 TB SSD per node, 13.41 PB ÷ 2 TB ≈ 6706 nodes
search index nodesAssuming each node handles 10K QPS with 100ms latency, 462,962 ÷ 10,000 ≈ 47 nodes
🏗️
Architecture Diagram
Architecture Diagram
          +----------------+
          |  Client/API GW |
          +--------+-------+
                   |
        +----------+-----------+
        |                      |
 +------+-------+      +-------+-------+
 | Write Ingest  |      | Search Query  |
 |  Service      |      |  Service      |
 +------+-------+      +-------+-------+
        |                      |
 +------+-------+      +-------+-------+
 | Kafka Cluster |      | HNSW Index    |
 | (Write Buffer)|      | Search Nodes  |
 +------+-------+      +-------+-------+
        |                      |
 +------+-------+      +-------+-------+
 | Embedding DB |      | Metadata DB   |
 | (Cassandra)  |      | (Elasticsearch)|
 +--------------+      +---------------+
🧩
Components
Client/API Gateway
Entry point for all client requests including embedding writes and ANN search queries.
Why thisNginx or Envoy provides scalable, low-latency routing with TLS termination and rate limiting.
Why notDirect client connections to backend services lack centralized control and complicate scaling.
Write Ingest Service
Receives embedding write requests, validates, and publishes to Kafka for asynchronous processing.
Why thisStateless microservice allows horizontal scaling and decouples ingestion from storage latency.
Why notSynchronous writes directly to DB cause high tail latency and reduce throughput.
Kafka Cluster
Durable, distributed write buffer for embedding data to decouple ingestion from storage and indexing.
Why thisKafka supports high throughput (millions of messages/sec), partitioning, and consumer groups for parallelism.
Why notRabbitMQ or Redis Streams have lower throughput and weaker durability guarantees at this scale.
Embedding DB (Apache Cassandra)
Stores raw embedding vectors with high write throughput and horizontal scalability.
Why thisCassandra offers linear write scalability, tunable consistency, and efficient storage for large volumes.
Why notPostgreSQL requires manual sharding and B-tree writes do not scale linearly to 925K+ writes/sec.
HNSW Index Search Nodes
Maintain and serve the HNSW graph index for fast approximate nearest neighbor search queries.
Why thisFaiss or NMSLIB implementations of HNSW provide sub-100ms P99 latency and support incremental updates.
Why notBrute-force linear scan or tree-based indexes (e.g., KD-tree) do not scale well to billion-scale vectors.
Metadata DB (Elasticsearch)
Stores metadata and supports filtering on vector search results.
Why thisElasticsearch provides inverted index and rich filtering capabilities integrated with vector search.
Why notRelational DBs have poor full-text and filtering performance at this scale.
Search Query Service
Receives ANN search requests, queries HNSW index nodes and metadata DB, merges results, and returns top-K.
Why thisStateless service enables horizontal scaling and aggregation of vector and metadata results.
Why notEmbedding DB cannot efficiently serve low-latency ANN queries directly.
🔄
Data Flow
1
Client/API Gateway → Write Ingest Service
Receive embedding write requests with metadata
Validate and forward asynchronously
2
Write Ingest Service → Kafka Cluster
Publish embedding write messages
Decouple ingestion from storage
3
Kafka Cluster → Embedding DB
Consume and store raw embeddings
High throughput writes
4
Kafka Cluster → HNSW Index Search Nodes
Consume and update HNSW index
Maintain graph for ANN search
5
Client/API Gateway → Search Query Service
Receive ANN search queries with filters
Query vector and metadata filters
6
Search Query Service → HNSW Index Search Nodes
Query ANN index for nearest neighbors
Fast approximate search
7
Search Query Service → Metadata DB
Query metadata filters
Filter results by metadata
8
Search Query Service → Client/API Gateway
Merge and return top-K results
Combine vector and metadata results

Practice

(1/5)
1. In a primary-replica replication system, at step 4 the replica receives a batch of write-ahead log entries from the primary. What is the replica's exact state after applying these entries?
easy
A. Replica marks entries as committed and acknowledges primary before applying
B. Replica applies entries to its data store and then acknowledges primary
C. Replica applies entries and immediately serves reads from them before acknowledgment
D. Replica buffers entries without applying until primary confirms commit

Solution

  1. Step 1: Trace replica behavior at step 4

    Replica applies WAL entries to its local store to catch up with primary.

  2. Step 2: Understand acknowledgment timing

    Replica acknowledges primary only after applying entries to ensure durability and consistency.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Replica applies then acknowledges -> ensures data durability [check]
Hint: Apply WAL entries before ack -> durability ensured [check]
Common Mistakes:
2. In the message delivery trace, at Step 4 the Delivery Worker checks Bob's presence TTL in the presence service cache. What happens if Bob's presence TTL has expired at this step?
easy
A. The Delivery Worker queues the message for offline storage and does not send over WebSocket
B. The Delivery Worker immediately marks the message as delivered without sending
C. The Delivery Worker retries presence check indefinitely before sending
D. The Delivery Worker sends the message over WebSocket regardless of presence TTL

Solution

  1. Step 1: Trace Delivery Worker decision at Step 4 -- Bob's presence TTL

    If Bob's presence TTL expired, Delivery Worker treats Bob as offline and queues message for offline storage.

  2. Step 2: Eliminate other options

    Marking delivered without sending is incorrect; retrying indefinitely blocks delivery; sending regardless ignores offline status.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Expired presence TTL -> queue for offline delivery [check]
Hint: Expired presence TTL means offline -> queue message [check]
Common Mistakes:
3. A distributed messaging system must handle 1 million writes per second and guarantee message durability despite node failures. Which component best handles this requirement?
easy
A. Use a distributed log system like Apache Kafka with replication and partitioning
B. Use an in-memory cache like Redis without persistence to speed up writes
C. Use a relational database with synchronous writes for durability
D. Use a simple message queue with no replication to reduce latency

Solution

  1. Step 1: Identify durability and high write throughput needs

    Redis without persistence (A) cannot guarantee durability on failure. Relational DB (C) cannot handle 1M writes/sec synchronously without bottlenecks. Simple queue without replication (D) risks message loss.

  2. Step 2: Recognize Kafka's replication and partitioning

    Kafka provides durable, replicated logs with partitioning for high throughput and fault tolerance.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Kafka replication + partitioning -> durability and scale [check]
Hint: Kafka replicates logs for durability and scales with partitions [check]
Common Mistakes:
4. At 10x scale, which component is most likely to become the bottleneck first in a read-heavy CQRS system with read replicas, and why?
hard
A. Event queue, because increased write events overwhelm its processing capacity
B. Primary database, because write throughput scales linearly with read volume
C. Read replicas, because replication lag increases and they cannot keep up with read demand
D. Client-side caches, because cache invalidation traffic grows exponentially

Solution

  1. Step 1: Analyze scaling impact on components

    Write volume and event propagation increase 10x, stressing the event queue.

  2. Step 2: Compare bottlenecks

    Primary DB writes scale with writes, not reads; read replicas scale horizontally; client caches don't cause exponential invalidation.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Event queue overwhelmed first due to write event surge [check]
Hint: Event queue chokes first as write events surge 10x [check]
Common Mistakes:
5. At 10x scale, which component in a synchronous chat system is most likely to fail first and why?
hard
A. The database, because it cannot handle the increased write volume synchronously
B. The load balancer, because it cannot distribute synchronous requests evenly at high scale
C. The client devices, because they cannot maintain multiple synchronous connections simultaneously
D. The chat servers, because WebSocket connections are stateful and cannot be easily resharded or migrated

Solution

  1. Step 1: Identify stateful bottleneck in synchronous chat

    Chat servers maintain WebSocket connections statefully, binding clients to specific servers.

  2. Step 2: Analyze scaling challenges

    At 10x scale, resharding or migrating these stateful connections is complex, causing chat servers to fail first.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Stateful WebSocket servers limit horizontal scaling, causing early failure [check]
Hint: Stateful WebSocket servers bottleneck synchronous chat scaling [check]
Common Mistakes:
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard