Force install snapshot when follower log is ahead

Force install snapshot when follower log is ahead

It's possible for a follower's log to actually be ahead of the leader's log.
Normally this doesn't happen in raft as a node cannot become leader if its
log is behind another's. However, the non-voting semantics deviate a bit
from raft. Only voting members participate in elections and can become
leader so it's possible for a non-voting follower to be ahead of the leader.
This can happen if persistence is disabled and all voting members are
restarted. In this case, the voting leader will start out with an empty log
however the non-voting followers still retain the previous data in memory.
On the first AppendEntries, the non-voting follower returns a successful
reply b/c the prevLogIndex sent by the leader is -1 and thus the integrity
checks pass. However the follower's returned lastLogIndex may be higher in
which case we want to reset the follower by installing a snapshot.
Therefore I added a check in AbstractLeader#handeAppendEntriesReply if
the reply lastLogIndex > leader's last index.

Since the initial AppendEntries is sent immediately by the leader,
normally the follower will reply and this change works. However if a
follower happens to be disconnected and doesn't reply for some time, the
leader can still progress with new commits. If the leader has enough
commits such that its lastIndex matches or exceeds the lagging
non-voting follower, this check doesn't work. In this case, the
follower's integrity checks will fail since the leader's prevLogTerm
will differ. On reply the leader will start decrementing the follower's
nextIndex in an attempt to find where the logs match. During this
process the leader may trim its log via replicatedToAllIndex in which
case the follower's nextIndex may no longer be in the leader's log and
the leader will install a snapshot.

However if other nodes are down and prevent the log trimming then the
follower's nextIndex may be in the log until it eventually decrements to
0. The follower's integrity checks will pass in this case since the
leader's prevLogIndex will be -1. The follower will then attempt to add
the leader's log entries to its log. It first loops the log entries in
the AppendEntries with the intent of skipping matching entries in its
log (ie index and term the same) and stopping when it finds an entry
that doesn;t exist or finds one whose term doesn't match, in which case
it removes the entries beginning at this index. However I found some
issue in this code. First it was calling get on the getReplicatedLog
which doesn't take into account that the index may be part of the prior
snaphot and not actually in the log. I changed this check to
isLogEntryPresent which takes into account the snapshot. Second, if it
hits a conflicting entry it tries to remove it from the log. However,
as before, it may be in the snapshot and not in the log in which case
nothing gets removed. To alleviate this, I modified removeFromAndPersist
to return a boolean - false meaning it didn't find the index. In this
case I changed it to send back a reply to force a snapshot.

I added several tests in a new class NonVotingFollowerIntegrationTest
that runs thru various scenarios to cover the cases described above.

While testing I ran into some orthoganl issues that I also fixed.

- if a leader has only non-voting followers, on replicate, it should
  immediately commit and apply to state as it does when there's no
  followers since it doesn't need consensus from non-voting followers.
  So I added a method anyVotingPeers to RaftActorContext to handle this
  case.

- When calculating the prevLogIndex and prevLogTerm for the
  AppendEntries message, it calls get on the getReplicatedLog
  which doesn't take into account that the index may be the snaphot
  index/term. Follower does this check prevLogIndex/prevLogTerm so
  the leader should as well.

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