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

21–30 of 87 posts

Re: In search of a simple consensus algorithm

#21

Post by leg »

rystsov wrote: post #17
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…

What is the performance penalty you're talking about? Gryadka does 1 roundtrip to write a value and its performance (4720 rps, 1.68ms latency) is very similar to Etcd (5227 rps, 1.55ms).

The performance penalty is on reads. If you elect a leader with a timeout you can do strong reads without re-establishing consensus.

Re: In search of a simple consensus algorithm

#22

Post by SEJeff »

irfansharif wrote: post #18
SEJeff wrote: post #14

Earlier quoted context omitted.

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…

yup, I've been closely following Heidi's work for some time now - non-intersecting consensus groups, still hoping someone beats me to a Go implementation so I don't have to. +1 for Adrian Coyler's blog, constantly amazed at the sheer volume and depth of his analyses.

Ah got it. I was thinking, "Wow, this is literally someone describing the Flexible Paxos work. I wonder if they have read the paper?"

Distributed systems learning ftw

Re: In search of a simple consensus algorithm

#23

Post by rystsov »

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…

Btw, Gryadka uses an idea of quorums with non-standard size to change a configuration of the cluster, see http://rystsov.info/2016/01/05/raft-paxos.html#details1. I came up with this idea independently of Howard when misread the Vertical Paxos paper :)

Re: In search of a simple consensus algorithm

#24

Post by rystsov »

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

Re: In search of a simple consensus algorithm

#25

Post by cube2222 »

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

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)

Re: In search of a simple consensus algorithm

#26

Post by rystsov »

leg wrote: post #21
rystsov wrote: post #17

Earlier quoted context omitted.

What is the performance penalty you're talking about? Gryadka does 1 roundtrip to write a value and its performance (4720 rps, 1.68ms latency) is very similar to Etcd (5227 rps, 1.55ms).

The performance penalty is on reads. If you elect a leader with a timeout you can do strong reads without re-establishing consensus.

Etcd used this scheme to provide fast reads but Aphyr demonstrated that it may lead to stale reads https://github.com/coreos/etcd/issues/741.

If you can't afford stale reads then you should ask Etcd to wait for confirmation from the majority of followers before acknowledging a read with ?quorum=true. It makes Etcd do 1 round trip for reads (just like Gryadka).

The same is applicable to other products (you can't relay on time in distributed systems, unless you're Google, consequently you can't relay on read leases)

So there is no performance penalty.

Re: In search of a simple consensus algorithm

#27

Post by sseveran »

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)

TrueTime is a very special case. I have not seen anyone else who has the same hardware infrastructure required to provide guarantees related to wall-clock time. Spanner also trades off transaction latency to create the wall clock time guarantees, so its not magically free.

Re: In search of a simple consensus algorithm

#28

Post by rystsov »

badminton1 wrote: post #12

I wonder what are the author thoughts on ZAB.

I don't have a deep understanding of how ZAB works but based on the documentation (initLimit) and prior experience with ZooKeeper, ZAB has the same issues as Raft when a leader dies.

Folk from Elastifile demonstrated it in their Bizur paper - https://arxiv.org/abs/1702.04242v1

Re: In search of a simple consensus algorithm

#30

Post by rescrv »

Paxos's complexity is often overstated. I made a simple implementation of Paxos for a key-value store as a proof of concept to demonstrate how you can simplify Paxos by removing leader election, multi-master management, and log garbage collection.

Here's my blog post on the issue: http://hack.systems/2017/03/13/pocdb/

The entire implementation is 1100 lines of code including comments.

Post reply on HN