Architecture SystemDesign

【Architecture】System Design - News Feed

Posted by 西维蜀黍 on 2023-07-31, Last Modified on 2023-11-03

Background

What is news feed? According to the Facebook help page, “News feed is the constantly updating list of stories in the middle of your home page. News Feed includes status updates, photos, videos, links, app activity, and likes from people, pages, and groups that you follow on Facebook”.

Similar questions commonly asked are: design Facebook news feed, Instagram feed, Twitter timeline, etc.

Scope

Functional Requirements

  • Follow others
  • Create tweets
    • 140 limit
    • Include img, and videos
  • View Feed
  1. Candidate: Is this a mobile app? Or a web app? Or both? Interviewer: Both
  2. Candidate: What are the important features? Interview: A user can publish a post and see her friends’ posts on the news feed page.
  3. Candidate: Is the news feed sorted by reverse chronological order or any particular order such as topic scores? For instance, posts from your close friends have higher scores. Interviewer: To keep things simple, let us assume the feed is sorted by reverse chronological order.
  4. Candidate: Can feed contain images, videos, or just text? Interviewer: It can contain media files, including both images and videos.
  5. The whole content of a specified post can be seen on news feed page? Or a simplified version

Non-functional Requirements

  1. Candidate: How many friends can a user have? Interviewer: 5000

  2. Candidate: What is the traffic volume? Interviewer: 10 million DAU

  3. SLA of fetching feed data

  4. Candidate: Can we leverage some of the existing cloud infrastructures provided by Amazon, Google, or Microsoft? Or our compaies have our own infrastructures and we need to use it due to any kinds of consideration

  5. Are we able to use any commercial CDN?

High-level Design

Misc

  • use RDBMS or NoSQL
  • Use CDN/ Object storage
    • object storage may be cheaper
    • CDN is faster

Sharding

  • user_id

Cache

  • Eviction, e.g., LRU

Pull vs Push vs mixture

  • do Push for frequent followers
  • Not do push for famous followees

Estimation

  • storage estimation
  • DAU
  • to store tweets: how many people send * per tweet

Data Model

  1. Follower-Followee: A User can follow other Users or Entities. (m:n)
  2. Author-Post: Users and Entities can generate Posts. For simplicity, assume only Users can generate Posts. (1:n; we can embed the authorId)
  3. Post-Media: Each Post has some associated Medias. (1:n)

Follow APIs

  • POST follow

Newsfeed APIs

The news feed APIs are the primary ways for clients to communicate with servers. Those APIs are HTTP based that allow clients to perform actions, which include posting a status, retrieving news feed, adding friends, etc. We discuss two most important APIs: feed publishing API and news feed retrieval API.

Feed publishing API To publish a post, a HTTP POST request will be sent to the server. The API is shown below:

POST /v1/me/feed Params:

  • content: content is the text of the post.
  • auth_token: it is used to authenticate API requests.

Newsfeed retrieval API The API to retrieve news feed is shown below:

GET /v1/me/feed Params:

  • auth_token: it is used to authenticate API requests.
  • timeline_from
  • timeline_to

Feed publishing

newfeed building

  • User: a user sends a request to retrieve her news feed. The request looks like this: / v1/me/feed.
  • Load balancer: load balancer redirects traffic to web servers.
  • Web servers: web servers route requests to newsfeed service.
  • Newsfeed service: news feed service fetches news feed from the cache.
  • Newsfeed cache: store news feed IDs needed to render the news feed.

feed publishing

  • Load balancer: distribute traffic to web servers.
  • Web servers: web servers redirect traffic to different internal services.
  • Post service: persist post in the database and cache.
  • Fanout service: push new content to friends’ news feed. Newsfeed data is stored in the cache for fast retrieval.
  • Notification service: inform friends that new content is available and send out push notifications.

Deep Dive

My Own Design

feed publishing

Fanout service

Fanout is the process of delivering a post to all friends. Two types of fanout models are: fanout on write (also called push model) and fanout on read (also called pull model). Both models have pros and cons. We explain their workflows and explore the best approach to support our system.

The fanout service works as follows:

  1. Fetch friend IDs from the graph database. Graph databases are suited for managing friend relationship and friend recommendations. Interested readers wishing to learn more about this concept should refer to the reference material [2].

  2. Get friends info from the user cache. The system then filters out friends based on user settings. For example, if you mute someone, her posts will not show up on your news feed even though you are still friends. Another reason why posts may not show is that a user could selectively share information with specific friends or hide it from other people.

  3. Send friends list and new post ID to the message queue.

  4. Fanout workers fetch data from the message queue and store news feed data in the news feed cache. You can think of the news feed cache as a <post_id, user_id> mapping table. Whenever a new post is made, it will be appended to the news feed table as shown The memory consumption can become very large if we store the entire user and post objects in the cache. Thus, only IDs are stored. To keep the memory size small, we set a configurable limit. The chance of a user scrolling through thousands of posts in news feed is slim. Most users are only interested in the latest content, so the cache miss rate is low.

  5. Store <post_id, user_id > in news feed cache.

Fanout on write (Push)

With this approach, news feed is pre-computed during write time. A new post is delivered to friends’ cache immediately after it is published.

Pros:

  • The news feed is generated in real-time and can be pushed to friends immediately.
  • Fetching news feed is fast because the news feed is pre-computed during write time.

Cons:

  • If a user has many friends, fetching the friend list and generating news feeds for all of them are slow and time consuming. It is called hotkey problem.
  • For inactive users or those rarely log in, pre-computing news feeds waste computing resources.

Fanout on read (Pull)

The news feed is generated during read time. This is an on-demand model. Recent posts are pulled when a user loads her home page.

Pros:

  • For inactive users or those who rarely log in, fanout on read works better because it will not waste computing resources on them.
  • Data is not pushed to friends so there is no hotkey problem.

Cons:

  • Fetching the news feed is slow as the news feed is not pre-computed.

Evaluation

We adopt a hybrid approach to get benefits of both approaches and avoid pitfalls in them. Since fetching the news feed fast is crucial, we use a push model for the majority of users. For celebrities or users who have many friends/followers, we let followers pull news content on-demand to avoid system overload. Consistent hashing is a useful technique to mitigate the hotkey problem as it helps to distribute requests/data more evenly.

newfeed building

  1. A user sends a request to retrieve her news feed. The request looks like this: /v1/me/feed

  2. The load balancer redistributes requests to web servers.

  3. Web servers call the news feed service to fetch news feeds.

  4. News feed service gets a list post IDs from the news feed cache.

  5. A user’s news feed is more than just a list of feed IDs. It contains username, profile picture, post content, post image, etc. Thus, the news feed service fetches the complete user and post objects from caches (user cache and post cache) to construct the fully hydrated news feed.

  6. The fully hydrated news feed is returned in JSON format back to the client for rendering.

Wrap up

Requirements

  • recommend posts: recall, rank, filter, post process etc.

Consideration

Scaling the database:

  • Vertical scaling vs Horizontal scaling

  • SQL vs NoSQL

    • we have joint?

  • Master-slave replication

  • Read replicas

  • Consistency models

  • Database sharding

Other talking points:

  • Keep web tier stateless
  • Cache data as much as you can
  • Support multiple data centers
  • Lose couple components with message queues
  • Monitor key metrics. For instance, QPS during peak hours and latency while users refreshing their news feed are interesting to monitor.

Post Composer

  • Server-side rendering (SSR): Rendering the HTML on the server side, which is the most traditional way. Best for static content that require SEO and does not require heavy user interaction. Websites like blogs, documentation sites, e-commerce websites are built using SSR.
  • Client-side rendering (CSR): Rendering in the browser, by dynamically adding DOM elements into the page using JavaScript. Best for interactive content. Applications like dashboards, chat apps are built using CSR.

Infinite Scrolling (prefetch)

  • Infinite scrolling/feed works by fetching the next set of posts when the user has scrolled to the end of their current loaded feed. This results in the user seeing a loading indicator and a short delay where the user has to wait for the new posts to be fetched and displayed.
  • A way to reduce or entirely eliminate the waiting time is to load the next set of feed posts before the user hits the bottom of the page so that the user never has to see any loading indicators. A trigger distance of around one viewport height should be sufficient for most cases. The ideal distance is short enough to avoid false positives and wasted bandwidth but also wide enough to load the rest of the contents before the user scrolls to the bottom of the page.
  • A dynamic distance can be calculated based on the network connection speed and how fast the user is scrolling through the feed.

一致性模型

  • 读己所写一致性（Read-your-writes Consistency）
  • 因果一致性（Causal Consistency）/ Consistent Prefix Reads
  • 单调读一致性（Monotonic Reads）
  • 会话一致性（Session Consistency）

master-master architecture

  • 处理冲突

Rate limit

Downgrade Behaviour

Reference

FEATURED TAGS
algorithm algorithmproblem architecturalpattern architecture aws c# cachesystem codis compile concurrentcontrol database dataformat datastructure debug design designpattern distributedsystem django docker domain engineering freebsd git golang grafana hackintosh hadoop hardware hexo http hugo ios iot java javaee javascript kafka kubernetes linux linuxcommand linuxio lock macos markdown microservices mysql nas network networkprogramming nginx node.js npm oop openwrt operatingsystem padavan performance programming prometheus protobuf python redis router security shell software testing spring sql systemdesign truenas ubuntu vmware vpn windows wmware wordpress xml zookeeper
FRIENDS

TOC