beginnerintermediateadvanced

System Design · Section 85

Social Feed Design

Level: advanced
Read: 18 min
Concepts: 2

A feed is a join between "who I follow" and "what they posted", and the first decision is when to pay for that join. Fan-out-on-write pushes each new post into a precomputed list for every follower at publish time, making reads a single cheap range fetch and writes proportional to follower count. Fan-out-on-read stores each post once and merges at query time, making writes trivial and reads proportional to following count. Consumer feeds are read-dominated, which argues for fan-out-on-write — until follower-count skew is taken into account, because one post from an account with tens of millions of followers produces tens of millions of writes from a single tap, with no natural smoothing. The working answer is a hybrid: fan out below a follower threshold, skip fan-out entirely above it, and merge those large accounts in at read time, which bounds write cost by the threshold and read cost by how many large accounts one person follows. Fan-out also runs asynchronously behind a durable post write, so publish latency stays constant and propagation delay becomes measurable queue lag. Four read-path decisions follow, all tuned by the same two signals — skew and read-to-write ratio. Caching is unusually effective because a user re-reads their feed far more often than it changes, and large accounts' timelines are read by everyone. Ranking runs over a bounded candidate set retrieved first, never over the whole corpus, so read latency depends on page size rather than history size. Pagination must be cursor-based, because a feed inserts at the head continuously and any offset means something different a second later — producing duplicates when items arrive and gaps when they are removed. And materialization is a dial rather than a switch: materialising more buys read latency and pays in write amplification and in how long a ranking change takes to reach anyone.

This section

Designing INSTAGRAM: System Design of News FeedGaurav Sen

What is true here

Fan-out-on-write buys cheap reads with writes proportional to follower count; fan-out-on-read does the reverse. Reads dominate, so write-time is the default.
Follower counts are heavily skewed, so neither pure strategy survives: the hybrid fans out below a threshold and merges large accounts at read time.
Materialised feeds are derived data — keep posts and follows authoritative so a fan-out bug or ranking change is a re-run, not an incident.
Retrieve a bounded candidate set, then rank it; ranking the whole corpus makes feed latency grow with a user's history.
Offset pagination is broken on a head-inserting list; cursors encode a position in the ordering and stay stable as items arrive.

What you will be able to do

Cost a post and a feed read under both fan-out strategies and pick a follower threshold for the hybrid
Explain why fan-out must be asynchronous and what publish latency looks like when it is not
Design a two-stage retrieve-then-rank read path with a bounded candidate set
Build a stable feed cursor, and explain the duplicate-and-gap failure offsets produce

Where the join is paid for

Fan-out-on-write, fan-out-on-read, the celebrity skew that breaks both, and the hybrid threshold.

coreadvanced

A feed is a join between "who I follow" and "what they posted", and you can pay for that join at write time or at read time. Fan-out-on-write pushes each new post into a precomputed list for every follower at the moment it is published, so opening the app is one cheap read of an already-assembled list. Fan-out-on-read stores each post once and assembles the feed when someone asks for it, by fetching the recent posts of everyone they follow and merging. The trade is direct: fan-out-on-write makes reads fast and writes expensive and proportional to follower count, while fan-out-on-read makes writes trivial and reads expensive and proportional to following count. Which is right depends on the ratio between the two, and for most social products reads dominate heavily, which argues for fan-out-on-write. The problem is that write cost is not evenly distributed. A user with fifty followers costs fifty list insertions; a user with fifty million costs fifty million, all triggered by one tap, and that skew — usually called the celebrity problem — is what makes the pure form of either approach unworkable at scale. Real systems use a hybrid: fan out on write for ordinary accounts, do not fan out posts from very large accounts at all, and merge those in at read time. Each user's feed is then one cheap read of their materialised list plus a small merge from the handful of large accounts they follow.

Think of it as

Two ways to run a newsletter. You can address and post an envelope to every subscriber the moment you write something, which makes reading effortless — the letter is already on the doormat — and makes publishing proportional to your subscriber list. Or you can pin the letter to a noticeboard and let each subscriber walk round every noticeboard they care about, which makes publishing free and reading a chore that grows with how many boards someone follows. Neither works for a writer with fifty million subscribers and neither works for a reader who follows two thousand boards, which is why real systems post envelopes for ordinary writers and keep noticeboards for the famous ones.

python

FANOUT_THRESHOLD = 100_000

def publish(post):
    posts.insert(post)                 # durable first
    if follower_count(post.author) < FANOUT_THRESHOLD:
        fanout_queue.put(post.id)      # async, per
                                       # follower
    # large accounts: no fan-out at all

def feed(user_id, limit):
    materialised = feed_list.range(user_id, limit)
    from_large   = merge_recent(
        large_accounts_followed_by(user_id), limit)
    return rank(merge(materialised, from_large))[:limit]

What we're doing: Cost the same two posts under both strategies, then under the hybrid.

fanout-cost.txttext

Post A: an ordinary user, 180 followers
Post B: a celebrity, 40,000,000 followers

Fan-out-on-write
  Post A  ->        180 feed insertions
  Post B  -> 40,000,000 feed insertions from one
             tap. At 50k inserts/s that is 800
             seconds of write amplification, and
             the last follower sees the post 13
             minutes late.

Fan-out-on-read
  Post A  ->          1 insertion
  Post B  ->          1 insertion
  Feed read for a user following 800 accounts:
             800 timeline reads + a merge, every
             time they pull to refresh.

Hybrid (threshold 100,000 followers)
  Post A  ->        180 insertions (below cut-off)
  Post B  ->          1 insertion (above cut-off)
  Feed read: 1 range read of the materialised
             list, plus a merge across the ~5
             large accounts this user follows.

6: This is the number that kills pure fan-out-on-write. The cost is not the total volume — it is that one user action produces it, so the write burst has no natural smoothing and the queue behind it becomes the feature's latency.
15: Pure fan-out-on-read fails from the other direction, and it fails on every read rather than on rare writes. Eight hundred reads per refresh is the kind of cost that looks acceptable in a prototype and does not survive a real user base.
23: The hybrid bounds both sides: write cost can never exceed the threshold, and read cost is bounded by how many large accounts one person follows, which is small in practice because there are not many such accounts.

Why this works: Costing both strategies against the two extreme cases shows that neither pure form is a design so much as one half of one. The threshold is the actual design decision, and it is tunable: raise it and reads get cheaper while celebrity writes get more expensive, lower it and the reverse.

Fanning out synchronously inside the publish request

Wrong

python

def publish(post):
    posts.insert(post)
    for follower in followers(post.author):   # blocks
        feed_list.insert(follower, post.id)   # the
    return 201                                # request

Better

python

def publish(post):
    posts.insert(post)          # durable
    fanout_queue.put(post.id)   # returns immediately
    return 201                  # workers fan out
                                # behind the response

What you see: Publish latency scales with follower count, so posting is instant for new users and takes tens of seconds for popular ones. Under load the publish endpoint's connection pool is exhausted by long-running fan-out loops, and posting fails for everyone.

Why: Fan-out is bounded by audience size, which is a property of the author rather than of the request, so putting it on the request path makes latency depend on something the user cannot influence and the system cannot cap. Making the post durable and fanning out asynchronously gives a constant-time publish and turns propagation delay into queue lag, which is measurable and shed-able.

Where the join is paid for

Fan-out-on-write

+One post → one insertion per follower, asynchronously
+Opening the feed is a single ordered range read
+Feed lists are derived data and must be rebuildable
+Breaks on skew: one celebrity post is millions of writes

Fan-out-on-read

−One post → one insertion, regardless of audience
−Opening the feed reads every followed account and merges
−No duplicated storage, no propagation lag
−Breaks on breadth: a user following thousands is a slow read

The two strategies, side by side

The two strategies, side by side
Property	Fan-out-on-write	Fan-out-on-read
Cost of a post	O(followers) insertions	O(1) insertion
Cost of opening the feed	O(1) list read	O(following) reads plus a merge
Storage	One row per post per follower	One row per post
Freshness	Eventual — the fan-out job lags publication	Immediate — nothing to propagate
Worst case	A celebrity posts	A user follows thousands of accounts
Changing the ranking rule	Requires rebuilding materialised feeds	Takes effect on the next read

Why the hybrid is the usual answer

Why the hybrid is the usual answer
Account type	On publish	On feed read
Ordinary account (below the threshold)	Fan out to every follower's list	Already present — no extra work
Large account (above the threshold)	Write the post once, fan out to nobody	Merged in from that account's own timeline
Effect	Write cost bounded by the threshold	Read cost bounded by how many large accounts one user follows

Remember: A feed is a join between follows and posts, paid for either at write time (fan-out-on-write: cheap reads, writes proportional to follower count) or at read time (fan-out-on-read: cheap writes, reads proportional to following count). Reads dominate, so fan-out-on-write is the default — but follower counts are skewed, and one celebrity post is millions of writes from one tap. The working answer is a hybrid: fan out below a follower threshold, merge large accounts in at read time, run fan-out asynchronously, and keep posts and follows authoritative so materialised feeds stay rebuildable.

The read path

Caching, retrieve-then-rank, cursor pagination, and materialization as a tunable dial.

coreadvanced

Choosing a fan-out strategy leaves four read-path decisions, and each one is tuned by the same two inputs: how skewed the follower distribution is, and how the read and write rates compare. Caching a feed is unusually effective because a user re-reads their own feed far more often than it changes, so a short-lived per-user cache absorbs most refresh traffic — and the entries most worth caching are the large accounts' timelines, which are read by everyone. Ranking is where a feed stops being a list and becomes a product: chronological order is cheap and needs no extra state, while a scored order needs features computed per candidate post, which is why ranking usually runs over a small candidate set retrieved first rather than over everything. Pagination has to be cursor-based, not offset-based, because a feed has items inserted at the head continuously: an offset of 20 means something different one second later, so `page=2` shows items the reader already saw or skips items they never did. And materialization is a dial rather than a switch — you can materialise the full ranked feed, materialise only the candidate list and rank on read, or materialise nothing; each step toward more materialization buys read latency and pays in write amplification and in how long a ranking change takes to take effect.

Think of it as

Think of the read path as four dials, all reading from the same two gauges: skew and read-to-write ratio. Turn caching up when the same feed is read repeatedly between changes. Turn materialization up when reads outnumber writes and the follower distribution is flat enough that write amplification stays bounded. Turn ranking complexity up only over a candidate set small enough to afford it. And pagination is not a dial at all — it is the one setting a live, head-inserting list forces on you, because offsets stop meaning anything the moment new items arrive.

sql

-- cursor pagination: seek, do not skip
SELECT post_id, created_at
  FROM feed_list
 WHERE user_id = $1
   AND (created_at, post_id) < ($2, $3)   -- cursor
 ORDER BY created_at DESC, post_id DESC
 LIMIT 20;

-- the cursor is the last row's (created_at, post_id),
-- so new items at the head cannot shift it

What we're doing: Show the duplicate-and-gap failure offset pagination produces on a live feed, and the cursor version that does not.

pagination-drift.txttext

Feed at t0 (newest first):
  P30 P29 P28 ... P11 P10 P09 ... P01

Client requests page 1: offset=0 limit=20
  -> P30 ... P11

Between the two requests, 3 new posts arrive:
  P33 P32 P31 P30 P29 ... P01

Client requests page 2: offset=20 limit=20
  -> P13 P12 P11 P10 ...
     P13, P12 and P11 were already on page 1.
     The reader sees three duplicates.

Now with a cursor. Page 1 returned
  cursor = (created_at of P11, id of P11)

Client requests page 2: after=<cursor>
  -> P10 P09 P08 ...
     Correct, regardless of how many posts
     arrived at the head in between.

11: The duplicates are not a rendering bug — the query did exactly what it was asked. Offset 20 meant P11 before the new posts arrived and means P13 afterwards, because every offset is measured from a head that moved.
18: The cursor encodes a position in the ordering rather than a count from the start, so items added at the head do not move it. This is also why the cursor must include a tiebreaker (the post id) — two posts sharing a timestamp would otherwise make the position ambiguous.

Why this works: A social feed is the clearest case for cursor pagination because insertions at the head are its normal operation, not an edge case. The same reasoning applies to any continuously-appended list — event logs, notifications, chat history — and the failure is always the same shape: duplicates when items are added, gaps when they are removed.

Ranking the whole corpus on the read path

Wrong

python

def feed(user_id):
    posts = all_posts_from(following(user_id))  # every
    scored = [(score(p, user_id), p)            # post,
              for p in posts]                   # every
    return sorted(scored, reverse=True)[:20]    # read

Better

python

def feed(user_id, cursor):
    candidates = retrieve(user_id, cursor,
                          limit=300)   # bounded
    scored = [(score(p, user_id), p)   # 300 scores,
              for p in candidates]     # not 300,000
    return sorted(scored, reverse=True)[:20]

What you see: Feed latency grows with how long a user has been on the platform and how many accounts they follow, so the most engaged users get the slowest experience. Adding a feature to the ranking model makes every feed request slower in proportion.

Why: Scoring cost is per candidate, so an unbounded candidate set makes read latency depend on corpus size rather than page size. Retrieval and ranking are two stages for exactly this reason: retrieval cheaply narrows to a few hundred plausible items using an index, and ranking spends real computation only on those.

A feed read, from request to response

Cache lookup

Per-user page keyed by (user, cursor). A refresh within the TTL never touches the store.

Retrieve candidates

Read the materialised list from the cursor, plus recent posts from the large accounts this user follows.

Merge and deduplicate

Combine both sources into one ordered candidate set, bounded to a few hundred items.

Rank

Score only the candidates — never the whole corpus. Chronological order skips this step entirely.

Cut and emit a cursor

Return the page plus a cursor built from the last item, so the next request seeks instead of skipping.

Four read-path decisions and the signal that sets each

Four read-path decisions and the signal that sets each
Decision	Set by	Rule of thumb
Caching	How often a feed is read between changes	Cache per-user feed pages briefly; cache large accounts' timelines aggressively
Ranking	Whether ordering is chronological or scored	Rank a bounded candidate set, never the whole corpus, on the read path
Pagination	Whether the list has items inserted at the head	Always cursor-based for a live feed; offsets are only safe on a frozen list
Materialization	Read-to-write ratio and follower skew	Materialise more as reads dominate, less as skew and ranking churn rise

Cursor versus offset on a list that grows at the head

Cursor versus offset on a list that grows at the head
Scenario	Offset pagination	Cursor pagination
Page 2 request	`?offset=20&limit=20`	`?after=<cursor from last item>&limit=20`
If 5 items were added since page 1	Items 16–20 of page 1 reappear on page 2	Continues exactly where page 1 ended
If 5 items were deleted since page 1	Five items are skipped and never seen	Continues correctly
Cost at deep pages	The store must skip N rows	A seek to the cursor position
Can jump to an arbitrary page?	Yes	No — only forward and backward from a position

Remember: Cache per-user pages briefly and large accounts' timelines aggressively, since both are read far more often than they change. Retrieve a bounded candidate set and rank only that, never the whole corpus. Use cursor pagination — a feed inserts at the head, so every offset means something different one second later. And treat materialization as a dial set by read-to-write ratio and skew, remembering that the more you materialise, the longer a ranking change takes to reach anyone.