Re: Effect of not storing votedFor, on leader-election

[Diego Ongaro]

Hi Unmesh (CC raft-dev),

You should know that I've forgotten so many things by now and that raft-dev is a better place for questions. Off the top of my head, though, you just can't allow a server to vote for two different candidates in the same term. You don't strictly need to persist who a server voted for. I think in a very early implementation I didn't persist the vote at all and just had servers decline to vote upon boot until the next term. I believe John convinced me that persisting votedFor is simpler conceptually, as it's one less thing to explain. From our perspective, persisting the vote wasn't intended as an optimization; *not* persisting the vote would be an optimization.

Hope this helps,

Diego

On Wed, Sep 14, 2022 at 9:07 PM Unmesh Joshi <unmes...@gmail.com> wrote:

Hi,

I was thinking about the effect of not remembering votedFor for the raft leader election. The leader election is essentially phase 1 of Paxos which establishes a unique term number (a ballot or what I call a monotonic generation-clock pattern) which can then be used to propose values. Establishing a unique term by voting needs the last promised term to be stored and persisted on each node. I see that votedFor essentially makes the requestVote idempotent for a candidate. But worst case, if votedFor is not stored, the candidate won't be able to retry the requestVote requests and will need to restart the election (after a random wait). That way, storing votedFor only helps with progress (by not needing a suitable candidate to unnecessarily restart election), but it does not affect safety in any way.

Is it fair to say that votedFor is essentially stored to make leader elections progress faster in case a candidate needs to retry the requestVote messages?

Thanks,

Unmesh

[Unmesh Joshi]

Thanks Diego. It helps. I am curious to know from the people in this group if they will find it easier to understand leader election if votedFor is removed and explained as an addition to allow requestVote retries from the candidate and avoid unnecessary declines until the next term.

Thanks,

Unmesh

[Bhavin Thaker]

Hi Unmesh, 

No, because as mentioned by Diego, 

“ you just can't allow a server to vote for two different candidates in the same term.”

It is important to understand that “votedFor” is an important and core concept for “safety” of the RAFT protocol having a node voting for ONLY one candidate during a particular term.

Hence, the votedFor explanation is a core component of the overall description 

… in my humble opinion.

Bhavin Thaker.

--
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.
To view this discussion on the web visit https://groups.google.com/d/msgid/raft-dev/CAOk%2Bzfd%3D4m5sdeUQ0yTiGaXqq-66JhvkLiE0K1jYPfmTXd9n-Q%40mail.gmail.com.

[Unmesh Joshi]

It won't affect safety, but will cause a delay for one more term to elect a leader in the worst case. I think in general, a mechanism to establish epoch/term/generation by quorum voting can be safe if it responds only to strictly greater epoch values. The need to remember the proposer is there if it chooses to respond to greater than or equal values of epochs. If this "or equals" condition is removed then it's safe. No?

To view this discussion on the web visit https://groups.google.com/d/msgid/raft-dev/CAFdgvPHj0f92qnrP2uMsVV97b4di1aQkuUPb6ox7hsBOKVaUGw%40mail.gmail.com.

[Jesper Lindholm]

Allowing a node to vote for two different candidates during the same term absolutely affects safety. The guarantees of safety are based on a few “properties”, one of which is the promise and assumption that any one node will only ever vote for one candidate during a given term. For more information, see the Raft paper. 

/Jesper

16 sep. 2022 kl. 20:16 skrev Unmesh Joshi <unmes...@gmail.com>:



To view this discussion on the web visit https://groups.google.com/d/msgid/raft-dev/CAOk%2Bzfepbzxm63itUYC1rozDpiOdVAptAUFy0XoQAvV4WwOjRQ%40mail.gmail.com.

[Unmesh Joshi]

It won't vote for two candidates for the same term if it responds only once to 

each term and remembers the term. This is equivalent to paxos prepare phase not responding to ballot equal to the last promised ballot. 

To view this discussion on the web visit https://groups.google.com/d/msgid/raft-dev/2BD08C0F-744A-4271-8B2E-10F9D1F2BFF1%40treetop.se.

[Jesper Lindholm]

Sorry, not the paper, the dissertation (at https://github.com/ongardie/dissertation#readme ). Figure 3.2 lists all the properties which does not include this directly, but section 3.4 includes “Each server will vote for at most one candidate in a given term, on a first- come-first-served basis” which does not leave any leeway. 

/Jesper

16 sep. 2022 kl. 20:24 skrev Jesper Lindholm <Jesper....@treetop.se>:

 Allowing a node to vote for two different candidates during the same term absolutely affects safety. The guarantees of safety are based on a few “properties”, one of which is the promise and assumption that any one node will only ever vote for one candidate during a given term. For more information, see the Raft paper. 

[Jesper Lindholm]

I agree but if that’s the case I don’t understand the purpose of removing votedFor or allowing the election to run longer. If being able to respond in time is an issue, that suggest there’s a problem with the election duration for the current circumstances. 

/Jesper

16 sep. 2022 kl. 20:29 skrev Unmesh Joshi <unmes...@gmail.com>:



To view this discussion on the web visit https://groups.google.com/d/msgid/raft-dev/CAOk%2BzffhHTwC%3Dutd6pwGx5DyYneuQ-t8Vs1Toa61viYZ9xFUCA%40mail.gmail.com.

[Bhavin Thaker]

+1 to Jesper’s reply.

Bhavin Thaker.

To view this discussion on the web visit https://groups.google.com/d/msgid/raft-dev/2BD08C0F-744A-4271-8B2E-10F9D1F2BFF1%40treetop.se.

[Unmesh Joshi]

Election will run longer only if response to the candidate gets lost and candidate retries the requestvote which will be rejected. So its good to mention the reason explicitly. 

Raft's leader election mechanism is a good example of an implementation to establish monotonic epochs by quorum voting, and this mechanism only needs to remember last promised epoch and nothing more.

I wanted to check if looking at it in this general form, allows to understand it as a pattern. (That way making it easier to map it to Paxos's prepare phase, or ViewStamp replication's startViewChange phase or Zab's epoch establishment mechanism)

To view this discussion on the web visit https://groups.google.com/d/msgid/raft-dev/969B0680-2AC5-4F7D-AF39-9F115EA8B55A%40treetop.se.

[Unmesh Joshi]

Just to give some context on why I am trying out more generic descriptions and implementations is that I am trying to document common patterns in distributed system implementations.  I am restructuring some patterns, particularly Quorum ('Quorum Intersection' might be a better word) and Generation Clock (Epoch).  Raft can be viewed as a pattern sequence to implement Replicated Log like this. 

https://martinfowler.com/articles/patterns-of-distributed-systems/#PatternSequenceForImplementingReplicatedLog