Bird
Raised Fist0

Design a Recommendation System - Collaborative Filtering, Embedding Storage

HLDhardInterview freq: high
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🏗️
Design a Recommendation System - Collaborative Filtering, Embedding Storage
Design a scalable collaborative filtering recommendation system with embedding storage for 2B DAU
hardAI and ML System DesignFreq: high
Prerequisites:Collaborative FilteringEmbeddingsDistributed StorageReal-time Data Processing
⚙️
Functional Requirements
  • Generate personalized item recommendations for users based on collaborative filtering using user-item interaction data.
  • Store and serve dense vector embeddings for users and items to enable similarity computations.
  • Support real-time updates of user interactions and embeddings to reflect recent behavior.
  • Provide APIs for fetching top-N recommendations with low latency (sub-100ms P99).
  • Support batch offline model training and embedding generation pipelines.
  • Allow cold-start handling for new users and items using fallback strategies.
📊
Non-Functional Requirements
  • Support 2 billion daily active users (DAU) with 40 interactions per user per day.
  • Achieve 99.99% system availability for recommendation serving APIs.
  • Ensure recommendation API P99 latency under 100 milliseconds.
  • Handle peak write throughput of up to 1.5 million writes per second during global peak hours.
  • Data retention for user interactions and embeddings for at least 90 days.
❓
Clarifying Questions to Ask
  • What is the expected number of items in the catalog and their update frequency?
  • Are recommendations personalized per user or also session/context aware?
  • What is the acceptable staleness for recommendations after user interaction?
  • Is the system expected to support multi-tenant or multiple domains?
  • What is the expected read-to-write ratio for recommendation queries?
  • Are embeddings updated in real-time or only during batch training?
Out of Scope
✗ Design of the offline machine learning model training algorithms.
✗ Content-based recommendation or hybrid models beyond collaborative filtering.
✗ User authentication and authorization mechanisms.
✗ UI/UX design for recommendation display.
📌
Assumptions
  • 2 billion DAU
  • 40 interactions per user per day
  • 100 bytes per interaction record
  • Average embedding size: 256 floats (4 bytes each) = 1KB per embedding
⚡
QPS Calculation
write qps2B × 40 / 86400 ≈ 925,926 writes/sec
peak write qpsAssuming 1.5× peak factor → 925,926 × 1.5 ≈ 1,388,889 writes/sec
read qpsAssuming 5 reads per user per day → 2B × 5 / 86400 ≈ 115,741 reads/sec
💾
Storage Estimate
daily storage2B × 40 × 100 bytes = 8 TB/day
retention 90 days8 TB × 90 = 720 TB raw
with replication 3x720 TB × 3 = 2.16 PB total storage
🖥️
Server Estimate
write pathKafka cluster with 50 brokers (each broker handles ~30K writes/sec)
read pathRedis cluster with 200 nodes (each node handles ~600 reads/sec with sub-ms latency)
🏗️
Architecture Diagram
Architecture Diagram
          +----------------+
          | User Interaction|
          |    Clients      |
          +--------+-------+
                   |
                   v
          +----------------+
          | Kafka Cluster  |
          | (50 brokers)   |
          +--------+-------+
                   |
                   v
          +----------------+       +----------------+
          | Stream Process |       | Offline Batch  |
          | (Apache Flink) |       | Training Jobs  |
          +--------+-------+       +--------+-------+
                   |                        |
                   v                        v
          +----------------+       +----------------+
          | Embedding Store|       | Model Storage  |
          | (Cassandra)    |       | (S3 + Metadata)|
          +--------+-------+       +--------+-------+
                   |                        |
                   v                        |
          +----------------+                |
          | Recommendation |<---------------+
          | Serving Layer  |
          | (Redis Cluster)|
          +--------+-------+
                   |
                   v
          +----------------+
          | API Gateway    |
          +----------------+
🧩
Components
Kafka Cluster
Ingest and buffer user interaction events at high throughput
Why thisKafka supports partitioned logs with high throughput and durability for 1.4M writes/sec peak
Why notRabbitMQ lacks partitioning and scales poorly beyond 100K msgs/sec; Kinesis is costlier at this scale
Apache Flink Stream Processor
Real-time processing of interaction streams to update embeddings and user-item matrices
Why thisFlink provides exactly-once semantics and low-latency stateful stream processing at scale
Why notSpark Streaming has higher latency and weaker exactly-once guarantees for real-time updates
Cassandra Embedding Store
Store user and item embeddings with fast read/write and horizontal scalability
Why thisCassandra's wide-column model supports high write throughput and tunable consistency for 2PB scale
Why notPostgreSQL requires manual sharding and does not scale linearly at 1M+ writes/sec
Redis Cluster
Serve low-latency top-N recommendations and embedding lookups for real-time API queries
Why thisRedis supports sub-millisecond lookups with TTL and clustering for horizontal scaling
Why notMemcached lacks persistence and complex data structures needed for embedding similarity queries
Offline Batch Training Jobs
Periodically retrain collaborative filtering models and generate updated embeddings
Why thisBatch jobs on Spark or Hadoop handle large-scale matrix factorization and embedding generation
Why notReal-time training is infeasible due to model complexity and data volume
API Gateway
Expose recommendation APIs with authentication, rate limiting, and routing
Why thisAPI Gateway centralizes request handling and scales horizontally for 100K+ QPS
Why notDirect client access to Redis risks security and lacks request management
Model Storage (S3 + Metadata DB)
Store trained model artifacts and metadata for versioning and rollback
Why thisS3 provides durable, cost-effective storage with metadata in DynamoDB or similar
Why notLocal storage is not durable or scalable for multi-PB model artifacts
🔄
Data Flow
1
→
2
→
3
→
4
→
5
→
6
→

Practice

(1/5)
1. A system needs to quickly check membership of millions of items with minimal memory and can tolerate some false positives but no false negatives. Which component best handles this requirement?
easy
A. A simple hash set stored in memory
B. A relational database with indexed lookups
C. A distributed cache with strong consistency guarantees
D. A Bloom filter implemented with multiple hash functions and a bit array

Solution

  1. Step 1: Identify membership check requirements

    The system requires fast membership queries with minimal memory and can tolerate false positives but not false negatives.

  2. Step 2: Match component capabilities

    Bloom filters use multiple hash functions and a bit array to provide space-efficient membership checks with false positives but no false negatives, fitting the scenario.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Bloom filter trades memory for false positives, no false negatives [check]
Hint: Bloom filters trade memory for false positives [check]
Common Mistakes:
2. In the request flow of a video call setup, at step 5 the Signaling Server receives an SDP offer from Alice and forwards it to Bob. What state does the Signaling Server maintain immediately after forwarding the offer?
easy
A. It stores the offer and waits for Bob's SDP answer before updating session state
B. It queues the offer indefinitely until Bob acknowledges receipt
C. It deletes the offer after forwarding, assuming Bob will respond directly to Alice
D. It marks the session as established and starts media relay between Alice and Bob

Solution

  1. Step 1: Trace Signaling Server behavior at step 5

    The server forwards Alice's SDP offer to Bob and stores it to correlate with Bob's answer.

  2. Step 2: Understand session state management

    Session is not established until Bob's SDP answer arrives; the offer must be retained temporarily.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Signaling Server stores offer awaiting answer before session established [check]
Hint: Signaling stores offer until answer arrives, then session established [check]
Common Mistakes:
3. In a system using TCP for file transfer, at step 4 the TCP sender retransmits a packet after a timeout. What is the state of the sender's congestion window at this step?
easy
A. The congestion window is increased to allow faster sending
B. The congestion window is doubled to compensate for lost packets
C. The congestion window remains unchanged until ACKs arrive
D. The congestion window is reduced to the initial slow-start threshold

Solution

  1. Step 1: Understand TCP congestion control on timeout

    When a retransmission timeout occurs, TCP interprets it as network congestion and reduces the congestion window to the slow-start threshold.

  2. Step 2: Confirm congestion window behavior

    The congestion window is reset to a lower value to reduce sending rate, avoiding further congestion.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Timeout triggers congestion window reduction to slow-start threshold [check]
Hint: Timeout -> congestion window reset to slow-start threshold [check]
Common Mistakes:
4. A financial system requires strict ACID compliance for transactions involving multiple accounts, ensuring atomicity and consistency. Which component is most appropriate to handle these transactional guarantees?
easy
A. A message queue system for decoupling writes and reads
B. A distributed NoSQL store with eventual consistency
C. An in-memory cache with asynchronous write-behind
D. A relational database with support for multi-statement transactions

Solution

  1. Step 1: Identify transactional requirements

    The scenario demands strict ACID properties, especially atomicity and consistency across multiple accounts.

  2. Step 2: Match component capabilities

    Relational databases provide multi-statement transactions with ACID guarantees, unlike NoSQL stores or caches which sacrifice consistency or durability.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Relational DBs ensure ACID transactions for multi-account updates [check]
Hint: ACID transactions require relational DBs, not eventual consistency [check]
Common Mistakes:
5. At 10x scale, which component is most likely to fail first and why in Slack's real-time delivery system?
hard
A. Chat servers, because WebSocket connections are stateful and cannot be resharded easily
B. Presence service, because TTL cache invalidations overwhelm the system
C. Kafka brokers, because partition count cannot scale beyond a fixed limit
D. The database, because increased writes cause locking and slow queries

Solution

  1. Step 1: Identify stateful bottlenecks at scale

    Chat servers hold WebSocket connections in memory, which are stateful and tied to specific servers, limiting horizontal scaling.

  2. Step 2: Compare other components

    Databases can be sharded; Kafka scales with partitions; presence service caches can be distributed; chat servers' stateful connections are the hardest to shard.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Stateful WebSocket connections -> chat servers bottleneck at 10x scale [check]
Hint: Stateful WebSocket binds chat servers -> first bottleneck [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