Lecture
The CAP theorem (also known as Brewer's theorem) is a heuristic statement that any implementation of distributed computing can provide no more than two of the following three properties:
The acronym CAP in the name of the theorem is formed from the first letters of the English names of these three properties.
The principle was proposed by Eric Brewer, a professor at the University of California, Berkeley, in July 2000 and subsequently gained wide popularity and recognition among distributed computing specialists . The NoSQL concept, within which distributed non-transactional database management systems are created, often uses this principle as justification for the inevitability of giving up data consistency . However, the CAP theorem is criticized by many scientists and practitioners for the looseness of its interpretation and even for being inaccurate in the sense in which it is commonly understood in the community.
In 2002, Seth Gilbert and Nancy Lynch of the Massachusetts Institute of Technology devised formal models of asynchronous and synchronous distributed computing, within which they demonstrated that the CAP theorem holds when the nodes of a distributed system lack synchronization (a shared clock), and showed the fundamental possibility of a trade-off in partially synchronous systems[10]. In this work, «consistency» in the sense of the CAP theorem is correlated with the fulfillment of the first two ACID requirements — atomicity and consistency. Subsequently, many practitioners cited this work as proof of the CAP theorem [11] .
From the standpoint of the CAP theorem, distributed systems fall into three classes depending on which pair of the three possible properties is practically supported — CA, CP, and AP.
In a system of the CA class, data is consistent across all nodes and availability is ensured, while the system sacrifices partition tolerance. Such systems are possible based on technology software that supports transactionality in the ACID sense; examples of such systems can be solutions based on clustered database management systems or a distributed LDAP directory service[12].
A system of the CP class ensures a consistent result at every moment and is able to function under partitioning, but achieves this at the expense of availability: it may fail to respond to a request. Partition tolerance requires ensuring that changes are duplicated across all nodes of the system, and in this connection it is noted that it is practically expedient to use distributed pessimistic locks in such systems to preserve integrity[13].
In a system of the AP class, consistency is not guaranteed, but the conditions of availability and partition tolerance are met. Although systems of this kind have been known long before the CAP principle was formulated (for example, distributed web caches or DNS)[14], the growth in popularity of solutions with this set of properties is specifically linked to the spread of the CAP theorem. Thus, most NoSQL systems fundamentally do not guarantee data consistency, and cite the CAP theorem as the motive for this limitation . The task in building AP systems becomes ensuring some practically reasonable level of data consistency; in this sense, AP systems are described as «eventually consistent» (eventually consistent)[15] or as «weakly consistent» (weak consistent)[16].
In the second half of the 2000s, an approach to building distributed systems was formulated in which the requirements of consistency and availability are not fully met, named with the acronym BASE (from Basically Available, Soft-state, Eventually consistent — basic availability, soft state, eventual consistency), with this approach being directly contrasted with ACID[17]. Basic availability refers to an approach to application design such that a failure in some nodes leads to a denial of service only for a small fraction of sessions, while availability is preserved in most cases[18]. Soft state implies the possibility of sacrificing long-term storage of session state (such as intermediate query results, navigation information, and context), while focusing on committing updates only for critical operations. Eventual consistency, interpreted as the possibility of data inconsistency in some cases, but with consistency achieved within a practically reasonable time, is the subject of a significant body of independent research
Comments