The whole course ▾
System Design · Lesson 25 of 39 · Week 6
News feeds: fan-out on write or on read
QuickBite adds a feed: posts from the restaurants you follow. One chain has five million followers. Today: fan-out.
New System Design videos go up at 6 pm. Subscribe on YouTube so you don't miss it.
Got a doubt? Ask in the comments under the video.Subscribe
A feed of restaurants you follow.
QuickBite is the food delivery app we grow through the course, from one server to millions of orders.
A feed of restaurants
Week six is about patterns: designs that appear again and again in famous interview questions. The first one powers every social app on your phone.
QuickBite launches a feed: restaurants post new dishes and offers, and customers see posts from the restaurants they follow, newest first. A restaurant app sends a new post to the posts service, which saves it in the posts DB. When a customer app opens the feed, the feed service must gather the latest posts from every restaurant that customer follows, and put them in order. It's the same problem behind every social app's home feed.
Done naively, each feed is a big job: find the two hundred restaurants I follow, fetch each one's recent posts, merge them by time, and keep the newest twenty. At dinner, fifty thousand feeds open every second, and every one repeats that work from scratch. Mock interview two met this problem, called it fan-out, and promised it a lesson of its own. This is that lesson.
Pull: build it when asked
There are two basic ways to build a feed. The first is the one we just drew: build it at the moment someone asks.
It's called fan-out on read, or pull. A post is written once, in one place. The feed is built when someone opened the app, by pulling recent posts from everyone they follow. So writing is cheap, no matter how many followers a restaurant has, and the feed is always fresh: a post appears the moment it's saved.
But reading is expensive. Every open means hundreds of lookups, then a merge. It's slowest for exactly the keen users who follow the most restaurants. And the work is repeated all day: open the app ten times, and the same feed is rebuilt ten times. Caching each restaurant's recent posts helps, as mock interview two showed, but the merge still happens on every open. At fifty thousand opens a second, that adds up fast.
Push: build it in advance
The other way flips it: do the work when a post is written, so reading is instant.
When a restaurant app posts, the posts service puts a job on a fan-out queue. Fan-out workers look up the restaurant's followers, say eight hundred, and add the new post's ID to the front of each follower's list in a feed cache: one Redis list per customer, trimmed to the newest few hundred. Now when the customer app opens the feed, it's a single read of one list, plus fetching twenty posts by ID. Reading becomes almost instant.
That's fan-out on write, or push, and the trade is clear. The work moves from reading to writing: one post becomes one write per follower. Since feeds are read far more often than restaurants post, that's usually a great deal. Usually. In numbers: if a restaurant posts twice a day and each follower opens the feed ten times, push does the work twice, where pull does it ten times.
The celebrity problem
Push works beautifully, right up until one account has millions of followers.
A national pizza chain on QuickBite has five million followers. One post means five million writes, to five million lists. The fan-out workers fall behind: by the time they finish, tonight's offer has expired, and every other restaurant's posts are stuck in the queue behind it. Push breaks on exactly the accounts people care about most. Every big social network has hit exactly this wall.
The answer most big feeds use is a hybrid. For normal accounts, with up to, say, ten thousand followers, push. For huge accounts, don't fan out at all. When a customer opens their feed, read their ready-made list, then merge in the recent posts of the few huge accounts they follow. Those posts are cached and read millions of times: a hot key, from lesson eight, served from memory. Each approach is used exactly where it's cheapest.
Serving it well
Three details turn a working feed into a good one.
Keep ready-made lists only for active users. Someone who hasn't opened the app in a month gets their feed built by pull when they return, which saves a huge amount of memory. Ranking: most feeds don't sort purely by time; a model scores each post, by freshness, and how often you order from that restaurant, and the feed sorts by score. And cursor pagination, from lesson three: the next page starts after the last post you saw, so new posts arriving at the top never cause repeats.
So, in one line: pull for huge accounts and for inactive users, push for everyone else, and merge the two when the feed is read. Twitter, Instagram and Facebook have all described designs built around exactly this idea.
In the interview
Feeds come up as a full question, design Twitter or design Instagram's feed, and inside many other designs.
Say it like this: a hybrid fan-out. Push new posts into followers' feed caches through a queue and workers, except for accounts above a follower threshold, whose posts are pulled and merged in at read time. Then say the threshold out loud, with a number, and that you'd tune it.
Then expect these. Where's the celebrity threshold? Pick a number, say ten thousand followers, and tune it by watching fan-out delays. What if someone unfollows? Filter their posts out when the feed is read, and clean the list lazily. And how fresh must the feed be? A few seconds late is fine, which is what makes the queue and the workers acceptable. And a deleted post? The lists only hold IDs, so when the feed is read, a deleted post simply isn't found, and is skipped.
The common mistake is defending pure push, or pure pull. Each one fails on someone. Name both, show where each breaks, and land on the hybrid.
Quick check
A restaurant with 2,000 followers posts a new dish. Push, or pull?
Show the answer
Push: 2,000 writes is cheap, and every follower's read stays instant.
A chain with 5 million followers posts an offer. How do followers see it?
Show the answer
Pull: its recent posts are merged in when each follower's feed is read.
Remember: pull makes writes cheap and reads costly. Push makes reads cheap and writes costly. And the hybrid pushes for most accounts, and pulls for the celebrities. Tomorrow: searching two million dishes in milliseconds.
Lessons on weekdays, the week's revision on Saturday, a mock interview on Sunday.