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
45 min · senior
senior

You are building a vector database backend for a 50 million daily active users (DAU) startup that provides semantic search over user-generated content embeddings. The system must store billions of high-dimensional vectors (e.g., 512 dimensions), support low-latency approximate nearest neighbor (ANN) queries using Hierarchical Navigable Small World (HNSW) graphs, and handle 100k QPS with P99 latency under 200ms. Data must be encrypted at rest and in transit. The system should support offline batch ingestion and online incremental updates.

Constraints
  • Store and index billions of 512-dimensional float vectors with efficient disk and memory usage
  • Support 100k QPS ANN search with P99 latency < 200ms
  • Data encrypted at rest (AES-256) and in transit (TLS 1.3)
  • Support offline batch ingestion and online incremental updates without downtime
  • Ensure high availability with minimal query disruption during index rebuilds
📋
Guided Steps
1/5
Step 1
Embedding Storage Design
How would you design the storage layer for billions of high-dimensional vectors with efficient writes and reads?
💡 Hint
Consider a distributed, horizontally scalable storage optimized for large sequential writes and range scans.
Key Decision
Use Apache Cassandra with partition key as vector_id and clustering on timestamp to enable efficient writes and range queries; Cassandra's LSM-tree architecture supports high write throughput and linear horizontal scaling.
Interviewer Expectation
Mid: Names Cassandra for scalable storage. Senior: Explains why Cassandra's LSM-tree and partition key design fit high write throughput and range queries, and why alternatives like MongoDB or MySQL would bottleneck at scale.
⚠️Common Wrong Answer
Using a relational database like MySQL for vector storage - it cannot handle billions of writes per day and leads to high write amplification and slow queries.
Step 2
ANN Search Indexing with HNSW
How would you implement the ANN search index to meet the P99 < 200ms latency requirement at 100k QPS?
💡 Hint
Consider an in-memory graph-based index optimized for fast approximate nearest neighbor search with efficient updates.
Key Decision
Use HNSW (Hierarchical Navigable Small World) graph implemented with NMSLIB or Faiss's HNSW module, sharded across multiple nodes with vector partitions to distribute query load and keep latency low.
Interviewer Expectation
Mid: Mentions HNSW for ANN search. Senior: Explains sharding strategy, memory management, and why alternatives like brute-force or tree-based indexes (e.g., KD-trees) fail at high dimensionality and scale.
⚠️Common Wrong Answer
Using brute-force linear scan for ANN queries - leads to unacceptable latency and CPU cost at billions of vectors.
Step 3
Data Encryption and Security
How would you ensure data encryption at rest and in transit for sensitive embedding data?
💡 Hint
Consider industry-standard encryption protocols and key management integrated with storage and network layers.
Key Decision
Enable AES-256 encryption at rest using Cassandra's Transparent Data Encryption (TDE) and enforce TLS 1.3 for all client-server and inter-node communication; integrate with HashiCorp Vault for centralized key management.
Interviewer Expectation
Mid: Mentions encryption at rest and TLS. Senior: Details Cassandra TDE, TLS 1.3 benefits, key rotation policies, and why application-level encryption alone is insufficient.
⚠️Common Wrong Answer
Relying only on network-level encryption without encrypting data at rest - exposes data if storage nodes are compromised.
Step 4
Index Update and Consistency
How would you handle offline batch ingestion and online incremental updates to the HNSW index without downtime?
💡 Hint
Consider a dual-index approach or background rebuilds with atomic switch-over to maintain availability.
Key Decision
Implement a dual-index system where a new HNSW index is built offline using Apache Spark batch jobs, then atomically swapped with the active index; incremental updates are applied asynchronously using a write-ahead log and merged periodically.
Interviewer Expectation
Mid: Describes batch rebuild and online updates. Senior: Explains atomic index swap to avoid query disruption, incremental update merge strategies, and why naive in-place index rebuild blocks queries.
⚠️Common Wrong Answer
Rebuilding the entire index in-place synchronously - causes query downtime and violates SLA.
Step 5
API Design for Vector Database
Design three core API endpoints for embedding ingestion, ANN search, and index update status monitoring.
💡 Hint
Think about request/response payloads, parameters for search tuning, and asynchronous update status reporting.
Key Decision
Define POST /vectors to ingest embeddings with metadata, GET /search with query vector and parameters (k, efSearch), and GET /index/status to report current index version and rebuild progress.
Interviewer Expectation
Mid: Lists endpoints and basic parameters. Senior: Details payload schemas, supports batching in ingestion, search tuning parameters, and asynchronous status with versioning for client consistency.
⚠️Common Wrong Answer
Designing only synchronous ingestion without batch support - leads to high client latency and throughput bottlenecks.
🔌
API Design Challenge
Sketch 3 core API endpoints for the vector database: embedding ingestion, ANN search query, and index update status.
Hints
  • How does the client send new embeddings and metadata to the system?
  • How does the client query for nearest neighbors and specify search parameters?
  • How does the client check the status of index rebuilds or incremental updates?
📊
Scoring Rubric
▼ Show
Must Have - 60%
  • Use of Cassandra with appropriate partition key for scalable embedding storage
  • Implementation of HNSW index for ANN search meeting latency and QPS constraints
  • Encryption at rest and in transit with concrete technologies (AES-256, TLS 1.3)
  • Handling index rebuilds with zero downtime via dual-index and atomic swap
  • API design covering ingestion, search, and index status
Good to Have - 30%
  • Sharding strategy for load distribution and latency optimization
  • Incremental update mechanism for index freshness
  • Centralized key management integration
Bonus - 10%
  • Detailed explanation of failure modes during index rebuild and recovery
  • Consideration of memory management and caching for HNSW index nodes
Anti-patterns to Avoid
✅
Model Answer
▼ Reveal

This design outlines a scalable vector database system that stores billions of 512-dimensional float vectors using Apache Cassandra for high write throughput and linear scaling. It uses HNSW graph indexes implemented with NMSLIB or Faiss, sharded across nodes to meet 100k QPS with P99 latency under 200ms. Data is encrypted at rest with AES-256 via Cassandra's TDE and in transit with TLS 1.3, with keys managed centrally by HashiCorp Vault. The system supports offline batch ingestion and online incremental updates via a dual-index architecture with atomic swaps to ensure zero downtime. APIs include POST /vectors for batch ingestion, GET /search for ANN queries with tuning parameters, and GET /index/status for monitoring index rebuild progress.

Key Decisions
  • Use Apache Cassandra for embedding storage due to its LSM-tree design enabling high write throughput and horizontal scaling
  • Implement ANN search with HNSW graph using NMSLIB or Faiss, sharded across nodes to distribute load and maintain low latency
  • Encrypt data at rest with AES-256 using Cassandra's Transparent Data Encryption and enforce TLS 1.3 for all communications
  • Adopt a dual-index architecture with offline batch rebuilds and atomic index swap to avoid query downtime during index updates
  • Apply incremental updates asynchronously via a write-ahead log merged periodically into the HNSW index
  • Design APIs to support batch ingestion, search tuning parameters (k, efSearch), and asynchronous index status monitoring with versioning
  • Shard vectors and indexes by vector_id hash to balance query load and reduce latency
  • Integrate with HashiCorp Vault for secure key management and automated rotation policies
  • Apache Cassandra for embedding storage - LSM-tree design enables high write throughput and linear scaling
  • HNSW index implemented with NMSLIB or Faiss - supports fast ANN queries with P99 < 200ms at 100k QPS
  • AES-256 Transparent Data Encryption in Cassandra and TLS 1.3 for secure data at rest and in transit
  • Dual-index architecture with offline batch rebuilds and atomic index swap to ensure high availability
  • Incremental updates applied asynchronously via write-ahead logs merged periodically into the HNSW index
  • API endpoints: POST /vectors for ingestion, GET /search for ANN queries with tuning parameters, GET /index/status for monitoring
  • Sharding vectors and HNSW index by vector_id hash to distribute load and reduce query latency
  • Integration with HashiCorp Vault for centralized encryption key management and rotation

Practice

(1/5)
1. For a mobile chat app requiring low latency and offline support, which architecture is best suited to handle message synchronization and delivery?
medium
A. Use WebSockets with server push and no offline caching
B. Use gRPC streaming for real-time message delivery to mobile clients
C. Use REST APIs with client-side local storage and background sync
D. Use polling every few seconds to fetch new messages

Solution

  1. Step 1: Analyze mobile client constraints

    Mobile clients often have intermittent connectivity and limited support for persistent streaming (gRPC streaming in Use gRPC streaming for real-time message delivery to mobile clients is unreliable on mobile). WebSockets without offline caching (Use WebSockets with server push and no offline caching) fail offline support. Polling (Use polling every few seconds to fetch new messages) adds latency and battery drain.

  2. Step 2: Evaluate REST with local storage

    REST APIs combined with client-side local storage and background sync enable offline message access and eventual consistency with low latency.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    REST + local storage -> offline support and sync [check]
Hint: Offline support needs local storage, not persistent streaming [check]
Common Mistakes:
2. If the Kafka broker cluster loses ZooKeeper coordination, what exactly breaks in the message delivery process?
medium
A. Messages are lost immediately as brokers cannot write to logs
B. Producers can still write, but partition leadership cannot be elected, causing delivery stalls
C. Consumers receive duplicate messages due to offset corruption
D. The entire cluster shuts down automatically to prevent data loss

Solution

  1. Step 1: Role of ZooKeeper in Kafka

    ZooKeeper manages partition leadership and consumer offsets; losing it affects coordination but not immediate message loss.

  2. Step 2: Failure impact on delivery

    Without ZooKeeper, offset metadata can become inconsistent, causing consumers to re-read messages and receive duplicates (C); producers may still write (B is partially true but leadership election stalls eventually); cluster does not shut down automatically (D).

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    ZooKeeper loss -> offset inconsistency -> duplicate consumer messages [check]
Hint: ZooKeeper loss corrupts offsets causing duplicates, not immediate loss [check]
Common Mistakes:
3. For billing in a multi-tenant SaaS platform, which architecture best supports accurate usage tracking with minimal latency impact on tenant requests?
medium
A. Asynchronous event-driven usage aggregation via a message queue and batch processing
B. Embedding billing logic directly in the tenant service to update counters in-memory
C. Periodic polling of tenant usage logs by the billing service every hour
D. Synchronous billing updates on every tenant API call to the billing database

Solution

  1. Step 1: Analyze latency and accuracy trade-offs

    Synchronous updates (Synchronous billing updates on every tenant API call to the billing database) add latency; polling (Periodic polling of tenant usage logs by the billing service every hour) delays billing data; in-memory counters (Embedding billing logic directly in the tenant service to update counters in-memory) risk data loss.

  2. Step 2: Evaluate asynchronous event-driven approach

    Asynchronous event-driven usage aggregation via a message queue and batch processing decouples billing from tenant requests, ensuring accurate aggregation with minimal latency impact.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Event-driven async billing -> accurate, low-latency tenant requests [check]
Hint: Async event-driven billing decouples latency [check]
Common Mistakes:
4. For a global service requiring low latency and high availability, which DNS load balancing approach is best when client IPs are often masked by VPNs or proxies?
medium
A. Use DNS-based latency measurements to route clients dynamically
B. Use GeoDNS with IP-based geolocation to route clients
C. Use Anycast IP routing combined with DNS round-robin for global distribution
D. Use a centralized DNS server that manually assigns IPs based on user profiles

Solution

  1. Step 1: Analyze IP masking impact

    GeoDNS relying on client IP (A) fails when IPs are masked by VPNs/proxies, causing inaccurate geolocation.

  2. Step 2: Evaluate alternatives

    Anycast IP routing (B) routes clients to nearest data center at network level, unaffected by IP masking. DNS latency-based routing (C) adds complexity and latency. Centralized DNS (D) is a bottleneck and not scalable.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Anycast routes at network layer, bypassing IP masking issues [check]
Hint: Anycast routes clients despite IP masking, GeoDNS fails [check]
Common Mistakes:
5. If the Inverted Index Update Service crashes and stops updating document frequencies (DF), what is the exact failure observed in search relevance?
medium
A. The system automatically switches to BM25 scoring without DF dependency
B. Ranking uses stale DF causing relevance scores to drift and degrade over time
C. New documents are not indexed but existing DF remains accurate
D. Search queries fail with errors due to missing DF data

Solution

  1. Step 1: Understand DF update role

    Inverted Index Update Service maintains DF counts; if it crashes, DF stops updating and becomes stale.

  2. Step 2: Trace impact on ranking

    Ranking cannot rely on fresh DF; system falls back to BM25 variant that tolerates stale DF or uses approximations; queries do not error out; new documents may still be indexed but DF is outdated.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    System falls back to BM25 variant tolerating stale DF [check]
Hint: Without DF updates, system falls back to BM25 variant [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