(Présentation de l'algorithme de RAFT pour l'UE PPD)

L'algorithme de RAFT est algorithme de consensus se proposant comme une alternative à l'algorithme de Paxos. Il se veut simple à comprendre et réduit aussi le nombre de communications que Paxos peut provoquer.

Quelques termes

• Term : Unité de temps avec une durée aléatoire comprise entre 150ms et 300ms.
• Battement de coeur : Message envoyé par le leader aux autres noeuds dans un intervalle de temps régulier.
• Client : rôle souhaitant ajouter une valeur dans le cluster.

Les différents états des noeuds

Dans l'algorithme un noeud doit avoir un des rôles suivants :

• Suiveur : est un noeud qui va attendre les informations du leader.
• Candidat : est un noeud qui quand il n'a reçu aucun battement de coeur du leader et que son term est expiré souhaite devenir leader.
• Leader : est un noeud qui va transmettre des informations via ces battements de coeur au système.

Règles de RAFT

• On peut avoir au plus un leader par term.
• Le leader peut seul faire des ajouts, il ne peut pas faire de suppression.
• Si un ajout est accepté, cet ajout sera alors présent dans les logs du leader à partir de son term.
• Si un cluster à ajouter une commande dans une entrée de ses logs alors aucun autre cluster ne peut avoir une autre commande à la même entrée de ses logs.

Élection du leader

L'algorithme de RAFT se base sur l'utilisation d'un leader. Pour créer un leader il y un processus d'élection. Pour déclencher une élection il y a 2 situations. La première situation est lors du démarrage aucun leader existe. La seconde situation ce déclenche quand les battements de coeur du leader ne sont plus reçus par un suiveur.

Déroulement d'une élection

Quand un suiveur atteint la fin de son term sans recevoir de message du leader alors il devient candidat. Une fois devenu candidat le noeuds envoie un message à tous les autres noeuds pour qu'ils votent. Si le candidat reçoit la majorité de votes alors il devient le leader et commence créer des battements de coeur.

Si plusieurs candidats se présente en même temps et qu'aucun n'obtient de majorité alors au prochain term une nouvelle élection est lancé et ainsi de suite jusqu'à ce qu'un leader soit élu.

Réplication des données

Quand un client souhaite faire un ajout sur le cluster, il envoie ce qu'il souhaite rajouter au leader. Le leader envoie durant un de ces battements de coeur la valeur du client. Lorsqu'un suiveur reçoit cette demande d'ajout il envoie au leader un message qu'il a bien pris en compte cette demande. Une fois que le leader a reçu une majorité de réponse des suiveurs il écrit alors la valeur dans les logs et prévient les suiveurs qu'ils peuvent en faire autant.

Fusion de 2 réseaux

Avec RAFT si à la suite d'une panne le réseau se retrouve séparer, les plusieurs sous-réseaux fonctionne toujours indépendamment et ont chacun leur leader. Au moment où les deux sous réseaux refusionnent pour n'en former qu'un se pose la question de qui devient le leader. Pour choisir le leader dans cette situation il n'y pas d'élection. Parmi les leaders existant RAFT garder le leader ayant le term le plus élevé. Suite à ça le leader restant envoie dans ses battements de coeur les informations pour mettre à jour les informations dans tous les noeuds du cluster.

source

• http://thesecretlivesofdata.com/raft/
• https://medium.com/free-code-camp/in-search-of-an-understandable-consensus-algorithm-a-summary-4bc294c97e0d
• https://en.wikipedia.org/wiki/Raft_(algorithm)