Chapter 31 of 33

Design a News Feed

Open Instagram, Facebook, LinkedIn or X and the first thing you see is a news feed: a scrolling list of posts from the people and pages you follow. It looks simple, but behind it sits one of the most famous problems in system design. Every time someone posts, that post must somehow reach the feeds of everyone who follows them, and every time someone opens the app, their feed must load in well under a second.

This chapter designs a news feed end to end. We will use almost everything from earlier chapters: Back-of-the-Envelope Estimation for sizing, Caching for fast reads, Message Queues & Pub/Sub for background work, Database Sharding & Partitioning for scale, and Object Storage & File Storage plus Content Delivery Networks (CDN) for photos and videos. The heart of the chapter is one decision: fan-out on write vs fan-out on read.

A news feed system collects posts from the accounts a user follows, orders them (by time or by relevance) and serves them to the user page by page, quickly and at very large scale.


Step 1: Clarify Requirements

As we learned in How to Approach a System Design Interview, never start drawing before you agree on scope.

Functional Requirements

  • A user can create a post (text, optionally with images or video).

  • A user can follow and unfollow other users.

  • A user can view their feed: posts from people they follow, newest first (we will discuss ranking later).

  • The feed is paginated: infinite scroll loads, say, 20 posts at a time.

Out of scope (say so explicitly): comments, likes counters, notifications, ads, stories, search.

Non-Functional Requirements

  • Low read latency: the feed should load in roughly 200 ms or less at p99 on the server side.

  • High availability: showing a slightly stale feed is far better than showing an error.

  • Eventual consistency is acceptable: if a friend's post appears in your feed 5 seconds late, nobody is harmed. (Recall the CAP Theorem & PACELC and Consistency Models chapters: here we happily choose availability and low latency.)

  • Read-heavy: people scroll far more often than they post.


Step 2: Back-of-the-Envelope Estimation

Assumptions
-----------
Daily active users (DAU)          : 200 million
Posts per user per day            : 0.5      (one post every two days)
Feed loads per user per day       : 10
Average followers per user        : 200
Post text + metadata              : ~1 KB
Posts with an image               : 20%, ~500 KB each
Peak factor                       : 3
Writes (new posts)
  200M × 0.5            = 100 million posts/day
  100M / 86,400         ≈ 1,160 posts/s       (peak ≈ 3,500/s)

Reads (feed loads)
  200M × 10             = 2 billion feed loads/day
  2B / 86,400           ≈ 23,000 reads/s      (peak ≈ 70,000/s)

Fan-out (if we push every post to every follower)
  100M posts × 200      = 20 billion feed inserts/day
  20B / 86,400          ≈ 230,000 inserts/s on average

Storage
  Post text/metadata    : 100M × 1 KB   = 100 GB/day ≈ 36.5 TB/year
  Images                : 20M × 500 KB  = 10 TB/day  (object storage + CDN)

Feed cache (only post IDs, not post bodies)
  500 entries × 16 bytes (8-byte post id + 8-byte timestamp) × 200M users
                        = 1.6 TB of RAM   (spread across a cache cluster)

Three insights come straight out of these numbers:

  • Reads outnumber writes by about 20 to 1, so we should make reads cheap even if writes become more expensive.

  • Pushing every post to every follower is about 230,000 writes per second. Heavy, but manageable for a sharded in-memory cache cluster and an asynchronous worker fleet.

  • The feed cache stores IDs only. Storing full post bodies in every follower's feed would multiply 100 GB/day by 200. IDs keep the raw data at about 1.6 TB. (A real Redis sorted set adds per-entry overhead of several times the raw 16 bytes, so in practice you would provision a few times more RAM, or store feeds in a more compact structure; it is still a cache-cluster-sized number, not a database-sized one.)


Step 3: API Design

Following API Design: REST, GraphQL & gRPC, a simple REST API is enough. Authentication (see Authentication & Authorization: OAuth & JWT) identifies the current user, so the user ID is not in the URL.

POST   /v1/posts                      body: { "text": "...", "media_ids": ["m1"] }
                                      → 201 { "post_id": "1849...", "created_at": "..." }

GET    /v1/feed?limit=20&cursor=<opaque>
                                      → 200 { "posts": [ ... ], "next_cursor": "..." }

POST   /v1/users/{id}/follow          → 204
DELETE /v1/users/{id}/follow          → 204

Notice the cursor instead of a page number. With offset pagination (?page=3), new posts arriving at the top shift everything down and the user sees duplicates. A cursor says "give me posts older than this one", which stays correct even while the feed keeps changing.


Step 4: Data Model

users        (user_id PK, name, avatar_url, created_at)
posts        (post_id PK, author_id, text, media_ids, created_at)
               → sharded by post_id; secondary index on (author_id, created_at)
follows      (follower_id, followee_id, created_at)
               → stored twice: by follower ("whom do I follow?")
                               and by followee ("who follows me?")
feed cache   key: feed:{user_id}  →  list of (post_id, timestamp), newest first,
               capped at ~500 entries (e.g. a Redis sorted set or list)

Post IDs are usually time-sortable 64-bit IDs (a "Snowflake-style" ID: timestamp bits + machine bits + sequence bits). Sorting by ID then means sorting by time, which makes cursors and merging very cheap. The posts table can live in a sharded SQL database or a wide-column store like Cassandra; the SQL vs NoSQL Databases chapter discusses that trade-off. The follow graph is large (200M users × 200 edges = 40 billion edges), so it is sharded too.


Step 5: The Core Decision — Fan-out on Write vs Fan-out on Read

Fan-out on Read (Pull Model)

Nothing special happens when you post. When a user opens the app, the feed service pulls: it fetches the list of people they follow, gets recent posts from each, merges them and sorts.

GET /feed for Asha (follows 300 people)
   → read 300 authors' recent posts  → merge by time  → return top 20

Writes are cheap, but every feed load does hundreds of reads and a big merge. At 70,000 feed loads per second at peak, that is tens of millions of reads per second. Reads are our hot path, so this is the wrong place to do the heavy lifting.

Fan-out on Write (Push Model)

When a user posts, the system immediately pushes the post ID into the cached feed of every follower. Reading a feed becomes a single cache lookup.

Bala posts  → find Bala's 200 followers → append post id to 200 cached feeds
Asha opens app → read feed:asha from cache (one lookup) → hydrate → done

This is perfect for normal users. But consider a cricket star with 250 million followers. One post means 250 million cache writes. Even at a million writes per second, that is over 4 minutes of work for a single post, and most of those followers will not even open the app today. This is the famous celebrity problem (also called the "hot key" or "Justin Bieber" problem).

Comparison

Aspect

Fan-out on write (push)

Fan-out on read (pull)

Work done when posting

High: one write per follower

Tiny: store the post once

Work done when reading

Tiny: one cache read

High: query every followee and merge

Read latency

Very low

Higher, grows with number followed

Celebrity accounts

Terrible (millions of writes per post)

Fine

Inactive users

Wasted work (feeds nobody reads)

No waste

Freshness

Slight delay while fan-out runs

Always up to date at read time

The Answer: A Hybrid

Real systems combine both:

  • Normal users (followers below a threshold, for example 10,000 to 100,000): fan-out on write.

  • Celebrities (above the threshold): no fan-out. Their posts are pulled at read time and merged with the pre-built feed. A user follows only a handful of celebrities, so this merge is small.

  • Inactive users (not logged in for, say, 30 days): skip fan-out for them; build their feed by pulling when they return.

Large platforms such as X (formerly Twitter) have publicly described timelines built this way: pre-computed home timelines held in an in-memory cache, with very high-follower accounts handled separately at read time.


Step 6: High-Level Architecture

                         ┌──────────────┐
  Mobile / Web  ───────▶ │ Load balancer│ ──▶  API Gateway (auth, rate limiting)
                         └──────────────┘              │
                  ┌────────────────────────────────────┼─────────────────────┐
                  ▼                                    ▼                     ▼
          ┌──────────────┐                     ┌──────────────┐       ┌─────────────┐
          │ Post service │                     │ Feed service │       │ Graph svc   │
          └──────┬───────┘                     └──────┬───────┘       │ (follows)   │
     write post  │  publish "post_created"            │ read          └──────┬──────┘
                 ▼              │                     ▼                      │
          ┌──────────────┐      │              ┌──────────────┐              │
          │ Posts DB     │      ▼              │ Feed cache   │◀─────┐       │
          │ (sharded)    │  ┌─────────┐        │ (Redis-like, │      │       │
          └──────────────┘  │  Queue  │──────▶ │  IDs only)   │      │       │
                 ▲          └─────────┘        └──────────────┘      │       │
                 │               │                                   │       │
                 │               ▼                                   │       │
                 │        ┌──────────────┐ get followers             │       │
                 │        │ Fan-out      │ ──────────────────────────┼──────▶│
                 │        │ workers      │ push post id ─────────────┘       │
                 │        └──────────────┘                                   │
                 └──── Post cache (hot post bodies) ◀── hydration           │
   Media: client uploads to object storage (pre-signed URL) → served via CDN

Write Path: Creating a Post

  1. The client uploads any image directly to object storage using a pre-signed URL (see Object Storage & File Storage) and gets back a media ID.

  2. The client calls POST /v1/posts. The post service generates a time-sortable post ID, stores the post in the posts DB, and returns 201 immediately.

  3. The post service publishes a post_created event to a queue (see Message Queues & Pub/Sub). The user does not wait for fan-out.

  4. Fan-out workers consume the event. If the author is a celebrity, they stop. Otherwise they fetch the follower list in batches (say 1,000 at a time), skip inactive users, and append the post ID to each follower's cached feed, trimming each list to ~500 entries.

Because the queue gives at-least-once delivery, a worker may process the same event twice. Making the insert idempotent (a sorted set keyed by post ID simply overwrites the same member) prevents duplicate posts in a feed.

Read Path: Loading the Feed

  1. The feed service reads feed:{user_id} from the cache: a list of post IDs.

  2. It fetches recent posts of the celebrities the user follows (each celebrity's own recent-posts list is itself cached and extremely hot).

  3. It merges the lists by timestamp, applies the cursor, and takes the top 20.

  4. Hydration: it turns the 20 IDs into full posts with a batch lookup in the post cache (falling back to the posts DB), and attaches author names and avatars from a user cache. Media URLs point at the CDN.

  5. It filters out posts that were deleted or that the viewer is blocked from seeing, then returns the page plus next_cursor.

If the feed cache entry is missing (a cache miss, or an inactive user returning), the service falls back to the pull model, builds the feed, and writes it back to the cache. This is the cache-aside pattern from Cache Strategies & Eviction Policies.


Step 7: A Working Hybrid Fan-out in Python

The program below simulates the whole idea in memory: push for normal users, pull for celebrities, a capped cached feed, a k-way merge with heapq.merge, and cursor-based pagination. The celebrity threshold is tiny (3 followers) so we can see the behaviour.

import heapq
from collections import defaultdict, deque

CELEBRITY_THRESHOLD = 3   # followers above this = "celebrity" (tiny for demo)
FEED_LIMIT = 5            # keep only the newest N ids in each cached feed

followers = defaultdict(set)   # author -> set of followers
following = defaultdict(set)   # user   -> set of authors they follow
posts = {}                     # post_id -> (timestamp, author, text)
user_posts = defaultdict(list) # author -> [(timestamp, post_id)], newest last
feed_cache = defaultdict(deque)  # user -> deque of (timestamp, post_id), newest first

clock = 0
next_id = 100

def follow(user, author):
    followers[author].add(user)
    following[user].add(author)

def is_celebrity(author):
    return len(followers[author]) > CELEBRITY_THRESHOLD

def create_post(author, text):
    global clock, next_id
    clock += 1
    next_id += 1
    pid = next_id
    posts[pid] = (clock, author, text)
    user_posts[author].append((clock, pid))
    if is_celebrity(author):
        return pid, 0                      # no fan-out: pulled at read time
    for f in followers[author]:            # fan-out on write (push)
        feed = feed_cache[f]
        feed.appendleft((clock, pid))
        while len(feed) > FEED_LIMIT:
            feed.pop()
    return pid, len(followers[author])

def get_feed(user, limit=4, before=None):
    """Merge pushed feed + pulled celebrity posts, newest first.
    'before' is a cursor: only return posts older than this timestamp."""
    sources = [list(feed_cache[user])]
    for author in following[user]:
        if is_celebrity(author):
            sources.append(sorted(user_posts[author], reverse=True)[:FEED_LIMIT])
    merged = heapq.merge(*sources, reverse=True)
    page = []
    for ts, pid in merged:
        if before is not None and ts >= before:
            continue
        page.append((ts, pid))
        if len(page) == limit:
            break
    cursor = page[-1][0] if len(page) == limit else None
    return page, cursor

# --- build a small social graph ---
for u in ["asha", "bala", "chen", "dev", "esha"]:
    follow(u, "virat")                     # virat has 5 followers -> celebrity
follow("asha", "bala"); follow("chen", "bala")
follow("asha", "chen")

for author, text in [("bala", "Exam tomorrow!"), ("virat", "Match day"),
                     ("chen", "Learning system design"), ("bala", "Passed!"),
                     ("virat", "Thank you fans"), ("chen", "Feed design done")]:
    pid, pushed = create_post(author, text)
    mode = "pull (celebrity)" if is_celebrity(author) else f"pushed to {pushed} feeds"
    print(f"post {pid} by {author:5}: {mode}")

print("\nasha's cached (pushed) feed:", [pid for _, pid in feed_cache["asha"]])
page, cur = get_feed("asha")
print("asha page 1:")
for ts, pid in page:
    print(f"  t={ts} {posts[pid][1]:5} {posts[pid][2]}")
print("next cursor:", cur)
page, cur = get_feed("asha", before=cur)
print("asha page 2:")
for ts, pid in page:
    print(f"  t={ts} {posts[pid][1]:5} {posts[pid][2]}")
print("next cursor:", cur)

Output:

post 101 by bala : pushed to 2 feeds
post 102 by virat: pull (celebrity)
post 103 by chen : pushed to 1 feeds
post 104 by bala : pushed to 2 feeds
post 105 by virat: pull (celebrity)
post 106 by chen : pushed to 1 feeds

asha's cached (pushed) feed: [106, 104, 103, 101]
asha page 1:
  t=6 chen  Feed design done
  t=5 virat Thank you fans
  t=4 bala  Passed!
  t=3 chen  Learning system design
next cursor: 3
asha page 2:
  t=2 virat Match day
  t=1 bala  Exam tomorrow!
next cursor: None

What to notice:

  • Virat's posts (102, 105) were never written into anyone's cached feed, yet they appear correctly interleaved in Asha's feed because they are merged at read time.

  • Page 2 uses the cursor 3 ("older than timestamp 3"), so no post is repeated even if new posts arrive between page loads.

  • heapq.merge merges already-sorted lists in O(n log k) for k lists, which is exactly why each source must already be sorted newest first.


Step 8: Deep Dives

Ranking: Chronological vs Relevance

A pure time-ordered feed is easy to explain and to build. Most big platforms instead rank by predicted interest. A typical ranked feed works in two stages:

  1. Candidate generation: collect a few hundred to a few thousand candidate posts (the pre-built feed, celebrity posts, and possibly recommended posts from accounts you do not follow).

  2. Scoring: a machine learning model scores each candidate using features like how often you interact with the author, post age, post type, and early engagement. The top-scored posts are returned.

The fan-out design does not change: fan-out still produces the candidates. Ranking adds a scoring step on the read path, and scores are usually computed for one page at a time so latency stays low.

Sharding the Feed Cache

1.6 TB of feed IDs does not fit on one machine. Shard the cache by user_id using Consistent Hashing so adding cache nodes moves only a small fraction of keys. Each feed lives on exactly one shard, so a feed read touches one node. Replicate each shard (see Database Replication) so a node failure does not wipe out millions of feeds; and if a feed is lost anyway, it can be rebuilt by pulling.

Hot Posts and Hot Keys

A viral post's body is read millions of times. Keep post bodies in a separate post cache, and for extremely hot keys, replicate them across several cache nodes or add a small in-process cache in the feed service with a short TTL (a few seconds).

Deletes, Edits and Unfollows

  • Delete: do not try to remove the ID from millions of feeds. Mark the post deleted in the posts DB; the hydration step drops it. Background cleanup is optional.

  • Edit: feeds store IDs, so hydration automatically shows the latest version.

  • Unfollow: filter at read time, or run a background job to remove that author's IDs from the user's feed.

Real-Time "New Posts" Banner

To show "5 new posts" without the user refreshing, the client can poll a cheap endpoint every 30 to 60 seconds, or hold a persistent connection (Server-Sent Events or WebSocket, as discussed in Design a Chat Application). For feeds, polling is often good enough and much cheaper than millions of open sockets.


Common Mistakes

  • Picking pure push or pure pull. Each fails at the extremes. Always mention the hybrid and the celebrity problem.

  • Storing full posts in every feed. Store IDs; hydrate at read time. Otherwise storage explodes and edits/deletes become impossible.

  • Fan-out inside the request. The author should not wait for 200 (or 200 million) cache writes. Use a queue and workers.

  • Offset pagination. Feeds change constantly; use cursors based on time-sortable IDs.

  • Unbounded feed lists. Nobody scrolls back 10,000 posts. Cap each cached feed (a few hundred entries) and fall back to pull for deep scrolls.

  • Ignoring inactive users. Pushing to accounts that never log in wastes a large share of fan-out work.


Interview Questions

1. Why is fan-out on write a good default for a news feed?

Because feeds are read far more often than posts are written (about 20:1 in our estimate). Fan-out on write moves the expensive work (finding followers and inserting) to the rarer write path, so the frequent read path becomes a single cache lookup with very low latency.

2. A celebrity with 100 million followers posts. Walk through what happens in your design.

The post is stored once in the posts DB and appended to the celebrity's own recent-posts list (heavily cached). The fan-out worker sees the author is above the follower threshold and does not push. When any follower loads their feed, the feed service merges their pre-built feed with the recent posts of the few celebrities they follow. Cost: a few extra cache reads per feed load instead of 100 million writes per post.

3. Why use cursor-based pagination instead of page numbers for a feed?

New posts are constantly added at the top. With offsets, page 2 shifts after new posts arrive, causing duplicates or skipped posts. A cursor ("posts older than ID/timestamp X") is stable no matter what is inserted above it, and with time-sortable IDs it maps to an efficient range query.

4. A user deletes a post that was already fanned out to 5,000 feeds. How do you handle it?

Mark it deleted (soft delete) in the posts store and invalidate the post cache entry. Feeds hold only IDs, so the hydration step skips deleted posts. Optionally a background job removes the ID from feeds lazily; correctness does not depend on it.

5. The feed cache cluster loses a node. What happens to users whose feeds were there?

With replication, a replica takes over. If data is truly lost, those feeds miss in the cache and the feed service rebuilds them using the pull model (query followees' recent posts), then writes them back. Users see a slightly slower first load, not an error. This is why the cache is treated as a rebuildable copy, not the source of truth.

6. Estimate fan-out writes per second if 50M posts/day are made and the average user has 300 followers.

50M × 300 = 15 billion inserts/day. 15 × 109 / 86,400 ≈ 174,000 inserts per second on average, and around 520,000 per second at a 3× peak. Skipping celebrities and inactive users reduces this substantially.


Summary

  • A news feed is read-heavy, latency-sensitive and tolerant of eventual consistency.

  • Fan-out on write makes reads cheap; fan-out on read makes writes cheap. The hybrid (push for normal users, pull for celebrities, skip inactive users) is the standard answer.

  • Feeds store post IDs only, capped in length, in a sharded in-memory cache; full posts are hydrated at read time.

  • Fan-out runs asynchronously through a queue and workers, with idempotent inserts.

  • Use time-sortable IDs and cursor pagination; media goes to object storage and a CDN.

  • Ranking adds a scoring stage on top of candidate generation; the fan-out design stays the same.

Do the heavy work on the rare path, keep the frequent path to a single lookup, and treat celebrities as the exception they are.