CAP Theorem in System Design Interviews

[00:02] take a quick moment to discuss cap theorem specifically in the context of system design interviews and so there's a lot of content on cap theum online I'm sure you've read some of it uh but most of which I find makes it way more

[00:15] daunting than it needs to be and none of which explains particularly well why it matters specifically in the context of a system design interview and so working as the co-founder of hello interview it's shown me just how much confusion

[00:29] there is around this maybe seemingly simple topic uh and so I solve that confusion for you all uh kind of once and for all so if we turn our attention to the Whiteboard we can start with the very basic definition what is

[00:43] Cap theorem well cap theorem states that you can only have two out of three of the following consistency availability and partition tolerance so in a distributed system as is almost always the case in our system design interviews

[00:57] you'll have to choose two out of these three and so consistency we'll get into but consistency at a high level just means that all users see the same data time availability means that every request gets a response whether it's

[01:12] successful or not and then partition tolerance is defined as the system works despite Network failures between nodes now why does this even matter in the first place why do we care about cap theorem and a system design interview

[01:26] going to do is you're going to align on the requir Ms with your interviewer and requirements the features of the system and then the non-functional requirements now when you're going over the non-functional requirements the first

[01:42] thing you should do is start with cap theorem you should ask yourself does this system need to prioritize consistency or availability and the reason that's the question is because if we come back up

[01:54] here to cap theorem partition tolerance in a distributed system is a must so we've chosen one out of our three and now the question that you in a system design interview need to wrestle with is simply do I prioritize consistency in my

[02:07] system or do PRI do I prioritize availability and this ends up being have a significant influence on your design later on in the Deep Dives but one another in the first place why do we have to choose between consistency and

[02:23] look at an example which will hopefully answer that question imagine that you host a website this website has two servers one located this website has two servers one located in the USA and one located in Europe now

[02:36] user a goes to write data to the server that they're connected to located in the United States let's say this data that they're writing is an update to their public profile maybe they're just updating their name once they do so that

[02:48] data is replicated to the server in Europe so that when user B goes to read the public profile of user a they see that latest data the updated name easy that latest data the updated name easy now what happens if this network

[03:02] gets severed for some reason it goes down and more importantly what happens if it goes down uh before we had a chance to replicate that data that updated data from user uh from server a to the server in Europe well at this

[03:18] point we as a system have a decision to make when user B goes to read this data should we a give them an error because this data is now stale and so we don't want them to read stale data or B do we just let them view the stale

[03:35] just let them view the stale data so writing that down in the case of a network failure should we a stop serving the data if we choose that strong consistency if we chose that we can just

[03:50] risk giving them wrong data seeing the old name for a little bit until this is back online and figures itself out uh if that's okay then our system chose availability so what are some examples where we would choose option A we would

[04:04] stop serving data because we prioritized consistency in the context of cap theum well the first option would be if it was like a ticket booking platform either Airlines or events hotels and so imagine that what user a was doing when they

[04:18] wrote was that they were choosing seat 6A in an airplane and then our Network failure broke well user B is looking to book a seat on the same flight and if we showed them that seat 6A was still available when it's not this would be

[04:33] catastrophic it would mean that they could book seat 6A and both user a and the same day thinking that they're going to sit in the same seat obviously a problem so in that case we would choose consistency over availability what about

[04:47] like an inventory system like Amazon imagine that you're down to your last item user a is buying the last toothbrush on Amazon uh if we have our looks they would see that there was one AA ailable and they would buy it too now

[05:01] users that think that they bought it that's catastrophic lastly another common example is financial systems imagine that user a goes to buy a stock and they hit the USA server user B goes to either buy or sell that same stock

[05:17] particularly if it's a low float might have changed depending on the size of this sale in particular and so the order book needs to be kind of up to date and in this case it wouldn't be so we need to choose strong consistency we should

[05:31] show user be in error as opposed to showing them out ofate information now if you don't need strong consistency then you would choose everything else of course this list isn't exhaustive but in the case where

[05:45] case where you can risk stale data this is the overwhelming majority of cases like our first example with profile data so what if user B reads the wrong name for a little period of time who cares so anything like in a social media app a

[06:00] see their post for a while or doesn't see an update to their post no big deal what about a service like Yelp where there's businesses that get reviewed and they're updating their business information and user B is a customer and

[06:15] business information for a couple seconds or maybe up to a minute or so them the business because we want that business then uh you know care that one

[06:27] couple seconds same too with Netflix what if we change the description on a new movie or we update a new movie or we add a movie is doesn't see it for a couple seconds or they see something that's stale or out

[06:41] of date for a couple seconds of course it is and so what it comes down to in over your non-functional requirements you are asking yourself a simple question does this system need strong consistency does it matter that every

[06:55] single user sees the same state of my system at any given time time and if they didn't would it be catastrophic if the answer to that question is yes over availability if the answer to that question is no then you're going to

[07:09] prioritize availability over consistency great you made your decision in your either to prioritize consistency or availability but how does this influence Your Design now you have to go design the system well if you chose strong

[07:22] couple things in mind you might need to implement distributed transactions so if you had for example a cash in a database you need to ensure that those two things remain strongly consistent and so you'll have to guarantee that when a right

[07:37] other implementing a distributed transaction to ensure this you also might limit things to a single node like maybe your database is a single instance if it's a single instance then there can't be these propagation issues right

[07:52] and so you'll do the math and you might say for my airline ticket booking system I have a single database here and that single database is going to be something like a postgress database or a SQL database for which I can issue Atomic

[08:05] views the same data because they're all reading from the same instance we also might need to just accept higher latency right so we're going to have to show users Spinners or something while we're waiting for propagation to happen um

[08:20] between instances and so some example tools or traditional relational database Management Systems your postgress is your sqls spanner offered by Google is a if you have consistency you can't go with nosql many nosql databases offer

[08:36] strong consistency modes Dynamo DB offers one of them um it's controversial to some whether or not this would be the right choice in my opinion it's totally fine now what about if you ended up going with availability well if you go

[08:49] multiple replicas you're going to scale out your system and can have different read replicas and it's okay if there's propagation between those read replicas eventual consist is okay things like CDC change data capture which is by

[09:03] definition eventually consistent is okay to use in your system uh you're going to strong consistency mode but with like multiple availability zones could be the configuration there Technologies like Cassandra uh which are well optimized

[09:17] decisions if you decided to prioritize availability in your system last thing before we wrap up here I have some Nuance to throw at you if you are a want to just stop the video now I don't want things to get confusing if you're

[09:31] senior or up then this is important to know and the important thing to availability or consistency and those things are at odds we can have different parts of our system that prioritize different requirements so to make that

[09:46] clear imagine Ticket Master is a really good example in Ticket Master as we consistency for booking tickets because we can't have double booking we can't same seat but there are other parts of our system for which we should

[10:00] prioritize availability like for example the crud on events so creating updating deleting events if a user goes and updates the event description it's okay if that's eventually consistent uh it's better that people can always view the

[10:14] event and so in a system design interview you could be nuanced here with pertains to cap theorem I'm going to prioritize availability for searching prioritize consistency for booking tickets to events let's look at another

[10:28] example consider Tinder Tinder is a similar case where we need consistency similar case where we need consistency for matching because if user a swiped on me in Europe and then I swipe on them in the United States I want to immediately

[10:41] show the user a match you matched right when you swipe if you're the second person swiping and so I need a consistent view of who swiped of me cool so consistency for matching but when it comes to viewing profile data again if a

[10:53] user went and updated their profile to a different picture or something like this it's okay if I see the old picture for a while couple seconds minutes so be it interviewer I'm going to prioritize availability for viewing profile data

[11:07] and updating profile data but I'm going to prioritize consistency for match data now there's one other thing in this so-called Advanced section that's relevant you'll hear consistency always used and people will just say

[11:21] theorem what they really mean is strong consistency they mean all reads reflect we've been talking about so if you hear consistency in this context just think strong consistency but the reality is there's different levels to consistency

[11:36] into the Nuance of these different levels in your system and so there's also what's called causal consistency and this just ensures that related events appear in the same order and so for example you can't have a comment on

[11:52] a post uh maybe replying to a previous comment right that comes before that comment it's replying to that wouldn't make makes sense so it's okay if these things take a while to come in and not everyone sees all the same comments but

[12:05] nobody should see a comment replying to a previous comment in the inverted order hopefully that makes sense uh a third one here is read your own rights consistency and so this is that I as a user should have a consistent view of

[12:19] what I've just done but other users could see something different and so back to our USA Europe example user a who updated their profile should or else they'll think the system was broken so they need read your rights

[12:32] consistency but the system doesn't need strong consistency because user B in Europe can still see the old thing that's fine and then of course as I've whole interview the lowest level of consistency is that eventual consistency

[12:46] consistency we're not saying our system's not going to be consistent we're just saying that we're okay with eventual consistency we're okay that it's going to take a while for the

[12:58] system to level outed into a consistent state so if you want to go into each of Nuance it can show some senior some staff level thinking when you be specific here all right folks thanks for watching hopefully this was useful let

[13:11] of this new format it ended up being longer than I thought it would be I thought this would be five minutes but uh you know let me know I want to hop in something is a little bit more confusing to folks um as always we got a bunch of

[13:25] great breakdowns on the website hello interview.com a bunch more deep Dives on then actually at the end of this month November 2024 I don't know when you're watching this uh we're going to be launching a bunch more contents kind of

[13:38] in a premium offering so people are always asking for more content the free content will always continue the YouTube will continue um but we will have even more content for those who want to pay for premium so keep an eye on an eye out

[13:50] for that that'll be coming at the end of the month awesome all right folks good the month awesome all right folks good luck with your interviews