Why not allow tie breaking?

[David Roundy]

I was wondering what the ham would be to specify one node as the tie breaker, so in case of an even network partition the cluster has a chance to proceed? It would clearly break symmetry, and would fail to help if that node went down, but could enable a four node cluster to at least sometimes handle two nodes going down, which seems like a worthwhile benefit.

Is there a problem with this idea that I'm missing?

[Henrik Ingo]

David,

To generalize what you're saying, it should be completely feasible to extend Raft so that the "amount" of votes each node can cast is something else than 1. In the case you're describing, one node could be given 1.5 votes. But you could also give a node 0 votes, 2 votes,etc... for different reasons. (For example, to weight different data centers differently, without requiring to add (or remove) another actual node.) The key thing to understand is that when considering a write command as committed, it is the majority of votes, not the majority of nodes, that is significant.

Of course, in practice you may want to enforce some limits. For example, it would in itself be correct, but also silly, for one node to have more votes than everyone else combined.

A similar, yet compeletely separate topic, is to give nodes weights that cause other nodes to prefer them (or not) when casting their vote. This is in fact much more difficult to implement, because the correctness of Raft very fundamentally is based on the idea that nodes should always and immediately vote for the node that called for a new election.

The reason Raft paper doesn't describe either of these options is most likely that they would add complexity both to the algorithm and the correctness proofs.

henrik

On Sat, Nov 25, 2017 at 8:56 PM, David Roundy <daver...@gmail.com> wrote:

I was wondering what the ham would be to specify one node as the tie breaker, so in case of an even network partition the cluster has a chance to proceed? It would clearly break symmetry, and would fail to help if that node went down, but could enable a four node cluster to at least sometimes handle two nodes going down, which seems like a worthwhile benefit.

Is there a problem with this idea that I'm missing?

--
You received this message because you are subscribed to the Google Groups "raft-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to raft-dev+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--

henri...@avoinelama.fi
+358-40-5697354        skype: henrik.ingo            irc: hingo
www.openlife.cc

My LinkedIn profile: http://fi.linkedin.com/pub/henrik-ingo/3/232/8a7

[David Roundy]

Hi Henrik,

I agree that one could assign arbitrary weights to each node's vote.  What I'm interested in is whether there is a nonequal at of weights which is better than the equal set of weights.

If we maintain the set of priorities that raft values, we would want to ensure that a majority of the nodes can always elect a leader. This fully constrains the outcomes of votes when there are an odd number of nodes.  My interest is then in improving the case where there are an even number of nodes.  With normal raft, an even number of nodes is less fault tolerant than a raft with one less node, since it requires one greater majority, meaning that one more node needs to remain operational for forward progress so be made. By using non-equal weights this downside could be eliminated, by enabling progress to be made in case of a 50% network partition.

The most obvious option would be to have a single tie-breaker node. You could imagine many other ways to divvy up the fractional vote, but any fixed arrangement gives you a 50% chance of surviving an event that takes down half the nodes, assuming all nodes have equal probability of going down.  So unless you know which nodes are more reliable, there is no reason to be more clever than a single tie breaker.

The above assumes a fixed set of voting weights.  Another option would be to dynamically delegate a tie-breaker node.  The leader can't be the tie-breaker, since when an election happens the leader is generally down.  But the leader could designate a node in good standing ( i.e. responding to heartbeats) as the tie-breaker.  This could give better than 50% odds of surviving a 50% loss. Or alternatively, the leader could pick a node that has not responded recently to be there loser  tie-breaker. This, I suppose would be equivalent to making the node have no vote.  Now that I think of this, another option would be to deny a vote to the leader of the previous term, since that leader has already demonstrated instability leading to being kicked out of office.

What I'm wondering about is whether there exists a set of rules that preserve all the benefits of raft in terms of fault tolerance and correctness, but can make an even number of nodes behave in a way that is superior to having one less node, or at least not inferior.

David

On Sat, Nov 25, 2017, 11:08 AM Henrik Ingo <henri...@avoinelama.fi> wrote:

David,

To generalize what you're saying, it should be completely feasible to extend Raft so that the "amount" of votes each node can cast is something else than 1. In the case you're describing, one node could be given 1.5 votes. But you could also give a node 0 votes, 2 votes,etc... for different reasons. (For example, to weight different data centers differently, without requiring to add (or remove) another actual node.) The key thing to understand is that when considering a write command as committed, it is the majority of votes, not the majority of nodes, that is significant.

Of course, in practice you may want to enforce some limits. For example, it would in itself be correct, but also silly, for one node to have more votes than everyone else combined.

A similar, yet compeletely separate topic, is to give nodes weights that cause other nodes to prefer them (or not) when casting their vote. This is in fact much more difficult to implement, because the correctness of Raft very fundamentally is based on the idea that nodes should always and immediately vote for the node that called for a new election.

The reason Raft paper doesn't describe either of these options is most likely that they would add complexity both to the algorithm and the correctness proofs.

henrik

On Sat, Nov 25, 2017 at 8:56 PM, David Roundy <daver...@gmail.com> wrote:

I was wondering what the ham would be to specify one node as the tie breaker, so in case of an even network partition the cluster has a chance to proceed? It would clearly break symmetry, and would fail to help if that node went down, but could enable a four node cluster to at least sometimes handle two nodes going down, which seems like a worthwhile benefit.

Is there a problem with this idea that I'm missing?

--
You received this message because you are subscribed to the Google Groups "raft-dev" group.

To unsubscribe from this group and stop receiving emails from it, send an email to raft-dev+u...@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

--

henri...@avoinelama.fi
+358-40-5697354        skype: henrik.ingo            irc: hingo
www.openlife.cc

My LinkedIn profile: http://fi.linkedin.com/pub/henrik-ingo/3/232/8a7

--
You received this message because you are subscribed to a topic in the Google Groups "raft-dev" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/raft-dev/4w-M6mFKXg0/unsubscribe.
To unsubscribe from this group and all its topics, send an email to raft-dev+u...@googlegroups.com.

[Ben Darnell]

Flexible Paxos (https://fpaxos.github.io/) by Heidi Howard, Dahlia Malkhi, and Alexander Spiegelman discusses changes to quorums in Paxos that can be generalized to Raft. The key idea is that you can use different quorums for leader elections and for committing log entries. The simplest application of this is that if you require greater than half the votes for a leader election, you can commit log entries with responses from exactly half the nodes. This gives clusters with an even number of nodes a slight advantage: they can survive the temporary loss of half the nodes as long as the leader is on the surviving side. 

-Ben

[Martin Furmanski]

Using something like flexible paxos you would invariably lose some data safety.