YT YouTube2Text

YouTube2Text → Transcripts → System Design Interview Prep for Beginners (Full Course)

System Design Interview Prep for Beginners (Full Course) — Transcript

by KodeKloud · 23,662 words · 3,624 segments · language en · Watch on YouTube

Open in transcriber Summarize with AI Download SRT/VTT

Full transcript

0:00Welcome to the system design interview
0:01prep video. This video is designed for
0:04absolute beginners who do not have any
0:06prior system design experience.
0:09System design interviews are generally
0:11very intense and hectic because you have
0:13to think about multiple components and
0:15the pros and cons of each component. My
0:18goal is to provide you a framework that
0:21you can use to answer interview
0:22questions. Once you understand this
0:25framework, we will solve some real
0:27interview problems. You'll also get four
0:30hands-on labs along the video where you
0:33can actually get hands-on experience on
0:35some of the components. If that sounds
0:38useful, let's get started.
0:41I want to be honest about one thing
0:43before we start solving any system
0:45design problem. If you are new to system
0:48design, the first few problems you will
0:51solve will introduce you to concepts you
0:53have never seen before.
0:55And while you go through those new
0:57concepts, you will feel like you don't
1:00know anything. That feeling is normal.
1:04If you keep going, then after a few
1:07problems, you will start seeing the same
1:09patterns again and again, just in
1:12different problems.
1:14And to be completely frank, that is the
1:17only real way to prepare for system
1:19design. solve as many problems as you
1:22can until you know which component to
1:26use and when. That's exactly what we
1:29will do in this course. We will pick
1:32some of the famous problems and solve
1:34them. Now, most of the system design
1:38questions you will face in interviews
1:40are actually open-ended questions. You
1:43will face questions like design
1:45Instagram or design Dropbox.
1:49Now one thing should be absolutely clear
1:51in your mind. Nobody expects you to
1:55design a perfect system in 45 minutes.
1:59So the natural question is what do
2:01interviewers actually expect from you in
2:04these 45 minutes?
2:06When we look at the feedback that
2:08interviewers write for candidates, they
2:10do not write this person knows how a
2:13load balancer works or this person knows
2:17how a cache works. They write things
2:20like she can work with an ambiguous
2:23problem or he explained trade-offs of
2:27his design choices very clearly.
2:30or she took the hint I gave her and
2:34adjusted the design instead of defending
2:36it. If you notice, none of the above
2:40feedback lines is about a specific
2:43technology.
2:45And when the feedback is negative, there
2:48are two things that show up again and
2:50again. The first is the candidate who
2:54jumps straight into architecture.
2:56They do not ask any questions or confirm
2:59requirements with the interviewer.
3:02The second is the candidate who
3:05overengineers.
3:06They go into caches, cues, shards,
3:10multi-reion and are not able to complete
3:13within 45 minutes. If I have to
3:16summarize what interviewers are looking
3:18for, it comes down to four things. First
3:23is judgment under ambiguity.
3:26This means that when the problem is
3:28vague, can you narrow it down to
3:31something concrete?
3:34Second thing they're looking for is
3:35technical depth. When you say, "I will
3:39put a cash here," then can you explain
3:42what problem this cash will solve and
3:45what new problem the cash creates?
3:48Third, communication.
3:51Can you clearly explain to the
3:53interviewer what you're trying to do
3:55while you're doing it? And fourth,
3:57collaboration. You need to ask the right
4:00questions. Validate your assumptions
4:02with the interviewer. If you just assume
4:05things and go with what you think is
4:07right, you will most likely fail the
4:09interview. Picture two candidates
4:12answering the same design Instagram
4:14question. The first candidate grabs the
4:17marker and starts drawing all the
4:19application servers, databases, and
4:21arrows everywhere. The second candidate
4:24asks who the users are and how many,
4:27whether we care more about uploads or
4:30the feed, and then makes the problem
4:32concrete. I'll focus on posting photos
4:35and the home feed, and leave search and
4:38direct messages out of scope.
4:4110 minutes in, the first candidate has
4:43an impressive diagram of the wrong
4:45system. The second candidate has a
4:48smaller, clearer problem that they can
4:50actually solve in 45 minutes.
4:54Both of them may know the same
4:55technology, but they will get very
4:58different scores from the interviewer.
5:01So, the real question is, how do you
5:03become the second candidate every single
5:06time, even when you are under pressure?
5:10For this, you don't need talent or luck.
5:13You need a method. The method I want to
5:16give you is a well-known framework that
5:19you can follow in any system design
5:21interview. It has six steps in total.
5:25This is a very important framework. So,
5:28let's go through them one by one. Step
5:32one is clarifying requirements.
5:35Spend about 5 minutes to make the
5:37problem statement concrete.
5:39Your goal should be to convert design
5:41Instagram into something concrete. For
5:45example, users can post photos. Users
5:48can follow other users. Users can scroll
5:52through a feed where they can see photos
5:54posted by people they follow. And the
5:56feed should load fast as soon as the
5:59user opens the app.
6:01Step two is back of the envelope
6:03estimation.
6:05By this we mean we need to estimate some
6:07numbers to figure out how you need to
6:10scale this app. For example, let's say
6:14we have 10 million daily users and
6:17people scroll a lot more than they post.
6:20People scroll 100 photos every week but
6:24post only one every week. So our app is
6:27read heavy not write heavy. So we need
6:31to focus on reading photos.
6:33You confirm those numbers with the
6:35interviewer before you build on them.
6:38Step three is defining the API.
6:42Spend about 5 minutes here. For our
6:45Instagram, three calls are enough for
6:47all users. First, they make a call to
6:50upload a photo, then to follow a user,
6:55and third to get the home feed where
6:57they scroll photos. And if you notice,
6:59the calls that users make also tell you
7:01what your system needs to store for
7:02users. Photos, a follow list, and a
7:05feed. Step four is a highlevel design.
7:09Spend about 10 to 15 minutes drawing the
7:11plain boxes that satisfy the
7:13requirements for our Instagram. A user,
7:16an app server, a database for users and
7:19follows, a separate storage for the
7:21photos, and arrows showing how a photo
7:23goes in and how the feed comes out.
7:27Step five is the deep dives. Another 10
7:29to 15 minutes on the one or two
7:31components where this problem is
7:33actually hard for Instagram. That's the
7:36home feed. When someone with a million
7:38followers posts a photo, how does that
7:40photo show up in a million feeds without
7:42melting the system? And step six is
7:45bottlenecks and scaling the last 5
7:48minutes. Here you do a critical analysis
7:51of your system. What breaks first and
7:54what you would do about it. For example,
7:56the follows database becomes the
7:58bottleneck at 10 times the traffic. So
8:00we would add a cache in front of it.
8:03Then at the end you can summarize what
8:05you built in 30 to 60 seconds.
8:08So these are the six steps you need to
8:10keep in your mind when you are under
8:12pressure in the interview. Now we will
8:15use this framework on every problem we
8:17solve from here onwards.
8:20In the last video, I gave you the
8:22six-step framework and the first step
8:24was to clarify the requirements from the
8:26interviewer. These first five minutes of
8:29the interview are very important. If you
8:32don't ask the right questions, you will
8:34probably end up building the wrong
8:36system and that will surely be the end
8:38of your interview process. If the
8:41interviewer says that you need to design
8:43a photo sharing service, then you need
8:45to ask, "What kind of photo sharing
8:48service?" Because Instagram means
8:51billions of small images and a feed that
8:54loads in half a second. Flickr means
8:57fewer users will be uploading images.
9:00But these images will be huge in size
9:03and the images don't get compressed. To
9:06be honest, interviewers by default ask
9:09very vague questions because they want
9:12to see how clearly you can think.
9:15One thing I want to make absolutely
9:17clear when I say you need to ask
9:19questions, I do not mean that you will
9:22bombard the interviewer with a lot of
9:24questions. I have seen candidates ask 15
9:28memorized questions one after another in
9:31those five minutes. And these memorized
9:33questions shouldn't even be asked.
9:37Before you ask any question, you need to
9:39ask yourself, will the answer change my
9:43design? A good question creates a path
9:46for you. If the answer is A, then you
9:49design one way. If the answer is B, then
9:52you design in a different way. If the
9:55design is not dependent on the
9:57interviewer's answer, then don't ask
9:59that question at all. Just state your
10:02assumptions for the design and move on.
10:05You can quickly check with the
10:07interviewer if they are okay with your
10:09assumptions.
10:11Let me give you some concrete examples
10:13of questions that candidates ask. First
10:16question is, should I use SQL or NoSQL?
10:22Now, this question is bad because the
10:24database choice depends on what kind of
10:27data you are storing and how users will
10:30access your data. It's not a decision
10:33that the interviewer can make for you.
10:36It is your job to decide which database
10:38to use based on the requirements of your
10:41system. Let's see another question. Do
10:45we need the system to be scalable and
10:47highly available?
10:49This is also a rubbish question because
10:52if the interviewer says yes, then it
10:54doesn't add any information. So don't
10:57ask whether the system should scale. You
11:00should ask how many users are there and
11:03how fast the user base is growing. And
11:07let me tell you the biggest mistake.
11:10People ask a very good question but then
11:12they ignore the information that the
11:15interviewer gave them when they actually
11:17design the system.
11:19For example, the interviewer said, "Our
11:22system has 10,000 users, but then you
11:25ignored this information and created a
11:28massive distributed system.
11:30Yes, your massive distributed system is
11:33great, but we don't need this
11:35distributed system because we only have
11:3710,000 users.
11:40That's enough for bad questions.
11:43Now, let's see some good questions. The
11:46goal of a good question is to gather
11:48functional and non-functional
11:50requirements.
11:51Functional requirements are easy. You
11:54can directly ask the interviewer what
11:56this system is supposed to do. and
11:59interviewers generally describe the
12:01system for you.
12:03Let's see the non-functional requirement
12:05side. If you don't remember,
12:08non-functional requirement means how
12:10well the system should behave.
12:13There are four good questions that can
12:15take you a long way and those are how
12:18many users and how fast is that growing?
12:22Do people read more or write more?
12:26What data can we not afford to lose?
12:30How fast should the important actions in
12:32the system feel? In other words, what
12:36should be the latency of important
12:38actions?
12:39And when you ask for numbers, the
12:41interviewer will often ask you to decide
12:44the numbers. This means that the
12:47interviewer wants to see whether you can
12:49pick a defensible number yourself.
12:52If you are giving some numbers to the
12:54interviewer, you should always give the
12:56reasoning behind those numbers. For
12:59example, you should say this to the
13:01interviewer.
13:03This is a consumer photosharing app. So,
13:06let's say we have 10 million daily
13:08active users and people scroll a lot
13:10through the app, but they don't post
13:12very frequently. So, it is a read heavy
13:15system. Does that sound reasonable?
13:19And if the interviewer says it is
13:20reasonable, you go ahead with those
13:22numbers.
13:24Now, let me show you a set of good
13:26questions for one of the problems. Let's
13:29say the question is, design a ticket
13:32booking system like ticket master.
13:35Question one, are we only booking
13:38tickets or do we also need to handle the
13:40event organizers who create events? The
13:43answer decides the scope of the system.
13:47Question two, how many people show up
13:50when a big event goes on sale?
13:53Say the answer is 10 million.
13:56This decides the scale of our system.
13:59Question three. When one user starts
14:02checkout for one seat, does that seat
14:05become unavailable to everyone else? And
14:08if it becomes unavailable, then for how
14:11long? The answer to this question
14:14decides the hardest part of the design.
14:17how we hold the seats, the locks that we
14:19need to apply on the seats, and the
14:22timers that release the locks.
14:25Question four, do users search for
14:28events on our app and then book the
14:30ticket or do users arrive with a direct
14:33link for booking.
14:35The answer decides the features of our
14:37system.
14:39You see, we asked four questions here
14:42and we got to know about the scope of
14:44the system, the scale of the system, and
14:48the features of the system.
14:51Let's take a look at our first problem.
14:53The interviewer says, "Design a URL
14:56shortener like bit.ly." Basically, a
15:00user past a long link and the service
15:02returns a short and neat link back to
15:04the user. This is actually a very useful
15:07product because most of the links we
15:10deal with are long and not very neat.
15:13If you have a URL like this, then you
15:16wouldn't like to share it as it is. If
15:19you can convert this URL to something
15:21shorter like this, then it is sharable
15:25and much more useful. Now, anyone who
15:28clicks the short link gets redirected to
15:31the long link and that's why they land
15:33on the original page.
15:36It sounds almost too simple for an
15:38interview and that is exactly why
15:40interviewers love this question. So,
15:43let's apply our six-step framework on
15:46this problem.
15:48Step one, clarifying requirements.
15:51You need to only ask questions whose
15:53answers change the design.
15:56I would ask three questions here. First,
16:00can users pick their own custom short
16:02links? For example, can codecloud pick a
16:06branded short link with the word
16:07codecloud in it instead of a random
16:10code. If custom short links are allowed,
16:13we need to change how codes get created.
16:16So, this question can change the design.
16:20Let's say the interviewer says that we
16:22don't allow custom links.
16:25The second question I would ask is, do
16:27the short links created by us ever
16:29expire or do they live forever?
16:33Because if these links expire after a
16:35certain time, it means we need to do
16:38cleanup work and extra checks on every
16:40click.
16:42Let's say the interviewer says links
16:44live forever.
16:46The third question I'd ask is, do we
16:49need analytics for the links?
16:52basically a service which tracks how
16:54many times each link was opened. Let's
16:58say the interviewer says analytics is
17:00nice to have but not required.
17:03Keep this answer in mind because we will
17:06discuss this in a later part of the
17:08video in a surprising situation.
17:11So after getting answers to your
17:13questions, we repeat the scope of our
17:16system very clearly in front of the
17:18interviewer. We need to create a short
17:21link that redirects to the original
17:23link. We are not allowing custom links
17:27and there is no expiry date on the links
17:30our system generates
17:32and analytics is good to have so we can
17:35work on it if we have some spare time.
17:38The second step is to do back of the
17:40envelope estimation and we only try to
17:43estimate numbers that actually decide
17:46something in our system. Question one
17:49is, how many new links are created per
17:52day? Let's assume we create 1 million
17:55links per day. 1 million sounds big, but
17:59if you spread this number over a day, it
18:02is about 12 new links per second. And
18:06any database can handle 12 writes per
18:08second.
18:10Question two, how many clicks will your
18:13short links receive?
18:15The short links that we create exist to
18:17be shared with external users and every
18:20link can get tens or hundreds or even
18:24thousands of clicks. A reasonable
18:27assumption is a thousand clicks for
18:29every link created.
18:32These numbers give a big hint to you.
18:35You should notice that for every link
18:37you create, you will end up with 1,000
18:40clicks on it. Which means our system is
18:43massively redheavy.
18:45Therefore, we need to work on the read
18:48path where users click and we need to
18:51redirect them to the original link.
18:54And question three, how many links will
18:57we ever store?
18:59A million a day for 10 years is about
19:023.6 billion links.
19:05Now, we move to step three, which is
19:08defining the API of this system.
19:11To begin with, two API calls are enough.
19:16The first API call creates a short link
19:19for the user. The user sends the long
19:22URL and they get back a short code. The
19:27second API call is the redirect. When a
19:31user clicks on a short URL in the
19:33browser, the browser asks for the real
19:36URL and we send the browser to the long
19:40URL.
19:41And if you notice these two API calls,
19:45then it is clear that we actually need
19:47to store one table that maps a short
19:50code to a long URL.
19:53And this is actually our data model.
19:56Now we also need to decide which
19:59database would be good to store this
20:00data. A weak answer here is we need
20:04scale. That's why no SQL.
20:08This sentence doesn't tell anything to
20:10the interviewer. The strong answer comes
20:13from the access pattern. In our system,
20:16we are looking to access one large link
20:19from a small link. It's like a onetoone
20:22mapping. This is the simplest data shape
20:26that exists, a key and a value. And we
20:30are not looking for any joins, no
20:33operation that touches many rows in the
20:35database.
20:37A plain SQL database like Postgress with
20:41an index on the short code can handle
20:43this comfortably. So that is where we
20:46start.
20:48Step four, we will start with a
20:50high-level design. When a user sends a
20:53request to create a short URL, the
20:56request goes to an application server.
20:58The server creates a short URL or code
21:02and then the server stores the long URL
21:05and short URL in the database.
21:08Then the server shares this short URL
21:10with the user which they can share with
21:13the general public. Now anyone who is
21:16accessing this short link, they will
21:18send the request to the application
21:20server to fetch the real URL. The server
21:23finds the long URL in the database and
21:26returns the long URL to the user.
21:29Now you say one thing to the interviewer
21:32very clearly.
21:34This simple version already works. So
21:37now let's find the hard part.
21:40We said the server will create a short
21:42URL or code. But how exactly will we
21:46create that? If you think about it, we
21:50have two important constraints. The code
21:53we generate must be short and it must
21:56never repeat. If two different links get
21:59the same code, then it will be a huge
22:02mess because then you will have two long
22:06URLs for which you have one short URL.
22:11Now before I show you the two options,
22:14pause this video for a moment and think.
22:17How would you generate a code that is
22:19short and that never repeats?
22:22This is exactly the question the
22:24interviewer is watching you think
22:26through.
22:28Okay, let me show you the two options
22:31that we can use to generate the short
22:33code. The first option is hashing. We
22:37take the long URL and pass it through a
22:40hash function and we get a string of
22:43characters.
22:45We can pick the first seven characters
22:47for the code and this will become part
22:50of our URL.
22:52A hash function converts any input into
22:55a fixed jumble of characters. And the
22:58good thing about hash functions is that
23:01if you provide the same input twice, it
23:04creates the same output.
23:07Basically what I want to convey is that
23:10a hash function is not creating
23:12characters randomly.
23:15If the input is the same, the output
23:18will be the same. But two different URLs
23:22when passed through a hash function can
23:24produce the same first seven characters
23:28and this is called a collision.
23:31So every time we create a code, we need
23:34to check the database first and see if
23:37this code is already taken. If yes, we
23:41can add one extra character at the end
23:44of the long URL before hashing and due
23:47to that extra character, the input
23:50changes. So the hash output changes and
23:54we get a fresh code which might not
23:57collide. Now this works but if you think
24:01it through the major problem is that as
24:04your database grows in size collision
24:07will happen more frequently because you
24:10already have too many codes in your
24:12system. And now when you try to generate
24:15a new code it might collide with a
24:18previous code and you have to make one
24:21more attempt to generate new code. The
24:25busier your system becomes, the number
24:28of collisions will increase and because
24:31a lot of collisions are happening,
24:33system will take some more time to
24:35create a short URL.
24:38Option two is counting.
24:41We can keep one global counter and every
24:44new link that arrives at your system
24:47gets the next number. The first link is
24:50one, the next is two and so on. Then you
24:55can encode this number in base 62.
24:59I will not go into the detail of how
25:01encoding works but base 62 means you are
25:05dealing with 62 characters.
25:08We normally count with 10 digits using 0
25:11to 9. If we add 26 lowercase letters and
25:1626 uppercase letters, then you have 62
25:20symbols per position.
25:22So for a string of length seven, the
25:25first position can have 62 characters.
25:28The second can have 62 characters. The
25:32third can also have 62 characters and so
25:35on. With seven characters that gives
25:38about 3 and 12 trillion possible codes
25:42and we only need 3.6 billion for the
25:46next 10 years. And the good thing is a
25:49counter never repeats. So there are no
25:52collisions and no retries no matter how
25:55full the table gets.
25:59So we compare these two approaches
26:01against our requirements. With the
26:03counter approach, we will be able to
26:05make sure that the code generated never
26:07collides. So the counter wins. But we
26:10need to present the disadvantage of the
26:12counter approach before the interviewer
26:14does. The disadvantage is that we are
26:17using a counter and a counter is easy to
26:20guess.
26:21Let me show you how someone can misuse
26:23this. Say an attacker has one of our
26:26real short links. The attacker decodes
26:29the short code back into its number by
26:32using easily available decoders. There
26:34are many decoders that can convert base
26:3662 codes back into normal numbers.
26:40Let's say for the link that the attacker
26:42has, the number comes out as 1 million.
26:46Now the attacker adds one to it and then
26:48encodes 1 million and one and gets
26:51another valid short link, a link that
26:54was never shared with them. And they can
26:57keep adding one again and again and walk
27:00through every link in our system one by
27:02one. The fix is to shuffle the number
27:06before encoding it. For example, say the
27:09counter gives us the number 45 6 7 8 9.
27:14We will not encode that number directly.
27:17We first apply a fixed secret rule to
27:19it. Something like rearrange the digits
27:22in a fixed secret order and then shift
27:25every digit up by a secret amount. So 4
27:285 6 7 8 9 might become 07281
27:349. And only then do we encode it in base
27:3862.
27:39Notice that while shuffling the number,
27:42every step in the rule is reversible. So
27:44two different numbers can never shuffle
27:46into the same result. This makes sure
27:49that the uniqueness of the counter
27:50remains intact. So the codes look random
27:53from outside and the counter has a
27:55second weakness. If two requests arrive
27:58at the same time, then both request one
28:02and request two will try to read the
28:04counter at the same time. And because
28:08none of these two requests has actually
28:10updated the counter yet, both walk away
28:14with the same number and both encode to
28:17the same code.
28:19We now have two links with same code. So
28:23we need to make sure that the counter
28:25stays correct even when multiple
28:28requests from multiple users try to
28:31access it. So here is the summary of the
28:33design we did till now. We store one
28:36table that maps short codes to long URLs
28:39in a Postgress database. We create a
28:42link using a global counter. We shuffle
28:44the counter number and then encode it in
28:47base 62.
28:49And seven characters gives us trillions
28:51of codes with zero collisions.
28:54And we index the short code so that we
28:57can search it fast in the table.
29:00This design is good for the writing part
29:02where we are actually creating the short
29:04links. But remember we said that our
29:07system is read heavy a th00and to one.
29:10What happens when a celebrity posts one
29:12of our links and a million people click
29:14it in a short span of time?
29:17So if a celebrity posts one of our short
29:19links and now a million people are
29:21clicking on this link in a short span of
29:24time, we should be ready to absorb that
29:27traffic.
29:29First, let's take a look at a normal
29:31day. In step two, we estimated a
29:34thousand clicks for every link created,
29:38and we create 1 million links per day.
29:42So, that is about a billion redirect
29:45requests per day.
29:48If you spread them evenly over the day,
29:51that is more than 11,000 database reads
29:55per second.
29:57A well-tuned Postgress database might be
30:00able to do this, but 11,000 reads per
30:03second is already a lot of work for one
30:07database machine. And you should notice
30:10that every one of those reads from the
30:12database is asking a question whose
30:16answer never changes.
30:19So if we get a thousand queries for the
30:22same short URL,
30:25our database is replying with the same
30:28long URL 1,000 times.
30:32And honestly, that should feel wasteful
30:35to you.
30:37Keep this in mind because this can be
30:40easily fixed.
30:42But first, let's add the celebrity to
30:44our system.
30:47A million clicks arrive in the first
30:49hour. And if the link really goes
30:52global, it can be a 100 million clicks
30:56in a single day.
30:58And the painful part is that all of
31:01those requests are asking for the same
31:04short URL that the celebrity posted.
31:08This situation, where one thing goes
31:11viral and is accessed by many, is called
31:14a hotkey.
31:16and it is the signature failure of any
31:19readheavy system.
31:22So this is step five, the deep dives. We
31:25found the component where our problem is
31:28actually hard.
31:30Pause for a moment and think how can we
31:33fix this problem.
31:36Let's think about what we need. We don't
31:39want to send a million same queries to
31:42our database. So, we need a component
31:45that can store hotkeys.
31:47By hotkeys, we mean famous links that
31:50are getting clicked more frequently.
31:54That component is called a cache.
31:57And in our example, we will use Reddus,
32:00a popular cache that answers in under a
32:04millisecond.
32:06So when a user clicks on a short URL,
32:09the request goes to the application
32:11server and the server first checks with
32:14Reddus.
32:16If the cache has the URL, we call it a
32:19cache hit and we can return the long URL
32:23to the user. The request doesn't even go
32:27to the database.
32:30If the user requests answer is not in
32:32the cache, we read it from the Postgress
32:35database once and then put it into the
32:39cache and every user after that can
32:43access that link from the cache. So in
32:46case of a viral link, the first user
32:48reads from the database and then that
32:50data gets stored in the cache and the
32:52remaining millions of clicks are served
32:54from the cache. Now normally a cache
32:58comes with a famous headache and it is
33:00called staleness.
33:02Staleness basically means inconsistency
33:05between the cache and the database. It
33:08happens when the cache stores some data
33:10let's say x= 7. But then a user changes
33:13the data to x= 9 in the database. Now
33:16the cache is serving the old data 7 when
33:19we know in the database it was updated
33:21to 9. But if we look at our system
33:24carefully, a short code always points to
33:26the same long URL. We write the mapping
33:30once and we never update it. That means
33:33our cache can never serve a wrong
33:35answer. A URL shortener is a dream case
33:38for caching. And you should say this to
33:40the interviewer clearly. I can cache
33:43this aggressively because the data never
33:45changes. This one sentence shows your
33:48technical depth. But you should also
33:50mention that cache memory is limited. So
33:53Reddus removes entries that have not
33:54been used recently to make room for new
33:57ones. Popular links stay in the cache,
34:00dead links are removed from the cache.
34:02That is exactly what we want. Can we
34:05make further improvements? We can
34:07actually make two quick upgrades. First,
34:10if one link becomes so hot that even our
34:12cache gets overloaded, then we can move
34:14our top few thousand links even closer
34:16to the user. Basically, each application
34:19server can keep its own small copy of
34:22the top few thousand links in its own
34:24memory. So, the hottest links can be
34:26given out directly by the server. There
34:28is one more way to push hot links closer
34:30to the user and this is the content
34:33delivery network or CDN.
34:36A CDN is a fleet of servers sitting
34:39across different countries and
34:40continents. With a CDN, a user accessing
34:44a link from Tokyo gets its long URL from
34:47the server nearest to them instead of
34:50getting the URL from Virginia.
34:53Now comes one tricky part. When our
34:55server tells a browser, go to this long
34:58URL, there are two ways to do it. A 301
35:02redirect and a 302 redirect.
35:06301 means this link has moved
35:09permanently.
35:10A 302 redirect means go there for now,
35:14but ask me again next time you access
35:16this link. Most candidates pick 301
35:19without thinking because permanent
35:22sounds correct. Our mapping is permanent
35:24after all. But let's see what 301
35:27actually does. Once you click on a 301
35:30link, the browser remembers the answer.
35:33And the next time the same user clicks
35:35on this link, the browser goes straight
35:37to the destination URL. The browser
35:40doesn't even ask our system for the long
35:42URL. So, we actually don't know if the
35:45click happened or not. It's definitely
35:48faster for the user and less load for
35:50us. And it sounds like a pure win. But
35:54if the clicks never reach us, we can
35:56never count them. So, analytics becomes
35:59impossible.
36:00And there is a bigger problem. We lose
36:03control.
36:04If a short link turns out to point at a
36:06scam page, then we will want to kill
36:08that link. But the browsers have already
36:11memorized our answer and we cannot take
36:13it back. A 302 redirect keeps every
36:18click flowing through our service. Yes,
36:21we have to spend more to answer queries,
36:23but in exchange, we keep our analytics
36:25and control so that we can kill any link
36:28in the future.
36:30One thing I wanted to mention here is
36:31that the exact redirect behavior of the
36:33browsers also depends on the browser
36:36config and the headers we send. But what
36:39actually matters in the interview is the
36:40reasoning. If the business ever wants
36:43data analytics on clicks or they want
36:45the power to disable a link, I will
36:47choose the 302 redirect due to the
36:50reasons we just discussed.
36:53And now the last step of our framework
36:55which is bottlenecks and scaling. Here
36:58we need to do the critical analysis of
36:59our system. I will ask two questions for
37:02myself. What component of the system
37:05breaks first and what can we actually
37:07afford to lose? For example, if the
37:10reddis cache crashes, every read
37:13suddenly lands on the database again.
37:15The system becomes extremely slow if the
37:18cache fails. But the system does not
37:20become wrong. And when the cache comes
37:22back online, it will get filled as we
37:24process queries.
37:26Say this property out loud. The cache is
37:29a performance layer, not the source of
37:31truth. Next, what data can we never
37:35lose? I am sure that we should never
37:37lose the mapping table which tracks the
37:39short to long URL mapping. If we lose
37:43one row, then that link is dead forever
37:46for everyone who has that link.
37:50So the Postgress database should have a
37:52replica and regular backups.
37:55And one more thing, the counter must
37:58never repeat a number, even after a
38:01crash.
38:03If it repeats, two links get the same
38:06code. And that is what will really break
38:09the URL shortener system.
38:13So, let me summarize the full system
38:14once in the same way you would close
38:17this in the interview.
38:20A click hits our servers. Most of the
38:23time the answer comes straight from the
38:25cache and the user gets redirected
38:28within a few milliseconds with a 302
38:31redirect so that we keep our visibility
38:35and control.
38:37We make sure our database has replicas
38:40and is continuously backed up because
38:43the mapping table can never be lost.
38:47New links are generated using the global
38:49counter and the base 62 encoding.
38:53In our system, database reads scale
38:56through caching and writes were never
38:59the problem because our system is read
39:02heavy, not write heavy.
39:06From my side, here are the key takeaways
39:09from this interview question.
39:11First, this was a readheavy problem and
39:15that's why we used caching.
39:18So, whenever you have to serve the same
39:20thing again and again to users, the
39:23caching strategy should come to your
39:26mind.
39:27Secondly, we learned how to generate
39:30unique short codes using a counter and
39:33base 62 encoding
39:36and we also looked at the hashing
39:38technique. You should remember these
39:41techniques.
39:43Third, we learned the important concept
39:46of 301 and 302 redirects.
39:50Towards the end of the interview, you
39:52can expect some follow-up questions from
39:54the interviewer. And these follow-up
39:56questions test if you can point out what
39:58exactly you will change in your design.
40:02Let's quickly see three follow-up
40:04questions.
40:05Follow-up one. Two create requests
40:08arrive at the same instant. Can they get
40:11the same code?
40:13This question attacks the counter and in
40:16short the answer is no. They should not
40:19get the same code. We have to use a lock
40:22system so that only one request can
40:25fetch and change the counter. So if
40:28request one gets access to the counter,
40:31the counter should not be accessed by
40:33request two and the counter will become
40:35available only when request one has read
40:39the value of the counter, incremented
40:41the counter and stored the new value of
40:44the counter.
40:46After these three steps are done by
40:47request one, only then can the next
40:51request access the counter.
40:55Follow-up two.
40:57That counter is one shared thing. What
41:00happens when it goes down?
41:03It's a good question because the counter
41:05is a single point of failure for us. So
41:08what we can do to improve the design is
41:11instead of asking the counter for one
41:13number at a time, each application
41:16server gets a block of 10,000 numbers in
41:19one call.
41:21For example, server 1 gets the counts
41:24from 1 million to 1,ion10,000
41:28and then server 2 gets 1,10,01
41:32to 1,20,000
41:35and so on. And then each app server can
41:39allocate these numbers to the requests
41:41on their own.
41:43Now the counter is touched rarely and
41:46even if the counter goes down for a
41:48short time it will not be a single point
41:51of failure because the servers already
41:54have a block of numbers with them to
41:56handle incoming requests.
41:59Follow-up three. We want links to expire
42:03after a certain time. What will you do?
42:07Well, this is simple because in the URL
42:10mapping table, we can add an expiry date
42:14and when somebody tries to access this
42:16link, we compare if we have reached the
42:19expiry date and if we have reached it,
42:22we will block the URL or we can say the
42:26URL doesn't exist.
42:29The trade-off is that every URL redirect
42:32now does one extra comparison with the
42:35expiry date.
42:37With this, we wrap up the URL shortener
42:40problem. I want you to take a second to
42:44process all the questions and then you
42:47can move to the next problem.
42:50Now, it's time for the first lab of this
42:52course. And don't worry if you're not
42:54feeling confident because every lab
42:57comes with hints and full solutions. All
43:00you have to do is go to the link
43:02provided in the description, then enroll
43:04in the course and click start on the
43:07lab.
43:08In this first lab, you'll run the exact
43:11URL shortener that we just designed.
43:14You'll create real short links and then
43:16send 200 requests to one of the links
43:19and watch every single request hitting
43:22the database.
43:24The lab link is in the description. Go
43:26give it a try.
43:29Let's take a look at our second
43:30interview problem. And the interviewer
43:32asks you to design a rate limiter. Now
43:35rate limiter is one of the most
43:37important component of all the modern
43:39systems like chatgbt, claude, etc. In
43:44fact, rate limiter is also important for
43:46the URL shortener we designed earlier.
43:50We know that anyone can create an
43:52account on our website and call the
43:54create API endpoint to create a short
43:57URL.
43:58Now imagine one user named Shadow signs
44:01up on our platform and then writes a
44:04small script that runs in a loop and
44:07creates 1 million API calls in 1 hour.
44:12This will create 1 million junk URLs in
44:15our system.
44:17Due to this, our database will get
44:19filled with garbage links that doesn't
44:22serve any purpose.
44:24And because the shadow user is keeping
44:27the server busy, the legitimate users
44:30might see a slow system because the
44:32resources are overutilized by shadow
44:35user.
44:36And if you notice, this user has not
44:39hacked our server. They are simply
44:42calling our API too many times.
44:45So we need a component that can actually
44:48slow down or limit the noisy users.
44:52This component is called a rate limiter
44:56and design a rate limiter is a very
44:58common interview question on its own.
45:01Basically, we need to keep an upper cap
45:04on how many API calls per user can make.
45:08And if they try to make more than the
45:11upper limit, then we don't entertain
45:13their request.
45:15So, let's apply our six-step framework
45:18on this problem. Step one is to clarify
45:21the requirements.
45:23I would ask three questions for this
45:26problem.
45:27First question is how do we identify who
45:30is making API call. We can usually
45:33identify a API request by three things.
45:37First is which account it belongs to.
45:41Second way to identify is to see which
45:44IP address it came from. Third way is to
45:48track which API key the request is
45:51carrying.
45:52Now each of these three has a problem.
45:56If we count per IP address, then one
45:59office where 300 people share a single
46:02internet connection looks like one very
46:05noisy user and we will block all of
46:08them. Also, an attacker can simply keep
46:11changing their IP address to abuse the
46:14system and IP addresses are easy to get.
46:19If we count number of requests per API
46:22key then it become niche because it only
46:25works for developers who are given an
46:28API key. Normal app users don't
46:31generally use API keys
46:34and if we count number of requests per
46:37account that we can't do anything for
46:40requests where nobody is logged in yet.
46:43So let's say the interviewer tells us
46:46that for loggedin user we need to track
46:49number of requests per account and for
46:52non-loggedin users we track IP address.
46:56My second question is what is the limit
46:59for each user?
47:01Let's agree that every user can make 100
47:05API requests per minute. And if the
47:08interviewer asks, "How did you come up
47:10with this number?" Then don't invent a
47:13number confidently.
47:15The honest answer is that you look at
47:17your real traffic first.
47:20In reality, you first check what a
47:23normal user actually does in a minute
47:26and then set the limit comfortably above
47:29that.
47:31And the third question is what should
47:33happen when a user crosses this limit?
47:36Will the extra requests wait in a queue
47:39or should we reject them straight away?
47:43Let's discuss about the queue for a
47:45moment.
47:46If a request is waiting on Q to be
47:49processed, then there are high chances
47:52the user's app has made the same request
47:54again. So if we keep a Q then we might
47:59unwantedly create duplicate requests.
48:02I think it makes sense to reject the
48:05requests if the limit exceed but we
48:08should do it politely.
48:10The user should know that they were
48:12limited and when they can try again.
48:16So we clearly state the scope of problem
48:18clearly. We allow about 100 requests per
48:23minute per user.
48:25We count number of requests by account
48:29for loggedin users.
48:31Extra requests are rejected with a clear
48:34message.
48:36And users who do not exceed limit should
48:39not even notice that rate limit system
48:41exists.
48:43The second step is to do back of the
48:46envelope estimation.
48:48And we only estimate the numbers that
48:50actually decide something.
48:53From my perspective, two numbers matter
48:56here. The first one is how much do we
48:59store per user.
49:02If we use a simple counter, we need one
49:05number and one time stamp. That is
49:08roughly 50 bytes per user. So 10 million
49:12active users is about 500 megabytes,
49:16which fits in the memory of one machine
49:19easily.
49:20Keep this 50 bytes in mind. because it
49:23will be useful later.
49:26The second number is the API calls rate
49:29because this rate limiter component
49:32checks every single request that enters
49:34our system.
49:3610 million users and each user on
49:39average makes 100 requests per day which
49:43makes total requests to be 1 billion
49:46requests a day which is roughly 12,000
49:50requests per second on average.
49:54And let's say in the busy time the
49:56traffic goes by three times. That will
50:00be 35,000 per second in the peak time.
50:04Students usually get confused here. So I
50:07want to make one thing absolutely clear.
50:11This 100 per day is basically an average
50:15of how many requests we get from each
50:18user per day. Do not confuse this with
50:21our limit. Our limit is set as 100 per
50:26minute. And this limit is for heavy
50:29users.
50:30Normal users never key the 100 requests
50:33per minute limit. In fact, they use 100
50:37requests in an entire day. Okay, let's
50:41move on. Next thing to notice is that a
50:44user's 100 requests a day do not arrive
50:47evenly. They come in a few short bursts
50:51when somebody actually opens the app.
50:54which is exactly why a per minute limit
50:56can catch abuse without ever touching
50:59normal use.
51:02Step three is defining the API and this
51:05one is very easy. A rate limiter check
51:09only one thing. It checks if this
51:12particular request is allowed or not.
51:15When the answer is no, we respond to the
51:18user with a status code 429, which means
51:22too many requests. And we also attach a
51:26retry after header. This retry after
51:29header is basically a small note that
51:32says try again in 40 seconds.
51:35This note is important because without
51:38this note, the blocked user will keep
51:40retrying again and again. And our
51:44limiter will now deal with even more
51:46traffic than before. And it helps to
51:50send two more small numbers on every
51:52successful response as well. how many
51:55requests the user has left and when
51:58their limit resets so that a good user
52:01can then slow itself down before it ever
52:04gets blocked. Now before we draw the
52:07components, there is one important
52:09question that I need you to think about.
52:12Where should this rate limit component
52:14live in overall design?
52:17This component rejects API requests. So
52:21it should sit as early as possible at
52:24the front door of our [music] system.
52:26That front door is the API gateway, the
52:30first server that every request passes
52:33through. If we place the limiter deep
52:36inside the system, let's say next to the
52:39database, then a rejected request has
52:42already traveled through half of our
52:44system without any real purpose.
52:48Step four is to do the high-level design
52:51and we start with the simplest version.
52:54We have one gateway server and in its
52:56memory we keep one counter per user.
53:00When a request from user named Allen
53:03arrives, then we check the Allen's
53:05counter. If the counter is less than 100
53:09in the current minute, we add one and
53:12let the request go through.
53:14When the current minute ends in the
53:16clock, the counter resets to zero.
53:20If the count reaches to 100, then we
53:23respond to user that request limit has
53:25been reached. Try later.
53:28This is called a fixed window technique
53:31because we are looking at clock and
53:33tracking requests for each minute and
53:36each minute is fixed window. You can't
53:39change the clock and honestly this
53:41simple version already works.
53:44So let's go and find the hard part of
53:46this problem.
53:48Here is the first problem that we will
53:50face. Say a user named Allen sends 100
53:54requests in the last second of a minute.
53:58All of the requests are allowed because
54:00the current minute has not ended.
54:03Then the current minute ends and the
54:06counter resets to zero.
54:09Now Allan sends 100 more requests in the
54:12first second of the new minute. These
54:15are also allowed because it's a new
54:17minute. So if you notice, Allen just
54:20pushed 200 requests in about 2 seconds.
54:24100 in the last second of earlier minute
54:27and 100 in the first second of the
54:29current minute. and our limiter which
54:32promised 100 per minute allowed
54:35everything because technically these
54:38were two different minutes according to
54:40the clock.
54:41The problem is how we are resetting the
54:43counter every minute. Our minute window
54:46has a sharp edges.
54:48Pause the video for a moment and think
54:51how would you count the last 1 minute
54:53more accurately.
54:56The most obvious fix is to stop using
54:58fixed minute-wise window at all and we
55:00use a technique called sliding window
55:03log.
55:04Let's make this concrete with an
55:06example.
55:07Every time Allen sends a request, we
55:10write down the exact timestamp when a
55:12request arrives.
55:14When a new request comes in, we look at
55:16our list and throw away every time stamp
55:19older than 60 seconds and count the
55:21number of requests in last 60 seconds.
55:25Let's say right now we have 94 requests
55:28sitting inside that last minute and
55:30Allen is still under the 100 requests
55:33limit. So the new request comes and we
55:36add its timestamp to the list as well
55:38and this request goes through.
55:4110 seconds later Allen sends another
55:43request and we do exactly the same
55:45thing. But now the last 60 seconds means
55:49something different because time has
55:51moved forward and some of those old
55:53timestamps have dropped out of the
55:55window of 60 seconds.
55:58So the window slides forward with every
56:00single request and checks only last 60
56:03seconds.
56:05To summarize, we remember the timestamp
56:08of every request and when a new request
56:10arrives, we count how many timestamps
56:13fall inside the last 60 seconds. We
56:16reject request if we have reached 100
56:18requests quota. We don't have fixed
56:21window anymore. Last 60 seconds window
56:24moves as new requests arrive.
56:27But this approach costs us a lot. Our
56:29limit is 100 per minute. So for an
56:32active user we are storing 100
56:34timestamps about 2 and a half kilobytes
56:37per user instead of 50 bytes.
56:4010 million users now needs around 25 GB
56:44of memory. And notice this cost is tied
56:47directly to the API limit. So if the
56:50interviewer had said 10,000 requests per
56:52minute, this option would be not
56:54feasible at all.
56:57Now the last option to track API
56:59requests is called a token bucket. This
57:02token bucket approach is what Stripe,
57:05GitHub, and most API gateways actually
57:08use for tracking API calls. Let's see
57:11how it works.
57:13Every user gets a bucket that holds 100
57:16tokens and every request from user takes
57:19one token out of it and we will keep
57:22filling the bucket at rate of 100 tokens
57:24per minute which is approximately 1.67
57:28tokens per second. If user doesn't make
57:31any API call the bucket will remain at
57:34100 and we don't need to fill. If the
57:38bucket is empty, we will reject the
57:40request. So, let's take Allen again and
57:43watch this work. Allan drains all 100
57:47tokens in 2 seconds. And then Allen has
57:51to slow down because the bucket only
57:53fills about 1.67
57:56or approximately two tokens per second.
57:59So, from this point on, he can make
58:01about two calls per second. And he is
58:04never fully locked out from the system
58:07because each second he gets two tokens.
58:11So let's be precise about what we are
58:13promising to our users in this approach.
58:16A token bucket does not give a hard
58:19ceiling of 100 requests inside every
58:2260-second window. User can also use 100
58:26tokens in one go if bucket is full and
58:30then bucket gives a sustained rate of
58:321.67 tokens per second.
58:36And this approach is different from the
58:38fixed windows problem because here the
58:41burst is a number we chose on purpose,
58:44not an accident of where the clock
58:46happens to reset. And if we want a
58:48smaller burst, we make the bucket
58:51smaller. For example, we can say bucket
58:54size is 20 tokens without touching the
58:57sustained rate of 1.67 tokens per
59:00second.
59:02What we store per user is only the
59:04tokens left in the bucket and the time
59:07of the last refill so that we can refill
59:09the bucket continuously.
59:12If we look at the memory needed to store
59:14these info is again just 50 bytes.
59:19Now you need to put the honest
59:20comparison of all these approaches in
59:23front of the interviewer. The sliding
59:25window approach is the only one of these
59:27three that gives an exact ceiling on
59:30every rolling 60 seconds. But we are
59:33rejecting it because we need to store a
59:35lot of time stamps and it needs lot of
59:37memory.
59:39We are choosing the token bucket for two
59:41different reasons. First, it lets us set
59:45the continuous rate at which we fill the
59:47bucket. Due to this continuous filling
59:49of bucket, a user is never fully locked
59:52out of system.
59:54They still get two calls per second. And
59:57if the bucket is full, they can still
1:00:00spend all 100 tokens in one go if they
1:00:03wish to.
1:00:05Second, the bucket already knows how
1:00:08many tokens are left, which is the
1:00:10number we can send back to our users in
1:00:12the response headers.
1:00:15So let's see the summary of the design
1:00:16we have till now.
1:00:19The rate limiter sits at the API gateway
1:00:22which is the front door of our system.
1:00:25We count per account for loggedin users
1:00:28and per IP address for non-loggedin
1:00:31traffic.
1:00:32Every user gets a token bucket which
1:00:35gives them a sustained 100 requests a
1:00:37minute with a burst allowance.
1:00:40And when a user runs out of API
1:00:42requests, we return 429 error with a
1:00:46retry note.
1:00:48And this design works beautifully on one
1:00:51gateway server, but real system often
1:00:54runs more than one gateway servers.
1:00:57So what happens to our bucket when the
1:00:59Allen's requests start landing on more
1:01:02than one gateway?
1:01:04Now in a real production system, we
1:01:07would normally run multiple API gateways
1:01:10to handle requests behind a load
1:01:12balancer.
1:01:14Also having one API gateway is also a
1:01:18single point of failure. So let's say in
1:01:21our case we run two API gateways to
1:01:25track API requests made by users. Each
1:01:28gateway store buckets in its own memory.
1:01:32Now Allen makes multiple API calls and
1:01:35the load balancer splits traffic and
1:01:38sends some requests to gateway one and
1:01:40some requests to gateway 2.
1:01:43Can you spot the problem here? Each
1:01:46gateway sees only half of Allen's
1:01:48requests and each one is holding its own
1:01:52separate bucket for Allen.
1:01:54So Allen effectively has two buckets now
1:01:57and he can make more API calls. Add a
1:02:01third gateway and he can make even more
1:02:03calls.
1:02:05Basically, none of the gateways know how
1:02:08many calls did Allen make because both
1:02:10gateways will be storing different
1:02:12numbers.
1:02:14The fix is to move the buckets out of
1:02:16the gateways memory and put them in one
1:02:19shared place that every gateway can talk
1:02:22to. This shared place should be fast.
1:02:26Therefore, we can use Reddus for doing
1:02:28this job. All the buckets will be stored
1:02:31in Reddus. Now every gateway checks
1:02:34Reddus to determine if the user is
1:02:36eligible to make API call.
1:02:39But we need to be careful here because
1:02:42there is one more problem inside this
1:02:44fix which interviewer may ask. So the
1:02:48question is what happens if some of the
1:02:50Allen's API requests reach to both API
1:02:54gateways and both API gateways try to
1:02:57change the data in Allen's bucket at the
1:03:00same time.
1:03:02Let's see what we can do. Now accessing
1:03:06a token bucket is not one action. It is
1:03:09three different action.
1:03:11First you read how many tokens are left.
1:03:15Calculate how many tokens we need to add
1:03:17based on time and then write back the
1:03:20new value of tokens left. If both
1:03:23gateways do these three steps at the
1:03:26same moment, both of them read Allen's
1:03:28last remaining token. Both of them think
1:03:31there is a token available and both of
1:03:34them allow the API request.
1:03:37The fix for this problem is called an
1:03:39atomic operation.
1:03:41We have to ensure that all three steps
1:03:43are done and we consider these three
1:03:46steps as one operation.
1:03:49When one request access the bucket, we
1:03:52lock this bucket so that these three
1:03:54steps can be done and no other request
1:03:57access this bucket while this operation.
1:04:00So how does this lock works? Instead of
1:04:04our gateway doing these three steps one
1:04:06by one over the network, we hand all
1:04:09three steps to Reddus as one small
1:04:11script. In Reddus, these are called Luis
1:04:14scripts. And Reddus runs that whole
1:04:17script in one go. And while it is
1:04:20running, no other gateway can touch
1:04:22Allen's bucket.
1:04:24Now, it does not matter how many
1:04:26gateways we run because the bucket is
1:04:29only ever changed by one request at a
1:04:32time.
1:04:34And now, the last step of our framework
1:04:36is bottlenecks and scaling. Let's do the
1:04:39critical analysis of our system. First,
1:04:42a quick check on Reddus itself. One
1:04:45Reddus instance can handle around
1:04:48100,000 operations per second. And from
1:04:51our requirement, we know that we need
1:04:5335,000 operations per second. So, one
1:04:57instance is enough for now with room to
1:04:59grow.
1:05:01Every API request now makes one extra
1:05:04trip to Reddus, which costs around 1
1:05:07millisecond if Reddus is sitting close
1:05:09to our gateways. And that word close
1:05:12matters a lot here. If your gateway is
1:05:15in one region and Reddus is in another,
1:05:18that 1 millisecond becomes 50
1:05:21milliseconds. And now your rate limiter
1:05:23is the slowest thing in your entire
1:05:25system.
1:05:271 millisecond is okay, but 50 is not.
1:05:32But the most important question is what
1:05:34happens if Reddus goes down? Our API
1:05:38gateways cannot count anything. Now here
1:05:42we have to choose between two failure
1:05:44modes and this choice is a classic
1:05:47interview moment. The first option is
1:05:50fail open. Fail open means if we cannot
1:05:53count we let everyone through the API
1:05:56gateway. The product keeps working and
1:05:59we accept the risk of abuse for a few
1:06:02minutes.
1:06:03Second option is fail closed. Fail
1:06:06closed means that if we cannot count, we
1:06:09block everyone. Nobody's request is
1:06:12entertained until we get the Reddus back
1:06:15online.
1:06:17Which of these choices is correct? It
1:06:20depends on kind of system we are
1:06:22protecting. For a normal product API, we
1:06:26should allow all users because blocking
1:06:29every real user is worse than allowing
1:06:31one attacker for a few minutes. One of
1:06:35the example is Stripe. Stripe says that
1:06:38their API stays functional if the rate
1:06:40limiter store goes down. But for a
1:06:43sensitive endpoint like login endpoint
1:06:46where the rate limiter is actually
1:06:48stopping users from password guessing
1:06:50attacks, closing the system for all
1:06:53users or fail closed can be the safer
1:06:56choice.
1:06:57And if red is tied because your system
1:07:00is already under a heavy load from
1:07:02users, then allowing all users to send
1:07:05lot of requests straight to your servers
1:07:08can create troubles for your system. So
1:07:11say this trade-off clearly to your
1:07:13interviewer. So let me summarize the
1:07:16full system once. In the same way, you
1:07:19will close this in real interview.
1:07:22The rate limiter lives at the API
1:07:24gateway which is the front door of our
1:07:26system.
1:07:27We count per account for logged in users
1:07:31and per IP address for anonymous
1:07:33traffic. Every user gets a token bucket
1:07:37about 50 bytes. And we are refilling
1:07:39this bucket at about 1.67 tokens per
1:07:43second. That is a sustained 100 requests
1:07:46a minute with a burst allowance on top.
1:07:50The buckets live in Reddus which is
1:07:52shared by all the gateways and each
1:07:55check runs as one small atomic script.
1:07:58So the count stays correct no matter how
1:08:01many gateways try to access same bucket.
1:08:05When a user crosses the limit we return
1:08:07429 with the retry after note and if
1:08:11reddis fails we fail open if security is
1:08:15not the concern. From my side, here are
1:08:18the key takeaways from this interview
1:08:20question. First, a rate limiter belongs
1:08:24at the front door of the system. We
1:08:26should reject useless work before it
1:08:29becomes work. Second, remember the token
1:08:32bucket technique. It is small and it
1:08:35lets you set the sustained rate and the
1:08:37burst as two separate numbers, which is
1:08:40how real API limits are actually
1:08:42published.
1:08:44And third, the most important lesson.
1:08:47Local counters lie in distributed
1:08:49systems. Whenever multiple servers are
1:08:52counting the same thing, the count must
1:08:55live in one shared place and the update
1:08:58must happen as one atomic step. Keep an
1:09:02eye out for this pattern because it is
1:09:04coming back. When we make sure the same
1:09:07concert seat is never sold to two people
1:09:10and when we make sure the same driver is
1:09:13never sent to two riders, it is going to
1:09:16be this same problem in a new costume.
1:09:20Towards the end of the interview, the
1:09:21interviewer can probably cross question
1:09:24and ask some tricky questions for some
1:09:26of the parts of our design.
1:09:28So the interviewer wants to see what
1:09:30changes you will make to the design
1:09:32based on the questions without throwing
1:09:35the whole design away. Let's look at
1:09:38three such questions.
1:09:40Question number one. You assumed 100
1:09:43requests a minute as the limit, but 100
1:09:46API requests per minute cannot be the
1:09:49right limit for every API.
1:09:52How will you handle that? And to be
1:09:54honest, this is a good question because
1:09:57we might have different limits for
1:09:59different APIs. For example, if users
1:10:03are just reading the URL, the limit
1:10:06might be 10,000. But if they are
1:10:08creating a URL using API, then the limit
1:10:11might just be 100 because creating
1:10:14something takes a lot of resources
1:10:17comparatively.
1:10:18and login API would have a completely
1:10:21different limit and it will be the
1:10:24strictest of all. If you make three API
1:10:27calls backto back, you might be
1:10:30perceived as a bad actor. So the limit
1:10:33is not one number sitting in our code.
1:10:36Instead, we keep a small set of rules.
1:10:40Different rules apply to the login
1:10:42endpoint API. Different rules apply to
1:10:45the create URL API. Different rules
1:10:48apply to the read URL API.
1:10:52When any request arrives, the gateway
1:10:55looks up the relevant rule and uses the
1:10:57right bucket.
1:10:59Question number two, your system is now
1:11:02taking 1 million API requests per
1:11:05second. Is one Reddus still enough?
1:11:09The answer is no. And we should say that
1:11:12clearly. One Reddus handles around
1:11:15100,000 operations per second. So for
1:11:19one million requests per second, we will
1:11:21roughly need around 10 Reddus instances.
1:11:25And the good news for us is that you can
1:11:27divide rate limiting very cleanly
1:11:30because Allen's bucket has nothing to do
1:11:32with John's or anyone else's bucket. So
1:11:35we can easily run several Reddus
1:11:37instances and we decide which Reddus
1:11:40holds which user data.
1:11:43Every request for Allen lands on the
1:11:45same Reddus, maybe Reddus one, so that
1:11:49the count stays correct and no Reddus
1:11:52instance ever has to talk to another
1:11:54one. But there is one issue that we
1:11:57should think about. Let's say Alan has
1:12:00reached his limit of 100, but he is not
1:12:03stopping. He is continuously sending the
1:12:07extra requests. And every time he is
1:12:10sending a request, we confirm with the
1:12:12Reddus bucket if he is eligible to make
1:12:15an API call. So Allen is still keeping
1:12:19the Reddus busy. So if Alan hammers us
1:12:22at 50,000 requests per second, then we
1:12:26will be making 50,000 calls to Reddus to
1:12:30check if this API call is valid.
1:12:33that keeps Reddus busy even though we
1:12:36are not allowing more than 100 calls a
1:12:39minute. Let's see the last question.
1:12:43Every API request now makes a network
1:12:45call to Reddus to check the limit. Can
1:12:48you avoid this network call? Well, the
1:12:51answer to this question is yes, we can
1:12:53avoid it. And some large companies
1:12:56actually do this. For example, what
1:12:59Stripe does is that they keep a small
1:13:01counter inside each API gateway's own
1:13:04memory. And then this counter syncs with
1:13:07Reddus every few hundred milliseconds
1:13:10instead of asking Reddus on every single
1:13:12API request.
1:13:15And this local counter also fixes the
1:13:17problem we just discussed because once
1:13:20the gateway knows Allen is blocked, the
1:13:23gateway can reject his requests straight
1:13:25away instead of making a network call to
1:13:28Reddus and confirming from Reddus.
1:13:31The trade-off is that for those few
1:13:34hundred milliseconds where the gateway
1:13:36has not synced with Reddus, the limit
1:13:38goes slightly loose.
1:13:40We don't know about the exact limit
1:13:42right now because we are not
1:13:44communicating with Reddus for a short
1:13:46period of time. This is it for the rate
1:13:49limiter problem. Take a second to
1:13:52process these three answers and then we
1:13:54can move on to the next problem.
1:13:57It's time for the next lab. In this lab,
1:14:00you will place a rate limiter in front
1:14:02of an API and watch it apply a limit of
1:14:0510 requests per minute. If you try to
1:14:07make more than 10 requests, you will be
1:14:09rejected. The lab link is in the
1:14:12description. Go try it yourself.
1:14:16Let's now take a look at our next
1:14:17interview question. The interviewer says
1:14:20that you need to design a notification
1:14:22system. So, first let's be absolutely
1:14:25clear. What does notification system
1:14:27actually do? And to be honest, it's very
1:14:30obvious because we all use smartphones
1:14:32and get notification from Uber, Amazon,
1:14:36Gmail, Slack, and many other apps. You
1:14:39might have got one notification for this
1:14:41YouTube video as well. If you're a
1:14:43subscriber
1:14:45on a high level, we can say that when
1:14:47some event happens inside the system,
1:14:50then we have to send a nudge to a
1:14:52particular user who should know about
1:14:54this event. For example, your payment
1:14:57goes through, you get a notification.
1:15:00Someone replies to your comment and then
1:15:02you get a notification.
1:15:04Now, one simple thing companies can do
1:15:07is send the updates to the app in your
1:15:09phone and when you open the app, then
1:15:12you get the notification.
1:15:14But most of the time, you might not open
1:15:16the app on time. So, we can't depend on
1:15:19user opening the app or website. So we
1:15:23need to notify them outside the app and
1:15:25we can do that in four different ways.
1:15:29First we can send a push notification
1:15:32lighting up users phone screen. Second
1:15:35we can use an SMS.
1:15:38Third we can use email and last is as a
1:15:43small red notification dot waiting
1:15:45inside the app when you open the app. To
1:15:48summarize notification system we can say
1:15:51that when event happens on one side the
1:15:54right user gets the right message on the
1:15:57right channels.
1:15:59This problem looks like a small side
1:16:01service but it contains some system
1:16:03design pattern that we will reuse in
1:16:06almost every problem and that is exactly
1:16:09why interviewers love this question.
1:16:12So now let's apply our six-step
1:16:15framework on this problem. Step one is
1:16:18to clarify the requirements and remember
1:16:21that our aim is to get functional and
1:16:23non-functional requirements of this
1:16:25system by asking minimum number of
1:16:27questions. I would ask four questions
1:16:30for this problem. First question is what
1:16:34are these notifications for? Because a
1:16:37product usually sends two very different
1:16:39kinds of notifications.
1:16:41We have transactional notifications that
1:16:44we send when a payment goes through or
1:16:46we share a login code or something
1:16:48similar. And then there are marketing
1:16:51notifications like a flash sale is live
1:16:54or sale ends in 3 hours.
1:16:57Let's say the interviewer says that we
1:16:59need both kind of notifications.
1:17:02Then interviewer is basically expecting
1:17:04us to build one central notification
1:17:07system that can take care of all the
1:17:09different needs our product require.
1:17:12My second question will be which
1:17:14channels do we send notifications to?
1:17:17Let's say the interviewer says four
1:17:19types of notifications are needed that
1:17:22includes push notification, SMS,
1:17:25email and inapp notifications.
1:17:29Then my third question will be do
1:17:32transactional and marketing
1:17:33notifications need to reach the user
1:17:35equally fast.
1:17:37I will ask this because two types of
1:17:39notifications have very different
1:17:41patience levels. A login code has to
1:17:44reach the user. Let's call our user Alan
1:17:47while he is still staring at the screen.
1:17:50So transactional notifications need to
1:17:53be delivered within few seconds.
1:17:55But for a flash sale notification, we
1:17:58might be able to afford slight delay for
1:18:00marketing notifications.
1:18:02So if we have a few seconds of headroom,
1:18:05then we are allowed to accept the work
1:18:07first and do the actual sending a moment
1:18:10later. And that freedom is going to
1:18:13shape our design. And the fourth
1:18:16question is the most important one. Can
1:18:19we lose a notification?
1:18:21And can we send the same notification
1:18:23twice?
1:18:25The interviewer says losing a
1:18:26notification is bad, but sending the
1:18:29same notification twice is even worse.
1:18:33This makes sense because if Alan makes a
1:18:35payment and receives two payment SMS,
1:18:38Allen will think he has been charged
1:18:40twice for the same thing. So sending it
1:18:43twice does make it worse.
1:18:46And one important clarification you
1:18:49should ask from interviewer.
1:18:51Do users get notification preferences?
1:18:54By user preference, we simply mean if
1:18:57our users have ability to switch off
1:18:59marketing notifications. But of course,
1:19:02important notifications like payment
1:19:04cannot be turned off. Let's say the
1:19:07interviewer says yes to user preference
1:19:10because in some countries they have law
1:19:12that anyone can choose to opt out from
1:19:15marketing messages. So before moving on
1:19:18to next stage of interview, we state the
1:19:20scope of problem very clearly. The
1:19:23functional requirements say what the
1:19:25system must do. Our notification system
1:19:29takes one event and it delivers it on
1:19:31four channels and it will respect users
1:19:34preferences. That means users can turn
1:19:37off marketing notifications.
1:19:40The non-functional requirements say how
1:19:42well the system must behave. We
1:19:45mentioned to interviewer that a small
1:19:47delay is acceptable. We try not to lose
1:19:50notification and the user should ideally
1:19:53never see the same notification twice.
1:19:56And notice that we have used the word
1:19:58ideally because as we will see later in
1:20:01this problem, guaranteeing only one
1:20:04notification is impossible. And this
1:20:07will be the hardest part of this whole
1:20:09design.
1:20:13The second step is back of the envelope
1:20:15estimation. And the first thing I will
1:20:18do here is ask the interviewer for the
1:20:20scale. How many notifications per day we
1:20:23are looking at? And is the traffic
1:20:25steady or it spikes during certain time
1:20:28of the day. Let's say the answer is 10
1:20:31million notifications per day. And if
1:20:34these 10 million notifications were
1:20:36spread evenly across the day, that is
1:20:39around 115 notifications per second,
1:20:43which is not scary at all. But as a
1:20:46candidate, we should always ask for the
1:20:48peak because that is where the problems
1:20:50start arising. When the marketing team
1:20:53sends a campaign to 1 million users at 9
1:20:56in the morning, then those 1 million
1:20:59notifications arrive at the same moment.
1:21:03So our system must survive sudden
1:21:05floods. And I want to tell you one
1:21:08important fact. We do not deliver
1:21:11anything ourselves. Push notifications
1:21:14go through APNS and FCM.
1:21:18APNS is Apple's push service. And FCM is
1:21:23Google's version of the same thing. SMS
1:21:26goes through an SMS gateway provider
1:21:29like Twilio. and emails go through an
1:21:32email provider like send grid. These
1:21:35providers are external systems and not
1:21:37part of your system and external systems
1:21:41can go down. So we need to keep that in
1:21:44mind. Also calling external systems
1:21:47might take half a second might not be as
1:21:50quick as you want to. So we need to keep
1:21:53these facts in mind while designing the
1:21:55system.
1:21:57Step three is defining the API and APIs
1:22:01in this is very simple. We just need one
1:22:04API call and we can name it as notify.
1:22:08When something happens inside the
1:22:09product, the caller should call the
1:22:11notify endpoint to give the user info.
1:22:14The message that needs to be sent and
1:22:17which channels we need to send it to.
1:22:20This caller could be anything. a program
1:22:22that takes new order or a program that
1:22:25processes refund. The important part is
1:22:28that the caller should not wait while we
1:22:30send notification to the users. So the
1:22:33caller does only one thing. It calls the
1:22:36API and we record the notification in
1:22:39our database with a unique notification
1:22:42ID and notification system should
1:22:45immediately reply accepted. The actual
1:22:48sending of notification to the end user
1:22:50happens later and this notification ID
1:22:54is important to track all the
1:22:56notifications that we are sending out to
1:22:58users. Now we just said that we will
1:23:01store the notification in our database.
1:23:04So the next question is how exactly each
1:23:07notification in database looks like. At
1:23:10minimum we store the notification ID,
1:23:13the user that we send this notification
1:23:15to and list of channels where we send
1:23:18the notification, the message body, a
1:23:21status field that will track if
1:23:23notification is sent or not. So this
1:23:26field is by default filled with status
1:23:28called pending because we haven't sent
1:23:31the notification yet. And then we have a
1:23:34timestamp field that stores the time
1:23:36when this particular notification was
1:23:38created in our system.
1:23:41We can also keep one small flag that
1:23:43tracks if the end user has actually seen
1:23:46our notification.
1:23:48Later you will see that this flag is
1:23:49used to track the inapp notification.
1:23:53And you might wonder why keep a scene
1:23:55flag for inapp notifications only?
1:23:59Because in app is the only channel where
1:24:01we can actually track if user has seen
1:24:03the notification.
1:24:05When Allen opens our app, the app can
1:24:07tell us that Allen opened and saw this
1:24:09notification.
1:24:11For SMS and email, we mostly have no
1:24:15visibility after sending the message.
1:24:17The phone network will never tell us if
1:24:19Alan actually read that text or not.
1:24:22Now the thing is that you might want to
1:24:24store more fields but those extra fields
1:24:27actually depends on your product. For
1:24:29example, if you're running a shopping
1:24:31website, then you might also store the
1:24:34order ID. This is basically a table for
1:24:37our notification system. Remember that
1:24:39our system will also have other tables
1:24:42like users table that stores all users
1:24:45details. This users table stores each
1:24:48user's name, user ID, contact details
1:24:51like phone number and email address. We
1:24:54also store the device token. This device
1:24:57token is collected when a user installs
1:24:59our app on their phone. And this device
1:25:02token is actually used to send push
1:25:04notifications.
1:25:06And lastly, we also need to store the
1:25:09user's notification preferences to know
1:25:11if we can send marketing notifications
1:25:13to this person or not.
1:25:16Now a regular SQL database like
1:25:18Postgress should be completely fine for
1:25:21this design because every notification
1:25:23is just one small row and even if we are
1:25:26processing 10 million notifications a
1:25:29day or around 100 small writes per
1:25:31second it shouldn't be a problem for
1:25:33Postgress.
1:25:38Now we move to the next step which is
1:25:40the highle design. Till now we know that
1:25:44different applications in the system can
1:25:46call our notification system by calling
1:25:48notify endpoint. For example, order
1:25:52service or refund service can call the
1:25:54notify endpoint.
1:25:56We should be absolutely clear that our
1:25:59notification system is not any magical
1:26:01box. It is just another application
1:26:04program that runs on a normal server.
1:26:08Now we store the incoming notification
1:26:10requests in our Postgress database and
1:26:13we initially set the status pending
1:26:16because we haven't processed the
1:26:17notification yet. So once we have the
1:26:20notification details in database now we
1:26:23need to see who actually does the
1:26:25notification sending work. Let's start
1:26:28with the simplest version and in this
1:26:30version the notification server does the
1:26:32sending work itself.
1:26:34So right after saving the notification
1:26:37in the database, the server calls the
1:26:39Apple push notification service for the
1:26:42push notification.
1:26:44Then the server calls the SMS gateway
1:26:47and calls the email provider and then we
1:26:50wait for the confirmation by third-party
1:26:53providers that message is sent.
1:26:56Once all three external providers
1:26:58confirm that message is sent, then we
1:27:01update the status of notification in our
1:27:03database from pending to sent.
1:27:06This process can work on small scale but
1:27:09not on large scale. Why? Because if you
1:27:13notice our server is waiting from all
1:27:15three providers for confirmation. So our
1:27:18server is essentially waiting for 1 to 2
1:27:20seconds. This wait time is huge. And if
1:27:24a flood of 1 million notifications
1:27:26arrive suddenly and each notification is
1:27:28holding our application busy for more
1:27:30than a second, then we won't be able to
1:27:33process notifications on time and it
1:27:35will be a chaos and it can get worse.
1:27:39What happens if our notification server
1:27:41crashes suddenly?
1:27:43Let's say we were processing
1:27:44notification number 2000 and our
1:27:47notification server has already sent the
1:27:49notification to email provider and SMS
1:27:52provider but we haven't got the
1:27:54confirmation from the providers yet and
1:27:56the server crashes right now. In this
1:27:59case we did only the sending part. We
1:28:02don't know if we got response from SMS
1:28:04or email provider. Basically we are not
1:28:08sure what happened to notification
1:28:09number 2000.
1:28:12Now pause the video for a moment and
1:28:14think how can you accept the
1:28:16notification right now but send the
1:28:19actual notification later without losing
1:28:22anything even if a server crashes in
1:28:25between.
1:28:26So what we actually need is a component
1:28:29which can do one simple job. This
1:28:33component should be holding the pending
1:28:35notifications safely until we send them.
1:28:38and this component should keep holding
1:28:40them even if a server crashes.
1:28:43Now this can be easily done by a que.
1:28:47Just to make things absolutely clear,
1:28:50the database will still hold the full
1:28:52notification record, the message body,
1:28:55the channels, the status, the timestamp.
1:28:58Database is our permanent register and
1:29:01database will never go away. The Q
1:29:04actually holds something much smaller. Q
1:29:08will just hold a small ticket that
1:29:10includes notification ID and a note
1:29:13saying this notification is waiting to
1:29:15be sent.
1:29:17Now the final flow looks like this. The
1:29:20notification server writes the full
1:29:22record into the database and then drops
1:29:25the small ticket into the queue. Now
1:29:28what we do is we run separate servers
1:29:31called workers. The role of worker is to
1:29:34pick one ticket from the queue and then
1:29:37get more information about the
1:29:39notification from the database using the
1:29:41notification ID.
1:29:44Then worker sends the notification to
1:29:46all the providers and once the worker
1:29:49gets confirmation from these external
1:29:51providers, it then acknowledges the
1:29:54ticket and the ticket is removed from
1:29:56the queue. And if a worker crashes in
1:29:59the middle of the work, the Q notices
1:30:02that the ticket was never acknowledged
1:30:04in time. And the Q simply hands the same
1:30:07ticket to another worker, so nothing
1:30:10gets lost.
1:30:12And you should remember that you can run
1:30:14multiple workers in parallel to process
1:30:17the notifications faster. And even if
1:30:20one worker goes down, other workers can
1:30:22still work on sending notifications. So
1:30:25there is no single point of failure.
1:30:28Let's make this concrete with one
1:30:30example. The worker sees a notification
1:30:33ticket in Q and sees that notification
1:30:36ID is 35. Worker then checks the
1:30:39database for this notification ID and
1:30:42finds out that this notification needs
1:30:44to send to Allen. Worker fetches Allen's
1:30:48contact details from the users table
1:30:50that we already saw. From this users
1:30:53table, we get Allen's device token, his
1:30:55phone number, and his email address.
1:30:59Now, the worker makes one quick check.
1:31:02The worker sees Alen's notification
1:31:04preferences. And if Alan has switched
1:31:06off marketing SMS, and if this
1:31:08particular notification that we were
1:31:10about to send is marketing related, then
1:31:13the worker will drop this message and
1:31:15remove it from Q.
1:31:17Before we move on, I would like to
1:31:19repeat that our notification server now
1:31:22does two separate writes. It saves the
1:31:25full notification record in the database
1:31:27and it also drops the ticket into the
1:31:30queue.
1:31:33So when the interviewer asks what kind
1:31:35of queue you want, you have to name
1:31:38three properties. The Q must be durable.
1:31:42That means the Q should store the
1:31:44incoming tickets on disk, not in RAM.
1:31:47Why? Because RAM is volatile and if Q
1:31:51needs to restart due to some reason then
1:31:54RAM will lose the data.
1:31:57Second property of the queue we want is
1:31:59that it must support acknowledgement.
1:32:01A message is removed from the queue only
1:32:04when a worker confirms the work is done.
1:32:07And the Q must be able to work with
1:32:09multiple workers. and we should be able
1:32:12to add more workers when more
1:32:14notifications pile up and queue grows
1:32:16long.
1:32:18One property we do not need is strict
1:32:20ordering of messages within the queue.
1:32:23Basically, we mean that if two unrelated
1:32:25notifications swap places in the line,
1:32:28then it doesn't matter because nothing
1:32:30will break or go wrong if Allen's
1:32:32notification gets delivered before Jon's
1:32:35notification.
1:32:37And in fact, dropping strict ordering
1:32:39makes the queue much easier to scale
1:32:42because you have less constraints.
1:32:45If we see the overall design now, the
1:32:48notification accepting side and the
1:32:50sending side are now separated. And this
1:32:53style has a name that you should
1:32:55emphasize on in the interview. You
1:32:57should say that we are doing
1:32:59asynchronous processing of
1:33:01notifications.
1:33:02The caller program never waits for the
1:33:05notification to be sent. It just
1:33:07registers the notification to the
1:33:09notification server. When a sudden flood
1:33:12of notifications comes to our system, we
1:33:14just store them and put them in the
1:33:16queue and we simply add more worker
1:33:18nodes to send notifications to end users
1:33:21at faster rate.
1:33:23Now the next logical question is should
1:33:26all four channels share one single que?
1:33:30The answer is no. We should have
1:33:32separate Q for each channel.
1:33:35Why is that? This is helpful in case
1:33:38when one provider gets slow. For
1:33:41example, if email provider becomes slow,
1:33:44then every worker that picks up an email
1:33:46notification gets stuck waiting on the
1:33:49slow email provider. And soon most of
1:33:52our workers are busy with slow email
1:33:54provider while the push notification and
1:33:57SMS messages sit in a growing queue even
1:34:00when SMS provider is not slow.
1:34:04The learning is that one slow channel
1:34:06can keep worker nodes busy.
1:34:09Therefore, we isolate the channels and
1:34:11we deploy one Q for each channel. So, we
1:34:15will have four Q's and each Q has its
1:34:19own pool of workers. Now, each channel
1:34:22can also scale independently and deploy
1:34:25more workers on its own. If you see now
1:34:29a slow email provider delays only the
1:34:31email notifications and the other three
1:34:34channels keep delivering the
1:34:35notifications like nothing happened.
1:34:38And notice that the inapp channel is the
1:34:41easiest one here. Why? Because we are
1:34:45not dependent on any external providers
1:34:47for sending notification.
1:34:49The notification row is already sitting
1:34:51in our own database. So the worker just
1:34:54marks the inapp part as sent. And notice
1:34:58that the scene flag that we introduced
1:34:59earlier is still false at this point.
1:35:03Now when Alan opens the app on mobile,
1:35:05the mobile app asks our server how many
1:35:08unseen notifications Allen has. And then
1:35:11we can check our database for scene
1:35:13flag. If it is not seen, then we put
1:35:16that notification in Allen's app. And
1:35:19when Alan actually views the
1:35:21notifications, the mobile app informs
1:35:23our server and the notification server
1:35:26changes the scene flag value to true. I
1:35:29would like to introduce one more concept
1:35:31here. The notification server publishes
1:35:34one event and every channel Q gets its
1:35:38own copy of the event and this copying
1:35:40of one event into many cues is called
1:35:43fan out. So let's see the summary of the
1:35:46design we have till now. The notify API
1:35:50records the notification in our database
1:35:52with a unique notification ID and we
1:35:55immediately reply accepted.
1:35:58This notification then fans out into
1:36:00four durable cues. Basically we are
1:36:03maintaining one Q for each channel so
1:36:06that one slow provider cannot block the
1:36:09other channels.
1:36:10Then workers pick messages from each
1:36:12que. workers look up the user's contact
1:36:15details, check the user's preferences,
1:36:18and call the providers to send the
1:36:20notification.
1:36:22Now, the next big question is, what
1:36:24should a worker do when the email
1:36:26provider doesn't give any response and
1:36:28this request times out?
1:36:32Okay, we have four cues and our workers
1:36:35are pulling notification tickets from
1:36:37all four cues and calling the service
1:36:39providers. And on a normal day,
1:36:42everything works fine.
1:36:44Now one day our email provider goes down
1:36:46for 30 minutes and we are not getting
1:36:49any response from the provider.
1:36:51This is where we will discuss step five
1:36:53of our framework. And step five is the
1:36:56deep dive in design.
1:36:59The first question is very simple. What
1:37:02should a worker do when a provider call
1:37:04fails?
1:37:06The obvious answer is that the worker
1:37:08should try again. Let's say in the
1:37:10second attempt the provider call fails
1:37:12again and the worker doesn't get any
1:37:14response. Then the next question is how
1:37:18many times we should retry.
1:37:21If the email provider is already down
1:37:23and then hundreds of our workers are
1:37:25trying to contact the email provider
1:37:26again and again then we are just
1:37:29overloading somebody else's API.
1:37:32Therefore we should always retry
1:37:34politely.
1:37:35Instead of retrying immediately, we wait
1:37:381 second before the first retry. If it
1:37:40fails, we wait for 2 seconds before the
1:37:43second retry. And if that also fails,
1:37:46then we wait for 4 seconds before the
1:37:48third. Basically, we double the waiting
1:37:51time before trying again so that we give
1:37:54the struggling email provider some room
1:37:56to breathe. And this technique is called
1:37:58exponential backoff.
1:38:01But of course, we won't be retrying
1:38:02infinite times. Let's say after several
1:38:05retries we do not get any response. Then
1:38:09we do not throw the notification away.
1:38:11Instead we move the notification to a
1:38:14separate queue called a dead letter Q.
1:38:18This dead letter Q is like a Q specially
1:38:20for the failed messages so that a
1:38:23support engineer can look at these
1:38:24messages and take appropriate action.
1:38:30But RQ has created a new problem for us.
1:38:33And this problem is the real trap of
1:38:35this interview. Let's walk through the
1:38:38problem with one example.
1:38:40Let's say a worker picks the ticket for
1:38:42Allen's payment notification from the
1:38:44queue, reads Allen's details from the
1:38:46database, and calls the SMS provider.
1:38:50And the SMS is sent to Allen's phone
1:38:52number. And at that exact moment before
1:38:55this worker could acknowledge the ticket
1:38:57to the queue, the worker crashes.
1:39:01Now look at this situation from the Q's
1:39:03perspective. The Q only knows that a
1:39:06ticket was picked up by this worker, but
1:39:08this worker never acknowledged the queue
1:39:10in time. The Q doesn't know whether the
1:39:13SMS was actually sent or not. So the Q
1:39:17assumes the safe thing. Given the Q
1:39:20didn't get any acknowledgement, the Q
1:39:22hands the same ticket to another worker
1:39:24and Allen's phone buzzes twice with the
1:39:27same payment message.
1:39:29Now you can see the problem. We sent the
1:39:32payment notification twice to Alen. And
1:39:35if you think it through, we cannot fix
1:39:37this problem by writing careful code
1:39:40because the worker can always crash
1:39:41after sending the message but before
1:39:44acknowledging to the queue. Pause the
1:39:47video here and think how can I prevent
1:39:49one notification to be sent two times.
1:39:52We have to think about this problem from
1:39:54a different perspective.
1:39:56First we accept the fact that the Q can
1:39:59sometimes process the same ticket twice
1:40:02which leads to duplicate sending. So we
1:40:04let the duplication happen. But what we
1:40:07can do is we can build a mechanism that
1:40:09can identify duplication and drop the
1:40:12duplicate instead of sending it.
1:40:14Basically, we try to make the duplicate
1:40:16harmless. So, how do we make a duplicate
1:40:19harmless? Let me show you step by step.
1:40:23If you remember, each notification has a
1:40:26notification ID that we store in our
1:40:28database.
1:40:30Now, before calling any provider, the
1:40:32worker first checks in one shared place
1:40:35if this notification ID has already been
1:40:38sent. If the answer is yes, the worker
1:40:41silently drops the ticket because some
1:40:44other worker has already handled this
1:40:45notification and this ticket is just a
1:40:48duplicate.
1:40:49But if the answer is no, the worker
1:40:52first writes a note in that shared place
1:40:54saying this notification is taken and
1:40:57only after writing the note, the worker
1:40:59calls the provider.
1:41:01And you need to pay attention to the
1:41:03sequence here because the sequence is
1:41:05the key here. the worker first adds a
1:41:08note to the shared store and then sends
1:41:11the notification
1:41:13because if the worker crashes after
1:41:15sending the notification, the note is
1:41:18already there in the shared store. So
1:41:21when the next worker picks this ticket
1:41:23and checks the shared store, then the
1:41:25next worker will find the note that this
1:41:28notification was already processed.
1:41:31Therefore, the worker will drop this
1:41:34ticket.
1:41:35There is one more scenario that we need
1:41:37to think about. If the worker adds a
1:41:40note to the shared store that this
1:41:42notification was handled and then
1:41:45crashes just before sending the
1:41:47notification, then the notification was
1:41:50not sent at all. But the note in the
1:41:54shared store is already there. So any
1:41:57future worker will drop this
1:41:59notification and Allen never gets his
1:42:02notification.
1:42:04Well, this is why the note in the shared
1:42:07store is not permanent. We write the
1:42:09note with an expiry time and the note
1:42:12deletes itself after a minute so that a
1:42:15worker can pick it up after a minute if
1:42:18it was not sent.
1:42:20Let's take a look at what we changed
1:42:22here. Earlier, the worst case was Allen
1:42:26getting the same payment message twice,
1:42:28but now the worst case is a notification
1:42:31going out a little late. Now this little
1:42:35note that we put in the shared store has
1:42:37a name. The note is called an item
1:42:40potency key. In our case, the item
1:42:44potency key is the notification ID only.
1:42:48I would like to take a moment to define
1:42:50item potency here. Item potency means no
1:42:54matter how many times you do a task, the
1:42:57result is always the same. In our case,
1:43:01no matter how many times a worker picks
1:43:03up the same ticket, the notification is
1:43:06sent only one time.
1:43:09There are two small details that you
1:43:11should note. First, if the provider call
1:43:14fails and the worker doesn't get any
1:43:17response from the provider, then the
1:43:19worker removes the note from the shared
1:43:22store so that we can try to send the
1:43:24notification again.
1:43:26And the second point is that once the
1:43:28send succeeds the worker changes the
1:43:31status in our database from pending to
1:43:34sent.
1:43:36Now we have said that we will add the
1:43:38note to the shared store. But where does
1:43:40this shared store live? Well, every
1:43:44worker needs to check this shared store
1:43:46before every single send. So it has to
1:43:49be fast. And we already know one tool
1:43:52that can do this and it's Reddus. Before
1:43:59we move forward, let's quickly walk
1:44:01through everything we have designed till
1:44:03now. First, a notification request comes
1:44:07in and we save the notification in our
1:44:10database with a unique notification ID
1:44:13and the status pending.
1:44:16Then we drop a small ticket into the
1:44:18relevant cues. Remember we have one Q
1:44:22for each channel and we are using four
1:44:25Q's so that one slow channel never
1:44:28blocks the other channels.
1:44:30Next a free worker picks the ticket from
1:44:33the queue and before anything the worker
1:44:36checks the shared store in Reddus to see
1:44:39if this particular notification ID has
1:44:42already been handled.
1:44:44If the worker finds a note there, the
1:44:46worker drops the ticket.
1:44:49But if the worker finds no note, the
1:44:52worker writes a note with an expiry time
1:44:54and then calls the provider.
1:44:57Now if the worker fails to call the
1:45:00service provider, the worker retries
1:45:03with exponential backoff.
1:45:05And if the notification keeps failing
1:45:08even after several attempts, the
1:45:10notification is moved to the dead letter
1:45:13Q where a support engineer can take a
1:45:15look.
1:45:17But if the worker is able to call the
1:45:19provider and succeeds in sending the
1:45:21notification, the worker changes the
1:45:24status of the notification from pending
1:45:27to sent in our database. And finally,
1:45:31the worker acknowledges the ticket to
1:45:32the Q so that the Q can remove this
1:45:36ticket forever.
1:45:38And if a worker crashes anywhere between
1:45:40these steps, the queue will hand the
1:45:43same ticket to another worker and the
1:45:46note in the shared store make sure the
1:45:49duplicate ticket is not sent again and
1:45:51is dropped.
1:45:54Also, we established that the note in
1:45:56the shared store is actually an item
1:45:59potency key and the item potency key
1:46:02should be unique. So we can use the
1:46:05notification ID as our item potency key
1:46:09in our case.
1:46:11Okay. Now I want to fix one more thing
1:46:13in our design. If you notice our
1:46:16notification server does two separate
1:46:19rights. The first right is it saves the
1:46:22full notification record in the database
1:46:24and then the second right is it drops
1:46:26the ticket into the queue. Again we are
1:46:30doing two writes one to the database and
1:46:33another to the queue. If the
1:46:36notification server writes to the
1:46:37database and then it goes to the queue
1:46:40for writing but it crashes just before
1:46:43writing to the queue then we are in a
1:46:46situation where the notification is
1:46:48saved in our database but it never
1:46:50arrived in the queue. We can fix this
1:46:54easily. At the end there should be only
1:46:57one place which should be the source of
1:46:59truth and in this case it will be the
1:47:02database. So what we do is in the
1:47:05beginning we only store the notification
1:47:08in the database and then we run a small
1:47:11background job that keeps looking at the
1:47:14database to see which notifications are
1:47:17still in the pending state and whichever
1:47:20notifications are in the pending state.
1:47:22This background job adds them to the
1:47:24queue. Now the workers can pick the
1:47:27tickets from the queue. If the
1:47:30background job puts the same
1:47:32notification twice into the queue, it's
1:47:34not a problem because our design already
1:47:37takes care of duplicate items.
1:47:42Now the last step of our framework which
1:47:45is bottlenecks and scaling and we want
1:47:48to know where does our design break when
1:47:51the number of notifications grows.
1:47:54First of all, the Q is the heart of this
1:47:57system. And in the interview, you can
1:47:59name a real Q like Amazon SQS, which is
1:48:03a natural fit in our case because SQS
1:48:06gives us the acknowledgement behavior we
1:48:09mentioned in our design and it also has
1:48:12a built-in dead letter Q. Rabbit MQ is
1:48:16another solid pick for Q's in our
1:48:18system.
1:48:19Second, if we get a notification flood
1:48:22due to some event, then our cues keep
1:48:25growing and their size doesn't come
1:48:28down. If our cues are getting larger,
1:48:31then it is a signal to add more workers
1:48:34so that we can process more
1:48:35notifications in less time.
1:48:39And then there is that point that you
1:48:41should mention to the interviewer
1:48:42clearly that we never actually prevented
1:48:45duplicates in our design. The queue
1:48:48still processes the same ticket twice.
1:48:51What we chose in our design is called at
1:48:54least once delivery, which simply means
1:48:57that when our system is not sure if the
1:49:00notification is sent, the system sends
1:49:02the notification again anyway because
1:49:06sending twice is better than losing the
1:49:08notification.
1:49:10And then our item potency key catches
1:49:13those extra sends at the very last step
1:49:16right before the provider call. So Allen
1:49:19almost never sees a duplicate.
1:49:22So we should clearly mention that
1:49:24exactly once delivery of notifications
1:49:27in a distributed system is not possible.
1:49:31You can only make the redely harmless.
1:49:34So let me summarize the full
1:49:36notification system once. In the same
1:49:39way, you will close this in the real
1:49:41interview.
1:49:42The notify API records the notification
1:49:46with a unique notification ID in the
1:49:48database and immediately replies
1:49:51accepted.
1:49:52And a background job then puts a ticket
1:49:55in the queue so that the notification
1:49:58can be sent. We have one Q per channel
1:50:01so that one slow provider cannot block
1:50:04the other channels.
1:50:06workers pick tickets from the cues and
1:50:08check Reddus to see if we have already
1:50:11sent this notification.
1:50:13If we haven't sent it, then we check the
1:50:15user's preferences to see if we can
1:50:18actually send the notification. And if
1:50:20yes, the worker calls the provider to
1:50:23send the notification.
1:50:25In case of failures, we retry sending
1:50:28the notification with exponential
1:50:30backoff, and whatever still fails goes
1:50:33to a dead letter Q.
1:50:35Before closing this topic, I also want
1:50:38to mention that we could also solve this
1:50:40problem using Kafka or a pub sub
1:50:43architecture instead of Q's.
1:50:46Conceptually, the idea remains the same
1:50:48in both cases.
1:50:50Now, you might be thinking how close
1:50:52this design is to what real companies
1:50:55actually run in production.
1:50:57The design is actually very close. We
1:51:01can take the example of LinkedIn. Every
1:51:04team at LinkedIn used to send
1:51:06notifications on its own and users were
1:51:08getting multiple emails. So LinkedIn
1:51:11built one central platform called air
1:51:14traffic controller which is a single
1:51:16gateway that every notification request
1:51:19must pass through. So all teams send
1:51:21their notifications to this traffic
1:51:24controller. The requests flow in through
1:51:26Kafka and the results were actually very
1:51:29good. LinkedIn now sends 50% fewer
1:51:33emails and complaints dropped by more
1:51:36than 65%.
1:51:38Uber uses a similar approach for its
1:51:40push notifications with one extra
1:51:43addition. And the addition is that every
1:51:46message falls under different priority
1:51:48buckets. For example, a trip update has
1:51:52a higher priority than a promotional
1:51:54offer and notifications with higher
1:51:56priority are sent first and then lower
1:52:00priority notifications are sent.
1:52:02So this is how real companies use the
1:52:05notification system.
1:52:07Next, we will see some follow-up
1:52:09questions asked by interviewers.
1:52:14Towards the end of the interview, you
1:52:16can expect some follow-up questions from
1:52:18the interviewer. And these follow-up
1:52:20questions test if you can point out what
1:52:23exactly you will change in your design.
1:52:27Let's quickly see three follow-up
1:52:29questions.
1:52:30Question number one is that a marketing
1:52:33campaign just dropped 1 million
1:52:35notifications into the cues. When Allan
1:52:38triggers the login code, his
1:52:40notification is sitting behind all the
1:52:43marketing notifications in the queue.
1:52:46What do you change? And to be honest,
1:52:49you should see this coming as it's a
1:52:51valid question. Remember that in our
1:52:53clarifying questions, we learned that
1:52:56transactional and marketing
1:52:57notifications have completely different
1:52:59patience levels. A login code should be
1:53:03sent as soon as possible within a few
1:53:05seconds. So we can fix this easily and
1:53:09we do that by assigning separate cues to
1:53:12marketing and transactional
1:53:13notifications.
1:53:15Inside each channel, we keep two cues
1:53:18instead of one, a transactional queue
1:53:21and a marketing queue. And we give the
1:53:24transactional queue its own dedicated
1:53:27workers that the marketing can never
1:53:29borrow. And this is not our invention.
1:53:32Remember, Uber's priority buckets are
1:53:35already doing this. Question number two
1:53:38is that the email provider goes down for
1:53:401 hour. Walk me through what your system
1:53:44does for 1 hour. In this case, the first
1:53:48thing you should mention is that nothing
1:53:50gets lost from the system. The queue is
1:53:53durable, which means for 1 hour, the
1:53:56email notifications accumulate safely in
1:53:59the queue, but our workers still keep
1:54:03retrying to send the notification.
1:54:06If the provider is dead for an hour,
1:54:08hundreds of workers are still running
1:54:11with no outcome. So in this case, we
1:54:14should add a circuit breaker. After some
1:54:17number of consecutive failures, the
1:54:19workers completely stop calling the
1:54:21email provider. And every minute or so,
1:54:24a single probe call checks whether the
1:54:27provider has come back online.
1:54:30Next thing you should know is that big
1:54:32companies do not just rely on a single
1:54:35email provider. They keep a second email
1:54:38provider on standby or they use two
1:54:41providers together so that they have a
1:54:43backup option in case one provider
1:54:46fails. And you should mention one more
1:54:49thing to impress the interviewer. That a
1:54:51login code is only valid for about a
1:54:54minute. So delivering it 60 minutes late
1:54:57doesn't make any sense.
1:54:59So every notification can actually carry
1:55:02an expiry time. And when a worker
1:55:05finally picks up an expired message, the
1:55:08worker drops the message. Let's see the
1:55:11last question from the interviewer. You
1:55:13keep saying exactly once delivery is
1:55:16impossible. Show me exactly in which
1:55:19case you will still send the
1:55:21notification twice and your item potency
1:55:24key will fail. Actually, this is a great
1:55:27question. So let's show the exact
1:55:30scenario.
1:55:31A worker picks a ticket and checks
1:55:33Reddus and the worker finds out that
1:55:36this notification ID is not sent. The
1:55:40worker writes the note to Reddus that
1:55:42this notification is picked up and then
1:55:45calls the SMS provider. The worker now
1:55:48doesn't get the response back from the
1:55:50SMS provider and hits a timeout. Now
1:55:54think it through and answer. Did the SMS
1:55:57go to the user or not? The answer is
1:56:01that we cannot know with 100% certainty.
1:56:05The provider might have sent the message
1:56:07but got late in replying to our worker.
1:56:10If we retry, Allen might get the SMS
1:56:14twice. And if we do not retry, Allen
1:56:17might get nothing.
1:56:19And we can't do anything in this case
1:56:22because our system does not know if the
1:56:25SMS provider sent the message or not. In
1:56:29the real world, many SMS or email
1:56:31providers actually accept an item
1:56:34potency key from our system. So what we
1:56:37do is we send the item potency key along
1:56:40with the SMS request and the provider
1:56:43then checks if they have already sent
1:56:46this notification.
1:56:48In our case, our item potency key is our
1:56:51notification ID because it is unique for
1:56:54each notification.
1:56:56Now, if they see the same notification
1:56:58ID again, then they will not send the
1:57:01notification and drop the request.
1:57:04But then the phone networks like AT&T,
1:57:07Verizon, Airtel themselves can send a
1:57:10duplicate SMS on a bad day. So, we have
1:57:14placed a lot of mechanisms to avoid
1:57:16duplicates. But there are edge cases
1:57:19that can always happen. And that is
1:57:21exactly why our requirement said the
1:57:24user should ideally never see the same
1:57:27notification twice. This is it for the
1:57:30notification system. Take a second to
1:57:32process all the questions and answers we
1:57:34discussed and then you can move on to
1:57:37the next problem.
1:57:40It's time for one more lab. In this lab,
1:57:42you'll run the notification system where
1:57:44one event will fan out to a push worker
1:57:47and an email worker through separate
1:57:49cues. You will also see how duplicate
1:57:51notifications can be delivered and how
1:57:53undelivered notifications go to the dead
1:57:55letter Q. Go give this lab a shot.
1:58:00Let's now take a look at our next
1:58:01interview question. The interviewer says
1:58:04that you need to design a news feed. So,
1:58:07first let's be absolutely clear about
1:58:09what a newsfeed actually is.
1:58:11Now when you hear the term newsfeed, you
1:58:14might be thinking that we want to make a
1:58:16news app which will show the latest
1:58:18news. But notice that he didn't say news
1:58:22app. He said news feed. So newsfeed is a
1:58:27general term which we use for any social
1:58:30media feed. For example, when you open
1:58:34your LinkedIn, the first screen that you
1:58:37see is the series of items posted by
1:58:40people you follow. This is the news feed
1:58:44of LinkedIn.
1:58:46Similarly, if you open X, the first
1:58:48screen you see is the tweets posted by
1:58:52people you follow. It is the newsfeed of
1:58:55X. So newsfeed is a general term for the
1:59:00first page where you have an endless
1:59:02number of posts which you can scroll.
1:59:05Now this feed is just a sorted list of
1:59:08posts and we need to build a system that
1:59:11can efficiently build this list.
1:59:15So now let's apply our six-step
1:59:17framework on this problem.
1:59:20Step one is to clarify the requirements
1:59:22and remember that our aim is to get
1:59:25functional and non-functional
1:59:26requirements of this system by asking
1:59:29minimum number of questions. First
1:59:32question is what exactly goes into the
1:59:34feed and posts appear in what order?
1:59:38Let's say the interviewer says that the
1:59:40feed should only have posts from the
1:59:43accounts you follow and you need to show
1:59:46the newest post first.
1:59:49And this answer actually simplified
1:59:51things for us because we just have to
1:59:53sort the posts by their timestamps and
1:59:56we can make the feed. The interviewer
1:59:59could have also asked us to build a
2:00:01ranking algorithm and a ranking
2:00:04algorithm is a separate problem in
2:00:06itself because you have to look at
2:00:08multiple things. For example, you need
2:00:11to consider when this post was created,
2:00:14who created this. Did anyone in your
2:00:17connections like this? So, the ranking
2:00:20algorithm needs us to build a whole
2:00:23scoring mechanism so that we can score
2:00:25the posts and we can show the highest
2:00:28scoring post first.
2:00:31So, in our case, the interviewer has
2:00:33said we just store the posts and sort
2:00:36them by time.
2:00:38My second question will be when a user
2:00:41creates a new post, how quickly should
2:00:44this post show up in the followers feed?
2:00:47Let's say the interviewer says a few
2:00:49seconds is fine, but it shouldn't take
2:00:52minutes.
2:00:53Then my third question will be what is
2:00:55the target for feed load latency? How
2:00:59quickly do we want the feed to load? The
2:01:02interviewer says the feed should load
2:01:05within 1 second. And my fourth question
2:01:08will be to know if the feed is text only
2:01:12or do we need to show images and videos
2:01:15in the feed. The interviewer says that
2:01:18images and videos are both supported in
2:01:21the newsfeed along with text. And the
2:01:25fifth question is what if the same post
2:01:27appears again in the user's feed after a
2:01:31refresh?
2:01:32The interviewer says the same post
2:01:34appearing twice is not a big problem.
2:01:38So before moving on to next stage of
2:01:40interview, we state the scope of this
2:01:43problem very clearly.
2:01:46So you should clearly mention that users
2:01:48can follow other accounts. Users can
2:01:51create posts with text, images, or
2:01:54videos. And users can read a feed. And
2:01:59in the feed, we show the newest posts
2:02:02from the accounts they follow. When
2:02:05users open the app, the feed must load
2:02:08within 1 second. A new post can take a
2:02:12few seconds to reach the followers
2:02:14feeds. And when a user refreshes their
2:02:17feed, an occasional duplicate post on
2:02:20the feed is acceptable.
2:02:23The second step is back of the envelope
2:02:25estimation. And the first thing I will
2:02:28do here is ask the interviewer for the
2:02:30scale. So my question will be how many
2:02:34users are we serving and how often do
2:02:37they open the feed? Let's say the
2:02:40interviewer says that we have 10 million
2:02:43daily active users.
2:02:45Now, we know that on platforms like
2:02:47LinkedIn or X, we read more than what we
2:02:51post. So, let's say every user opens
2:02:54their feed five times a day. And we know
2:02:58that we have 10 million active users.
2:03:01That means we have to serve 50 million
2:03:05feed reads per day, which is roughly 600
2:03:09feed reads every second on average. And
2:03:13users post very rarely. There are 10
2:03:16million active users and each posts
2:03:19three times a month. That means 30
2:03:23million posts in a month or we can say
2:03:2730 million posts in 30 days. The final
2:03:31number comes out to be around 1 million
2:03:34posts per day. Now a day has about
2:03:3886,000 seconds.
2:03:40That means on an average we write 12
2:03:43posts per second.
2:03:46Now if we compare the number of scrolls
2:03:48per second and posts per second the
2:03:51ratio comes out to be 50 is to one. For
2:03:56every one post that gets written on our
2:03:58platform there are around 50 feed reads
2:04:01happening. Basically this is a read
2:04:04heavy system and this is the most
2:04:07important fact in this problem.
2:04:10Because we know that our app is read
2:04:12heavy, we should focus more on the feed
2:04:15reading path.
2:04:18Step three is to define the API. One
2:04:22thing should be very clear in your mind.
2:04:24You don't have to do anything to make
2:04:27API calls. If the user is using a mobile
2:04:30application, the mobile application will
2:04:33make these API calls on the user's
2:04:36behalf.
2:04:37Now a real newsfeed app like LinkedIn
2:04:40will have multiple API calls available
2:04:43but for our case we can focus on two
2:04:45work items. The first is to create a new
2:04:49post. When a user named Alen wants to
2:04:52create a new post Allen's phone will
2:04:55call the create post endpoint. And if
2:04:59Alen opens the app, the mobile app on
2:05:02Alen's phone should call the get feed
2:05:04endpoint. so that the mobile app can
2:05:07receive the feed which Allen can see.
2:05:11When Allan calls the create post
2:05:13endpoint, his phone will also send the
2:05:16content of the new post so that our
2:05:19server can save this post. And when Alan
2:05:22calls the get feed endpoint, our server
2:05:25should return the top 50 posts from all
2:05:28the accounts that Alan follows. Now
2:05:31obviously there will be other API calls
2:05:34for likes, comments and follow but for
2:05:37now we will not discuss them. Now we
2:05:40just said we will store posts and we
2:05:43will show those posts to our users. So
2:05:45the next question is what exactly do we
2:05:48store in our database?
2:05:51We need three tables for this problem.
2:05:54First is the users table. In this table,
2:05:58we store the user information like the
2:06:00user ID, the name of the user, and the
2:06:03profile details. And interestingly, we
2:06:07also keep one small flag in this table
2:06:10that checks if this account is a
2:06:12celebrity account. Right now, you
2:06:15shouldn't worry about this flag, but
2:06:17later you will see the importance of
2:06:19this flag. The second table we store is
2:06:23the follows table. And this table is
2:06:25very simple. Every row is just two
2:06:29values. The follower and the person
2:06:31being followed. For example, Alan
2:06:35follows John. This is one row. And this
2:06:39table grows very fast because we have 10
2:06:42million users. And if each user on an
2:06:45average follows 200 users, it will
2:06:48result in 2 billion rows. Now, here is
2:06:52the question. How will we read this
2:06:55table? One of the scenarios is when we
2:06:58want to know which accounts Alen is
2:07:00following. This is required when we
2:07:03build Alen's feed because we want to
2:07:06know which accounts are followed by
2:07:08Allen so that we show posts only from
2:07:11those accounts in Alen's feed. And there
2:07:15is a second direction too. Who follows
2:07:17John? Right now this direction looks
2:07:21useless but later you will see that this
2:07:24direction becomes the most important
2:07:26query in the whole system. And the third
2:07:29table that we will store is the posts
2:07:31table. In this table we store all the
2:07:34posts. Each row in this table includes
2:07:38the post ID, the author of the post, the
2:07:42actual content of the post and the
2:07:45timestamp.
2:07:46Also we should organize this table by
2:07:49author and by time so that we can answer
2:07:53queries like give me John's latest posts
2:07:56very easily. Basically what we are
2:07:59trying to do is we are trying to see
2:08:01what the access pattern will be or how
2:08:04we will fetch the information when we
2:08:07serve end users and based on that we are
2:08:10trying to organize our tables.
2:08:15Now we move to the next step where we do
2:08:17the highle design of the system. Until
2:08:20now we know that the user's mobile app
2:08:23talks to our servers with two API calls
2:08:26and our data is sitting in three tables
2:08:29in the database.
2:08:31So the next question is that when Alan
2:08:33opens the app, how do we actually build
2:08:36his feed?
2:08:38Let's start with the very simplest
2:08:40version. And in this version, we do all
2:08:43the work when Allen opens the app. Let
2:08:47me walk you through one complete request
2:08:49by Alan so you can see exactly how
2:08:51things travel inside the system.
2:08:55Alan opens the app and the app calls the
2:08:58get feed endpoint. Our server first goes
2:09:01to the follows table and asks who does
2:09:04Alan follow? The query runs and the
2:09:07answer comes back and the answer has 300
2:09:11accounts that Allen follows.
2:09:14Then the server goes to the posts table
2:09:16and asks, "Give me the recent posts of
2:09:19these 300 accounts."
2:09:22The query runs for all 300 accounts that
2:09:25Allen follows. And once the query
2:09:27finishes, the server now has a few
2:09:30hundred posts sitting in its memory.
2:09:34The server sorts them by time and then
2:09:36keeps the newest 50 and returns these 50
2:09:40posts to Alen's app. Alan now sees his
2:09:44feed.
2:09:45To be honest, this design works, but
2:09:48let's see some problems with this
2:09:50design.
2:09:52Now, let's see how this design behaves
2:09:54when the number of users increases.
2:09:57Whenever a user is trying to access his
2:09:59feed, it triggers one read operation on
2:10:03the follows table to find out which
2:10:05accounts this user follows.
2:10:08Once we have the accounts that this user
2:10:10follows, then we trigger 300 separate
2:10:13lookups to see what these 300 accounts
2:10:16have posted.
2:10:18Then we merge the posts that we get from
2:10:20these 300 accounts and sort them by
2:10:23time. Remember that we receive 600 feed
2:10:27opens per second. So for 600 feed opens
2:10:31each second, we have to read the follows
2:10:34table 600 times. And we have to do
2:10:39180,000 database lookups every second
2:10:42just for building feeds.
2:10:45In the evening time, we will probably
2:10:47get peak traffic. If we assume peak
2:10:50traffic to be five times of normal
2:10:52traffic, then multiply this number by
2:10:55five.
2:10:56This will make our database extremely
2:10:58slow and users will have to wait a while
2:11:01to get the feed on their screen. And
2:11:04remember that we promise the feed loads
2:11:06within 1 second.
2:11:09If you look carefully, most of this work
2:11:11is wasted work. Why? Let's understand
2:11:15this with an example.
2:11:18Alan opens his feed in the morning and
2:11:20then he goes through some posts and then
2:11:23closes the app. But after a few seconds,
2:11:26he opens the app again.
2:11:29Because he opened the app very soon, new
2:11:32posts might not have arrived from the
2:11:34accounts he follows. Or maybe two or
2:11:37three new posts arrived.
2:11:40But we have to rebuild Allen's entire
2:11:42feed from scratch again just to find out
2:11:45that almost nothing has changed in
2:11:47Allen's feed.
2:11:49So can we do something with our design
2:11:51to fix this?
2:11:53The instinct might be to use read
2:11:55replicas of the database. But even then
2:11:59we are using more machines doing the
2:12:01same wasteful query. Now pause the video
2:12:04for a moment and think. Every feed is
2:12:08rebuilding from scratch.
2:12:10Is there a way where we don't have to
2:12:12rebuild from scratch?
2:12:14The answer is very logical. We shouldn't
2:12:18build the feed when Allen reads it.
2:12:21Therefore, we should actually have the
2:12:23feed built before Allen accesses it and
2:12:27we store this feed somewhere.
2:12:29And then when somebody posts something
2:12:31new, let's say John posts a new thing,
2:12:35then we will go to Allen's feed and we
2:12:38will just add J's post. Basically, we
2:12:42change Allen's feed only when someone
2:12:44posts a new thing. Otherwise, we won't
2:12:48change Alen's feed. Let's see how we
2:12:51will implement this.
2:12:53Okay, let's now see how we build the
2:12:56feeds for users before they open the
2:12:58app. And before we build anything, one
2:13:02thing should be absolutely clear in your
2:13:04mind. The three tables we had in our
2:13:08database are not going anywhere. The
2:13:11users table, the posts table and the
2:13:14follows table stay exactly as they are
2:13:17and they hold the source of truth. Now
2:13:21if we are premputing a feed for every
2:13:24user the first question is where these
2:13:27readymade feeds should live. Now if you
2:13:30remember the requirement is that the
2:13:33feed should load within 1 second. So the
2:13:36readymade feeds should live somewhere
2:13:38fast and in memory and that's why we
2:13:41will store our feeds in Reddus.
2:13:44For example, there is a list for John
2:13:47with the posts we need to show to John.
2:13:49And we have a list for Alan with the
2:13:51posts we need to show to Alan. Because
2:13:54we have 10 million users, we will have
2:13:57to create 10 million small lists sitting
2:14:00in our Reddis cache. And now when Alan
2:14:03opens the app, the request comes to the
2:14:05server. The server checks the cache for
2:14:08the list. And Alen's list is already
2:14:11there. The feed was prepared before Alan
2:14:14ever asked for it. The next natural
2:14:17question is who prepares these lists. So
2:14:21let me walk you through one complete
2:14:23journey. Let's say John writes good
2:14:25morning and posts it to our platform.
2:14:29The create post endpoint will save this
2:14:31post in the posts table and the post
2:14:34will get some ID. Let's say the ID is
2:14:3771.
2:14:39Now we have to show this post to every
2:14:41user who follows John. To do this, we
2:14:45keep a background job whose whole task
2:14:47is to take each new post and deliver the
2:14:50post to the right lists that are there
2:14:53in cache.
2:14:55This background job checks the follows
2:14:57table and sees who follows John. The
2:15:01answer comes back 800 followers and Alan
2:15:04is one of them. So the background job
2:15:07goes to Alen's list that is stored in
2:15:09the cache and adds post 71 at the top
2:15:14along with Alen. The background job goes
2:15:16to the other 799 followers and adds this
2:15:20post to the lists of those people. Now
2:15:23when Alan opens his feed, John's post is
2:15:27already there for Alan to see. Notice
2:15:29that we did not rebuild Alen's whole
2:15:32feed. We took one new post and slipped
2:15:35it into Alen's list. Before we go
2:15:38further, there is one thing you should
2:15:40be clear about. What does each list in
2:15:42the cache actually hold?
2:15:45Each list in the cache only holds post
2:15:48IDs that we need to show to the user.
2:15:51For example, Allen's list has post ID
2:15:5571, 68, 64, and so on. The newest post
2:16:00is sitting at the top.
2:16:02Basically, we are not storing the actual
2:16:05post content here. So when Alan opens
2:16:08the app, we still have to fetch the
2:16:10actual post content for these ids. And
2:16:14if we fetch these posts from the
2:16:15database every time, we are again
2:16:18sending a lot of queries to the database
2:16:21and we will be putting unnecessary
2:16:23pressure on the database because the
2:16:25same fresh post from John appears in the
2:16:28feeds of hundreds of people. So it
2:16:31doesn't make sense to fetch the same
2:16:33post content again and again from the
2:16:35database.
2:16:36So what we will do is deploy a second
2:16:39cache whose only job is to hold the
2:16:42actual content of recent posts. I am
2:16:45naming this as the post cache. Now let's
2:16:48revisit how our system looks. Now when
2:16:51Allan opens the app, we read Allen's
2:16:54list from the first cache and based on
2:16:57the post ids in this list, we fetch the
2:17:00actual content from the second cache or
2:17:02the post cache. If some post is not
2:17:06found in the post cache, then we go to
2:17:08the database and fetch the post from the
2:17:11database. And whenever we fetch a post
2:17:14from the database like this, we also
2:17:16update the post cache with this content
2:17:19so that next time we don't have to go to
2:17:21the database for the same post.
2:17:24Overall, we are now running two caches
2:17:27with two different jobs. The first cache
2:17:31says which posts to show and the post
2:17:34cache holds the posts themselves.
2:17:37Remember that we promised the feed loads
2:17:39within 1 second. And now our system is
2:17:42indeed fast due to the use of two
2:17:45caches.
2:17:50Now let's zoom into the background job
2:17:52because in an interview if you say a
2:17:55background job handles the new post then
2:17:57the interviewer may ask how you would
2:17:59implement this background job. So let me
2:18:02show you what happens when John adds a
2:18:04new post.
2:18:06When John clicks on the send button on
2:18:08his phone, his phone calls the create
2:18:10post endpoint on our servers.
2:18:13Our server opens a database transaction.
2:18:16And within this transaction, we do two
2:18:18things. First, we add the new post
2:18:21content into the posts table. And
2:18:24second, we add one small note into a
2:18:27second table called the outbox table.
2:18:31This note simply says that post with ID
2:18:3471 needs to be delivered and the note
2:18:37carries a pending flag.
2:18:40You should carefully notice that we have
2:18:41said in one transaction we do both the
2:18:44things. That means either both the
2:18:47things happen or nothing happens at all.
2:18:51Now a background worker keeps checking
2:18:53this outbox table every few seconds and
2:18:56it picks the jobs that are still marked
2:18:58as pending and drops a ticket into the
2:19:00queue.
2:19:02Once we have dropped the ticket in the
2:19:03queue, we change the flag in the outbox
2:19:06table from pending to done.
2:19:09The ticket that we have posted in the
2:19:11queue simply says post with ID71
2:19:15posted by John is new.
2:19:18Once we have the ticket in the queue,
2:19:20what happens next? On the other side of
2:19:22the queue sits our worker node. This
2:19:25worker picks this ticket and sees that
2:19:28this ticket was posted by John. This
2:19:30worker checks the follows table to know
2:19:32who follows John. And the worker node
2:19:35realizes that John is followed by 800
2:19:38followers.
2:19:40Then this worker pushes this new post
2:19:42into the list of each follower. And once
2:19:45the worker has added this new post to
2:19:47the lists of all the concerned people,
2:19:49the worker then acknowledges the ticket
2:19:52and then the ticket is closed.
2:19:55And you might be thinking, why have we
2:19:57made this new outbox table? Why can't we
2:20:00simply save the post in the database and
2:20:03drop the ticket into the queue itself?
2:20:06If we do that, then those would be two
2:20:08separate writes into two separate
2:20:10systems.
2:20:11One write will be in the database and
2:20:13one right will be in the queue. Now
2:20:16imagine if the server crashes after
2:20:18saving the post in the database but
2:20:20before dropping the ticket in the queue.
2:20:23Then the post is saved in the database
2:20:25but the queue never gets it. That's why
2:20:28we are doing everything within the
2:20:29database with the help of the outbox
2:20:32table.
2:20:33Notice that now when someone posts
2:20:35something then we write the details only
2:20:38to the database. Both the post and the
2:20:41note land there together in the
2:20:42database.
2:20:44And this trick of saving a small note in
2:20:46the outbox table and then letting a
2:20:48background worker deliver the
2:20:50information is called the outbox
2:20:52pattern. Now there is one more thing you
2:20:55should notice in this flow. If a worker
2:20:58writes the post with ID71
2:21:01in the lists of all followers and
2:21:03crashes before acknowledging the ticket
2:21:05in the queue, another worker will pick
2:21:07the same ticket and push the post with
2:21:10ID71
2:21:11into the same followers lists a second
2:21:14time.
2:21:15So now Allen's list is holding the same
2:21:18post with ID71 twice. But this problem
2:21:22can be solved easily. The worker can
2:21:25simply check if this post ID already
2:21:27exists. And if yes, it can simply skip
2:21:30this post with the same post ID. And
2:21:33even if some duplicate still slips
2:21:36through after a refresh, remember that
2:21:38the interviewer told us that an
2:21:40occasional duplicate after a refresh is
2:21:43not a big problem.
2:21:47So premputing every feed looks like a
2:21:49great upgrade to our system. But you
2:21:52should remember that every solution
2:21:53comes with its own problem. So let me
2:21:56show you one big problem with this
2:21:58system.
2:22:00Let's say one of our account holders is
2:22:02Leonel Messi and 100 million users
2:22:05follow Leonel Messi.
2:22:08Now as soon as Leonel Messi posts
2:22:10something, we will have to add this post
2:22:12to the lists of all these 100 million
2:22:15users so that all of them can see Leonel
2:22:18Messi's post. This one operation could
2:22:22itself take minutes. And you can imagine
2:22:26how big this operation is. One person is
2:22:30posting something and we are writing the
2:22:33same thing into 100 million lists.
2:22:37We have one more issue here. We are
2:22:40writing Leonel Messi's post into 100
2:22:44million lists. But some of these users
2:22:47might not open the app in upcoming days.
2:22:50And that means some of the work done by
2:22:52our system gets wasted.
2:22:56So now we can see the full picture of
2:22:58pros and cons. When we were building the
2:23:01feed at the time the user opens the app,
2:23:04it was leading to a lot of read queries
2:23:07running on our database.
2:23:09But if we premputee the feed, then we
2:23:12are making the feed for all the users
2:23:15even if they don't open the app in the
2:23:17coming few days.
2:23:19And in the preomputation approach, if a
2:23:22celebrity posts, then we have to write
2:23:25the same post into millions of lists.
2:23:29So can we really say the precomputing
2:23:32approach is the better approach for
2:23:34building the feed? Let's answer this
2:23:36question.
2:23:38In reality, precomputing is actually a
2:23:41good approach for normal users. But for
2:23:45celebrities, we shouldn't premputee.
2:23:48We should read the celebrity accounts
2:23:49when we open the app. Therefore, the
2:23:53best approach is the hybrid approach. We
2:23:56divide our users into normal users and
2:23:59celebrity users. How do we divide the
2:24:02users? We can put a threshold on the
2:24:06number of followers. Let's say at
2:24:09100,000 followers.
2:24:11Accounts below 100,000 followers are
2:24:14normal accounts. And when these normal
2:24:17users post anything, we push their posts
2:24:21into the follower lists exactly the way
2:24:24we just built.
2:24:26Accounts above 100,000 followers get the
2:24:29celebrity flag. And posts that come from
2:24:32celebrity accounts are not pushed into
2:24:35the followers lists.
2:24:38Now when a user named Allen calls the
2:24:40get feed functionality to get his home
2:24:42feed, our system does two small jobs
2:24:46instead of one. First, the system reads
2:24:49Allen's ready-made list that lies in
2:24:52Reddus. And the second job is that our
2:24:55system separately fetches the latest
2:24:57posts from the celebrity accounts that
2:25:00Allen follows.
2:25:02Now the data is coming from two streams.
2:25:05one the premputed list that contains
2:25:08posts from normal users and second the
2:25:12direct fetch for celebrity users.
2:25:15So our system will need to merge both
2:25:18kinds of posts and return the first 50
2:25:21posts to Allen.
2:25:23And because we are reading celebrity
2:25:25posts directly, we don't need to write
2:25:28the celebrity posts to the lists of
2:25:30millions of users.
2:25:33And do you remember that small flag we
2:25:35kept in our users table? The flag that
2:25:38tells us whether an account is a
2:25:40celebrity account. I told you back then
2:25:43that you will see its importance later.
2:25:46And this flag is what our system checks
2:25:49to decide whether a post should be
2:25:51pushed into the follower lists or not.
2:25:55In summary, you should always remember
2:25:58that normal accounts get pushed and
2:26:00celebrity users get pulled.
2:26:03And now that the design is complete, let
2:26:06me tell you some industry terminologies
2:26:08that your interviewer or your peers will
2:26:10use frequently.
2:26:12The approach where we build the fresh
2:26:14feed when the user reads the feed is
2:26:17called fan out on read. And the approach
2:26:21where we premputee the feed when a new
2:26:23post is written is called fan out on
2:26:26write.
2:26:27I disclosed the names late purposefully
2:26:30because I wanted you to understand the
2:26:32concept first and then understand the
2:26:35terminology.
2:26:39And now the last step of our framework
2:26:42which is bottlenecks and scaling. We
2:26:45need to think about how this design
2:26:46behaves when the number of users grows
2:26:49and where this design will fail.
2:26:52First, the most important component for
2:26:55our precomputed feeds is the cache. We
2:26:58are using two caches in our design and
2:27:01these two caches keep the system fast
2:27:05and because of these two caches, we are
2:27:07able to serve the feed very quickly.
2:27:10So, let's see how much data we have to
2:27:12store in these caches.
2:27:15Now, let's take the first cache. This
2:27:18cache holds the list of 10 million
2:27:20users. But for each user, we can't have
2:27:23an infinite list. So we have to decide
2:27:26the maximum number of posts that can be
2:27:29stored in one list. And it is common
2:27:32practice to keep around 500 posts in
2:27:35this list. So let's do the calculation
2:27:38based on 500 posts per list.
2:27:42One post ID takes around 8 bytes. So 500
2:27:47post ids would be around 4 kilob.
2:27:52That means for one user we have to store
2:27:554 kilob
2:27:57and for 10 million users we multiply
2:28:00this by 10 million and this comes out to
2:28:04around 40 GB.
2:28:07So our first cache should be at least 40
2:28:10GB.
2:28:12Okay. Now let's take a look at the
2:28:14second cache. And in this cache we
2:28:16actually store the posts.
2:28:19Earlier we calculated that each user on
2:28:22an average posts three times per month
2:28:26and we have 10 million active users. So
2:28:30you can see that we will have 30 million
2:28:32posts per month. So if we store all the
2:28:36posts in the last one month then we have
2:28:39to store around 30 million posts and
2:28:43each post is around 1 kilobyte.
2:28:47So the total storage for storing one
2:28:49month of posts would be around 30 GB.
2:28:54But in reality we might not be storing
2:28:56all the posts that were posted in the
2:28:58last 30 days. We simply give this cache
2:29:02a fixed amount of memory and then the
2:29:05cache only keeps the posts that are read
2:29:07more frequently and we know that the new
2:29:10posts will be read more frequently.
2:29:14And there is one more important thing
2:29:16about these lists.
2:29:18Note that we are not making lists for
2:29:20every user. We are making lists only for
2:29:23the active users.
2:29:25For our design, let's say an active user
2:29:28is somebody who opened the app in the
2:29:30last 30 days, but 30 days is not fixed.
2:29:35And this duration can change from
2:29:37company to company.
2:29:39So when Lionol Messi posts something, we
2:29:42don't push his post into the lists of
2:29:44people who have not opened the app in
2:29:46months because all that work would be
2:29:49wasted.
2:29:50And when a user comes back after two
2:29:52months and opens the app, we build the
2:29:55feed for this user once at read time.
2:29:59One more point we need to discuss is
2:30:01that somewhere the interviewer will ask
2:30:03about the database because a real system
2:30:06rarely uses one database for everything.
2:30:10For example, a post is written to the
2:30:13posts table exactly once. This post is
2:30:16usually never updated. And data in this
2:30:19post row is always read by looking at
2:30:22author and by time.
2:30:24This shape fits well with a database
2:30:27like Cassandra which is built for
2:30:29exactly this type of timeordered data.
2:30:33And if you look at the other tables like
2:30:34the users table and the follows table,
2:30:37they are very different. They have small
2:30:40rows. They have relationships and
2:30:43lookups are done in both directions.
2:30:46And a relational database handles these
2:30:49very well.
2:30:50And one more thing about our database,
2:30:53we are writing 30 million posts every
2:30:56month. And these posts are never deleted
2:30:59and they stay with our system forever.
2:31:02So in one year we are looking at around
2:31:05360
2:31:06million posts. And this number only
2:31:09keeps growing.
2:31:12One single database machine will not be
2:31:14able to hold all these posts. So we will
2:31:17have to store our posts across multiple
2:31:20database machines.
2:31:22And this splitting of data across
2:31:24multiple machines is called sharding.
2:31:30Okay, we have come a very long way and I
2:31:34want to turn your attention to our
2:31:36fourth clarifying question that we asked
2:31:38where the interviewer said that posts
2:31:40can carry images and videos along with
2:31:43the text.
2:31:45So what about these photos and videos?
2:31:48Where do we store them? We do not store
2:31:50the image and the video in our table
2:31:53where we store all the posts because
2:31:56this will make our database very heavy.
2:31:59Therefore, in the database row, we will
2:32:02only store the link of the image and
2:32:04video that needs to be attached with the
2:32:06post.
2:32:08Basically what we are saying is that in
2:32:10the database we have the text and then
2:32:13we ask our user's app to load the image
2:32:16or video from object storage like S3.
2:32:22Typically a CDN sits in front of the
2:32:24object storage and caches the media to
2:32:27ship it faster to the end user. So the
2:32:30app normally downloads the image or
2:32:32video through the CDN. The image is
2:32:35loaded directly from the content
2:32:37delivery network.
2:32:39Let's summarize this. A post row should
2:32:42carry the text of the post and a link to
2:32:45the image or video. The image goes to
2:32:48the object storage and is delivered
2:32:50through the content delivery network so
2:32:53that it can be served to the user much
2:32:55faster.
2:32:56You should also note that the post cache
2:32:59or our second cache where we store the
2:33:01actual post will also store the image or
2:33:05video URL.
2:33:07This way the heavy images and videos
2:33:10don't have any impact on our system.
2:33:13And finally, let's look at what happens
2:33:16when one of the posts goes viral.
2:33:19The problem is that everyone on the
2:33:21planet is reading the same post at the
2:33:24same time. And this post sits in our
2:33:27post cache on one single cache. So that
2:33:31one single cache takes the whole world's
2:33:34reads and is not able to keep up.
2:33:37Therefore, to distribute the extreme
2:33:39load from users, we put that one viral
2:33:42post on several cache instances and
2:33:46spread the reads across these copies of
2:33:48the cache.
2:33:50At the end of the interview, we have to
2:33:52summarize what we have done in this
2:33:54design.
2:33:55So let me summarize this system for you.
2:33:59When a normal account posts, the post
2:34:01and its small outbox note are saved
2:34:04together in the database in one
2:34:06transaction.
2:34:08A background worker will check the note
2:34:10in the outbox and then add a ticket in
2:34:12the queue.
2:34:14Then one of the workers will pick this
2:34:16ticket and push the post ID into the
2:34:19feed list of every follower. And this
2:34:22feed list is stored in Reddus.
2:34:25Each feed list can store up to 500 post
2:34:29ids. Celebrity accounts function
2:34:32differently. When Allen opens his mobile
2:34:35app, the get feed API is called and the
2:34:39server reads his Reddit list and gets
2:34:41the actual posts from the second cache.
2:34:45And along with this, we also pull posts
2:34:47from the few celebrities he follows.
2:34:50We merge both the normal users posts and
2:34:53the celebrity posts and then return the
2:34:56top 50 posts to Allen. We do not
2:35:00premputee the feed list for inactive
2:35:02users. We build the feed when they
2:35:05return to the platform.
2:35:07And at last, a viral post is served from
2:35:10multiple cache copies.
2:35:15Towards the end of the interview, you
2:35:17can expect some follow-up questions from
2:35:19the interviewer. And these follow-up
2:35:22questions test if you can improve your
2:35:24design based on the questions.
2:35:27Let's quickly see three follow-up
2:35:29questions.
2:35:31Question number one is that Allan is a
2:35:34power user and he follows 20,000
2:35:37accounts and 800 of those accounts are
2:35:40celebrity accounts.
2:35:42So, every time Alan opens the app, our
2:35:45system has to go and pull the recent
2:35:48posts of 800 celebrities before Allen
2:35:52can see anything on his screen. Will you
2:35:55change anything for this power user?
2:35:58And this is a good question because in
2:36:00our hybrid design, we said that
2:36:03celebrity posts are never pushed into
2:36:05the follower lists and instead we read
2:36:09the celebrity posts at the time the feed
2:36:11is opened. For a normal user who follows
2:36:15a few celebrities, this operation is
2:36:17cheap. For Allen, this becomes 800
2:36:21separate fetches from the database
2:36:23because he follows 800 celebrities.
2:36:27Now before answering the interviewer,
2:36:30you should notice one thing carefully.
2:36:33The 20,000 number by itself is not the
2:36:36problem here because Allen's list is
2:36:39already built and sitting in Reddis
2:36:41cache. The problem is only the 800
2:36:45celebrity accounts of those 20,000
2:36:48accounts that he follows.
2:36:50So the fix is that we should stop
2:36:53fetching a celebrity's posts from
2:36:55database for every single user. Instead,
2:36:59we keep one small list in the cache for
2:37:02each celebrity account. And this list
2:37:05holds the recent post ids of that
2:37:08celebrity.
2:37:09For example, we will keep one list for
2:37:12Leonel Messi and this list will keep all
2:37:16the recent posts by Leonel Messi.
2:37:19This one list is shared by everybody who
2:37:21follows Leonel Messi and there are only
2:37:24a few thousand celebrity accounts on our
2:37:27platform. So we will have to keep a few
2:37:30thousand small lists to serve the
2:37:32celebrity posts.
2:37:34Now Allen's feed request reads 800 small
2:37:37lists from the cache instead of sending
2:37:40800 queries to our database.
2:37:43The interviewer could have asked this
2:37:45question differently. They could have
2:37:47asked that if Leonel Messi has a 100
2:37:50million followers then when Leonel Messi
2:37:53posts something thousands of users will
2:37:56pull the new post from Leonel Messi. Due
2:38:00to this all the users will be sending a
2:38:02lot of queries to our database and can
2:38:05overload our database.
2:38:07So now we have made it clear that we
2:38:09will keep the celebrity posts in cache
2:38:12as well.
2:38:13There is a second smaller thing you
2:38:15should be honest about with the
2:38:17interviewer. If 20,000 accounts are
2:38:20followed by Allen, then Allen's feed
2:38:22list, which can hold only 500 posts,
2:38:26will be filled very quickly.
2:38:29And because new posts are pouring into
2:38:31the list, the older posts will be pushed
2:38:34out of the list before Alen ever sees
2:38:37them. And that is acceptable because
2:38:40Allan is going to read only the top 50
2:38:42posts anyway.
2:38:45Let's see the second question that the
2:38:46interviewer can ask.
2:38:48Your system has a backlog and new posts
2:38:51are taking 8 minutes to reach the
2:38:53follower lists. What will you do to fix
2:38:56the situation?
2:38:59First of all, whenever there is a
2:39:01latency or speed issue in your system,
2:39:04you should first identify where the
2:39:06problem is. And to identify a problem,
2:39:09you should be measuring the right thing.
2:39:12So the first thing you should say is, I
2:39:15would watch the time between the post
2:39:17getting saved in our database and the
2:39:19post landing in the last followers list.
2:39:23If posts are accumulating in the queue,
2:39:25then you can add more worker nodes so
2:39:28that multiple worker nodes can work in
2:39:30parallel. They take the tickets from the
2:39:33queue and write the new post into the
2:39:35followers lists. But adding worker nodes
2:39:39costs money and time. So you need to be
2:39:42slightly more strategic on how you
2:39:45handle new posts. Here is the answer
2:39:48that will impress the interviewer.
2:39:50We do not need to treat all the
2:39:52followers equally. When we are writing
2:39:55the post into the feed of all the
2:39:57followers, we can prioritize the
2:39:59followers who have been active on the
2:40:01app in the last few minutes or hours or
2:40:04if they are active right now.
2:40:07When the worker picks the ticket for J's
2:40:09new post, the worker first pushes this
2:40:12post into the lists of the followers who
2:40:15are using the app right now or open the
2:40:19app in the last few hours. And all the
2:40:22remaining followers get the same post in
2:40:24a second pass.
2:40:27A user whose app is not open and is not
2:40:30looking at the screen will not even know
2:40:32it took a few minutes to write the post
2:40:35into their feed.
2:40:37Let's see one last question from the
2:40:39interviewer. They say, "Right now, you
2:40:43are showing the newest post first to the
2:40:45user, but now the product team wants a
2:40:49ranked feed. They don't want you to show
2:40:51the newest post first. They want to show
2:40:55the most relevant post first.
2:40:58What will you change in your design?"
2:41:00And remember in our very first
2:41:03clarifying question the interviewer told
2:41:06us to sort the posts by time and we said
2:41:09that a ranking algorithm is a separate
2:41:12problem in itself.
2:41:14So the interviewer is now bringing it
2:41:16back to see if your design can absorb
2:41:19this change.
2:41:21So the first thing you should tell the
2:41:22interviewer is what does not change.
2:41:26We won't change the three tables we had
2:41:28in the database and the Q doesn't change
2:41:31as well. The workers pushing post ids
2:41:35into the follower lists don't change and
2:41:38the post cache doesn't change.
2:41:42So when Allen opens the app, we take the
2:41:45newest 500 post ids from Alen's list. We
2:41:49add the celebrity post to them and we
2:41:52hand all of these candidates to a
2:41:54separate service called the scoring
2:41:57service.
2:41:58This scoring service gives every
2:42:00candidate a score and we sort by that
2:42:03score and then we return the top 50
2:42:07posts to Allen.
2:42:09Ranking or scoring algorithms generally
2:42:12look at how old the post is, how many
2:42:16likes and comments the post has right
2:42:18now and how much Allen interacts with
2:42:21the author of that post. Notice one very
2:42:25very important thing here. We can't
2:42:28really premputee the score because
2:42:30things like comments, likes, and
2:42:32interactions change very frequently.
2:42:36That means a score cannot be precomputed
2:42:39when a new item is posted by someone
2:42:42because the score depends on likes and
2:42:44comments which happen after the post
2:42:46goes live. Therefore, the ranking has to
2:42:50happen at read time and it should happen
2:42:53very quickly because we want to serve
2:42:56the feed almost instantly
2:42:58and that is why we score only a few
2:43:01hundred candidates and not the whole
2:43:03list.
2:43:05But you should also tell the interviewer
2:43:07the cost of this change. The first cost
2:43:10is that every time a user opens the
2:43:13feed, we are running the scoring step.
2:43:16And to compute these scores, we also
2:43:18need the current like and comment counts
2:43:21of these posts.
2:43:23Basically, we are doing a lot of work
2:43:26here which will consume time.
2:43:29The second cost is that the order of
2:43:31posts will keep changing every time the
2:43:33user opens the app because the score of
2:43:36each post keeps changing.
2:43:39Let me show you this with an example.
2:43:42Alan opens his feed and John's post
2:43:45appears at position 5. So Alan sees the
2:43:48post and keeps scrolling.
2:43:51After 2 minutes, Alan refreshes his
2:43:53feed. But in these two minutes, J's post
2:43:57got 200 new likes. So the score of J's
2:44:01post went up. And now J's post is
2:44:05sitting at position two in Allen's feed.
2:44:08So Allen is seeing the same post again
2:44:11after a refresh.
2:44:14This is fine because the interviewer
2:44:16said in the beginning that duplicate
2:44:18post after refresh is acceptable.
2:44:21But in reality, if you don't want to
2:44:23show the same post again, then you have
2:44:26to also track what posts Allan has
2:44:28already seen. And then we don't show
2:44:31those posts again.
2:44:34This is it for the news feed. And one
2:44:36last thing, if an interviewer asks you
2:44:39to design Twitter or the Instagram feed
2:44:42or the Facebook feed, it is the same
2:44:45problem wearing a different name.
2:44:48So everything we discussed here applies
2:44:51directly.
2:44:53Take a second to process all the
2:44:55questions and answers we discussed and
2:44:57then you can move on to the next
2:44:59problem.
2:45:01Now let's try one more lab. In this lab,
2:45:04you'll run a real news feed. When
2:45:07someone posts something, a worker copies
2:45:10that post into every followers feed list
2:45:13ahead of time. So when a follower opens
2:45:16their feed, the new post loads
2:45:19instantly.
2:45:21Go give this lab a try.

About this transcript

This page contains the full transcript of System Design Interview Prep for Beginners (Full Course) by KodeKloud, generated from the public captions YouTube serves with the video. The transcript has 23,662 words across 3,624 segments, with the original timestamps preserved so you can click any line to jump to that moment in the embedded player.

What you can do with it

Use the transcript to take notes, quote the speaker, build a study guide, generate a summary with ChatGPT or Claude via the YouTube Summary tool, or export it as a timed subtitle file with YouTube to SRT. You can also re-open it in the transcriber to translate the transcript into 100+ languages.

Free YouTube transcript tool

YouTube2Text is a free YouTube transcript generator — no signup, no daily limit. Paste any YouTube link and get the full transcript instantly, with timestamps, click-to-jump, translation to 100+ languages, AI prompts for ChatGPT, Claude, and Gemini, and exports to TXT, SRT, VTT, or Markdown.