#47 Pull/Push Hybrid Fan-out
Instagram News Feed
Build each user's home feed from the people they follow, fast enough to open instantly, including for accounts with a hundred million followers.
What is being asked
Design the home feed of a photo-sharing app: when a user opens the app they see recent posts from accounts they follow, ranked. The classic difficulty is the celebrity whose post must reach an enormous number of feeds.
Requirements
Functional
- Post photos; follow accounts; view a ranked home feed with paging.
Non-functional
- Reads dominate; the feed must load in a couple of hundred milliseconds.
- A new post should appear in followers' feeds within seconds.
- Follower counts range from ten to hundreds of millions.
Design
- Fan-out on write (push). When an ordinary user posts, workers add the post id to the cached feed list of each follower. Reading a feed is then one cache lookup.
- Fan-out on read (pull). For accounts with huge followings, nothing is pushed. When a user opens the feed, the service fetches recent posts of the celebrities they follow.
- Hybrid. The feed service merges the precomputed list with the pulled celebrity posts, sends the candidates to a ranking service, and returns a page.
- Feed caches hold only ids, a few hundred per user; post content is fetched from its own cache.
Key decisions and trade-offs
- Push is fast to read but costly to write: one post by a celebrity would mean a hundred million cache writes. Pull is cheap to write but slow to read. The hybrid uses each where it is cheap.
- Do not build feeds for inactive users. Fan out only to users seen recently; rebuild the feed on demand for someone returning after months.
- Ranking against chronology. Ranking needs features and models and makes paging harder; a cursor with a snapshot of candidates keeps pages stable.
- Eventual consistency. A post that appears a few seconds late, or a deleted post that lingers briefly, is acceptable.
Follow-up questions
- What happens to feeds when a user unfollows someone?
- Where would you set the follower threshold between push and pull?
- How do you page through a ranked feed without duplicates?
- How would you insert advertisements into this pipeline?