Facebook News Feed

The problem

"Design the Facebook News Feed": the posts from your friends, the Pages you follow and the groups you're in, scrolled every time you open the app. Park Messenger and ads: each is a system of its own.

This practice problem reuses the pattern of Twitter at Scale. What's new: a friendship is two-way and capped at 5,000 friends, the feed is ranked rather than newest first, every post has an audience, and a refresh should show posts you haven't seen.

The numbers

From the interviewer: 2 billion daily users, each posting about 0.5 times a day and opening the feed about 10 times a day, with about 200 friends on average. Round a day to 100,000 seconds (86,400 really).

• Posts: 2 billion × 0.5 = 1 billion a day, about 10,000 a second (about 12,000 with 86,400).
• Pushes: each post goes to about 200 friends, so about 2 million pushes a second (about 2.3 million exactly). Using the 5,000 cap for every post would give 50 million: the cap is the most, not the average.
• Feed opens: 2 billion × 10 = 20 billion a day, about 200,000 a second.

Push or pull: friends are capped

As in Twitter, a new post's id is pushed into each reader's ready feed in a cache, and huge accounts are pulled at read time. The difference is the cap: a friendship needs both people to agree, and nobody can have more than 5,000 friends. So the most expensive friend's post costs 5,000 pushes: 25× an average post, and 20,000× less than a Twitter celebrity's 100 million. No friend is ever a celebrity, so friends' posts are always pushed. Store a friendship as two rows, Ana → Ben and Ben → Ana, so "Ana's friends" is one lookup.

Pages and groups have no cap. A news Page with 40 million followers would cost 40 million writes per post. Store those posts once, and when someone opens the feed, pull the latest from their big Pages and groups and merge them in.

Ranking: not newest first

For each open, the feed service gathers a few hundred candidates: the ids in the reader's feed cache plus the latest posts of their Pages and groups. A ranking service scores each one, and the feed sends the top 10 or so. A toy score multiplies affinity (how close the reader is to the author), engagement (the likes and comments the post is drawing) and freshness (higher when newer):

post              age        affinity  engagement  freshness  score
Ben's photo       5 hours    5         3           2          30
News Page video   1 hour     2         4           3          24
Dee's post        2 hours    4         1           3          12
Cy's status       just now   1         2           4          8

Newest first would put Cy's status on top; ranked, it comes last. Real systems learn the weights with a model. Facebook's early ranking, publicly known as EdgeRank, was described the same way: affinity, a weight for the type of story, and time decay, multiplied.

Scoring at read time

Scores keep changing: likes pile up, and every post loses freshness by the hour. Scoring once at push time would freeze a post's likes and never let it age, and pulled posts are never pushed at all; a nightly batch job would leave today's posts unranked until tonight. So candidates are scored when the reader opens the feed. That costs 200,000 opens a second × 500 candidates = 100 million scores a second, which is why ranking is a ranking service of its own, sized separately, and why candidates are capped at a few hundred.

Privacy: check the audience on every read

Every post stores its audience: public, friends, or a custom list such as Close friends. Say Cy posts to her friends, then an hour later narrows it to Close friends, a list without Ana: the id is already in Ana's feed cache. Before ranking, the feed service drops every candidate whose current audience doesn't include the reader. That one cheap check catches edited audiences, unfriends and blocks, for pushed and pulled posts alike.

Cleaning the id out of up to 5,000 feeds saves space, but one missed write would leak the post, so it can't be the only guard. A "hidden" flag for the app to obey is worse: the post has already reached the phone.

Seen posts: a refresh shows something new

Ana reads her top 10 and opens the feed again 5 minutes later. Few new posts have arrived, so the same 10 would win again. Keep a seen set per person, the ids shown in the last few days, beside her feed in the cache, and drop them (or rank them lower) at the next read: the posts just below the top 10 move up.

"Only posts newer than the last visit" fails because a ranked feed isn't in time order: this morning's 11th-best post would never be shown. Deleting shown ids from the cached list misses the pulled posts, which come back on every read.

Same pattern as Twitter at Scale

The engine is Twitter's: a queue of new posts, fan-out workers pushing ids into a feed cache split by user id, and huge accounts pulled at read time and merged in. Pages and groups play the celebrities, and the busy path is still the read.

Summary

• Scope: friends (two-way, at most 5,000), Pages and groups; a ranked feed.
• Data: each post keeps its audience; a friendship is stored both ways.
• Numbers: about 2 million pushes and 200,000 feed opens a second.
• Scale: friends' posts always pushed (5,000 at most), big Pages and groups pulled.
• Ranking: a few hundred candidates scored at read time by a ranking service; the top 10 shown.
• Privacy: every candidate's current audience checked at read time.
• Seen posts: a seen set per person, so a refresh shows something new.