Feb. 27, 2022
Here is the link.
, I worked on Facebook's News Feed.
You want to minimize the number of disk seeks that need to happen when loading your home page. The number of seeks could be 0 or 1 but definitely not O(num friends). You also can't store all the data on one machine if you're concerned about scaling, so you've got a couple of options...
If you're willing to tolerate one disk seek, or if your graph has low fan-out (small number of people following any given person), you can de-normalize the data such that the metadata about every piece of activity is propagated to each of the followers of that activity at the time the action occurs. You might think of this as a "push" model. You'd still probably only store one copy of the actual activity data, but you'd push pointers to it (along with whatever other metadata is needed if you're supporting any ranking/filtering) to all the subscribers at the time it is created. Generally the first thing to break in this model will be the process of propagating the activity to all the subscribers, particularly if you have users that have large numbers of followers (celebrities). When this fails, the feed will start to get backed up. This can also be complicated in that you may need to write code that properly updates all of the subscribers whenever the important metadata about the content is updated, and you may want to also add code to update things when someone changes their list of subscriptions.
The alternative is to keep all the recent activity data in memory and not propagate the updates to the subscribers at write time, instead fanning out at the time of loading the home page. This way you avoid all disk seeks. It's also nice in that your fan out size is limited to the number of people a user follows rather than the number of people who follow a user (most people don't have enough time on their hands to follow millions of people, so you don't have the inverse of the celebrity problem). It's also easier to keep things up-to-date, since you don't have to worry about propagating updates to all of the subscribers. The downside of this approach is that the failure scenario is more catastrophic - instead of just delaying updates, you may potentially fail to generate a user's feed. Having some kind of fallback mechanism that approximates the feed (eg by querying only a subset of your friends) is handy to avoid having to show an error page.
Probably the theoretically best approach would be a hybrid of the above two options, but either of these options can be made to work reasonably well even at very large scales.
No comments:
Post a Comment