Improve leader election convergence

When 2 nodes startup with the first node's log behind the second node's,
it usually takes several election rounds to converge - I've seen
anywhere from 40 s to 3 min, depending on timing. What happens is that
the first node goes to Candidate first but it's RequestVote is rejected
by the seconds node. Shortly after the seconds node goes to Candidate -
the term is higher than the first which causes the first node to go back
to Follower. However it doesn't respond to the RequestVote. Then the
first node goes to Candidate and the cycle repeats. Eventually, due to
the election variance, the seconds node times out first and the second
node process the RequestVote and grants it. But it can take more than 10
cycles.

We can improve the convergence by allowing a Candidate to process and
respond to RequestVote when the sender's term is greater. It still
transitions to Follower as per the raft rules. The raft paper does not
say whether or not a Candidate can/should process a RequestVote in this
case but it seems to make sense. With this change, the first RequestVote
sent by the second node is granted and it converges quickly.

Change-Id: If9416ddf7bf0dfc1220a169be4174f440626a0dd
Signed-off-by: Tom Pantelis <tpanteli@brocade.com>

diff --git a/opendaylight/md-sal/sal-akka-raft/src/main/java/org/opendaylight/controller/cluster/raft/behaviors/Candidate.java b/opendaylight/md-sal/sal-akka-raft/src/main/java/org/opendaylight/controller/cluster/raft/behaviors/Candidate.java
index 4d51922bc22f7c2bc63886989e354cfb0e912288..1205c4bad66ed26e4a305d45612b2881464de533 100644 (file)
--- a/opendaylight/md-sal/sal-akka-raft/src/main/java/org/opendaylight/controller/cluster/raft/behaviors/Candidate.java
+++ b/opendaylight/md-sal/sal-akka-raft/src/main/java/org/opendaylight/controller/cluster/raft/behaviors/Candidate.java
@@ -157,6 +157,12 @@ public class Candidate extends AbstractRaftActorBehavior {
             if (rpc.getTerm() > context.getTermInformation().getCurrentTerm()) {
                 context.getTermInformation().updateAndPersist(rpc.getTerm(), null);
 
+                // The raft paper does not say whether or not a Candidate can/should process a RequestVote in
+                // this case but doing so gains quicker convergence when the sender's log is more up-to-date.
+                if (message instanceof RequestVote) {
+                    super.handleMessage(sender, message);
+                }
+
                 return internalSwitchBehavior(RaftState.Follower);
             }
         }

diff --git a/opendaylight/md-sal/sal-akka-raft/src/test/java/org/opendaylight/controller/cluster/raft/behaviors/CandidateTest.java b/opendaylight/md-sal/sal-akka-raft/src/test/java/org/opendaylight/controller/cluster/raft/behaviors/CandidateTest.java
index 6e5c9315025a9ab68950245eafee0861bf697547..40080a8c72ba7978d365057fcd875897307048b4 100644 (file)
--- a/opendaylight/md-sal/sal-akka-raft/src/test/java/org/opendaylight/controller/cluster/raft/behaviors/CandidateTest.java
+++ b/opendaylight/md-sal/sal-akka-raft/src/test/java/org/opendaylight/controller/cluster/raft/behaviors/CandidateTest.java
@@ -313,7 +313,7 @@ public class CandidateTest extends AbstractRaftActorBehaviorTest<Candidate> {
         context.getTermInformation().update(2, "test");
 
         // Send an unknown message so that the state of the RaftActor remains unchanged
-        RaftActorBehavior expected = behavior.handleMessage(candidateActor, "unknown");
+        behavior.handleMessage(candidateActor, "unknown");
 
         RaftActorBehavior raftBehavior = behavior.handleMessage(candidateActor, appendEntries);
 
@@ -333,6 +333,7 @@ public class CandidateTest extends AbstractRaftActorBehaviorTest<Candidate> {
         return new MockRaftActorContext("candidate", getSystem(), candidateActor);
     }
 
+    @SuppressWarnings("unchecked")
     private Map<String, String> setupPeers(final int count) {
         Map<String, String> peerMap = new HashMap<>();
         peerActors = new TestActorRef[count];
@@ -349,6 +350,10 @@ public class CandidateTest extends AbstractRaftActorBehaviorTest<Candidate> {
     protected void assertStateChangesToFollowerWhenRaftRPCHasNewerTerm(final MockRaftActorContext actorContext,
             final ActorRef actorRef, final RaftRPC rpc) throws Exception {
         super.assertStateChangesToFollowerWhenRaftRPCHasNewerTerm(actorContext, actorRef, rpc);
-        assertEquals("New votedFor", null, actorContext.getTermInformation().getVotedFor());
+        if(rpc instanceof RequestVote) {
+            assertEquals("New votedFor", ((RequestVote)rpc).getCandidateId(), actorContext.getTermInformation().getVotedFor());
+        } else {
+            assertEquals("New votedFor", null, actorContext.getTermInformation().getVotedFor());
+        }
     }
 }