RIP CAP Theorem, time for a new hat?


Architecture, Database, Distributed Systems, Software, Technology / Thursday, March 1st, 2018

“Why should anyone be frightened by a hat?”

Antoine de Saint-Exupéry, The Little Prince

CAP Theorem is one of those concepts that is fundamental in classifying the behavior of shared data storage  in distributed systems. It has been around for about two decades now and during this time it sure has had a bumpy ride. The most common and also the most widely adopted understanding of the CAP theorem is something along the lines of “Out of the trio of Consistency, Availability and Partition Tolerance, you only get to pick any 2 of them”. So this boils down to a system being one of :

  • CA – Consistent and Available, but not Partition tolerant
  • CP – Consistent and Partition tolerant, but not Available
  • AP – Available and Partition tolerant, but not Consistent

That is easy enough to comprehend (at a high and abstract level), remember and quickly reason about when trying to make choices and trade-offs. Thus CAP theorem has been very popular and you can see a reference to it in most database related literature. From a quick online scan, you can see that the majority of developers also use this same level of abstractness and comprehension.

I was in this same category until recently, but then I came across this interesting paper: A Critique of the CAP Theorem by Martin Klepmann. This led me down the road of serial binge reading of other references, blogs, papers etc. It’s akin to pulling on a loose thread – you can’t stop midway (at least I can’t), you have to pull it all the way through, until it unravels.

The result of it all was a long unraveling for me. I therefore wanted to document my thoughts in this post – to clear my understanding and to serve as a future reference for myself. I write below my interpretation and the main takeaways. Here we go:

I am convinced that CAP theorem is really not a good way to reason about complex distributed data stores. It is only applicable to a narrow and strict definition of consistency (Linearizability), availability, partitions and not very practical in current systems. It also ignores nuances when it comes to providing consistency and availability both in the presence of partitions and in its absence.

The CAP theorem makes it seem like as though you have a choice in being partition intolerant, i.e not accepting of network failures, as in the case of a CA system. However the reality is that network failures are a fact of life for distributed systems, the more nodes, the more the probability of failure. So not accepting that reality is just not a practical choice. Distributed systems, by their very nature have to tolerate failures, so the choice of your system being ‘P’ out of the trio is already made. You are now left with a choice of either being Consistent (CP) or being Available (AP).

So the CAP theorem is better re-framed as capable of being both consistent and available in the absence of partitions, but either consistent or available in the presence of partitions. The consistency and availability in practice are on a continuum, depending on several factors and do not always reflect the strict definitions laid out in CAP.

Another issue with CAP is that it ignores one of the most fundamental characteristics of distributed systems – that of latency of operations.  Latency can affect both availability and consistency of distributed data and  therefore should be an important evaluation factor. In my opinion this factor is perhaps even more important than network failures which in practice are relatively rare, but latency can potentially affect every operation. This next paper discusses exactly this aspect. As an alternative to CAP, in the paper Consistency Tradeoffs in Modern Distributed Database Design, the author Daniel Abadi presents a proposal called the PACELC which expands to:

If there is a partition (P) how does the system tradeoff between availability and consistency (A and C); else (E) when the system is running as normal in the absence of partitions, how does the system tradeoff between latency (L) and consistency (C)?

The author emphasizes the importance of taking latency into consideration during normal operations:

Ignoring the consistency/latency tradeoff of replicated systems is a major oversight, as it is present at all times during system operation.

The gist of it is that for systems that aim to provide high availability, the latency has to be contained to a minimum, especially so when the data is geographically replicated across WANs. Strong consistency guarantees (irrespective of the approach taken to implement it) increase latency and hence for such systems, it necessitates a tradeoff between consistency and latency.

Further refining on latency tradeoffs, the first paper argues that availability should also be modeled in terms of operational latency. To that end they propose the a ‘delay sensitivity‘ framework. It is based on this question – how does network latency affect the operational latency at different levels of consistency? Assuming the lower bound on the operational latency to be a function of the network delay d they summarize the results as in the table below.

Consistency LevelWrite LatencyRead Latency
LinearizabilityO(d)O(d)
Sequential consistencyO(d)O(1)
Causal ConsistencyO(1)O(1)
Lowest possible operation latency at various consistency levels, as a function of network delay d

 

The process by which they arrived at these results for each of these consistency types was derived from existing work and is explained in the paper. Looking at the table, operational latency is either independent of network delay (i.e O(1) – a constant) or dependent on network delay (O(d)).  Although the operation latency is dependent on the implementation algorithm, the table establishes theoretical bounds which can be used along the same lines as CAP while considering tradeoffs.

Draft definitions are provided for the characteristics that form the evaluation criteria for the delay-sensitivity framework. I find these to be more appropriate and practical than CAP. Here are the definitions:

  • Availability – the percentage of successful requests (returning a non-error response within a predefined latency bound) over some period of system operation
  • Delay-Sensitive – Dependent on network delay as opposed to delay independent
  • Consistency – A spectrum of consistencies and each should be defined explicitly
  • Network Faults – All kinds of faults (packet loss, node failure, link failure etc.), not just limited to network partitions. Assumes that the system retries lost packets and failed requests, so that all kinds of faults can be modeled in terms of long delays.
  • Fault Tolerance – Used instead of partition tolerance, the P in CAP. The system must specify the fault tolerance threshold and the behavior when faults increase beyond the threshold.

In summary, I feel that although CAP is a good starting point, the new approaches proposed by the papers above are better. They are in the same spirit as CAP but have improved on it by trying to clear the ambiguities and misunderstandings. The most salient point for me though is that modeling in terms of latency just feels more intuitive at the end of the day.

Further Reading:

CAP Twelve Years Later: How the “Rules” Have Changed

Please stop calling databases CP or AP

IEEE Computer issue on the CAP Theorem

You can’t sacrifice partition tolerance

Leave a Reply

Your email address will not be published. Required fields are marked *