25 — A news feed

A news feed shows each user recent posts from the accounts they follow. Its defining problem is a multiplier: one post has to reach every follower, and follower counts vary by many orders of magnitude. The design is mostly about where that work happens. It follows the process from chapter 23.

Requirements

Functional.

1. Publish a post (text, with media stored elsewhere).
2. Follow and unfollow accounts.
3. Read the home feed: posts from followed accounts, newest first or ranked, in pages.
4. A user’s own new post appears in their own feed immediately.

Non-functional.

Out of scope: comments, likes, notifications (chapter 27), search, and the media pipeline.

Estimates

All inputs are assumptions (chapter 4).

DAY = 86_400
dau, reads_per_user, posters, followers_avg, peak = 100e6, 10, 0.10, 200, 3   # assumptions
posts = dau * posters
reads = dau * reads_per_user
print(f"posts/day {posts:,.0f}  avg {posts/DAY:,.0f}/s  peak {posts/DAY*peak:,.0f}/s")
print(f"feed reads/day {reads:,.0f}  avg {reads/DAY:,.0f}/s  peak {reads/DAY*peak:,.0f}/s")
print(f"fan-out inserts/day {posts*followers_avg:,.0f}  avg {posts*followers_avg/DAY:,.0f}/s")
entries, bytes_per_entry = 500, 50                                            # assumptions
print(f"feed cache: {dau*entries*bytes_per_entry/1e12:,.1f} TB")
post_bytes = 1_000                                                            # assumption
print(f"post storage/year: {posts*365*post_bytes/1e12:,.1f} TB")

posts/day 10,000,000  avg 116/s  peak 347/s
feed reads/day 1,000,000,000  avg 11,574/s  peak 34,722/s
fan-out inserts/day 2,000,000,000  avg 23,148/s
feed cache: 2.5 TB
post storage/year: 3.6 TB

The post writes themselves are small: under 350 a second at peak. The multiplier is what matters. With 200 followers per post on average, those posts become 23,000 feed inserts a second on average. Reads outnumber posts 100 to 1, so the design should make reads cheap. And a precomputed feed for every daily user is terabytes of cache, which means a partitioned Redis cluster rather than one instance (chapter 11). The 50 bytes per entry is an assumption and should be checked with Redis’s MEMORY USAGE on a real feed.

API

POST   /posts                   {"text": "...", "media_ids": [...]}
       Idempotency-Key: <uuid>  -> 201 {"post_id": 734213...}

PUT    /follows/{account_id}    -> 204
DELETE /follows/{account_id}    -> 204

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

The cursor is opaque to the client. It encodes the position of the last item returned, not a page number. The pagination section below shows why.

Data model

PostgreSQL holds the source of truth: accounts, the follow graph and posts.

CREATE TABLE follows (
    follower_id  bigint      NOT NULL,
    followee_id  bigint      NOT NULL,
    created_at   timestamptz NOT NULL DEFAULT now(),
    PRIMARY KEY (follower_id, followee_id)
);
CREATE INDEX follows_by_followee ON follows (followee_id, follower_id);

CREATE TABLE posts (
    id          bigint      PRIMARY KEY,     -- time-ordered, from an ID generator
    author_id   bigint      NOT NULL,
    created_at  timestamptz NOT NULL,
    body        text        NOT NULL,
    deleted_at  timestamptz
);
CREATE INDEX posts_by_author ON posts (author_id, id DESC);

Each index serves one access pattern:

Post IDs are time-ordered, so sorting by ID sorts by time, and the ID can be a feed’s sort key. They’re kept to 53 bits: 41 bits of milliseconds since a chosen epoch (about 69.7 years of range), 6 bits of generator ID and 6 bits of sequence. The reason for 53 bits is Redis. Sorted-set scores are double-precision floats, and the Redis ZADD documentation notes that they represent integers exactly only up to $2^{53}$. A 64-bit ID used as a score would lose its low bits, and nearby posts would compare equal. Chapter 11 covers ID generation.

Derived data lives in Redis:

All of it can be rebuilt from PostgreSQL, so losing it costs latency, not data.

Topology

            +-------------+     +------------+
 publish -> | post service| --> | PostgreSQL |  (posts, follows)
            +-------------+     +------------+
                   | outbox / CDC
                   v
             [log stream] --> [fan-out workers] --> Redis feed:{follower}
                                     |  (look up followers)
                                     v
                                 PostgreSQL

            +-------------+     +---------------------------------------+
 read  ---> | feed service| --> | Redis: feed:{user}, timeline:{celeb}, |
            +-------------+     |        post:{id}                      |
                                +---------------------------------------+

A publish writes the post to PostgreSQL and records an event in the same transaction, using a transactional outbox or change data capture (chapter 15). That avoids the dual write in which the post is saved but its fan-out event is lost. The event goes to a log stream partitioned by author (chapter 8), and fan-out workers consume it.

When to do the work

Pure pull makes every feed read query hundreds of timelines, at the 34,700 reads a second estimated above. Pure push makes reads cheap, but one account with a million followers turns one post into a million writes. The hybrid pushes for ordinary authors and pulls for large ones. The question is where to put the threshold, and that depends on the shape of the follower distribution.

Simulating fan-out cost

The simulation below builds a network of one million accounts. Follower counts are drawn from a Pareto (power-law) distribution, which is an assumption standing in for a real follower graph: most accounts have a few dozen followers, and a few have hundreds of thousands. Every account is assumed to post once a day. For each candidate threshold it reports:

• Push writes a day: feed inserts for posts by accounts below the threshold.
• Largest push: the biggest single fan-out job that remains.
• Pulls per read: how many above-threshold accounts the average reader follows, which is how many timelines a feed read has to merge.

import random

USERS = 1_000_000
rng = random.Random(3)
# Assumption: follower counts follow a Pareto tail, alpha = 1.1, minimum 20,
# capped at the number of users.
followers = sorted((min(USERS - 1, int(20 * rng.paretovariate(1.1))) for _ in range(USERS)),
                   reverse=True)
edges = sum(followers)

def pct(p):
    return followers[int(len(followers) * (1 - p))]

print(f"follow edges: {edges:,}  mean followers: {edges/USERS:,.0f}  median: {pct(0.5):,}")
print(f"p99: {pct(0.99):,}  p99.99: {pct(0.9999):,}  max: {followers[0]:,}")
top = followers[: USERS // 1000]
print(f"top 0.1% of accounts hold {sum(top)/edges:.0%} of follow edges")

print("threshold   accounts pulled  push writes/day  vs push-all  largest push  pulls per read")
for T in (None, 1_000_000, 100_000, 10_000, 5_000, 1_000):
    pushed = [f for f in followers if T is None or f < T]
    pulled = [f for f in followers if T is not None and f >= T]
    push = sum(pushed)
    label = "push all" if T is None else f"{T:,}"
    print(f"{label:>9}  {len(pulled):>16,}  {push:>15,}  {push/edges:>10.1%}"
          f"  {max(pushed):>12,}  {sum(pulled)/USERS:>14.2f}")

follow edges: 155,331,438  mean followers: 155  median: 37
p99: 1,318  p99.99: 82,188  max: 999,999
top 0.1% of accounts hold 34% of follow edges
threshold   accounts pulled  push writes/day  vs push-all  largest push  pulls per read
 push all                 0      155,331,438      100.0%       999,999            0.00
1,000,000                 0      155,331,438      100.0%       999,999            0.00
  100,000                84      124,896,386       80.4%        99,022           30.44
   10,000             1,045      101,424,516       65.3%         9,998           53.91
    5,000             2,305       92,741,996       59.7%         4,998           62.59
    1,000            13,512       70,795,128       45.6%           999           84.54

The same program with a lighter tail (alpha 1.3) gives a different picture:

follow edges: 83,281,981  mean followers: 83  median: 34
p99: 692  p99.99: 22,847  max: 464,966
top 0.1% of accounts hold 18% of follow edges
threshold   accounts pulled  push writes/day  vs push-all  largest push  pulls per read
 push all                 0       83,281,981      100.0%       464,966            0.00
1,000,000                 0       83,281,981      100.0%       464,966            0.00
  100,000                22       78,950,256       94.8%        97,007            4.33
   10,000             299       72,662,907       87.2%         9,998           10.62
    5,000             724       69,731,036       83.7%         4,999           13.55
    1,000           6,104       59,466,525       71.4%           999           23.82

Reading the results

The hybrid saves less total work than expected. Pulling the 84 largest accounts in the heavier-tailed network cut daily push writes by only 20%. In the lighter-tailed one, pulling 22 accounts saved 5%. Total write volume isn’t the main reason for the hybrid.

The real gain is the size of the largest job. Under pure push, one post from the largest account is a million inserts. If the fan-out workers together manage 100,000 inserts a second (an assumption, to be measured), that post takes 10 seconds to reach everyone. Worse, the log stream is partitioned by author, so other posts queued behind it on the same partition wait too. A threshold of 10,000 caps any single job at about 0.1 seconds of worker time. Fan-out latency becomes predictable.

The cost moves to reads. Every account above the threshold is a timeline that every follower’s feed read must fetch and merge. With the heavier tail, a threshold of 10,000 means 54 merges per read on average. With the lighter tail it means 11. Lowering the threshold quickly makes reads expensive.

The pulled timelines are hot keys. Those 54 timeline reads per feed read land on about a thousand keys, the same ones for everyone. That is a hot-key load, not a database load. Celebrity timelines change only when the celebrity posts, so they cache very well: a copy in each feed service’s own memory, refreshed every second or two, absorbs most of it (chapter 7).

So the threshold is chosen from two limits: the largest fan-out job that meets the freshness target, and the number of merges a read can afford within its latency budget. Both depend on the real distribution, which should be measured from the follow graph, not assumed. In practice the threshold is a setting that can change, and moving an account across it needs a backfill or a cleanup of its pushed entries.

Two refinements reduce push cost further:

• Skip inactive followers. Followers who haven’t opened the app for weeks don’t need a pushed feed. Their feed is rebuilt from the follow graph and timelines when they return, as a cache miss.
• Batch inserts. A worker that pipelines many ZADD commands to the same Redis node pays one round trip for many inserts.

The read path

A feed read for user U:

1. Read up to N post IDs from feed:{U} older than the cursor.
2. Read the same range from timeline:{A} for each followed account A above the threshold, from the local cache.
3. Read U’s own recent posts, so that a post U just published appears even if fan-out hasn’t reached U’s feed yet.
4. Merge the lists by post ID, newest first, and drop duplicates.
5. Filter out deleted posts and blocked or muted accounts.
6. Hydrate the post IDs with a multi-get on post:{id}, falling back to PostgreSQL on a miss.

Step 3 is how the requirement “own post appears immediately” is met without making publishing wait for fan-out. It’s a read-your-writes guarantee for one user, done at read time (chapter 12).

The program below implements this read path with cursors, using in-memory lists in place of Redis, and checks it while new posts keep arriving between pages:

import heapq, itertools, random

THRESHOLD = 3          # accounts with at least this many followers are pulled, not pushed
FEED_LEN = 500         # pushed feeds are trimmed to this many entries

followers = {}         # author -> set of followers
following = {}         # user -> set of authors
pushed = {}            # user -> list of post ids, newest first   (Redis sorted set)
timeline = {}          # author -> list of post ids, newest first (author's own posts)
next_id = itertools.count(1)   # stands in for a time-ordered ID generator

def follow(user, author):
    followers.setdefault(author, set()).add(user)
    following.setdefault(user, set()).add(author)

def is_celebrity(author):
    return len(followers.get(author, ())) >= THRESHOLD

def post(author):
    pid = next(next_id)
    timeline.setdefault(author, []).insert(0, pid)
    if not is_celebrity(author):
        for f in followers.get(author, ()):               # fan-out on write
            feed = pushed.setdefault(f, [])
            feed.insert(0, pid)
            del feed[FEED_LEN:]
    return pid

def read_feed(user, cursor=None, limit=10):
    """Up to `limit` post ids older than `cursor`, newest first, and the next cursor."""
    sources = [pushed.get(user, []), timeline.get(user, [])]           # own posts at read time
    sources += [timeline[a] for a in following.get(user, ()) if is_celebrity(a) and a in timeline]
    older = ((pid for pid in s if cursor is None or pid < cursor) for s in sources)
    merged = heapq.merge(*older, reverse=True)
    page = []
    for pid in merged:
        if not page or pid != page[-1]:                                # drop duplicates
            page.append(pid)
        if len(page) == limit:
            break
    return page, (page[-1] if page else None)

rng = random.Random(1)
users = [f"u{i}" for i in range(8)] + ["star"]
for u in users[:8]:
    follow(u, "star")
follow("u0", "u1"); follow("u0", "u2"); follow("u3", "u0")

expected = []
for _ in range(60):
    author = rng.choice(["star", "u1", "u2", "u0", "u5"])
    pid = post(author)
    if author in ("star", "u1", "u2", "u0"):
        expected.append(pid)              # posts u0 should see (its follows and itself)

seen, cursor = [], None
while True:
    page, cursor = read_feed("u0", cursor, limit=7)
    if not page:
        break
    seen += page
    post("star"); post("u1")              # new posts between pages
print(f"star is pulled: {is_celebrity('star')}, u1 is pushed: {not is_celebrity('u1')}")
print(f"posts u0 should see before paging began: {len(expected)}")
print(f"posts returned across pages: {len(seen)}, duplicates: {len(seen) - len(set(seen))}")
print(f"missing: {sorted(set(expected) - set(seen))}")
print(f"strictly newest first: {all(a > b for a, b in zip(seen, seen[1:]))}")

star is pulled: True, u1 is pushed: True
posts u0 should see before paging began: 49
posts returned across pages: 49, duplicates: 0
missing: []
strictly newest first: True

Every post appeared once, in order, across pages, while new posts arrived from both a pushed and a pulled author. New posts don’t appear in later pages, since they are newer than the cursor. The client fetches them separately with a “newer than the first item” request when the user pulls to refresh.

Pagination with cursors

Offset pagination (LIMIT 20 OFFSET 40) breaks on a feed, because the list shifts while it’s being read. A small program shows both failures:

feed = [(1000 - i, 5000 - i) for i in range(50)]        # (timestamp, post_id), 50 posts

def newest_first():
    return sorted(feed, reverse=True)

def page_by_offset(offset, limit=10):
    return newest_first()[offset: offset + limit]

def page_by_cursor(cursor, limit=10):
    items = newest_first()
    if cursor is not None:
        items = [p for p in items if p < cursor]          # like SQL (ts, id) < (...)
    return items[:limit]

p1_offset, p1_cursor = page_by_offset(0), page_by_cursor(None)
feed += [(2000 + i, 9000 + i) for i in range(3)]        # three new posts arrive
p2_offset, p2_cursor = page_by_offset(10), page_by_cursor(p1_cursor[-1])
ids = lambda page: [pid for _, pid in page]
print("offset: duplicates on page 2:", sorted(set(ids(p1_offset)) & set(ids(p2_offset))))
print("cursor: duplicates on page 2:", sorted(set(ids(p1_cursor)) & set(ids(p2_cursor))))

feed = [(1000 - i, 5000 - i) for i in range(50)]
p1_offset, p1_cursor = page_by_offset(0), page_by_cursor(None)
feed.remove(p1_offset[3])                               # a post on page 1 is deleted
p2_offset, p2_cursor = page_by_offset(10), page_by_cursor(p1_cursor[-1])
everything = set(ids(newest_first()[:19]))
print("offset: posts skipped after a delete:",
      sorted(everything - set(ids(p1_offset)) - set(ids(p2_offset))))
print("cursor: posts skipped after a delete:",
      sorted(everything - set(ids(p1_cursor)) - set(ids(p2_cursor))))

offset: duplicates on page 2: [4991, 4992, 4993]
cursor: duplicates on page 2: []
offset: posts skipped after a delete: [4990]
cursor: posts skipped after a delete: []

Three new posts pushed the last three items of page 1 onto page 2, so the reader saw them twice. A deletion did the opposite, and one post was never shown. A cursor names a position in the data, not a count of rows, so neither change affects it.

In PostgreSQL the same idea is keyset pagination, using a row comparison, which compares element by element from the left as described in the PostgreSQL row comparison documentation:

SELECT id, author_id, created_at, body
FROM posts
WHERE author_id = $1
  AND (created_at, id) < ($2, $3)        -- the cursor: last row of the previous page
ORDER BY created_at DESC, id DESC
LIMIT 20;

With an index on (author_id, created_at DESC, id DESC), each page is an index range scan, and its cost doesn’t grow with the page number, unlike OFFSET, which reads and discards every earlier row. The id in the cursor breaks ties between posts with the same timestamp. Since post IDs here are time-ordered and unique, id alone also works, which is what posts_by_author assumes.

In Redis, ZRANGE with BYSCORE, REV and LIMIT gives the same behavior. A ( before a score makes the bound exclusive:

ZRANGE feed:42 (734213990012 -inf BYSCORE REV LIMIT 0 20

This returns up to 20 post IDs with scores strictly below the cursor, newest first. Since scores are unique post IDs, the exclusive bound never skips a tie.

Ranking

A chronological feed is simple to build and to reason about. A ranked feed orders candidates by predicted interest, and changes the design in three ways.

Candidate generation and scoring split apart. The fan-out machinery above becomes candidate generation: it produces a few hundred recent post IDs. A ranking step then scores each candidate, using features such as the reader’s past interactions with the author, the post’s engagement so far, and its age. A common shape for the score is engagement weighted by affinity and divided by a growing function of age, so that recent posts win among equals. The weights come from offline evaluation and experiments, not from a design document.

Ranking costs latency. Scoring a few hundred candidates per read needs features fetched from a feature store and a model evaluated per candidate. That runs inside the read latency budget, so the candidate set is capped and features are precomputed where possible.

Cursors need a snapshot. A ranked order isn’t stable: scores change between page requests, so “items after this one” isn’t well defined. The usual fix is to rank once per session, store the ranked list of IDs under a session key with a short time-to-live, and page through that stored list. The cursor is then a position in the snapshot. New posts appear on the next refresh, which builds a new snapshot.

Failure modes

The deletion and unfollow rows share a pattern: fan-out on write copies data, and copies go stale. The read path filters against the source of truth, and cleanup of the copies happens later. Correctness comes from the filter, and the cleanup only saves space.

The takeaway

A news feed is a multiplier problem: one post becomes as many writes as its author has followers, and follower counts are heavy-tailed. Pushing to followers makes reads cheap, pulling makes writes cheap, and the hybrid uses a threshold. The simulation showed that the hybrid saves less total write volume than expected. Its value is capping the largest fan-out job, at the cost of merges on every read, so the threshold comes from the measured distribution and two latency budgets. Feeds should page with cursors, never offsets, and a ranked feed pages through a per-session snapshot.