Lesson 1.3• 6 min read

Availability, consistency, CAP and PACELC

The mathematical trade-offs of distributed state when networks partition.

What you will learn

State the three guarantees in CAP, and why partition tolerance is not optional.
Tell CP systems from AP systems by what they do during a partition.
Use PACELC to name the trade-off a replicated system makes when there is no partition.

The CAP Theorem

A distributed system can offer only two of these three guarantees at once:

Consistency (C): Every read receives the most recent write or an error.
Availability (A): Every request receives a non-error response, without a guarantee that it contains the most recent write.
Partition tolerance (P): The system continues operating despite messages between nodes being dropped or delayed.

Networks are not reliable, so partitions will happen and a real system must tolerate them. The actual choice is what to give up while a partition lasts:

\text{During a partition: choose } C \text{ or } A

CP systems (e.g., etcd): Nodes cut off from the majority refuse requests (or time out) rather than risk returning stale or conflicting data. In etcd, the minority side of a partition becomes unavailable. Choose CP when the business needs atomic reads and writes.
AP systems (e.g., Cassandra and Riak in their default settings): Every node keeps answering, possibly with stale data, and writes propagate between nodes once the partition heals. Choose AP when eventual consistency is acceptable.

Labels are not absolute. Google's Spanner is technically CP (during some partitions it gives up availability), but its availability is so high that its users can treat it as "effectively CA".

The PACELC Theorem

CAP only describes behavior during network partitions. Daniel Abadi's PACELC adds the trade-off a replicated system faces the rest of the time:

\text{If } \mathbf{P} \text{ (Partition)} \implies \mathbf{A} \lor \mathbf{C}, \quad \text{Else } (\mathbf{E}) \implies \mathbf{L} \lor \mathbf{C}

Even when the network is healthy, keeping replicas consistent means waiting for other nodes before acknowledging a write, which adds latency (L). Acknowledging before the replicas confirm is faster but gives up consistency (C). The default versions of Dynamo, Cassandra and Riak are PA/EL: they give up consistency both during partitions and for lower latency in normal operation.

Figure 3: Multi-node database replication across availability zones with partition boundaries.

Key takeaways

Partitions happen, so the real choice is what to give up while one lasts: consistency or availability.
CP systems such as etcd make the minority side unavailable; AP systems such as Cassandra in its default settings keep answering, possibly with stale data, and catch up after the partition heals.
Even on a healthy network, waiting for replicas before acknowledging a write costs latency: PACELC's "else, latency or consistency".
Labels are not absolute: Spanner is CP, yet available enough to be treated as effectively CA.

Sources

Adapted from The System Design Primer by Donne Martin, licensed under CC BY 4.0. Changes were made.