Designing a News Feed

The "News Feed" is the core of Facebook, Instagram, and Twitter. The challenge isn't storing posts; the challenge is retrieving the right posts for a user in milliseconds.

1. Requirements

Functional

• Post: User can upload image/text.
• Follow: User can follow others.
• Feed: User sees a list of posts from people they follow.

Non-Functional

• Latency: Feed generation must be < 200ms.
• Availability: Posting must succeed even if the feed is delayed.
• Lag: Ideally, a new post appears in followers' feeds within 5 seconds.

2. API Design

GET /feed?cursor=123&limit=10

• Cursor: Don't use OFFSET. Use a cursor (Timestamp or ID) for efficient pagination.

3. Architecture Approaches

Approach 1: Pull Model (Fan-out on Read)

When User Bob loads his feed:

1. Fetch Following: Get IDs of everyone Bob follows (e.g., 500 users).
2. Fetch Posts: Query DB: SELECT * FROM posts WHERE user_id IN (500_ids) ORDER BY time DESC LIMIT 10.
3. Merge: Return to Bob.

• Pros: Writes are fast ($O(1)$). No storage overhead.
• Cons: Reads are Slow ($O(N)$). If Bob follows 5,000 users, the query is heavy. Twitter crashed frequently in 2010 due to this.

Approach 2: Push Model (Fan-out on Write)

We pre-compute the feed. Every user has a "Home Feed" list (Redis List) stored in memory.

When Alice posts:

1. Fetch Followers: Get IDs of everyone following Alice (e.g., 500 users).
2. Push: Insert Post ID into all 500 Redis lists.
3. Read: When Bob loads his feed, we just return GET Bob_Feed_List.

• Pros: Reads are Instant ($O(1)$).
• Cons: Writes are slow ($O(N)$). "The Celebrity Problem".

The "Celebrity" Problem (Thundering Herd)

Justin Bieber has 100 Million followers. If he tweets, Approach 2 means we have to do 100 Million Redis writes instantly. This creates a massive lag/backlog.

4. The Hybrid Solution (Instagram/Twitter)

We combine both models based on the user type.

1. Normal Users: Use Push.
   • If I post (100 followers), push it to their feeds.
2. Celebrities (VIPs): Use Pull.
   • If Bieber posts, don't push it to 100M lists. Just save it to his DB.
3. Reading the Feed:
   • When Bob loads his feed, we fetch his pre-computed "Push" feed.
   • We also check: "Does Bob follow any VIPs (Bieber)?"
   • If yes, we fetch Bieber's latest posts (Pull) and merge them into the feed at runtime.

5. Storage

Relational DB (Postgres/MySQL)

• Users: Profile data.
• Follows: Graph relationships (User A -> User B).
• Metadata: Post text, geotags.

NoSQL / Blob (Cassandra + S3)

• Media: Images/Videos go to S3. CDN handles delivery.
• UserFeed: Redis (for active users) + Cassandra (for archived feed history).

6. Feed Ranking (Algorithmic Feed)

A chronological feed is easy. An algorithmic feed (Facebook style) is harder.

1. Candidate Generation: Get 1,000 recent posts from friends.
2. Scoring: Weigh features.
   • EdgeRank = Affinity * Weight * Time_Decay
   • Probability of click? Probability of Like?
3. Sorting: Return Top 10 by score.

7. Back-of-Envelope: Sizing the Fan-Out

Numbers make the design decisions concrete. Assume Instagram-like scale:

Users:               500M daily actives
Posts:               100M/day  ≈ 1,150 posts/sec average, ~5,000/sec peak
Avg followers:       200
Fan-out writes:      1,150 × 200 = 230,000 feed inserts/sec (average!)
Feed reads:          500M users × 10 loads/day ≈ 58,000 reads/sec

The asymmetry is the whole story: fan-out multiplies every write by the follower count, turning 1,150 posts/sec into 230K+ inserts/sec, while reads stay comparatively modest. This is why the fan-out happens asynchronously through a message queue — the posting user gets a 200 OK immediately, and workers drain the fan-out backlog within seconds. The "5-second lag" non-functional requirement exists precisely to buy this freedom.

Memory check for the Redis feed cache: 500M users × 800 entries × ~20 bytes (post ID + score) ≈ 8 TB — feasible across a sharded Redis fleet, but only because feeds are capped. Uncapped feeds would be 10x that. Cap each stored feed (Instagram-style, a few hundred to a thousand entries) and fall back to pull for deep scrollback.

8. Consistency Corners That Bite

• Unfollow/block: Bob unfollows Alice, but Alice's posts are already sitting in Bob's precomputed feed. Purging them eagerly from millions of lists is expensive; most systems filter at read time instead (check the follow set when assembling the response) — precomputed lists are treated as candidates, not truth.
• Post deletion: same shape — the post ID remains in follower feeds but the hydration step (fetching post content by ID) discovers the tombstone and drops it. This is why feeds store IDs, never denormalized content.
• Idempotent fan-out: queue workers crash and retry; without idempotency (e.g., Redis ZADD, which is naturally idempotent per member), users see duplicate posts. Choosing a sorted-set with post-ID as member makes retries harmless.
• New followers: when Bob follows Alice, does her back-catalog appear in his feed? A backfill job pulls her recent posts into his list — an on-follow "mini fan-out" that also runs async.

9. Sharding the Feed Store

At 8TB of feed state, one Redis node won't do. Shard by user ID (the feed owner), so one user's feed read touches exactly one shard — feed reads stay single-hop. Consistent hashing keeps resharding cheap as the fleet grows. The follow graph, meanwhile, shards by followee for fan-out ("who follows Alice?") — accepting that the two access patterns want two differently-partitioned copies of the data is a hallmark of mature social-graph design.

Interview Follow-Ups Worth Rehearsing

• "Where's the cutoff for 'celebrity'?" It's a tunable measured in fan-out cost, not fame — commonly 10K–100K followers. Users cross the threshold dynamically; a migration job flips their delivery mode.
• "Chronological vs. ranked?" Ranking changes the read path: instead of returning the top of the Redis list, you fetch ~1,000 candidates, hydrate features, score with a model, and re-sort — adding tens of milliseconds and an ML serving dependency. See ML Model Serving.
• "What about ads and suggested posts?" They're injected at merge time — the feed assembler blends organic candidates, ads, and recommendations under position rules ("no two ads within 4 slots"), which is another argument for assembling feeds at read time from candidate sources.

Summary

1. Pull: Good for small scale / VIPs.
2. Push: Good for high read throughput / normal users.
3. Hybrid: Best of both worlds. Push for most, Pull for celebrities.
4. Async everything: fan-out through queues, backfill on follow, filter at read time.

Related Concepts

• Message Queues
• Consistent Hashing
• Redis Internals
• Caching Strategies