Design a News Feed Recommendation Engine

What is a News Feed?

It is the first thing user sees on Facebook or other social apps which has posts, pictures, and videos from friends or pages the user follows. It's not just a random list; it's carefully made to keep the user engaged and active. If we want to create something like that, we first need to know what our goals are. As these apps get bigger and more people use them, we have to be sure that the News Feed stays fun, fresh, and relevant for everyone.

Goals

These are the requirements that we need to consider when designing a system like this:

1. Users might have lots of friends and people they follow.
2. The feed should show pictures, videos, and posts from those a user connects with.
3. Whenever someone shares a new post, it should instantly pop up for those online.
4. Users should see their feed updates immediately, without delay. With these basics in mind, the next thing is to figure out how big and powerful our system should be. Let's dive into how much capacity our News Feed needs.

Capacity Estimation for News Feed

1. Users and Growth: Assume Facebook has 2 billion active users monthly, with a 5% growth rate per year.
2. Activity Rate: On average, let's say each user has 300 friends and follows 100 pages. If each friend/page posts 2 times a day, that’s 800 new posts per day per user.
3. Data Size: Estimating an average post size (considering text, image, and some metadata) is about 500 KB. For videos, it could be 5 MB, but not everyone posts videos. Therefore, daily data influx per user might be close to:

• 700 posts * 500 KB + 100 videos * 5 MB = 1 GB (approximately)

4. Storage Requirement:

• Daily: 2 billion users * 1 GB = 2 Exabytes
• Yearly: 365 days * 2 Exabytes/day = 730 Exabytes

5. Bandwidth:

• Every time a user refreshes their feed, they might load the latest 20 posts. So, the bandwidth per refresh would be 20 posts * 500 KB = 10 MB.
• If an average user refreshes their feed 20 times a day, daily bandwidth per user would be 200 MB.
• Total Bandwidth Daily: 2 billion users * 200 MB = 400 Petabytes

High-Level Design

Facebook's News Feed operates chiefly on two pillars: Feed Generation and Feed Publishing.

Feed Generation: Here's how it works:

1. The system first fetches the latest posts from all the users, pages, and groups you follow.
2. It then ranks these posts. Instead of showing you everything, it picks the top ones (say the best 20 or 50) to appear in your feed.

Feed Publishing: This is about how you access more posts when you keep scrolling.

• Initially, you see the latest posts.
• As you scroll, your device asks the server for more. If there's something new, the server lets your device know, and you can either view them instantly or pull them in by refreshing them.

Some of the major building blocks that shape this system.

1. Core Elements:

a. User:

• Heart of the System: Every user is unique in the newsfeed system.
• Unique Identifier: Every user gets a distinct ID.
• Profile Details: Data such as birthdays, emails, etc., needed to set up an account.

b. Feed Overview:

• What It Is: Think of this as a box containing all the posts, images, videos, etc., a user sees.
• Unique Tag: Each of these "boxes" has its identifier.
• User Link: Connects the feed to a particular user or set of users.
• Content Cluster: Groups different types of posts, images, videos, etc.

c. Feed Content:

• Details: These are the individual posts or pieces of content in the newsfeed.
• Unique Tag: Every piece of content has its ID and link to its feed.
• Nature of Content: Differentiates and manages various forms like texts, images, and videos.

d. Media Types:

• Variety: Things like photos or videos.
• Standalone Element: Treated separately to better manage diverse media forms.

Low-level design

Feed Generation

Feed Generation service is responsible for assembling a user's newsfeed by following the below steps:

1. Database Query: The system searches the feed database to:

• Retrieve posts from one's connections, including friends and followed entities.
• Gather content that aligns with the user's interests.

2. Organizing Content (Sort and Rank) Post-collection, there's a need to arrange and prioritize:

• Freshness: Fresh content takes precedence to maintain an updated feed.
• Relevance: Posts are ordered based on their relevance to the user, influenced by a specific ranking algorithm.

Feed Optimization

Some challenges of feed generation are:

• For users with an extensive network, real-time feed generation can be very slow. This latency is due to the intensive preprocessing required to organize vast volumes of posts.
• High-profile users with a multitude of followers further strain the system when sharing their activities.

A solution to mitigate this is pre-generation. Dedicated servers can persistently create news feeds in advance, holding them in memory. When a user opens the app to see their feed, it's promptly served from this pre-compiled data, enhancing efficiency and speed.

For users who infrequently access the platform, continuous feed updates and storage can be resource-draining. Implementing an LRU (Least Recently Used) cache addresses this. Instead of holding every user's pre-generated feed, the LRU cache prioritizes active users. Inactive profiles, or those not accessed for extended periods, are deprioritized, optimizing memory usage.

<aside> 💡 The LRU (Least Recently Used) cache is a caching mechanism that stores a limited number of items based on their recent usage. When the cache is full and a new item needs to be added, the least recently used item is evicted from the cache to make space for the new item. </aside> <aside> 💡 In the context of the News Feed recommendation engine, the LRU cache can be used to optimize memory usage by prioritizing active users. Instead of storing pre-generated feeds for all users, the cache holds feeds for the most recently accessed users. This helps improve efficiency and speed by reducing the storage and processing requirements for infrequently accessed profiles. By implementing the LRU cache, the system can manage limited resources effectively and ensure that the most relevant and up-to-date feeds are readily available for active users. </aside>

Feed Publishing

Feed publishing is the mechanism through which users push content to their followers on platforms like Facebook. Due to the many interactions a user might have, this becomes a hefty task. There are three key methodologies to this: pull, push, and hybrid models.

1. Pull Model

a. Mechanics: The feed is formed and saved in the system's memory when one of the user's connections updates their status. This stored feed is presented to the user only when they actively ask for it.

b. Upsides: This method helps in cutting down data-writing activities. The feed is only assembled when a user wants to see it, reducing system workload.

c. Downfalls: However, it intensifies data-reading activities, which might overload servers. Additionally, there's a waiting period for users, as they must make a request to see newer updates.

2. Push Model

a. Mechanics: In the push model, as soon as a post is made, it's instantly relayed to all followers. The heavy lifting, in terms of data distribution, happens right when the content is posted.

b. Upsides: This approach trims down the amount of data-reading actions, as there's no need to continually sift through a user's myriad of connections for new content.

c. Downfalls: On the flip side, it amplifies data-writing activities. Especially for users with a large network, this can considerably increase the demand on the system, ramping up the database write tasks.

3. Hybrid Model

a. Mechanics: The hybrid approach fuses elements from both pull and push models. So, users with a smaller circle might experience the immediacy of the push model, while those with a larger following might get the on-demand nature of the pull model.

b. Upsides: This blended strategy offers a middle ground, marrying the strengths of both models. It's tailored to enhance system performance and optimize resources, depending on user needs.

c. Downfalls: However, melding two distinct models adds layers of intricacy. Fine-tuning this balance might be challenging, as it necessitates a nuanced design.

Conclusively, feed publishing is a balance between user satisfaction and maintaining robust system operations. Grasping the nuances of the pull, push, and hybrid models is important for efficiency on platforms like Facebook.

Feed Personalization

Facebook uses personalized ranking to make sure its two billion users see what's most important to them on their Feed. With so much content available, it's hard for someone to see everything in one go. In short, personalized ranking helps Facebook show users content they'll really like.

In order to perform personalisation, we would need to sift through a lot of factors to decide the order of posts. While EdgeRank was Facebook's initial approach, the platform now uses more advanced Machine Learning (ML) techniques, offering a finely-tuned, personal experience.

<aside> 💡 **What's the Edge Rank Algorithm About?** On Facebook, interactions like sharing, commenting, or liking are termed as "edges." The Edge Rank Algorithm gives these interactions a score, determining their visibility on your feed. The formula is :Rank = Affinity x Weight x Decay </aside>

Here are some steps that facebook follows:

Inventory: First, they collect recent content you might see when you open Facebook. This includes posts from friends, Pages you follow, and groups you've joined, but not anything that goes against our rules.

Signals: Next, they look at thousands of "signals" for every post to guess what you'd find interesting. These signals are based on actions you take, like liking a post or adding a friend. They help us understand your preferences.

Predictions: Using these signals, they make personalized guesses about the content you'd like. They predict if you'll comment on a post, if it'll start a discussion, or if it's worth your time. They even use surveys to refine our predictions.

The Facebook Feed ranking system utilizes over 100 prediction models, generally falling into four categories:

1. Predictions about your possible actions on a post.
2. Estimates of how long you'll view a post.
3. Assumptions about your interest in the post's origin (person, Page, or group).
4. Predictions about interactions from others if you act on the post.

Each prediction hints at the content's value to you. For instance, if you share a post, it's likely valuable. No single prediction perfectly captures value, so Facebook uses multiple models aiming to provide long-term value.

Some models predict where you might click on a post. For simplicity, these are grouped under "likelihood of clicking on a post part."

These models have varying effectiveness in determining post value. However, their collective use is crucial. Everyone's preferences differ; some might find value in "liking" a post, while others value time spent reading it.

The aim is to tailor the content based on individual preferences. For instance, video engagement might be more crucial than clicking on it. Conversely, article engagement might prioritize clicking.

Ranking: Finally, they give each post a "relevance score" and arrange them based on this score. This ensures you see valuable content first and get a variety of posts from different sources, not just repeated ones from the same Page or group.

Before finalizing the user’s feed, Facebook also adds in recommended content. This helps the user discover more about their interests from others who share them, even if they’re not connected. Additionally, ads are added to the feed. After these steps, the tailored feed is all set and ready to go!