In this chapter, you are asked to design a news feed system. 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” [1]. This is a popular interview question. Similar questions commonly asked are to: Design Facebook news feed, Instagram feed, Twitter timeline, etc.

A notification system has already become a very popular feature for many applications in recent years. A notification alerts a user with important information like breaking news, product updates, events, offerings, etc. It has become an indispensable part of our daily life. In this chapter, you are asked to design a notification system.

A notification is more than just mobile push notification. Three types of notification formats are: mobile push notification, SMS message, and Email. Figure 1 shows an example of each of these notifications.

In this chapter, we focus on web crawler design—an interesting and classic system design interview question.

A web crawler is known as a robot or spider. It is widely used by search engines to discover new or updated content on the web. Content can be a web page, an image, a video, a PDF file, etc. A web crawler starts by collecting a few web pages and then follows links on those pages to collect new content. Figure 1 shows a visual example of the crawl process.

In this chapter, we will tackle an interesting and classic system design interview question: Designing a URL shortening service like TinyURL.

Step 1 - Understand the problem and establish design scope

System design interview questions are intentionally left open-ended. To design a well-crafted system, it is critical to ask clarification questions.

Candidate: Can you give an example of how a URL shortener work?
Interviewer: Assume https://www.systeminterview.com/q=chatsystem&c=loggedin&v=v3&l=long is the original URL. Your service creates an alias with shorter length: https://tinyurl.com/y7keocwj. If you click the alias, it redirects you to the original URL.
C: What is the traffic volume?
I: 100 million URLs are generated per day.
C: How long is the shortened URL?
I: As short as possible.
C: What characters are allowed in the shortened URL?
I: Shortened URL can be a combination of numbers (0-9) and characters (a-z, A-Z).
C: Can shortened URLs be deleted or updated?
I: For simplicity, let us assume shortened URLs cannot be deleted or updated.

Here are the basic use cases:

1. URL shortening: Given a long URL -> Return a much shorter URL.
2. URL redirecting: Given a shorter URL -> Redirect to the original URL.
3. High availability, scalability, and fault tolerance considerations.

In this chapter, you are asked to design a unique ID generator in distributed systems. Your first thought might be to use a primary key with the auto_increment attribute in a traditional database. However, auto_increment does not work in a distributed environment because a single database server is not large enough and generating unique IDs across multiple databases with minimal delay is challenging.

Here are a few examples of unique IDs:

Step 1 - Understand the problem and establish design scope

Asking clarification questions is the first step to tackle any system design interview question. Here is an example of candidate-interviewer interaction:
Candidate: What are the characteristics of unique IDs?
Interviewer: IDs must be unique and sortable.
C: For each new record, does ID increment by 1?
I: The ID increments by time but not necessarily only increments by 1. IDs created in the evening are larger than those created in the morning on the same day.
C: Do IDs only contain numerical values?
I: Yes, that is correct.
C: What is the ID length requirement?
I: IDs should fit into 64-bit.
C: What is the scale of the system?
I: The system should be able to generate 10,000 IDs per second.