While understandable, implementing it is however far from easy.
Doing that in a way that's easy to automate, set up, evaluate, and tear down various scenarios seems like the hardest part to me.
The assertion at the time was that only a few people understood it well enough to make a correct implementation, the others were full of bugs.
The problem we have with Lamport is that he’s very good at talking to computers but not so good at talking to humans. I think the world would be a better place today if someone had forced him to learn to speak human.
He did a presentation at MS just after he won the Turing Award. He prefaces it with how important writing is to thinking, and how you don’t really know what you think until you write it down. Those are the words and thinking of an introvert. Writing is still the shallow end of understanding. The deep end is teaching. If you understand something and you teach it to others, then you have proven that you understand it, and caused that understanding not to be lost to posterity. If you only write about it, it might work as instructional material, or it may require some very clever people who can teach themselves using your words. But they may also get it wrong, and not have you for feedback.
The latter is where seem to be with Leslie’s works. The consensus is that few people actually understand what he’s talking about well enough to implement it correctly.
I had a coworker once who was shocked to learn I read the ACM SIGPLAN proceedings. “You can read those??” I knew what he meant and yeah, a lot of those were very unapproachable and I understood two thirds of them and only half of each of the rest. Before I committed to using Raft I gave Lamport’s paper a try. It was a slog and he doesn’t sell the why of each part. He’s just giving you a very, very long recipe without the mental models necessary to reproduce it robustly.
I think Leslie Lamport asserted that Paxos is minimal, and that "all other consensus algorithms are just Paxos with more steps". I'm inclined to believe him.
I've implemented Paxos but I can't get through "Raft for dummies" style blog posts.
Regarding Raft [1]:
> The consensus problem is divided into three sub-problems: Leader election, Replication and Safety.
When I read these posts, i see things like "timeout", "heartbeat", and I think: timeout according to whom? 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? I don't doubt that Raft is correct, but the writing about it seems simple by glossing over details.
Paxos, on the other hand, seems timeless. (And the writing about it doesn't trigger my "distributed system fallacies" reaction)
> 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 "according to whom" is "the majority of voting nodes". When the leader assumes its role, it sends heartbeats which are then accepted by the other nodes in the cluster. Even if (in your example) node 3 starts a new election, it will only succeed if it can get a majority of votes. If node 2 has already acknowledged a leader, it won't vote for node 3 in the same term.
There's some implicit concessions inherent there around eventual consistency, but I don't think thats novel to Raft compared to other distributed consensus protocols.
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.
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.
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).
I am curious on your thoughts here.
Whereas I think each line of pseudocode in Paxos is much more motivated.
In other words, if a philosopher had to design a crash-fault protocol from scratch, without having seen any before, I think 80% of the time it would look exactly like Paxos.