Design a news feed

Design a news feed that provides a user with a list of news items, sorted by approximate reverse chronological order that belong to the topics selected by the user. A news item can be categorized into 1–3 topics. A user may select up to three topics of interest at any time.

This is a common system design interview question. In this chapter, we use the terms “news item” and “post” interchangeably. In social media apps like Facebook or Twitter, a user’s news feed is usually populated by posts from friends/connections. However, in this news feed, users get posts written by other people in general, rather than by their connections.

Requirements

Functional requirements of our news feed system

• A user can select topics of interest. There are up to 100 tags. (We will use the term “tag” in place of “news topic” to prevent ambiguity with the term “Kafka topic.”)
• A user can fetch a list of English-language news items 10 at a time, up to 1,000 items.
• Although a user need only fetch up to 1,000 items, our system should archive all items.
• Latest news first; that is, news items should be arranged in reverse chronological order, but this can be an approximation.
• Components of a news item:
  • A new item will usually contain several text fields, such as a title with perhaps a 150-character limit and a body with perhaps a 10,000-character limit. For simplicity, we can consider just one text field with a 10,000-character limit.
  • Timestamp that indicates when the item was created.
  • It may contain audio, images, or video.
• We may not want to serve certain items because they contain inappropriate content.
• We may consider personalization or social media features like sharing or commenting.

The non-functional requirements of our news feed system can be as follows:

• Scalable to support 100K daily active users each making an average of 10 requests daily, and one million news items/day.
• High performance of one-second P99 is required for reads.
• User data is private.
• Eventual consistency of up to a few hours is acceptable. Users need not be able to view or access an article immediately after it is uploaded, but a few seconds is desirable. Some news apps have a requirement that an item can be designated as “breaking news,” which must be delivered immediately with high priority, but our news feed need not support this feature.
• High availability is required for writes. High availability for reads is a bonus but not required, as users can cache old news on their devices.

High-level architecture

The sources of the news items submit news items to an ingestion service in our backend, and then they are written to a database. Users query our news feed service, which gets the news items from our database and returns them to our users.

A few observations we can make from this architecture:

• The ingestion service must be highly available and handle heavy and unpredictable traffic. We should consider using an event streaming platform like Kafka.
• The database needs to archive all items but only provide up to 1,000 items to a user. This suggests that we can use one database to archive all items and others to serve the required items. We can choose a database technology best suited for each use case. A news item has 10,000 characters, which equals 10 KB. If they are UTF-8 characters, the size of the text will be 40 KB:
  • For serving 1,000 items and 100 tags, the total size of all news items is 1 GB, which can easily fit in a Redis cache.
  • For archival, we can use a distributed sharded file system like HDFS.
• If eventual consistency of up to a few hours is acceptable, a user’s device may not need to update its news items more frequently than hourly, reducing the load on our News feed service.

Above figure shows High-level architecture of our news feed service. A client submits a post to our news feed service. Our ingestor receives the post and performs some simple validations. If the validations pass, our ingestor produces it to a Kafka queue. Our consumer cluster consumes the post and writes it to HDFS. Our batch ETL jobs process the posts and produce them to another Kafka queue. They may also trigger notifications via a notification service. User requests for posts go through our API gateway, which may retrieve users’ tags from our metadata service and then retrieve posts from our Redis table via our backend service. When backend hosts are idle, they consume from the queue and update the Redis table.

Our news feed service’s sources push new posts to the ingestor. The ingestor performs validation tasks that can be done on the news item alone; it does not perform validations that depend on other news items or other data in general. Examples of such validation tasks:

• Sanitize the values to avoid SQL injection.
• Filtering and censorship tasks, such as detecting inappropriate language. There can be two sets of criteria: one for immediate rejection, where items that satisfy these criteria are immediately rejected, and another criteria where items that satisfy these criteria are flagged for manual review. This flag can be appended to the item before it is produced to the queue.
• A post is not from a blocked source/user. The ingestor obtains the list of blocked users from a moderation service. These blocked users are added to the moderation service either manually by our operations staff or automatically, after certain events.
• Required fields have non-zero length.
• A field that has a maximum length does not contain a value that exceeds that length.
• A field that cannot contain certain characters (such as punctuation) does not have a value containing such characters.

The consumer just polls from the queue and writes to HDFS. We need at least two HDFS tables: one for raw news items submitted by the consumer and one for news items that are ready to be served to users. We may also need a separate table for items that require manual review before they are served to users.

Users make GET /post requests to our API gateway, which queries our metadata service for the user’s tags and then queries the appropriate news items from a Redis cache via our backend service. The Redis cache key can be a (tag, hour) tuple, and a value can be the corresponding list of news items. We can represent this data structure as {(tag, hour), [post]}, where tag is a string, hour is an integer, and post is an object that contains a post ID string and a body/content string.

The API gateway also has its usual responsibilities such as handling authentication and authorization, and rate limiting. If the number of hosts increases to a large number, and the usual responsibilities of the frontend have different hardware resources compared to querying the metadata service and Redis service, we can split the latter two functionalities away into a separate backend service, so we can scale these capabilities independently.

Regarding the eventual consistency requirement and our observation that a user’s device may not need to update its news items more frequently than hourly, if a user requests an update within an hour of their previous request, we can reduce our service load in at least either of these two approaches:

1. Their device can ignore the request.
2. Their device can make the request, but do not retry if the response is a 504 timeout.

Before the raw news items are served to users, we may first need to run validation or moderation/censorship tasks that depend on other news items or other data in general. For simplicity, we will collectively refer to all such tasks as “validation tasks”. We may need an additional HDFS table for each task. Each table contains the item IDs that passed the validations. Examples are as follows:

• Finding duplicate items.
• If there is a limit on the number of news items on a particular tag/subject that can be submitted within the last hour, there can be a validation task for this.
• Determine the intersection of the item IDs from the intermediate HDFS tables. This is the set of IDs that passed all validations. Write this set to a final HDFS table. Read the IDs from the final HDFS table and then copy the corresponding news items to overwrite the Redis cache.

Each validation task outputs a set of valid post IDs. When the tasks are done, the intersection task determines the intersection of all these sets, which are the IDs of posts that users can be served. We may also have ETL jobs to trigger notifications via a notification service. Notification channels may include our mobile and browser apps, email, texting, and social media.

Prepare feed in advance

In our design, each user will need one Redis query per (tag, hour) pair. Each user may need to make many queries to obtain their relevant or desired items, causing high read traffic and possibly high latency on our news feed service.

We can trade off higher storage for lower latency and traffic by preparing a user’s feed in advance. We can prepare two hash maps, {user ID, post ID} and {post ID, post}. Assuming 100 tags with 1K 10K-character items each, the latter hash map occupies slightly over 1 GB. For the former hash map, we will need to store one billion user IDs and up to 100*1000 possible post IDs. An ID is 64 bits. Total storage requirement is up to 800 TB, which may be beyond the capacity of a Redis cluster. One possible solution is to partition the users by region and store just two to three regions per data center, so there are up to 20M users per data center, which works out to 16 TB. Another possible solution is to limit the storage requirement to 1 TB by limiting it to a few dozen post IDs, but this does not fulfill our 1,000-item requirement.

Validation and content moderation

In this section, we discuss concerns about validation and possible solutions. Validation may not catch all problems, and posts may be erroneously delivered to users. Content filtering rules may differ by user demographic.

Certain ETL jobs may flag certain posts for manual review. We can send such posts to our approval service for manual review. If a reviewer approves a post, it will be sent to our Kafka queue to be consumed by our backend and served to users. If a reviewer rejects a post, our approval service can notify the source/client via a messaging service.

Certain validations are difficult to automate. For example, a post may be truncated. For simplicity, consider a post with just one sentence: “This is a post.” A truncated post can be: “This is a.” A post with spelling mistakes is easy to detect, but this post has no spelling mistakes but is clearly invalid. Such problems are difficult for automated validation.

Certain inappropriate content, like inappropriate words is easy to detect, but much inappropriate content like age-inappropriate content, bomb threats, or fake news is extremely difficult to automatically screen for.

In any system design, we should not try to prevent all errors and failures. We should assume that mistakes and failures are inevitable, and we should develop mechanisms to make it easy to detect, troubleshoot, and fix them. Certain posts that should not be delivered may be accidentally delivered to users. We need a mechanism to delete such posts on our news feed service or overwrite them with corrected posts. If users’ devices cache posts, they should be deleted or overwritten with the corrected versions.

To do this, we can modify our GET /posts endpoint. Each time a user fetches posts, the response should contain a list of corrected posts and a list of posts to be deleted. The client mobile app should display the corrected posts and delete the appropriate posts.

One possible way is to add an “event” enum to a post, with possible values REPLACE and DELETE. If we want to replace or delete an old post on a client, we should create a new post object that has the same post ID as the old post. The post object should have an event with the value REPLACE for replacement or DELETE for deletion.

For our news feed service to know which posts on a client need to be modified, the former needs to know which posts the client has. Our news feed service can log the IDs of posts that clients downloaded, but the storage requirement may be too big and costly. If we set a retention period on clients (such as 24 hours or 7 days) so they automatically delete old posts, we can likewise delete these old logs, but storage may still be costly.

Another solution is for clients to include their current post IDs in GET /post requests, our backend can process these post IDs to determine which new posts to send (as we discussed earlier) and also determine which posts need to be changed or deleted.

Tagging posts

We can assume an approval or rejection is applied to an entire post. That is, if any part of a post fails validation or moderation, we simply reject the entire post instead of attempting to serve part of it. What should we do with posts that fail validation? We may simply drop them, notify their sources, or manually review them. The first choice may cause poor user experience, while the third choice may be too expensive if done at scale. We can choose the second option.

Another requirement we may need to discuss is whether we need to distinguish rules that apply globally versus region-specific rules. Certain rules may apply only to specific countries because of local cultural sensitivities or government laws and regulations. Generalizing this, a user should not be shown certain posts depending on their stated preferences and their demographic, such as age or region. Furthermore, we cannot reject such posts in the ingestor because doing so will apply these validation tasks to all users, not just specific users. We must instead tag the posts with certain metadata that will be used to filter out specific posts for each user. To prevent ambiguity with tags for user interests, we can refer to such tags as filter tags, or “filters” for short. A post can have both tags and filters. A key difference between tags and filters is that users configure their preferred tags, while filters are completely controlled by us. This difference means that filters will be configured in the moderation service, but tags are not.

A single Redis lookup is no longer sufficient for a user to fetch their posts. We’ll need three Redis hash tables, with the following key-value pairs:

• {post ID, post}: For fetching posts by ID
• {tag, [post ID]}: For filtering post IDs by tag
• {post ID, [filter]}: For filtering out posts by filter

Multiple key-value lookups are needed. The steps are as follows:

1. A client makes a GET /post request to our news feed service.
2. Our API gateway queries our metadata service for a client’s tags and filters. Our client can also store its own tags and filters and provide them in a GET /post request, and then we can skip this lookup.
3. Our API gateway queries Redis to obtain the post IDs with the user’s tags and filters.
4. It queries Redis for the filter of each post ID and excludes this post ID from the user if it contains any of the user’s filters.
5. It queries Redis for the post of each post ID and then returns these posts to the client.

Moderation service

Our system does validation at four places: the client, ingestor, ETL jobs, and in the backend during GET /post requests. We implement the same validations in the various browser and mobile apps and in the ingestor, even though this means duplicate development and maintenance and higher risk of bugs. The validations add CPU processing overhead but reduce traffic to our news feed service, which means a smaller cluster size and lower costs. This approach is also more secure. If hackers bypass client-side validations by making API requests directly to our news feed service, our server-side validations will catch these invalid requests.

Regarding the server-side validations, the ingestor, ETL jobs, and backend have different validations. The general purpose of the moderation service is for us (not users) to control whether users will see submitted posts. Based on our discussion so far, the moderation service will provide the following features for admins:

1. Configure validation tasks and filters.
2. Execute moderation decisions to change or delete posts.

Consolidating moderation into a single service ensures that teams working on various services within our news feed service do not accidentally implement duplicate validations and allows non-technical staff in content moderation teams to perform all moderation tasks without having to request engineering assistance. The moderation service also logs these decisions for reviews, audits, or rollback (reverse a moderation decision).

This moderation request can be processed in the same manner as other write requests to our news feed service. Similar to the ETL jobs, the moderation service produces to the news feed topic, and our news feed service consumes this event and writes the relevant data to Redis.