CAP theorem

from Wikipedia, the free encyclopedia

The CAP Theorem or Brewers theorem states that in a distributed system is impossible to simultaneously the three properties C onsistency ( consistency ) A vailability ( availability ) and P artition Tolerance ( fault tolerance ) guarantee.

properties

Illustration of the CAP theorem

According to the CAP theorem, a distributed system can satisfy two of the following properties at the same time, but not all three.

Consistency (C consistency )
The consistency of the stored data. In distributed systems with replicated data, it must be ensured that all replicas of the manipulated data record are updated after a transaction has been completed. This consistency should not be confused with the consistency from the ACID transactions, which only affects the internal consistency of a database.
Availability (A availability )
The availability in terms of acceptable response times. All inquiries to the system are always answered.
Partition tolerance (P partition tolerance )
The failure tolerance of the computer / server networks. The system continues to operate even if it is partitioned, i.e. That is, when nodes can no longer communicate with each other (e.g. to keep the data consistent with each other). This can occur due to the loss of messages, the failure of individual network nodes or the interruption of connections in the network (the partition of the network).

Since only two of these three requirements can be fully met at the same time in distributed systems, the CAP theorem is often visualized as a triangle in which a specific application can be classified on one of the edges. However, this is inaccurate. Since the CAP theorem relates to distributed systems, a selection without partition tolerance is not part of the consideration. The interpretation is therefore that in the case of network partitioning (i.e. in the event of an error that does not describe the desired system design), one has to decide between the consistency of the data and the availability of the system.

The system properties C, A and P can be seen as gradual quantities, i.e. H. availability is high when the system is responding quickly and low when the system is responding slowly. In terms of consistency, this means that it is either ensured immediately (with strict consistency) or only after a certain time window of the inconsistency ( "BASE" principle (= B asically A , vailable S state often, e ventual consistency ) of many NoSQL Databases).

history

The theorem arose in 2000 as a conjecture made by the computer scientist Eric Brewer at the University of California, Berkeley at the Symposium on Principles of Distributed Computing (PODC) . In 2002, Seth Gilbert and Nancy Lynch of MIT published an axiomatic proof of Brewer's Conjecture, establishing it as a theorem .

Examples

AP - Domain Name System (DNS) or cloud computing

The Domain Name System is the Internet service that is used to resolve symbolic host names and de.wikipedia.orgnumeric IP addresses for TCP / IP communication.

The DNS falls into the AP category . The availability is extremely high, as is tolerance for the failure of individual DNS servers. However, the consistency is not always given immediately: it can sometimes take days until a changed DNS entry is propagated to the entire DNS hierarchy and is thus seen by all clients.

Cloud platforms rely on horizontal scaling , which means that the load is distributed across many nodes that (can) consist of cheap, not necessarily fail-safe hardware. Therefore, a cloud application must be able to show tolerance for the failure of individual nodes. High availability is also required. It follows that a cloud application (at least in large parts) also falls into the AP category . Examples of web applications that do not rely on strict consistency would be social media sites like Twitter or Facebook ; if individual messages do not arrive at all users at the same time, the basic function of the service is not impaired.

Since strict consistency can no longer be guaranteed because of the CAP theorem, but completely inconsistent data management is also not desired, one has to come to terms with weaker consistency conditions. As a counterpart to the ACID principle of relational databases, many NoSQL databases rely on the BASE principle: B asically A vailable, S often State, E ventual consistency. Eventual consistency can be translated well as “final consistency”, which means: the system is again in a consistent state after a certain (as short as possible) period of inconsistency has elapsed.

CA - Relational Database Management System (RDBMS)

The relational databases like DB2 or Oracle strive primarily for consistency.

An RDBMS cluster mostly falls into the CA category . Above all, you strive for the availability and consistency of all nodes. Since they are mostly operated with highly available networks and servers, they do not necessarily have to be good at partitioning. As mentioned above, C , A, and P are gradual quantities.

CP - banking applications

For distributed finance applications such as B. At ATMs, the consistency of the data is the top priority: a withdrawn amount of money must also be reliably debited on the account side, and deposited money must appear on the account. This requirement must also be ensured in the event of disruptions in data traffic (partition tolerance).

Compared to consistency and partition tolerance, availability is of secondary importance ( CP ): In the event of network disruptions, an ATM or other service should be unavailable rather than process incorrect transactions.

See also

Web links

Individual evidence

  1. ^ A b Gilbert, Seth and Lynch, Nancy. "Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services." ACM SIGACT News, v. 33 issue 2, 2002, p. 51-59.
  2. ↑ julianbrowne.com: Brewer's CAP theorem. Retrieved 02-Mar-2010.
  3. ↑ royans.net: Brewers CAP theorem on distributed systems
  4. ^ Akhil Mehra: Understanding the CAP Theorem. In: DZone. DZone, September 6, 2017, accessed September 19, 2018 .
  5. ↑ 12 years later - the rules have changed
  6. ^ Brewer, Eric. Towards Robust Distributed Systems (PDF; 229 kB)