The Post-CAP Reading List

Eric Brewer and Daniel Abadi expand our notions of what the real trade-offs are in the CAP theorem.

Flexible positioning between C and A

Eric Brewer discusses the range of options available under CAP in “CAP Twelve Years Later: How the "Rules" Have Changed”. In particular, he notes that designers don’t have to pick exclusively between AP or CP, but can choose a range of flexible options between the two, including limiting operations during a partition to just certain, inviolable operations that will maintain invariants.

Brewer also makes an point regarding latency. In the original CAP paper, a partition is indistinguishable from a high-latency network, since in both cases a node is out of communication with another node for a period of time. This allows for an interesting optimization, that “designers can set time bounds intentionally according to target response times.”

In both cases, latency and operations, Brewer argues that the trade-offs in CAP are actually quite flexible and allow middle-of-the-road choices.

Focus on Latency

Daniel Abadi talks about latency too, but brings it to the forefront of the CAP theorem in “Problems with CAP, and Yahoo’s little known NoSQL system”.

Many programmers have noted that you don’t get a real choice on whether to handle partitions or not, if you allow multiple nodes then you must handle partitions. The correct formulation of CAP isn’t “pick 2 of 3” but “if you have multiple nodes, do you pick availability or consistency?” Where Abaci breaks from Brewer is that he doesn’t treat latency as subset of Partition, instead Abadi adds Latency as a fourth trade-off. Yahoo’s PNUTs database relaxes both Consistency and Availability in exchange for better Latency.

Abaci extends CAP to the unpronounceable PACELC, which stands for: if Partitions, you can choose Availability or Consistency. Elsewise, you can choose Latency or Consistency.

For example, Amazon’s Dynamo (and related systems like Cassandra and SimpleDB) are PA/EL in PACELC --- upon a partition, they give up consistency for availability; and under normal operation they give up consistency for lower latency. Giving up C in both parts of PACELC makes the design simpler --- once the application is configured to be able to handle inconsistencies, it makes sense to give up consistency for both availability and lower latency.

Fully ACID systems are PC/EC in PACELC. They refuse to give up consistency, and will pay the availability and latency costs to achieve it.

However, there are some interesting counterexamples where the C’s of PACELC are not correlated. One such example is PNUTS, which is PC/EL in PACELC. In normal operation they give up consistency for latency; however, upon a partition they don’t give up any additional consistency (rather they give up availability).


(Commenting is closed. Please tweet me at @landedstar instead.)