Improve follower term conflict resolution 34/79334/1
authorRobert Varga <robert.varga@pantheon.tech>
Tue, 23 Jan 2018 16:08:03 +0000 (17:08 +0100)
committerRobert Varga <robert.varga@pantheon.tech>
Wed, 9 Jan 2019 09:15:59 +0000 (10:15 +0100)
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>
opendaylight/md-sal/sal-akka-raft/src/main/java/org/opendaylight/controller/cluster/raft/FollowerLogInformation.java
opendaylight/md-sal/sal-akka-raft/src/main/java/org/opendaylight/controller/cluster/raft/behaviors/AbstractLeader.java
opendaylight/md-sal/sal-akka-raft/src/test/java/org/opendaylight/controller/cluster/raft/FollowerLogInformationTest.java

index fe83636..ca3de59 100644 (file)
@@ -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 &gt;= 0, false otherwise.
+     * @param followerLastIndex follower's last reported index.
+     * @return true if the next index was decremented, i.e. it was previously &gt;= 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;
     }
 
index 2175eb7..fbdfd49 100644 (file)
@@ -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 {}",
index d22e9e5..8e80e30 100644 (file)
@@ -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());
     }
 }

©2013 OpenDaylight, A Linux Foundation Collaborative Project. All Rights Reserved.
OpenDaylight is a registered trademark of The OpenDaylight Project, Inc.
Linux Foundation and OpenDaylight are registered trademarks of the Linux Foundation.
Linux is a registered trademark of Linus Torvalds.