CAP Theorem

The CAP theorem states that a distributed data store cannot simultaneously provide all three of: Consistency (every read returns the latest write), Availability (every request receives a response), and Partition tolerance (the system continues to operate despite network splits). Under a network partition, a system must give up either consistency or availability.

What the three properties mean here

• Consistency (C). Specifically linearizability: a global, real-time ordering of operations such that every read sees the most recent write.
• Availability (A). Every request to a non-failing node returns a non-error response, even if no replica is up to date.
• Partition tolerance (P). The system keeps functioning when network messages between nodes are dropped or delayed indefinitely.

The practical reading

In any real distributed system the network can partition, so partition tolerance is not optional. The real choice is between consistency and availability when a partition occurs. Systems are usually described as CP (sacrifice availability) or AP (sacrifice consistency) under partition:

• CP systems: Spanner, etcd, ZooKeeper, CockroachDB, HBase, MongoDB (with majority write concern). Reject requests rather than return stale data.
• AP systems: Cassandra, DynamoDB (default), Riak, CouchDB. Accept writes on either side of the partition and reconcile later.

Beyond CAP: PACELC

PACELC extends CAP by also asking what the system does when there is no partition (Else, choose between Latency and Consistency). Most real systems make tradeoffs in both cases.