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
Design a scalable personalized news feed system using EdgeRank and fan-out strategies
hardSocial Media and Feed SystemsFreq: high
Prerequisites:System Design FundamentalsCAP TheoremDistributed SystemsCaching and Data Partitioning
⚙️
Functional Requirements
  • Generate personalized news feed for each user based on their friends' posts and interests using EdgeRank algorithm.
  • Support real-time feed updates with low latency when users or their friends post new content.
  • Allow users to like, comment, and share posts with immediate reflection in their feed.
  • Support feed pagination and infinite scroll with consistent ordering.
  • Enable feed ranking based on recency, affinity, and content weight (EdgeRank factors).
  • Support multi-media content types (text, images, videos) in feed items.
📊
Non-Functional Requirements
  • Support 2 billion daily active users (DAU).
  • Handle peak write throughput of approximately 925K posts per second.
  • Ensure 99.99% availability for feed retrieval APIs.
  • Achieve 100ms P99 latency for feed read requests.
  • Data retention for at least 30 days of feed content.
❓
Clarifying Questions to Ask
  • What is the expected average number of friends/followers per user?
  • What is the average number of posts a user generates per day?
  • Should the feed be strictly real-time or is eventual consistency acceptable?
  • What is the expected read-to-write ratio for the feed system?
  • Are we supporting only text posts or multimedia content as well?
  • What is the maximum acceptable staleness for feed updates?
Out of Scope
✗ Design of the social graph storage and friend/follower management.
✗ Detailed design of content storage and media delivery (CDN).
✗ User authentication and authorization mechanisms.
✗ Ad targeting and sponsored content integration.
📌
Assumptions
  • 2 billion DAU
  • Average 40 posts/messages per user per day
  • Average post size 100 bytes (metadata + text)
  • Average 200 friends/followers per user
⚡
QPS Calculation
write qps2B x 40 / 86400 ≈ 925,926 writes/sec
peak write qpsAssuming 3x peak factor: 925,926 x 3 ≈ 2.78M writes/sec
read qps2B users x 1 feed read per 10 seconds ≈ 200M reads/sec peak
💾
Storage Estimate
daily storage2B x 40 x 100 bytes = 8 TB/day
retention days30
total storage8 TB x 30 = 240 TB
with replicationAssuming 3x replication: 240 TB x 3 = 720 TB
🖥️
Server Estimate
write serversAssuming each write server handles 10K writes/sec, need 278 servers
read serversAssuming each read server handles 10K reads/sec, need 20,000 servers
🏗️
Architecture Diagram
Architecture Diagram
User
  |
  v
API Gateway
  |
  v
Write Service (Post Ingestion)
  |
  v
Kafka (Write Log)
  |
  v
Fan-out Workers
  |
  v
Feed Storage (Cassandra)
  |
  v
Cache Layer (Redis)
  |
  v
Read Service (Feed Retrieval)
  |
  v
User
🧩
Components
API Gateway
Entry point for all user requests, routes to write or read services
Why thisNginx with Envoy proxy for high throughput and low latency routing with TLS termination
Why notDirect client-to-service communication lacks centralized control and load balancing
Write Service (Post Ingestion)
Handles user post creation, validates and publishes to Kafka
Why thisStateless microservice in Go for high concurrency and easy horizontal scaling
Why notMonolithic backend would not scale to 2.78M writes/sec peak
Kafka (Write Log)
Durable, ordered, partitioned log for all incoming posts to enable asynchronous processing
Why thisKafka supports high throughput (millions of writes/sec), partitioning, and consumer groups for fan-out
Why notRabbitMQ lacks Kafka’s throughput and partitioning scalability at this scale
Fan-out Workers
Consume Kafka posts, apply EdgeRank, and write personalized feed entries to storage
Why thisKubernetes-managed stateless workers allow elastic scaling and fault tolerance
Why notFan-out on read would cause high latency and overload read path
Feed Storage (Cassandra)
Stores personalized feed entries per user with fast writes and time-series data model
Why thisCassandra’s wide-column store supports high write throughput and tunable consistency
Why notPostgreSQL requires complex manual sharding and does not scale linearly at 2.78M writes/sec
Cache Layer (Redis)
Caches most recent feed entries per user for sub-100ms read latency
Why thisRedis supports TTL-based eviction and sub-millisecond lookups with high QPS
Why notMemcached lacks native TTL and persistence, increasing cache miss risk
Read Service (Feed Retrieval)
Serves feed requests by querying Redis cache and falling back to Cassandra
Why thisStateless microservice with autoscaling to handle 200M reads/sec peak
Why notDirect DB queries without cache cause high latency and overload storage
🔄
Data Flow
1
User → API Gateway
User submits a new post
API Gateway routes to Write Service
2
API Gateway → Write Service
Validate and enqueue post to Kafka topic
Write Service is stateless and horizontally scalable
3
Kafka → Fan-out Workers
Fan-out Workers consume posts asynchronously
Apply EdgeRank to score and rank posts per follower
4
Fan-out Workers → Feed Storage (Cassandra)
Write personalized feed entries for each follower
Wide-column model stores feed sorted by timestamp
5
Feed Storage → Cache Layer (Redis)
Update cache with latest feed entries
Cache TTL ensures freshness and eviction of stale data
6
User → API Gateway
User requests news feed
API Gateway routes to Read Service
7
Read Service → Cache Layer (Redis)
Fetch feed entries from cache
If cache miss, fallback to Cassandra
8
Read Service → User
Return personalized feed with EdgeRank ordering
Ensure 100ms P99 latency

Practice

(1/5)
1. A critical database cluster must failover automatically without data loss or downtime during a primary node crash. Which component is responsible for orchestrating this failover in a distributed SQL database system?
easy
A. Consensus protocol (e.g., Raft) managing leader election and log replication
B. Load balancer redirecting traffic based on health checks
C. Client-side retry logic to reconnect to a new primary node
D. Backup scheduler triggering periodic snapshots for recovery

Solution

  1. Step 1: Identify failover orchestration component

    The consensus protocol like Raft manages leader election and ensures log replication consistency, enabling automatic failover without data loss.

  2. Step 2: Eliminate other options

    Client-side retries (A) handle reconnection but don't orchestrate failover; load balancers (B) redirect traffic but don't manage state; backups (D) aid recovery but not live failover.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Consensus protocol controls leader election and failover [check]
Hint: Consensus protocols manage failover, not clients or load balancers
Common Mistakes:
2. You must design a multi-primary replication system for a geo-distributed database with low write latency and conflict detection. Which approach is best?
medium
A. Use asynchronous replication with vector clocks for conflict detection and resolution
B. Use a single global primary with read replicas in each region
C. Use synchronous replication between primaries to ensure consistency
D. Use asynchronous replication with last-write-wins conflict resolution

Solution

  1. Step 1: Analyze latency and conflict requirements

    Low write latency requires asynchronous replication; conflict detection needs metadata like vector clocks.

  2. Step 2: Evaluate options

    Synchronous replication (A) adds latency; single primary (C) violates multi-primary requirement; last-write-wins (D) ignores conflicts.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Async replication + vector clocks -> low latency + conflict detection [check]
Hint: Vector clocks detect conflicts in async multi-primary [check]
Common Mistakes:
3. Without the Rendezvous Hashing component in a distributed cache, what exactly breaks when a node fails?
medium
A. Cache keys are evenly redistributed instantly with no downtime
B. The system blocks all requests until a new mapping is manually configured
C. Clients must retry multiple nodes, causing increased latency and inconsistent cache hits
D. Requests are routed to a random node, causing cache misses and stale data

Solution

  1. Step 1: Understand role of Rendezvous Hashing in failure

    Rendezvous Hashing provides deterministic mapping without central coordination. Without it, no automatic remapping occurs.

  2. Step 2: Trace failure impact

    Without Rendezvous Hashing, system blocks or requires manual remapping, causing request blocking and downtime.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    No automatic remapping -> system blocks until manual config [check]
Hint: No Rendezvous -> manual remap blocks requests [check]
Common Mistakes:
4. If Zookeeper's session timeout mechanism fails to detect a crashed leader node promptly, what is the most likely failure observed in the leader election process?
medium
A. Multiple nodes simultaneously assume leadership causing split-brain
B. Leader election proceeds normally due to backup leader election mechanism
C. Followers wait indefinitely for leader node removal, blocking leader election
D. Clients receive stale configuration but leader election continues

Solution

  1. Step 1: Understand session timeout role

    Session timeout detects leader failure by ephemeral node removal.

  2. Step 2: Failure of timeout detection

    If timeout fails, ephemeral node remains, so followers do not start election; no split-brain occurs.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Backup election mechanisms prevent split-brain despite timeout failure [check]
Hint: Session timeout failure -> ephemeral node stays -> no immediate election [check]
Common Mistakes:
5. At 10x traffic scale, which component is most likely to fail first in a system without rate limiting, and why?
hard
A. The backend cache, because its memory fills up causing evictions and cache misses
B. The database, due to increased write load causing slow queries and deadlocks
C. The network load balancer, as it cannot handle the increased number of TCP connections
D. The API servers, because they maintain stateful connections that cannot be easily sharded

Solution

  1. Step 1: Analyze component scalability at 10x traffic

    Databases (A) and caches (D) can be scaled horizontally or sharded; load balancers (C) can be scaled or replaced with L4/L7 solutions.

  2. Step 2: Identify API servers as bottleneck

    API servers maintaining stateful connections (e.g., WebSockets) are hard to shard or move; connection limits cause saturation and failure first.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Stateful API servers hit connection limits first at scale [check]
Hint: Stateful API servers fail first due to connection limits [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