CAP and PACELC

Once data lives on several machines, the network will sometimes split them apart. CAP describes what a system must give up during that split. PACELC covers the other case, when nothing is broken but the copies still need to agree.

The big idea

CAP names three properties:

• Consistency (C): every read returns the most recent completed write.
• Availability (A): every request to a working node gets a non-error response.
• Partition tolerance (P): the system keeps running when messages between nodes are dropped.

Say replica X in Virginia cannot reach replica Y in Oregon. A client writes to X and then reads from Y. Y must either return an error (you chose C) or return the old value (you chose A). CAP says you cannot have both during that split.

Walking through it

PACELC says: if there is a Partition, choose A or C; Else, choose Latency or Consistency.

The else branch is the everyday one. Say the replicas are about 70 ms apart, as roughly US East to US West. A write that must reach both coasts before it is acknowledged waits at least that 70 ms round trip.

A system that acknowledges after a local write, and copies in the background, answers in about 1 ms. But a read on the far side may be stale.

Most rows are a setting, not a product. Consistency is a dial you set per request or per table.

Common mistakes

• Treating P as optional. Networks split. A "CA" system is one that has not decided what happens during a split.
• Thinking CAP covers normal operation. CAP says nothing about the 99.99% of time with no partition. The latency cost lives there, and PACELC covers it.
• Calling whole databases "CP" or "AP". One database can offer strong reads and stale reads through different calls.
• Equating the C in CAP with the C in ACID. ACID consistency means the application's invariants hold. It is a different idea.

Check yourself

1. Why is a leader-based database with failover not fully "available" in the CAP sense? During a failover or a split, nodes cut off from the leader return errors, so not every request gets an answer.
2. A write reaches a far-away region in 70 ms. What does a strongly consistent write pay even with no partition? At least the 70 ms round trip, on every write.

Key takeaways

• CAP says that during a partition you choose between consistency and answering every request.
• Partitions are not optional, so the real choice is what the system does when one happens.
• PACELC adds latency: strong consistency costs round trips even when the network is healthy.
• Consistency is usually a per-request setting, not a property of the whole database.

Further learning

Next, see the guarantees between "latest value" and "eventually" in causal and session guarantees.

Martin Kleppmann's essay argues that calling databases CP or AP hides what they actually do.

Please stop calling databases CP or AP (Martin Kleppmann)Please stop calling databases CP or AP — Martin Kleppmann’s blogmartin.kleppmann.com CAP Twelve Years Later: How the "Rules" Have Changed (Eric Brewer)The CAP theorem asserts that any networked shared-data system can have only two of three desirable properties (Consistency, Availability and Partition Tolerance). In this IEEE article, author Eric Brewer discusses how…InfoQ