Raft paper question regarding ranks and elections

[Kavinda Wewegama]

Hello,

I didn't understand the bolded sentence below from section 5.2 of the (awesome!) Raft paper:

Elections are an example of how understandability guided our choice between design alternatives. Initially we planned to use a ranking system: each candidate was assigned a unique rank, which was used to select between competing candidates. If a candidate discovered another candidate with higher rank, it would return to follower state so that the higher ranking candidate could more eas- ily win the next election. We found that this approach created subtle issues around availability (a lower-ranked server might need to time out and become a candidate again if a higher-ranked server fails, but if it does so too soon, it can reset progress towards electing a leader). We made adjustments to the algorithm several times, but after each adjustment new corner cases appeared. Eventually we concluded that the randomized retry approach is more obvious and understandable.

Is this saying that if a higher ranked candidate H fails during an election, and a lower ranked candidate L times out before H fails, it can slow down the election completion process?  Is the (lack of) availability referring to the fact that we won't have a leader during this time?

Thanks!

[Kijana Woodard]

Just to confirm, you're trying to explore the nuances of the approach that the Raft author's rejected?

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

[K]

Hello Kijana,

I am interested in making sure I understand the "subtle issues around availability" that ranking causes.  In other words, I want to ensure that I fully/correctly interpreted the scenario the paper gives and didn't miss some other subtlety.

Thanks.

[Kijana Woodard]

Ok, but Raft doesn't use ranking. The section you cited states that such an approach was rejected because it created those "subtle issues". I'm fairly sure that's the first & last time you'll see "ranking" mentioned in the entire paper.

"Initially we planned to use a ranking system...Eventually we concluded that the randomized retry approach is more obvious and understandable."

The randomized approach is what is used in Raft.

[K]

Hello Kijana,

Thank you for the reply.  I understand that Raft doesn't use ranking to elect leaders.  My question deals with understanding the availability issue that ranking causes.  Let me see if I can rephrase my question better.

The Raft paper mentions the following:

Initially we planned to use a ranking system: each candidate was assigned a unique rank, which was used to select between competing candidates. If a candidate discovered another candidate with higher rank, it would return to follower state so that the higher ranking candidate could more eas- ily win the next election. We found that this approach created subtle issues around availability (a lower-ranked server might need to time out and become a candidate again if a higher-ranked server fails, but if it does so too soon, it can reset progress towards electing a leader). We made adjustments to the algorithm several times, but after each adjustment new corner cases appeared. Eventually we concluded that the randomized retry approach is more obvious and understandable.

My interpretation of the bolded section above was this:

If a higher ranked candidate H fails during an election, and a lower ranked candidate L times out before H fails, it can slow down the election completion process.  The (lack of) availability issue is referring to the fact that we won't have a leader during this time.

So the question I have is whether my interpretation is correct.  Or is "subtle issues around availability" referring to some other scenario?

[Oren Eini (Ayende Rahien)]

K,

Imagine that you have three servers, H, L and N.

H has high priority.

L has lower priority.

N has lowest priority.

1) H is the leader.

2) Now we have a transient failure, L decides to become leader and call elections.

3) H is up, see that there was an election, see that it is higher rank, and force another election.

4) Transient failure.

5) Go to step 2

Now you have unavailable cluster.

It also cause issues when you have multiple ranks participating with the election with different timeouts.

L1 might timeout later than L2, so L2 starts elections, then L1 force it out when it times out, etc.

Hibernating Rhinos Ltd  

Oren Eini l CEO l Mobile: + 972-52-548-6969

Office: +972-4-622-7811 l Fax: +972-153-4-622-7811

 

[Diego Ongaro]

Hey,

My memory is pretty fuzzy here, but I think Kavinda is right.

The lower-ranking servers must have a timeout, otherwise a failure of a higher-ranking server could cause a permanent outage.

Now suppose a higher-ranking server has made itself relatively known, so that it's likely to collect enough votes in the next term, but then a lower-ranking server times out.  All progress is now reset, and the higher-ranking server has to be re-discovered.  Maybe it'd work in practice, but it's not obvious to me how many terms I'd expect an election to take or how to set that timeout value.

As the paper states, we discarded this approach in favor of the randomized timeouts. One nice thing about the randomized approach is that, assuming your timeouts are sort of reasonable and your PRNGs barely function, it's not going to get stuck in some pathological case over and over again.

-Diego

[K]

Hello Ayende and Diego,

Your replies answered my question and clarified my understanding.  Thank you very much!