News Feed (Twitter / Instagram)

Fan-out on write vs read, ranking, media and celebrity users.

• Advanced
• 42 min read
• 3 objectives

Before this lessonLesson 8: Key-Value Store and Pastebin

Design a home timeline: a user opens the app and sees a ranked list of posts from people they follow. It must feel instant for a normal user and still work when a celebrity posts to tens of millions of followers.

Step 1 — Clarify

• Text only, or images and video? Likes and comments in v1 or v2?
• Reverse chronological, or ranked?
• Follow graph size? Celebrity accounts?
• How fresh must a new post be in a follower's feed (seconds vs minutes)?

v1: publish, follow/unfollow, paginated feed. Media allowed (pointers, not bytes). Ranking can start as recency. Eventual consistency is OK — a post may appear a second late. Likes can be a counter service, not in the first schema if time is short.

Step 2 — Scale

dau = 200_000_000
posts_per_user_day = 0.5
posts_per_sec = dau * posts_per_user_day / 86_400
feed_loads = dau * 10 / 86_400
avg_fanout = 200                  # average follower count
celebrity = 50_000_000
print("posts/s", round(posts_per_sec))
print("feed loads/s", round(feed_loads))
print("naive fanout writes/s", round(posts_per_sec * avg_fanout))
print("one celebrity post writes", celebrity)

posts/s 1157
feed loads/s 23148
naive fanout writes/s 231481
one celebrity post writes 50000000

Reads dominate feed loads. A naive join of all followees on every open cannot work. A naive fan-out of every post to every follower also cannot work for celebrities — 50 million writes for one tap.

Step 3 — API and data model

POST /v1/posts          { text, media_ids[] } -> { post_id }
POST /v1/follow         { user_id }
GET  /v1/feed?cursor=   -> { items[], next_cursor }

users(user_id, name, is_celebrity)
posts(post_id, author_id, text, media_keys, created_at)   -- PK post_id; index author_id + created_at
follows(follower_id, followee_id)                          -- both directions indexed
timeline(user_id, ts, post_id, author_id)                  -- PK (user_id, ts, post_id)
-- media in object storage + CDN

IDs are Snowflake-style so post_id is roughly time-ordered. The timeline table (or a Redis list) is a precomputed inbox of post ids for one user — that is fan-out on write.

Step 4 — High-level design

flowchart TB subgraph pub [Publish] U[User] --> API[Post API] API --> P[(Posts)] API --> Q[Fan-out queue] Q --> W[Workers] W --> T[(Timeline Cassandra / Redis)] end subgraph feed [Feed load] V[Viewer] --> F[Feed API] F --> C[(Redis page-1 cache)] C -->|miss| T F --> Merge[Merge celebrity posts] Merge --> P end

A publish stores the post once, then workers copy the id into ordinary followers' inboxes. Feed load reads the inbox and merges a few celebrity pulls.

Step 5 — Fan-out on write vs read vs hybrid

On write (push)

At publish time, enqueue jobs that prepend post_id to each follower's timeline (keep last ~800–1000 ids). Reads are a range scan plus cache. Cost: O(followers) writes. Skip inactive users; hydrate them on next login.

On read (pull)

At feed-load time, fetch recent posts of everyone you follow and merge. Cheap writes, expensive reads. Fine if you follow 50 people; painful at 2,000 followees and 20k QPS of feed opens.

Hybrid — the design you should give

Push for regular accounts. Mark celebrities (or anyone over a follower threshold) as pull. When loading a feed: read the precomputed timeline, plus the latest posts of the celebrity followees, merge by time/rank, cache page 1. You never write 50 million timeline rows for one celebrity post.

Step 6 — Deep dives

Ranking

v1: reverse chronological. v2: candidate set of ~500–1000 ids (inbox + celebrity pulls + maybe a 'discover' source), then a ranker (recency, affinity, media, seen). Rank asynchronously; cache the ranked first page for a minute. Do not run a model on every scroll event in v1.

Pagination

Cursor = (ts, post_id), never OFFSET. OFFSET walks skipped rows and breaks if new posts arrive at the top.

Cache

Redis list or JSON of page 1 per user. On a push, LPUSH and trim. TTL as a safety net. Hot celebrities' recent posts cached once, reused by every hybrid merge.

Media

Client uploads to object storage via a pre-signed URL. The post stores keys. A CDN serves images. Video uses the transcode pipeline from the video lesson.

Unfollow, mute, block

Applied at read time from small filter sets (Redis). Do not rewrite 800 timeline rows on unfollow; skip those authors when rendering. Optionally a background job to compact later.

// Write your solution here