Designing Facebook Newsfeed

Why the newsfeed is a fan-in problem, not just a fan-out problem

Twitter's timeline is dominated by one question: when someone posts, how do we push that post to every follower's cached timeline? Facebook's newsfeed has the same push problem, but it adds a second axis: each item in the feed can come from a friend, a page, or a group, and the feed has to merge all three sources, then rank them, before a single pixel renders. That merge-and-rank step is what makes the newsfeed a genuinely different design problem from a plain chronological timeline.

The two failure modes to avoid are the ones the base design calls out: (1) building the feed synchronously on every page load — too slow once a user follows hundreds of people and pages — and (2) blindly fanning out every post to every follower on write — catastrophic once an account has millions of followers. The accepted answer is the hybrid model: fan-out-on-write for ordinary accounts, fan-out-on-load (a live pull) for celebrity accounts, merged at read time.

Requirements and the numbers that drive the design

Functional scope: generate a per-user feed from friends, pages, and groups the user follows; support images, video, and text; append new posts within 5s of publish; serve any user's feed within 2s.

Capacity: at 300M DAU pulling their feed ~5×/day, that's ~1.5B feed reads/day (~17,500 req/s). The storage estimate provisions a ceiling of 500 feed items resident in memory per user (~500KB/user, ~150TB across all active users, ~1,500 machines at 100GB/box). But that ceiling is not the number actually kept warm: usage data shows almost nobody pages past the first 10 pages (20 items/page = 200 items), so the design tunes the resident precomputed store down to 200 items per user for the common case, and falls back to querying the backend directly for the rare user who scrolls further. Everywhere below, "the precomputed feed" means this tuned figure — 200 items — not the 500-item worst-case ceiling. The write side deserves the same sizing: if ~50M posts/day are created and an average author has ~200 followers, fan-out-on-write is 10B timeline appends/day ≈ 115K appends/s in steady state — the budget the celebrity exclusion below protects, and the number that sizes the fan-out queue and worker fleet.

Traced: assembling Jane's first page of feed

Jane follows 300 friends, 200 pages/groups, and 3 celebrity accounts. She opens the app and requests page 1 (20 items). Here is what the feed-read path does, with concrete numbers that stay consistent end to end:

1. Precomputed-feed lookup. The feed service hashes Jane's UserID to the machine holding her resident feed struct (LinkedHashMap<FeedItemID, FeedItem> feedItems; DateTime lastGenerated;) and reads it. This struct was built by write-time fan-out from Jane's ordinary friends, pages, and groups — everyone except the 3 celebrities, who are excluded from write fan-out. The lookup returns the top 200 precomputed items, the tuned resident size from the capacity discussion above.
2. Live pull for celebrities. Because celebrity accounts do not fan out on write, the service issues a targeted read against each of the 3 celebrities' own post stores for anything newer than Jane's lastGenerated timestamp — 20 items per celebrity, capped, giving 60 items.
3. Merge. The 200 precomputed items and the 60 live-pulled items are merged into one candidate set: 200 + 60 = 260 candidate items.
4. Rank. Each of the 260 candidates gets a score from recency, engagement (likes/comments/shares), and Jane's affinity with the author. Candidates are sorted by score, descending.
5. Dedup. A celebrity post that a friend also reshared can appear once from the precomputed set and once from the live pull. Deduping by FeedItemID removes any repeats — in this trace, 2 duplicates — leaving 258 ranked, unique items.
6. Trim and cache. The top 20 of the 258 are returned to Jane's client for page 1. The remaining 238 are written back into Jane's resident struct (subject to the 200-item cap, so the coldest ~38 age out), and the FeedItemID of item #20 becomes the pagination cursor for the next page request.

Every number threads through consistently: 200 (precomputed) + 60 (live-pulled) = 260 candidates, minus 2 duplicates = 258 ranked items, of which the client sees the top 20.

Cursor pagination: what a LinkedHashMap actually gives you

The base design stores each user's resident feed items in a LinkedHashMap<FeedItemID, FeedItem> and describes pagination as "jump to the last FeedItemID the client saw, then return the next batch from there." That is a correct description of the API contract, but a plain LinkedHashMap cannot execute it on its own, and it is worth being precise about why.

A LinkedHashMap gives you O(1) get(key) — so "does FeedItemID X exist, and what is its FeedItem" is fast — and it gives you a defined iteration order (insertion or access order). What it does not give you is a "find the first entry after key X" operation. There is no ceilingKey/floorKey/tailMap equivalent: locating where X sits in the iteration order and continuing from there means walking the map from the beginning, which is O(n) per page, not O(log n) or O(1).

A TreeMap<FeedItemID, FeedItem> (or an in-memory skip list keyed the same way) is the structure that actually supports seek-based pagination: since FeedItemIDs are monotonically increasing (for example, Snowflake-style IDs), tailMap(cursorId, false) gives every entry strictly after the cursor in O(log n), and the first 20 of that view become the next page. Reach for that structure when the API needs "give me the next batch after ID X"; reserve the plain hash-map-backed struct for the O(1) "does this ID exist in my resident set" checks used during merge and dedup in the trace above.

Ranking, consistency, and dedup, tied together

Ranking is a weighted score over signals — likes, comments, shares, recency, media presence. What the trace above adds is exactly where that scoring sits in the pipeline: after the merge of precomputed and live-pulled candidates, and before dedup. Order matters — ranking before dedup means a duplicate FeedItemID can occupy two rank slots until it is removed, so dedup must run once more, cheaply, right before the final trim to the page size the client asked for.

Consistency is deliberately loose here, and that is a design choice, not an oversight: Jane's resident feed struct is a read-mostly cache, rebuilt incrementally every few minutes and refreshed further by the live celebrity pull at request time. A post from a friend can take up to the 5s SLA to reach Jane's resident struct; a post from a celebrity she follows never arrives via a per-follower write — no fan-out job has to reach Jane's struct before she can see it — so a brand-new celebrity post is only as stale as the live pull's own read latency. Be precise about the limit of that payoff, though: after the trace's step 6, pulled celebrity items do sit in Jane's resident struct as merged read results, and from then on their engagement counts and rank are exactly as stale as any fanned-out item until the next request's live pull (keyed on lastGenerated) refreshes the set. So the direct payoff of excluding celebrities from write fan-out is avoiding the fan-out storm and making new posts visible without waiting on a fan-out job — not permanently database-fresh content.

Dedup has one more subtlety worth naming: it needs a stable identity per underlying post, not per fan-out copy. If the same FeedItemID gets written into Jane's resident struct once by ordinary fan-out and once by a periodic regeneration pass, the merge step must key on FeedItemID — not write timestamp or insertion order — or the same post will double-count in ranking and silently take two of the 20 slots on page 1.

Pitfalls

• Celebrity fan-out amplification. Forgetting to exclude high-follower accounts from write fan-out means a single post from a million-follower page triggers a million cache writes; the hybrid model's entire point is to keep write cost proportional to follower count only for "normal" accounts, and pay a small per-request read cost for celebrities instead.
• Push is async through a queue; if a worker crashes mid-fanout, some followers get the update and others do not. The post looks live to some of Jane's friends and missing to others, and a naive retry re-sends the whole fanout job rather than the remaining slice. The fix is to make each fanout job idempotent and resumable: partition the follower list into shards, checkpoint which shards have been written, and on retry skip shards already marked done so a crash only replays the unfinished tail instead of re-fanning-out to followers who already have the post.
• LRU eviction thrash for infrequent users. If the resident-feed cache evicts a user's struct purely on an LRU policy, a user who logs in slightly less often than the cache's working set can churn in and out of memory, forcing a full backend regeneration on every login instead of an incremental one. Predicting login patterns (time of day, day of week) to pre-warm likely-active users avoids paying full generation cost repeatedly for the same borderline users.
• Stale ranking scores. A score computed once at generation time does not move as a post accumulates likes and comments afterward, so a post that goes viral 10 minutes after Jane's feed was generated stays buried below older, lower-engagement posts until the next periodic regeneration. Re-scoring resident items on a short interval is cheaper than a full feed rebuild and keeps ranking closer to real engagement.
• Cursor invalidation across regenerations. If a periodic regeneration pass rewrites Jane's resident struct while she is mid-scroll, a cursor she captured from page 1 (a FeedItemID) might no longer exist in the new struct, or might now sit in a different relative position because ranking scores shifted. Pagination has to tolerate a "cursor not found" case gracefully — falling back to fetching by timestamp — rather than assuming the structure backing the cursor is immutable between requests.

Takeaways

• A newsfeed is a fan-in-then-rank problem: multiple sources (friends, pages, groups) have to be merged and scored before a single timeline exists, which is strictly more than a chronological fan-out.
• The hybrid push/pull split is the load-bearing decision: fan-out-on-write for accounts with normal follower counts keeps reads O(1) per user; fan-out-on-load for celebrity accounts keeps writes from exploding — merge the two at read time.
• Pin down which capacity number is being used at each step — a worst-case ceiling (500 items/user) and a tuned working size (200 items/user) are both legitimate, but a design that mixes them without saying which is which produces silently wrong arithmetic.
• "Jump to a key and return the next batch" is a TreeMap or skip-list operation (ceilingKey/tailMap), not something a plain hash map gives for free — say precisely which structure backs which operation.

Sources

This trace builds on the base "Designing Facebook Newsfeed" lesson in this guide's System Design Problems track (feed generation, fan-out models, data partitioning, and the LinkedHashMap-based resident feed struct), cross-checked against the general fan-out-on-write vs. fan-out-on-load pattern used across large-scale feed systems, as also traced in this guide's "Designing Twitter's Timeline — Fan-out on Write, Traced" lesson, and against standard java.util.TreeMap and java.util.LinkedHashMap API semantics (Java SE documentation) for the pagination correction above.

The push-vs-pull boundary and the memory budget

Where the line sits. Push (fan-out-on-write) is right for accounts whose follower count is bounded: the write cost is one cache append per follower, amortized over many reads, so a normal account with a few hundred followers is cheap. It becomes wrong exactly at the power-law tail — a single post from a million-follower page is a million cache writes in a burst. Pure pull has the mirror-image failure: it makes every feed load re-query and merge all of a user's sources, so a user following 500 friends, pages, and groups pays a 500-way fan-in on every open, blowing the 2s read SLA. The hybrid decides per-account: push below a follower threshold, pull above it, merge at read time. The threshold is a computed quantity, not a label — the guide's Instagram page derives it from a waste budget (with only ~1% of followers opening their feed while a post is still fresh, wasted writes ≈ 0.99·F; capping waste at ~10,000 writes per post puts the crossover near 10⁴ followers, with teams tuning anywhere in the 10k–100k band) — which is exactly why Jane's 3 celebrity accounts are pulled live while her 500 ordinary sources are pushed.

Memory budget, with numbers consistent with the trace. At the tuned 200 items/user and ~1KB/item, each resident feed is ~200KB; across 300M DAU that is ~60 TB, or ~600 boxes at 100GB each. The 500-item worst-case ceiling is ~150 TB / ~1,500 boxes. Quoting the tuned figure (200 items) and the ceiling (500 items) as two different numbers is fine — mixing one's item count with the other's per-item size is the arithmetic trap the trace was built to avoid. Beyond the memory line, the two operational hazards to watch are a fan-out worker crashing mid-job (partial timelines — fixed by the sharded, checkpointed, idempotent fan-out in the pitfalls) and a cursor invalidated by a re-rank between page requests (fall back to timestamp fetch); the on-deploy fingerprint of the former is "some friends see the post, some don't", diagnosable from per-shard fan-out cursor metrics.