Hacker News Reader

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

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.

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 election as Howard and Mortier also describe.

Raft's simplicity and the fact that there's exactly one way to do it is what I find most comforting in the most important component of a distributed system. I can look at an implementation of raft and immediately understand what's going on, and what is missing.

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-degree primitive makes it make that much more sense. This is missing from Raft.

It's like learning about a byte and never learning about endianness because everything is pretty much little-endian these days.

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.

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

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

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

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.

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

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.

Yeah, you kind of can’t test any of it until you test all of it…

Check out maelstrom

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?

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

Agree, Raft is less modular and therefore harder to understand than MultiPaxos:

https://maheshba.bitbucket.io/blog/2021/12/14/Modularity.htm...