Versions Compared

Version Old Version 4 New Version 5
Changes made by

thierry sinassamy

thierry sinassamy

Saved on

Key

  • This line was added.
  • This line was removed.
  • Formatting was changed.
Cfm round rect
cornerstrue,true,true,true
verticalsize25px
bgcolor#d0e0e3
horizontalsize25px
cornersize15px
ideldsiphawip
titleGeneration Clock with Martin Fowler
rowstrue,true,true

Generation Clock pattern is an example of a Lamport timestamp: a simple technique used to determine ordering of events across a set of processes, without depending on a system clock. Each process maintains an integer counter, which is incremented after every action the process performs. Each process also sends this integer to other processes along with the messages processes exchange. The process receiving the message sets its own integer counter by picking up the maximum between its own counter and the integer value of the message. This way, any process can figure out which action happened before the other by comparing the associated integers. The comparison is possible for actions across multiple processes as well, if the messages were exchanged between the processes. Actions which can be compared this way are said to be 'causally related'.

Problem

Possibility of the leader being temporarily disconnected from the followers. There might be a garbage collection pause in the leader process, or a temporary network disruption which disconnects the leader from the follower.

The old leader itself should also be able to detect that it was temporarily disconnected from the cluster and take necessary corrective action to step down from leadership.

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.

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

Code Block
languagejava
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.

Code Block
languagejava
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

Code Block
languagejava
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.

Code Block
languagejava
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);
  }

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.

Code Block
languagejava
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.

Code Block
languagejava
Old leader (class ReplicatedLog...)

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