Fan-out on write vs fan-out on read

Some writes have an audience. A post goes to every follower. A group message goes to every member. A breaking news alert goes to 50 million phones. Each reader then sees a merge of many writers. A feed is the newest posts of everyone you follow, interleaved.

Somewhere, the system has to join “who follows whom” with “who posted what”. Fan-out on write (push) does that join when the post is made. It stores the result in an inbox per reader. Fan-out on read (pull) does it when a reader asks. Large systems do both, split by a threshold. The hard part is placing the line. The news feed problem designs one end to end. This page covers the pattern wherever it appears.

The problem it solves

A social app has 500 million daily users. Each opens the feed about ten times a day, and the users together make 100 million posts a day. An average post has 200 followers, and an average user follows 200 accounts. At the evening peak (3× the average) that is about 170,000 feed loads a second and 3,500 posts a second.

A feed load needs the 20 newest posts from the 200 accounts this reader follows. There are two places to do that work:

The same join, done at write time or at read time

Scroll or pinch to zoom, drag to pan

• Color key
• Service
• Database
• Cache
• Queue or stream
• Background worker

Pull reads 200 lists on every load: 35 million list reads a second. Push writes each post into 200 inboxes: 690,000 inserts a second, and each load reads one list.

The same shape appears wherever one write has many readers:

System	Writers to one reader	Readers per write	Freshness needed
Social feed	Hundreds of followees	1 to 500 million followers	Seconds
Group chat	The group’s members	Up to about 1,000 members	Under a second
Broadcast notification	A few campaigns	Up to 50 million users	Minutes
Shared folder or document	The collaborators	Members, viewers	Seconds
Market data, live scores, a live leaderboard	One publisher	Thousands to millions	Milliseconds to 1 s

Three numbers decide the design:

• The read to write ratio: feed loads per post.
• The fan-out factor, and how skewed it is. It’s a power law, not a bell curve.
• The freshness target.

How it works

Step 1: Pull: build the feed when it is read

The simplest design stores each post once, in its author’s outbox: a list of post IDs, newest first. A feed load does the join on the spot:

1. Read the list of accounts the reader follows (200).
2. Fetch the newest 20 post IDs from each outbox.
3. Merge the 200 sorted lists, newest first, and keep the top 20. A k-way merge with a heap costs O(n log k).
4. Hydrate the 20 posts (bodies, authors, counts) with one multi-get.

Writes are one append per post, whatever the audience. A post is visible on every follower’s next load, and deletes, privacy changes and unfollows need nothing special, because nothing was copied.

The cost is read amplification. Every load reads 200 lists, so the read path does 35 million lookups a second at peak. Those lookups also hurt latency: they go to 200 places, and the load waits for the slowest. If each lookup has a 1% chance of hitting its p99 latency, a load of 200 lookups hits it on 1 − 0.99^200, about 87% of loads. Fan-out on read turns every load into the tail case.

A cache helps only the head: an account with 150 followers is read a few hundred times a day and is rarely in cache. Pull is right while the numbers are small or reads are rare.

Step 2: Push: write into every follower’s inbox

Move the join to write time. When a post is made, look up the author’s followers and insert the post ID into each follower’s inbox, a bounded list sorted newest first. A feed load reads one inbox and hydrates 20 posts.

Fan-out on write, off the request path

Scroll or pinch to zoom, drag to pan

• Color key
• Database
• Service
• Background worker
• Queue or stream

Three decisions make push affordable:

• Store IDs, not posts. An inbox entry is a post ID and an author ID, about 30 bytes in a Redis sorted set. The post exists once, so an edit is one write and a delete one tombstone.
• Bound the inbox. 500 entries is about 15 KB per user, or 15 TB for a billion users. Almost nobody scrolls past a few hundred posts. Anyone who does falls back to pull for older pages.
• Fan out asynchronously. The author’s request ends once the post is durable and the event is in the log. Workers do the inserts behind it, so the author never waits for 200 or 2 million writes.

The cost is write amplification. One post becomes one insert per follower: 20 billion a day here. And because the work happens after the write, a post reaches its last follower some time later. That delivery lag is the fan-out work, divided by the rate the worker fleet can sustain. At 1 million inserts a second, a post to 200 followers lands in 0.2 ms of fleet time. A post to 50 million followers takes 50 seconds of the whole fleet.

TradeoffPush IDs into bounded inboxes

We gain

A feed load is one list read and one multi-get, a few milliseconds whatever the reader follows. Inboxes can be rebuilt, so they can live in memory without disk durability.

We give up

20 billion inserts a day, and terabytes of RAM. A delay between posting and delivery. And copies of every ID, which deletes, unfollows and privacy changes must chase.

Step 3: Compare them in one unit

The decision is arithmetic, done in operations a second at peak:

Approach	Work per post	Work per feed load	At this app’s peak
Pull	1 append	200 list reads, a merge	35 million list reads a second
Push	1 insert per follower (200)	1 list read	690,000 inserts, 170,000 list reads

Here’s a cleaner way to see it. Every follow edge is used by pushing, once per post the author makes. Or it’s used by pulling, once per feed load the follower makes. So along any edge,

push cost per day = author's posts per day       × cost of one inbox insert
pull cost per day = follower's feed loads per day × cost of one outbox read

Here, authors post 0.2 times a day, and followers load 10 times a day: a ratio of 50. So push wins on total work, unless an inbox insert costs 50 times an outbox read. That’s why systems where reads dominate (feeds, timelines, inboxes) push. And systems where writes dominate, or readers are rare (an audit trail, a dashboard opened once a week), pull.

The Feeding Frenzy paper (Yahoo, 2010) applies this rule per edge. Note what is missing from it: the follower count. Per edge, a celebrity costs no more to push than anyone else.

Step 4: The celebrity: why the average lies

Followers follow a power law. Most accounts have dozens, a few thousand have millions, and a handful have over 100 million. The average of 200 hides that one post from an account with 80 million followers is 80 million inserts at one instant.

Say the fleet is sized for the average peak, with headroom: 1 million inserts a second. It needs 80 seconds for that one post. Whatever is queued behind it waits. That’s called head of line blocking, and it’s what breaks the freshness target, not the total cost. Adding workers does not fix it. A fleet five times larger still needs 16 seconds, and it sits idle the rest of the day. The burst also lands on one partition of the event log (keyed by author), and on every shard of the inbox store at once.

Twitter hit this. In a 2012 talk, Raffi Krikorian described home timelines as lists of about 800 tweet IDs in Redis, filled by fan-out. He said a tweet from an account with tens of millions of followers could take minutes to reach every timeline. For those very large accounts, he described merging their tweets at read time as the direction.

On the read side, a celebrity looks very different: their outbox is read by millions of feeds every second. It is the hottest data in the system, small (a few dozen recent post IDs), and it fits in the memory of every feed server. Reading it costs a memory access, not a network call.

Step 5: The hybrid: push most, pull the few

Split authors by follower count:

• Below the threshold, push. Ordinary posts go into followers’ inboxes as in step 2.
• Above it, pull. A celebrity’s post is appended to their outbox only. Feed servers keep the recent post IDs of every pulled account in memory, refreshed about once a second.
• At read time, merge. A feed load reads the reader’s inbox. It adds the cached outboxes of the pulled accounts this reader follows. It merges them newest first, drops duplicates and deleted posts, and returns the top 20.

Hybrid: one read merges the pushed inbox with pulled outboxes

Scroll or pinch to zoom, drag to pan

• Color key
• Service
• Database
• Cache
• Queue or stream
• Background worker

The code below is the whole pattern in memory:

• Push below the threshold, and pull above it, with a gap between the two thresholds (explained below).
• Idempotent inbox inserts.
• Backfill on follow.
• Inactive users rebuilt on return.
• A k-way merge that filters deletes and unfollows on every read.

JHybridFeed.javaPyhybrid_feed.pyC#HybridFeed.csGohybrid_feed.goTShybrid-feed.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

// An inbox entry is a post ID and its author, never the post itself: an edit or a delete then
// changes one row, not millions of copies. Post IDs are time-ordered (Snowflake style), so the
// ID alone is the sort key and two servers agree on the order without comparing clocks.
record Entry(long postId, String authorId) {}

// Hybrid fan-out. Ordinary authors are pushed: each post is written into every active
// follower's inbox at publish time. Celebrities are pulled: their posts stay in their own
// outbox and are merged into each reader's feed at read time.
final class HybridFeed {
    // Production values are about 1,000,000 and 800,000. Tiny here so the demo shows both paths.
    // The gap is hysteresis: an account hovering near the line does not flip mode every day.
    static final int PULL_ABOVE = 3;
    static final int PUSH_BELOW = 2;
    // Bounded lists: memory per user is capped, and almost nobody scrolls past a few hundred.
    static final int INBOX_CAP = 500;
    static final int OUTBOX_CAP = 500;
    // A new follow copies this many recent posts, or the followee shows up only after its next post.
    static final int BACKFILL = 20;
    // Newest first.
    static final Comparator<Entry> NEWEST_FIRST = Comparator.comparingLong(Entry::postId).reversed();

    private final Map<String, Set<String>> followers = new HashMap<>();
    private final Map<String, Set<String>> following = new HashMap<>();
    private final Set<String> pullMode = new HashSet<>();
    private final Set<String> inactive = new HashSet<>();
    private final Map<String, List<Entry>> inboxes = new HashMap<>();
    private final Map<String, List<Entry>> outboxes = new HashMap<>();
    private final Set<Long> deleted = new HashSet<>();

    void markInactive(String user) {
        // Fan-out skips users who have not opened the app in 30 days. Their inbox is dropped
        // and rebuilt by pull if they come back, so idle users cost no writes and no memory.
        inactive.add(user);
        inboxes.remove(user);
    }

    void follow(String user, String author) {
        followers.computeIfAbsent(author, k -> new HashSet<>()).add(user);
        following.computeIfAbsent(user, k -> new HashSet<>()).add(author);
        updateMode(author);
        // Backfill: a pushed author's recent posts are copied in now. A pulled author needs
        // nothing, because the read path reads its outbox anyway.
        if (!pullMode.contains(author) && !inactive.contains(user)) {
            List<Entry> recent = outboxes.getOrDefault(author, List.of());
            for (Entry e : recent.subList(0, Math.min(BACKFILL, recent.size()))) {
                insertSorted(inboxes.computeIfAbsent(user, k -> new ArrayList<>()), e, INBOX_CAP);
            }
        }
    }

    private void updateMode(String author) {
        // Decided per author from the follower count, with two thresholds. Push to pull is
        // safe at once: old pushed copies stay in inboxes and the merge drops duplicates. Pull to
        // push (not reachable here, as there is no unfollow) must first backfill the author's recent
        // posts into active followers' inboxes, or posts made while pulled vanish from feeds.
        int n = followers.getOrDefault(author, Set.of()).size();
        if (n > PULL_ABOVE) pullMode.add(author);
        else if (n < PUSH_BELOW) pullMode.remove(author);
    }

    // Returns how many inbox writes the post cost: the write amplification of this one post.
    int publish(String author, long postId) {
        Entry e = new Entry(postId, author);
        // Every post lands in its author's outbox: the pull path, backfill and rebuilds read it.
        insertSorted(outboxes.computeIfAbsent(author, k -> new ArrayList<>()), e, OUTBOX_CAP);
        if (pullMode.contains(author)) return 0; // a celebrity post costs one write, whatever the audience
        int writes = 0;
        for (String f : followers.getOrDefault(author, Set.of())) {
            if (inactive.contains(f)) continue;
            // Idempotent: a redelivered event (a worker crashed before committing its offset)
            // finds the ID already there and writes nothing, so retries never duplicate.
            if (insertSorted(inboxes.computeIfAbsent(f, k -> new ArrayList<>()), e, INBOX_CAP)) writes++;
        }
        return writes;
    }

    void delete(long postId) {
        // The guarantee is enforced on read. Removing the ID from every inbox is cleanup that
        // can lag by minutes, so the feed must never trust an inbox entry blindly.
        deleted.add(postId);
    }

    List<Long> feed(String user, int limit) {
        if (inactive.remove(user)) rebuild(user); // returning user: build the inbox once by pull
        Set<String> follows = following.getOrDefault(user, Set.of());
        // Sources to merge: one pushed inbox plus the outbox of every pulled author followed.
        List<List<Entry>> sources = new ArrayList<>();
        sources.add(inboxes.getOrDefault(user, List.of()));
        for (String a : follows) if (pullMode.contains(a)) sources.add(outboxes.getOrDefault(a, List.of()));

        // k-way merge of lists already sorted newest first: take the newest head each step.
        // A heap makes each step O(log k); a scan is simpler and fast for the few dozen
        // sources a reader has.
        int[] pos = new int[sources.size()];
        Set<Long> seen = new HashSet<>();
        List<Long> page = new ArrayList<>();
        while (page.size() < limit) {
            int best = -1;
            for (int i = 0; i < sources.size(); i++) {
                if (pos[i] < sources.get(i).size()
                        && (best < 0 || sources.get(i).get(pos[i]).postId() > sources.get(best).get(pos[best]).postId())) {
                    best = i;
                }
            }
            if (best < 0) break;
            Entry e = sources.get(best).get(pos[best]++);
            // Drop duplicates (an author that just flipped mode is in both sources), deleted
            // posts, and authors the reader no longer follows. Filtering here is what makes
            // deletes, unfollows and mode flips correct on the very next load.
            if (!seen.add(e.postId()) || deleted.contains(e.postId()) || !follows.contains(e.authorId())) continue;
            page.add(e.postId());
        }
        return page;
    }

    private void rebuild(String user) {
        List<Entry> inbox = new ArrayList<>();
        for (String a : following.getOrDefault(user, Set.of())) {
            if (pullMode.contains(a)) continue;
            List<Entry> recent = outboxes.getOrDefault(a, List.of());
            for (Entry e : recent.subList(0, Math.min(BACKFILL, recent.size()))) insertSorted(inbox, e, INBOX_CAP);
        }
        inboxes.put(user, inbox);
    }

    // Insert in newest-first order, skip if present, trim the oldest past the cap.
    // Returns whether anything was written.
    private static boolean insertSorted(List<Entry> list, Entry e, int cap) {
        int i = Collections.binarySearch(list, e, NEWEST_FIRST);
        if (i >= 0) return false;
        list.add(-i - 1, e);
        if (list.size() > cap) list.remove(list.size() - 1);
        return true;
    }
}

class Main {
    public static void main(String[] args) {
        var feed = new HybridFeed();
        for (String u : List.of("ann", "bob", "cat", "dan")) feed.follow(u, "star"); // 4 followers: pulled
        feed.follow("ann", "pal"); // 1 follower: pushed
        feed.markInactive("dan");

        System.out.println(feed.publish("pal", 101)); // 1: one inbox write
        System.out.println(feed.publish("star", 102)); // 0: pulled, merged at read time
        System.out.println(feed.publish("pal", 103)); // 1
        System.out.println(feed.publish("pal", 103)); // 0: a redelivered event writes nothing
        System.out.println(feed.feed("ann", 10)); // [103, 102, 101]

        feed.delete(101);
        System.out.println(feed.feed("ann", 10)); // [103, 102]: hidden on the next load

        feed.follow("bob", "pal"); // backfill copies pal's recent posts into bob's inbox
        System.out.println(feed.feed("bob", 10)); // [103, 102]
        System.out.println(feed.feed("dan", 10)); // [102]: dan follows only star, rebuilt on return
    }
}

TradeoffHybrid fan-out with a celebrity threshold

We gain

The largest pushed post is bounded by the threshold. Big accounts’ posts are readable the moment they are stored. Write volume falls by the share of edges pointing at big accounts (30% here). And the pulled lists are the cheapest reads in the system.

We give up

Every feed load becomes a merge, whose width grows with how many big accounts the reader follows. And two sources of entries (inbox and outboxes) must give one consistent page.

Step 6: Choose the threshold with numbers

The threshold is not a guess. Four numbers bound it:

1. The burst bound. The biggest pushed post must finish within a small share of the freshness budget. At 1 million inserts a second, 1 second of fleet time is 1 million followers.
2. The edge share. Take the share of follow edges that point at accounts above the threshold. It’s the write volume removed. It’s also the number of pulled lists in an average merge. In this app, 30% of edges point at accounts above 1 million. So that’s 30% fewer inserts, and an average reader follows about 60 pulled accounts.
3. Feed server memory. Every feed server holds every pulled account’s recent IDs. About 42,000 accounts × 100 IDs × 16 bytes is under 70 MB: cheap. At a 10,000 follower threshold it would be 4.4 million accounts and 7 GB per server: too much.
4. Cost per operation. Use the per-edge formula from step 3, with real costs. A pulled celebrity’s read is a memory access, not a network call. That tips that edge to pull.

Threshold	Inserts a second at peak	Pulled lists per load	Pulled accounts	Worst pushed post
None (all push)	417,000	0	0	48 s
10 million	375,000	20	about 1,600	6 s
1 million	292,000	60	about 42,000	0.6 s
100,000	208,000	100	about 440,000	0.06 s

These rows assume fan-out skips the 40% of follow edges that point at idle users (step 7). They also assume a power law: 50% of edges point at accounts above 100,000 followers, 30% above 1 million, and 10% above 10 million. 1 million is where the burst fits the freshness budget. The merge stays a few dozen lists. And the pulled set fits easily in memory.

Two refinements matter in production:

• Two thresholds, with a gap. An account switches to pull above 1 million followers. It switches back to push only below 800,000. So an account near the line does not switch every day. (This gap is called hysteresis.) Switching from push to pull is safe at once. The old copies stay in inboxes, and the merge drops duplicates. Switching from pull to push needs one step first. Copy the author’s recent posts into active followers’ inboxes. Otherwise, the posts made while pulled vanish from feeds.
• Count what costs. Count followers who are active, not raw followers, because bot farms inflate raw counts. Count posting rate too. An account with 600,000 followers that posts 200 times a day costs more fan-out than one with 3 million that posts weekly.

Try it. Post as each author under each strategy and compare the columns. Then move the threshold and watch writes, reads and memory trade against each other.

Celebrity threshold: pull authors above 1M followers Skip followers idle for 30 days

Graph shows

PushPullHybrid

Post as

@maya180 followers @bakery2.4K followers @writer45K followers @reporter600K followers @athlete8M followers @singer80M followers

pushed author pulled authorinbox copy the post, stored oncezz: idle 30 days

Load your feedReset

Post as an author. Small accounts cost a handful of writes in any strategy; try @singer.

On the whole network	Push	Pull	Hybrid, 1M
This post: inbox writes	-	-	-
This post: every follower can see it after	-	-	-
Fan-out backlog now (time to drain)	empty	empty	empty
Inbox writes a second at peak
Lists read per feed load
List reads a second at peak
Inbox storage

The graph is a sample of eight readers; the table prices the whole network: 100 million posts and 5 billion feed loads a day, peak 3× the average, 200 followers per post on average, 30% of follow edges pointing at accounts above 1 million followers, 40% at users idle for 30 days. A fan-out fleet does 1 million inbox inserts a second. Timelines hold 500 entries of 30 bytes. Times count fan-out work only; queues and networks add tens to hundreds of milliseconds.

Things to try:

• Post as @singer under all three. Push writes 48 million copies and the backlog takes 48 seconds to drain. Pull and the hybrid write once.
• Post as @singer, then at once as @writer. Under push, the writer’s 27,000 copies wait behind the singer’s backlog. Her followers wait most of that 48 seconds. Under the hybrid, it lands in 27 ms. That is head of line blocking, the real reason celebrities are pulled.
• Drag the threshold to 1K. Inserts fall to 42,000 a second, but every load merges 180 lists.
• Untick “skip idle”. Inserts rise by two thirds and inbox memory doubles, all for readers who are not there.

Step 7: Inactive users and lazy materialization

In a typical social graph, a large share of follow edges point at people who have not opened the app in a month. In this example, it’s 40%. Pushing to them buys nothing. Their inboxes take memory and inserts, and nobody reads them.

So fan-out skips users idle for 30 days, and their inbox is dropped. When one returns, the feed service finds no inbox and builds it once by pull: the step 1 algorithm, run once, about 100 ms. It writes the result as the new inbox and marks the user active, so fan-out includes them again. This is lazy materialization: the inbox is a cache of the pull result, created on first read and kept while it is used.

An evicted inbox is handled the same way, so the store is sized for the active set. Many users “returning” at once is the rebuild storm under How it fails.

Step 8: Follows, unfollows and backfill

A new follow must show the followee’s recent posts at once. Otherwise the follow appears to do nothing until their next post. Backfill copies the followee’s newest 20 or so post IDs from their outbox into the follower’s inbox. It is one small job per follow, done asynchronously. A pulled account needs no backfill at all, because the read path reads its outbox anyway.

An unfollow or a block must hide the author’s posts on the very next load, but their IDs sit in the inbox. Each entry carries the author ID, so the merge drops entries whose author is no longer followed (a cached set per reader). A cleanup job removes the entries later. The same filter covers a mode flip: posts pushed before an author became “pulled” are still in inboxes, and the merge simply deduplicates them.

Step 9: Order, edits and deletes in copied data

Order. Each inbox is ordered by post ID, not arrival time, using time-ordered Snowflake-style IDs. So a post fanned out late (a retry, a slow partition) lands in its correct place, not at the top. Pages use the last ID seen as a cursor, so a late insert does not shift the next page.

Events for one author are keyed by author ID in the log, so a delete or edit is processed after the create it refers to. Keying by post ID spreads load better, but then a delete can arrive first, remove nothing, and the post appears after it was deleted.

Edits are cheap because inboxes hold IDs and posts are hydrated from their one copy. Copying full posts into inboxes turns every edit into another fan-out.

Deletes and privacy changes cannot wait for a fan-out to reach every copy. The post store holds a tombstone, hydration returns nothing for it, and the post vanishes from every feed on the next load. Removing the ID from inboxes afterwards is cleanup, as the news feed’s delete deep dive shows.

Step 10: Fan-out workers, queues and lag

At scale, fan-out is a pipeline built from a log and a worker fleet:

A fan-out pipeline with lanes and page tasks

Scroll or pinch to zoom, drag to pan

• Color key
• Service
• Database
• Cache
• Queue or stream
• Background worker

• Split big jobs into page tasks. A post to 500,000 followers becomes 50 tasks of 10,000 followers each. Tasks run in parallel on many workers, and a crash repeats one task, not the whole post.
• Separate lanes. Small fan-outs go through a fast lane, large ones through a bulk lane with its own workers. A friend’s post to 180 followers never waits behind a 900,000 follower fan-out. The same idea as priority queues in the message queues block.
• Group writes by inbox shard. A page of 1,000 followers maps to a few dozen shards of the inbox store. One pipelined batch per shard turns 1,000 network round trips into a few dozen.
• Make every insert idempotent. Delivery from the log is at least once. A sorted set keyed by post ID makes a repeated insert a no-op. A plain list append (LPUSH) would show the post twice.

Fan-out lag is the age of the oldest event not yet fully fanned out, per lane. It is the metric that tells you the freshness target is failing. Consumer offset lag in messages is less useful: one message can be 10 inserts or 10 million.

Options and tradeoffs

Push, pull or hybrid

Strategy	Work per post	Work per read	Inbox storage	Fresh after	Wins when
Pull	1 append	1 read per followee + merge	None	Next read	Few reads per write, small scale, small follow lists
Push	1 insert per follower	1 read	Bounded list per user	Fan-out lag	Reads far outnumber writes and audiences are bounded
Hybrid	Push below the threshold	1 read + merge of pulled	Less than push	Lag, or next read	Reads dominate and a few accounts have huge audiences
Per edge	Push only to frequent readers	Pull from the rest	Smallest	Mixed	Very large graphs where cost per edge is worth computing

Group chat with a cap of about 1,000 members can push everything: no member list is big enough to burst. Channels with unlimited subscribers pull. A broadcast notification has no “read” to defer to, so it pushes, throttled to its deadline.

TradeoffHybrid as the default for feeds

We gain

The read cost of push for almost everyone, without the burst, and an explicit dial for the cases that do not fit.

We give up

The complexity of both. A system that will never have accounts over a few hundred thousand followers should not pay it.

What an inbox entry holds

Entry	Size	Edit or delete	Read cost	Wins when
Post ID + author ID	~30 bytes	One write to the post	1 list read + 1 multi-get	Almost always
ID + precomputed score	~40 bytes	Same	Same, ranked order free	A score known at post time is good enough
Full post copy	1 KB or more	A fan-out to every copy	1 read	Small, immutable messages (some chat designs)
A nudge (“something new”)	A few bytes	Nothing to chase	The client pulls the changes	Clients sync state, as in file sync

The last row is a hybrid in time, instead of by author. Push a tiny notification to every interested client, and let each one pull the data. File sync and collaborative tools use it, because the data a client needs depends on what it already has.

TradeoffIDs in the inbox, hydration at read time

We gain

Inboxes stay small, edits and deletes are one write, and privacy checks run on every read.

We give up

A second lookup on every load (a multi-get of 20 posts from a post cache), which must itself be fast and highly available.

Go deeperWhere inboxes live1 min

Store	Fits because	Costs
In-memory sorted sets (Redis)	Insert and range read in microseconds; trim built in	RAM for every active user; rebuilt after loss
Wide-column store (Cassandra, Bigtable)	Durable, cheap per byte, row per user sorted by ID	Milliseconds per read; deletes leave tombstones to compact
Per-user log in a durable queue	Ordered and replayable, natural for chat sync	Read by offset only; trimming and random deletes are hard

Memory wins for feeds, where the inbox is a cache that can be rebuilt. Chat inboxes are the opposite. The undelivered messages for an offline device are the only record of what it has not seen. So they live in a durable store.

Who gets pushed

Target	Saves	Costs
Every follower	Nothing	Inserts and memory for readers who never come
Active in 30 days	40% of inserts and half the inbox memory	One rebuild per returning user, about 100 ms
Online now (chat, live)	Everything for offline users	Offline users pull on reconnect, from a durable log
Per device	Nothing: devices multiply the fan-out	Needed when each device keeps its own cursor or keys

Go deeperThe per-edge optimum, and why few systems run it2 min

The Feeding Frenzy paper treats each follow edge separately. Push along it if the follower’s read rate times the cost of a pull exceeds the author’s post rate times the cost of a push. On real workloads, it beat both pure push and pure pull. It pushes to the active reader of a quiet author, and pulls for the rare reader of a chatty one.

Few production systems run it in full. The decision needs a rate per edge, and there are hundreds of billions of them, re-estimated as habits change. And the read path must know, per followee, which way each edge goes. A threshold per author, plus “skip idle readers”, captures most of the saving with two numbers. A middle ground is a few reader tiers (daily, weekly, dormant), crossed with author tiers.

How it fails

A fan-out storm. One post with a huge audience floods the workers. It might be a celebrity just under the threshold, a viral reshare that is itself fanned out, or a campaign sent to everyone. Every other post waits. The fix is the threshold, separate lanes, and a cap on how much of the fleet one post may use.

The backlog after the burst. Even when the storm ends, the queue is long. Say the fleet does 1 million inserts a second, with a baseline of 690,000. Then a 30 million insert backlog drains at only 310,000 a second. That’s 97 seconds of every post being late. Size headroom for drain time, not just steady state. And autoscale workers on lag in seconds.

Partial delivery. A worker crashes after writing 400,000 of a post’s 900,000 inserts. Some followers have the post, some do not, and they compare notes. The log redelivers the event because its offset was not committed, and the work repeats. With page tasks, only the unfinished page repeats:

A crash mid fan-out, repaired by redelivery

Scroll or pinch to zoom, drag to pan

• Color key
• Database
• Background worker
• Service

Retries that duplicate. The repair above only works if inserts are idempotent. A list append duplicates the post in 400,000 inboxes. Use a set keyed by post ID, or check-and-insert in one atomic script. The idempotency pattern covers the general rule.

A rebuild storm. Say you lose an inbox cache shard, or a region fails over. Millions of inboxes empty at once. Every one of those readers falls back to pull in the same minute: the 200-read path, at full read rate. Rate-limit rebuilds, and serve a short chronological feed past the limit. Keep inbox replicas, so a node loss does not mean a rebuild.

Out-of-order events. A delete processed before its create, when events are keyed by post ID (step 9). Key by author, and check tombstones on read regardless.

Failure	Blast radius	Detect	Fix
Fan-out storm	Every post behind it is late	Lag up, one author at the head of the queue	Threshold, bulk lane, cap per post
Backlog after a burst	Freshness for everyone, for minutes	Fan-out lag in seconds, drain rate	Headroom, autoscale on lag, lanes
Partial delivery	Some followers miss a post	Tasks retried, lag on the bulk lane	At least once delivery, page tasks, commit after the work
Duplicating retries	A post shown twice	Duplicate IDs in sampled inboxes	Idempotent inserts keyed by post ID
Rebuild storm	Read path at pull cost for many readers	Inbox misses a second, rebuild rate	Rate-limited rebuilds, fallback feed, replicas
Out-of-order events	Deleted posts reappear	Deletes that removed nothing	Key by author, tombstones checked on read

At scale

Numbers to remember.

What	Typical figure
Inbox entry (ID + author + score) in Redis	About 30 bytes compact, 3× that in the default skiplist encoding
Inbox length	A few hundred to 800 entries (Twitter’s 2012 talk: about 800)
One Redis shard, pipelined sorted-set inserts	Hundreds of thousands a second
Fan-out fleet for 100 million posts a day	About 1 million inserts a second with headroom
Celebrity threshold in feed designs	Hundreds of thousands to a few million followers, per author
Mutual friendship caps (Facebook)	5,000 friends, which removes the celebrity problem for friends
Group chat cap (WhatsApp class)	About 1,000 members, pushed to every device
Broadcast notification	50 million users in 10 minutes is about 83,000 sends a second

At 10x activity (a billion posts and 50 billion feed loads a day), things tighten. Pure push with idle readers skipped passes 4 million inserts a second. The hybrid passes about 3 million. The threshold drops, or the freshness target loosens. Page tasks and lanes stop being optional. Inbox memory grows with active users, not activity, because inboxes are capped.

At 100x, regions matter. Each region runs its own fan-out for the users homed there. It reads a replicated stream of every post, because a cross-region insert per follower is too slow and too expensive.

What to monitor:

• Fan-out lag per lane: the age of the oldest unfinished post, alerting above the freshness target.
• Inserts a second, and the distribution of fan-out size per post. The tail tells you the next storm.
• Duplicate rate in sampled inboxes, and retries per task.
• Inbox misses a second, and rebuild latency. A jump means a lost cache, or a mass return.
• Pulled accounts, pulled lists per load and merge latency p99 on feed servers.
• Delivery time from post to the last active follower, sampled with synthetic accounts.

In the interview

Interviewer asksPush or pull for a news feed? Defend it with numbers.

Put both in operations a second at peak. Say 500 million daily users load ten times a day, and 100 million posts have 200 followers each. Pull is about 35 million list reads a second. Push is about 690,000 inserts, with one read per load. Reads outnumber posts 50 to 1, so push wins, as bounded inboxes of post IDs in a sharded in-memory store. Then I would say what push costs: the burst from big accounts, and the memory for idle users. That’s where the hybrid comes in.

Interviewer asksAn account with 80 million followers posts. What happens?

Under pure push, it is 80 million inserts at once. That’s about 80 seconds of a 1 million a second fleet, and every other post queued behind it is late. So accounts above about a million followers are pulled. The post is appended once. Feed servers keep those accounts’ recent post IDs in memory. And every feed load merges them into the pushed inbox. The total work was not the problem. The burst and the head of line blocking were. And the celebrity’s outbox is hot enough to read from memory.

Interviewer asksHow would you choose the threshold?

The fleet rate, times a slice of the freshness budget, caps the biggest pushed post. The edge share above the threshold is both the write saving and the merge width. Feed server memory caps the pulled set. At 1 million inserts a second, that lands near 1 million active followers. I’d switch back to push only below 800,000, so accounts near the line don’t flip. And I’d adjust for posting rate.

Interviewer asksA fan-out worker crashes halfway through a large post. What do followers see?

For a moment some have it and some do not. The event or page task was not committed, so it is redelivered and the work repeats. That is safe because inserts are idempotent, keyed by post ID, so the followers who already have it are unaffected. Big fan-outs are split into tasks of about 10,000 followers, so a crash repeats one task. Fan-out lag on the bulk lane shows it.

Common mistake

"Celebrities are pulled because pushing them is more total work"

Per follow edge, pushing costs one insert per post, and pulling costs one read per feed load. A follower loads far more often than a celebrity posts. So pushing a celebrity is usually less total work. They are pulled because of the burst: tens of millions of writes at one instant, delaying every other post. And because their outbox is hot enough to serve from memory.

Common mistake

Treating a pushed inbox as the source of truth

The inbox is a cache of a join. It can be missing (an idle user, a lost shard), late (fan-out lag), or stale (a deleted post, an unfollow). The read path must handle all three. Rebuild by pull on a miss. Merge pulled sources. And filter every entry against the post store and the follow list. Designs that trust the inbox show deleted posts, and break when a cache node dies.

Mid-level covers

Explains push and pull, and picks push for a read-heavy feed. Stores post IDs in bounded inboxes. Runs fan-out asynchronously through a queue. Names the celebrity problem, with a hybrid.

Senior adds

Prices both in operations a second. Knows the per-edge rule, and why celebrities are a burst problem. Derives the threshold from fleet rate, edge share and memory. Skips idle readers, and rebuilds lazily. Enforces deletes and unfollows on read. Designs lanes, page tasks, idempotent inserts and lag monitoring for the worker fleet.

Seen in

• News feed: the full hybrid. It pushes into Redis timelines, and pulls above 1 million followers. Idle users are rebuilt on return, and deletes are enforced on read.
• Instagram: the news feed’s hybrid reused, with fan-out starting only when a post’s media has finished processing.
• Chat: push through a log to every device of every member, batched per gateway. A 1,024 member cap means no group can burst. And pull for unlimited channels.
• Notification system: a 50 million user broadcast as sharded, throttled, checkpointed fan-out with idempotent recipient IDs.
• Collaborative editor: a fan-out tree, the owner sending each revision to a few relays that send it on to thousands of viewers.
• File sync: push a nudge to every device watching a folder, and let each device pull the changes it is missing.
• Stock exchange: market data fanned out by UDP multicast, one copy on the wire for every subscriber.
• Leaderboard: a live top 10 pushed every second to 100,000 viewers through a fan-out service holding their connections.

Recap

The shape. One write, many readers, each reader a merge of many writers. The join happens at write time (push) or read time (pull).

Pull. One append per post, a read per followee per load. Always fresh, trivial deletes, but read amplification and tail latency on every load.

Push. One insert per follower into a bounded inbox of IDs, one read per load. Write amplification, inbox memory, and lag equal to fan-out work divided by fleet rate.

Decide in one unit. Per edge, push costs the author’s posts and pull costs the follower’s loads. Reads dominate feeds, so push wins on total work.

The hybrid. Celebrities are pulled because of the burst, and because their outboxes are hot. Not because they cost more in total. Set the threshold from fleet rate × freshness budget, edge share, feed server memory and cost per op. Use two thresholds with a gap, so accounts don’t flip.

The details. Skip idle readers and rebuild lazily. Backfill on follow. Order by time-ordered IDs and key events by author. Enforce deletes and unfollows on read, clean up after.

Operations. A log, page tasks, fast and bulk lanes, idempotent inserts, and fan-out lag in seconds as the alert.

Further reading

• The news feed and chat problems on this site. The message queues, caching and partitioning blocks, for the machinery. And hot keys, for the celebrity’s other problems.
• Timelines at Scale, Raffi Krikorian (QCon San Francisco 2012): fan-out into bounded in-memory timelines for active users, and the cost of very large accounts.
• Feeding Frenzy: Selectively Materializing Users’ Event Feeds, Silberstein et al. (SIGMOD 2010): the per-edge push or pull rule and its measured savings.
• Designing Data-Intensive Applications, Martin Kleppmann: chapter 1 uses the Twitter timeline to introduce load parameters, the same push or pull choice.