Improve Article
Save Article
Like Article
Improve Article
Save Article
Like Article
The CAP theorem, originally introduced as the CAP principle, can be used to explain some of the competing requirements in a distributed system with replication. It is a tool used to make system designers aware of the trade-offs while designing networked shared-data systems.
The three letters in CAP refer to three desirable properties of distributed systems with replicated data: consistency (among replicated copies), availability (of the system for read and write operations) and partition tolerance (in the face of the nodes in the system being partitioned by a network fault).
The CAP theorem states that it is not possible to guarantee all three of the desirable properties – consistency, availability, and partition tolerance at the same time in a distributed system with data replication.
The theorem states that networked shared-data systems can only strongly support two of the following three properties:
- Consistency –
Consistency means that the nodes will have the same copies of a replicated data item visible for various transactions. A guarantee that every node in a distributed cluster returns the same, most recent and a successful write. Consistency refers to every client having the same view of the data. There are various types of consistency models. Consistency in CAP refers to sequential consistency, a very strong form of consistency.
- Availability –
Availability means that each read or write request for a data item will either be processed successfully or will receive a message that the operation cannot be completed. Every non-failing node returns a response for all the read and write requests in a reasonable amount of time. The key word here is “every”. In simple terms, every node (on either side of a network partition) must be able to respond in a reasonable amount of time.
- Partition Tolerance –
Partition tolerance means that the system can continue operating even if the network connecting the nodes has a fault that results in two or more partitions, where the nodes in each partition can only communicate among each other. That means, the system continues to function and upholds its consistency guarantees in spite of network partitions. Network partitions are a fact of life. Distributed systems guaranteeing partition tolerance can gracefully recover from partitions once the partition heals.
The use of the word consistency in CAP and its use in ACID do not refer to the same identical concept.
In CAP, the term consistency refers to the consistency of the values in different copies of the same data item in a replicated distributed system. In ACID, it refers to the fact that a transaction will not violate the integrity constraints specified on the database schema.
Like Article
Save Article
From Wikipedia, the free encyclopedia
In theoretical computer science, the CAP theorem, also named Brewer’s theorem after computer scientist Eric Brewer, states that any distributed data store can provide only two of the following three guarantees:[1][2][3]
- Consistency
- Every read receives the most recent write or an error.
- Availability
- Every request receives a (non-error) 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.
When a network partition failure happens, it must be decided whether to do one of the following:
- cancel the operation and thus decrease the availability but ensure consistency
- proceed with the operation and thus provide availability but risk inconsistency.
Thus, if there is a network partition, one has to choose between consistency or availability. Note that consistency as defined in the CAP theorem is quite different from the consistency guaranteed in ACID database transactions.[4]
Eric Brewer argues that the often-used «two out of three» concept can be somewhat misleading because system designers need only to sacrifice consistency or availability in the presence of partitions, but that in many systems partitions are rare.[5][6]
Explanation[edit]
No distributed system is safe from network failures, thus network partitioning generally has to be tolerated.[7][8] In the presence of a partition, one is then left with two options: consistency or availability. When choosing consistency over availability, the system will return an error or a time out if particular information cannot be guaranteed to be up to date due to network partitioning. When choosing availability over consistency, the system will always process the query and try to return the most recent available version of the information, even if it cannot guarantee it is up to date due to network partitioning.
In the absence of a partition, both availability and consistency can be satisfied.[9]
Database systems designed with traditional ACID guarantees in mind such as RDBMS choose consistency over availability, whereas systems designed around the BASE philosophy, common in the NoSQL movement for example, choose availability over consistency.[5]
History[edit]
According to University of California, Berkeley computer scientist Eric Brewer, the theorem first appeared in autumn 1998.[5] It was published as the CAP principle in 1999[10] and presented as a conjecture by Brewer at the 2000 Symposium on Principles of Distributed Computing (PODC).[11] In 2002, Seth Gilbert and Nancy Lynch of MIT published a formal proof of Brewer’s conjecture, rendering it a theorem.[1]
In 2012, Brewer clarified some of his positions, including why the often-used «two out of three» concept can be somewhat misleading because system designers only need to sacrifice consistency or availability in the presence of partitions; partition management and recovery techniques exist. Brewer also noted the different definition of consistency used in the CAP theorem relative to the definition used in ACID.[5][6]
A similar theorem stating the trade-off between consistency and availability in distributed systems was published by Birman and Friedman in 1996.[12] Birman and Friedman’s result restricted this lower bound to non-commuting operations.
The PACELC theorem, introduced in 2010,[9] builds on CAP by stating that even in the absence of partitioning, there is another trade-off between latency and consistency. PACELC means, if partition (P) happens, the trade-off is between availability (A) and consistency (C); Else (E), the trade-off is between latency (L) and consistency (C).
Blockchain technology often sacrifices immediate consistency for availability and partition tolerance. By requiring a specific number of «confirmations», Blockchain consensus algorithms are basically reduced to eventual consistency. [13]
See also[edit]
- Fallacies of distributed computing
- PACELC theorem
- Paxos (computer science)
- Raft (computer science)
- Zooko’s triangle
References[edit]
- ^ a b Seth Gilbert and Nancy Lynch, «Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant web services», ACM SIGACT News, Volume 33 Issue 2 (2002), pg. 51–59. doi:10.1145/564585.564601.
- ^ «Brewer’s CAP Theorem», julianbrowne.com, Retrieved 02-Mar-2010
- ^ «Brewers CAP theorem on distributed systems», royans.net
- ^ Liochon, Nicolas. «The confusing CAP and ACID wording». This long run. Retrieved 1 February 2019.
- ^ a b c d Eric Brewer, «CAP twelve years later: How the ‘rules’ have changed», Computer, Volume 45, Issue 2 (2012), pg. 23–29. doi:10.1109/MC.2012.37.
- ^ a b Carpenter, Jeff; Hewitt, Eben (July 2016). «Cassandra: The Definitive Guide, 2nd Edition [Book]». www.oreilly.com. Archived from the original on 2020-08-07. Retrieved 2020-12-21.
In February 2012, Eric Brewer provided an updated perspective on his CAP theorem [..] Brewer now describes the «2 out of 3» axiom as somewhat misleading. He notes that designers only need sacrifice consistency or availability in the presence of partitions, and that advances in partition recovery techniques have made it possible for designers to achieve high levels of both consistency and availability.
- ^ Kleppmann, Martin (2015-09-18). «A Critique of the CAP Theorem». Apollo — University of Cambridge Repository. arXiv:1509.05393. Bibcode:2015arXiv150905393K. doi:10.17863/CAM.13083. S2CID 1991487. Retrieved 24 November 2019.
- ^ Martin, Kleppmann. «Please stop calling databases CP or AP». Martin Kleppmann’s Blog. Retrieved 24 November 2019.
- ^ a b Abadi, Daniel (2010-04-23). «DBMS Musings: Problems with CAP, and Yahoo’s little known NoSQL system». DBMS Musings. Retrieved 2018-01-23.
- ^ Armando Fox and Eric Brewer, «Harvest, Yield and Scalable Tolerant Systems», Proc. 7th Workshop Hot Topics in Operating Systems (HotOS 99), IEEE CS, 1999, pg. 174–178. doi:10.1109/HOTOS.1999.798396
- ^ Eric Brewer, «Towards Robust Distributed Systems»
- ^ Ken Birman and Roy Friedman, «Trading Consistency for Availability in Distributed Systems», April 1996. hdl:1813/7235.
- ^ Bashir, Imran. (2018). Mastering blockchain. Birmingham, England: Packt Publishing. p. 41. ISBN 978-1-78883-904-4.
External links[edit]
- CAP Twelve Years Later: How the «Rules» Have Changed Brewer’s 2012 article on conflict-free replicated data types (CRDT)
- Spanner, TrueTime and the CAP Theorem
- A Critique of the CAP Theorem
- Please stop calling databases CP or AP Kleppmann’s 2015 blog post corresponding with the publication of «A Critique of the CAP Theorem»
Have you ever seen an advertisement for a landscaper, house painter, or some other tradesperson that starts with the headline, “Cheap, Fast, and Good: Pick Two”?
The CAP theorem applies a similar type of logic to distributed systems—namely, that a distributed system can deliver only two of three desired characteristics: consistency, availability, and partition tolerance (the ‘C,’ ‘A’ and ‘P’ in CAP).
A distributed system is a network that stores data on more than one node (physical or virtual machines) at the same time. Because all cloud applications are distributed systems, it’s essential to understand the CAP theorem when designing a cloud app so that you can choose a data management system that delivers the characteristics your application needs most.
The CAP theorem is also called Brewer’s Theorem, because it was first advanced by Professor Eric A. Brewer during a talk he gave on distributed computing in 2000. Two years later, MIT professors Seth Gilbert and Nancy Lynch published a proof of “Brewer’s Conjecture.”
More on the ‘CAP’ in the CAP theorem
Let’s take a detailed look at the three distributed system characteristics to which the CAP theorem refers.
Consistency
Consistency means that all clients see the same data at the same time, no matter which node they connect to. For this to happen, whenever data is written to one node, it must be instantly forwarded or replicated to all the other nodes in the system before the write is deemed ‘successful.’
Availability
Availability means that any client making a request for data gets a response, even if one or more nodes are down. Another way to state this—all working nodes in the distributed system return a valid response for any request, without exception.
Partition tolerance
A partition is a communications break within a distributed system—a lost or temporarily delayed connection between two nodes. Partition tolerance means that the cluster must continue to work despite any number of communication breakdowns between nodes in the system.
CAP theorem NoSQL database types
NoSQL databases are ideal for distributed network applications. Unlike their vertically scalable SQL (relational) counterparts, NoSQL databases are horizontally scalable and distributed by design—they can rapidly scale across a growing network consisting of multiple interconnected nodes. (See «SQL vs. NoSQL Databases: What’s the Difference?» for more information.)
Today, NoSQL databases are classified based on the two CAP characteristics they support:
- CP database: A CP database delivers consistency and partition tolerance at the expense of availability. When a partition occurs between any two nodes, the system has to shut down the non-consistent node (i.e., make it unavailable) until the partition is resolved.
- AP database: An AP database delivers availability and partition tolerance at the expense of consistency. When a partition occurs, all nodes remain available but those at the wrong end of a partition might return an older version of data than others. (When the partition is resolved, the AP databases typically resync the nodes to repair all inconsistencies in the system.)
- CA database: A CA database delivers consistency and availability across all nodes. It can’t do this if there is a partition between any two nodes in the system, however, and therefore can’t deliver fault tolerance.
We listed the CA database type last for a reason—in a distributed system, partitions can’t be avoided. So, while we can discuss a CA distributed database in theory, for all practical purposes a CA distributed database can’t exist. This doesn’t mean you can’t have a CA database for your distributed application if you need one. Many relational databases, such as PostgreSQL, deliver consistency and availability and can be deployed to multiple nodes using replication.
MongoDB and the CAP theorem
MongoDB is a popular NoSQL database management system that stores data as BSON (binary JSON) documents. It’s frequently used for big data and real-time applications running at multiple different locations. Relative to the CAP theorem, MongoDB is a CP data store—it resolves network partitions by maintaining consistency, while compromising on availability.
MongoDB is a single-master system—each replica set (link resides outside ibm.com) can have only one primary node that receives all the write operations. All other nodes in the same replica set are secondary nodes that replicate the primary node’s operation log and apply it to their own data set. By default, clients also read from the primary node, but they can also specify a read preference (link resides outside ibm.com) that allows them to read from secondary nodes.
When the primary node becomes unavailable, the secondary node with the most recent operation log will be elected as the new primary node. Once all the other secondary nodes catch up with the new master, the cluster becomes available again. As clients can’t make any write requests during this interval, the data remains consistent across the entire network.
Cassandra and the CAP theorem (AP)
Apache Cassandra is an open source NoSQL database maintained by the Apache Software Foundation. It’s a wide-column database that lets you store data on a distributed network. However, unlike MongoDB, Cassandra has a masterless architecture, and as a result, it has multiple points of failure, rather than a single one.
Relative to the CAP theorem, Cassandra is an AP database—it delivers availability and partition tolerance but can’t deliver consistency all the time. Because Cassandra doesn’t have a master node, all the nodes must be available continuously. However, Cassandra provides eventual consistency by allowing clients to write to any nodes at any time and reconciling inconsistencies as quickly as possible.
As data only becomes inconsistent in the case of a network partition and inconsistencies are quickly resolved, Cassandra offers “repair” functionality to help nodes catch up with their peers. However, constant availability results in a highly performant system that might be worth the trade-off in many cases.
Microservices and the CAP theorem
Microservices are loosely coupled, independently deployable application components that incorporate their own stack—including their own database and database model—and communicate with each other over a network. As you can run microservices on both cloud servers and on-premises data centers, they have become highly popular for hybrid and multicloud applications.
Understanding the CAP theorem can help you choose the best database when designing a microservices-based application running from multiple locations. For example, if the ability to quickly iterate the data model and scale horizontally is essential to your application, but you can tolerate eventual (as opposed to strict) consistency, an AP database like Cassandra or Apache CouchDB can meet your requirements and simplify your deployment. On the other hand, if your application depends heavily on data consistency—as in an eCommerce application or a payment service—you might opt for a relational database like PostgreSQL.
Related solutions
Cloud databases on IBM Cloud
Explore the range of cloud databases offered by IBM to support a variety of use cases: from mission-critical workloads, to mobile and web apps, to analytics.
IBM Cloudant
IBM Cloudant is a scalable, distributed cloud database based on Apache CouchDB and used for web, mobile, IoT and serverless applications.
DataStax Enterprise with IBM
Get this scalable, highly available, cloud-native NoSQL database built on Apache Cassandra from IBM, your single source for purchase, deployment and support.
Resources
Take the next step
IBM Cloud database solutions offer a complete portfolio of managed services for data and analytics. Using a hybrid, open source-based approach, these solutions address the data-intensive needs of application developers, data scientists and IT architects. Hybrid databases create a distributed hybrid data cloud for increased performance, reach, uptime, mobility and cost savings.
Find your IBM Cloud database solution