Cruxly › System design › Design Exercises

Activity Feed

fan-out on write vs read; the celebrity problem

Prompt: users follow other users. Each user has a home feed of recent posts from the people they follow, ordered newest first, loaded in pages of 20. Design it.

40 minutes first. The whole problem is one decision, and the correct answer to it is "both".

Applying the four moves: Scope — follow, post, and a paginated home feed newest-first; ranking and ads are a different exercise (see feed ranking). Estimate — the one number is the fan-out: average followers is fine, but the long tail (an account with 10M followers) is what the whole design bends around. Sketch — fan-out-on-write into per-user feed lists, because reads dominate and a precomputed list is the cheapest possible read. Deep dive — break it on purpose with the celebrity account, then arrive at the hybrid: push for normal accounts, pull-and-merge at read time for the few huge ones. That hybrid is the "both" the prompt promises.

Scope and numbers

In scope: post, follow, home feed (reverse chronological, paginated). Out of scope: ranking and relevance, comments, likes, media processing, notifications. Reverse-chronological is a deliberate simplification — say that ranking is a layer on top of the same retrieval problem, not a different problem.

Estimate. 200 million daily actives, 2 posts per user per day, 20 feed loads per user per day.

Posts: 4 x 10^8 / 10^5 = 4,000 writes/s.
Feed reads: 4 x 10^9 / 10^5 = 40,000 reads/s.
Read:write ≈ 10:1 — meaningfully read-heavy, but not 1000:1.

The number that matters is the follower distribution. Median follower count: maybe 200. Mean: maybe 500. Maximum: 100 million. That four-order-of-magnitude spread between median and maximum is the entire design problem, and you should say so in your first two minutes.

Almost every account looks like the median. The system still has to survive the one that doesn't.

The two architectures, costed

Push is cheap to read and expensive to write at the tail. Pull is the exact mirror. Neither survives alone.

	Push (fan-out on write)	Pull (fan-out on read)
Read cost	One partition read — excellent	500 queries + merge, ×40,000/s = 20M queries/s
Write cost	4,000 posts/s × 500 avg followers = 2M inserts/s	One insert — perfect
Celebrity cost	100M-follower post = 100M inserts, ~100s of amplification	No duplication, new follows reflected instantly
Storage	Bounded by capping each feed (~800 entries) → ~2.5 TB total	None — posts stored once

:::key Why neither survives alone The costs are inverted, and they're inverted along the same axis — follower count. That symmetry is what tells you the answer isn't "pick one," it's "split by exactly that axis." :::

The hybrid, and where the threshold goes

Chosen design. Fan out on write for normal accounts. For accounts above a follower threshold, do not fan out at all — store the post once and merge it in at read time.

A feed read becomes: read the precomputed list (one partition read), then query the handful of celebrity accounts this user follows (a few point queries, heavily cached because thousands of users are reading the same celebrity's recent posts), merge the two by timestamp, return 20.

Where does the threshold go? Not a round number pulled from the air. Derive it: fan-out is cheap when followers x post_rate is small relative to the read saving. Most users follow few celebrities, so the read-side merge stays bounded. A threshold around 10^5 followers puts a very small number of accounts on the pull path while removing essentially all of the write amplification. Say the reasoning and then give the number — "call it 100,000, and I'd tune it from the observed distribution" — rather than only the number.

Why this is the right shape. The distribution is extremely long-tailed, so a rule that handles the tail differently costs you two code paths and buys you a bounded worst case. Any single-strategy answer has an unbounded worst case somewhere.

The subtlety worth raising: a celebrity's posts are read by enormous numbers of users, so they are the most cacheable objects in the system. The pull path is cheap precisely because the accounts on it are popular. The two properties that make fan-out impossible are the same ones that make merge-on-read work.

The hybrid isn't a third algorithm — it's the two failed single-strategy answers, run side by side and merged.

Storage and the write path

Posts table. Partition by post_id; a point lookup per post. Posts are immutable after creation, which means aggressive caching with no invalidation.

Author index. (author_id, created_at DESC) — the pull path needs "recent posts by author X" as a single partition read. This is a separate table, keyed differently, maintained on write.

Feed lists. (user_id, created_at DESC) -> post_id, capped at ~800 entries. Store only the ID, not the post — hydrate from the post cache on read. This is what keeps duplication cheap: 16 bytes per entry rather than a kilobyte.

Follow graph. (follower_id) -> followees for the read path, and (followee_id) -> followers for the fan-out path. Both directions, maintained together — a follow writes two rows. Cross-shard, so it is not atomic; make it idempotent and reconcile with a periodic job rather than pretending you have a transaction.

Fan-out is asynchronous. The post write commits, emits an event, and returns. Workers drain the event and do the inserts. The user must see their own post immediately, so the client renders it optimistically and the author's own feed read merges their recent posts directly — a small special case that removes the most-noticed inconsistency in the entire system.

Fan-out to a million followers is chunked: partition the follower list into batches of a few thousand per task so one task cannot run for minutes, and make each batch idempotent so a retry is harmless.

The write commits in one step; everything after that line is background work the author never waits on.

Deep dives

Crossing the threshold. An account grows past 100,000 followers. Existing entries stay in followers' precomputed feeds; new posts go to the pull path. Both paths are merged at read time anyway, so the transition needs no migration at all. A dropping account is the reverse and is equally harmless. This falling-out-for-free property is worth pointing at — it is why the hybrid is cheap rather than merely clever.

A new follow. Their old posts are not in your precomputed feed. Options: backfill on follow (a bounded job — take their last 50 posts), or accept that the feed fills going forward. Backfill is better product and it is a burst of writes on an action that is much rarer than posting. Choose backfill and say the cost.

Deleting a post. With fan-out on write, the ID is in millions of feed lists. Do not chase it. Filter on read: hydration looks up the post and skips ones that are deleted or from blocked authors. The feed list is a list of candidates, not of guaranteed-visible posts — and that framing also gives you blocking, muting and privacy changes for free. This is the single most useful reframing in the design.

Pagination. Never OFFSET — new posts arrive between pages and items shift, so the user sees duplicates and gaps. Use a cursor: the (timestamp, post_id) of the last item returned, and the next page is everything strictly before it. Stable under concurrent writes, and it costs nothing.

Read amplification on the merge path. A user following 50 celebrities does 50 point lookups per feed load. Bound it: cache each celebrity's recent-post list as a single object with a short TTL, so those 50 lookups become 50 cache hits on objects shared by millions of readers.

What if ranking is added? The retrieval stays exactly the same — you over-fetch candidates (say 500 instead of 20) and score them. Saying this shows you chose a design that does not have to be thrown away when the product inevitably changes.

A feed list is a list of candidates, never a list of guaranteed- visible posts — that one framing gives you deletion, blocking, and muting from a single filter step.

How to say it in the interview

"There is exactly one architectural decision here: do I do the work when someone posts, or when someone reads? Let me compute both costs with real numbers, because the answer depends entirely on the follower distribution."

Checklist

Identified fan-out-on-write vs on-read as the single decision
Costed both with real numbers rather than describing them
Led with the follower distribution: median, mean, maximum
Chose a hybrid and derived the threshold rather than asserting it
Noted celebrity posts are the most cacheable objects, which is why pull works
Stored post IDs in feed lists, not post bodies, and capped the list
Made fan-out async and chunked, with the author's own post shown immediately
Handled deletion by filtering on read rather than chasing millions of rows
Used cursor pagination, not OFFSET
Said the design survives the addition of ranking

Practice this interactively