Cajitas que piensan

Generation Clock

Basado en los apuntes de Unmesh Joshi

Cuando tenemos una configuración de Lider y Seguidores, existe la posibilidad de que el lider quede desconectado del resto temporalmente. Esto puede suceder por problemas de red entre los nodos, entre datacenters pero también por problemas en el host del lider, ejemplo un garbage collection muy largo.

En estos casos, al estar el proceso todavía corriendo, cuando vuelve a tener conexión con el resto del cluster, va a intentar a seguir replicando sus datos a los seguidores. Esto podría generar inconsistencias, puesto que ante su “ausencia”, los seguidores podrian haber elegido a un nuevo lider y recibido operaciones por parte del cliente. Es importante en estos casos que los viejos seguidores detecten que las solicitudes del antiguo Lider son “antiguas” y además que el Lider ante estas negativas por parte de los seguidores pueda entenderlas como avisos de que estuvo caído durante un periodo de tiempo y debe buscar al nuevo lider.

Para detectar estas caídas y reingresos al cluster, es que se utiliza el patron de Generation Clock, el cual es un ejemplo de Lamport timestamp, una técnica para lograr determinar el orden entre eventos ocurridos en un conjunto de procesos, independientemente del reloj de cada sistema.

El proceso si lo describiéramos básicamente se compone de :

  • Cada proceso mantiene un contador, el cual va incrementando con cada acción que genera el proceso.
  • Cada proceso envía este contador a los otros procesos como adjunto en los mensajes que intercambian.
  • El proceso que recibe este mensaje actualiza su contador, con el máximo entre su contador y el que recibe.
  • Solo podemos comparar el orden de eventos que hayan ocurrido en procesos que han intercambiado mensajes. A estos eventos se dice que están “casualmente relacionados”.

Basicamente queremos mantener una variable monotoníca creciente que nos indique la generación del servidor. Cada vez que haya una elección de lider, debería incrementarse la generación. Además necesitamos que esta variable este disponible a pesar de que el servidor se haya reiniciado, así que la guardaremos en el WAL con cada operación que guardamos.

Al iniciar, el servidor lee la ultima generación que conoció desde el WAL:

class ReplicationModule {

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

}

Y cada vez que inicie una elección de Lider, aumenta el contador en 1

class ReplicationModule {

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

Cuando el nodo solicite a los otros nodos su voto para ser Lider, les envía su numero de generación. De esta manera, luego de una elección exitosa, todos los nodos tienen la misma generación, puesto que apenas se elija un lider, este enviara a los seguidores la generación.

// en un nodo que no gano la elección
class ReplicationModule {
  private void becomeFollower(Long generation) {
      replicationState.setGeneration(generation);
      transitionTo(ServerRole.FOLLOWING);
  }
}

A partir de aqui, el lider incluye su numero de generación en cada mensaje a sus seguidores, tanto en los HeartBeats como en los mensajes para replicación de datos. Y por cada operación de guardado en el WAL, anexa además el numero de generación.

// el nodo que si gano la elección
class ReplicationModule {

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

Esto permite que también se guarde en el log del seguidor como parte del proceso de replicado del WAL.

Si un seguidor, recibe un mensaje por parte de un lider antiguo, tiene toda la info para poder chequear esto y rechazar las solicitudes.

class ReplicationModule {

	private ReplicationResponse processReplicationRequest(ReplicationRequest replicationRequest){
 		Long currentGeneration = replicationState.getGeneration();
  		if (currentGeneration > replicationRequest.getGeneration()) {
      		return new ReplicationResponse(FAILED, serverId(), currentGeneration, wal.getLastLogEntryId());
  		}
	}
}

Al recibir esta respuesta fallida, el antiguo lider se convierte en follower y espera mensajes del nuevo lider.

class ReplicationModule {

	private void processVoteResponse(VoteResponse response){
		if (!response.isSucceeded()) {
      		if (replicationResponse.getGeneration() > replicationState.getGeneration()) {
          			becomeFollower(replicationResponse.getGeneration());
      		}
      		return;
  		} else{
			// continuo con la votacion
		}
	}
}

Veamos esto con un ejemplo de 3 nodos, donde el nodo 1 tiene un GC largo y mientras esta caído el nodo 2 pasa a ser el lider.

generation_1

Luego que el nodo 1 vuelve al cluster, intercambia mensajes con los otros 2 y se termina transformando en seguidor.

generation_1

Ejemplos

  • Un poco de detalle del global logical clock de MongoDB
  • Cassandra no tiene un lider, por lo que la numeración de los eventos ocurre por marcas de tiempo generadas por cada cliente (por defecto) o por el nodo que recibe la operación a realizar.
    • Si usamos la marca generada por el nodo que recibe la operacion podemos tener descoordinaciones, con nodos que tengan relojes mas atrasados que otros.
    • Si la marca la genera el cliente, mientras haya un solo cliente no habría problema, pero si hay varios clientes para un mismo partitition, es recomendable usar Lightweight Transactions
    • Usemos la estrategia que sea, Cassandra recomienda utilizar un servicio de NTP para mantener los relojes sincronizados.
  • En Zookeeper se mantiene un numero de época en cada transacción, por lo cual cada transacción persistía en Zookeeper esta etiquetada con una época.