News for hackers. Stuff that matters.
Re:In search of a simple consensus algorithm by cube2222 on Friday March 17, 2017 @10:30AM (#13894214)
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 actually), this way you have shorter unavailability.

There's another point he touches, about the unavailability of the whole cluster when the leader is down. Really, this isn't something dependent on the protocols, but on the applications. If you have one paxos/raft group per replica, you actually only get a small unavailability. Additionally, even consistent reads do not need a living master to be possible.

It's worth reading the spanner paper to get more insight into high availability/consistency achieved with a paxos based db implementation ( https://static.googleusercontent.com/media/research.google.c... ).

EDIT: And in my opionion, calling it a SPOF is missing the point a little bit.

Re:In search of a simple consensus algorithm by rystsov on Friday March 17, 2017 @11:25AM (#13894665)
> 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 by cube2222 on Friday March 17, 2017 @11:38AM (#13894777)
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 by rescrv on Friday March 17, 2017 @11:51AM (#13894900)
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 by cube2222 on Friday March 17, 2017 @11:54AM (#13894937)
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 by sseveran on Friday March 17, 2017 @11:43AM (#13894819)
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 by cube2222 on Friday March 17, 2017 @11:50AM (#13894892)
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 by rystsov on Friday March 17, 2017 @01:10PM (#13895768)
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 by iambvk on Friday March 17, 2017 @12:33PM (#13895337)
When leader is not around, isn't a majority read sufficient?
Re:In search of a simple consensus algorithm by krenoten on Friday March 17, 2017 @01:34PM (#13896018)
It depends on the implementation. If you have a replication system that generates a monotonic sequence ID for each update, and you have all writes block on a majority of replicas acking an update, then you can just read from a majority and pick the result with the highest monotonic identifier. This will not be consistent unless the leadership mechanism demands that leadership is chosen based on the same criteria.
Re:In search of a simple consensus algorithm by rystsov on Friday March 17, 2017 @11:56AM (#13894953)
> 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 by cube2222 on Friday March 17, 2017 @12:00PM (#13895002)
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 by eutectic on Friday March 17, 2017 @12:06PM (#13895063)
Just fyi, you were presumably thinking of incur rather than infer.
Re:In search of a simple consensus algorithm by cube2222 on Friday March 17, 2017 @12:08PM (#13895085)
Thank you, I'm not a native speaker :)