Data Modeling in System Design Interviews with a Meta Staff Engineer

[00:01] modeling. And so this has been requested a ton and it'll be specifically in the context of system design interviews. Now, really importantly, if you stumbled engineer and you're preparing for a dedicated data modeling interview, then

[00:15] you are in the wrong place. uh instead we're going to focus specifically on the need to know as a software engineer preparing for system design interviews interview you're going to be expected to produce at least a minimal data model

[00:29] to the channel, I'm Evan. I'm a former metastaff engineer and I'm the current help candidates just like you prepare for your upcoming interviews. So, check More importantly, head over to the website. Lots of free content, tools,

[00:45] >> Let's start with just the basics. What is data modeling? Well, data modeling is application's data is structured, stored, and how it's related. Now, in

[00:57] practice, this just means that you need to decide what entities or tables exist, how you're going to be able to identify or find them, and how they relate or connect to one another. And so, this video is going to outline exactly how

[01:09] you would do that. The first natural question that people usually ask me when design interview is when should I do the data modeling? And it's a it's a totally fair question. But before I can answer it, let me put it in the context of the

[01:22] if you've watched any of our other videos, you're probably really familiar this is the framework that we suggest you use in order to walk step by step interview. So we suggest that you start

[01:36] outline the core entities or the nouns of your system followed by the API or the interface. Optionally a data flow, a highle design to satisfy the functional requirements and then finally your deep

[01:49] dives to layer on those non-functional requirements um and enrich your design with that added complexity. Now when it comes to data modeling, it usually shows comes to data modeling, it usually shows up in two of these six phases. The first

[02:01] of course is your core entities. This is where you outline the core entities, the nouns, the tables of your system. So that's the four first step of your data model. You know, what are the actual tables that I'm going to be dealing

[02:13] with? And then later on as you get to your highle design in context, as you're satisfying your functional requirements and talking about how each API endpoint will be served or resolved, you're naturally then going to be in the

[02:27] database talking about what sorts of fields, columns, relationships, indexes, etc. are needed in order to satisfy those basic requirements. And that's when you'll end up outlining the remaining factors of your data model. To

[02:42] make that just a little bit more concrete, I'm going to zoom over here and what I have is a full system design interview. This is an interview for an online auction. So went through the requirements. Here are of course those

[02:54] core entities. In the case of an online auction, we list an auction, an item, a bid, and a user. We outlined our API, went through the highle design, and then design, we said, for example, users need to be able to create an auction. And so

[03:07] that comes through to our database, and here's what an auction is. Here's how it get into more detail on this in a moment, uh to items. Here's how it relates to bids and how bids relate to users, etc. We outline this all in

[03:21] users, etc. We outline this all in context when it makes sense in order to API endpoints or functional requirements. Hopefully, that's a useful modeling our data, what you're going to need to do is you're going to need to

[03:34] want to work with. This is because different databases shape how you structure your data and so this choice will ultimately have a strong effect on interviews all the time where candidates have this really strong temptation to

[03:48] choose sometimes the most exotic database type. Um strong suggestion to you resist this. More times than not I would say almost every time the right answer can be justified to be a relational database. Now, unless you

[04:02] have specific detailed experience with another database type um and you know this hands-on experience, if that's not the case for you, then I suggest that you're learning system design either from scratch or you don't have a bunch

[04:17] Postgress. It's really hard for you to go wrong with Postgress. Um now, importantly, this doesn't mean that other databases aren't worth knowing. might be useful, their trade-offs, this can be of course incredibly valuable.

[04:32] interviews and you're learning from scratch, as I said, stick to Postgress. you can see them on the screen here, that are worth knowing. And we're going a high level again because this is foundational to us actually talking

[04:47] relational database. We'll touch on the document database really quickly, key then we'll get into the meat of the actual modeling as we go through this. In order to show how the type of database actually affects your model, uh

[05:00] example that we're going to use here is Instagram, but a really simple Instagram that just has posts, users, and likes. Now, in the case of the relational straightforward. You're going to have three distinct tables. A table for each

[05:15] of those entities that you would have listed in the core entity section. So you'll have a po a user table. This will have a primary key as an ID. And then importantly have a foreign key to the user ID that posted it. Again, more on

[05:30] calling it out so you can see the relationships. And then you'll have a likes table which has foreign keys both to the person doing the liking and to the post ID that is being liked. This structure and the set of relationships

[05:44] is really important because it prevents orphaned data and it makes complex queries really straightforward. Um, and so this is one of the reasons why these relational databases are often times the the go-to choice in system design

[05:56] interviews and really in system design in general. So next up you have document databases like MongoDB or like fire store. And so instead of having separate tables, document databases, they store data as JSON like documents or

[06:09] collections uh with really flexible schemas. That's kind of the key here. So what you see is that I've taken the exact same data that was above in our Postgress or our SQL relational database example and I've displayed it

[06:22] separate tables, we're embedding that post data directly into the user information. So if you want to load John and his posts, you're going to load just one document here and you're going to get all of that. Now we could have done

[06:37] the inverse here too. We could have had posts which had the user information inside of it. that also would have been fine. It's also not the case that a document database forces you to denormalize or embed data like this as

[06:51] I've done here. You could still have three separate collections, a collection for posts, a collection for users, and a collection for likes like we had above. like this with document databases is because they don't have the same level

[07:05] of support for joins traditionally at least that relational databases do. Now, I know as I said that many of you uh correctfully in that are listening may that's not totally true. Plenty of document databases support at least some

[07:18] form of joins." And you're totally right. This is true. But at least in a historical context, this is why you would typically embed more information into a single document um because of that lack of support or lack of as

[07:30] robust support at least for joins as relational databases. Um now, all of system design interview? Well, I'm going to give you a hot take. The main reason that you typically choose a document database is because you want to support

[07:44] schema flexibility. And so, you don't know what you're going to need to add next to this database. And it's expensive to run an entire new migration on a SQL database where you have all of those constraints. So, in the case of a

[07:56] document database, we just add a new key value pair here to all of the documents. It's flexible. It's easy. But I would argue that if you're in a system design narrowly scoped the functional requirements of the design because you

[08:09] only have so much time. You've agreed on that narrow scope with your interviewer and this is what you are now designing for the next 35 to 45 minutes. As a result, almost by definition, there is going to be no evolving schema unless

[08:22] at you and and not many do. So whereas you don't know what requirements are going to come up. Leaving room for that flexibility may make sense in a system design interview. I think it's less

[08:34] relevant and thus it neutralizes one of the main reasons you would choose a database in the first place. So again unless you have vast experience here as many of you may um go with a relational database or Postgress instead. Now key

[08:48] value stores they're the the simplest database model to understand. You simply store values and fetch them by an exact key match. They're just key value pairs. It's just like a giant hashmap where you can only look up things by their key. So

[09:01] for our Instagram example, you might be able to store user data with the key like user ID colon 1 and that's going to give you the value of all the user information. Post data maybe like post colon, you know, 1 2 3. Um, and that's

[09:15] going to give you all of the information for that given post. Key value stores are extremely fast because lookups are so simple like we just described, but they're also pretty limited. And so you can't query like find all posts from the

[09:27] last week or get posts by users that I follow. You can only fetch based on that exact key match. And so this means that you typically again that word which we'll go into more in a moment denormalize heavy and duplicate data

[09:40] thing that we were alluding to in the document database average case. Like if you want to load a bunch of recent posts, well, you might need a key like recent posts that you update every single time someone posts. And now the

[09:54] post data has been duplicated. It's in its normal place with the key post colon one. And it's also added to the list of recent posts. Hopefully, you're following that. Um the obvious example where key value stores are super

[10:07] valuable is for caches like Reddus uh which are absolutely perfect for storing really hot data typically in front of a database like we have in this example here. Uh but there are primary databases like Dynamob that is fundamentally a a

[10:21] key value database but DynamoB adds a bunch of document like features on top. So it's a key value document store somewhere in between the two that we've just described. So why does all this matter? Again, Evan, bring it back to

[10:34] interviews, right? In practice, you're rarely going to use a pure key value store as your primary database. Uh, but you will certainly put it in front of your database as a quick key value cache. And so the example here would be

[10:47] data stored in my database in a relational database, but maybe I need to relational database, but maybe I need to have users feeds. And so those feeds are here. A feed for user 1 2 3 that's its key. And then its value is all of the

[11:02] feed. And you'll notice these are data is here. But this just is a really quick, usually in-memory lookup in order to get a user's feed. So key value store, not in replace of a relational

[11:16] database or whatever your primary database is. Next up, you have wide column databases, which I actually just realized I didn't put into the list above. So apologies for wide column databases. Uh, and I'll admit that these

[11:30] understand just because they break your intuition a little bit, but I think we can explain it fairly simply. The key to the wide column database is what's called column families. And so basically, instead of having fixed

[11:43] columns like we had in relational databases for every single row, they're much more flexible. Each row can have completely different columns, right? Let that sink in. Each row can have completely different columns. And so if

[11:55] we look at our Instagram example here, we have users as our row, user one, and then our column family is posts. Now, within that column family, each post

[12:07] gets its own column. So here's like two additional columns, right, for each of the posts associated with user one. This might seem a little bit funky and it like I said it breaks intuition a little bit, but the motivation here is is

[12:20] actually um maybe quite quite brilliant in that it's meant to support massive write volume. It makes writes incredibly fast uh because you're always just appending new columns rather than updating any existing data. And so

[12:35] there's no need to modify anything that already exists or seek or find the location of something that you need to update the page that you need to update. so because of that wide column databases, they're perfect for data

[12:49] where you have lots of writes coming in quickly and you don't need to query them um in some ordered manner as regularly. So things like time series database, event logging, um or scenario where kind of old data is is rarely updated like

[13:04] IoT sensors is another example, maybe analytic workloads. Those are all places where where wide column databases make sense. As for your your interview, again, unless you see a place where there is a ton of write volume, you're

[13:17] option. Even if there is a ton of right volume, there's other ways to get around it, like putting a queue in front, batching rights. It depends on the problem. Um, but that would be the one place where you want to reach for and

[13:29] learn more about wide column databases. All right, last and and frankly least, at least in my opinion, um you have graph databases. And so graph databases store data as nodes and edges. In our example with Instagram, you have users

[13:44] which are an a node. They have an edge with a relationship of either posted or liked to then what is another node being the post. Uh the reality is my strong never use graph databases in an interview. Um I consider it to be a

[14:00] it only from junior candidates for the most part. they hear a problem that that may support some graph and they immediately think that they need a graph database. Uh classic examples would be like social networks like Instagram,

[14:13] maybe recommendation engines where graphs make sense. But here's a a fun fact for you. Even Facebook models their social graph using MySQL, just a SQL relational database. And so if it's good enough for the largest social network in

[14:28] the world, it's probably good enough for your interview. Uh and thus as has been the reoccurring theme, I would avoid graph databases altogether and just stick with a relational database. Really quick before we continue, let me

[14:41] popular feature on hello interview.com, guided practice. It's an interactive design interviews step by step using that hello interview delivery framework. from the non-functional requirements to the core entities, API routes, all the

[14:56] way through to your highle design and deep dives, drawing on the whiteboard and narrating your response, all while getting real-time feedback on what improve by a model that Stephan and I have spent hundreds of hours tuning.

[15:10] We've expanded the library to 25 of the most common system design interview questions now, and we're constantly adding more. So, candidates absolutely love this feature. I think you will, too. Check it out at hello.com. Link

[15:22] we've covered the database types, let's talk about actually designing the schema. The way that I typically do this in an interview, and I suggest you all of my decisions in three key factors. And now these are three key

[15:36] factors that you would have already come up with and defined either dying during the requirement gathering phase of your interview or during API design. Those three factors are first data volume. This determines where your data is going

[15:48] building a social media media app with millions or billions of users like was the case with Instagram, then you'll probably need to spread that data across multiple systems. This is going to drive how you design your schema. It's going

[16:01] to impact how you design your schema. Second is your access pattern. This usually comes from your API and it's probably the most important factor. So this is how is your data going to be queried? A news feed loading recent

[16:14] posts by followed users suggests that you'll want to denormalize that data or have a specific index so that that query can be really fast. Now, this comes you've defined. You just need to ask yourself what queries you'll need to be

[16:28] able to support at each endpoint and then how do you make them fast enough to have a good user experience. And then the third is the consistency requirement. And so this determines how tightly coupled your data can be.

[16:40] Financial transactions need strong consistency. So you'd keep related data in the same database, but a user's activity feed can handle some eventual that data across separate systems, maybe even like a cache, which we described

[16:53] just a moment ago with the key value store. And so all the techniques that we're about to cover next, we're going to go through a list of techniques now from entities, uh, keys, normalization, indexing, all the things we've sort of

[17:07] been talking about throughout. These are just tools and technique techniques used to address these three key factors. Let's let's talk about structuring your data within tables. And this comes down to understanding two fundamental

[17:20] concepts. First, the primary key and the foreign key. And so a primary key is simply a unique identifier for each record in the table. That simple. You number. Every user in this case of a user table gets exactly one. No two

[17:35] users can have the same one. So in our user table, our user ID would be the primary key and it's just a randomly generated ID or maybe a a monotonically increasing ID. What matters is just that it's unique. Um foreign keys on the

[17:50] other hand, this is how we create relationships between tables. And so it's a field in one table that's going to point to the primary key of another table. In our post table, we would have a user ID as a foreign key. um because

[18:04] this is what is enforcing that relationship that the post belongs to this user, right? Uh okay, why do why do primary keys and foreign keys even matter? Well, primary keys ensure that we can always uniquely identify any

[18:18] given record. And then foreign keys, this is really key or not to overuse the word foreign keys. They enforce what's called referential integrity, which is just a fancy way to say that the database isn't going to let you create a

[18:31] post that references a user that doesn't exist. So you can't create a post uh that was created by an unknown user, right? That's what foreign keys enforce. So in the in the actual interview, you typically want to call out what your

[18:44] keys are. And so for Instagram, it would look like this for us. Users table as we've been discussing is going to have the ID as the primary key and then nothing else in that table. For post you have the ID as the primary key and then

[18:57] the user ID is going to be a foreign key to the ID in the users table. Right? So we know who created this post. When it comes to likes and comments um you're going to have foreign keys to both the user ID. This is who's doing the liking

[19:11] and the post ID uh the post that we are actually liking. And a similar story here for comments, the person who wrote the comment and on which post they wrote that comment, right? So you can see how these relationships end up being

[19:24] maintained. Um, now I see candidates get to memorize and recite whether relationships are one to many or many to many. I think in many of the textbooks they emphasize this as important. In my

[19:40] and it's evident by how confused candidates are usually trying to recite that. Instead, my suggestion is just to focus on defining your foreign keys clearly and then the relationships become obvious. When you say post table

[19:54] has a user ID foreign key that points to users, it's immediately clear that one user can have many posts. When you say a likes table has both user ID and post ID foreign keys, it's clear that users can like many posts and posts can be liked

[20:09] by many users. So don't get caught up in the terminology, I think is my point foreign keys and let the relationships speak for themselves. The last thing here is that you can layer in what are called constraints. These are

[20:22] columns are not null or the values in the columns are not null or that they are unique within the table um or check these enforce the correctness at a database level. And so the really common

[20:34] example is that emails should be unique. And so I put this example down here to design interview. In the interview itself, imagine you're designing your database. You explain that your to your interviewer the database you're going to

[20:48] use in RSO in our case Postgress. And then you might go into the data model. table is going to have a primary key to post ID with a foreign key to the user ID. The users table looks like this with a unique constraint on email, the

[21:02] comments table, etc. You don't always have to write the foreign key for what it's worth. Um I actually don't typically cuz it's implied. Like I have a user ID here and I have a user ID here. it it's pretty clear that there's

[21:15] a foreign key relationship there, but especially if it's like a more junior interview, it's good to to be explicit here. So, you can write your keys and your constraints directly next to the columns as you list them off during your

[21:27] interview, directly alongside your database during the highle design. I've denormalization a couple times now in this video, so it's probably about time that I actually go ahead and define them. Normalization just means that

[21:40] you're storing each piece of information in exactly one location. And so user it's not duplicated across any other tables. This basically prevents anomalies where you might update a user's email in one place but forget to

[21:54] do it in another place. This is going to lead to inconsistent data. Um opposite of this. It's deliberately duplicating data across tables and this is almost always for performance reasons. So in our example here we have

[22:07] is in its normalized form. You can see there's no duplicate data. Now if we always wanted to be able to query the user information with the post information anytime we fetched a post we wanted to know its users. Well, one

[22:21] thing you could do in theory and careful I warn against this a bit but is you This would be the denormalized version over here. So each post has the information about the poster including their username and their email. As

[22:36] pointed out, this means that if you go and update John's email here, but you into some issues. And so the trade-off is pretty clear. Normalization is going is pretty clear. Normalization is going to keep data consistent over here, but

[22:49] join these two tables. Whereas normalization makes reads faster, but it has the potential to create the consistency problems when data changes. And so in a system design interview, my suggestion is that you start with a

[23:03] clean normalized model always like this one. And you only denormalize when you have a specific performance need that can't be met by indexing, which we'll go into in a second, or anything else. Often times, if you are going to

[23:17] denormalize, it's best to put it in the cache. So like we had over here, maybe I have my normalized posts in my comments or posts and users table in that example, but I have a denormalized version that exists in the cache because

[23:31] I'm okay with some eventual consistency in order to make feeding or serving users feeds really quick. So next up, let's let's talk about indexing. Usually the first thing that you're going to do when you need to make data access faster

[23:44] about a second ago, but instead to add indexes. And so indexing is the process structures that help the database find records more quickly than having to scan

[23:56] every row. And so you have an example here of what is a B tree index. I'm not going to go into detail about how it works, but it's a tree. And you can see how instead of scanning to find where user Evan is, we can walk down a tree in

[24:10] order to make this login, right? Instead of O of N. And so we can find the page that has Evan's information and bring it in. TLDDR. Adding an index makes accessing that data faster, but you need to be explicit about which columns

[24:24] you're going to add indexes to. And so for Instagram, we would add indexes that support our most common queries. This would be true of any system design interview. So if we have an API endpoint like get users uh ID posts, so basically

[24:39] get all the posts for a given user, then we need to put an index on user ID on because we want to be able to query posts for all posts by a given user. And this is how we can make that fast. Maybe we want to be able to sort by created ad

[24:54] as well. So we would add an index there. Same thing with comments. We want to be post. That's our query. Well, we should add an index to post ID. If we want to this is actually a less common operation, but if for some bizarre

[25:10] reason it was needed based on your API, you would add an index here, right? And so you can see on the right how your data model, your data schema is evolving during the interview. As you're going through that highle design, you're

[25:24] foreign keys, maybe you're adding some unique constraints. You're specifying which columns have indexes. And this is the final output of the data modeling this is in the context of your full design that would be here. We're just

[25:38] looking at only the database. Um, but that's the key. Work backwards from those APIs. look at each endpoint and ask what query does this need to run and then make sure you have indexes that support those queries efficiently. Last

[25:51] up, we we should mention sharding. So when your data gets too large for a you've done the math and you've determined that all of your data isn't going to fit into a single node, then you need to shard it across multiple

[26:04] machines. And the key is choosing the right partition strategy in order to keep related data together. And so again with our Instagram uh example, let's say we want to shard by post ID. Then posts with ids 0 to 10k might go to this

[26:18] database, 10k to 20k to this, and 20k to 30k this database. But importantly, we put comments in the same database as their corresponding posts since comments always relate to the specific post that the comment is happening on. Now the

[26:34] related data together so that we can avoid what our expensive cross shard joins. If I want to get a post and its comments which is a really common one database. I shouldn't have to get the posts from this and the comments

[26:49] from this, right? And so in your actual interview, what you're going to end up complete our data model by maybe specifying what we're sharting by. And I'm going to put that here. either shart or partition and then similarly the

[27:04] comments table is also going to be sharted by post ID and I would argue that the reason here is to keep related data colllocated on the same database. Uh so golden rule just to summarize shard by your primary access pattern so

[27:17] that you can avoid cross shard queries whenever possible and your choice of shard key effectively uh affects every single query. So think really careful single query. So think really careful about how you'll actually uh access the

[27:30] data. All right, great job first of all for making it to this point. Um, let me want to summarize all the many things that we've talked about so far and try for you guys to go off into your studies. When you're defining the data

[27:43] you're going to largely do this during the highle design. At which point when you're first drawing that database box, you're going to choose a database. This choice impacts how data is stored. Unless you have strong prior opinions or

[27:56] experiences, you should choose a relational database like Postgress. The You're going to write them directly next to the database like this. These should order to satisfy the functional requirements of your system. Don't go

[28:10] overboard here. Just keep it limited to those that are strictly required. Next, you'll add the primary and foreign keys respectively. This is in order to define the constraints and relationships within your data. The fourth thing is that

[28:24] you're going to determine what indexes are needed. This is derived directly outlined. So if you have an API which is going to load all the posts for a given user, well then you should know that you should add an index on user ID in order

[28:37] to make that query efficient. Otherwise, we'd have to read every single row in this table pulling out all of the rows that have the user ID that was specified in the API endpoint. Adding an index will make it quicker. You can continue

[28:49] to label and update your data model by writing index next to it. Next, you'll denormalize. Again, the assumption should be that you always start with purely normalized data and you denormalize only if there is some rare

[29:02] occasion where you need to make things a lot faster by avoiding joins altogether. If you are doing this, it's probably by way of a cache. And so the example for Instagram is that you would add a new cache here which has a denormalized

[29:17] uh news feed. Basically, all the post information that each user needs in the Instagram breakdown, how to design Instagram breakdown on hello.com if you And then lastly, you're going to consider if sharding is needed. This is

[29:32] which can fit into a single database. And if yes, choose a partition key wisely. And that partition key should make sure that there are no cross shard make sure that there are no cross shard joins if at all possible. Now for steps

[29:46] three to six here, this should all be in the context of the three things you defined early in the interview. The necessary access patterns, the data volume, and the consistency requirements. If you're able to do this,

[29:59] portion of the interview. You should feel really happy uh and you can go on and focus on the much more important and interesting things like the deep dives and all else that comes in a system design interview. So, thank you

[30:12] everybody for watching. I hope this was informative. Please leave comments. I'll do my best to respond to as many as I can. Uh like and subscribe. As you guys I'm not going to forget this time. So, please do like and subscribe and let me

[30:25] going to try to continue to pump out videos at an increasing pace, and so I'd from me. All right, take care and best of luck with your upcoming interviews.