System Design Case Study: News Feed and Timeline

Version note: The code in this post was built and run with C# 14 and .NET 10; the feed cache example ran against Redis 7.4 with StackExchange.Redis 3.4, and the fan-out simulation uses a fixed seed.

Guess First

Bookstore is adding a "Reader Community": readers follow authors and each other, share short reviews and quotes from books, and the home page shows a feed made of the posts of the accounts they follow. To give the fastest possible reads, the team decides to add every post, at the moment it's written, to the ready-made feeds of all followers. The first month goes fine. Then a famous author with a million followers joins the platform and announces a new book.

Two questions. How much write work does that single announcement create, and when does the last follower see it? And if new posts arrive while a reader scrolls the feed (?page=2), what does she see on the second page?

Requirements and Capacity Estimation

Functional requirements: a user can publish a post with text and an optional image; she sees the posts of the accounts she follows in a feed, newest first; the feed loads page by page (infinite scroll). Out of scope: like and comment counters, notifications, search. Non-functional requirements: the feed must open fast (p99, the time 99% of requests stay under, below 200 ms); it's enough for a new post to land in followers' feeds within a few seconds, it doesn't need to be instant; the system must stay up even with famous accounts around. That last sentence says we choose availability and latency over consistency: the feed can live with eventual consistency.

Assumptions: 10 million DAU (Daily Active Users), 2 posts and 10 feed reads per person per day, 125 followers on average, peak at 3 times the average, a 500 KB image in 10% of posts.

const double dau = 10_000_000, postsPerUser = 2, readsPerUser = 10, avgFollowers = 125, peak = 3;
const double postBytes = 1_000, mediaShare = 0.10, mediaBytes = 500_000, feedEntries = 800, entryBytes = 16;
double postsPerSec = dau * postsPerUser / 86_400, readsPerSec = dau * readsPerUser / 86_400;

posts/s 231 (peak 694), feed reads/s 1,157 (peak 3,472)
fan-out inserts/s if every post is pushed: 28,935
post text/day 20 GB, media/day 1.0 TB
feed cache: 800 ids x 16 B x 10 M users = 128 GB before Redis overhead

The most important line in the table is the second: 231 posts per second, if each one is distributed to followers as it's written, turn into 29 thousand feed writes per second. The read side (1,157 per second, 3,500 at peak) isn't hard on its own; the hard part is how much more expensive we're willing to make writes in order to make reads cheap. Images, at 1 TB a day, are 50 times the text; their place isn't the database. The feed cache, if we keep only 800 post IDs per user, is 128 GB raw; with Redis's data structure overhead it's several times that, meaning a cluster of a few nodes.

API and Data Model

The API (Application Programming Interface) consists of two endpoints: POST /api/posts (the text and, if one was uploaded, the image's key in object storage) and GET /api/feed?cursor=...&limit=20. The feed response returns the posts and an opaque nextCursor for the next page; there's no page number, and we'll see why below.

Persistent data comes in three parts. The Posts table holds the post itself, and the post ID is time ordered (like Snowflake in the series' "Generating Unique IDs: Auto-Increment, UUIDv4, UUIDv7 and Snowflake" post), so sorting by ID is sorting by time. The Follows table is the follow relationship; it's queried in both directions ("who follows Grace?" for fan-out, "whom does Ada follow?" for reads), so it needs two indexes or two separate tables. The feed cache, by contrast, isn't persistent: one Redis sorted set per user, feed:{user}, holding only post IDs. The post's text isn't copied into feeds; a feed is a list of IDs, and a post is stored once. That split means an edited or deleted post changes in every feed from a single place.

High-Level Design

On the write path, the Post API writes the post to the database, drops the image into object storage and puts a fan-out job on a queue; at that point the user already has her response. Fan-out workers read the author's followers and add the post ID to each follower's feed cache. On the read path, the Feed API takes IDs from the user's feed cache, adds the latest posts of the high-follower accounts she follows (merge), turns IDs into actual posts from the post cache (hydrate), sorts them and returns them with a cursor. Why this two-part structure is needed is the subject of the deep dives.

Deep Dive: Fan-Out on Write or on Read?

There are two extreme models. Fan-out on write (push): a post is added to all followers' feeds at the moment it's written; reading is as cheap as a single cache read, writing is as expensive as the follower count. Fan-out on read (pull): the post is written only to the author's list; the reader collects and merges the latest posts of everyone she follows. Writes are cheap, reads are as expensive as the number of followed accounts.

Averages don't tell you how expensive each one is, because followers aren't evenly distributed: most accounts have a few dozen followers while a handful have millions. I built a model of a million users with a power-law (Pareto) distribution and compared the two models with 2 posts and 10 reads a day:

// Follower counts follow a power law: most users have a few dozen, a handful have millions.
public static FanOutReport Run(int users, double postsPerUserPerDay, double readsPerUserPerDay, long celebrityThreshold)
{
    Random random = new(7);
    long[] followers = new long[users];
    for (int i = 0; i < users; i++)
        followers[i] = Math.Min(users - 1, (long)(20 * Math.Pow(1 - random.NextDouble(), -1 / 1.15)));

    double totalEdges = followers.Sum(f => (double)f);
    double celebrityEdges = followers.Where(f => f >= celebrityThreshold).Sum(f => (double)f);
    double avgFollowing = totalEdges / users;                 // every edge is one follower and one following
    double avgCelebritiesFollowed = celebrityEdges / users;

    double posts = users * postsPerUserPerDay, reads = users * readsPerUserPerDay;
    return new FanOutReport(
        AvgFollowers: avgFollowing,
        MaxFollowers: followers.Max(),
        Celebrities: followers.Count(f => f >= celebrityThreshold),
        WritesPerDay: postsPerUserPerDay * totalEdges,                         // push: one feed insert per follower
        BiggestFanOut: followers.Max(),
        PullReadCostPerDay: reads * avgFollowing,                             // pull: every read scans every followee
        HybridWritesPerDay: postsPerUserPerDay * (totalEdges - celebrityEdges),
        HybridReadCostPerDay: reads * (1 + avgCelebritiesFollowed));          // cached feed + celebrity merge
}

avg followers 125, max 999,999
push  : 250 M feed inserts/day, one post can fan out to 999,999
pull  : 1,249 M followee lookups/day for 10 M feed reads

Push produces 250 million feed writes a day, but one cache read per feed read is enough. Pull eliminates the writes and loads the cost onto reads: 1.25 billion "latest posts of a followed account" queries for 10 million reads, 125 per read on average. Since reads are more frequent than writes and reads are the side the user waits on, most systems choose push by default. But the number on the second line of the table shows why push alone isn't enough: a single post can turn into nearly a million writes.

Deep Dive: The Celebrity Problem and the Hybrid Model

The answer to the first Guess First question is here. The million-follower author's announcement means a million feed writes; if workers process those at a few thousand per second, the last follower sees the announcement minutes later, and meanwhile ordinary users' posts waiting behind it in the queue are delayed too. Twitter's run-in with this problem is well documented: according to High Scalability's summary of Raffi Krikorian's 2012 "Timelines at Scale" talk, home timelines were kept in Redis with at most 800 entries per user and the fan-out target was under 5 seconds, but a tweet from an account with 31 million followers could take up to 5 minutes to reach everyone. As the fix, it describes moving to not fanning out tweets from high-follower accounts and merging them into the timeline at read time instead.

That's the hybrid model: regular accounts push, accounts over a threshold pull. The threshold is a tuning knob; the simulation shows where to put it:

hybrid >=  10,000: 795 pull accounts, 184 M inserts/day + 337 M lookups/day
hybrid >= 100,000:  54 pull accounts, 220 M inserts/day + 158 M lookups/day

With the threshold at 10 thousand followers, 795 accounts switch to pull and writes drop from 250 million to 184 million, but since the average user follows about 33 "celebrities", every read becomes a merge of about 34 parts. Raising the threshold to 100 thousand leaves only 54 accounts and halves the read cost; writes rise to 220 million. A high threshold is enough to cut off the most expensive fan-outs (the million-follower accounts); lowering it reduces writes a little and makes reads much more expensive. Making the merge on the pull side cheap is also a design job: each celebrity account's latest posts sit in their own small cached list, and the Feed API fetches them with a single batched (multi-get) call.

Two more details. Updating feeds on every post for users who haven't logged in for a long time is wasted work; fan-out can go only to active users, and a user returning after a long absence gets her feed rebuilt with pull on first login. And fan-out runs at-least-once: as we discussed in the series' "Asynchronous Processing: Queues, Workers, Fan-Out and Backpressure" post, the same job can be processed twice. Adding the same post ID to a sorted set twice leaves a single entry, so this operation is naturally idempotent.

Deep Dive: The Feed Cache and Cursor Pagination

A Redis sorted set is a good fit for the feed cache: the member is the post ID, and the score is the post ID too (since it's time ordered). Insert with ZADD, keep the newest 800 with ZREMRANGEBYRANK, read a page with a range query. I tried the second Guess First question on this structure: Ada gets the first page, two new posts arrive, then she requests the second page. Once with an offset, once with a cursor:

long[] page1 = await PageByOffset(db, feed, offset: 0, size: 10);
await db.SortedSetAddAsync(feed, 1031, 1031);                      // a new post arrives while Ada scrolls
await db.SortedSetAddAsync(feed, 1032, 1032);
long[] page2Offset = await PageByOffset(db, feed, offset: 10, size: 10);
long[] page2Cursor = await PageByCursor(db, feed, before: page1[^1], size: 10);

static async Task<long[]> PageByOffset(IDatabase db, RedisKey feed, int offset, int size) =>
    [.. (await db.SortedSetRangeByRankAsync(feed, offset, offset + size - 1, Order.Descending)).Select(v => (long)v)];

// Cursor = the last post id the client saw; exclusive upper bound, newest first
static async Task<long[]> PageByCursor(IDatabase db, RedisKey feed, long before, int size) =>
    [.. (await db.SortedSetRangeByScoreAsync(feed, double.NegativeInfinity, before, Exclude.Stop, Order.Descending, 0, size))
        .Select(v => (long)v)];

page 1         : 1030,1029,1028,1027,1026,1025,1024,1023,1022,1021
page 2 (offset): 1022,1021,1020,1019,1018,1017,1016,1015,1014,1013  duplicates: 1022,1021
page 2 (cursor): 1020,1019,1018,1017,1016,1015,1014,1013,1012,1011  duplicates: 0

With an offset, the second page shows the first page's last two posts again: two new entries at the top shifted everything down by two. With a deleted post it's the reverse, and a post is skipped without ever being shown. The cursor says "give me the ones older than 1021", so whatever is added at the top of the feed doesn't matter. The Solution Patterns series post "Pagination Strategies in Depth: Offset, Keyset and Opaque Cursor Tokens" covered the database side of this and handing the cursor to the client as an opaque token in detail. To fetch the newest part of the feed, the same idea is used in reverse: "give me the ones newer than 1030".

Deep Dive: Ranking and Media

So far the feed was chronological. Most products move to ranking at some point: new posts, accounts the user interacts with often, and posts with a lot of engagement come forward. What matters architecturally is that ranking doesn't change the feed cache: the cache keeps holding candidate IDs, and the Feed API takes a few hundred candidates, passes them through a scoring step and returns the first page. If a model does the scoring, that step becomes a separate service and takes a share of the latency budget. In a ranked feed the cursor can't be a simple post ID either, because order isn't by time; an identifier for the ordered list produced on the first request and the position within it go into the cursor.

Images and videos shouldn't pass through the application server. The client gets a short-lived, signed upload address (URL, Uniform Resource Locator; known in the literature as a pre-signed URL) from the Post API and uploads the file directly to object storage; the post only carries the file's key. Producing smaller copies is an asynchronous job, and reading goes through a CDN (Content Delivery Network). That way 1 TB a day of image traffic touches neither the API servers nor the database.

Trade-offs

Common Pitfalls

Designing for the average

An average of 125 followers makes push look cheap; the cost is set by a few accounts in the tail of the distribution. Test the design against the largest fan-out.

Writing a copy of the post into the feed

A copy means an edited or deleted post stays in its old form in millions of feeds. The feed holds IDs, and the hydrate step filters out deleted and blocked content.

Doing fan-out inside the request

If the post request waits until every follower has been written to, the author's "Post" button slows down with her follower count. Fan-out is a queue job.

Infinite scroll with an offset

On an ever-growing list, page numbers mean repeated and skipped posts. Use a cursor.

Keeping everyone's feed up to date all the time

Every ID written to the feed of a user who hasn't logged in for months is wasted work. Limit fan-out to active users and rebuild the feed for those who return.

A Small Experiment

★☆☆ Redo the capacity estimate with an average of 400 followers and 5 posts per person per day. How many feed writes per second does the push model produce?

★★☆ Add the pull side to the Redis example: take the latest posts of two followed celebrities from posts:{author} lists, merge them with feed:{user} and return a page of 10 without breaking the cursor logic.

★★★ Add the notion of "active user" to the simulation: if only 40% of users have logged in within the last 7 days and fan-out goes only to them, what's the push model's daily write count? Also compute the cost of rebuilding a returning user's feed.

The feed was something the user pulls when she opens the page. In the next case study the server pushes data to the user the moment it exists: in a chat and notification system we'll discuss WebSocket connections, message ordering and offline users.