Hacker News Reader

Comment by thaumaturgy | Hacker News Reader

As an alternative to Paxos-related consensus algorithms, some projects may want to take a look at the Raft consensus protocol: https://www.brianstorti.com/raft/

Whereas Paxos tries to maintain a fully distributed consensus state, Raft instead proposes a protocol for automatically electing a leader node from a group of follower nodes, and coordinating the replication of the write log through that leader node.

I haven't had the pleasure of experimenting with either one though and would love to hear from people who have.

View on HN

Raft is arguably more difficult to understand at a deep level. After extensive study, I've noticed that Raft hides all of its complexity under its leader election setup. There's nuance after nuance. With Paxos, the complexity is explicit and at the forefront, which is actually better, when trying to reason about a distributed system and its invariants.

That was my experience as well. The rules around leader election, terms, voting, timeouts and the like are very subtle.

Raft is basically a fixed leader elected by a single round of Paxos.

It's not that simple. Here's an overview on paxos/raft consensus algorithms: https://vadosware.io/post/paxosmon-gotta-concensus-them-all/ and even that is incomplete and not necessarily describes trade-offs well. Submitted generalized solution is a better point to start experimenting from.

This paper is deliberately a generalization of all of them, actually. Raft can also be explained in terms of the rules/system she provides.

She happens to use PaxOS as examples to show they are non-optimal, in part because Raft is already deliberately non-optimal.

The other reason is that Raft is completely trivial in her framework.

It is equivalent to only having one thing decide the registers (and all the hard work is in deciding which thing).

Exactly this, not sure why people think it's a different thing - just wrap nodes into a higher level of abstraction. I believe Raft might be a better approach to scalable consensus tho but there needs to be more layers to a network so the network can be more self-balancing and localised.

If we we call "heartbeat" the frequency at which a node is synced to the network (achieves consensus) - lower heartbeat nodes need to stay close only to nodes with a "heartbeat" faster than theirs and elect leaders in that group. The leaders in that group are also in a group of other leaders of that layer and listening to their leader, which belongs to a group above (like zooming out from a group and the group becoming a node in a larger graph).

In the end, there is only one state after all and the graph is the ultimate leader with the highest heartbeat. We wouldn't need many layers to cover all nodes, assuming laws of nature and all. Then just go a layer up/down if the network is getting too large, use a karmic system to position new/reactivated nodes. Seems scalable enough.

Sorry OP, it might be too early and I'm just thinking out loud in a comment box.

Can the framework model the leader election though?

They do, effectively. They show what is necessary for quorums, and show that a large number of algorithms meet these requirements.

Hence, the single leader election is not actually necessary (and this is one of their points - the existing algorithms require much stronger quorum guarantees than are actually necessary for correctness)

By the way, Paxos is the name of a Greek island; it doesn’t have funky capitalisation. The name is from Lamport’s paper “the part-time parliament” which describes the algorithm in the setting of Ancient Greece.

It took me months to do a reliable Raft implementation. The author of the Raft paper, Diego Ongaro, wrote in a comment on a Raft mailing list that it could take weeks.

The Raft paper is really easy to read and understand, but the actual code is very tricky.

What did you find most difficult about the implementation?

Not OP, but it is very easy to make mistakes while implementing it and end up with something that is not actually reliable. You have to have the paper opened and write code line by line looking at it. I implemented it a while ago so that's the most I remember, but it did a bit of fuzzing to nail down every bug.

Also not OP, I think I went through the paper 10 times over during the implementation. There's a lot of cross-references all over the place.

Could I ask you something, or maybe on Steam?

Or I could ask you here one of the questions.

Do you host diep.io on cloudflare, heroku, linode etc.? or do you have own servers?

Because I'm interested about developing something.

To make it work with any kind of performance, all message passing needs to be asynchronous, and you need an event loop to process messages one at a time. Things are much simpler if your code is effectively single-threaded when processing an inbound message. That took me a while to figure out. Futures and promises are very helpful.

It took a while to get the building blocks together: the log file, which can be traversed, read, and rolled back/truncated (use a kv store for this, trust me), and the transport mechanism to deal with sending complex objects and handling errors and timeouts.

Tracking terms, states (leader, follower, candidate), rejecting out of date terms, voting, elections -- it's all very complex. You'll have to build some really, really good multi-threaded tests that simulate out-of-order and dropped messages, then really pound away at the system. And good logging to find that odd corner case that keeps coming up and throwing mysterious messages.

I haven't even tried membership changes yet.

> use a kv store for this, trust me

Order is important here - is this inherent in your key?

Yes.

I did two implementations, one with plain text files and one with a kv store. For plain text files, I had to maintain file offsets of the records so I could traverse backward and truncate records that had to be replaced, and then break the files into segments so I could retire segments that are no longer needed. It had all kinds of little bugs.

Then I reimplemented using a kv store, and it took a tiny fraction of the time. And surprisingly had better performance.

Just create a good interface at the start, use the kv store underneath, and then later if you don't want the dependency swap it out for the more complicated code.

Cool - I’d like to talk about your design and how you arrived at it if you’re interested.

Happy to. I just added my email address to my profile.

Isn't raft the default for Bitcoin?

No. Raft and Bitcoin's algorithms for agreeing on what the blockchain is are completely different.

AIUI, Bitcoin's "consensus" is just whoever has the longest valid blockchain is the winner. The algorithm tunes the difficulty s.t. it takes ~10 minutes to find a block, so the chance of two blockchains continuing to have the same length for any long amount of time is unlikely. That is, one chain will find the next block before the other, and in the meantime, be able to distribute that fact to the other nodes and thus "win".

From https://en.bitcoin.it/wiki/Block_chain:

> Honest generators only build onto a block (by referencing it in blocks they create) if it is the latest block in the longest valid chain. "Length" is calculated as total combined difficulty of that chain, not number of blocks, though this distinction is only important in the context of a few potential attacks.

No. Bitcoin uses its own protocol. Raft could not be used for a secure cryptocurrency bevause Raft does not handle byzantine faults[1]. It assumes nodes are not run by malicious actors and messages sent are unaltered in transit.

[1] https://en.m.wikipedia.org/wiki/Byzantine_fault

True. Though in tradeoff it has massively increased throughput. I'm always frustrated when I see blockchains recommended as a solution for a consensus problem in anything but a zero-trust scenario

Even in a zero trust scenario, you need a majority of nodes to be good faith, non-colluding actors. Even anarchy breaks down in the face of unequal power.

Bitcoin consensus is extremely simple: the chain with the most accumulated difficulty. Furthermore blocks aren't removed or changed, so consensus is in fact a monotonic process. You don't need either Paxos or Raft or any other sophisticated algorithm; just broadcast every block you believe to be part of the most difficult chain and consensus will be achieved.

Bitcoin consensus is what is called Byzantine consensus - that is your consensus still has to work with some nodes actively trying to send bad information to mess up the protocol.

Raft and Paxos are non-Byzantine. They assume that the nodes are actively trying to follow the protocol though there me be such things as network partitions and crashes.

Reply on news.ycombinator.com