4 ms·

It is my understanding that the motivation in seeking out consensus algorithms with strong leaders (or equivalent) as opposed to horizontally weighted peer-to-p

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, circumventing the cost of determining 'consensus' every single time. It's readily apparent that this would lend to a performance penalty in the pathological case, as is demonstrated here, when the leader node is taken down repeatedly - but I'm skeptical if this is true for workloads that systems like coreos/etcd, cockroachdb/cockroach were intended to handle.

forgotpwtomain 10y ago
> 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. Yeah, that was my understanding as well but without having read the paper in question (as of yet) I'm entirely short on the particular technical details of the trade-offs.
- stelfer 10y ago
  I didn't read the whole thing carefully, but... Leader Election + Terminating Reliable Broadcast is practically equivalent to building the Weakest Failure Detector and is the most feasible way of doing so. So, there are good reasons for doing leader election. This is why almost every serious consensus system ends up doing it whether they know they need to or not.
SEJeff 10y ago
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 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 while allowing less quorum nodes for quorum read/write. This means you get strong consistency with better performance. Distributed systems are one of my favorite things. I literally spent part of an evening with a beer reading a small handful of papers like this one. If you want an absolute treasure trove of similar works, visit the blog of Adrian Coyler: https://blog.acolyer.org/ https://blog.acolyer.org/ He has a good writeup on the Flexible Paxos paper as well: https://blog.acolyer.org/2016/09/27/flexible-paxos-quorum-intersection-revisited/ https://blog.acolyer.org/2016/09/27/flexible-paxos-quorum-in...
- irfansharif 10y ago
  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.
  - SEJeff 10y ago
    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
- rystsov 10y ago
  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 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 :)
- Xorlev 10y ago
  > I literally spent part of an evening with a beer Just one? :) Consensus algorithms are _fascinating_! And +1 for https://blog.acolyer.org/ 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 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/ https://raft.github.io/
  - SEJeff 10y ago
rystsov 10y ago
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).
- leg 10y ago
  The performance penalty is on reads. If you elect a leader with a timeout you can do strong reads without re-establishing consensus.
  - rystsov 10y ago
    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 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.
    - leg 10y ago
      etcd didn't implement leases; it just assumed that the last Raft election was still good. You can elect a leader for a set period of time (say, 10 seconds) and serve strong reads for a lesser period of time (5 seconds) if you have reasonable assumptions of how good your local oscillators work and avoid jumps. If you don't trust your local clock to any level of accuracy, why do you trust your local CPU? Cockroach DB does this correctly. https://github.com/cockroachdb/cockroach/blob/master/docs/design.md#range-leases https://github.com/cockroachdb/cockroach/blob/master/docs/de...
      - rystsov 10y ago
        Making implicit assumptions about the environment is wrong. An instance may be running in virtual environment where time freezes are possible. A human may make an error and rollback time to 1970. It's impossible to eliminate all these factors so yes I don't trust time but I trust CPU. Maybe CockroachDB is doing it correctly but the terrible default settings make this optimisation negligible because when the leader dies the system hangs for 12 seconds.
bdarnell 10y ago
The raft paper states that its use of an explicit leader election was chosen for understandability, not performance. Leaderless systems can potentially improve performance, especially when replicas are far apart (so you don't have the extra network hop to the leader before you can get started). The main drawback IMHO to ePaxos (as a hopefully representative leaderless algorithm) is not performance but its complexity, since it intrudes into the application to track dependencies and conflicts between proposed commands. If I squint at the scheme proposed here, it looks like ePaxos taken to the extreme of a single key/value per paxos group, so conflict tracking becomes trivial. It has demonstrated good performance in the case of uncontended writes; I'd be curious to see how it behaves under contention, or when a downed node rejoins the cluster.

forgotpwtomain 10y ago

> 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. Yeah, that was my understanding as well but without having read the paper in question (as of yet) I'm entirely short on the particular technical details of the trade-offs.

stelfer 10y ago
I didn't read the whole thing carefully, but... Leader Election + Terminating Reliable Broadcast is practically equivalent to building the Weakest Failure Detector and is the most feasible way of doing so. So, there are good reasons for doing leader election. This is why almost every serious consensus system ends up doing it whether they know they need to or not.

SEJeff 10y ago

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 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 while allowing less quorum nodes for quorum read/write. This means you get strong consistency with better performance. Distributed systems are one of my favorite things. I literally spent part of an evening with a beer reading a small handful of papers like this one. If you want an absolute treasure trove of similar works, visit the blog of Adrian Coyler: https://blog.acolyer.org/ https://blog.acolyer.org/ He has a good writeup on the Flexible Paxos paper as well: https://blog.acolyer.org/2016/09/27/flexible-paxos-quorum-intersection-revisited/ https://blog.acolyer.org/2016/09/27/flexible-paxos-quorum-in...

irfansharif 10y ago
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.
- SEJeff 10y ago
  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
rystsov 10y ago
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 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 :)
Xorlev 10y ago
> I literally spent part of an evening with a beer Just one? :) Consensus algorithms are _fascinating_! And +1 for https://blog.acolyer.org/ 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 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/ https://raft.github.io/
- SEJeff 10y ago

rystsov 10y ago

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

leg 10y ago
The performance penalty is on reads. If you elect a leader with a timeout you can do strong reads without re-establishing consensus.
- rystsov 10y ago
  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 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.
  - leg 10y ago
    etcd didn't implement leases; it just assumed that the last Raft election was still good. You can elect a leader for a set period of time (say, 10 seconds) and serve strong reads for a lesser period of time (5 seconds) if you have reasonable assumptions of how good your local oscillators work and avoid jumps. If you don't trust your local clock to any level of accuracy, why do you trust your local CPU? Cockroach DB does this correctly. https://github.com/cockroachdb/cockroach/blob/master/docs/design.md#range-leases https://github.com/cockroachdb/cockroach/blob/master/docs/de...
    - rystsov 10y ago
      Making implicit assumptions about the environment is wrong. An instance may be running in virtual environment where time freezes are possible. A human may make an error and rollback time to 1970. It's impossible to eliminate all these factors so yes I don't trust time but I trust CPU. Maybe CockroachDB is doing it correctly but the terrible default settings make this optimisation negligible because when the leader dies the system hangs for 12 seconds.

bdarnell 10y ago

The raft paper states that its use of an explicit leader election was chosen for understandability, not performance. Leaderless systems can potentially improve performance, especially when replicas are far apart (so you don't have the extra network hop to the leader before you can get started). The main drawback IMHO to ePaxos (as a hopefully representative leaderless algorithm) is not performance but its complexity, since it intrudes into the application to track dependencies and conflicts between proposed commands. If I squint at the scheme proposed here, it looks like ePaxos taken to the extreme of a single key/value per paxos group, so conflict tracking becomes trivial. It has demonstrated good performance in the case of uncontended writes; I'd be curious to see how it behaves under contention, or when a downed node rejoins the cluster.