3 ms·

> A trivial system with these properties is one that replicates every update to all available nodes and requires reads to get matching results from at least hal

by jbellis 17y ago

> A trivial system with these properties is one that replicates every update to all available nodes and requires reads to get matching results from at least half of the nodes. Nope. You haven't thought this through. One problem is that "all available nodes" is one of those fuzzy concepts that sounds reasonable but is actually impossible to actually do. Say you send a write to 3 replicas, all of which you think are up. Only one acks the write within 10s. Did the other nodes fail before getting the write? You have no way to know. In the meantime, what do you do with the node that did ack your write? If you tell it to rollback, what happens if the other, "failed" nodes failed after performing the write, but before the ack? Or are they about to ack, if only you wait another 1s? (2PC can help but there are failure scenarios it can't handle, either. http://en.wikipedia.org/wiki/Two-phase_commit_protocol#Disadvantages http://en.wikipedia.org/wiki/Two-phase_commit_protocol#Disad...) Another way to think of the P in CAP is "Proceeds without potentially unbounded waits." > Paxos is another example. Paxos isn't a magic wand, either. You should read http://pl.atyp.us/wordpress/?p=2521 http://pl.atyp.us/wordpress/?p=2521.

dadkins 17y ago
> Nope. You haven't thought this through. That's not really fair. Paxos provably addresses all of the missing ack problems you suggest and makes progress as long as a quorum of nodes can communicate with each other. That's why I mentioned it. I'm also aware of the problems with two phase commit, namely the single point of failure. Funny enough, Paxos Commit is the solution to that problem. So really, Paxos is a magic wand when it comes to available and consistent distributed systems. You shouldn't use it for every single update in your distributed database; it's way too much overhead. But somewhere in the system there's probably some algorithm that looks like Paxos handling some important piece of metadata or the system isn't truly fault-tolerant. The link you gave is consistent with what I've said. Namely, the concept of quorum is a way to sacrifice availability for the minority of nodes in the presence of a partition but otherwise remain consistent. Paxos does precisely that. It's consistent and available in the absence of partitions, and it sacrifices availability for some in the presence of a partition. By the way, the other possibility in the design space is to remain available but sacrifice consistency in the face of a partition. This is the eventual consistency camp.

by jbellis 17y ago

dadkins 17y ago

> Nope. You haven't thought this through. That's not really fair. Paxos provably addresses all of the missing ack problems you suggest and makes progress as long as a quorum of nodes can communicate with each other. That's why I mentioned it. I'm also aware of the problems with two phase commit, namely the single point of failure. Funny enough, Paxos Commit is the solution to that problem. So really, Paxos is a magic wand when it comes to available and consistent distributed systems. You shouldn't use it for every single update in your distributed database; it's way too much overhead. But somewhere in the system there's probably some algorithm that looks like Paxos handling some important piece of metadata or the system isn't truly fault-tolerant. The link you gave is consistent with what I've said. Namely, the concept of quorum is a way to sacrifice availability for the minority of nodes in the presence of a partition but otherwise remain consistent. Paxos does precisely that. It's consistent and available in the absence of partitions, and it sacrifices availability for some in the presence of a partition. By the way, the other possibility in the design space is to remain available but sacrifice consistency in the face of a partition. This is the eventual consistency camp.