4 ms·

PACELC theorem for distributed databases – improves on CAP theorem

38 points by jph 10y ago

jph 10y ago
I am learning about PACLEC and creating the Wikipedia page. Advice and discussion is welcome here, and I will add to the Wikipedia page. (Or you can edit it as you like)
- rdtsc 10y ago
  Thanks for sharing! See my other comment. It seems the title should be PACELC. From paper: "PACELC (pronounced “pass-elk”)..."
kevindeasis 10y ago
I'm pretty sure rethinkDB fans and datastore fans would love to have their database included in that list ;)
graup 10y ago
PACLEC is pretty old. I wonder what the next thing will be? Anyone have some recent papers?
rdtsc 10y ago
> whereas CAP is only relevant in the arguably rare case of a network partition." Isn't it ambiguous in a system when and if a partition occurs? At least I have seen 2 sides of the partition disagree if a partition occurs and when it occurs. I have seen clients see the server, but servers don't see each other (yeah that was horrible...). It seems the idea in the wiki (and paper) is to assume code is operating in this binary fashion -- partitioned mode vs un-partitioned mode. Which implies somehow all sides will immediately know if a partition happens and switch modes. If that is the assumption, I think it is impractical. > tradeoff of replicated systems is a major oversight [in CAP] Usually the way distributed algorithms work, if they are implemented to pick A in case of a partition, they are already working in a certain way that will also pick E in case of PACELC. If they are implemented to pick C in case of a partition they will also be implemented to pick C for PACELC. The provided table shows that pattern in 5/7 cases, most pretty solid databases (Dynamo, Cassandra, Riak, Volt, Megastore). And is disproved for 2 cases (MongoDB and PNUTS). So I don't know.... Based on what I've read and seen, I wouldn't trust MongoDB with any distributed systems claims. It had a history of terrible default (un-acknowledged writes) and also terribly failing Aphyr's Knossos check. And I don't know much about PNUTS. > [Title] PACLEC theorem for distributed databases – improves on CAP theorem (wikipedia.org) It is "PACELC" according to the paper not "PACLEC" it seems. Though, granted PACLEC is more fun to say so maybe the paper can backronym that in.
- grogers 10y ago
  Yeah, PCEL and PAEC are the weird cases. If you are going to operate inconsistently when there isn't a partition, why would you strengthen your guarantee when there is a partition? It seems like there might theoretically be some useful system in that space, but I have no idea what it would look like. Detecting the partition and switching modes will probably have false positives and false negatives, so it wouldn't be predictable what behavior you would get. And PAEC seems like a system that usually is consistent but then throws data away during a partition (but it accepts all your writes!). Systems where the worst case behavior is weaker than the ordinary case typically have lots of surprising behavior in that worst case. Similar to CAP where you can't choose CA, I don't know why you'd choose either of these weird cases in PACELC.
  - rdtsc 10y ago
    Exactly, I suspect it might be a problem with what is advertised vs lack of trust that they actually implement that model. Aphyr showed for example that in large majority distributed db's claims in regards to CAP differ greatly from reality. MongoDB was one example that did particularly bad. Don't know much about PNUTS so can't comment on that one.
ageek123 10y ago
Shouldn't it be PACELC?
- dang 10y ago
  Typo. Fixed.
phamilton 10y ago
Isn't the ELC side quite often a runtime choice? Wouldn't reading from a replica be EL even if reading from the master is consistent? Perhaps that doesn't work both ways. An EL system can't choose to be EC. (Except for consistent reads in Cassandra/Dynamo/Riak, which certainly trade latency for consistency...)

38 points by jph 10y ago

jph 10y ago

I am learning about PACLEC and creating the Wikipedia page. Advice and discussion is welcome here, and I will add to the Wikipedia page. (Or you can edit it as you like)

rdtsc 10y ago
Thanks for sharing! See my other comment. It seems the title should be PACELC. From paper: "PACELC (pronounced “pass-elk”)..."

kevindeasis 10y ago

I'm pretty sure rethinkDB fans and datastore fans would love to have their database included in that list ;)

graup 10y ago

PACLEC is pretty old. I wonder what the next thing will be? Anyone have some recent papers?

rdtsc 10y ago

> whereas CAP is only relevant in the arguably rare case of a network partition." Isn't it ambiguous in a system when and if a partition occurs? At least I have seen 2 sides of the partition disagree if a partition occurs and when it occurs. I have seen clients see the server, but servers don't see each other (yeah that was horrible...). It seems the idea in the wiki (and paper) is to assume code is operating in this binary fashion -- partitioned mode vs un-partitioned mode. Which implies somehow all sides will immediately know if a partition happens and switch modes. If that is the assumption, I think it is impractical. > tradeoff of replicated systems is a major oversight [in CAP] Usually the way distributed algorithms work, if they are implemented to pick A in case of a partition, they are already working in a certain way that will also pick E in case of PACELC. If they are implemented to pick C in case of a partition they will also be implemented to pick C for PACELC. The provided table shows that pattern in 5/7 cases, most pretty solid databases (Dynamo, Cassandra, Riak, Volt, Megastore). And is disproved for 2 cases (MongoDB and PNUTS). So I don't know.... Based on what I've read and seen, I wouldn't trust MongoDB with any distributed systems claims. It had a history of terrible default (un-acknowledged writes) and also terribly failing Aphyr's Knossos check. And I don't know much about PNUTS. > [Title] PACLEC theorem for distributed databases – improves on CAP theorem (wikipedia.org) It is "PACELC" according to the paper not "PACLEC" it seems. Though, granted PACLEC is more fun to say so maybe the paper can backronym that in.

grogers 10y ago
Yeah, PCEL and PAEC are the weird cases. If you are going to operate inconsistently when there isn't a partition, why would you strengthen your guarantee when there is a partition? It seems like there might theoretically be some useful system in that space, but I have no idea what it would look like. Detecting the partition and switching modes will probably have false positives and false negatives, so it wouldn't be predictable what behavior you would get. And PAEC seems like a system that usually is consistent but then throws data away during a partition (but it accepts all your writes!). Systems where the worst case behavior is weaker than the ordinary case typically have lots of surprising behavior in that worst case. Similar to CAP where you can't choose CA, I don't know why you'd choose either of these weird cases in PACELC.
- rdtsc 10y ago
  Exactly, I suspect it might be a problem with what is advertised vs lack of trust that they actually implement that model. Aphyr showed for example that in large majority distributed db's claims in regards to CAP differ greatly from reality. MongoDB was one example that did particularly bad. Don't know much about PNUTS so can't comment on that one.

ageek123 10y ago

Shouldn't it be PACELC?

dang 10y ago
Typo. Fixed.

phamilton 10y ago

Isn't the ELC side quite often a runtime choice? Wouldn't reading from a replica be EL even if reading from the master is consistent? Perhaps that doesn't work both ways. An EL system can't choose to be EC. (Except for consistent reads in Cassandra/Dynamo/Riak, which certainly trade latency for consistency...)