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

61–70 of 91 posts

Re: Raft: Understandable Distributed Consensus (2014)

#61

Post by lanstin »

MarkMarine wrote: post #60
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…

> this fact and the use of raft in production has caused real, large scale network outages. Paxos as well, I remember full cloud GCP outage that had something to do with Paxos, and I can’t find the data on it but I thought there was a nasty bug in zookeeper paxos implementation. That isn’t to say any of these are perfect or bug free, it’s made by humans and we’re going to make mistakes, but my experience implementing…

My zookeeper outages are always due to simple things like all the workers having the same basic image and then having increased write rate filling up the disk of all workers at the same time.

Re: Raft: Understandable Distributed Consensus (2014)

#62

Post by quelltext »

In the log replication example, after healing the partition the uncommitted log changes in the minority group are rolled back and the leader's log is used.

However it's not clear how that log is transmitted. Until this point only heartbeats via append entry were discussed, so it's not clear if the followers pull that information from the leader somehow via a different mechanism, or whether it's the leader's responsibility to detect followers that are left behind and replay everything. That would seem rather error prone and a lot of coordination effort. So how's it actually done?

Re: Raft: Understandable Distributed Consensus (2014)

#63

Post by heromal »

jimbokun wrote: post #44
alexchamberlain wrote: post #39

Earlier quoted context omitted.

I've read both the Paxos and Raft papers a few times, and hacked on some implementations, but never quite got one over the line to working... Raft strikes me as a particular set of decisions made within a Paxos framework, such as having 1 entity for Proposers, Acceptor and Followers. It's frustrating that there isn't a clearly written defacto paper on Paxos - the story style confused the monkeys out of me.

> but never quite got one over the line to working... I've never implemented something like this. But my first thought is "how do you implement the testing system?" I feel like once you had a robust testing system that can verify things work correctly in all the different network partition and other scenarios, and allowing rapid iteration of setting up those scenarios, the implementation would be comparatively easy.

Check out maelstrom

Re: Raft: Understandable Distributed Consensus (2014)

#64

Post by sriram_malhar »

_russross wrote: post #19

I am in the minority who thinks Raft is overrated. I tried teaching Raft one year instead of Paxos but ended up switching back. While it was much easier to understand how to implement Raft, I think my students gained deeper insight when focusing on single-decision Paxos. There is a lightbulb moment when they first understand that consensus is a property of the system that happens first (and they can point at the mome…

I have had the opposite trajectory. Used to teach Paxos, but was so relieved to switch to Raft when the paper came out.

I discuss distributed data structures in the context of maps and sequences.

For maps, I discuss key-value stores (NUMA, Redis). I have them implement cache coherence (MESI protocol, TARDIS 2.0), then linearizable, fault-tolerant, wait-free shared memory registers (the Attiya/Bar-Noy/Dolev algorithm[1]).

For sequences, I cover shared logs and state machine replication, including database log shipping, Kafka, queues and Raft.

I like Raft because it cuts down the design space by making certain very intuitive and pragmatic choices, like using timeouts (which are almost beneath Lamport to discuss :), or idioms like "follow the leader", "if the leader is unreachable, stand for election", "elect the latest & most informed leader", (how I wish that was true in real life!), "always append" etc. There are simple mechanisms to preserve invariants.

The problem with Paxos is that there is such a large range of papers that there is no one paper that makes the leap in easy digestible chunks from Basic to MultiPaxos. When I got students to implement MultiPaxos, I never could get sufficient confidence that it was done right (esp. the "disorderly" filling in of log slots).

Paxos is like Monads; when you get it, you feel compelled to write a "Paxos explained" paper :)

[1]https://groups.csail.mit.edu/tds/papers/Attiya/PODC90.pdf

Re: Raft: Understandable Distributed Consensus (2014)

#65

Post by lifeinthevoid »

mbivert wrote: post #35

In case this is of interest, MIT's 6.5840[0], distributed systems, has a series of labs, implementing Raft in Go. Haven't made it through the whole thing yet, but it's quite entertaining so far. The teachers provide you with some code templates, a bunch of tests, and a progressive way to implement it all. [0]: https://pdos.csail.mit.edu/6.824/index.html

really liked the course, it was also instrumental in landing me my previous job :-)

Re: Raft: Understandable Distributed Consensus (2014)

#66

Post by withinboredom »

sriram_malhar wrote: post #64
_russross wrote: post #19

I am in the minority who thinks Raft is overrated. I tried teaching Raft one year instead of Paxos but ended up switching back. While it was much easier to understand how to implement Raft, I think my students gained deeper insight when focusing on single-decision Paxos. There is a lightbulb moment when they first understand that consensus is a property of the system that happens first (and they can point at the mome…

I have had the opposite trajectory. Used to teach Paxos, but was so relieved to switch to Raft when the paper came out. I discuss distributed data structures in the context of maps and sequences. For maps, I discuss key-value stores (NUMA, Redis). I have them implement cache coherence (MESI protocol, TARDIS 2.0), then linearizable, fault-tolerant, wait-free shared memory registers (the Attiya/Bar-Noy/Dolev algorithm[…

I feel like you are doing your students a disservice. (multi-)Paxos, while complex to wrap your head around, enables far more modes of consensus. The possibilities and papers out there are amazing.

Raft essentially only allows a single mode. Moreover, you are starting to see people putting things on top of Raft instead of something like Paxos, in the enterprise, because they don't know any better nor have the foundation to understand what they are doing is "wrong."

> When I got students to implement MultiPaxos, I never could get sufficient confidence that it was done right

Testing this is fairly straightforward, they should be able to join an already existing cluster. If they got it wrong, it shouldn't take down the cluster, and they should be able to step through their own code. There aren't any timeouts, so they can take their time, going through each step of the process until a value is committed.

At that point, you simply explain each step as an individual algorithm, not the sum of its parts. You can even build each part individually because an existing cluster should recover from a misbehaving peer.

From there, it is a rather simple visualization process to see what is going on.

The hard part of paxos is building it from scratch.

Re: Raft: Understandable Distributed Consensus (2014)

#67

Post by mananaysiempre »

hintymad wrote: post #57
_russross wrote: post #19

I am in the minority who thinks Raft is overrated. I tried teaching Raft one year instead of Paxos but ended up switching back. While it was much easier to understand how to implement Raft, I think my students gained deeper insight when focusing on single-decision Paxos. There is a lightbulb moment when they first understand that consensus is a property of the system that happens first (and they can point at the mome…

Is there any paper/handouts/video that explains Paxos in depth, especially its implementations and intuitions? Paxos Made Simple gave intuitive explanations, but I feel it still misses a lot of intricate details if I were to build Praxos for production use.

The papers and talks[1] by Heidi Howard and Richard Mortier, in particular “Paxos vs Raft: Have we reached consensus on distributed consensus?”[2,3] and “Flexible Paxos”[4,5], are what finally made things click for me. A real implementation also needs other stuff[6], though, such as dynamic membership and state machine replication, which I still don’t know how to do.

[1] https://fpaxos.github.io/

[2] https://dl.acm.org/doi/abs/10.1145/3380787.3393681 or https://arxiv.org/abs/2004.05074

[3] https://www.youtube.com/watch?v=0K6kt39wyH0

[4] https://doi.org/10.4230/LIPIcs.OPODIS.2016.25 or https://arxiv.org/abs/1608.06696

[5] https://www.youtube.com/watch?v=r6NG_1HM0lA

[6] https://github.com/heidihoward/distributed-consensus-reading...

Post reply on HN