32 - Design News Feed
Series: System Design & Distributed Systems
Previous: 31 - Design Chat System | Next: 33 - Design YouTube or Netflix
1. Requirements
Functional Requirements
| Feature | Details |
|---|
| Create post | Text, images, video, links |
| View news feed | Aggregated posts from friends/followed users |
| Like, comment, share | Engagement actions |
| Pagination | Efficient scrolling through feed |
| Notifications | Alert on friend activity (optional) |
Non-Functional Requirements
- Latency: Feed loads in < 500ms
- Availability: 99.99%
- Freshness: New posts appear within seconds for close friends
- Scale: 1B users, 300M DAU, avg 500 friends per user
- Ranking: Not purely chronological -- relevance matters
2. Capacity Estimation
DAU: 300M
Avg posts created/day: 2 per active user = 600M posts/day
Avg feed fetches/day: 10 per user = 3B feed reads/day
Avg friends: 500
Fan-out write volume: 600M posts x 500 friends = 300B writes/day (push model)
Feed read QPS: 3B / 86400 = ~35K QPS
Peak read QPS: ~70K QPS
| Resource | Estimate |
|---|
| Post storage/day | ~600M posts x 1KB = 600GB |
| Feed cache per user | ~2000 post IDs x 8B = 16KB |
| Total feed cache | 300M users x 16KB = ~5TB |
3. High-Level Architecture
+---------+ +--------------+ +-----------+
| Client |-------->| API Gateway |------->| Post |
| (App) | | | | Service |
+---------+ +-+------+-----+ +-----+-----+
| | |
| | +-----+------+
| | | Post DB |
| | | (MySQL/ |
| | | Postgres) |
| | +------------+
| |
+------+ +--------+
| |
+------+------+ +-------+------+
| Feed | | Feed |
| Generation | | Retrieval |
| Service | | Service |
+------+------+ +-------+------+
| |
+------+------+ +-------+------+
| Fan-out | | Feed Cache |
| Workers | | (Redis) |
+------+------+ +--------------+
|
+------+------+
| Message |
| Queue |
| (Kafka) |
+-------------+
4. Feed Generation: Three Approaches
Approach 1: Fan-Out on Write (Push Model)
User A creates post
|
v
Fan-out Service reads A's follower list
|
v
For each follower, prepend post_id to their feed cache
|
+----+----+----+----+
| | | | |
F1 F2 F3 F4 ...FN
feed feed feed feed feed
| Pros | Cons |
|---|
| Feed read is O(1) -- just fetch from cache | Write amplification: celebrity with 10M followers = 10M writes |
| Low latency on read | Wasted work for inactive users who never check feed |
| Simple feed retrieval | Hot users create thundering herd on write path |
Approach 2: Fan-Out on Read (Pull Model)
User B opens feed
|
v
Feed Service fetches B's friend list
|
v
For each friend, query their recent posts
|
v
Merge, rank, return top N
| Pros | Cons |
|---|
| No write amplification | Slow: must query N friends' timelines on every read |
| No wasted computation | High read latency, especially for users with 1000+ friends |
| Fresh results every time | Hard to rank without pre-computation |
Approach 3: Hybrid (Facebook's Approach)
Is poster a celebrity?
|
+-------+-------+
| |
YES NO
| |
Pull on read Push to followers'
(lazy fetch) feed cache (fan-out)
| User Type | Strategy | Reason |
|---|
| Normal user (< 10K followers) | Fan-out on write | Low fan-out cost, fast reads |
| Celebrity (> 10K followers) | Fan-out on read | Avoid millions of writes per post |
| Close friends | Fan-out on write + priority | Ensure low-latency delivery |
Interview Tip: Always propose the hybrid approach. Explain the celebrity problem first, then show how the hybrid solves it. This demonstrates depth.
5. Feed Ranking Algorithm
Simple Chronological
score = timestamp
Engagement-Based (EdgeRank, simplified)
score = affinity x weight x time_decay
affinity = how close is the poster to the viewer (interaction history)
weight = type of content (video > photo > text > link)
time_decay = 1 / (now - post_time)^gravity
Modern ML Ranking
Feed candidates (1000s)
|
v
Stage 1: Candidate retrieval (lightweight model)
|
v
Stage 2: Feature extraction
| - User features (age, location, interests)
| - Post features (type, engagement, recency)
| - Cross features (past interactions between user and poster)
|
v
Stage 3: Ranking model (deep learning)
| - Predict: P(like), P(comment), P(share), P(hide)
| - Combine into final score
|
v
Stage 4: Re-ranking (diversity, dedup, policy filters)
|
v
Top 50 posts returned
6. News Feed Cache
Cache Structure (Redis Sorted Set per User)
feed:{user_id} = sorted set of (post_id, score)
Example:
feed:U123 = {
(post_789, 0.95),
(post_456, 0.88),
(post_123, 0.72),
...
}
Cache Operations
| Operation | Command | Complexity |
|---|
| Add post to feed | ZADD | O(log N) |
| Get top N posts | ZREVRANGE | O(log N + M) |
| Trim old posts | ZREMRANGEBYRANK | O(log N + M) |
| Remove post (deleted) | ZREM | O(log N) |
Cache Policy
- Keep latest 2000 post IDs per user
- TTL: 7 days for inactive users
- Cache-aside pattern: miss triggers on-the-fly generation
7. Pagination: Cursor-Based
Why Not Offset-Based?
Problem: New posts push items down, causing duplicates or skips
Page 1: [A, B, C, D, E]
^--- New post X inserted here
Page 2: [E, F, G, H, I] <-- E appears twice!
Cursor-Based Pagination
GET /feed?cursor=post_456&limit=20
Response:
{
"posts": [...20 posts...],
"next_cursor": "post_789",
"has_more": true
}
- Cursor = last seen post ID or timestamp
- Stable regardless of new inserts
- Works naturally with sorted sets in Redis
Interview Tip: Always propose cursor-based pagination for feeds. Mention that offset-based has the "shifting window" problem.
8. Social Graph Storage
Graph Database or Adjacency List
+------------+ follows +------------+
| User A |----------------->| User B |
+------------+ +------------+
| |
| follows | follows
v v
+------------+ +------------+
| User C | | User D |
+------------+ +------------+
Storage Options
| Option | Use Case | Trade-off |
|---|
| Adjacency list (MySQL) | < 100M edges | Simple, ACID |
| Graph DB (Neo4j, TAO) | Social graph queries | Fast traversal, complex ops |
| Redis set per user | Fan-out lookup | Ultra-fast reads |
Facebook TAO
- Distributed graph store built on MySQL shards
- Two tables: Objects (users, posts) and Associations (follows, likes)
- Heavy caching layer on top
- Handles billions of edges
9. Media Storage
Client --> Upload Service --> Object Store (S3)
| |
v v
Metadata DB CDN (CloudFront)
(post_id, (serve to clients)
media_url,
dimensions)
Optimization
- Generate multiple sizes: thumbnail (150px), medium (600px), full (1200px)
- Serve responsive images based on device screen
- Lazy load below-the-fold media
- AVIF/WebP with JPEG fallback
10. Post Creation Flow
Client API GW Post Service Fan-out
| | | |
|-- Create post ----->| | |
| |-- Validate ------>| |
| | |-- Store in DB -->|
| | | |
| | |-- Enqueue ------>|
| |<-- 201 Created ---| |
|<-- Post created ----| | |
| | | +------+------+
| | | | Fan-out to |
| | | | followers' |
| | | | feed caches |
| | | +-------------+
Steps
- Client sends post content + media URLs
- API Gateway authenticates and rate-limits
- Post Service validates, stores in Post DB
- Post Service enqueues fan-out event to Kafka
- Fan-out workers read follower list, push to feed caches
- Response returned to client without waiting for fan-out
11. Feed Freshness
Problem
Cached feeds can become stale. New posts from friends may not appear.
Solutions
| Technique | How It Works |
|---|
| Push on write | Fan-out ensures feed cache is updated immediately |
| Pull on open | When user opens app, fetch recent posts from close friends |
| Hybrid refresh | Background job periodically refreshes cold caches |
| Real-time updates | WebSocket/SSE pushes new post IDs to active clients |
Real-Time Feed Update
Fan-out Worker --> Notification Service --> WebSocket to Client
|
"New post from Alice"
Client prepends to feed
12. Notification on New Posts
Post Created --> Kafka --> Notification Service
|
+---------+---------+
| | |
In-App Push Email
Badge (APNs/FCM) (digest)
- Don't notify for every post (notification fatigue)
- Prioritize: close friends > acquaintances > pages
- Batch digest emails: "Here's what you missed today"
13. Complete System Diagram
+--------+ +--------+ +--------+
|Client 1| |Client 2| |Client N|
+---+----+ +---+----+ +---+----+
| | |
+-----+-----+-----+-----+
| |
+------+------+ |
| CDN | |
| (media) | |
+-------------+ |
|
+-------+--------+
| API Gateway |
| (Auth, Rate |
| Limit, Route) |
+---+---+---+---+
| | |
+----------+ | +----------+
| | |
+------+------+ +-----+------+ +----+-------+
| Post | | Feed | | User |
| Service | | Service | | Service |
+------+------+ +-----+------+ +----+-------+
| | |
+----+----+ +-----+------+ +---+--------+
| Post DB | | Feed Cache | | Social |
| (MySQL | | (Redis | | Graph DB |
| sharded)| | Cluster) | | (MySQL/TAO)|
+---------+ +------------+ +------------+
|
+----+--------+
| Kafka |
+----+--------+
|
+----+--------+
| Fan-out |
| Workers |
+----+--------+
|
+----+--------+--------+
| | |
+--+---+ +----+---+ +---+------+
|Feed | |Notif | |Analytics |
|Cache | |Service | |Service |
|Update| +--------+ +----------+
+------+
14. Trade-Off Summary
| Decision | Option A | Option B | Recommendation |
|---|
| Fan-out | On write (push) | On read (pull) | Hybrid |
| Pagination | Offset | Cursor | Cursor |
| Ranking | Chronological | ML-based | ML with chrono fallback |
| Graph store | Relational | Graph DB | Depends on scale |
| Cache | Write-through | Cache-aside | Cache-aside for feed |
15. Interview Tips
- Lead with the hybrid fan-out: This is THE key insight for this problem
- Celebrity problem: Always mention it -- shows you understand scale
- Ranking: At minimum, mention affinity + recency + content type
- Cache is king: Feed cache in Redis is what makes reads fast
- Cursor pagination: Mention the "shifting window" problem with offset
- Don't overcomplicate: If interviewer says "chronological only", skip ML ranking
- Numbers matter: Know that fan-out for 500 friends x 600M posts = 300B writes
16. Resources
- Alex Xu - System Design Interview Vol. 1, Chapter 11: Design a News Feed System
- Facebook Engineering: "Serving Facebook Multifeed" (2015)
- Facebook TAO Paper: "TAO: Facebook's Distributed Data Store for the Social Graph"
- Instagram Engineering: "Scaling the Instagram Explore Feed"
- Twitter Engineering Blog: "The Infrastructure Behind Twitter: Scale"
- Martin Kleppmann - Designing Data-Intensive Applications, Chapter 3 (Indexes)
Previous: 31 - Design Chat System | Next: 33 - Design YouTube or Netflix