‫Welcome to another lecture.
‫In the previous lecture,
‫we learned a few techniques to improve the performance,
‫scalability and availability of our database.
‫A few of those techniques
‫turned our database into a distributed database.
‫So although the details of implementing
‫and managing a distributed database
‫are outside the scope of this course,
‫there is one topic that we,
‫as software architects and system designers,
‫absolutely need to understand.
‫So in this lecture,
‫we're going to talk about the CAP Theorem.
‫We're first going to get the intuition behind this theorem.
‫And later, we will define it more formally
‫using precise terminology.
‫So what is the CAP Theorem all about?
‫The CAP Theorem, which was first introduced
‫by Professor Eric Brewer in the late '90s,
‫states that in the presence of a network partition,
‫a distributed database cannot guarantee
‫both consistency and availability
‫and has to choose only one of them.
‫Let's explain what it means with a more concrete example.
‫Let's imagine that we have a database
‫that we replicated onto multiple computers
‫to provide high availability for our system.
‫For simplicity, let's assume that this is a very simple
‫NoSQL key-value store.
‫Also, let's assume that inside the key-value store,
‫we have a record that represents a counter
‫that multiple services read and increment.
‫So in normal conditions, we have no problem.
‫As long as all those replicas can successfully
‫communicate with each other through the network,
‫any updates to this counter can easily propagate
‫to all the replicas.
‫For example, if Service A incremented the counter
‫on Replica 1 and that update did not make its way
‫to the rest of the replicas yet,
‫and Service B wants to get
‫the most up-to-date value of the counter,
‫it can still get it
‫even though it sends the query to Replica 2.
‫Replica 2 can easily send a message to Replica 1
‫and Replica 3 to check if there were any modifications
‫to the counter value.
‫And if there was an update, then it can update its own copy
‫and also return the most up-to-date value of the counter
‫to Service B.
‫Now it's important to note
‫that the exact method of propagating the new values
‫to all the replicas is a database implementation detail
‫and is not actually that important for the theorem
‫as long as all the replicas can communicate with each other
‫through the network.
‫Now, the problem happens when some replicas
‫in our distributed database become inaccessible to others.
‫For example, because of a network switch problem
‫or some faulty network cables,
‫Replica 1 and Replica 2 can still talk to each other.
‫However, Replica 3 cannot talk
‫to the rest of the replicas
‫and is now isolated from the rest of the database.
‫This type of problem is called a network partition.
‫So now let's imagine what happens
‫if Service A updates the counter
‫maybe even multiple times on Replica 1
‫while Replica 3 has no way to get that update
‫because of that network partition.
‫So when Service B sends a read request to Replica 3,
‫we have two options.
‫The first option favors availability over consistency.
‫With this option, Replica 3 responds to Service B
‫with its own value of the counter
‫knowing that this value may be inconsistent
‫with the rest of the database.
‫The second option favors consistency over availability.
‫In this option, Replica 3 returns an error message
‫to Service B telling it to try again in the future
‫because at the moment, it cannot guarantee
‫that the value it returns is the most up to date
‫and that it's consistent
‫with what the rest of the services see.
‫This is essentially what CAP Theorem states
‫that in the presence of a network partition
‫in our distributed database,
‫we have to choose either consistency or availability,
‫but we cannot provide both simultaneously.
‫It's important to note and it's something that many people
‫tend to have confusion about is that this theorem
‫forces our database to make this choice
‫only when there's a network partition.
‫However, in the majority of the time
‫when there is no network partition
‫and our replicas can freely communicate with each other,
‫there is no tradeoff to be made
‫and we can easily provide both consistency and availability.
‫So now that we have a pretty good understanding
‫of what CAP Theorem is all about,
‫let's define the terms used in this theorem
‫a bit more formally.
‫The C in the CAP Theorem stands for consistency,
‫A stands for availability
‫and P stands for partition tolerance.
‫The definitions for consistency and availability
‫as used in the CAP Theorem are a bit different
‫than the ones we used before throughout the course.
‫In the CAP Theorem,
‫consistency means that every read request
‫receives either the most recent write or an error.
‫In other words, if there are no network issues,
‫a consistent database will return the value of the record
‫that corresponds to the most recent write operation
‫to that particular record.
‫This consistency guarantees that all the clients
‫see the same value at the same time
‫regardless of which instance of the database they talk to.
‫The definition of availability is that every request
‫receives a non-error response without the guarantee
‫that it contains the most recent write.
‫This implies that occasionally,
‫different clients may get different versions
‫of a particular record.
‫Some of them may be stale.
‫But the most important thing when we have availability
‫is that all requests return successfully with a valid value.
‫Now, partition tolerance means that the system
‫continues to operate despite an arbitrary number of messages
‫being lost or delayed by the network
‫between different computers.
‫So with those definitions in mind,
‫let's revisit the CAP Theorem
‫and interpret what it means for us in practice.
‫The CAP Theorem essentially tells us
‫that when we either choose or configure a database,
‫we have to drop one of those three properties.
‫We can have a consistent and available database,
‫but have no partition tolerance.
‫We can choose to have a consistent
‫and partition tolerant database,
‫but if we get into a network partition,
‫we would not be able to provide availability.
‫Or we can prioritize availability and partition tolerance
‫and compromise on consistency.
‫But can we really have a database
‫that guarantees both consistency and availability?
‫Well, network partitions can happen at any time
‫for any distributed database.
‫Even a database that consists of only two replicas
‫running on two separate computers with sufficient time
‫and query volume will encounter a network partition.
‫So the only way we can have a database
‫that guarantees both availability and consistency
‫is one that runs on only one computer.
‫So only with a centralized database,
‫we can avoid network partitions
‫by eliminating network communication entirely.
‫However, it's important to realize
‫that with a high amount of data and query volume,
‫such a database simply cannot scale
‫and provide high enough performance and fault tolerance.
‫So if we do choose to go the distributed route
‫and run multiple replicas of our database
‫on different computers,
‫we have to also choose partition tolerance.
‫And in that case, we have to choose
‫to either drop availability or consistency.
‫So when should we favor consistency over availability?
‫If we go back to the same example of a shared counter,
‫if this counter corresponds to the inventory
‫of a particular item in our online store,
‫then consistency is much more important than availability.
‫The reason for that is, for example,
‫if we're running low on a particular item
‫and we have only one left in stock
‫while two clients are trying to purchase this item,
‫both clients should see the same
‫consistent picture of our inventory.
‫So if the first client
‫completes the purchase before the second,
‫the second client should see immediately
‫that there are no more items left in stock
‫and get an error if he tries to pay for that item.
‫On the other hand, in a different system,
‫that same counter can represent
‫a completely different thing.
‫For example, in a social media system,
‫this counter can represent the number of likes or views
‫for a particular post or video.
‫So it would be inconceivable
‫if a user got an error in the browser
‫just because temporarily he cannot get the most accurate
‫number of likes for a particular post.
‫And it's completely acceptable
‫to see a not so up-to-date number of likes
‫for some duration of time.
‫So in this case,
‫we would definitely favor availability over consistency
‫to go with our distributed database.
‫Now, it's also worth noting that in practice,
‫when it comes to consistency and availability,
‫things aren't completely black and white.
‫In other words, we don't have to choose entirely
‫between availability and no consistency
‫or 100% consistency and no availability.
‫When we configure a distributed database, in most cases,
‫we have a choice of how much availability
‫and how much consistency we need or can tolerate.
‫So it's more of a dial that we can move
‫depending on our requirements.
‫And anytime we move that dial and add more consistency,
‫we get less availability.
‫And if we want more availability, we get less consistency.
‫The CAP Theorem is really one of the most
‫pronounced examples of making tradeoffs
‫when choosing the quality attributes for our system.
‫And it's important to make those tradeoffs correctly
‫in the architectural design phase
‫when we formalize the non-functional requirements.
‫In this lecture, we learned about a very important concept
‫for databases that operate on a high scale.
‫This concept is the CAP Theorem.
‫After getting the intuition for the CAP Theorem,
‫we learned the definitions of consistency,
‫availability and partition tolerance
‫with respect to a distributed database.
‫And later, we formalized the CAP Theorem as a tradeoff
‫between consistency and availability that we need to make
‫in the presence of network partitions.
‫And finally, we talked about the considerations
‫we need to make when we choose
‫between availability and consistency
‫in a distributed database for our use case.
‫I hope to see you soon in the next lecture.