CAP Theorem for System Design Interviews

SystemDesign
Feb 10 · 7 min read

Top 5 YouTube Videos On CAP Theorem

Here’s a list of some YouTube Videos That best explain the CAP theorem:

  1. Learn System design : Distributed datastores | RDBMS scaling problems | CAP theorem
  2. CAP Theorem | Trade offs to choose a Database | System Design Primer | Tech Primers
  3. CAP theorem explained for Frontend Developers
  4. CAP Theorem (Explained) || Why to sacrifice either Consistency, Availability or Partition Tolerance
  5. Cap Theorem — System Design by Coding Simplified

If you are preparing for tech interviews at FANGs, you may want to check out the course Grokking the System Design Interview by Educative.

Understanding the CAP Theorem

When working with distributed systems, you’re often encountered with the need for making trade-offs between two desired network characteristics, availability and consistency, depending on your unique use case. That’s where some basic understanding of the CAP theorem comes in handy. Even after all the advancements in parallel processing and distributed systems, Eric Brewer’s CAP theorem still makes sense today, after 21 years! What is the CAP theorem, what does it state, and where do we need it? Let’s take a look.

A Short History

The CAP theorem is also sometimes called Brewer’s theorem after Eric Brewer, the computer scientist who came up with the concept in the first place. Mr. Brewer presented the ‘conjecture’ in Symposium on Principles of Distributed Computing back in the year 2000. MIT professors, Seth Gilbert and Nancy Lynch, published its formal proof two years later, giving it the status of a ‘theorem’.

What is the CAP Theorem?

So what did Eric Brewer state? What is the CAP theorem?

The CAP theorem states that a distributed database system can at best guarantee 2 out of the 3 desired features: Consistency, Availability, and Partition tolerance. That’s where the name “CAP” comes from.

When designing a distributed system, there are countless databases to choose from, including MySQL, Cloudbase, Oracle, Cassandra, and so many others. An understanding of the CAP theorem makes it simpler to categorize the options and choose the right tool to use in different scenarios.

What are the Three Components of the CAP Theorem?

The three distributed system characteristics that the CAP theorem talks about are consistency, availability, and partition tolerance. What does each one mean?

Consistency is the guarantee that all the clients see the exact same data at the same time, irrespective of the node they connect to.

Each node returns the same, most recent, ‘successful’ data. This means that for the value of a write operation to be regarded as ‘successful’ once it’s performed on a single node, it must be instantly copied to all the nodes.

If a read operation is performed on a consistent system, all the nodes will return the same data, which is the value of the most recent write operation. If the most recent, ‘successful’ write is not available, an error is returned.

High availability in a distributed system means that the system is 100% operational at all times. Any client that makes a request gets a response, even if one or more nodes in the cluster are down.

In simpler words, all operational nodes return a non-error response for all read and write requests within a reasonable time frame. The value they return, may or may not be the most recent write.

So a highly available system will continue operating even in the presence of a node failure.

A partition refers to a break in connection between nodes within a distributed system. It could either mean a loss in connection or a temporary delay in the transfer of messages between two nodes. Partition tolerance means that the system must continue operation despite any number of partitions in the system.

In short, the system does not fail, even if a certain number of messages are being lost or delayed between nodes.

CAP Theorem System Design — How to Make the Trade-Off?

CAP theorem is often misinterpreted in that you can only have two out of the three characteristics at any given time. This is not true, though. The fact is that you can have all three characteristics (consistency, availability, and partition tolerance) as long as there is no network failure.

In other words, it means that partition tolerance is really not an option. Your distributed system needs to be partition tolerant in any case. Upon network failure, you can choose between consistency and availability.

  • If you choose consistency, the system will block all non-sync nodes so that they do not return an out-dated value. These non-sync nodes are not available. All requests to the non-sync nodes are returned with an error. With this choice, you guarantee that the data returned is consistent but you risk availability.
  • If you choose availability, the client will be returned the current value present on the server when a request is made. With this, you guarantee that the system is highly available, but there is no guarantee that the returned value is the most recent write.

Database Types Based On CAP Theorem

So if there’s a choice between two of the three properties in designing systems, our distributed databases are categorized into three types:

CP Database (Consistent and Partition Tolerant)

A CP database does not mean that the system is always unavailable. It only means that the system sacrifices availability in the case of a network partition, but makes sure that consistency and partition tolerance is never compromised. This is achieved by blocking the non-consistent node until the network partition is resolved.

In applications such as banking, eCommerce, user login, or text messages, availability is not as important as consistency. These applications strictly require data consistency. Only the most recent, “successful” write is of value to the client, and not an old version of it. So it’s okay if the system is not available at all times, but if a value is returned by the node, it must be consistent.

  1. MongoDB
  2. Apache Hbase
  3. Couchbase
  4. Redis

AP Database (Available and Partition Tolerant)

An AP database is one that guarantees availability and partition tolerance but will compromise consistency in the event of a network partition. All nodes continue operating in such a system, however, some that are affected by the partition may return an older value of write, different (or inconsistent) from the other nodes. Once the partition is resolved, the most recent write is replicated to each node, and consistency is reestablished.

In the era of big data, AP databases are more practical in many cases than CP databases. In applications such as Facebook and Instagram that work with millions of posts each day, availability is more important than consistency. The system needs to iterate data quickly and scale horizontally.

It’s alright for nodes to take some time to sync and return an old value to the client until they do so, but they must be available all the time. This is called eventual consistency, as opposed to strict consistency, since the nodes may take some time, but will eventually replicate the latest copy of the data.

  1. Cassandra
  2. Cosmos DB
  3. Amazon DynamoDB
  4. CouchDB

CA Database (Consistent and Available)

A CA database is consistent and available as long as there’s no network partition. Distributed systems are defined by their ability to have partitions. So the system designer simply cannot ignore partitions to deliver consistency and availability at the same time. While it is discussed in theory, in practice, a CA database can’t exist in distributed systems, apart from relational databases (SQL databases).

Relational databases, such as PostgreSQL, and MySQL are the best examples of CA databases.

  1. IBM DB2
  2. Microsoft SQL Server
  3. Oracle
  4. MYSQL

Certain systems can be configured to operate in either CP or AP mode, depending on your application. Cassandra and Cosmos, for example, give users the option to choose between the guarantee of consistency or availability, depending on what suits the customer’s application best.

NoSQL Databases And The CAP Theorem

The choice between consistency and availability comes when you have to pick a database type for your distributed system. Modern databases are classified between SQL (relational) and NoSQL (non-relational) data structures. NoSQL databases are a more common choice in designing distributed systems because they’re horizontally scalable (unlike SQL databases that are vertically scalable). They’re easy to scale, especially beneficial if the network is growing rapidly, with multiple interconnected nodes.

NoSQL follows two popular consistency models: ACID and BASE. ACID models guarantee consistency over availability. It’s called a ‘strong consistency model’. BASE models, which are the more popular choice of NoSQL systems, guarantee availability over consistency. BASE models offer ‘eventual consistency’.

Slight Difference In The C of ACID and The C of CAP

The C in ACID and the C in CAP are often confused and taken to have the same meaning. However, there’s a slight difference. CAP consistency means that the client is always returned the most recent information.

ACID consistency is about the integrity of data according to some database rules. If there are a set of rules that define a system, no transaction will break these constraints. So it is not exactly the same meaning as implied in the CAP consistency.

Conclusion

Understanding the CAP theorem is essential in choosing the right database when designing distributed systems or microservices-based architecture. Unless you know how to make the suitable trade-offs between different features, it’s hard to achieve an optimally scaled system that can best accommodate the client’s requirements. Hope this post provides enough knowledge to make the correct decisions when choosing distribution databases.

Tech Wrench

Tech tales, anecdotes and musings…

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store