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

The CAP theorem is about three guarantees a distributed system can offer:

  • 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.

CAP is often put as "pick two of the three", but that is misleading. Networks are not reliable, so partitions will happen whether you choose them or not. The actual choice is what to give up while a partition lasts:

During a partition: choose C or A\text{During a partition: choose } C \text{ or } Awhat its symbols mean
  • 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 every read to see the latest write.
  • 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:

If P (Partition)  ⟹  A∨C,Else (E)  ⟹  L∨C\text{If } \mathbf{P} \text{ (Partition)} \implies \mathbf{A} \lor \mathbf{C}, \quad \text{Else } (\mathbf{E}) \implies \mathbf{L} \lor \mathbf{C}what its symbols mean

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.

App servers4× instancesLeader1× instanceRead replicas3× instancesApp servers4× instancesLeader1× instanceRead replicas3× instancesApp servers4× instancesLeader1× instanceRead replicas3× instances
Figure 3

A leader and its read replicas.

Follow a write from the app servers: it goes to the leader, which sends it on to three read replicas, and reads can go to any replica. While the network is healthy, the leader can wait for the replicas before confirming the write (consistent, but slower) or confirm at once (faster, but the replicas are briefly behind): that is PACELC’s else case. If a partition cuts a replica off, it must either refuse reads or answer with data that may be stale: that is the choice CAP describes.

  • App servers: 4 × App server
  • Leader: 1 × Relational database
  • Read replicas: 3 × Read replica
  • App servers sends requests to Leader
  • App servers sends requests to Read replicas
  • Read replicas keeps a copy of Leader

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.
Sources5