A feed for 10 million followers: build early or on demand (fan-out)

Many apps show a home feed: the newest posts from the people you follow. The interviewer asks: "How do you build the home feed for a user who follows 200 people?" Then comes the second question: "What if one account has 10 million followers?"

A weak answer picks one method and stops, or says "query the posts of everyone they follow" without counting the work. A strong answer counts the work both ways, from the number of posts, the number of feed opens and the number of followers. It sees that the few huge accounts need a different rule.

At SDE-1 level you should explain both methods. At SDE-2 level you should do the arithmetic and design the hybrid. At SDE-3 level you should also handle the burst of work, inactive users and the memory.

Think about newspapers. In one way, a delivery boy puts the paper into every letterbox early in the morning. Reading is quick, but the boy does a lot of work. In the other way, you walk to the newsstand and buy your 200 magazines when you want to read. Delivery needs no work, but reading is slow. Now a famous magazine has 10 million subscribers. Delivering it to 10 million letterboxes at once takes all day. So the shop delivers small magazines to the home, and asks readers to collect the famous one.

• A feed is the list of the newest posts from the accounts a user follows, newest first.
• Fan-out means that one thing spreads to many places.
• Fan-out on write (push): when someone posts, the system adds the post to the feed list of every follower. A read is then one lookup of one list.
• Fan-out on read (pull): at post time the system does nothing extra. At read time it takes the newest posts of every account the user follows and merges them by time.

A feed list holds only post IDs, not whole posts. The IDs are small (8 bytes) and sort by time (lesson 23). A list keeps the newest 200. The system fetches the post text for the IDs it shows from a post store, with a cache in front (lesson 32). If a post was deleted, the system skips its ID.

The work for each method:

• push list writes per day = posts per day x followers per post
• pull lookups per day = feed opens per day x accounts each user follows

Push does work when someone posts. Pull does work when someone reads. So the better method depends on how often people read and how often they post.

The star problem

Push needs one write for each follower. An account with 10 million followers (a star) makes 10 million writes for one post, all at once. The average over a day hides this burst. During the burst, the followers wait for the post, and so does everyone else if they share the same workers.

The fan-out queue and the priority lane

The post itself is saved in the request. That is the promise to the user (lesson 58). The spreading is a job on a queue: "fan out post P". A worker reads the author's follower IDs in batches and inserts the post ID into each list. The lists sit on list servers, split by user ID (lesson 43), so the inserts run in parallel. Adding the same ID twice to a list changes nothing, so a repeated job is safe. The author's own list gets the post at once, so the author sees it.

One queue has a problem. The 10 million jobs of a star wait in front of the normal posts. A priority lane fixes this: a second queue for big accounts. Workers take from the normal lane first and use spare capacity for the big lane.

The hybrid

A celebrity threshold is a follower count. Accounts above it are not pushed. Their posts stay in their own short list of recent posts, and many readers read that same list, so a cache holds it (lesson 31). At read time the system reads the user's feed list and the recent posts of each star the user follows. It merges them by ID and returns the newest 20 (an assumed page size).

How to pick the threshold: the post of an account just below it must reach all followers within your freshness target, using only spare capacity. So threshold = spare list writes per second x target seconds.

Pushing and pulling a star do a similar amount of work in total. Pull spreads it into a smooth stream of cheap cached reads. Push puts it into one burst of writes.

Skip inactive followers

A follower who has not opened the app for 30 days does not read the list. Skip them. This saves writes and memory. When such a user comes back, the system builds the list once with a pull, and then push continues.

A social app. We compare the methods with numbers.

Assumptions (made up to teach with, not real data):

• 20 million users. 12 million are active readers (opened their feed in the last 30 days). 8 million (40%) are inactive readers. An inactive reader can still post.
• Each user follows 200 accounts, so there are 20,000,000 x 200 = 4 billion follow links.
• 200 million of the links point at 50 stars. A star has 4 million followers on average, and each has more than 1 million. The other 3.8 billion links point at ordinary accounts.
• Each ordinary account posts once a day. Each star posts 5 times a day. Each active reader opens the feed 10 times a day: 12,000,000 x 10 = 120 million opens.
• Peak is 3 times the average (lesson 14). One list server does 35,000 list lookups or inserts per second at our 70% target.
• A day has 86,400 seconds.

Step 1: pull for everyone. Each open merges 200 accounts: 120,000,000 x 200 = 24 billion lookups a day = 277,778 per second. At the peak: 833,333 per second. Servers = 833,333 / 35,000 = 23.8, so 24.

Step 2: push for everyone. Ordinary accounts: 3.8 billion writes a day. Stars: 50 stars x 5 posts x 4,000,000 = 1 billion. Total 4.8 billion = 55,556 per second. The stars are 250 posts a day, and still 21% of the writes. At the peak: 166,667 writes per second. Reads are one lookup per open: 120,000,000 / 86,400 = 1,389 per second, 4,167 at the peak. Load = 166,667 + 4,167 = 170,833. Servers = 170,833 / 35,000 = 4.9, so 5. Pull needs 277,778 / 55,556 = 5 times the operations.

Step 3: one star post (the predict box). One server needs 10,000,000 / 35,000 = 286 seconds, which is 4.8 minutes. The five servers can do 5 x 35,000 = 175,000 per second. At the peak they have only 175,000 - 170,833 = 4,167 spare. So the post needs 10,000,000 / 4,167 = 2,400 seconds = 40 minutes. With one shared queue, every normal post waits behind it for up to 40 minutes.

Step 4: the priority lane. Normal posts go first. The star's jobs use the spare 4,167 per second. Normal followers see no delay, but the star's followers still wait 40 minutes.

Step 5: the hybrid. We do not push the 50 stars. Writes: 3.8 billion a day = 43,981 per second, 131,944 at the peak. A star post now costs 0 list writes. Each open reads 1 list and 10 star lists (200 million links / 20 million users = 10 stars on average): 11 lookups, not 200. That is 120,000,000 x 11 = 1.32 billion a day, 18 times fewer than pull. The 50 star lists are the same for all readers, so the cache hit rate is close to 100%. The star lookups are 120,000,000 x 10 / 86,400 = 13,889 per second, 41,667 at the peak. Assumption: one cache server does 100,000 reads per second, so one server (plus a second for safety). List servers at the peak: (131,944 + 4,167) / 35,000 = 3.9, so 4.

Step 6: skip inactive users. 40% of the links to ordinary accounts point at inactive users. Writes become 3.8 billion x 0.6 = 2.28 billion a day = 26,389 per second, 79,167 at the peak. Servers = (79,167 + 4,167) / 35,000 = 2.4, so 3. Memory: a list is 200 x 8 = 1,600 bytes (raw size, without extra overhead). For all users: 20,000,000 x 1,600 = 32 GB. For active users only: 12,000,000 x 1,600 = 19.2 GB. We save 12.8 GB. A returning user costs one pull of 200 lookups.

Step 7: the threshold. Three servers can do 105,000 per second. At the peak, 105,000 - 83,333 = 21,667 are spare. Assumption: a post must reach all followers within 60 seconds. Threshold = 21,667 x 60 = 1,300,000. We choose 1,000,000, which takes 1,000,000 / 21,667 = 46 seconds. All 50 stars are above it.

• Push solves slow reads: one lookup, not 200. It costs write work for every follower, memory for every list, and bursts for stars. I would change it when an account's followers are so many that one post breaks the freshness target.
• Pull solves write bursts and memory. It costs 200 lookups on every open (24 servers against 5). I would use pull for small apps, and for the rare returning user.
• The hybrid solves both problems for almost every user. It costs a merge on every read, a cache for the stars, and a threshold to choose and to watch. I would move the threshold when the spare capacity or the freshness target changes.
• Skipping inactive users solves wasted writes and memory (40%). It costs a slower first open for a returning user.

"Push is always better, because feeds are read far more than they are written." Reads win for most accounts. A star turns one post into 10 million writes, 40 minutes of work at the peak. The daily average hides the burst.

"Pull is too slow to use." Pull is simple, and right for a small app. Take a campus app with 50,000 users. Assumption: each opens the feed 5 times a day and follows 50 accounts. That is 50,000 x 5 x 50 = 12,500,000 lookups a day, or 145 per second. One server is enough.

"Every follower must get the post in their list at once." A follower who has been away for 30 days does not need it. Skipping inactive users cut writes by 40% and memory by 12.8 GB.

1. What does each method do when someone posts and when someone reads? What is the hybrid?
2. An app has 1,000,000 users. Each posts once a day and has 100 followers. Each user follows 100 accounts and opens the feed 20 times a day. (a) How many list writes per second for push? (b) How many lookups per second for pull? (c) How many times more is pull?
3. A star with 2,000,000 followers posts. Your list servers have 10,000 spare inserts per second, and all posts share one queue. How long do normal posts wait? What do you change?