I12 · Part 2 · Intermediate
Walkthrough: a news feed / chat app
Fan-out on write, fan-out on read, and the hybrid that exists because one account has 150 million followers.
09On this page
- The problem, and what makes it a real interview
- Capacity estimation, with the arithmetic shown
- The core services and the data model
- Fan-out on write: pay at post time
- Fan-out on read: pay at feed time
- The celebrity problem, and the hybrid that answers it
- Ranking, cursors, and the caching stack
- Part two: the same reasoning applied to chat
- What the interviewer was actually scoring
The problem, and what makes it a real interview
"Design a news feed" is the most-asked medium system design question in the industry, and it is asked because it has one genuinely hard decision buried under a lot of easy ones. Everything about it — the API, the data model, the caching — is routine. The decision is where the work happens: at write time or at read time, and the fact that neither answer works alone at scale. Candidates who reach the hybrid, and can say why the threshold exists, pass. Candidates who describe a beautiful CRUD service and never state the tradeoff do not.
Spend the first four minutes on scope. Not because interviewers reward ceremony, but because the fan-out decision is entirely determined by numbers you have to extract from them.
| In scope | Explicitly out of scope |
|---|---|
| Post text and images; follow / unfollow | Ads, monetization, DMs |
| Home feed: posts from accounts you follow | Search and hashtag discovery (see the search chapter) |
| Infinite scroll, newest-first with light ranking | Full ML ranking infrastructure and training pipelines |
| Likes and comment counts on feed items | Comment threads themselves |
Non-functional targets, stated as numbers because vague ones cannot drive a design: feed load p99 under 200 ms; a new post visible to followers within a few seconds (eventual consistency is fine and the product does not need better); read-heavy by roughly 100:1; availability 99.9% — a briefly stale feed is acceptable, an unavailable one is not. That last sentence tells you the system should favour availability and low latency over strict consistency. Be careful with the label: this is a product-level choice to accept eventual consistency, not the CAP theorem itself, which only describes what a system must give up during a network partition (the PACELC framing, which also covers the latency-versus-consistency tradeoff in normal operation, is closer to what the requirement says).
Capacity estimation, with the arithmetic shown
Do this on the board, out loud, rounding aggressively. The goal is not accuracy to two significant figures; it is to surface the one or two numbers that eliminate an entire design.
| Quantity | Arithmetic | Result |
|---|---|---|
| Daily active users | given | 500 M |
| Feed opens | 500 M × 15 per day ÷ 86,400 s | ~87,000 reads/s average |
| Peak reads | 87,000 × 3 for daily peak | ~260,000 reads/s |
| Posts | 10% of DAU × 1.5 posts ÷ 86,400 s | ~870 writes/s average, ~2,600/s peak |
| Read : write ratio | 87,000 ÷ 870 | ~100 : 1 |
| Average accounts followed | given (mean; median far lower) | 200 |
| Post metadata storage | 75 M/day × 500 B × 365 | ~14 TB/year — trivial |
| Media storage | 30% of 75 M × ~800 KB (all renditions) × 365 | ~6.6 PB/year — object storage, not a database |
| Media egress at peak | 260,000 feeds/s × ~6 images × 150 KB | ~230 GB/s — a CDN problem, not an origin problem |
Two of those numbers decide the architecture. 100:1 read-heavy says precompute: it is worth doing substantially more work per write to make reads cheap. And 6.6 PB/year of media at ~230 GB/s says the media path is completely separate from the feed path — object storage behind a CDN, with the feed API returning URLs, never bytes. Neither of those is a close call, and saying so quickly buys you time for the decision that is.
Say it like this → "At 100:1 read-to-write I'll
spend write-time work to buy read-time speed — that points at
fan-out on write. Before I commit, let me check what happens at the tail of
the follower distribution, because that's where this design usually breaks."
The core services and the data model
Four services, deliberately boring, so that the interesting part stands out. Post service owns the canonical posts table. Graph service owns follows, and answers "who follows X" and "who does X follow" — both directions, because fan-out needs the first and read-time merge needs the second. Feed service owns per-user materialized feeds. Media service issues presigned upload URLs and runs the transcode pipeline from the storage chapter.
| Store | Key | Holds | Why this shape |
|---|---|---|---|
| posts | post_id (snowflake: time-ordered) | author_id, text, media keys, created_at, counters | Time-ordered IDs mean a sort by ID is a sort by time — no extra index |
| follows | (follower_id, followee_id) | created_at | Stored twice, once per direction, because both lookups are hot |
| feed | user_id → sorted list of (score, post_id) | capped at ~500 entries | IDs only. Hydrate post bodies separately so an edited post is never stale in a million copies |
| counters | post_id | likes, comments | Separate, because they change orders of magnitude more often than the post does |
The single most important line in that table is "IDs only". If you copy the post body into every follower's feed, a post edit or deletion means chasing a million copies, and your feed store balloons by a factor of 50. Store references; hydrate at read time from a cache keyed by post_id, where a single copy serves every reader.
Fan-out on write: pay at post time
When a user posts, immediately push the post ID into the materialized feed of every one of their followers. Reading a feed then costs one range read of a precomputed list.
The arithmetic: 870 posts/s × 200 followers = ~174,000 feed appends per second average, and roughly 520,000/s at peak (2,600 × 200). That is a lot but it is entirely tractable — these are tiny appends to a sorted structure, spread across a sharded Redis or Cassandra cluster, and they are asynchronous so they can absorb a queue. Read the 200 as a planning figure, not a measurement: the real fan-out per post is the author's own follower count, so the total is the sum over posts of followers(author), weighted by how often each author posts. Accounts that post a lot tend to have more followers than the mean, so expect the true average to sit above 174,000/s, with a long tail of a few accounts far above it. That tail is the next section.
Two optimizations cut it substantially and both are worth volunteering. Fan out only to active users: with 2 B registered accounts and 500 M daily actives, most followers will not open the app today, so writing to them is pure waste. Fan out to accounts active in the last 30 days (assume about 1 B of the 2 B, a planning figure) and lazily build the feed for anyone else on their next login. That can cut the write rate by up to roughly half. And cap the feed at ~500 entries — nobody scrolls past that, and an uncapped list grows without bound.
Fan-out on read: pay at feed time
| Fan-out on write | Fan-out on read | |
|---|---|---|
| Write cost | O(followers) — 200 appends, up to 150 M for an extreme celebrity | O(1) — one insert |
| Read cost | O(1) — one range scan, p99 target under 10 ms from cache | O(following) — 200 lookups plus a merge, per request |
| Total ops at our numbers | 174 k writes/s, 87 k cheap reads/s | 870 writes/s, 17.4 M lookups/s |
| Storage | Duplicated per follower | Single copy of each post |
| Freshness | Seconds of lag while fan-out drains | Perfectly fresh by construction |
| Unfollow / delete | Requires cleanup, or filtering at read | Free — the merge just stops including them |
| Reach for this when… | Read-heavy, bounded follower counts | Write-heavy, or the reader follows very few, very prolific accounts |
17.4 million lookups per second, with a p99 gated by the slowest of 200 parallel calls, is not a system you can operate. At a 100:1 read ratio, fan-out on read loses on arithmetic. But look at the top-right cell of that table again — that is where fan-out on write dies.
The celebrity problem, and the hybrid that answers it
An account with 150 million followers posts (a deliberately extreme but plausible assumption; the case-studies chapter reports a 31-million-follower account in Twitter's 2013 talks). Under pure fan-out on write that is 150 million feed appends for one tweet. Even at a dedicated 100,000 appends/s you are looking at 1,500 seconds — 25 minutes before the last follower sees it. Worse, it is bursty and it starves everyone else's fan-out behind it in the same queue. And ten such accounts posting in the same minute is a self-inflicted denial of service.
The answer many large feed systems reach: fan out on write for normal accounts, fan out on read for the handful of accounts above a follower threshold, and merge the two at request time. It is not universal. The published design space is push, pull, or a hybrid chosen per producer and consumer (the SIGMOD 2010 "Feeding Frenzy" paper frames it exactly that way), and real systems differ: Twitter's 2013 talks describe push, with an exception for very large accounts reported as being explored, while other feeds compute more at read time. What is universal is that you must justify where the work happens with numbers.
Why this is cheap: the number of accounts above 100,000 followers is small, and, as an assumption you should state, the number of them any one user follows is small — say around six for a typical reader. That figure is illustrative, not a measurement: follow graphs are skewed, so a heavy user may follow dozens of large accounts. Measure the distribution, and if the tail is long, cap the pull (for example, the top 20 large accounts by affinity). With the assumption, a feed read becomes one range scan of the materialized feed plus perhaps six cached "recent posts by author" lookups, merged and re-sorted. That is a bounded, predictable cost, unlike the 200 lookups of pure fan-out on read.
Two refinements, if the interviewer digs. The threshold is a tunable chosen from a cost model, anywhere from roughly 100,000 to 1,000,000 followers, and ideally dynamic rather than a magic constant — the real cost driver is followers × posting rate, so an account with 80,000 followers posting 50 times a day may deserve pull treatment while a 200,000-follower account posting monthly does not. And the celebrity's recent posts are a perfect cache target: one list, read by tens of millions of people, with a hit rate approaching 100%.
This is the whole question
Push for the many, pull for the few, merge at read. If you say only one
thing in this interview, say that — with the 150 million × 25 minutes
arithmetic that forces it.
Dry run: one normal post and one celebrity post through the hybrid design
| Step | Normal account (200 followers) | Celebrity account (150M followers) |
|---|---|---|
| Post time | Fan-out worker appends the post ID to 200 followers' materialized feeds — finishes in well under a second | Follower count is past the ~100k threshold, so no fan-out happens — the post is written once, to the posts table, and nothing else |
| What pure fan-out on write would have cost | (this is what actually happens) 200 appends | 150,000,000 appends; even at a dedicated 100,000 appends/s that's 1,500s — 25 minutes before the last follower sees it |
| Read time — a follower opens their feed | One range scan of their materialized feed, which already contains this post's ID — O(1), p99 under 10 ms from cache | Not in the materialized feed. The read instead pulls the celebrity's cached "recent posts" list (~100% hit rate) and merges it in |
| How many celebrity lists does that one request pull? | 0, if the reader follows no account above the threshold | Around six, under this chapter's stated assumption about a typical reader (measure it; cap the pull if the tail is long) |
| Total read cost for this feed request | 1 range scan | 1 range scan + ~6 cached celebrity-list lookups (assumed), merged and re-sorted — bounded, unlike the 17.4M lookups/s of pure fan-out on read |
Same mechanism, same merge code path — what changes is only which side of the 100k-follower threshold an author falls on. That is why "push for the many, pull for the few, merge at read" describes one system, not two bolted together.
Ranking, cursors, and the caching stack
Ranking. Reverse-chronological is a legitimate v1 and you should say so. When ranking arrives, use the same two-stage shape as search: candidate generation pulls ~500 entries from the materialized feed plus celebrity pulls, then a scorer ranks them on affinity × recency_decay × predicted_engagement. Affinity is how much this reader interacts with this author; recency decay is exponential with a half-life of hours. Keep the score out of the stored feed if you want to change the model without a backfill.
Pagination must use cursors, never OFFSET. The feed has new items
inserted at the head constantly. With LIMIT 20 OFFSET 20, if
five posts arrive between page 1 and page 2, everything shifts down by five
and the user sees five duplicates and misses nothing — or, scrolling the
other way, misses items entirely. A cursor encodes the position in the
ordering itself: (last_score, last_post_id) for a ranked feed,
or just the last post ID for a chronological one, base64-encoded so clients
treat it as opaque. For a ranked feed also pin a session seed and
snapshot timestamp in the cursor, so the ranking model does not reshuffle
under the user mid-scroll.
⚠ OFFSET is also a performance trap, not just a correctness one
Even with a static dataset,
OFFSET 10000 makes the database
produce and discard 10,000 rows before returning yours. Deep pagination
costs grow linearly with depth. A cursor costs an index seek (O(log n))
plus the page itself, regardless of how far the user has scrolled, because
it seeks directly into the index.
| Layer | Key | Hit rate (target) | Why it exists |
|---|---|---|---|
| CDN | media URL | >95% | Media is ~230 GB/s at peak — this is the only layer that can carry it |
| Feed list cache | feed:user_id | ~90% for active users | The top ~100 IDs for 30-day active users; ~4 TB across the fleet (sizing below), the tail lives in Cassandra |
| Post hydration cache | post:post_id | >95% | One copy read by everyone. A multi-get of 20 IDs replaces 20 database reads |
| Celebrity timeline cache | author:recent | ~100% | Makes the pull half of the hybrid essentially free |
| Counter cache | counts:post_id | high, written back in batches | Like counts change far faster than posts; do not make the post cache churn for them |
Feed store sizing, since interviewers ask. Size it for the accounts you actually fan out to, the 30-day actives (assume 1 B, a planning figure of about twice the DAU): 1 B users × 500 entries × 40 bytes = 20 TB if you keep everything hot. Keeping only the top 100 entries in memory is 1 B × 100 × 40 = 4 TB, which is a manageable Redis cluster, with the remainder paged in from a disk-backed store on the rare deep scroll. (Sizing for the 500 M DAU alone would give 10 TB and 2 TB, but those users are only half the accounts you write to.) The hit rates in the table above are targets to design for, not measurements.
Part two: the same reasoning applied to chat
Chat looks like a different problem and is largely the same one with the latency requirement tightened and the connection made persistent. Targets: message delivery p99 under 500 ms, 100 M concurrent connections (20% of 500 M DAU, as in the capacity chapter), ~20 B messages/day (~230,000/s average, ~700,000/s peak), and — unlike the feed — ordering and delivery guarantees actually matter. A feed showing posts slightly out of order is fine. A conversation showing the answer before the question is broken.
Connection management. A tuned Linux box holds 250,000-500,000 idle
WebSockets (a planning figure; WhatsApp reached 2 M+ on one tuned box in 2012,
but that is a record, not a plan) — the constraint is memory (roughly 10-50 KB
per connection in kernel and userspace buffers) and file descriptors, not the
mythical 65,535 port limit, which applies to outbound tuples rather than
accepted connections. So 100 M concurrent needs 100 M ÷ 250,000 = 400
gateway nodes at the conservative figure (200 at 500,000), plus headroom.
Gateways must be as thin as possible: terminate TLS, hold the socket,
translate frames to internal messages. The routing state lives in a
registry (Redis: user_id → gateway_node_id, with a TTL
refreshed by heartbeat) so that any service can find any user's socket in
one lookup. Sending to a user is then: look up the node, publish to that
node's topic, gateway writes the frame.
⚠ The reconnect storm is the failure mode interviewers probe
A gateway holding 250,000 sockets restarts. All 250,000 clients notice
simultaneously and reconnect within a second, hammering your load balancer,
your auth service and your registry at once — and if that overloads the
next gateway, you cascade. Mitigations to name: jittered exponential
backoff on the client (mandatory), a connection-rate limit at the gateway
that sheds rather than queues, and rolling restarts that drain slowly
instead of dropping everything at once. This is the availability chapter's
failback storm, in its most common real-world costume. Also decide what
happens when the registry itself is lost: treat it as a cache that gateways
re-populate on their next heartbeat, and rely on the durable message store
so that nothing is lost, only delayed until the recipient's gateway
re-registers.
Ordering. Never order by client timestamp — clocks are skewed by seconds and users can set them arbitrarily. Assign a monotonic per-conversation sequence number at a single owner (the shard that owns that conversation), so ordering is total within the conversation, which is the only place it is observable. Global ordering across conversations is neither needed nor affordable. The client also attaches a client-generated message UUID so a retry after an ambiguous timeout is deduplicated server-side rather than posting twice — the cheapest idempotency mechanism there is, and its absence is a very visible gap.
Delivery receipts are a four-state machine — sent, server-acked, delivered to device, read — and each transition is itself a message that must be stored and routed. That doubles or triples your message volume, so batch them: acknowledge up to a sequence number rather than per message. Presence looks trivial and is not: 100 M online users heartbeating every 30 seconds is ~3.3 M writes/s just to say "still here," and a single online/offline transition must notify everyone watching. Only subscribe to presence for contacts currently visible on screen, and batch transitions into a periodic digest rather than pushing each one.
And then group chat brings the fan-out question straight back. A message to a 5-person group is 5 deliveries — push it into each member's inbox, exactly like fan-out on write. A message to a 100,000-member community is 100,000 deliveries per message, which is the celebrity problem wearing a different hat. The same answer applies: store the message once per conversation and let clients pull by (conversation_id, seq > last_seen_seq), with a lightweight "something changed" nudge instead of a full delivery. Small groups push, large groups pull, and the threshold is again about member count times message rate. Read receipts in a large group get degraded to an aggregate count or removed entirely, because N readers × M messages of receipt traffic exceeds the traffic of the conversation itself.
Four details that come up as follow-ups. Transport: WebSocket is the default for a persistent bidirectional channel, with long polling as the fallback for networks that block it. Offline users: a message for a device with no live socket is stored, and a push notification (APNs on iOS, FCM on Android) wakes the app, which then syncs by sequence number. Multiple devices: each device tracks its own last-seen sequence number per conversation and pulls the gap, which is the same mechanism as large-group pull. Encryption: with end-to-end encryption the servers route and store ciphertext only, so server-side search, spam filtering and link previews move to the client or need explicit design.
Say it like this → "Chat is the same fan-out
decision with a tighter latency budget. Small conversations fan out on
write into per-user inboxes; large ones store once and let clients pull by
sequence number. Ordering is a per-conversation monotonic sequence assigned
server-side, and client-generated message IDs make retries idempotent. The
genuinely stateful part is the gateway layer, so I'd keep gateways thin and
put user-to-node routing in a registry with heartbeat TTLs."
What the interviewer was actually scoring
- Did you find the real decision? Everything in this design is easy except fan-out. Time spent on the posts table schema is time not spent on the thing being evaluated. Getting to the fan-out tradeoff inside ten minutes is itself the signal.
- Did the numbers drive the design, or decorate it? Estimating 87,000 reads/s and then not using it is worse than not estimating. The chain that scores is: 100:1 read ratio → precompute → 150 M followers breaks precompute → hybrid. Each number must eliminate an option.
- Did you reach the hybrid unprompted? Proposing pure fan-out on write and defending it until the interviewer says "what about a celebrity" is a mid-level performance. Anticipating the tail of the follower distribution yourself is a senior one.
- Did you state what you gave up? Every choice here costs something: the hybrid adds merge complexity and two code paths that can disagree; capped feeds mean deep scroll needs a fallback; async fan-out means seconds of staleness. Naming the cost of your own design is the strongest single behaviour in the whole loop.
- Did you separate the media path? Candidates who route 230 GB/s of images through their API tier have quietly designed something that cannot exist. Object storage plus CDN, with the feed returning URLs, should be a throwaway sentence — but it has to be said.
- Did you handle the boring correctness details? Cursor pagination instead of OFFSET, idempotent writes, IDs-not-bodies in the feed. These separate people who have shipped this from people who have read about it, and they cost one sentence each.
- Did you scope, and did you push back? Saying "reverse-chronological for v1, and here's where ranking would slot in" is stronger than hand-waving an ML system you cannot describe. Interviewers are calibrating judgement about what to build now, not enthusiasm for building everything.
Before you move on
- State the two numbers that rule out each pure strategy — 17.4M lookups/sec for fan-out on read, 25 minutes for the last follower under fan-out on write for a celebrity — and derive the hybrid from their failure.
- Explain why the feed store holds post IDs rather than post bodies, and what breaks on an edit or delete if it stored bodies instead.
- Explain why chat assigns a per-conversation monotonic sequence number instead of trusting client timestamps, and how a client-generated message UUID makes retried sends idempotent.
- Explain why OFFSET-based pagination breaks on a feed with items constantly inserted at the head, and what a cursor encodes instead.
- Describe a reconnect storm and name at least two mitigations that stop one gateway restart from cascading into the next.
- Say which of this chapter's numbers are assumptions you would measure (average followers, large accounts per reader, hit rates) and which are arithmetic (87,000 reads/s, 25 minutes, 400 gateways).
Sources and further reading
- Feeding Frenzy: selectively materializing users' event feeds (SIGMOD 2010) — push, pull and a hybrid decided per producer and consumer pair from update and view rates
- InfoQ: Timelines at Scale (Raffi Krikorian, 2013) — Twitter's published push-based timeline design
- High Scalability: Twitter's architecture (2013 summary) — the 300k read and 6,000 write figures and the large-account exception
- WhatsApp: 1 million is so 2011 — the 2.28 million connections on one server record cited as an upper bound
- Designing Data-Intensive Applications (Martin Kleppmann) — the standard reference for describing load with parameters and percentiles, and its Twitter timeline example
- Google SRE book: addressing cascading failures — why clients must back off with jitter, relevant to the reconnect storm
Claims in this chapter were checked against these sources in October 2026. Figures marked "planning figure" are rules of thumb, not guarantees.
5 questions drawn from 8, scored out of 5. This is practice: it runs in your browser, saves nothing and does not change what you have marked read.
Design a social news feed
"A photo-sharing app wants a home feed: when you open the app you see recent posts from the accounts you follow, and you can keep scrolling. Walk me through the design, and tell me which decision you think matters most."
In scope: creating a post with text and images, following and unfollowing, and the home feed with infinite scroll, newest first. Out of scope: search, ads, direct messages, comment threads, and the training of any ranking model. The figures below are planning assumptions for this exercise, not facts about any real service.
- 100 million daily active users, each opening the feed 20 times a day, spread evenly over 86,400 seconds. The busiest period runs at 3 times the daily average.
- 10% of daily active users publish one post per day. One post in five carries images totalling about 1 MB.
- 400 million accounts are registered, and about 200 million of them opened the app in the last 30 days.
- On average an account follows 200 accounts and has 200 followers. The distribution is very skewed: the median account has fewer than 50 followers, a few thousand accounts have more than 1 million, and the largest has 50 million.
- A new post must appear in followers' feeds within a few seconds. Feed load p99 should be under 300 ms. A briefly stale feed is acceptable; an unavailable feed is not.
- A worker pool dedicated to feed fan-out can append about 100,000 entries per second to feed storage.
Work it out on the whiteboard or on paper first. Nothing on this card is saved, and the checklist stays hidden until you ask for it.
Finished reading?
0 of 36 chapters read in this series