Design a News Feed
People follow each other and open an app to see a feed of recent posts. Reading the feed is by far the most common action. When someone posts, the post has to appear in every follower's feed, and when a celebrity posts that means millions of copies at once. Ranking makes the feed better but must never stop it from loading.
Constraints
- Opening a feed must take under 120 ms
- About 8,000 feed reads per second at peak, and about 1 new post for every 30 reads
- A new post is copied into followers' feeds in the background, and never twice
- A celebrity post can multiply the fan-out work by ten
- Feeds are ranked by a model, but a slow model must not slow the feed
- Keep infrastructure under $16,500 a month
- About 10 billion feed entries are stored, one per post per follower, and people scroll a long way back
Scenarios to survive
Typical peak
Steady reading with a normal posting rate.
Interviewer asks: Why is a feed read-heavy, and what do you precompute so that opening the app is cheap?
Event night (2x)
A big event doubles the feed reads.
Interviewer asks: Which component feels double the reads first, and how do you scale it cheaply?
A celebrity posts
Posting and the copy work behind it jump tenfold for a few minutes.
Interviewer asks: One post becomes millions of feed writes. Where does that work queue up, and what do you do so readers do not notice?
The ranking model slows
Whatever runs ranking becomes 8x slower.
Interviewer asks: Ranking is slow. What does the reader see, and where do you cut the model off?
Readers on every continent
The same number of feed reads, but 60% of them now come from Europe and Asia.
Interviewer asks: A reader in Tokyo opens their feed. Which parts of the answer can come from Tokyo, and which cannot?
What a good design must do
- Feeds open within the latency target at peak
- At least 98% of reads are served at double the load
- Total monthly cost stays within $16,500
- Feeds are read from a precomputed cache
- Something copies posts into feeds
- The celebrity post is absorbed without readers noticing
- A slow ranking model cannot slow feeds
- The design explains when a post is copied at write time and when it is fetched at read time
- Every query is answered through a key or an index, never by reading a whole table
- Readers on every continent open their feed within the target