opendaylight/md-sal/sal-akka-raft/src/test/java/org/opendaylight/controller/cluster/raft/behaviors/LeaderElectionScenariosTest.java

   1 /*
   2  * Copyright (c) 2015 Brocade Communications Systems, Inc. and others.  All rights reserved.
   3  *
   4  * This program and the accompanying materials are made available under the
   5  * terms of the Eclipse Public License v1.0 which accompanies this distribution,
   6  * and is available at http://www.eclipse.org/legal/epl-v10.html
   7  */
   8 package org.opendaylight.controller.cluster.raft.behaviors;
   9
  10 import static org.junit.Assert.assertEquals;
  11 import static org.junit.Assert.assertNotNull;
  12 import static org.junit.Assert.assertTrue;
  13 import akka.actor.ActorRef;
  14 import akka.actor.ActorSystem;
  15 import akka.actor.Props;
  16 import akka.dispatch.Dispatchers;
  17 import akka.testkit.JavaTestKit;
  18 import akka.testkit.TestActorRef;
  19 import com.google.common.collect.ImmutableMap;
  20 import com.google.common.util.concurrent.Uninterruptibles;
  21 import java.util.Map;
  22 import java.util.concurrent.ConcurrentHashMap;
  23 import java.util.concurrent.CountDownLatch;
  24 import java.util.concurrent.TimeUnit;
  25 import org.junit.After;
  26 import org.junit.Test;
  27 import org.opendaylight.controller.cluster.raft.DefaultConfigParamsImpl;
  28 import org.opendaylight.controller.cluster.raft.MockRaftActorContext;
  29 import org.opendaylight.controller.cluster.raft.MockRaftActorContext.MockPayload;
  30 import org.opendaylight.controller.cluster.raft.MockRaftActorContext.MockReplicatedLogEntry;
  31 import org.opendaylight.controller.cluster.raft.MockRaftActorContext.SimpleReplicatedLog;
  32 import org.opendaylight.controller.cluster.raft.RaftActorContext;
  33 import org.opendaylight.controller.cluster.raft.RaftState;
  34 import org.opendaylight.controller.cluster.raft.base.messages.ElectionTimeout;
  35 import org.opendaylight.controller.cluster.raft.base.messages.SendHeartBeat;
  36 import org.opendaylight.controller.cluster.raft.messages.AppendEntries;
  37 import org.opendaylight.controller.cluster.raft.messages.AppendEntriesReply;
  38 import org.opendaylight.controller.cluster.raft.messages.RequestVote;
  39 import org.opendaylight.controller.cluster.raft.messages.RequestVoteReply;
  40 import org.opendaylight.controller.cluster.raft.utils.MessageCollectorActor;
  41 import org.slf4j.Logger;
  42 import org.slf4j.LoggerFactory;
  43 import org.slf4j.impl.SimpleLogger;
  44 import scala.concurrent.duration.FiniteDuration;
  45
  46 /**
  47  * Tests various leader election scenarios.
  48  *
  49  * @author Thomas Pantelis
  50  */
  51 public class LeaderElectionScenariosTest {
  52
  53     private static final int HEARTBEAT_INTERVAL = 50;
  54
  55     public static class MemberActor extends MessageCollectorActor {
  56
  57         volatile RaftActorBehavior behavior;
  58         Map<Class<?>, CountDownLatch> messagesReceivedLatches = new ConcurrentHashMap<>();
  59         Map<Class<?>, Boolean> dropMessagesToBehavior = new ConcurrentHashMap<>();
  60         CountDownLatch behaviorStateChangeLatch;
  61
  62         public static Props props() {
  63             return Props.create(MemberActor.class).withDispatcher(Dispatchers.DefaultDispatcherId());
  64         }
  65
  66         @Override
  67         public void onReceive(Object message) throws Exception {
  68             // Ignore scheduled SendHeartBeat messages.
  69             if(message instanceof SendHeartBeat) {
  70                 return;
  71             }
  72
  73             try {
  74                 if(behavior != null && !dropMessagesToBehavior.containsKey(message.getClass())) {
  75                     RaftActorBehavior oldBehavior = behavior;
  76                     behavior = behavior.handleMessage(getSender(), message);
  77                     if(behavior != oldBehavior && behaviorStateChangeLatch != null) {
  78                         behaviorStateChangeLatch.countDown();
  79                     }
  80                 }
  81             } finally {
  82                 super.onReceive(message);
  83
  84                 CountDownLatch latch = messagesReceivedLatches.get(message.getClass());
  85                 if(latch != null) {
  86                     latch.countDown();
  87                 }
  88             }
  89         }
  90
  91         void expectBehaviorStateChange() {
  92             behaviorStateChangeLatch = new CountDownLatch(1);
  93         }
  94
  95         void waitForBehaviorStateChange() {
  96             assertTrue("Expected behavior state change",
  97                     Uninterruptibles.awaitUninterruptibly(behaviorStateChangeLatch, 5, TimeUnit.SECONDS));
  98         }
  99
 100         void expectMessageClass(Class<?> expClass, int expCount) {
 101             messagesReceivedLatches.put(expClass, new CountDownLatch(expCount));
 102         }
 103
 104         void waitForExpectedMessages(Class<?> expClass) {
 105             CountDownLatch latch = messagesReceivedLatches.get(expClass);
 106             assertNotNull("No messages received for " + expClass, latch);
 107             assertTrue("Missing messages of type " + expClass,
 108                     Uninterruptibles.awaitUninterruptibly(latch, 5, TimeUnit.SECONDS));
 109         }
 110
 111         void dropMessagesToBehavior(Class<?> msgClass) {
 112             dropMessagesToBehavior(msgClass, 1);
 113         }
 114
 115         void dropMessagesToBehavior(Class<?> msgClass, int expCount) {
 116             expectMessageClass(msgClass, expCount);
 117             dropMessagesToBehavior.put(msgClass, Boolean.TRUE);
 118         }
 119
 120         void clearDropMessagesToBehavior() {
 121             dropMessagesToBehavior.clear();
 122         }
 123
 124         @Override
 125         public void clear() {
 126             behaviorStateChangeLatch = null;
 127             clearDropMessagesToBehavior();
 128             messagesReceivedLatches.clear();
 129             super.clear();
 130         }
 131
 132         void forwardCapturedMessageToBehavior(Class<?> msgClass, ActorRef sender) throws Exception {
 133             Object message = getFirstMatching(getSelf(), msgClass);
 134             assertNotNull("Message of type " + msgClass + " not received", message);
 135             getSelf().tell(message, sender);
 136         }
 137
 138         void forwardCapturedMessagesToBehavior(Class<?> msgClass, ActorRef sender) throws Exception {
 139             for(Object m: getAllMatching(getSelf(), msgClass)) {
 140                 getSelf().tell(m, sender);
 141             }
 142         }
 143
 144         <T> T getCapturedMessage(Class<T> msgClass) throws Exception {
 145             Object message = getFirstMatching(getSelf(), msgClass);
 146             assertNotNull("Message of type " + msgClass + " not received", message);
 147             return (T) message;
 148         }
 149     }
 150
 151     static {
 152         System.setProperty(SimpleLogger.LOG_KEY_PREFIX + MockRaftActorContext.class.getName(), "trace");
 153     }
 154
 155     private final Logger testLog = LoggerFactory.getLogger(MockRaftActorContext.class);
 156     private final ActorSystem system = ActorSystem.create("test");
 157
 158     @After
 159     public void tearDown() {
 160         JavaTestKit.shutdownActorSystem(system);
 161     }
 162
 163     private DefaultConfigParamsImpl newConfigParams() {
 164         DefaultConfigParamsImpl configParams = new DefaultConfigParamsImpl();
 165         configParams.setHeartBeatInterval(new FiniteDuration(HEARTBEAT_INTERVAL, TimeUnit.MILLISECONDS));
 166         configParams.setElectionTimeoutFactor(100000);
 167         configParams.setIsolatedLeaderCheckInterval(new FiniteDuration(1, TimeUnit.DAYS));
 168         return configParams;
 169     }
 170
 171     private MockRaftActorContext newRaftActorContext(String id, ActorRef actor,
 172             Map<String, String> peerAddresses) {
 173         MockRaftActorContext context = new MockRaftActorContext(id, system, actor);
 174         context.setPeerAddresses(peerAddresses);
 175         context.getTermInformation().updateAndPersist(1, "");
 176         return context;
 177     }
 178
 179     private void verifyBehaviorState(String name, TestActorRef<MemberActor> actor, RaftState expState) {
 180         assertEquals(name + " behavior state", expState, actor.underlyingActor().behavior.state());
 181     }
 182
 183     private void initializeLeaderBehavior(TestActorRef<MemberActor> actor, RaftActorContext context,
 184             int numActiveFollowers) throws Exception {
 185         // Leader sends immediate heartbeats - we don't care about it so ignore it.
 186
 187         actor.underlyingActor().expectMessageClass(AppendEntriesReply.class, numActiveFollowers);
 188         Leader leader = new Leader(context);
 189         actor.underlyingActor().waitForExpectedMessages(AppendEntriesReply.class);
 190         actor.underlyingActor().behavior = leader;
 191
 192         actor.underlyingActor().forwardCapturedMessagesToBehavior(AppendEntriesReply.class, ActorRef.noSender());
 193         actor.underlyingActor().clear();
 194     }
 195
 196     private TestActorRef<MemberActor> newMemberActor(String name) throws Exception {
 197         TestActorRef<MemberActor> actor = TestActorRef.create(system, MemberActor.props(), name);
 198         MessageCollectorActor.waitUntilReady(actor);
 199         return actor;
 200     }
 201
 202     private void sendHeartbeat(TestActorRef<MemberActor> leaderActor) {
 203         Uninterruptibles.sleepUninterruptibly(HEARTBEAT_INTERVAL, TimeUnit.MILLISECONDS);
 204         leaderActor.underlyingActor().behavior.handleMessage(leaderActor, new SendHeartBeat());
 205     }
 206
 207     @Test
 208     public void testDelayedMessagesScenario() throws Exception {
 209         testLog.info("Starting testDelayedMessagesScenario");
 210
 211         TestActorRef<MemberActor> member1Actor = newMemberActor("member1");
 212         TestActorRef<MemberActor> member2Actor = newMemberActor("member2");
 213         TestActorRef<MemberActor> member3Actor = newMemberActor("member3");
 214
 215         // Create member 2's behavior initially as Follower
 216
 217         MockRaftActorContext member2Context = newRaftActorContext("member2", member2Actor,
 218                 ImmutableMap.<String,String>builder().
 219                     put("member1", member1Actor.path().toString()).
 220                     put("member3", member3Actor.path().toString()).build());
 221
 222         DefaultConfigParamsImpl member2ConfigParams = newConfigParams();
 223         member2Context.setConfigParams(member2ConfigParams);
 224
 225         Follower member2Behavior = new Follower(member2Context);
 226         member2Actor.underlyingActor().behavior = member2Behavior;
 227
 228         // Create member 3's behavior initially as Follower
 229
 230         MockRaftActorContext member3Context = newRaftActorContext("member3", member3Actor,
 231                 ImmutableMap.<String,String>builder().
 232                     put("member1", member1Actor.path().toString()).
 233                     put("member2", member2Actor.path().toString()).build());
 234
 235         DefaultConfigParamsImpl member3ConfigParams = newConfigParams();
 236         member3Context.setConfigParams(member3ConfigParams);
 237
 238         Follower member3Behavior = new Follower(member3Context);
 239         member3Actor.underlyingActor().behavior = member3Behavior;
 240
 241         // Create member 1's behavior initially as Leader
 242
 243         MockRaftActorContext member1Context = newRaftActorContext("member1", member1Actor,
 244                 ImmutableMap.<String,String>builder().
 245                     put("member2", member2Actor.path().toString()).
 246                     put("member3", member3Actor.path().toString()).build());
 247
 248         DefaultConfigParamsImpl member1ConfigParams = newConfigParams();
 249         member1Context.setConfigParams(member1ConfigParams);
 250
 251         initializeLeaderBehavior(member1Actor, member1Context, 2);
 252
 253         member2Actor.underlyingActor().clear();
 254         member3Actor.underlyingActor().clear();
 255
 256         // Send ElectionTimeout to member 2 to simulate missing heartbeat from the Leader. member 2
 257         // should switch to Candidate and send out RequestVote messages. Set member 1 and 3 actors
 258         // to capture RequestVote but not to forward to the behavior just yet as we want to
 259         // control the order of RequestVote messages to member 1 and 3.
 260
 261         member1Actor.underlyingActor().dropMessagesToBehavior(RequestVote.class);
 262
 263         member2Actor.underlyingActor().expectBehaviorStateChange();
 264
 265         member3Actor.underlyingActor().dropMessagesToBehavior(RequestVote.class);
 266
 267         member2Actor.tell(new ElectionTimeout(), ActorRef.noSender());
 268
 269         member1Actor.underlyingActor().waitForExpectedMessages(RequestVote.class);
 270         member3Actor.underlyingActor().waitForExpectedMessages(RequestVote.class);
 271
 272         member2Actor.underlyingActor().waitForBehaviorStateChange();
 273         verifyBehaviorState("member 2", member2Actor, RaftState.Candidate);
 274
 275         assertEquals("member 1 election term", 1, member1Context.getTermInformation().getCurrentTerm());
 276         assertEquals("member 2 election term", 2, member2Context.getTermInformation().getCurrentTerm());
 277         assertEquals("member 3 election term", 1, member3Context.getTermInformation().getCurrentTerm());
 278
 279         // At this point member 1 and 3 actors have captured the RequestVote messages. First
 280         // forward the RequestVote message to member 1's behavior. Since the RequestVote term
 281         // is greater than member 1's term, member 1 should switch to Follower without replying
 282         // to RequestVote and update its term to 2.
 283
 284         member1Actor.underlyingActor().clearDropMessagesToBehavior();
 285         member1Actor.underlyingActor().expectBehaviorStateChange();
 286         member1Actor.underlyingActor().forwardCapturedMessageToBehavior(RequestVote.class, member2Actor);
 287         member1Actor.underlyingActor().waitForExpectedMessages(RequestVote.class);
 288
 289         member1Actor.underlyingActor().waitForBehaviorStateChange();
 290         verifyBehaviorState("member 1", member1Actor, RaftState.Follower);
 291
 292         // Now forward member 3's captured RequestVote message to its behavior. Since member 3 is
 293         // already a Follower, it should update its term to 2 and send a RequestVoteReply back to
 294         // member 2 granting the vote b/c the RequestVote's term, lastLogTerm, and lastLogIndex
 295         // should satisfy the criteria for granting the vote. However, we'll delay sending the
 296         // RequestVoteReply to member 2's behavior to simulate network latency.
 297
 298         member2Actor.underlyingActor().dropMessagesToBehavior(RequestVoteReply.class);
 299
 300         member3Actor.underlyingActor().clearDropMessagesToBehavior();
 301         member3Actor.underlyingActor().expectMessageClass(RequestVote.class, 1);
 302         member3Actor.underlyingActor().forwardCapturedMessageToBehavior(RequestVote.class, member2Actor);
 303         member3Actor.underlyingActor().waitForExpectedMessages(RequestVote.class);
 304         verifyBehaviorState("member 3", member3Actor, RaftState.Follower);
 305
 306         assertEquals("member 1 election term", 2, member1Context.getTermInformation().getCurrentTerm());
 307         assertEquals("member 2 election term", 2, member2Context.getTermInformation().getCurrentTerm());
 308         assertEquals("member 3 election term", 2, member3Context.getTermInformation().getCurrentTerm());
 309
 310         // Send ElectionTimeout to member 3 to simulate missing heartbeat from a Leader. member 3
 311         // should switch to Candidate and send out RequestVote messages. member 1 should grant the
 312         // vote and send a reply. After receiving the RequestVoteReply, member 3 should switch to leader.
 313
 314         member2Actor.underlyingActor().expectBehaviorStateChange();
 315         member3Actor.underlyingActor().clear();
 316         member3Actor.underlyingActor().expectMessageClass(RequestVoteReply.class, 1);
 317         member3Actor.underlyingActor().expectMessageClass(AppendEntriesReply.class, 2);
 318
 319         member3Actor.tell(new ElectionTimeout(), ActorRef.noSender());
 320
 321         member3Actor.underlyingActor().waitForExpectedMessages(RequestVoteReply.class);
 322
 323         RequestVoteReply requestVoteReply = member3Actor.underlyingActor().getCapturedMessage(RequestVoteReply.class);
 324         assertEquals("getTerm", member3Context.getTermInformation().getCurrentTerm(), requestVoteReply.getTerm());
 325         assertEquals("isVoteGranted", true, requestVoteReply.isVoteGranted());
 326
 327         verifyBehaviorState("member 3", member3Actor, RaftState.Leader);
 328
 329         // member 2 should've switched to Follower as member 3's RequestVote term (3) was greater
 330         // than member 2's term (2).
 331
 332         member2Actor.underlyingActor().waitForBehaviorStateChange();
 333         verifyBehaviorState("member 2", member2Actor, RaftState.Follower);
 334
 335         // The switch to leader should cause an immediate AppendEntries heartbeat from member 3.
 336
 337         member3Actor.underlyingActor().waitForExpectedMessages(AppendEntriesReply.class);
 338
 339         assertEquals("member 1 election term", 3, member1Context.getTermInformation().getCurrentTerm());
 340         assertEquals("member 2 election term", 3, member2Context.getTermInformation().getCurrentTerm());
 341         assertEquals("member 3 election term", 3, member3Context.getTermInformation().getCurrentTerm());
 342
 343         // Now forward the original delayed RequestVoteReply from member 3 to member 2 that granted
 344         // the vote. Since member 2 is now a Follower, the RequestVoteReply should be ignored.
 345
 346         member2Actor.underlyingActor().clearDropMessagesToBehavior();
 347         member2Actor.underlyingActor().forwardCapturedMessageToBehavior(RequestVoteReply.class, member3Actor);
 348
 349         member2Actor.underlyingActor().waitForExpectedMessages(RequestVoteReply.class);
 350
 351         verifyBehaviorState("member 1", member1Actor, RaftState.Follower);
 352         verifyBehaviorState("member 2", member2Actor, RaftState.Follower);
 353         verifyBehaviorState("member 3", member3Actor, RaftState.Leader);
 354
 355         assertEquals("member 1 election term", 3, member1Context.getTermInformation().getCurrentTerm());
 356         assertEquals("member 2 election term", 3, member2Context.getTermInformation().getCurrentTerm());
 357         assertEquals("member 3 election term", 3, member3Context.getTermInformation().getCurrentTerm());
 358
 359         testLog.info("testDelayedMessagesScenario done");
 360     }
 361
 362     @Test
 363     public void testPartitionedLeadersScenario() throws Exception {
 364         testLog.info("Starting testPartitionedLeadersScenario");
 365
 366         TestActorRef<MemberActor> member1Actor = newMemberActor("member1");
 367         TestActorRef<MemberActor> member2Actor = newMemberActor("member2");
 368         TestActorRef<MemberActor> member3Actor = newMemberActor("member3");
 369
 370         // Create member 2's behavior initially as Follower
 371
 372         MockRaftActorContext member2Context = newRaftActorContext("member2", member2Actor,
 373                 ImmutableMap.<String,String>builder().
 374                     put("member1", member1Actor.path().toString()).
 375                     put("member3", member3Actor.path().toString()).build());
 376
 377         DefaultConfigParamsImpl member2ConfigParams = newConfigParams();
 378         member2Context.setConfigParams(member2ConfigParams);
 379
 380         Follower member2Behavior = new Follower(member2Context);
 381         member2Actor.underlyingActor().behavior = member2Behavior;
 382
 383         // Create member 3's behavior initially as Follower
 384
 385         MockRaftActorContext member3Context = newRaftActorContext("member3", member3Actor,
 386                 ImmutableMap.<String,String>builder().
 387                     put("member1", member1Actor.path().toString()).
 388                     put("member2", member2Actor.path().toString()).build());
 389
 390         DefaultConfigParamsImpl member3ConfigParams = newConfigParams();
 391         member3Context.setConfigParams(member3ConfigParams);
 392
 393         Follower member3Behavior = new Follower(member3Context);
 394         member3Actor.underlyingActor().behavior = member3Behavior;
 395
 396         // Create member 1's behavior initially as Leader
 397
 398         MockRaftActorContext member1Context = newRaftActorContext("member1", member1Actor,
 399                 ImmutableMap.<String,String>builder().
 400                     put("member2", member2Actor.path().toString()).
 401                     put("member3", member3Actor.path().toString()).build());
 402
 403         DefaultConfigParamsImpl member1ConfigParams = newConfigParams();
 404         member1Context.setConfigParams(member1ConfigParams);
 405
 406         initializeLeaderBehavior(member1Actor, member1Context, 2);
 407
 408         member2Actor.underlyingActor().clear();
 409         member3Actor.underlyingActor().clear();
 410
 411         // Send ElectionTimeout to member 2 to simulate no heartbeat from the Leader (member 1).
 412         // member 2 should switch to Candidate, start new term 2 and send out RequestVote messages.
 413         // member 1 will switch to Follower b/c its term is less than the RequestVote term, also it
 414         // won't send back a reply. member 3 will drop the message (ie won't forward it to its behavior) to
 415         // simulate loss of network connectivity between member 2 and 3.
 416
 417         member1Actor.underlyingActor().expectMessageClass(RequestVote.class, 1);
 418
 419         member2Actor.underlyingActor().expectBehaviorStateChange();
 420
 421         member3Actor.underlyingActor().dropMessagesToBehavior(RequestVote.class);
 422
 423         member2Actor.tell(new ElectionTimeout(), ActorRef.noSender());
 424
 425         member1Actor.underlyingActor().waitForExpectedMessages(RequestVote.class);
 426         member3Actor.underlyingActor().waitForExpectedMessages(RequestVote.class);
 427
 428         // member 1 should switch to Follower as the RequestVote term is greater than its term. It
 429         // won't send back a RequestVoteReply in this case.
 430
 431         verifyBehaviorState("member 1", member1Actor, RaftState.Follower);
 432
 433         // member 2 should switch to Candidate since member 1 didn't reply.
 434
 435         member2Actor.underlyingActor().waitForBehaviorStateChange();
 436         verifyBehaviorState("member 2", member2Actor, RaftState.Candidate);
 437
 438         assertEquals("member 1 election term", 2, member1Context.getTermInformation().getCurrentTerm());
 439         assertEquals("member 2 election term", 2, member2Context.getTermInformation().getCurrentTerm());
 440         assertEquals("member 3 election term", 1, member3Context.getTermInformation().getCurrentTerm());
 441
 442         // Send ElectionTimeout to member 3 to simulate no heartbeat from the Leader (member 1).
 443         // member 2 should switch to Candidate and send out RequestVote messages. member 1 will reply and
 444         // grant the vote but member 2 will drop the message to simulate loss of network connectivity.
 445
 446         member1Actor.underlyingActor().clear();
 447         member1Actor.underlyingActor().expectMessageClass(RequestVote.class, 1);
 448         member1Actor.underlyingActor().expectMessageClass(AppendEntries.class, 1);
 449
 450         member2Actor.underlyingActor().clear();
 451         member2Actor.underlyingActor().dropMessagesToBehavior(RequestVote.class);
 452         member2Actor.underlyingActor().dropMessagesToBehavior(AppendEntries.class);
 453
 454         member3Actor.underlyingActor().clear();
 455         member3Actor.underlyingActor().expectMessageClass(RequestVoteReply.class, 1);
 456         member3Actor.underlyingActor().expectMessageClass(AppendEntriesReply.class, 1);
 457
 458         member3Actor.tell(new ElectionTimeout(), ActorRef.noSender());
 459
 460         member1Actor.underlyingActor().waitForExpectedMessages(RequestVote.class);
 461         member2Actor.underlyingActor().waitForExpectedMessages(RequestVote.class);
 462         member3Actor.underlyingActor().waitForExpectedMessages(RequestVoteReply.class);
 463
 464         RequestVoteReply requestVoteReply = member3Actor.underlyingActor().getCapturedMessage(RequestVoteReply.class);
 465         assertEquals("getTerm", member3Context.getTermInformation().getCurrentTerm(), requestVoteReply.getTerm());
 466         assertEquals("isVoteGranted", true, requestVoteReply.isVoteGranted());
 467
 468         // when member 3 switches to Leader it will immediately send out heartbeat AppendEntries to
 469         // the followers. Wait for AppendEntries to member 1 and its AppendEntriesReply. The
 470         // AppendEntries message to member 2 is dropped.
 471
 472         member1Actor.underlyingActor().waitForExpectedMessages(AppendEntries.class);
 473         member2Actor.underlyingActor().waitForExpectedMessages(AppendEntries.class);
 474         member3Actor.underlyingActor().waitForExpectedMessages(AppendEntriesReply.class);
 475
 476         verifyBehaviorState("member 1", member1Actor, RaftState.Follower);
 477         verifyBehaviorState("member 2", member2Actor, RaftState.Candidate);
 478         verifyBehaviorState("member 3", member3Actor, RaftState.Leader);
 479
 480         assertEquals("member 1 election term", 2, member1Context.getTermInformation().getCurrentTerm());
 481         assertEquals("member 2 election term", 2, member2Context.getTermInformation().getCurrentTerm());
 482         assertEquals("member 3 election term", 2, member3Context.getTermInformation().getCurrentTerm());
 483
 484         // member 2 is partitioned from the Leader (member 3) and hasn't received any messages. It
 485         // would get another ElectionTimeout so simulate that. member 1 should send back a reply
 486         // granting the vote. Messages (RequestVote and AppendEntries) from member 2 to member 3
 487         // are dropped to simulate loss of network connectivity. Note member 2 will increment its
 488         // election term to 3.
 489
 490         member1Actor.underlyingActor().clear();
 491         member1Actor.underlyingActor().expectMessageClass(AppendEntries.class, 1);
 492
 493         member2Actor.underlyingActor().clear();
 494         member2Actor.underlyingActor().expectMessageClass(RequestVoteReply.class, 1);
 495         member2Actor.underlyingActor().expectMessageClass(AppendEntriesReply.class, 1);
 496
 497         member3Actor.underlyingActor().clear();
 498         member3Actor.underlyingActor().dropMessagesToBehavior(AppendEntries.class);
 499         member3Actor.underlyingActor().dropMessagesToBehavior(RequestVote.class);
 500
 501         member2Actor.tell(new ElectionTimeout(), ActorRef.noSender());
 502
 503         member2Actor.underlyingActor().waitForExpectedMessages(RequestVoteReply.class);
 504
 505         requestVoteReply = member2Actor.underlyingActor().getCapturedMessage(RequestVoteReply.class);
 506         assertEquals("getTerm", member2Context.getTermInformation().getCurrentTerm(), requestVoteReply.getTerm());
 507         assertEquals("isVoteGranted", true, requestVoteReply.isVoteGranted());
 508
 509         member3Actor.underlyingActor().waitForExpectedMessages(RequestVote.class);
 510
 511         member1Actor.underlyingActor().waitForExpectedMessages(AppendEntries.class);
 512         member3Actor.underlyingActor().waitForExpectedMessages(AppendEntries.class);
 513         member2Actor.underlyingActor().waitForExpectedMessages(AppendEntriesReply.class);
 514
 515         // We end up with 2 partitioned leaders both leading member 1. The term for member 1 and 3
 516         // is 3 and member 3's term is 2.
 517
 518         verifyBehaviorState("member 1", member1Actor, RaftState.Follower);
 519         verifyBehaviorState("member 2", member2Actor, RaftState.Leader);
 520         verifyBehaviorState("member 3", member3Actor, RaftState.Leader);
 521
 522         assertEquals("member 1 election term", 3, member1Context.getTermInformation().getCurrentTerm());
 523         assertEquals("member 2 election term", 3, member2Context.getTermInformation().getCurrentTerm());
 524         assertEquals("member 3 election term", 2, member3Context.getTermInformation().getCurrentTerm());
 525
 526         // Re-establish connectivity between member 2 and 3, ie stop dropping messages between
 527         // the 2. Send heartbeats (AppendEntries) from member 3. Both member 1 and 2 should send back
 528         // an unsuccessful AppendEntriesReply b/c their term (3) is greater than member 3's term (2).
 529         // This should cause member 3 to switch to Follower.
 530
 531         RaftActorBehavior savedMember1Behavior = member1Actor.underlyingActor().behavior;
 532         RaftActorBehavior savedMember2Behavior = member2Actor.underlyingActor().behavior;
 533         RaftActorBehavior savedMember3Behavior = member3Actor.underlyingActor().behavior;
 534         long savedMember3Term = member3Context.getTermInformation().getCurrentTerm();
 535         String savedMember3VoterFor = member3Context.getTermInformation().getVotedFor();
 536
 537         member1Actor.underlyingActor().clear();
 538         member1Actor.underlyingActor().expectMessageClass(AppendEntries.class, 1);
 539
 540         member2Actor.underlyingActor().clear();
 541         member2Actor.underlyingActor().expectMessageClass(AppendEntries.class, 1);
 542
 543         member3Actor.underlyingActor().clear();
 544         member3Actor.underlyingActor().expectMessageClass(AppendEntriesReply.class, 1);
 545
 546         sendHeartbeat(member3Actor);
 547
 548         member3Actor.underlyingActor().waitForExpectedMessages(AppendEntriesReply.class);
 549
 550         AppendEntriesReply appendEntriesReply = member3Actor.underlyingActor().
 551                 getCapturedMessage(AppendEntriesReply.class);
 552         assertEquals("isSuccess", false, appendEntriesReply.isSuccess());
 553         assertEquals("getTerm", 3, appendEntriesReply.getTerm());
 554
 555         verifyBehaviorState("member 1", member1Actor, RaftState.Follower);
 556         verifyBehaviorState("member 2", member2Actor, RaftState.Leader);
 557         verifyBehaviorState("member 3", member3Actor, RaftState.Follower);
 558
 559         assertEquals("member 1 election term", 3, member1Context.getTermInformation().getCurrentTerm());
 560         assertEquals("member 2 election term", 3, member2Context.getTermInformation().getCurrentTerm());
 561         assertEquals("member 3 election term", 3, member3Context.getTermInformation().getCurrentTerm());
 562
 563         // Revert back to the partitioned leaders state to test the other sequence where member 2
 564         // sends heartbeats first before member 3. member 1 should return a successful
 565         // AppendEntriesReply b/c his term matches member 2's. member 3 should switch to Follower
 566         // as his term is less than member 2's.
 567
 568         member1Actor.underlyingActor().behavior = savedMember1Behavior;
 569         member2Actor.underlyingActor().behavior = savedMember2Behavior;
 570         member3Actor.underlyingActor().behavior = savedMember3Behavior;
 571
 572         member3Context.getTermInformation().update(savedMember3Term, savedMember3VoterFor);
 573
 574         member1Actor.underlyingActor().clear();
 575         member1Actor.underlyingActor().expectMessageClass(AppendEntries.class, 1);
 576
 577         member2Actor.underlyingActor().clear();
 578         member2Actor.underlyingActor().expectMessageClass(AppendEntriesReply.class, 1);
 579
 580         member3Actor.underlyingActor().clear();
 581         member3Actor.underlyingActor().expectMessageClass(AppendEntries.class, 1);
 582
 583         sendHeartbeat(member2Actor);
 584
 585         member1Actor.underlyingActor().waitForExpectedMessages(AppendEntries.class);
 586         member3Actor.underlyingActor().waitForExpectedMessages(AppendEntries.class);
 587
 588         member2Actor.underlyingActor().waitForExpectedMessages(AppendEntriesReply.class);
 589
 590         verifyBehaviorState("member 1", member1Actor, RaftState.Follower);
 591         verifyBehaviorState("member 2", member2Actor, RaftState.Leader);
 592         verifyBehaviorState("member 3", member3Actor, RaftState.Follower);
 593
 594         assertEquals("member 1 election term", 3, member1Context.getTermInformation().getCurrentTerm());
 595         assertEquals("member 2 election term", 3, member2Context.getTermInformation().getCurrentTerm());
 596         assertEquals("member 3 election term", 3, member3Context.getTermInformation().getCurrentTerm());
 597
 598         testLog.info("testPartitionedLeadersScenario done");
 599     }
 600
 601     @Test
 602     public void testPartitionedCandidateOnStartupScenario() throws Exception {
 603         testLog.info("Starting testPartitionedCandidateOnStartupScenario");
 604
 605         TestActorRef<MemberActor> member1Actor = newMemberActor("member1") ;
 606         TestActorRef<MemberActor> member2Actor = newMemberActor("member2");
 607         TestActorRef<MemberActor> member3Actor = newMemberActor("member3");
 608
 609         // Create member 2's behavior as Follower.
 610
 611         MockRaftActorContext member2Context = newRaftActorContext("member2", member2Actor,
 612                 ImmutableMap.<String,String>builder().
 613                     put("member1", member1Actor.path().toString()).
 614                     put("member3", member3Actor.path().toString()).build());
 615
 616         DefaultConfigParamsImpl member2ConfigParams = newConfigParams();
 617         member2Context.setConfigParams(member2ConfigParams);
 618
 619         Follower member2Behavior = new Follower(member2Context);
 620         member2Actor.underlyingActor().behavior = member2Behavior;
 621
 622         // Create member 1's behavior as Leader.
 623
 624         MockRaftActorContext member1Context = newRaftActorContext("member1", member1Actor,
 625                 ImmutableMap.<String,String>builder().
 626                     put("member2", member2Actor.path().toString()).
 627                     put("member3", member3Actor.path().toString()).build());
 628
 629         DefaultConfigParamsImpl member1ConfigParams = newConfigParams();
 630         member1Context.setConfigParams(member1ConfigParams);
 631
 632         initializeLeaderBehavior(member1Actor, member1Context, 1);
 633
 634         member2Actor.underlyingActor().clear();
 635         member3Actor.underlyingActor().clear();
 636
 637         // Initialize the ReplicatedLog and election term info for member 1 and 2. The current term
 638         // will be 3 and the last term will be 2.
 639
 640         SimpleReplicatedLog replicatedLog = new SimpleReplicatedLog();
 641         replicatedLog.append(new MockReplicatedLogEntry(2, 1, new MockPayload("")));
 642         replicatedLog.append(new MockReplicatedLogEntry(3, 1, new MockPayload("")));
 643
 644         member1Context.setReplicatedLog(replicatedLog);
 645         member1Context.getTermInformation().update(3, "");
 646
 647         member2Context.setReplicatedLog(replicatedLog);
 648         member2Context.getTermInformation().update(3, member1Context.getId());
 649
 650         // Create member 3's behavior initially as a Candidate.
 651
 652         MockRaftActorContext member3Context = newRaftActorContext("member3", member3Actor,
 653                 ImmutableMap.<String,String>builder().
 654                     put("member1", member1Actor.path().toString()).
 655                     put("member2", member2Actor.path().toString()).build());
 656
 657         DefaultConfigParamsImpl member3ConfigParams = newConfigParams();
 658         member3Context.setConfigParams(member3ConfigParams);
 659
 660         // Initialize the ReplicatedLog and election term info for Candidate member 3. The current term
 661         // will be 2 and the last term will be 1 so it is behind the leader's log.
 662
 663         SimpleReplicatedLog candidateReplicatedLog = new SimpleReplicatedLog();
 664         candidateReplicatedLog.append(new MockReplicatedLogEntry(1, 1, new MockPayload("")));
 665         candidateReplicatedLog.append(new MockReplicatedLogEntry(2, 1, new MockPayload("")));
 666
 667         member3Context.setReplicatedLog(candidateReplicatedLog);
 668         member3Context.getTermInformation().update(2, member1Context.getId());
 669
 670         // The member 3 Candidate will start a new term and send RequestVotes. However it will be
 671         // partitioned from the cluster by having member 1 and 2 drop its RequestVote messages.
 672
 673         int numCandidateElections = 5;
 674         long candidateElectionTerm = member3Context.getTermInformation().getCurrentTerm() + numCandidateElections;
 675
 676         member1Actor.underlyingActor().dropMessagesToBehavior(RequestVote.class, numCandidateElections);
 677
 678         member2Actor.underlyingActor().dropMessagesToBehavior(RequestVote.class, numCandidateElections);
 679
 680         Candidate member3Behavior = new Candidate(member3Context);
 681         member3Actor.underlyingActor().behavior = member3Behavior;
 682
 683         // Send several additional ElectionTimeouts to Candidate member 3. Each ElectionTimeout will
 684         // start a new term so Candidate member 3's current term will be greater than the leader's
 685         // current term.
 686
 687         for(int i = 0; i < numCandidateElections - 1; i++) {
 688             member3Actor.tell(new ElectionTimeout(), ActorRef.noSender());
 689         }
 690
 691         member1Actor.underlyingActor().waitForExpectedMessages(RequestVote.class);
 692         member2Actor.underlyingActor().waitForExpectedMessages(RequestVote.class);
 693
 694         verifyBehaviorState("member 1", member1Actor, RaftState.Leader);
 695         verifyBehaviorState("member 2", member2Actor, RaftState.Follower);
 696         verifyBehaviorState("member 3", member3Actor, RaftState.Candidate);
 697
 698         assertEquals("member 1 election term", 3, member1Context.getTermInformation().getCurrentTerm());
 699         assertEquals("member 2 election term", 3, member2Context.getTermInformation().getCurrentTerm());
 700         assertEquals("member 3 election term", candidateElectionTerm,
 701                 member3Context.getTermInformation().getCurrentTerm());
 702
 703         // Now send a couple more ElectionTimeouts to Candidate member 3 with the partition resolved.
 704         //
 705         // On the first RequestVote, Leader member 1 should switch to Follower as its term (s) is less than
 706         // the RequestVote's term (8) from member 3. No RequestVoteReply should be sent by member 1.
 707         // Follower member 2 should update its term since it less than the RequestVote's term and
 708         // should return a RequestVoteReply but should not grant the vote as its last term and index
 709         // is greater than the RequestVote's lastLogTerm and lastLogIndex, ie member 2's log is later
 710         // or more up to date than member 3's.
 711         //
 712         // On the second RequestVote, both member 1 and 2 are followers so they should update their
 713         // term and return a RequestVoteReply but should not grant the vote.
 714
 715         candidateElectionTerm += 2;
 716         for(int i = 0; i < 2; i++) {
 717             member1Actor.underlyingActor().clear();
 718             member1Actor.underlyingActor().expectMessageClass(RequestVote.class, 1);
 719             member2Actor.underlyingActor().clear();
 720             member2Actor.underlyingActor().expectMessageClass(RequestVote.class, 1);
 721             member3Actor.underlyingActor().clear();
 722             member3Actor.underlyingActor().expectMessageClass(RequestVoteReply.class, 1);
 723
 724             member3Actor.tell(new ElectionTimeout(), ActorRef.noSender());
 725
 726             member1Actor.underlyingActor().waitForExpectedMessages(RequestVote.class);
 727             member2Actor.underlyingActor().waitForExpectedMessages(RequestVote.class);
 728
 729             member3Actor.underlyingActor().waitForExpectedMessages(RequestVoteReply.class);
 730
 731             RequestVoteReply requestVoteReply = member3Actor.underlyingActor().getCapturedMessage(RequestVoteReply.class);
 732             assertEquals("getTerm", member3Context.getTermInformation().getCurrentTerm(), requestVoteReply.getTerm());
 733             assertEquals("isVoteGranted", false, requestVoteReply.isVoteGranted());
 734         }
 735
 736         verifyBehaviorState("member 1", member1Actor, RaftState.Follower);
 737         verifyBehaviorState("member 2", member2Actor, RaftState.Follower);
 738         verifyBehaviorState("member 3", member3Actor, RaftState.Candidate);
 739
 740         // Even though member 3 didn't get voted for, member 1 and 2 should have updated their term
 741         // to member 3's.
 742
 743         assertEquals("member 1 election term", candidateElectionTerm,
 744                 member1Context.getTermInformation().getCurrentTerm());
 745         assertEquals("member 2 election term", candidateElectionTerm,
 746                 member2Context.getTermInformation().getCurrentTerm());
 747         assertEquals("member 3 election term", candidateElectionTerm,
 748                 member3Context.getTermInformation().getCurrentTerm());
 749
 750         // At this point we have no leader. Candidate member 3 would continue to start new elections
 751         // but wouldn't be granted a vote. One of the 2 followers would eventually time out from
 752         // not having received a heartbeat from a leader and switch to candidate and start a new
 753         // election. We'll simulate that here by sending an ElectionTimeout to member 1.
 754
 755         member1Actor.underlyingActor().clear();
 756         member1Actor.underlyingActor().expectMessageClass(RequestVoteReply.class, 1);
 757         member2Actor.underlyingActor().clear();
 758         member2Actor.underlyingActor().expectMessageClass(RequestVote.class, 1);
 759         member3Actor.underlyingActor().clear();
 760         member3Actor.underlyingActor().expectMessageClass(RequestVote.class, 1);
 761         member3Actor.underlyingActor().expectBehaviorStateChange();
 762
 763         member1Actor.tell(new ElectionTimeout(), ActorRef.noSender());
 764
 765         member2Actor.underlyingActor().waitForExpectedMessages(RequestVote.class);
 766         member3Actor.underlyingActor().waitForExpectedMessages(RequestVote.class);
 767
 768         // The RequestVoteReply should come from Follower member 2 and the vote should be granted
 769         // since member 2's last term and index matches member 1's.
 770
 771         member1Actor.underlyingActor().waitForExpectedMessages(RequestVoteReply.class);
 772
 773         RequestVoteReply requestVoteReply = member1Actor.underlyingActor().getCapturedMessage(RequestVoteReply.class);
 774         assertEquals("getTerm", member1Context.getTermInformation().getCurrentTerm(), requestVoteReply.getTerm());
 775         assertEquals("isVoteGranted", true, requestVoteReply.isVoteGranted());
 776
 777         // Candidate member 3 should change to follower as its term should be less than the
 778         // RequestVote term (member 1 started a new term higher than the other member's terms).
 779
 780         member3Actor.underlyingActor().waitForBehaviorStateChange();
 781
 782         verifyBehaviorState("member 1", member1Actor, RaftState.Leader);
 783         verifyBehaviorState("member 2", member2Actor, RaftState.Follower);
 784         verifyBehaviorState("member 3", member3Actor, RaftState.Follower);
 785
 786         // newTerm should be 10.
 787
 788         long newTerm = candidateElectionTerm + 1;
 789         assertEquals("member 1 election term", newTerm, member1Context.getTermInformation().getCurrentTerm());
 790         assertEquals("member 2 election term", newTerm, member2Context.getTermInformation().getCurrentTerm());
 791         assertEquals("member 3 election term", newTerm, member3Context.getTermInformation().getCurrentTerm());
 792
 793         testLog.info("testPartitionedCandidateOnStartupScenario done");
 794     }
 795 }