Improving the PACELC Taxonomy

Daniel Abadi of Yale published a blog article last April criticizing the characterization of distributed storage systems using “you only get two of C, A, and P”. He proposed a new taxonomy with the acronym PACELC, to be read “If P, then trade off A for C; if E, trade off L for C”, with this meaning:

  • When there is a partition, how does the system trade off between:
    • Availability and
    • Consistency
  • Else, when there are no partitions, how does the system trade off between:
    • Latency and
    • Consistency

For example, a system characterized as PA/EL means that in the face of partitions, it favors availability over consistency, and if everything’s working, it favors low latency over consistency.

I think this is moving very much in the right direction, and I hope I can contribute and help develop these ideas a bit.

Problems with the “Proof of the CAP theorem”

The “CAP” characterization has a lot of problems. It is especially poorly applied, if not actually misused, when someone trots out the “proof of the CAP theorem” to show how they were forced into a tradeoff. While the proof is correct, what is proves is too crude to model what we really care about.

I discussed the proof in an earlier post. In the proof, each attribute is problematic:

  1. “Consistency” means the behavior that would have happened on a single server that never crashed and did each operation in serial, which is fine, but lack of consistency means that the system makes no guarantees or representations about the result of an operation whatsoever.
  2. “Available” means that you get an answer “eventually”, but since eventually can mean any amount of time (a trillion years), there’s no practical difference between A and not A.
  3. “Partition-tolerance” is never actually defined in the paper.

“E” implies “A”

The reason the acronym doesn’t need to be “PACELCA” is that if there are no partitions, then the system must be available. Adding an “A” to the second part is redundant. But for me (maybe not for you), putting in the redundant “A” in the “E” case helps me. A PA/EL system is always “available”, and calling it PA/ELA makes it easier for me to see that availability is always there.

How do Availability and Latency relate?

Consider what “highly available” and “low latency” mean. They are not entirely distinct and orthogonal. The only useful meaning of “A” is that the system replies within a maximum latency. It could be something like “response within 10ms at least 90% of the time and within 100ms in any case” rather than a simple deadline. We can call this “fast enough” to meet the system requirements. So availability is about latency.

There is, however, an important practical difference. “Available” refers to a system’s latency related to the amount of time it takes to repair a partition.

To see this, consider two web sites (with human users) that are based on a system that can have partitions:

  • The operators of the system move so quickly that they always fix partitions within 10ms. The system is “available” even in the face of any single partition, without any special mechanism to be “partition tolerant”.
  • The operators of the system move so slowly that it takes them five minutes to fix a partition. If the system has no way to be “partition tolerant”, it’s not available.

Latency (the “L” in PACELC) has nothing to do with repair time, since it only applies when there are no partitions. A web site is far better with a (maximum/average/whatever) latency of 10ms than with 1000ms.

So “A” and “L” are different. But, that said, even if a system meets its “A” (fast enough) requirement, it can be valuable to lower the latency below that requirement. The “PAC” characterization does not take this into account.

PC/EL is confusing

If a system is consistent when there are partitions, then surely it’s also consistent when there aren’t any partitions. If the components work better, the service should not be worse.

At first glance, this seems to mean that “if PC, then EC”. That would mean that PC/EL can’t describe any realistic system, but Prof. Abadi characterizes PNUTS/Sherpa (as originally presented). I’m sure that there isn’t really a paradoxical situation with any real system, but rather that there is a way to misinterpret the PACELC notation. What do PC and EL really mean?

PC means that if a client sends a request when there are partitions that prevent the system from answering promptly and correctly, then the system does not answer, rather than providing an answer that might be incorrect. Indeed, it might not be able to reply at all, since a total failure is a kind of partition, and there just isn’t anybody to send back a reply.

EL means that if a client sends a request, and the system can choose between waiting a longer time to send a consistent answer, versus waiting a shorter time to send an inconsistent answer, it chooses (or tilts toward) the latter.

Loose ends

  • What does “C” really mean? Can’t we say something better than “we don’t guarantee consistency”? Dynamo can give you answers that are not definitive but are very useful, with semantics that the application can understand. What about “eventual consistency”?
  • What about durability? There’s a big difference between some data being temporarily offline versus data being lost forever. Some systems use “commits over a WAN” to replace the use of disks, and then the tradeoff of latency versus correctness, from synchronous to asynchronous commits, is important.
  • Should be distinguish between “available for read” vs. “available for write”? This can come up in, e.g., a master-slaves configuration.

Stay tuned.