Design a News Feed

The question

"Design the home feed of a social app: users follow others and see a reverse-chronological feed of their posts."

Clarify the requirements

• Functional: create posts (text + image links); follow users; home feed of followed users' posts, newest first, paginated.
• Scale: 200 million daily active users; on average 200 follows each; some accounts have 50 million followers; users post ~1 time/day and open the feed ~10 times/day.
• Non-functional: feed loads in < 300 ms; a new post may take a few seconds to appear (eventual consistency is fine); feed must be highly available.
• Out of scope: ranking by relevance (we'll mention it), ads, comments.

Estimate the scale

• Posts: 200M/day ≈ 2,300 posts/s.
• Feed reads: 2B/day ≈ 23,000 reads/s (peak ~70,000/s). Ten reads for every write: optimise reads.
• Fan-out if we push each post to all followers: 2,300 posts/s × 200 followers ≈ 460,000 feed inserts/s, which is heavy but parallel and spread across workers.
• One post from a 50M-follower account would mean 50 million inserts: the celebrity problem.

API and data model

POST /posts                 { text, image_url }
POST /follow/{user_id}
GET  /feed?cursor=...&limit=20   -> { posts: [...], next_cursor }

posts:   post_id (time-sortable, e.g. snowflake) | author_id | text | image_url | created_at
follows: follower_id | followee_id
feed cache (Redis): feed:{user_id} -> list of the latest ~800 post_ids

High-level design

            write path                                       read path
author ─► post service ─► posts DB              reader ─► feed service ─► feed cache (post ids)
                │                                                   │          └─► celebrity posts (pull)
                └─► queue ─► fan-out workers ─► feed cache            └─► post cache (hydrate ids -> posts)
                                   (followers lookup)

• Write: store the post, then a queue hands it to fan-out workers that prepend the post ID to each follower's cached feed.
• Read: read the user's list of post IDs, merge in recent posts from any celebrities they follow, then hydrate the IDs into full posts from a post cache.

Deep dives

1. Push vs pull.

The hybrid: push for normal accounts, pull for accounts above a follower threshold (say 100,000). Readers merge the two at read time.

CELEBRITY_THRESHOLD = 3            # tiny for the demo; ~100,000 in real life

follows = {                        # follower -> followees
    "ana": ["ben", "cat", "star"],
    "ben": ["ana", "star"],
    "dan": ["ana", "ben", "cat", "star"],
}
followers = {}
for f, followees in follows.items():
    for e in followees:
        followers.setdefault(e, []).append(f)
followers["star"] += ["fan1", "fan2", "fan3"]   # star has 6 followers

feeds = {}                         # precomputed feed cache: user -> [post ids], newest first
posts_by_author = {}               # for pulling celebrity posts at read time
writes = 0


def publish(post_id, author):
    global writes
    posts_by_author.setdefault(author, []).insert(0, post_id)
    if len(followers.get(author, [])) >= CELEBRITY_THRESHOLD:
        return                      # celebrity: don't fan out, readers pull
    for f in followers.get(author, []):
        feeds.setdefault(f, []).insert(0, post_id)
        writes += 1


def read_feed(user, limit=5):
    pushed = feeds.get(user, [])
    pulled = [p for celeb in follows.get(user, []) if len(followers.get(celeb, [])) >= CELEBRITY_THRESHOLD
              for p in posts_by_author.get(celeb, [])]
    return sorted(set(pushed + pulled), reverse=True)[:limit]    # ids are time-sortable


for post_id, author in [(101, "ben"), (102, "star"), (103, "cat"), (104, "ana"), (105, "star")]:
    publish(post_id, author)

print("feed inserts written:", writes, "(star's 2 posts would have added 12)")
for user in ["ana", "ben", "dan"]:
    print(f"{user}'s feed:", read_feed(user))

feed inserts written: 6 (star's 2 posts would have added 12)
ana's feed: [105, 103, 102, 101]
ben's feed: [105, 104, 102]
dan's feed: [105, 104, 103, 102, 101]

2. Pagination. Use a cursor (the last post ID seen) rather than page numbers: new posts at the top don't shift what the next page returns.

3. Feed cache size. Keep only the latest few hundred IDs per user; older pages fall back to a slower pull. Don't precompute feeds for users who haven't logged in for 30 days; build theirs on demand.

4. Ranking (if asked). Generate candidates (the chronological feed plus a few extras), score them with a model (likes, recency, relationship), and cache the ranked list briefly.

Trade-offs

• Push vs pull vs hybrid: read latency vs write amplification.
• Freshness: precomputed feeds are seconds behind; acceptable here, stated explicitly.
• Storing IDs vs full posts in feeds: IDs keep the cache small and let edits and deletions show up via the post cache.
• Deletes and unfollows: filter at read time (cheap) rather than purging every feed (expensive).

What interviewers look for

• The push/pull trade-off and the celebrity problem, with a hybrid.
• Separating the write path (async fan-out) from the read path (cache + hydrate).
• Cursor pagination and time-sortable IDs.
• Numbers that show why fan-out cost matters.

Key points

• Push for normal users, pull for celebrities, merge at read time.
• Fan-out runs asynchronously through a queue.
• Feed caches hold post IDs; hydrate from a post cache.
• Cursor-based pagination; skip precomputing feeds for inactive users.