Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

In search of a simple consensus algorithm

rystsov.info

Post reply on HN
Print view View original

51–60 of 87 posts

Re: In search of a simple consensus algorithm

#51

Post by Xorlev »

SEJeff wrote: post #14
irfansharif wrote: post #6

It is my understanding that the motivation in seeking out consensus algorithms with strong leaders (or equivalent) as opposed to horizontally weighted peer-to-peer ones is due to the performance penalty imposed by the latter in the general case. Structuring the protocol to be a dissemination from the 'leader' node down to the followers as opposed to a bottom-up approach fares better when your leader is long-lived, ci…

Funnily enough, there is a paper on exactly what you're referring to from Microsoft Research called "Flexible Paxos": https://arxiv.org/pdf/1608.06696.pdf The gist of it is that there are realistically 2 quorums to be had: One for read/write to a cluster, and one for leader election. Assuming leader election is a relatively uncommon event (as it is in Paxos), you can require more quorum nodes for leader election whil…

> I literally spent part of an evening with a beer

Just one? :)

Consensus algorithms are _fascinating_! And +1 for https://blog.acolyer.org/ , I'll often read his blog over lunch.

Another great paper is https://research.google.com/archive/paxos_made_live.html which talks about what it's like to realistically run Paxos. There's a ton of corner cases, engineering realities, and optimizations to be done to make Paxos work well in practice.

Another good resource is the Raft GitHub page[1] which links to the paper, has an interactive visualization, and a plethora of talks by various people.

Raft is the backbone of opensource, I'd be curious to hear from any Googlers in the know whether there's deficiencies in Raft that lead to continued use of Paxos, or if it's experience (and already battle-tested code) with Paxos that leads them to continue deploying Paxos-backed systems.

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

Re: In search of a simple consensus algorithm

#52

Post by rystsov »

rescrv wrote: post #48
rystsov wrote: post #42

Earlier quoted context omitted.

Gryadka is less than 500 but supports membership change :) yet 3 hours on it is quite impressive

JS vs sparse C++? Cut comments and change coding style and you can easily get close to 500 lines. One thing I think is worth touching on is the pipelining ability of multi-paxos that is missing when you have a single register with the Synod protocol. For key-value operations, it's not a problem. For a true replicated state machine, this can hinder performance. In Replicant[1] I added pipelining to ensure Paxos was un…

It would still lack "Consistent get operations", "Paxos group changes", be "bound to localhost" and do more than 1 round trip to commit.

What do you mean by pipelining?

Re: In search of a simple consensus algorithm

#53

Post by iambvk »

rystsov wrote: post #24
cube2222 wrote: post #19

I have the feeling like this article is just bashing strong master consensus protocols. But the truth is, yes, they incur a penalty for electing a master. However, this really gets amortized in most workloads if the leader changes only rarely. Additionally, in an environment with a good network connection between nodes (a few ms), you can set the timeout to be much less than a few seconds (could be less than a second…

> consistent reads do not need a living master It's wrong. If you're fine with stale reads then you don't a living master, but if you want to have a guarantee that the read value is up-to-date then the living master is necessary. Etcd has a bug related to this - https://github.com/coreos/etcd/issues/741

When leader is not around, isn't a majority read sufficient?

Re: In search of a simple consensus algorithm

#54

Post by cube2222 »

rescrv wrote: post #46
cube2222 wrote: post #43

Earlier quoted context omitted.

I think that this is cause mainly by the fact, that Leslie Lamport had first written "The one time parliment", which was said to be complex because of the language he used there. I think this is the main cause, as now there are a lot of materials available to understand Paxos.

If you mean, "The Part-time Parliament," it's indeed a little complex. It's worth reading his description of the paper to understand why: http://lamport.azurewebsites.net/pubs/pubs.html#lamport-paxo... In short, not everyone has the same sense of humor.

I now it was for fun, but it did make the algorithm substantially more complex to understand.

Paxos made simple is much easier in comparison.

Re: In search of a simple consensus algorithm

#55

Post by rystsov »

ReidZB wrote: post #45

The article abuses Kolmogorov complexity... > When it is applied to the algorithms, it means that an algorithm with the shortest implementation is simpler. That is misleading. Kolmogorov complexity is the length of the shortest program (in a pre-defined language) that produces a given object. So, if the shortest program that produces Algorithm A is smaller than the shortest program that produces Algorithm B, then the…

Thank you! I'll rework this paragraph to be correct, I wanted to make an observation that the given data (two attempts to implement key-value storages with keeping the length of a program as short as possible) favour Gryadka but of course isn't wrong to make strong statements based just on one data point.

Re: In search of a simple consensus algorithm

#56

Post by eutectic »

ReidZB wrote: post #45

The article abuses Kolmogorov complexity... > When it is applied to the algorithms, it means that an algorithm with the shortest implementation is simpler. That is misleading. Kolmogorov complexity is the length of the shortest program (in a pre-defined language) that produces a given object. So, if the shortest program that produces Algorithm A is smaller than the shortest program that produces Algorithm B, then the…

Kolmogorov complexity is not computable in general, but it is decidable for a substantial subset of programs.

Re: In search of a simple consensus algorithm

#57

Post by jerf »

rystsov wrote: post #55
ReidZB wrote: post #45

The article abuses Kolmogorov complexity... > When it is applied to the algorithms, it means that an algorithm with the shortest implementation is simpler. That is misleading. Kolmogorov complexity is the length of the shortest program (in a pre-defined language) that produces a given object. So, if the shortest program that produces Algorithm A is smaller than the shortest program that produces Algorithm B, then the…

Thank you! I'll rework this paragraph to be correct, I wanted to make an observation that the given data (two attempts to implement key-value storages with keeping the length of a program as short as possible) favour Gryadka but of course isn't wrong to make strong statements based just on one data point.

I would suggest just dropping Kolmogorov in general, and just referencing the human idea that shorter is generally going to be simpler. I wouldn't have a problem sticking with you through that. Sure, I can feed that to my pedant mill as with anything else, but since it's not really the core idea I'll roll with you on it.

Re: In search of a simple consensus algorithm

#58

Post by rystsov »

cube2222 wrote: post #25
rystsov wrote: post #24

Earlier quoted context omitted.

> consistent reads do not need a living master It's wrong. If you're fine with stale reads then you don't a living master, but if you want to have a guarantee that the read value is up-to-date then the living master is necessary. Etcd has a bug related to this - https://github.com/coreos/etcd/issues/741

It may not be up to date at the time of actually READING the data, but it will be up to date if the date is the moment the client requested it. You can actually achieve this using timestamps. (So basically, it's semi-stale data, you're right, because you have a guarantee about the timestamp at which it was up to date, where the timestamp can be recent) (Not talking about etcd, check out the spanner paper)

Yes that's true if all the communication between agents goes through the database then the Monotonic Reads consistency level is equivalent to linearizability.

In case there are off the database communications then this level of consistency isn't enough.

Re: In search of a simple consensus algorithm

#60

Post by ReidZB »

jerf wrote: post #57
rystsov wrote: post #55

Earlier quoted context omitted.

Thank you! I'll rework this paragraph to be correct, I wanted to make an observation that the given data (two attempts to implement key-value storages with keeping the length of a program as short as possible) favour Gryadka but of course isn't wrong to make strong statements based just on one data point.

I would suggest just dropping Kolmogorov in general, and just referencing the human idea that shorter is generally going to be simpler. I wouldn't have a problem sticking with you through that. Sure, I can feed that to my pedant mill as with anything else, but since it's not really the core idea I'll roll with you on it.

Agreed. The section basically boils down to "despite maybe looking simpler, Single-Decree Paxos is still tricky." I don't think something particular and formal like Kolmogorov complexity even fits the tone there.
Post reply on HN