CAP Theorem
The CAP theorem is a fundamental concept in distributed computing that defines the limitations of consistency, availability, and partition tolerance in a distributed system. It was proposed by Eric Brewer in 2000 and later proved by Seth Gilbert and Nancy Lynch from MIT. The theorem states that it is impossible for a distributed data store to simultaneously provide more than two out of the following three guarantees:
- Consistency: Every read receives the most recent write or an error.
- Availability: Every request receives a response, without the guarantee that it contains the most recent write.
- Partition Tolerance: The system continues to operate despite an arbitrary number of messages being dropped (or delayed) by the network between nodes.
Let’s delve into each of these properties and understand them with examples.
Consistency
In a consistent system, all nodes see the same data at the same time. Consistency ensures that a read operation will return the value of the most recent write operation causing all nodes to return the same data. A system that has consistency as per the CAP theorem is a system that works as if it were on a single node, no matter how many nodes it actually has.
Example: Consider a distributed database that replicates data across multiple nodes. If a write operation is performed on one node, the same data should be visible if a read operation is performed on any other node. If this is always the case, the system is considered to be consistent.
Availability
Availability ensures that every request receives a response, without the guarantee that it contains the most recent write. In other words, the system is always online and there’s no downtime.
Example: Consider an e-commerce platform like Amazon. It’s crucial for their business that the website is always available to users for browsing and shopping, even if it means showing them slightly outdated data. In this case, the system is highly available.
Partition Tolerance
Partition tolerance means that the system continues to function even if communication between the nodes breaks down. In a partition-tolerant system, the system’s operations are not affected by network failures.
Example: Consider a global banking system with nodes spread across different geographical locations. Even if the network connection between some locations goes down, the system should continue to function and serve customers in the unaffected locations. This system is partition tolerant.
CAP Theorem Trade-off
The CAP theorem states that a distributed system can only guarantee two out of these three properties at the same time. This means that a system can be one of the following as illustrated by
- Consistent and available, but not partition tolerant (CA)
- Available and partition tolerant, but not consistent (AP)
- Consistent and partition tolerant, but not available (CP)
The following image shows how these trade-offs play out.
When there is no partition (nodes are connected correctly), which is often the case, we should have both Availability and Consistency. In reality, however, network partitions can and do occur, so partition tolerance is typically a requirement for any distributed system. This means the real trade-off is between consistency and availability and a distributed database system can provide either consistency or availability when it experiences a network failure.
Example: In the case of a network partition, a CA system would have to refuse to process requests, sacrificing availability to maintain consistency. On the other hand, an AP system would continue to process requests, potentially providing stale data and sacrificing consistency for availability.
In conclusion, the CAP theorem is a tool used to make system design decisions and understand the trade-offs between different properties of distributed systems. It’s important to note that the CAP theorem doesn’t prescribe one ideal type of system, but rather it helps in understanding the limitations and making informed decisions based on the specific needs and constraints of the system.
Classification of SQL and NoSQL databases
CA – Consistent and Available
Single-node databases like MySQL or PostgreSQL can be considered CA systems under normal operation. However, it’s important to note that in the event of a network partition, these systems can’t maintain both consistency and availability, so in a distributed context, they don’t fit perfectly into the CA category.
CP – Consistent and Partition-Tolerant
- Google’s BigTable: It prioritizes consistency and partition tolerance and sacrifices availability. If a network partition separates a client from all the replicas of the data it’s trying to read or write, Bigtable will return an error rather than returning stale data or accepting a write that might not be seen by all replicas.
- HBase: A distributed, versioned, non-relational database modeled after Google’s BigTable. It provides strong consistency for reads and writes.
- MongoDB (in CP mode): MongoDB can be configured to prioritize consistency and partition tolerance over availability.
- ZooKeeper: A high-performance coordination service for distributed applications. It exposes common services – such as naming, configuration management, synchronization, and group services – in a simple interface, relieving the user from the need to program from scratch.
AP – Available and Partition-Tolerant
- DynamoDB: Amazon’s managed NoSQL database prioritizes availability and partition tolerance. It provides eventual consistency but also offers a consistency model for reads.
- Cassandra: Designed to handle large amounts of data across many commodity servers, providing high availability with no single point of failure.
- CouchDB: A database that uses JSON for documents, JavaScript for MapReduce queries, and regular HTTP for its API.
- Riak: A distributed NoSQL key-value data store that offers high availability, fault tolerance, operational simplicity, and scalability.
It is important to remember that the classification of a database system according to the CAP theorem can change based on its configuration. For example, MongoDB and Cassandra can be configured to behave as CP or AP systems, depending on the specific needs of the application.
CAP Theorem Extension
The PACELC theorem, an extension of the CAP theorem, states that in case of a network Partition (P), a distributed system must choose between Availability (A) and Consistency (C), Else (E), even when the system is running normally in the absence of partitions, it has to choose between Latency (L) and Consistency (C).
This means that even when the system is running normally, every write operation involves a choice: wait for the data to be updated on all nodes (consistency) or respond to the write operation as soon as it’s updated on any one node (latency).
Example: In a social media application like Twitter, when a user posts a tweet, the system might choose to display the tweet to the user (and possibly a few others) before it has been propagated to all nodes, thereby favoring latency over consistency.