Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A More Flexible Paxos

ssougou.blogspot.com

Post reply on HN
Print view View original

11–20 of 23 posts

Re: A More Flexible Paxos

#11

Post by f0urtyfive »

ori_b wrote: post #6
f0urtyfive wrote: post #4

Earlier quoted context omitted.

Once 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.

The 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.

Why wouldn't you use redundant switches rather than n(2) servers?

Re: A More Flexible Paxos

#12

Post by sougou »

I'm the author of the blog. Thanks for the posts and interest shown.

This proposal is a generalization of the core Paxos algorithm. It's therefore orthogonal to all customizations and adaptations. I believe that they can all benefit from it, including RAFT.

If you read the thread on raft-dev, you'll see that Heidi Howard has independently come up with the same idea, and is working on a proof for it.

Re: A More Flexible Paxos

#13

Post by ori_b »

f0urtyfive wrote: post #11
ori_b wrote: post #6

Earlier quoted context omitted.

The 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.

Why wouldn't you use redundant switches rather than n(2) servers?

Why 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.

Re: A More Flexible Paxos

#14

Post by fizx »

There's no theoretical reason why multipaxos can't be implemented hierarchically in order to increase throughput or expand the key space beyond what a small number of machines can handle. But paxos itself is complicated enough to deter almost all implementers, so add two additional levels of complexity? I don't think I'm surprised no one has tried.

Paxos: Agree on a value.

Multipaxos: Agree on a Leader, who will coordinate a set of values.

Hierarchical Multipaxos: Agree on a Leader, who will coordinate a set of Leaders, who will each coordinate a set of values.

If you squint hard enough, this looks almost like a B-Tree.

Re: A More Flexible Paxos

#15

Post by im_down_w_otp »

fizx wrote: post #14

There's no theoretical reason why multipaxos can't be implemented hierarchically in order to increase throughput or expand the key space beyond what a small number of machines can handle. But paxos itself is complicated enough to deter almost all implementers, so add two additional levels of complexity? I don't think I'm surprised no one has tried. Paxos: Agree on a value. Multipaxos: Agree on a Leader, who will coor…

riak_ensemble is a hierarchical multi-paxos shaped system. It's what Riak Strong Consistency buckets are built on, but it's also a stand-alone consumable framework by itself.

Re: A More Flexible Paxos

#16

Post by fizx »

im_down_w_otp wrote: post #15
fizx wrote: post #14

There's no theoretical reason why multipaxos can't be implemented hierarchically in order to increase throughput or expand the key space beyond what a small number of machines can handle. But paxos itself is complicated enough to deter almost all implementers, so add two additional levels of complexity? I don't think I'm surprised no one has tried. Paxos: Agree on a value. Multipaxos: Agree on a Leader, who will coor…

riak_ensemble is a hierarchical multi-paxos shaped system. It's what Riak Strong Consistency buckets are built on, but it's also a stand-alone consumable framework by itself.

Nifty! Did not know that.

Re: A More Flexible Paxos

#17

Post by [deleted] »

dragonwriter wrote: post #10
bogomipz wrote: post #9

"With systems getting more and more distributed, the Paxos algorithm has been gaining popularity." Has it though? I feel like many of the new distributed systems I read about are Raft based consensus.

> Has it though? AFAICT, Yes. > I feel like many of the new distributed systems I read about are Raft based consensus. Sure, and Raft has probably been gaining popularity even more than Paxos has. With more and more distributed systems and more attention on guarantees for such systems, its possible for both Paxos and Raft (and perhaps other techniques) to be getting more popular.

[deleted]

Re: A More Flexible Paxos

#18

Post by rdtsc »

bogomipz wrote: post #9

"With systems getting more and more distributed, the Paxos algorithm has been gaining popularity." Has it though? I feel like many of the new distributed systems I read about are Raft based consensus.

I think there is more talk on HN about Raft. It ended up in some new visible open source projects etcd, RethinkDB. Any major companies the size of Amazon or Google running on raft?

As for Paxos I think Amazon, Google (Spanner), Microsoft? have all implemented Paxos based systems are built and in production for a while. Basho has made it part of their Riak database etc.

I mean, sure if popular is just number of times it appeared on HN recently, yes, raft wins hands down. But otherwise, I think Paxos still seems like the workhorse of distributed consensus.

Re: A More Flexible Paxos

#19

Post by ketzu »

ori_b wrote: post #6
f0urtyfive wrote: post #4

Earlier quoted context omitted.

Once 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.

The 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.

Classical 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.

Re: A More Flexible Paxos

#20

Post by oggy »

maccilia wrote: post #8
oggy wrote: post #5

Earlier quoted context omitted.

The 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, toler…

So 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.

Consensus 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).
Post reply on HN