Bird
Raised Fist0

Design Facebook News Feed - EdgeRank, Fan-Out on Write vs Read

HLDhardInterview freq: high
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🎯
Design Facebook News Feed - EdgeRank, Fan-Out on Write vs Read
45 min · senior
senior

You are designing the News Feed system for a social media platform with 50 million daily active users (DAU). The system must deliver personalized, relevant posts with low latency (P99 < 200ms) and support offline delivery. User posts and interactions are encrypted end-to-end. The system should balance freshness, scalability, and cost, considering the trade-offs between fan-out on write and fan-out on read approaches.

Constraints
  • End-to-end encryption of user posts and interactions
  • Support offline delivery with eventual consistency
  • P99 feed load latency under 200ms
  • 50 million DAU generating 10 million posts and 500 million interactions daily
  • Personalized ranking using EdgeRank or similar relevance algorithm
📋
Guided Steps
1/5
Step 1
Choosing Fan-Out Strategy
Should the system use fan-out on write or fan-out on read for delivering News Feed updates? Why?
💡 Hint
Consider write amplification, read latency, and user activity patterns at 50M DAU scale.
Key Decision
Use fan-out on write with Apache Kafka for write scalability and Redis sorted sets for per-user feed storage to achieve low read latency under 200ms P99.
Interviewer Expectation
Mid: Names fan-out on write and Kafka. Senior: Explains write amplification trade-off, how Kafka partitions by user ID to maintain ordering, and why fan-out on read causes high read latency and spikes.
⚠️Common Wrong Answer
Use fan-out on read with a single database query per feed request - leads to high read latency and database overload at 50M DAU.
Step 2
Feed Ranking Algorithm
How will you implement the EdgeRank relevance algorithm to rank posts in the feed?
💡 Hint
Think about precomputing scores vs computing on the fly and how to handle freshness and personalization.
Key Decision
Precompute EdgeRank scores during fan-out using Apache Flink streaming jobs, store scores in Redis sorted sets per user for O(log N) retrieval of top posts.
Interviewer Expectation
Mid: Describes EdgeRank basics and precomputation. Senior: Details streaming computation with Flink, incremental updates, and how Redis sorted sets enable efficient top-K queries with score-based ordering.
⚠️Common Wrong Answer
Compute EdgeRank scores on read - causes high CPU load and latency spikes during feed fetch.
Step 3
Data Storage and Encryption
Where and how will you store posts and user interactions securely, considering encryption and offline delivery?
💡 Hint
Separate encrypted storage from feed indexes; consider Cassandra for write-heavy workloads.
Key Decision
Store encrypted posts and interactions in Apache Cassandra with partition key=user_id for linear write scalability; feed indexes in Redis are pointers only, not containing plaintext data.
Interviewer Expectation
Mid: Names Cassandra for storage. Senior: Explains Cassandra's LSM-tree write optimization, partitioning by user_id for locality, and separation of encrypted blobs from feed metadata for security and offline access.
⚠️Common Wrong Answer
Store plaintext posts in Redis cache - risks data leakage and does not scale for persistent storage.
Step 4
Handling Offline Delivery and Consistency
How will the system ensure users receive feed updates when offline and maintain eventual consistency?
💡 Hint
Consider message queues and client sync protocols with cursors or timestamps.
Key Decision
Use Kafka topics per user for durable event logs; clients sync with cursor-based APIs to fetch missed feed updates upon reconnect, ensuring eventual consistency.
Interviewer Expectation
Mid: Mentions Kafka for durability. Senior: Explains cursor-based sync APIs, how Kafka offsets enable replay of missed events, and how Redis TTL and heartbeat mechanisms detect offline status.
⚠️Common Wrong Answer
Use HTTP polling without cursor sync - causes excessive load and inconsistent feed state.
Step 5
API Design for Feed Interaction
Design 3 core API endpoints for posting, fetching, and acknowledging feed items.
💡 Hint
Consider request payloads, pagination, and idempotency.
Key Decision
POST /feed/post to submit encrypted posts; GET /feed?cursor= to fetch paginated personalized feed from Redis; POST /feed/ack to mark items as seen, updating Kafka consumer offsets.
Interviewer Expectation
Mid: Names endpoints and basic functionality. Senior: Details payload encryption, cursor-based pagination for efficient sync, idempotent acknowledgments updating Kafka offsets to avoid duplicate delivery.
⚠️Common Wrong Answer
Use simple GET without pagination or acknowledgment - leads to inefficient data transfer and duplicate feed items.
🔌
API Design Challenge
Sketch 3 core API endpoints for the News Feed system that cover posting, fetching, and acknowledging feed items.
Hints
  • How does the client submit a new post and ensure it propagates?
  • How does the client fetch a personalized feed with pagination and freshness?
  • How does the client acknowledge or mark feed items as seen or interacted with?
📊
Scoring Rubric
▼ Show
Must Have - 60%
  • Clear choice and justification of fan-out on write using Kafka to handle 50M DAU scale
  • Precomputation of EdgeRank scores with streaming technology (Flink) and storage in Redis sorted sets
  • Encrypted storage of posts and interactions in Cassandra with appropriate partitioning
  • Cursor-based sync mechanism for offline delivery using Kafka offsets
Good to Have - 30%
  • Separation of encrypted data from feed metadata for security
  • Use of Redis TTL and heartbeat for offline user detection
  • Detailed API design covering posting, fetching with pagination, and acknowledgment
Bonus - 10%
  • Discussion of failure modes such as Kafka partition rebalancing impact on ordering
  • Trade-offs between fan-out on write and fan-out on read with quantitative reasoning
Anti-patterns to Avoid
Fan-out on read causing database overload and high latency at 50M DAU, leading to system crashes and poor user experience
Computing EdgeRank on read leading to CPU spikes and inconsistent feed freshness, causing latency spikes and degraded performance
Storing plaintext posts in cache risking data leakage and violating encryption constraints, exposing sensitive user data
HTTP polling without cursor sync causing excessive load and inconsistent feed state, resulting in server overload and stale feeds
Using a single monolithic database for all feed data causing write bottlenecks and poor scalability, limiting system throughput
✅
Model Answer
▼ Reveal

The News Feed system uses fan-out on write with Apache Kafka to distribute posts and interactions, precomputes EdgeRank scores via Apache Flink streaming jobs, and stores per-user feed indexes in Redis sorted sets for low-latency retrieval. Encrypted posts and interactions are stored securely in Apache Cassandra partitioned by user_id to ensure write scalability and data locality. Offline delivery is supported through cursor-based sync APIs leveraging Kafka offsets, enabling clients to fetch missed updates upon reconnect. Redis TTL and heartbeat mechanisms detect offline users to optimize delivery. The API design includes POST /feed/post for submitting encrypted posts, GET /feed with cursor-based pagination for fetching personalized feeds, and POST /feed/ack for acknowledging feed items, ensuring idempotency and efficient synchronization.

Key Decisions
  • Adopt fan-out on write using Apache Kafka to handle high write throughput and maintain low read latency under 200ms P99
  • Precompute EdgeRank relevance scores during fan-out with Apache Flink to avoid CPU spikes on read
  • Store encrypted posts and interactions in Apache Cassandra partitioned by user_id for write scalability and security
  • Use Redis sorted sets to store feed indexes with precomputed scores for O(log N) top-K retrieval
  • Implement cursor-based sync APIs leveraging Kafka offsets to support offline delivery and eventual consistency
  • Separate encrypted data blobs from feed metadata to maintain security and comply with encryption constraints
  • Design APIs with encrypted payloads, cursor-based pagination, and idempotent acknowledgments to ensure efficient and reliable client-server interaction
  • Apache Kafka for durable, partitioned event streaming enabling fan-out on write at 50M DAU scale
  • Redis sorted sets per user to store precomputed EdgeRank scores for low-latency feed retrieval
  • Apache Flink for real-time streaming computation of EdgeRank relevance scores during fan-out
  • Apache Cassandra for encrypted post and interaction storage with user_id partition key for write scalability
  • Cursor-based sync APIs leveraging Kafka offsets to support offline delivery and eventual consistency
  • Separation of encrypted data blobs from feed metadata to maintain security and comply with encryption constraints
  • Use of Redis TTL and heartbeat mechanisms to detect offline users and optimize delivery paths
  • API design with POST /feed/post, GET /feed with cursor pagination, and POST /feed/ack for acknowledgment

Practice

(1/5)
1. In a distributed cache using consistent hashing, at Step 4 the Cache Node receives a key lookup request. What happens if the node does not have the key locally?
easy
A. The node returns a cache miss immediately without forwarding
B. The node uses the consistent hash ring to forward the request to the correct node
C. The node queries a centralized metadata service for key location
D. The node broadcasts the request to all other cache nodes

Solution

  1. Step 1: Trace key lookup at Cache Node

    If the node lacks the key, it must find the correct node responsible for that key using the consistent hash ring.

  2. Step 2: Forwarding via consistent hash ring

    The node consults the hash ring to identify the node owning the key and forwards the request there; centralized metadata (The node queries a centralized metadata service for key location) adds latency and single point of failure; broadcasting (The node broadcasts the request to all other cache nodes) is inefficient.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Consistent hash ring lookup enables correct node forwarding [check]
Hint: Cache miss triggers consistent hash ring forwarding [check]
Common Mistakes:
2. Without a distributed lock in place, what exactly happens when multiple clients detect an expired cache key and simultaneously request backend data?
medium
A. Clients receive stale cache data until the backend recovers
B. All clients simultaneously hit the backend, causing a spike and possible overload
C. Clients queue up and retry sequentially, preventing backend overload
D. The cache automatically refreshes in the background without client involvement

Solution

  1. Step 1: Understand absence of distributed lock

    Without locking, multiple clients detect expired cache simultaneously.

  2. Step 2: Trace failure mode

    Clients serve stale data until backend responds; no serialization causes thundering herd spike.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Stale data served while backend recovers, no queuing or automatic refresh [check]
Hint: No lock -> stale data served, backend overload risk persists [OK]
Common Mistakes:
3. Without the seat lock expiration mechanism, what exact failure occurs during concurrent bookings?
medium
A. Users receive immediate errors due to deadlock detection in the database
B. Seats remain locked indefinitely, causing availability to drop and bookings to stall
C. Payment processing fails because seat status is inconsistent across services
D. The system automatically cancels bookings after a fixed timeout regardless of payment

Solution

  1. Step 1: Understand role of seat lock expiration

    Expiration releases seats if payment or booking is abandoned, preventing indefinite holds.

  2. Step 2: Trace failure without expiration

    Locks never expire, so seats remain reserved even if users abandon payment, reducing available seats and causing booking stalls.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    No TTL -> stale locks -> seats unavailable indefinitely [check]
Hint: No expiration -> stale locks -> seats blocked forever [OK]
Common Mistakes:
4. 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:
5. At 10x scale, which component in the alerting system is most likely to become the bottleneck first, and why?
hard
A. Anomaly detection engine, because complex ML models require exponential compute as data volume grows
B. Event ingestion pipeline, due to limited write throughput and storage I/O constraints
C. Composite alert processor, because combining many alerts requires stateful joins that grow quadratically
D. Threshold alerting component, since static limit checks are CPU-light and easily parallelizable

Solution

  1. Step 1: Identify scale bottlenecks

    At 10x scale, write throughput and storage I/O become critical constraints for ingestion pipelines.

  2. Step 2: Compare component scalability

    Anomaly detection can be scaled horizontally; composite alerting state grows but less than ingestion I/O; threshold checks are lightweight.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Ingestion pipeline limited by write throughput and storage I/O [check]
Hint: 10x scale -> ingestion pipeline hits write I/O bottleneck first [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