Bug 6540: Fix journal issues on leader changes 15/45515/4
authorTom Pantelis <tpanteli@brocade.com>
Fri, 9 Sep 2016 18:08:03 +0000 (14:08 -0400)
committerTom Pantelis <tpanteli@brocade.com>
Mon, 26 Sep 2016 03:43:04 +0000 (23:43 -0400)
commit74524984b8e8625f6b8e8c791c584844d49ccf45
tree4ab030b33569116d3517bcc1e00ca610996e88fa
parent95d3c7975a423951dcbdecfbfa4cb6b7a23591cc
Bug 6540: Fix journal issues on leader changes

Fixed a couple issues with journal syncing on leader changes and isolation.

Consider the scenario where a leader is isolated and the majority partition elects
a new leader and both sides of the partition attempt to commit entries independently.
Say the term was 1 and last journal index was 2 prior to isolation and was replicated
to all followers and applied to state. After isolation, the isolated leader appends a
new entry with index 3 and attempts to replicate but fails to reach consensus.
Meanwhile, the new leader appends its own new entry with index 3 and is successfully
replicated to the remaining follower and applied to state. The commitIndex in the
majority partition is now 3. The new leader attempts to send AppendEntries to the
isolated leader but doesn't get any replies so it marks it as inactive.

When the partition is healed, the isolated leader converts to follower when it hears
from the new leader with the higher term. Since the new leader has marked the isolated
leader as inactive, the initial AppendEntries that the previous leader sees will have
no entries and the leaderCommitIndex will be 3. This is greater than the current
commitIndex 2 so the previous leader will update its commitIndex to 3 and apply its
entry with index 3 to the state. However this entry was from the previous term 1 which
was not replicated to a majority of the nodes and conflicts with the new leader's entry
with index 3 and term 2. This is a violation of raft.

This violation occurs as a result of the new leader not sending any entries until it
knows the follower is active. This is for efficiency to avoid continuously trying to
send entries when a follower is down. This is fine however the leader should not send
its current commit index either since it doesn't know the state of the follower. The
intention of the empty AppendEntries in this case is to re-establish connectivity with
the follower and thus should not cause any state change in the follower. Therefore I
changed the code to send leaderCommitIndex as -1 if the follower is inactive.

The other case where the leader purposely sends an empty AppendEntries is when the
leader is in the process of installing a snapshot on a follower, as indicated by the
presence of a LeaderInstallSnapshotState instance in the FollowerLogInformation. The
empty AppendEntries is still sent at the heartbeat interval to prevent an election
timeout in case the snapshot capture/transfer is delayed. Again, the AppendEntries
should not cause any state change in the follower so I also changed the leader to send
-1 for the leaderCommitIndex. As a result, I also changed it so that the leader
immeditely records a LeaderInstallSnapshotState instance in the FollowerLogInformation
when it initiates the async snapshot capture. Previously this was done when the capture
completed and the RaftActor sent the SendInstallSnapshot message to the leader
behavior. However it may take some time to capture the snapshot and intervening AppendEntries heart beats may be sent to the follower.

The other issue in the above scenario is that the conflict with entry 3 is not
immediately detected. On the first AppendEntries, the previous leader reports back
a successful reply with lastLogIndex 3 and lastLogTerm 1 b/c the previous
index (2) and term (1) didn't conflict. The new leader sets the previous leader's
match index to 3 and thinks index 3 has been replicated to all the followers and
trims its in-memory log at index 2. Eventually when the next entry with index 4 is
replicated, the previous leader will detect the conflict as the leader's previous
log index 3 and term 2 will be sent in the next AppendEntries. The new leader will
backtrack and eventually install a snapshot to sync the previous leader however
it's inefficient and should be unnecessary. The leader should detect the conflict
immediately on the first AppendEntries reply. So I changed handleAppendEntriesReply
to check that the follower's lastLogTerm matches the leader's term for that index.
If not, the leader sets the follower's next index to lastLogTerm - 1. This prevents
the leader from trimming its log and the next AppendEntries will include the
conflicting entry which the follower will remove/replace.

Change-Id: I7a0282cc4078f33ffd049e4a0eb4feff6230510d
Signed-off-by: Tom Pantelis <tpanteli@brocade.com>
12 files changed:
opendaylight/md-sal/sal-akka-raft/src/main/java/org/opendaylight/controller/cluster/raft/FollowerLogInformationImpl.java
opendaylight/md-sal/sal-akka-raft/src/main/java/org/opendaylight/controller/cluster/raft/base/messages/ApplyState.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/main/java/org/opendaylight/controller/cluster/raft/behaviors/Follower.java
opendaylight/md-sal/sal-akka-raft/src/main/java/org/opendaylight/controller/cluster/raft/behaviors/LeaderInstallSnapshotState.java
opendaylight/md-sal/sal-akka-raft/src/test/java/org/opendaylight/controller/cluster/raft/AbstractRaftActorIntegrationTest.java
opendaylight/md-sal/sal-akka-raft/src/test/java/org/opendaylight/controller/cluster/raft/IsolationScenarioTest.java [new file with mode: 0644]
opendaylight/md-sal/sal-akka-raft/src/test/java/org/opendaylight/controller/cluster/raft/LeadershipTransferIntegrationTest.java
opendaylight/md-sal/sal-akka-raft/src/test/java/org/opendaylight/controller/cluster/raft/MockRaftActorContext.java
opendaylight/md-sal/sal-akka-raft/src/test/java/org/opendaylight/controller/cluster/raft/ReplicationAndSnapshotsWithLaggingFollowerIntegrationTest.java
opendaylight/md-sal/sal-akka-raft/src/test/java/org/opendaylight/controller/cluster/raft/behaviors/CandidateTest.java
opendaylight/md-sal/sal-akka-raft/src/test/java/org/opendaylight/controller/cluster/raft/behaviors/LeaderTest.java

©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.