Does every technical article need to be scattered with Impact font memes now?
In search of a simple consensus algorithm
31–40 of 87 posts
Re: In search of a simple consensus algorithm
#32Earlier quoted context omitted.
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.
It isn't, I haven't said it is. The point is, there are disadvantages you are writing about, that aren't really disadvantages of the protocol itself, but disadvantages of the common implementations.
Re: In search of a simple consensus algorithm
#33Earlier 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)
In order to get a linearizable read in Spanner, you do need to have a heartbeat from the leader of the Paxos tablet for the data you are reading in order to know that all data has been replicated up to the time at which you are taking your read. This is not free, but can be cheaper than active communication. (referred to as t_safe in the paper)
Re: In search of a simple consensus algorithm
#34Earlier quoted context omitted.
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)
In order to get a linearizable read in Spanner, you do need to have a heartbeat from the leader of the Paxos tablet for the data you are reading in order to know that all data has been replicated up to the time at which you are taking your read. This is not free, but can be cheaper than active communication. (referred to as t_safe in the paper)
As I understood it, if you are actually reading at some point it time (let's say 100 ms ago), then the non-leader node can check for himself, if he was in contact with the master after this point of time and give you an answer.
Re: In search of a simple consensus algorithm
#35I 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…
> If you have one paxos/raft group per replica, you actually only get a small unavailability
It isn't a small unavailability, it's an unavailability of the whole replica. If you don't have a lot of data then it's the whole cluster :)
Of cause, we can introduce something like virtual replicas and eventually end up with a replica per key which is almost a Single Decree Paxos but with an overhead on log compaction and snapshotting.
Re: In search of a simple consensus algorithm
#36I am surprised:
1. I am technically pretty strong but I have no idea what this paper is about
2. So many people know this is about that it shot up to #1 on HN
Can someone give a pointer (a link or two) to the lay, interested audience here about what the field IS. Just a sort of intro guide to someone who knows about programming and math, but has never heard the term paxos?
I am curious, and I am sure many others are as well.
edit: spelling
Re: In search of a simple consensus algorithm
#37Earlier quoted context omitted.
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 rela…
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/de...
Re: In search of a simple consensus algorithm
#38I 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…
> If you have one paxos/raft group per replica, you actually only get a small unavailability It isn't a small unavailability, it's an unavailability of the whole replica. If you don't have a lot of data then it's the whole cluster :) Of cause, we can introduce something like virtual replicas and eventually end up with a replica per key which is almost a Single Decree Paxos but with an overhead on log compaction and s…
Well, the unavailability is around 1/(number of machines in cluster) with a sufficient amount of replicas. That said, it's small relative to a whole-cluster unavailability and with small leader timeouts, it gets much better than you described in your article.
Btw, thanks for answering my comments actively, I really appreciate it!
Re: In search of a simple consensus algorithm
#39I am surprised: 1. I am technically pretty strong but I have no idea what this paper is about 2. So many people know this is about that it shot up to #1 on HN Can someone give a pointer (a link or two) to the lay, interested audience here about what the field IS. Just a sort of intro guide to someone who knows about programming and math, but has never heard the term paxos? I am curious, and I am sure many others are…
It's basically the topic of distributed computing and algorithms for the coordination of distributed systems.
This is a great introductory course about it in my opinion: https://www.coursera.org/learn/cloud-computing
Then, it's just reading papers like, which you mentioned, "The part time parliment" (paxos)
Re: In search of a simple consensus algorithm
#40I am surprised: 1. I am technically pretty strong but I have no idea what this paper is about 2. So many people know this is about that it shot up to #1 on HN Can someone give a pointer (a link or two) to the lay, interested audience here about what the field IS. Just a sort of intro guide to someone who knows about programming and math, but has never heard the term paxos? I am curious, and I am sure many others are…
Wikipedia is pretty good. The page for "consensus algorithm" has links for Paxos and Raft.
The basic idea is how to coordinate multiple independent agents over an unreliable network. For example, multiple servers trying to manage a shared database. Lots of HN people know about this because it's a key building block of reliable and scalable cloud computing.