System Design Interview · Very Common

Design Twitter (News Feed)

The most important aspect is designing the news feed generation at scale. This involves the classic fan-out trade-off.

1. Requirements

Functional

· Post tweets (text, images, videos)
· Follow / unfollow users
· View home timeline (chronological feed)
· View user profile timeline
· Like and retweet
· Search tweets

Scale Assumptions

· 300M monthly active users
· 500M tweets posted per day
· Average user follows 200 accounts
· Average 100 followers per user
· Home timeline reads: 300M/day
· Read:Write = ~100:1

2. Estimation

Tweet QPS: 500M/day ÷ 86,400 ≈ 5,800 write QPS Feed reads: 300M/day × 5 reads each ≈ 1,500M/day = 17,400 read QPS Fan-out on write (per tweet): Avg 100 followers × 5,800 QPS = 580,000 writes/sec to feed caches Celebrity (1M followers): 1M × 1 tweet = 1M cache writes per tweet (This is the CELEBRITY PROBLEM) Storage: Tweet: 140 chars = ~280 bytes + metadata = ~1 KB 5,800 QPS × 1 KB × 86,400 × 365 ≈ 178 TB/year Media (10% tweets have images): 580 QPS × 200 KB × 86,400 × 365 ≈ 3.6 PB/year → store in S3

3. The Core Design Challenge: Fan-out

Fan-out on WRITE (Push)

When a user tweets, immediately push the tweet ID to all followers' feed caches (Redis sorted sets).

✓ Fast reads (precomputed feed)

✓ Feed always ready instantly

✗ Huge write amplification

✗ Celebrity problem: 1M followers = 1M writes per tweet

✗ Wasteful for inactive users

Best for: Regular users with <10K followers

Fan-out on READ (Pull)

When a user opens their feed, fetch latest tweets from all followed users and merge-sort them.

✓ No write amplification

✓ Handles celebrities naturally

✗ Slow reads (N DB queries per feed load)

✗ Doesn't scale for users following 1000+ accounts

Best for: Celebrity accounts with millions of followers

Twitter's Actual Solution: Hybrid Approach

Regular users (<10K followers): Fan-out on write. Tweet is pushed to followers' feed caches at write time.
Celebrity users (>1M followers, e.g. verified): Fan-out on read. Their tweets are fetched and injected at read time.
At feed load time: Merge precomputed feed (regular users) + live fetch celebrities' recent tweets → sort by timestamp.

4. Architecture

POST /tweet ↓ Tweet Service ──→ Tweet DB (Cassandra — high write throughput) ↓ Kafka (tweet_posted event) ↓ Fan-out Service (consumers) │ ├── [Regular User] → push tweet_id to all followers' feed cache │ Redis Sorted Set: key = user_id, score = timestamp, value = tweet_id │ └── [Celebrity User] → skip fan-out; celebrity's tweets fetched on read GET /home_timeline?userId=123 ↓ Feed Service │ ├── Read precomputed feed from Redis (tweet_ids, paginated) ├── Fetch celebrity tweets user follows (fan-out on read) ├── Merge + deduplicate + sort by timestamp └── Hydrate tweet_ids → full tweet objects (from Tweet Cache or DB) ↓ Return top N tweets to user Media Storage: Tweet with image → Upload to S3 → CDN serves to users No media served from application servers

5. Database Choices & Rationale

Data	Storage	Why
Users, follows	MySQL	Relational data. Needs JOIN (user → follow → user). ACID transactions.
Tweets	Cassandra	High write QPS (5,800/sec). Partition by user_id. Time-series by tweet_id (Snowflake ID encodes time).
Feed cache	Redis Sorted Set	O(log n) inserts/reads. Score = tweet timestamp. Range queries for pagination.
Tweet search	Elasticsearch	Full-text search. Inverted index on tweet content. Near real-time indexing.
Media	S3 + CDN	Object storage for photos/videos. CDN edge caches for read performance.
Trending topics	Redis Counter	Increment counter per hashtag per time window. Top-K using sorted set.
Notifications	Cassandra	Append-heavy, time-series. Query by user_id + timestamp for notification feed.

6. Bottlenecks & Solutions

⚠️ Celebrity user posts a tweet → 50M fan-out writes (e.g. @BarackObama with 130M followers)

→

Identify celebrities at write time (follower count > threshold). Skip fan-out for them. Inject their tweets at read time. Redis pipeline for batch writes for regular users.

⚠️ Feed cache is cold on first app open

→

On user login, async warm their cache with latest 100 tweets. Background job pre-populates caches for users who log in regularly (predicted by ML).

⚠️ Tweet DB hot partition (all tweets for a celebrity in one Cassandra node)

→

Cassandra partition key = (user_id + date). Date bucketing distributes load across nodes over time. Add read replicas for popular user_ids.

⚠️ Redis memory limit (feed cache is large at scale)

→

Store only tweet_ids in Redis sorted set (8 bytes each). Full tweet content fetched from Tweet Cache/DB. Cap feed size at 1000 entries per user; evict oldest.

7. Key Trade-offs Summary

Decision	Option A	Option B	Chosen & Why
Fan-out strategy	Push (write-time)	Pull (read-time)	Hybrid: push for regular, pull for celebrities
Tweet storage	MySQL	Cassandra	Cassandra — handles 5.8K write QPS, scales horizontally
Feed storage	DB table	Redis sorted set	Redis — O(log n) operations, sub-ms reads
Feed delivery	Polling	WebSocket/SSE	Long polling or WebSocket for real-time updates
Consistency	Strong (SQL)	Eventual (NoSQL)	Eventual — users tolerate 100ms stale timeline
Media	App server	S3 + CDN	S3 + CDN — infinite scale, fast edge delivery

8. Follow-up Questions

Q: How would you implement trending topics?

A: Sliding window counter per hashtag. Every tweet increments hashTag counter for current time window (e.g. 15-minute buckets). Aggregate buckets over past hour. Top-K via Redis sorted set. Decay older windows to give recency bias.

Q: How do you handle tweet deletion (right to be forgotten)?

A: Soft delete: mark tweet as deleted in DB. Lazy propagation: remove from Redis caches on next access. Background job reconciles deleted tweets from feed caches. Fan-out deletion event via Kafka.

Q: How would you design the search feature?

A: Real-time indexing: as tweet is created, push to Elasticsearch via Kafka consumer. Elasticsearch inverted index on tweet text. Sharding by tweet_id range. Search ranking: recency + engagement score (likes + retweets). Cache popular queries in Redis.

Q: What if a user follows 10,000 accounts?

A: Fan-out on read for this user (too many accounts to merge efficiently from cache). Build their feed on read by querying recent tweets from each followed account. Pagination helps: only need latest 200 tweets. Precompute during off-peak hours.

← URL Shortener Rate Limiter →