System design practice

News Feed

medium fan-out queues caching read-heavy

Fan out on write through a queue into feed caches.

Solve it in your browser Read the lesson first

Design the home timeline of a social network: people publish short posts, and everyone who follows them sees those posts at the top of their feed, newest first.

Functional requirements

Use these use case names exactly: the traffic, requirements and tests in problem.proschi refer to them.

Scale

Constraints

What is given

problem.proschi declares the user and the existing graph service that knows who follows whom. Listing the followers of an account pages through up to 5,000 ids and takes about 50 ms. The file also holds the traffic, requirements and tests. Add the components, the connections and the two use cases.

How your design is checked

You write the design as text in Proschi. Tests run in your browser: a simulation of the traffic above checks latency, availability, cost and what happens when a machine fails. How the simulation works.

Start designing

Lesson · 11 min read

Learn it: News Feed #

News Feed: build the feed before anyone asks for it #

A home timeline looks like a query: "the 50 newest posts by people I follow". Run it on every app open and you join a social graph with a posts table ten thousand times a second. This lesson turns the query inside out: deliver each post into its readers' feeds when it is written.

What you'll learn #

The problem, explained #

Who uses it. 20 million daily active users of a social network who publish short posts and read what the people they follow posted.

Functional requirements.

Non-functional requirements.

RequirementTarget
p99 (the latency 99% of requests beat)Read under 50 ms, publish under 90 ms
AvailabilityReading 99.9%
DurabilityA post is never lost after 201; no feed shows a post that was not stored
DecouplingPublishing never waits for the social graph or the feeds; reading never touches a database or the graph
Fault toleranceAny single machine can fail
BudgetAt most $4,000 a month, including the social graph

What is given, and why. given.proschi declares the user and an existing graph service (four replicas) that knows who follows whom. A capacity line sets its latency to 50 ms per call, because listing up to 5,000 follower ids is slow. That number shapes the whole design.

What the tests check.

Back-of-the-envelope #

read : write requests
20 : 1
feed inserts from fan-out (500 × 200)
100k/s
on the feed cache
110k ops/s
through the Feed API
10.5k rps
all feeds, raw
≈ 80 GB
QuantityArithmeticResult
Read feedgiven10k rps
Publish postgiven500 rps
Read : write requests10k ÷ 50020 : 1
Feed inserts from fan-out500 posts/s × 200 followers100k writes/s
Feed cache operations100k inserts + 10k reads110k ops/s
Feed API requests10k reads + 500 publishes10.5k rps
Graph callsone per post500 rps
Feed size per user500 ids × 8 bytesabout 4 KB raw
All feeds (20M users)20M × 4 KBabout 80 GB raw, several times that with Redis overhead
Posts per day, upper bound500/s × 86,400 s × ~1 KBabout 43 GB/day

In Proschi, x200 ZADD … counts 200 cache writes per post; its latency is counted once, as if batched or pipelined.

Sizing the feed cache. A modelled Redis replica takes 100k operations a second, and caches serve writes on every replica. 110k ops/s on two replicas is 55% busy, fine until survive any node failure removes one: 110% on the survivor, saturated.

Sizing the Feed API. 10.5k requests a second at 2k per service replica is 5.25 replicas at 100%. Divide by a 70% target and check it with one replica lost.

Latency. Read feed is load balancer → API → feed cache → post cache: four short hops, two to a 1 ms cache. Publish post is load balancer → API → posts database → queue, then 201. Everything after the 201 (the graph's 50 ms, the 200 writes) is asynchronous. Put the graph call and the feed writes before the 201 and the modelled publish p99 passes 200 ms, against a 90 ms limit.

Database choice. 500 inserts a second fits one PostgreSQL primary (5k writes/s). Cassandra suits append-only posts keyed by author and grows without resharding. Either way, the database is off the read path.

Cost. Graph $400, service replicas $100, a Redis replica $150, a Kafka broker $200, a Cassandra replica $500, a load balancer $50. A careful design fits; an extra replica on every tier does not.

Concepts #

Fan-out on write versus fan-out on read #

ApproachOn publishOn readCost
Fan-out on read (pull)Store each post onceAsk the graph who the user follows, fetch their recent posts, merge and sortCheap writes; slow, expensive reads that hit the graph and the database on every app open
Fan-out on write (push)Look up the followers, insert the post id into each one's precomputed feedRead the precomputed feed: no graph, no mergeWrites amplified by the follower count

Pick by the read/write ratio, weighted by the cost of each. Here reads are 20 times more frequent, the read budget is 50 ms and follower counts stop at 5,000: push wins. Twitter's timeline service has long been described this way, inserting tweet ids into each follower's Redis-backed timeline.

When not to push: when some authors have millions of followers: one post becomes millions of writes and takes minutes to land. The fix is a hybrid: push for ordinary accounts, pull for the few huge ones, merge at read time. The "Feeding Frenzy" paper chooses per producer/consumer pair, by how often one posts and the other reads.

Deep dive A push fan-out in Proschi

The same shape on a different example, group announcements:

title "Push into inboxes"

author  "Author"       [Actor]
api     "Inbox API"    [REST API] x2
log     "Updates"      [Kafka]    x2
pusher  "Pusher"       [Worker]   x2
members "Member Index" [REST API] x2
inboxes "Inboxes"      [Redis]    x2

author -> api     : HTTPS
api    -> log     : produce
log    -> pusher  : consume
pusher -> members : list
pusher -> inboxes : write

usecase "Announce" {
  author   -> api     : POST /announcements
  api      -> log     : PRODUCE Announced a_1
  log     --> api     : ack
  api     --> author  : 202
  log     ->> pusher  : Announced a_1
  pusher   -> members : GET /groups/9/members
  members --> pusher  : 200 [~50 ids]
  pusher   -> inboxes : x50 LPUSH inbox:{member} a_1
}

Store first, then fan out (through a queue) #

Two ordering rules make push safe.

Store first. Write the post durably before anything references it: a feed must never point at a missing post. A fan-out that fails halfway is retried, and the post it points at is already there; a failed store shows the user an error and leaks nothing into feeds.

Fan out behind a queue. After the store, put a PostCreated event on a durable queue and answer 201. A fan-out worker consumes it, calls the graph and writes the feeds, so the author's latency no longer depends on follower count or graph speed.

Retries come free: if the worker dies, the event is consumed again, so feed inserts must be idempotent (safe to repeat). A sorted-set insert keyed by post id is.

The cost is eventual consistency: a follower may open the app a second before the post lands. "Within a few seconds" allows it, and clients usually show the author's own post immediately.

Caching ids and objects separately #

Store feeds as lists of post ids (a Redis sorted set per user, scored by time, trimmed to the newest 500) and the posts in a separate cache keyed by id. A read is two cache calls: 50 ids, then those 50 posts in one batched get.

Why split? A post is written once but referenced by 200 feeds. Copying its text into every feed multiplies memory by 200, and an edit or deletion needs 200 updates. Ids are tiny and immutable.

Deep dive Ids, then objects in Proschi

A board of cards works the same way:

title "Ids, then objects"

reader "Reader"      [Actor]
api    "Board API"   [REST API] x2
lists  "Board Lists" [Redis]    x2
items  "Card Cache"  [Redis]    x2

reader -> api   : HTTPS
api    -> lists : ZREVRANGE
api    -> items : MGET

usecase "Open board" {
  reader -> api    : GET /boards/3
  api    -> lists  : ZREVRANGE board:3 0 19
  lists --> api    : 20 card ids
  api    -> items  : MGET card:… (20 keys)
  items --> api    : 20 cards
  api   --> reader : 200
}

Trimming to 500 ids bounds memory per user. Inactive users' feeds can also expire and be rebuilt on their next visit, a common optimisation this problem leaves out.

Designing it step by step #

1. Scope. Ask about users (20M DAU), feed contents (followees' posts, newest first, no ranking), followers (average 200, max 5,000: no celebrities), freshness (a few seconds) and latency targets. Park ranking, media and celebrities as follow-ups.

2. High-level design. Sketch two flows.

Say why not fan-out on read: every read would call a 50 ms graph and merge the posts of every account the user follows out of the database. Reading the feed never queries a database rules it out, and so would the 50 ms p99.

3. Deep dive.

4. Wrap-up. Walk the requirements: reads touch only caches; publish answers after the store and the queue; the fan-out retries from the queue; nothing is single. Then extend: the celebrity hybrid, ranking (score more candidates than you show), rebuilding expired feeds, and deletion (drop the post from the post cache; feeds still listing its id skip it on read).

Common mistakes #

Fanning out inside the request (wrong/fan-out-in-request). The API stores the post and queues the event, then also calls the graph and writes the 200 feeds before answering. The queue is decoration: the author waits for the 50 ms graph and the fan-out (much longer with 5,000 followers), and the modelled publish p99 climbs past 200 ms. It fails Fan-out runs behind a queue and the Publish post p99 limit.

Two feed cache nodes (wrong/two-feed-cache-nodes). Two Redis replicas handle 110k ops/s at about 55%. Lose one and the survivor needs 110%: feeds stop updating, or the cache falls over and takes reads with it. It fails survive any node failure.

Other classic mistakes.

In the interview #

Start from the ratio: "Reads outnumber writes 20 to 1 and the read budget is 50 ms, so do the work at write time." Then draw the two flows and mark the async boundary.

Likely follow-ups:

Further reading #

Now design it

Review cards for this problem

Short questions on the ideas it needs, from the review cards. Review them daily so they stick.

More system design problems