CAP theorem - Wikipedia

The CAP Theorem in Distributed Systems

• Core Definition: The CAP theorem (or Brewer's theorem) states that a distributed data store can provide at most two of three guarantees simultaneously: Consistency, Availability, and Partition Tolerance.
• The Three Guarantees:
  • Consistency (C): Every read receives the most recent write or an error; all clients see the same data at the same time.
  • Availability (A): Every request to a non-failing node results in a response (though not necessarily the most recent data).
  • Partition Tolerance (P): The system continues to operate despite arbitrary network message loss or delays.
• The Trade-off: Because network partitions are inevitable in distributed systems, designers must choose between Consistency and Availability when a partition occurs.
• Historical Context:
  • Proposed by Eric Brewer in 1998/1999 and presented as a conjecture in 2000.
  • Formally proven as a theorem by Seth Gilbert and Nancy Lynch in 2002.
• Evolution of the Concept:
  • Brewer later clarified that the "two out of three" rule is misleading because it only applies during network partitions; partition recovery techniques allow for better balancing of these goals.
  • The PACELC theorem (2010) extends CAP by addressing trade-offs between latency and consistency even when no network partition exists.
• Database Examples:
  • CP Systems: Often include traditional RDBMS (ACID-focused) and systems like MongoDB or Redis, which prioritize consistency during partitions.
  • AP Systems: Include databases like CouchDB, Cassandra, and ScyllaDB, which prioritize availability.
  • Note: There are no NoSQL databases typically classified as "CA" (Consistent and Available) because they cannot ignore the reality of network partitions.
• Key Distinctions: CAP consistency is distinct from ACID consistency, and CAP availability is distinct from high availability in general software architecture.