The CAP Theorem: Balancing the Big Three in Distributed Databases

The CAP theorem, also known as Brewer’s theorem (named after computer scientist Eric Brewer), defines a fundamental trade-off in distributed systems: any distributed data store can provide only two out of three guarantees at any time:

• C: Consistency
• A: Availability
• P: Partition Tolerance

What Do These Terms Mean?

• Consistency (C): Every read receives the most recent write or an error. This means that the data you access is guaranteed to be the latest version, or the system will notify you that something went wrong.
• Availability (A): Every request receives a response, but without the guarantee that it contains the most recent write. In other words, you’ll always get a reply, but it may not always reflect the latest state of the system.
• Partition Tolerance (P): The system continues to operate even if there is a network partition—essentially, when some nodes in the system cannot communicate with others due to network failures.

The CAP Theorem Trilemma: “Pick Two”

A common phrase used to describe the CAP theorem is: “You can only pick two out of the three.” However, this description is a bit of an oversimplification. Here’s the real crux of the matter:

When a network partition occurs (i.e., a logical split between different parts of the network), a system must make a choice:

1. Cancel the operation to maintain data consistency, sacrificing availability.
2. Proceed with the operation to maintain availability, but at the risk of inconsistent data.

In the absence of network partitions (meaning the system is fully connected), it is possible to achieve both consistency and availability simultaneously.

A Closer Look at Partition Tolerance

In practice, especially for distributed systems that operate over a wide area network (WAN), network partitions are considered inevitable. Systems spread across large geographical distances or across continents are more prone to partitions due to network failures or latency issues.

However, for systems operating within a local network (like a single data center or region), the likelihood of network partitions is significantly reduced. In such cases, a system can often be both consistent and available, since partitioning is rare.

But in distributed systems spanning large areas, where partitions are expected, the system must be designed with the CAP trade-offs in mind. If you anticipate that partitions are inevitable, your system will have to forfeit either consistency or availability during those failures.

Conclusion

The CAP theorem is a powerful framework that forces us to acknowledge and navigate the inherent trade-offs in distributed system design. Understanding how these three factors—consistency, availability, and partition tolerance—interact allows engineers to make informed decisions based on their system’s requirements and the expected network conditions.

In the end, the key takeaway is that in distributed systems, especially those operating globally, the reality of network partitions means that we must carefully balance between consistency and availability depending on what matters most for the application.

Reference

• Inside Cloud Spanner and the CAP Theorem