Raft

Los nodos participantes en el algoritmo pueden estar en tres estados:

• Líder.- Todos los cambios que se realicen en el clúster de nodos pasan por él primero. Cómo máximo puede haber uno en cada momento. Si se cae el líder actual se abre un proceso para elegir al siguiente.
• Candidato.- Nodo que no ha encontrado líder y solicita su elección como tal. El líder será seleccionado entre los distintos candidatos. Una vez que un nuevo líder ha sido elegido se dice que comienza un término
• Seguidor.- Nodo cuya responsabilidad es actuar frente a las peticiones del nodo líder.

Supongamos que estamos en un instante en el que todos los nodos son seguidores y por tanto están esperando recibir comunicación de un nodo que actúe como líder. Cada nodo tiene un tiempo de espera aleatorio después del cual, si un líder no se comunica con él, pasa a estado candidato y pide ser elegido como líder.

Para ello el algoritmo divide el tiempo en términos que son plazos de tiempo definidos por el algoritmo. Para que un nodo sea elegido como líder es necesario que cuando pasa a estado candidato reciba la mayoría de votos de los seguidores en un término (se dice que hay quorum). Si tenemos N nodos la mayoría es al menos (N/2)+1 nodos. Solo los nodos que se encuentren en estado seguidor pueden votar una única vez a la primera solicitud que reciban dentro de un plazo. Si un equipo candidato no recibe los votos suficientes en el plazo y agota su tiempo de espera, espera al siguiente término y repite el proceso de votación. Para evitar problemas de varios nodos sincronizados en las peticiones, el tiempo de espera es aleatorio.

Una vez elegido el líder este, cada cierto tiempo, debe enviar mensaje, ya sea con información de actualización o no, a fin de que los nodos seguidores no agoten su tiempo de espera.

Supongamos que se pide un cambio en la información: El líder registra el cambio, lo pasa al resto de nodos para que lo registren y, una vez que un quorum de estos responde con que el cambio ha sido registrado, el líder hace efectivo el cambio en su sistema y finalmente notifica a los nodos seguidor indicando que el cambio ha sido efectivo.

Como las decisiones se basan en tener una mayoría de nodos de acuerdo, entonces el sistema funciona solo si la mayoría de los nodos están activos.[1]

Cuando un líder falla y luego se recupera, antes de recibir los mensajes del nuevo líder, puede enviar mensajes de actualización a los nodos. Los nodos que ya aceptaron un nuevo líder ignorarán sus mensajes. Los mensajes del viejo líder son detectados por número del término de los mensajes.[1]

El sistema puede recuperarse frente a algunas particiones de red. La partición de la red que contenga una mayoría de los nodos será la que seguirá funcionando con normalidad. El resto de nodos se sincronizará con esta cuando se reestablezcan las comunicaciones en la red.[2]

• Diseño y despliegue de servicios de alta disponibilidad en la nube usando herramientas de código abierto. Antonio Julián Alférez Zamora. Trabajo fin de grado. Escuela Técnica superior de ingenieros de telecomunicación. 2016