The problem
Design the home timeline of a social network: users publish posts, follow others, and see a feed of posts from people they follow, newest (or most relevant) first.
1. Requirements and estimates
- Publish a post (text plus optional media); follow/unfollow; read home feed with infinite scroll.
- 300M DAU, each opening the feed ~10 times a day: 3B feed reads/day ≈ 35k/s average, ~100k/s peak. Posts: ~50M/day ≈ 600/s.
- Feed load under ~200 ms. A new post may take a few seconds to appear for followers (eventual consistency is fine).
- Average 200 followers, but some accounts have 100M.
Reads vastly outnumber writes, so we want reading a feed to be cheap.
2. Two ways to build a feed
Fan-out on read (pull). At read time, fetch recent posts from everyone the user follows and merge them. Writing is trivial; reading is expensive (hundreds of lookups per feed load) and slow for users who follow many accounts.
Fan-out on write (push). When someone posts, insert the post id into each follower’s precomputed feed list (in Redis). Reading is a single list read. But a celebrity with 100M followers triggers 100M writes per post, and you waste work on inactive followers.
Hybrid. Push for normal accounts; for celebrities (above a follower threshold), don’t push. At read time, merge the precomputed feed with recent posts pulled from the few celebrities the user follows.
"""News feed: fan-out on write (push) vs fan-out on read (pull), with a celebrity hybrid."""
from collections import defaultdict
import heapq
FOLLOWERS = defaultdict(set) # author -> followers
FOLLOWING = defaultdict(set) # user -> authors they follow
POSTS = defaultdict(list) # author -> [(timestamp, text)]
FEEDS = defaultdict(list) # user -> precomputed [(timestamp, author, text)]
CELEBRITY_THRESHOLD = 3 # tiny for the demo; real systems use ~10k+ followers
def follow(user, author):
FOLLOWERS[author].add(user)
FOLLOWING[user].add(author)
def is_celebrity(author):
return len(FOLLOWERS[author]) >= CELEBRITY_THRESHOLD
def publish(author, ts, text):
POSTS[author].append((ts, text))
if is_celebrity(author):
return 0 # don't push: followers will pull at read time
for f in FOLLOWERS[author]: # push into each follower's precomputed feed
FEEDS[f].append((ts, author, text))
return len(FOLLOWERS[author])
def read_feed(user, limit=5):
pushed = FEEDS[user]
pulled = [(ts, a, text) for a in FOLLOWING[user] if is_celebrity(a) for ts, text in POSTS[a]]
return heapq.nlargest(limit, pushed + pulled)
if __name__ == "__main__":
for u in ("u1", "u2", "u3"):
follow(u, "star")
follow("u1", "friend")
print("friend post fan-out writes:", publish("friend", 1, "lunch?"))
print("star post fan-out writes:", publish("star", 2, "new album out"))
for ts, author, text in read_feed("u1"):
print(f"u1 sees @{author} t={ts}: {text}")
friend post fan-out writes: 1
star post fan-out writes: 0
u1 sees @star t=2: new album out
u1 sees @friend t=1: lunch?
The celebrity’s post costs zero fan-out writes, yet appears in the follower’s feed because it’s merged in at read time.
3. Architecture
post API --> post store (by post_id) + media to object storage/CDN
--> "PostCreated" event --> fan-out workers --> feed cache (Redis list per user, last ~800 ids)
^ follower lists from social-graph store
feed API --> feed cache (ids) + celebrity posts --> hydrate ids with post/user caches --> rank --> page
- Post store: posts keyed by id (sharded). Ids are time-sortable (Snowflake-style: timestamp + machine + sequence) so sorting by id ≈ sorting by time.
- Social graph store: who follows whom, both directions.
- Feed cache: per-user list of the latest post ids, trimmed to a few hundred. Only ids are stored; post bodies are fetched (“hydrated”) from a post cache, so editing a post doesn’t require touching millions of feeds.
- Fan-out workers consume post events from a queue (lesson 8), so publishing returns immediately.
Optimisations: skip fan-out to users inactive for 30+ days (rebuild their feed on next login), and process fan-out in batches.
4. Ranking
Chronological feeds are easy: merge by id. Ranked feeds take a candidate set (say the latest 500 ids) and score each with features such as recency, author affinity, engagement and content type, then sort. Ranking runs at read time on the candidates, or partially precomputed.
5. Pagination
Use cursor pagination keyed by post id (“posts older than id X”), never offsets (lesson 9): new posts arriving at the top would otherwise shift everything.
6. Deep dives
- Deletes and unfollows: filter at read time (check the post still exists, the author is still followed) rather than scrubbing millions of feed lists immediately.
- Hot posts: viral posts are read by everyone; keep them in replicated caches and the CDN.
- Cold start: a new user’s empty feed is filled from popular or suggested content.
Key takeaways
- Push (fan-out on write) makes reads cheap; pull (fan-out on read) makes writes cheap; the hybrid handles celebrities.
- Store only post ids in per-user feed caches and hydrate on read.
- Do fan-out asynchronously from an event queue; skip inactive users.
- Use time-sortable ids and cursor pagination; rank a bounded candidate set at read time.
Exercises
- Modify
feed_fanout.pyto skip inactive followers and to rebuild a feed on demand when an inactive user returns. - Estimate Redis memory for feed caches: 300M users × 800 ids × 8 bytes, plus overhead. Is it worth only caching active users?
- Design how “unfollow” should affect an existing feed cache.
Quiz
- Why is fan-out on write a problem for celebrities?
- Why do feed caches store post ids rather than full posts?
- What’s the read-time cost of the hybrid approach?
Show answers
- One post would require writing into tens of millions of feed lists, causing huge write spikes and delays.
- Ids are small, and post content can change (edits, deletes, like counts); hydrating from a post cache keeps a single source of truth.
- At read time you must also fetch recent posts from each followed celebrity and merge them with the precomputed feed.