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

Consensus Is Harder Than It Looks (2020)

brooker.co.za

Post reply on HN
Print view View original

21–30 of 32 posts

Re: Consensus Is Harder Than It Looks (2020)

#21

Post by _vvhw »

hinkley wrote: post #20

Author spends some time on determinism, which got me thinking of CRDTs, which are trying to make state changes commutative. They are in effect trying to get from linearalized state changes to causality. If we find a way to solve that problem, we have a more efficient consensus than Raft, one that can withstand small gaps in availability. I keep waiting for someone to bring a Turing, Gödel, or Shannon into this and po…

"we have a more efficient consensus than Raft,"

Except that in the Multi-Paxos family of consensus and replication protocols, Raft is probably the least efficient. It's to the extreme and foregoes several simple optimizations, because of design decisions taken in the name of understandability and simplicity.

I would suggest that VR is at least as understandable as Raft, while also being more efficient and with the lowest latency for leader election in the common case. There's no need for Raft's carefully tuned random timeouts because split votes are not possible with VR. VR also lets you do some really cool things like warm up the next leader, or prioritize synchronous replication under Flexible Paxos to the next leader with asynchronous replication amongst the remaining followers, or decide who you want the next leader to be to optimize for geographical placement etc.

VR's view change protocol for leader election is also entirely in-memory so it's far more fault tolerant compared to Raft if you have a storage fault model and not only a network fault model. For example, Raft requires strong persistence guarantees for correctness of the leader election phase. If anything goes wrong with your disk (a ghost write or misdirected write) then Raft's implementation as written would be unsafe. Raft also has liveness issues if all nodes have even a single block failure at any point in their log.

If you're going to reach for a consensus algorithm, there are a lot of good reasons to do a survey of the literature first. There's a whole spectrum to choose from.

Re: Consensus Is Harder Than It Looks (2020)

#22

Post by mjb »

hinkley wrote: post #20

Author spends some time on determinism, which got me thinking of CRDTs, which are trying to make state changes commutative. They are in effect trying to get from linearalized state changes to causality. If we find a way to solve that problem, we have a more efficient consensus than Raft, one that can withstand small gaps in availability. I keep waiting for someone to bring a Turing, Gödel, or Shannon into this and po…

Are you familiar with Joe Hellerstein and Peter Alvaro's work in this space? CALM provides something of a unifying theory of mergeable operations, of which CRDTs are an "object orientated" special case: https://arxiv.org/pdf/1901.01930.pdf

In practice, designers choose coordination-heavy protocols like consensus for a number of reasons. One is because writes don't or can't be merged. Operations as basic as simple assignment (x = 1;) can't be merged, so that's very real. Another is because readers can't tolerate weak consistency, because their business logic needs to make decisions at a particular point in time.

You're right that the thinking behind CRDTs (and CALM) is useful in reasoning through determinism in this context. The determinism problem, though, is easier than the general monotonicity problem, because only determinism is required and not associativity or commutativity.

Re: Consensus Is Harder Than It Looks (2020)

#23

Post by mjb »

_vvhw wrote: post #21
hinkley wrote: post #20

Author spends some time on determinism, which got me thinking of CRDTs, which are trying to make state changes commutative. They are in effect trying to get from linearalized state changes to causality. If we find a way to solve that problem, we have a more efficient consensus than Raft, one that can withstand small gaps in availability. I keep waiting for someone to bring a Turing, Gödel, or Shannon into this and po…

"we have a more efficient consensus than Raft," Except that in the Multi-Paxos family of consensus and replication protocols, Raft is probably the least efficient. It's to the extreme and foregoes several simple optimizations, because of design decisions taken in the name of understandability and simplicity. I would suggest that VR is at least as understandable as Raft, while also being more efficient and with the lo…

Joran, good to see your name come up!

> VR's view change protocol for leader election is also entirely in-memory so it's far more fault tolerant compared to Raft if you have a storage fault model and not only a network fault model.

Only in the fail-stop model, right? Or does this property extend to other models (like omissions)?

Re: Consensus Is Harder Than It Looks (2020)

#24

Post by mjb »

ignoramous wrote: post #8
FAANG_dream wrote: post #2

Ohh for sure! I tried implementing Raft, which is supposed to be the most understandable out of all available consensus algorithms, but wasn't able to make it work 100%. I came close but in the end gave up on resolving some concurrency issues :/

You are not alone: https://news.ycombinator.com/item?id=23123701 and https://youtu.be/QVvFVwyElLY?t=2502 Like TFA points out, distributed consensus is punishingly hard. AWS relied on TLA+ to prove consensus in DynamoDB and other systems https://lamport.azurewebsites.net/tla/formal-methods-amazon.... Interestingly, Kinesis [0] and SQS (?) avoid consensus for those same reasons. [0] https://news.ycombinator.com/item?id…

Chain Replication (and friends) are vastly simpler than Paxos (and friends) in many ways, but do have the same requirement for determinism. That's because chain replicated systems typically need to be confluent (see https://pathelland.substack.com/p/dont-get-stuck-in-the-con-...), which means that all the replicas need to have the same value in them when replication is done. Conceptually simpler, for sure, but many of the same challenges remain.

Re: Consensus Is Harder Than It Looks (2020)

#25

Post by eternalban »

_vvhw wrote: post #19
eternalban wrote: post #15

Earlier quoted context omitted.

Not surprised or disappointed, really. My take on RAFT is that it's basically Paxos for elections and a more relaxed regime in between. But Brooker's post (in my OP) actually addresses VR vs Paxos distiction: It's easy to believe that these two protocols are, in fact, the same. That doesn't appear to be the case. A new paper by van Renesse et. al., titled Vive La Difference: Paxos vs. Viewstamped Replication vs. Zab,…

"My take on RAFT is that it's basically Paxos" You're right that Raft is Paxos for the leader election phase, in the same way that VR is Paxos for the view change phase, or that Paxos is basically VR's view change but for deciding a value. But a better way of saying this would be that Raft is Multi-Paxos ( https://news.ycombinator.com/item?id=23123701 ), because Raft is much more than Paxos (in the same way that VR i…

Well, in that case we mildly disagree. My take is this:

That functionally M-Paxos and Raft are equivalent does not make them the equivalent. RAFT uses a protocol that looks awfully like Paxos for election of a single leader - so it has nothing to do with multi-Paxos (as I understand it). But that L.E. phase + the interim regime gives you functional equivalence to Multi-Paxos.

Re: Consensus Is Harder Than It Looks (2020)

#26

Post by _vvhw »

mjb wrote: post #23
_vvhw wrote: post #21

Earlier quoted context omitted.

"we have a more efficient consensus than Raft," Except that in the Multi-Paxos family of consensus and replication protocols, Raft is probably the least efficient. It's to the extreme and foregoes several simple optimizations, because of design decisions taken in the name of understandability and simplicity. I would suggest that VR is at least as understandable as Raft, while also being more efficient and with the lo…

Joran, good to see your name come up! > VR's view change protocol for leader election is also entirely in-memory so it's far more fault tolerant compared to Raft if you have a storage fault model and not only a network fault model. Only in the fail-stop model, right? Or does this property extend to other models (like omissions)?

Thanks Marc, I'm glad, you too!

Ever since I came across https://brooker.co.za/blog/2018/01/01/balls-into-bins.html, I've been really excited to see and follow all the fantastic design work you've been doing.

>> VR's view change protocol for leader election is also entirely in-memory so it's far more fault tolerant compared to Raft if you have a storage fault model and not only a network fault model.

> Only in the fail-stop model, right? Or does this property extend to other models (like omissions)?

You're far more knowledgeable about the domain... but I was thinking that with VRR's completely in-memory view change and replication protocol, this would then extend past the fail-stop model to include byzantine disk storage faults (misdirected reads/writes, corruption, latent sector errors) since VRR requires no guarantees from the disk in order for the consensus protocol to be correct, whereas Raft does.

To me this is just another reason that makes VRR such a fantastic protocol.

To be fair, I guess we could say that Raft assumes a fail-stop disk model, but then again Raft is supposed to be a practical implementation and disks are not fail-stop in reality. I'm sure you're also well familiar with WISC's Protocol-Aware Recovery for Consensus-Based Storage: https://www.usenix.org/system/files/conference/fast18/fast18...

Beyond that, I've also been wondering about this from the perspective of taking VRR's in-memory view change for the leader election phase, but then combining this with disk-based persistence for the replication phase, along with CTRL from WISC.

I would love to hear your thoughts on this. Did I understand you correctly regarding what you meant with extending "to other models (like omissions)"?

Would be great to catch up next time you are in the Cape!

Re: Consensus Is Harder Than It Looks (2020)

#27

Post by carapace »

MadSudaca wrote: post #14

If we can't make machines reach a consensus, what hope is there for human beings?

From the title I thought this might be about "Consensus decision-making" https://en.wikipedia.org/wiki/Consensus_decision-making

(I suspect it's the most efficient form of government, FWIW.)

Re: Consensus Is Harder Than It Looks (2020)

#28

Post by _vvhw »

eternalban wrote: post #25
_vvhw wrote: post #19

Earlier quoted context omitted.

"My take on RAFT is that it's basically Paxos" You're right that Raft is Paxos for the leader election phase, in the same way that VR is Paxos for the view change phase, or that Paxos is basically VR's view change but for deciding a value. But a better way of saying this would be that Raft is Multi-Paxos ( https://news.ycombinator.com/item?id=23123701 ), because Raft is much more than Paxos (in the same way that VR i…

Well, in that case we mildly disagree. My take is this: That functionally M-Paxos and Raft are equivalent does not make them the equivalent. RAFT uses a protocol that looks awfully like Paxos for election of a single leader - so it has nothing to do with multi-Paxos (as I understand it). But that L.E. phase + the interim regime gives you functional equivalence to Multi-Paxos.

Happy to mildly disagree!

"RAFT uses a protocol that looks awfully like Paxos for election of a single leader"

Agreed.

"so it has nothing to do with multi-Paxos (as I understand it)"

Except that Raft is not only a protocol for single leader election, it's also a replication protocol (see the "AppendEntries" message), and that's why it is Multi-Paxos. Multi-Paxos is just the category or classification for a family of consensus protocols that use the strategy of single leader election and replication with terms/views/epochs (the "interim regime" you refer to) for strict serializability. This is the passive replication leader/follower primary/backup strategy.

Outside of Multi-Paxos, there are also consensus protocols that achieve strict serializability with Paxos but without electing a single stable leader, e.g. FastPaxos. These exploit low latency between the client and all replicas, but this is not always available, or may suffer from tail latency issues, hence implementations such as Raft use the MultiPaxos strategy of a stable leader, which may be better connected to the rest of the cluster than the client.

As an implementation, depending on how you zoom, Raft is very different to VR and ZAB, but it's still in the same Multi-Paxos class since it reuses a single stable leader derived from one instance of Paxos for "multiple" rounds or instances of replication, hence "Multi-" "Paxos".

At least this is how I understand it from Heidi Howard and others who seem to share this "view".

Re: Consensus Is Harder Than It Looks (2020)

#29

Post by danbruc »

hinkley wrote: post #20

Author spends some time on determinism, which got me thinking of CRDTs, which are trying to make state changes commutative. They are in effect trying to get from linearalized state changes to causality. If we find a way to solve that problem, we have a more efficient consensus than Raft, one that can withstand small gaps in availability. I keep waiting for someone to bring a Turing, Gödel, or Shannon into this and po…

If we find a way to solve that problem [...]

We will not. And you are hinting at the reason yourself.

[...] CRDTs, which are trying to make state changes commutative.

But this is slightly wrong, when you are using CRDTs you are not trying to make state changes commutative, you are limiting the allowed state changes to commutative ones. But some state changes are inherently non-commutative and if your system requires those, then you can not build it with CRDTs.

Re: Consensus Is Harder Than It Looks (2020)

#30

Post by eternalban »

_vvhw wrote: post #28
eternalban wrote: post #25

Earlier quoted context omitted.

Well, in that case we mildly disagree. My take is this: That functionally M-Paxos and Raft are equivalent does not make them the equivalent. RAFT uses a protocol that looks awfully like Paxos for election of a single leader - so it has nothing to do with multi-Paxos (as I understand it). But that L.E. phase + the interim regime gives you functional equivalence to Multi-Paxos.

Happy to mildly disagree! "RAFT uses a protocol that looks awfully like Paxos for election of a single leader" Agreed. "so it has nothing to do with multi-Paxos (as I understand it)" Except that Raft is not only a protocol for single leader election, it's also a replication protocol (see the "AppendEntries" message), and that's why it is Multi-Paxos. Multi-Paxos is just the category or classification for a family of…

I guess my issue here is calling all these "paxos" when 2 (VR and VS) predate Paxos.

Anyway, did you check out Egalitarian Paxos? I think this protocol deserves more love, specially in WAN contexts (there is a ref. impl. on github):

https://www.usenix.org/system/files/nsdip13-paper14.pdf

Post reply on HN