Improve follower term conflict resolution

Rather than performing a linear search downwards for a matching
log entry, take into account follower's last log index. This
eliminates the need for a lot of round-trips if the follower is
far behind the leader, but does not have a complete common ancestry.

Change-Id: I63c815f108d322de5d438a6eda43aaa7982d820a
Signed-off-by: Robert Varga <robert.varga@pantheon.tech>

diff --git a/opendaylight/md-sal/sal-akka-raft/src/main/java/org/opendaylight/controller/cluster/raft/FollowerLogInformation.java b/opendaylight/md-sal/sal-akka-raft/src/main/java/org/opendaylight/controller/cluster/raft/FollowerLogInformation.java
index fe836362c819211dc0720daadbbdaa89c8c8dd5d..ca3de5944b6c4c9c732230d495f12dfefd57bd42 100644 (file)
--- a/opendaylight/md-sal/sal-akka-raft/src/main/java/org/opendaylight/controller/cluster/raft/FollowerLogInformation.java
+++ b/opendaylight/md-sal/sal-akka-raft/src/main/java/org/opendaylight/controller/cluster/raft/FollowerLogInformation.java
@@ -89,16 +89,23 @@ public final class FollowerLogInformation {
     }
 
     /**
-     * Decrements the value of the follower's next index.
+     * Decrements the value of the follower's next index, taking into account its reported last log index.
      *
-     * @return true if the next index was decremented, ie it was previously >= 0, false otherwise.
+     * @param followerLastIndex follower's last reported index.
+     * @return true if the next index was decremented, i.e. it was previously >= 0, false otherwise.
      */
-    public boolean decrNextIndex() {
+    public boolean decrNextIndex(final long followerLastIndex) {
         if (nextIndex < 0) {
             return false;
         }
 
-        nextIndex--;
+        if (followerLastIndex >= 0 && nextIndex > followerLastIndex) {
+            // If the follower's last log index is lower than nextIndex, jump directly to it, so we converge
+            // on a common index more quickly.
+            nextIndex = followerLastIndex;
+        } else {
+            nextIndex--;
+        }
         return true;
     }
 

diff --git a/opendaylight/md-sal/sal-akka-raft/src/main/java/org/opendaylight/controller/cluster/raft/behaviors/AbstractLeader.java b/opendaylight/md-sal/sal-akka-raft/src/main/java/org/opendaylight/controller/cluster/raft/behaviors/AbstractLeader.java
index 2175eb75557d743cbe09020f9408035f69e31c75..fbdfd49a3ff48c9c8eaee2012fbc2c7ff0460286 100644 (file)
--- a/opendaylight/md-sal/sal-akka-raft/src/main/java/org/opendaylight/controller/cluster/raft/behaviors/AbstractLeader.java
+++ b/opendaylight/md-sal/sal-akka-raft/src/main/java/org/opendaylight/controller/cluster/raft/behaviors/AbstractLeader.java
@@ -306,10 +306,9 @@ public abstract class AbstractLeader extends AbstractRaftActorBehavior {
                     + "updated: matchIndex: {}, nextIndex: {}", logName(), followerId,
                     followerLogInformation.getMatchIndex(), followerLogInformation.getNextIndex());
             } else {
-                // The follower's log conflicts with leader's log so decrement follower's next index by 1
+                // The follower's log conflicts with leader's log so decrement follower's next index
                 // in an attempt to find where the logs match.
-
-                if (followerLogInformation.decrNextIndex()) {
+                if (followerLogInformation.decrNextIndex(appendEntriesReply.getLogLastIndex())) {
                     updated = true;
 
                     log.info("{}: follower {} last log term {} conflicts with the leader's {} - dec next index to {}",

diff --git a/opendaylight/md-sal/sal-akka-raft/src/test/java/org/opendaylight/controller/cluster/raft/FollowerLogInformationTest.java b/opendaylight/md-sal/sal-akka-raft/src/test/java/org/opendaylight/controller/cluster/raft/FollowerLogInformationTest.java
index d22e9e5eb0a09c223bffb204d97c07eed5fddc8c..8e80e30d8bee736e6aad87cd3992c2065085d932 100644 (file)
--- a/opendaylight/md-sal/sal-akka-raft/src/test/java/org/opendaylight/controller/cluster/raft/FollowerLogInformationTest.java
+++ b/opendaylight/md-sal/sal-akka-raft/src/test/java/org/opendaylight/controller/cluster/raft/FollowerLogInformationTest.java
@@ -121,13 +121,13 @@ public class FollowerLogInformationTest {
         FollowerLogInformation followerLogInformation =
                 new FollowerLogInformation(new PeerInfo("follower1", null, VotingState.VOTING), 1, context);
 
-        assertTrue(followerLogInformation.decrNextIndex());
+        assertTrue(followerLogInformation.decrNextIndex(1));
         assertEquals("getNextIndex", 0, followerLogInformation.getNextIndex());
 
-        assertTrue(followerLogInformation.decrNextIndex());
+        assertTrue(followerLogInformation.decrNextIndex(1));
         assertEquals("getNextIndex", -1, followerLogInformation.getNextIndex());
 
-        assertFalse(followerLogInformation.decrNextIndex());
+        assertFalse(followerLogInformation.decrNextIndex(1));
         assertEquals("getNextIndex", -1, followerLogInformation.getNextIndex());
     }
 }