Skip to content

CAP Theorem

Overview

The CAP Theorem is a fundamental concept in distributed computing that states that a distributed data store can only guarantee two out of three properties:

  • Consistency: Every read receives the most recent write or an error. This means that all nodes in the system have the same data at the same time.  

  • Availability: Every request receives a (non-error) response, without guarantee that it contains the most recent write. This means that the system is always up and running, even if some nodes are down.  

  • Partition tolerance: The system continues to operate despite arbitrary network partitions. This means that the system can still function even if some nodes are unable to communicate with each other.  

The CAP theorem was first introduced by Eric Brewer in 2000, and it was later proven by Nancy Lynch and Seth Gilbert in 2002. It has had a profound impact on the design of distributed systems, and it is essential for anyone who is working with these systems to understand the implications of the theorem.  

Key Points

  • The CAP theorem is a trade-off. You can only choose two of the three properties.  

  • Partition tolerance is generally considered to be a must-have for distributed systems, so the choice is usually between consistency and availability.

  • The best choice depends on the specific requirements of the application. For example, a banking system might prioritize consistency, while a social media site might prioritize availability.  

Examples

  • Consistent and partition-tolerant (CP) systems: These systems prioritize consistency over availability. If a network partition occurs, they may refuse to serve requests until the partition is resolved. Examples include databases like MongoDB and Redis.  

  • Available and partition-tolerant (AP) systems: These systems prioritize availability over consistency. If a network partition occurs, they will continue to serve requests, even if they may not have the most recent data. Examples include databases like Cassandra and DynamoDB.  

Criticisms

The CAP theorem has been the subject of some criticism. Some people argue that it is too simplistic and that it does not take into account all of the factors that are important in distributed systems. Others argue that it is not always clear what the best choice is between consistency and availability.

Despite these criticisms, the CAP theorem remains an important concept in distributed computing. It is a useful tool for understanding the trade-offs that must be made when designing distributed systems.