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

Raft: Understandable Distributed Consensus (2014)

thesecretlivesofdata.com

Post reply on HN
Print view View original

81–90 of 91 posts

Re: Raft: Understandable Distributed Consensus (2014)

#81

Post by butterisgood »

pa7ch wrote: post #47
eatonphil wrote: post #11

Ben's visualization here is great. The other biggest help to me aside from the paper and the thesis was Ongaro's TLA+ spec: https://github.com/ongardie/raft.tla/blob/master/raft.tla . It's the only super concise "implementation" I found that is free of production-grade tricks, optimizations, and abstractions. And for building an intuition, TigerBeetle's sim.tigerbeetle.com is great. What happens to consensus when the…

Interesting that TigerBeetle uses Viewstamp Replication over Paxos/Raft. TB says viewstamp replication lends itself to a more performant implementation and doesn't rely on disk storage as much. I'm surprised I'm not seeing this brought up more in Paxos/Raft discussions.

VR is often overlooked and really pretty easily understood

Re: Raft: Understandable Distributed Consensus (2014)

#82

Post by spmurrayzzz »

withinboredom wrote: post #80
spmurrayzzz wrote: post #14

Earlier quoted context omitted.

I tend to agree that many explanations of raft dont get into the useful details and handwave some of the hard problems. But the original paper does do a good job of this and is pretty accessible to read IMO. > I read "once the leader has been elected", um, hangon, according to whom? Has node 1 finally agreed on the leader, just while node 3 has given up and started another election? The simple response I think to "ac…

> The simple response I think to "according to whom" is "the majority of voting nodes". Reminds me of this one time we had a Raft cluster arguing over who was the leader for 20 minutes in production. Raft leader election is non-deterministic, while Paxos is deterministic. It can 'randomly' get into a situation it cannot resolve for quite a long time.

> Reminds me of this one time we had a Raft cluster arguing over who was the leader for 20 minutes in production

That's certainly an interesting failure mode. Do you recall the details around root cause? I could imagine ephemeral network partitions (flapping interfaces? peering loss?) causing something like this for sure.

In my own experience, I've been running services that use Raft under the hood for the last ~10 years in production and haven't seen this happen myself. Though I do absolutely remember having misconfigured election timeouts causing very painful latency issues in failover scenarios.

Re: Raft: Understandable Distributed Consensus (2014)

#83

Post by bvrmn »

kfrzcode wrote: post #49
throwawaymaths wrote: post #12

Earlier quoted context omitted.

Weirdly it's also kinda worse is better: raft is non-deterministic and has an unboundedly long election cycle time. IIRC: - it assumes no hysteresis in network latencies and if there is a hysteresis it's possible that elections can be deterministically infinite. - this fact and the use of raft in production has caused real, large scale network outages. Paxos is of course a beast and hard to understand. There is an al…

I've made a longer comment in another thread; but have you investigated the hashgraph algorithm? Gossip-about-gossip and virtual voting combine to result in leaderless consensus, fair ordering and aBFT. It's very performant with over 10k TPS on-chain. I'm learning about DLT from the perspective of hashgraph which is why I don't understand why it doesn't get love - it seems to have all of the good and none of the bad.

hashgraph seems like snake-oil, and marketed in similar ways. Couldn't find any good paper with enough details to make a production ready implementation.

Re: Raft: Understandable Distributed Consensus (2014)

#84

Post by sriram_malhar »

withinboredom wrote: post #78
sriram_malhar wrote: post #77

Earlier quoted context omitted.

Can you tell more about what other interesting modes multiPaxos allows? For an example of what I find uninteresting, it is proposers or acceptors not having a local disk (I know there are some uses for it, but there are relatively straightforward ways of solving that issue without requiring a whole new protocol). In all examples I have seen, multipaxos and raft are fairly alike, except for parts of their leadership e…

What makes multiPaxos a better learning tool isn't multiPaxos for the sake of multiPaxos, but rather Paxos itself. The write-once consensus primitive is a valuable tool (whether you are implementing Raft or multiPaxos) or thing to know. Especially when it comes to flexible / compartmentalized Paxos. Don't get me wrong, the same things can theoretically be done with Raft (if they haven't already), but that single-degr…

There are many algorithms to implement a single wait-free shared register. I like Basic Paxos, don't get me wrong. I also love the Part-time parliament paper's description of it. What I don't care much for is the generalization to multipaxos; too many things left to the imagination, which, in the hands of people like me without Lamport's reasoning skills, is headed for disaster. There is a reason why they say Paxos is too hard, but few people say that about Raft. A raft implementation is maintainable by ordinary mortals, because like I said, there is only one documented recommended way to do it.

Re: Raft: Understandable Distributed Consensus (2014)

#85

Post by withinboredom »

spmurrayzzz wrote: post #82
withinboredom wrote: post #80

Earlier quoted context omitted.

> The simple response I think to "according to whom" is "the majority of voting nodes". Reminds me of this one time we had a Raft cluster arguing over who was the leader for 20 minutes in production. Raft leader election is non-deterministic, while Paxos is deterministic. It can 'randomly' get into a situation it cannot resolve for quite a long time.

> Reminds me of this one time we had a Raft cluster arguing over who was the leader for 20 minutes in production That's certainly an interesting failure mode. Do you recall the details around root cause? I could imagine ephemeral network partitions (flapping interfaces? peering loss?) causing something like this for sure. In my own experience, I've been running services that use Raft under the hood for the last ~10 y…

Root cause was “bad luck” IIRC. Every node voted mostly for itself.

Re: Raft: Understandable Distributed Consensus (2014)

#86

Post by spmurrayzzz »

withinboredom wrote: post #85
spmurrayzzz wrote: post #82

Earlier quoted context omitted.

> Reminds me of this one time we had a Raft cluster arguing over who was the leader for 20 minutes in production That's certainly an interesting failure mode. Do you recall the details around root cause? I could imagine ephemeral network partitions (flapping interfaces? peering loss?) causing something like this for sure. In my own experience, I've been running services that use Raft under the hood for the last ~10 y…

Root cause was “bad luck” IIRC. Every node voted mostly for itself.

Ah, interesting. That sort of split voting is indeed very bad luck, potentially a config-specific issue, or just a cluster that's seeing a catastrophic partition failure between every node.

In canonical Raft assuming no partition failures, this could only happen if every node's election timeout triggered at roughly the same time and they all become candidates simultaneously. For this state to persist (assuming short election timeouts and short heartbeat intervals), you have to get _really_ unlucky.

In terms of probabilistic likelihood though, this is about as likely as the live-lock issue in Paxos in which multiple proposals with differing proposal ids are made at the same time. You'd seem a similar delay in consensus in that scenario as well. Obviously MultiPaxos handles this with a separate leadership algorithm which makes that outcome much less likely, but the same types of strategies common in those systems to mitigate contention issues can be used in Raft as well (randomized backoffs for example).

Re: Raft: Understandable Distributed Consensus (2014)

#87

Post by withinboredom »

spmurrayzzz wrote: post #86
withinboredom wrote: post #85

Earlier quoted context omitted.

Root cause was “bad luck” IIRC. Every node voted mostly for itself.

Ah, interesting. That sort of split voting is indeed very bad luck, potentially a config-specific issue, or just a cluster that's seeing a catastrophic partition failure between every node. In canonical Raft assuming no partition failures, this could only happen if every node's election timeout triggered at roughly the same time and they all become candidates simultaneously. For this state to persist (assuming short…

Yeah, IIRC, we updated the configuration some. I don't remember what specifically, but now that you mention short timeouts, I vaguely remember that coming up as a problem.

Re: Raft: Understandable Distributed Consensus (2014)

#88

Post by nvarsj »

withinboredom wrote: post #76
nvarsj wrote: post #74

Earlier quoted context omitted.

The best approach is to implement Paxos. I suggest https://github.com/emichael/dslabs . It will take 100-200 hours to fully implement with all tests passing.

Bummer that it requires java. Would be awesome to have a 'networked' version where you just need to implement the protocol.

Usage of java is fine ime. It's the principles that matter. The main benefit of this project is the search based tests which thoroughly test your implementation for edge cases. There's nothing else quite like it - few people can successfully complete this project to 100%.

Re: Raft: Understandable Distributed Consensus (2014)

#89

Post by withinboredom »

nvarsj wrote: post #88
withinboredom wrote: post #76

Earlier quoted context omitted.

Bummer that it requires java. Would be awesome to have a 'networked' version where you just need to implement the protocol.

Usage of java is fine ime. It's the principles that matter. The main benefit of this project is the search based tests which thoroughly test your implementation for edge cases. There's nothing else quite like it - few people can successfully complete this project to 100%.

Yeah, that's the thing, I want to give this a go. I just hate Java.

Re: Raft: Understandable Distributed Consensus (2014)

#90

Post by nvarsj »

withinboredom wrote: post #89
nvarsj wrote: post #88

Earlier quoted context omitted.

Usage of java is fine ime. It's the principles that matter. The main benefit of this project is the search based tests which thoroughly test your implementation for edge cases. There's nothing else quite like it - few people can successfully complete this project to 100%.

Yeah, that's the thing, I want to give this a go. I just hate Java.

Hah fair enough. The volume of code is low overall though so the language doesn't matter that much.
Post reply on HN