Hello! Welcome back to our course on database systems.
In our last lesson, we dissected the failure modes of the Two-Phase Commit (2PC) protocol. We saw that in the face of a coordinator crash—a type of network partition—2PC prioritizes correctness by blocking participants. This forces the system to sacrifice availability to guarantee consistency. This dilemma isn't unique to 2PC; it's a fundamental trade-off that every distributed system designer must confront.
Today, we will formalize this trade-off. Our learning outcome is to explain the trade-offs defined by the CAP theorem (Consistency, Availability, Partition Tolerance). First proposed by computer scientist Eric Brewer in 2000, this theorem provides a powerful, high-level framework for reasoning about the design of distributed databases and other large-scale systems. Understanding CAP is essential for making informed architectural decisions.
Introducing the CAP Theorem
The CAP theorem states that it is impossible for a distributed data store to simultaneously provide more than two out of the following three guarantees:
- Consistency (C)
- Availability (A)
- Partition Tolerance (P)
Let's start with an intuitive video that uses a simple ATM example to illustrate what these three properties mean and why they are in tension.
This video from the Distributed Systems Course provides an excellent and easy-to-understand introduction to the CAP theorem using a bank ATM analogy. It clearly demonstrates the choice a system must make between consistency and availability when a network partition occurs.
Please watch the segment from the beginning until 03:59. As you watch, focus on the core dilemma: when the two ATMs can't communicate, what choice must the system designer make, and what are the consequences of that choice for the user?
As the video showed, when a partition happens, the system is forced to make a choice. This is the heart of the theorem. Let's formalize the definitions.
-
Consistency: In the context of CAP, this refers to strong consistency or, more formally, linearizability. It means that every read operation receives the most recent write or an error. To all clients, the system appears to be a single, up-to-date copy of the data. If a client writes a value and a second client reads it immediately after, the second client must see the new value.
-
Availability: Every request made to the system receives a (non-error) response. The system is always up and able to process requests, but there is no guarantee that the response reflects the most recent write.
-
Partition Tolerance: The system continues to function even when communication between nodes is lost or delayed. A "partition" is a network failure that divides the system's nodes into two or more groups that cannot communicate with each other.
In any real-world distributed system built on commodity hardware, network failures are a given. This means Partition Tolerance (P) is not really optional. A system that isn't partition-tolerant would have to halt completely during a network outage, defeating the purpose of a distributed design.
Therefore, the CAP theorem forces a more practical choice for system designers: when a network partition inevitably occurs, do you choose Consistency over Availability (a CP system), or Availability over Consistency (an AP system)?
Visualizing the Trade-off: CP vs. AP Systems
The following diagram provides a great visual summary of this trade-off, categorizing different database systems based on the choice they make.
To make this more concrete, let's look at how this choice manifests in real database systems. The next video from IBM Technology explains the CP and AP models using MongoDB and Apache Cassandra as respective examples.
This video breaks down the 'pick two' rule of the CAP theorem and provides excellent, concrete examples of how real-world databases like MongoDB and Cassandra embody the CP and AP design philosophies.
Watch the segment from 02:18 to 07:00. Pay close attention to the architectural differences described: MongoDB's use of a primary node to ensure consistency (CP), and Cassandra's 'no primary' model that prioritizes availability (AP).
As the video explained:
-
CP (Consistency + Partition Tolerance): When a partition occurs, the system chooses to preserve consistency. To do this, it may have to block requests (become unavailable) on the side of the partition that cannot guarantee access to the most recent data. MongoDB's single-primary architecture is a classic example. If a client can't reach the primary node, it cannot safely perform a write, thus preserving consistency at the cost of availability.
-
AP (Availability + Partition Tolerance): When a partition occurs, the system chooses to remain available. This means every node continues to accept requests. However, since nodes may be out of sync, clients might read stale data. The system aims for eventual consistency, where all replicas will converge to the same state once the partition is resolved. Cassandra's multi-master design allows writes to any node, ensuring high availability even if some nodes are unreachable.
Test your understanding!
Consider two different features of an e-commerce platform:
- Shopping Cart: A user adds items to their cart from their laptop and later wants to see the same items in the cart on their phone.
- Product Stock Inventory: A centralized system that tracks how many units of a popular item are left in the warehouse.
For each feature, would you lean towards a CP or an AP design? Justify your answer.
Show answer
-
Shopping Cart: This system would likely benefit from an AP design. If the user's phone can't sync with the central database for a few seconds, it's better to show a slightly stale (but still usable) cart than to show an error or a loading spinner. The user experience prioritizes availability. The cart can sync up eventually when connectivity is restored.
-
Product Stock Inventory: This system demands a CP design. It is critical that the system maintains a single, correct count of the inventory to avoid overselling the product. If two different parts of the system are partitioned, one part should become unavailable to take orders rather than risk selling the same last item twice. Consistency is more important than 100% availability in this case.
A Critical Perspective on CAP
The CAP theorem is a powerful mental model, but it's not without its critics and nuances. One of the most influential voices in the database world, Michael Stonebraker, has argued that its practical application can be misleading. He suggests that we should carefully consider the type and frequency of failures before blindly sacrificing consistency.
Errors in Database Systems, Eventual Consistency, and the CAP Theorem
This blog post by Michael Stonebraker, a Turing Award-winning database expert, offers a critical perspective on the CAP theorem. He argues that the trade-offs are more complex than the simple 'pick two' mantra suggests.
Please read the post (it's quite short). Focus on Stonebraker's central argument: Why does he believe that choosing AP over CP/CA is often not warranted in modern data center environments? What types of failures does he claim are more common than network partitions?
Stonebraker's main points provide crucial engineering context:
- Partitions are Rare: In a well-managed data center with redundant networking, true network partitions are exceptionally rare.
- Other Failures Dominate: Other issues like software bugs (
Bohr bugs), single-node hardware failures, and application errors are far more common causes of downtime. These errors often force a system to block or fail regardless of its CAP choice. - The "CA" Choice: Given this, Stonebraker argues for CA (Consistency + Availability) systems in many environments. A CA system assumes no partitions. If a partition does happen, the system will block to maintain consistency. This is exactly the behavior of a traditional single-node RDBMS and, as we saw, the behavior of 2PC. The argument is that sacrificing consistency all the time (in an AP system) to handle a rare partition event might not be the best engineering trade-off.
This perspective doesn't invalidate the CAP theorem, but it reframes it. It highlights that the choice is not a simple, one-time decision but a complex engineering trade-off based on your specific infrastructure, application requirements, and tolerance for different failure modes.
Conclusion
Today we explored the foundational CAP theorem, which governs the trade-offs in distributed system design. It provides a vocabulary and framework for reasoning about the hard choices that architects must make.
Key Takeaways:
- The Theorem: A distributed system can only guarantee two of three properties: Consistency, Availability, and Partition Tolerance.
- The Real Choice: Since Partition Tolerance (P) is a necessity in most systems, the primary trade-off is between Consistency (CP) and Availability (AP) during a network failure.
- CP Systems (e.g., MongoDB, systems using 2PC) prioritize correctness. They will become unavailable rather than return incorrect or stale data. This is often required for financial or inventory systems.
- AP Systems (e.g., Cassandra, Amazon's Dynamo) prioritize uptime. They will always respond to requests, even if it means returning stale data. They rely on eventual consistency. This is often acceptable for social media feeds or user profiles.
- Engineering Nuance: The "right" choice is not absolute. It depends on the business needs of the application and the reliability of the underlying network, as argued by experts like Michael Stonebraker.
Preview of the Next Lesson
Having established the high-level architectural trade-offs that govern distributed databases, our next step is to zoom in on how these systems actually execute queries to achieve high performance. In the next lesson, we will explain inter-operator and intra-operator parallelism in a shared-nothing system, exploring the fundamental techniques that allow databases to divide up the work of a single query across many machines.