System Design II
Recently, I read a book about System Design called
System Design Interview: An Insider’s Guide by Alex Xu, II edition.
Here’s my take on it.
I recommend reading the Part-I of this System Design Series here, do check it out!
In this article, we will understand and design 2 Systems
1. News Feed System (A low-level design)
2. Rate Limiter (A high-level design)
Few things to keep in mind!
It is imperative to ask the interviewer questions and clarify your doubts! In order to develop an apt design, it is a great idea to collaborate with the interviewer during the process. Consider your interviewer as your teammate and ask for their suggestions regularly!
- Come up with an initial blueprint for the design. Asking for feedback is very important.
- Draw box diagrams with critical components on the whiteboard or paper. This might include clients (mobile/web), APIs, web servers, etc.
- Do back-of-the-envelope calculations to evaluate if your blueprint fits the scale constraints. Think out loud. This is one of the most crucial steps!
What is back-of-the-envelope calculation?
According to Jeff Dean, Google Senior Fellow, “back-of-the-envelope calculations are estimates you create using a combination of thought experiments and common performance numbers to get a good feel for which designs will meet your requirements”
Estimate Twitter QPS and storage requirements
Please note the following numbers are for this exercise only as they are not real numbers from Twitter.
Assumptions:
• 300 million monthly active users.
• 50% of users use Twitter daily.
• Users post 2 tweets per day on average.
• 10% of tweets contain media.
• Data is stored for 5 years.
Estimations:
Query per second (QPS) estimate:
• Daily active users (DAU) = 300 million * 50% = 150 million
• Tweets QPS = 150 million * 2 tweets / 24 hour / 3600 seconds = ~3500
• Peek QPS = 2 * QPS = ~7000 We will only estimate media storage here.
• Average tweet size:
• tweet_id 64 bytes
• text 140 bytes
• media 1 MB
• Media storage: 150 million * 2 * 10% * 1 MB = 30 TB per day
• 5-year media storage: 30 TB * 365 * 5 = ~55 PB
Dos
- Always ask for clarification. Do not assume your assumption is correct. • Understand the requirements of the problem.
- Let the interviewer know what you are thinking. Communicate with your interview.
- Suggest multiple approaches if possible.
Don’ts
- Don’t jump into a solution without clarifying the requirements and assumptions.
- Don’t go into too much detail on a single component in the beginning.
- If you get stuck, don’t hesitate to ask for hints.
- Don’t think in silence.
News Feed System
Let’s start by building a News Feed System!
These are a few sample questions, one must ask the interviewer in order to design a system as simple as this!
Candidate: Is this a mobile app? Or a web app? Or both?
Interviewer: Both.
Candidate: What are the most important features of the product? Interviewer: Ability to make a post and see friends’ news feed.
Candidate: Is the news feed sorted in reverse chronological order or in a particular order?
The particular order means each post is given a different weight. For instance, posts from your close friends are more important than posts from a group.
Interviewer: To keep things simple, let us assume the feed is sorted by reverse chronological order.
Candidate: How many friends can a user have?
Interviewer: 5000
Candidate: What is the traffic volume?
Interviewer: 10 million daily active users (DAU)
Candidate: Can feed contain images, videos, or just text?
Interviewer: It can contain media files, including both images and videos.
At the high level, the design is divided into two flows:
• Feed publishing: when a user publishes a post, corresponding data is written into the cache/database, and the post will be populated into friends’ news feed.
• Newsfeed building: the news feed is built by aggregating friends’ posts in reverse chronological order.
Rate Limiter
In the HTTP world, a rate limiter limits the number of client requests allowed to be sent over a specified period, thus controlling the rate of traffic. If the API request count exceeds the threshold defined by the rate limiter, all the excess calls are blocked.
The conversation between you and the interviewer should be somewhat like this!
Candidate: What kind of rate limiter are we going to design? Is it a client-side rate limiter or server-side API rate limiter?
Interviewer: Great question. We focus on the server-side API rate limiter. Candidate: Does the rate limiter throttle API requests based on IP, the user ID, or other properties?
Interviewer: The rate limiter should be flexible enough to support different sets of throttle rules.
Candidate: What is the scale of the system? Is it built for a startup or a big company with a large user base?
Interviewer: The system must be able to handle a large number of requests. Candidate: Will the system work in a distributed environment?
Interviewer: Yes.
Candidate: Is the rate limiter a separate service or should it be implemented in application code?
Interviewer: It is a design decision up to you.
Candidate: Do we need to inform users who are throttled?
Interviewer: Yes.
Where to put the rate limiter?
- Client-side implementation - This method iss highly unreliable because client requests can easily be forged by malicious actors.
- Server-side implementation -
Besides the client and server-side implementations, there is an alternative way. Instead, we can create a rate limiter middleware that throttles the throttles excessive requests and returns a HTTP status code 429. The HTTP 429 response status code indicates a user has sent too many requests.
There are various algorithms that can be used for Rate limiting, you can read about them here!
Finally, coming to the high-level design.
At the high level, we need a counter to keep track of how many requests are sent from the same user, IP address, etc. If the counter is larger than the limit, the request is disallowed.
Where shall we store counters?
Using the database is not a good idea due to the slowness of disk access. In-memory cache is chosen because it is fast and supports a time-based expiration strategy. For instance, Redis is a popular option to implement rate limiting. It is an in-memory store that offers two commands:
• INCR: It increases the stored counter by 1.
• EXPIRE: It sets a timeout for the counter. If the timeout expires, the counter is automatically deleted.
So, This is how we can implement and analyze the system design of any low-level or high-level system. Thanks for reading this article, I will be posting Part -III of the System Design Series very soon! ❤
Connect with Me!
Feel free to get in touch with me or email me at vidhik2002@gmail.com!
