Walkthrough 3 — Design a News Feed (Twitter/Instagram)

# Design a News Feed (Twitter/Instagram) ## The brief Design the home feed for a social platform. Users follow others; feed shows recent posts from followed accounts. ## Step 1: Requirements - User posts text/images/video. - Users follow each other. - Home feed: chronological or ranked recent posts from followed users. - 100M DAU; avg 200 followers per user. - Read-heavy: feed views 100x more than posts. - Sub-second latency for feed load. ## Step 2: Capacity estimation - 100M DAU × 0.5 posts/day = 50M posts/day → ~580 posts/sec average. Peak: 5K/sec. - 100M DAU × 100 feed loads/day = 10B feed loads → ~116K feed loads/sec. - Storage: 50M posts/day × 1KB = 50GB/day = 18TB/year. With media (10-100KB/post): petabyte scale. ## Step 3: High-level design ``` [Client] ↓ [API Gateway] ↓ [Web Service] ↓ [Post Service] [User Service] [Feed Service] ↓ ↓ ↓ [Posts DB] [Users + Follow DB] [Feed cache] ↓ [Media Storage (S3)] [CDN] ``` ## Step 4: Two main approaches ### Push (fan-out on write) When user posts, push to all followers' feeds. Pros: feed reads are fast (already materialized). Cons: celebrity problem (Justin Bieber posts → 100M writes); write-heavy. ### Pull (fan-out on read) When user opens feed, query posts from all followed users; merge. Pros: write is cheap. Cons: feed reads are slow (100s of queries per load). ### Hybrid (most production systems) - Push for normal users (< 10K followers). - Pull for celebrities (followers fetch their posts at read time). - Merge at feed-load time. ## Step 5: Push fan-out architecture When user posts: ``` 1. Save post to Posts DB. 2. Async: push post_id to followers' feed cache. - Get followers from Follow DB. - For each follower: prepend post_id to their feed (Redis list). - Use a worker pool (Kafka consumer). 3. Truncate each feed to last 1000 posts. ``` ``` Post Service → Posts DB → Kafka topic "new_posts" → Fan-out workers → Redis (per-user feeds) ``` Feed read: ``` 1. Read user's feed cache (list of post_ids). 2. Fetch posts in batch from Posts DB / cache. 3. Return. ``` Storage: - Posts DB: relational (Postgres sharded) or KV (Cassandra). Cassandra fits write-heavy. - Feed cache: Redis. Each user's feed = list of last 1000 post_ids. ## Step 6: Handle the celebrity problem A celebrity with 100M followers: - Each post = 100M cache writes. Slow, expensive, async lag. Solution: don't push for celebrities. Mark them; for their followers, the feed service fetches their recent posts at read time and merges with the pre-computed feed. Threshold: e.g., > 1M followers triggers pull mode. ## Step 7: Feed ranking Chronological is simple. Modern feeds rank by engagement prediction: - Features: post recency, user's past engagement with author, content type, etc. - ML model scores each post; top N shown. Architecture: ranking service called by feed service; takes post candidates → returns ranked order. For interview simplicity: assume chronological. Mention ranking as an extension. ## Step 8: Media handling Photos/videos: - Upload to S3 directly (presigned URLs). - CDN in front for delivery. - Original + thumbnails (multiple sizes). - Transcoding: queue for video processing. ## Step 9: Caching layers - Feed cache (Redis): per-user feed of recent post_ids. - Post content cache: hot posts cached. - User profile cache: usernames, avatars (high read rate). - CDN: media. ## Step 10: Data model ```sql -- Posts CREATE TABLE posts ( post_id BIGINT PRIMARY KEY, user_id BIGINT NOT NULL, content TEXT, media_urls TEXT[], created_at TIMESTAMP, INDEX (user_id, created_at) ); -- Follows CREATE TABLE follows ( follower_id BIGINT, followee_id BIGINT, created_at TIMESTAMP, PRIMARY KEY (follower_id, followee_id) ); CREATE INDEX idx_followee ON follows(followee_id); ``` For Cassandra: ``` posts_by_user: partition by user_id, cluster by created_at DESC. feed_cache: partition by user_id, list of post_ids. ``` ## Step 11: Sharding - Posts: shard by user_id (most queries are per-user). - Follows: replicated graph DB might fit; or RDBMS sharded. - Feed cache: shard by user_id (Redis Cluster). ## Common follow-ups - **Replies/threads?** Each reply is a post with `parent_post_id`. Recursive query (or pre-computed thread). - **Notifications?** Separate notification service; pub-sub on post events. - **Search?** Elasticsearch indexed on post content + tags. - **Direct messages?** Separate service; not part of feed. - **Trending topics?** Stream processor (Flink) over post stream; sliding window count. ## Self-rubric - [ ] Clarified requirements - [ ] Estimated scale (DAU, QPS, storage) - [ ] Identified push vs pull trade-off - [ ] Designed hybrid (push for normal, pull for celebrities) - [ ] Designed feed cache (Redis lists) - [ ] Handled fan-out via async queue - [ ] Discussed sharding strategy - [ ] Addressed media via S3 + CDN - [ ] Drew the system diagra