Generation Clock

Solution

Maintain a monotonically increasing number indicating the generation of the server. Every time a new leader election happens, it should be marked by increasing the generation. The generation needs to be available beyond a server reboot, so it is stored with every entry in the Write-Ahead Log. As discussed in High-Water Mark, followers use this information to find conflicting entries in their log.

At startup, the server reads the last known generation from the log.

class ReplicatedLog…

  this.replicationState = new ReplicationState(config, wal.getLastLogEntryGeneration());

With Leader and Followers servers increment the generation every time there's a new leader election.

class ReplicatedLog…

  private void startLeaderElection() {
      replicationState.setGeneration(replicationState.getGeneration() + 1);
      registerSelfVote();
      requestVoteFrom(followers);
  }

The servers send the generation to other servers as part of the vote requests. This way, after a successful leader election, all the servers have the same generation. Once the leader is elected, followers are told about the new generation

follower (class ReplicatedLog...)

  private void becomeFollower(int leaderId, Long generation) {
      replicationState.reset();
      replicationState.setGeneration(generation);
      replicationState.setLeaderId(leaderId);
      transitionTo(ServerRole.FOLLOWING);
  }

Thereafter, the leader includes the generation in each request it sends to the followers. It includes it in every HeartBeat message as well as the replication requests sent to followers.

Leader persists the generation along with every entry in its Write-Ahead Log

leader (class ReplicatedLog...)

  Long appendToLocalLog(byte[] data) {
      Long generation = replicationState.getGeneration();
      return appendToLocalLog(data, generation);
  }

  Long appendToLocalLog(byte[] data, Long generation) {
      var logEntryId = wal.getLastLogIndex() + 1;
      var logEntry = new WALEntry(logEntryId, data, EntryType.DATA, generation);
      return wal.writeEntry(logEntry);
  }

This way, it is also persisted in the follower log as part of the replication mechanism of Leader and Followers

If a follower gets a message from a deposed leader, the follower can tell because its generation is too low. The follower then replies with a failure response.

follower (class ReplicatedLog...)

  Long currentGeneration = replicationState.getGeneration();
  if (currentGeneration > request.getGeneration()) {
      return new ReplicationResponse(FAILED, serverId(), currentGeneration, wal.getLastLogIndex());
  }

When a leader gets such a failure response, it becomes a follower and expects communication from the new leader.

Old leader (class ReplicatedLog...)

  if (!response.isSucceeded()) {
      if (response.getGeneration() > replicationState.getGeneration()) {
          becomeFollower(LEADER_NOT_KNOWN, response.getGeneration());
          return;
      }

Consider the following example. In the three server cluster, leader1 is the existing leader. All the servers in the cluster have the generation as 1. Leader1 sends continuous heartbeats to the followers. Leader1 has a long garbage collection pause, for say 5 seconds. The followers did not get a heartbeat, and timeout to elect a new leader. The new leader increments the generation to 2. After the garbage collection pause is over, leader1 continues sending the requests to other servers. The followers and the new leader which are at generation 2, reject the request and send a failure response with generation 2. leader1 handles the failure response and steps down to be a follower, with generation updated to 2.

Figure 1: Generation