3 ms·
Just like the author, I'm no Paxos expert. However, I see a clear issue with the proposed model. Taking the authors 11 node set up. 9 nodes are required for
by dsp1234 10y ago
Just like the author, I'm no Paxos expert.
However, I see a clear issue with the proposed model.
Taking the authors 11 node set up. 9 nodes are required for leader election. 3 nodes are needed for proposals.
Assume that a network partition splits the nodes with 5 nodes on side A and 6 nodes on side B. Assume also that the leader is on side B (though it works without loss of generality for side A as well).
At this point, no leader re-election can occur, since no side has the 9 total nodes required for a re-election. It's obvious that if the leader dies (or died as part of the partition) that no leader can be re-elected.
With the partition in place:
1.) let 1 node in side A make the proposal "X=3"
2.) Let 2 other nodes in side A agree to the proposal that "X=3"
3.) Let 1 node in the side B make the proposal "X=0"
4.) Let 2 other nodes in side B agree to the proposal that "X=0"
5.) Let the partition heal
6.) The cluster is now split brain on whether "X=0" or "X=3". According to the rule provided, the leader must accept any successful proposal.
Note that this split brain does not even require a network partition. Assume no network partition, and nodes are labeled 0-10. The leader is currently node 10.
1.) Let node 1 propose that "X=4"
2.) Let node 2 propose that "X=5"
3.) Let nodes 3 and 9 agree to the proposal that "X=4"
4.) Let nodes 6 and 8 agree to the proposal that "X=5"
5.) Split brain occurs as the leader has to accept any successful proposal, which includes "X=4" from nodes 1, 3 and 9, and also "X=5" from nodes 2, 6 and 8.
- f0urtyfive 10y agoOnce you're planning work arounds for the "assume half your servers fail" scenario, I think it's time to admit that eventually, something is going to go down that is not automatically recoverable.
- ori_b 10y agoThe problem is that half the servers failing is indistinguishable from a switch connecting two racks being flaky, or anything else which can lead to half the servers being temporarily disconnected from the others.
- f0urtyfive 10y agoWhy wouldn't you use redundant switches rather than n(2) servers?
- ori_b 10y agoWhy would I buy two switches when I can solve the problem in general with a consensus algorithm that handles hosts going away for any reason? Especially since a flaky switch isn't the only issue. Power loss could bring down even redundant backbone switches, but leave communication within the rack going. You could accidentally push a bad routing config and blackhole traffic to a bunch of hosts. You could send out a bad push that intermittently breaks connectivity to some hosts. And so on.
- ketzu 10y agoClassical consensus only solves the problem for up to 33% failure (3f+1 nodes, with f failures), having half of your servers fail can not be done with paxos.
- oggy 10y agoThe split-brain scenarios you mention cannot occur, since all the proposals have to go through the leader before they are agreed to by any processes. Moreover, the leaders are lease-based in the author's proposal, so I believe that what he describes correctly solves consensus. However, his proposal doesn't really give much of a resilience improvement over the original Paxos, since the system, in the worst case, tolerates only 2 failures (leader + one more process), same as a 5-process Paxos. Nevertheless, an interesting idea, one that I don't think I've seen elsewhere.
- maccilia 10y agoSo I'm pretty a similar problem could exist. If to accept a proposal we only need 3 nodes, not a majority, and we manipulate network latency in arbitrarily bad ways, a similar split brain could occur. Basically, you could commit the same transaction twice under different proposal numbers.
- oggy 10y agoConsensus is not about transactions, it's about agreeing on a value (a single value, strictly speaking, unlike atomic broadcast, which is about agreeing on a sequence of values, although people often identify the two). But anyway, your argument is not in any way concrete - try to come up with a counterexample. Having thought about it more, I am confident that the author's system is correct (in the sense that it always preserves agreement).