4 ms·

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 und

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 moment it happens) and then the nodes discover that it has been achieved later. Exploring various failure modes and coming to understand how Paxos is robust against them seems to work better in this setting as well. I think this paper by Heidi Howard and Richard Mortier is a great way to move on to Multipaxos: https://arxiv.org/abs/2004.05074 https://arxiv.org/abs/2004.05074 They present Multipaxos in a similar style to how Raft is laid out and show that Multipaxos as it is commonly implemented and Raft are almost the same protocol. Raft was a great contribution to the engineering community to make implementing consensus more approachable, but in the end I don't think the protocol itself is actually more understandable. It was presented better for implementers, but the implementation focus obscures some of the deep insights that plain Paxos exposes.

withinboredom 2y ago
Know that I join you in Raft being overrated. I’m working on a multipaxos implementation right now. There are some really neat capabilities/properties that paxos has that Raft can never achieve (see wpaxos, for example, that lets keys migrate to nodes near the client).
weinzierl 2y ago
This is an interesting insight into the educational side, but now I am curious about the implementation side. Raft is easier to implement but that's just one factor. Looking at real world usages there seems to be a draw. I could easily count as many Paxos implementations as Raft. Is this just historical or are there good reasons for a new project to still implement Oaxos?
- bfdes 2y ago
  Paxos and Multi-Paxos have been around much longer than Raft. The paper that introduced Raft was published in 2014.
alexchamberlain 2y ago
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.
- jimbokun 2y ago
  > 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.
  - alexchamberlain 2y ago
    Yeah, you kind of can’t test any of it until you test all of it…
  - heromal 2y ago
    Check out maelstrom
senderista 2y ago
Agree, Raft is less modular and therefore harder to understand than MultiPaxos: https://maheshba.bitbucket.io/blog/2021/12/14/Modularity.html https://maheshba.bitbucket.io/blog/2021/12/14/Modularity.htm...
alexnewman 2y ago
You are telling me your students can safely implement single decree paxos.... I worked on a few paxos production implementations before the RAFT paper, single and multi decree. The idea that paxos, as it is to be implemented, is easy for students to understand... Well let me re-read the paper, but i assure you, raft was a big deal
hintymad 2y ago
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.
- mananaysiempre 2y ago
  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/ https://fpaxos.github.io/ [2] https://dl.acm.org/doi/abs/10.1145/3380787.3393681 https://dl.acm.org/doi/abs/10.1145/3380787.3393681 or https://arxiv.org/abs/2004.05074 https://arxiv.org/abs/2004.05074 [3] https://www.youtube.com/watch?v=0K6kt39wyH0 https://www.youtube.com/watch?v=0K6kt39wyH0 [4] https://doi.org/10.4230/LIPIcs.OPODIS.2016.25 https://doi.org/10.4230/LIPIcs.OPODIS.2016.25 or https://arxiv.org/abs/1608.06696 https://arxiv.org/abs/1608.06696 [5] https://www.youtube.com/watch?v=r6NG_1HM0lA https://www.youtube.com/watch?v=r6NG_1HM0lA [6] https://github.com/heidihoward/distributed-consensus-reading-list https://github.com/heidihoward/distributed-consensus-reading...
- nvarsj 2y ago
  The best approach is to implement Paxos. I suggest https://github.com/emichael/dslabs https://github.com/emichael/dslabs. It will take 100-200 hours to fully implement with all tests passing.
  - withinboredom 2y ago
    Bummer that it requires java. Would be awesome to have a 'networked' version where you just need to implement the protocol.
    - nvarsj 2y ago
      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%.
sriram_malhar 2y ago
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 https://groups.csail.mit.edu/tds/papers/Attiya/PODC90.pdf
- withinboredom 2y ago
  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.

withinboredom 2y ago

Know that I join you in Raft being overrated. I’m working on a multipaxos implementation right now. There are some really neat capabilities/properties that paxos has that Raft can never achieve (see wpaxos, for example, that lets keys migrate to nodes near the client).

weinzierl 2y ago

This is an interesting insight into the educational side, but now I am curious about the implementation side. Raft is easier to implement but that's just one factor. Looking at real world usages there seems to be a draw. I could easily count as many Paxos implementations as Raft. Is this just historical or are there good reasons for a new project to still implement Oaxos?

bfdes 2y ago
Paxos and Multi-Paxos have been around much longer than Raft. The paper that introduced Raft was published in 2014.

alexchamberlain 2y ago

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.

jimbokun 2y ago
> 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.
- alexchamberlain 2y ago
  Yeah, you kind of can’t test any of it until you test all of it…
- heromal 2y ago
  Check out maelstrom

senderista 2y ago

Agree, Raft is less modular and therefore harder to understand than MultiPaxos: https://maheshba.bitbucket.io/blog/2021/12/14/Modularity.html https://maheshba.bitbucket.io/blog/2021/12/14/Modularity.htm...

alexnewman 2y ago

You are telling me your students can safely implement single decree paxos.... I worked on a few paxos production implementations before the RAFT paper, single and multi decree. The idea that paxos, as it is to be implemented, is easy for students to understand... Well let me re-read the paper, but i assure you, raft was a big deal

hintymad 2y ago

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.

mananaysiempre 2y ago
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/ https://fpaxos.github.io/ [2] https://dl.acm.org/doi/abs/10.1145/3380787.3393681 https://dl.acm.org/doi/abs/10.1145/3380787.3393681 or https://arxiv.org/abs/2004.05074 https://arxiv.org/abs/2004.05074 [3] https://www.youtube.com/watch?v=0K6kt39wyH0 https://www.youtube.com/watch?v=0K6kt39wyH0 [4] https://doi.org/10.4230/LIPIcs.OPODIS.2016.25 https://doi.org/10.4230/LIPIcs.OPODIS.2016.25 or https://arxiv.org/abs/1608.06696 https://arxiv.org/abs/1608.06696 [5] https://www.youtube.com/watch?v=r6NG_1HM0lA https://www.youtube.com/watch?v=r6NG_1HM0lA [6] https://github.com/heidihoward/distributed-consensus-reading-list https://github.com/heidihoward/distributed-consensus-reading...
nvarsj 2y ago
The best approach is to implement Paxos. I suggest https://github.com/emichael/dslabs https://github.com/emichael/dslabs. It will take 100-200 hours to fully implement with all tests passing.
- withinboredom 2y ago
  Bummer that it requires java. Would be awesome to have a 'networked' version where you just need to implement the protocol.
  - nvarsj 2y ago
    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%.

sriram_malhar 2y ago

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 https://groups.csail.mit.edu/tds/papers/Attiya/PODC90.pdf

withinboredom 2y ago
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.