From 2659ea7bb9f51d216c2736a58ad86591380a9527 Mon Sep 17 00:00:00 2001 From: Robert Varga Date: Tue, 23 Jan 2018 17:08:03 +0100 Subject: [PATCH] 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 --- .../cluster/raft/FollowerLogInformation.java | 15 +++++++++++---- .../cluster/raft/behaviors/AbstractLeader.java | 5 ++--- .../cluster/raft/FollowerLogInformationTest.java | 6 +++--- 3 files changed, 16 insertions(+), 10 deletions(-) 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 fe836362c8..ca3de5944b 100644 --- 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 2175eb7555..fbdfd49a3f 100644 --- 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 d22e9e5eb0..8e80e30d8b 100644 --- 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()); } } -- 2.36.6