Olivier Lemer
Pas plus de ⎡N/2⎤-1 pannes simultanées.
Pannes récupérables, sans amnésie.
Pas de duplication ou réordonnancement de messages.
Pertes possibles.
Réseau partiellement synchrone.
Pensé pour répliquer une machine d'état sur chaque processus.
Un log répliqué
Chaque processus maintient un log des opérations à appliquer.
Un élu
Responsable de synchroniser ces logs répliqués.
Synchronisation des logs
Un consensus doit exister sur le contenu du log.
Élection d'un leader
Un élu mort doit être remplacé, et toute incohérence corrigée.
Deux responsabilités distinctes
Un élu responsable du log
Deux concepts distincts
Le log d'opérations
Ce qui va être (ou a été) appliqué à la machine d'état
Chaque log peut donc être
(pas encore appliqué)
(appliqué)
La machine d'état elle-même
L'état actuel, après application de tous les logs committed.
Leader
Follower
A
B
C
"Nouvelle opération"
LogThis:C
A
B
C
ACK
A
B
C
"Une majorité a loggé,
on peut commit."
Confirm:C
A
B
C
Le leader reçoit les requêtes d'opérations, et assure leur application chez tous.
Pour tout message, penser un envoi RR ; je réessaie jusqu'à confirmation de réception.
En cas de panne ici ?
On y reviendra
En tant que follower,
À la réception d'un LogThis
À la réception d'un Confirm
En tant que leader,
À la réception d'une requête
Pourquoi pas tous ?
On y reviendra
Un algorithme spécialisé
Une panne de leader doit déclencher une nouvelle élection.
Comment faire ?
Le leader envoie un heartbeat régulier à tous les followers.
Un follower déclenche une élection s'il ne reçoit rien avant un timeout.
Détection de pannes :
Comment déterminer le leader ?
Problème :
Comment déterminer le leader ?
Problème :
Deux processus peuvent être en désaccord sur l'état de leur machine.
Celui ayant le log committed le plus récent doit gagner.
Follower 1
A
B
C
Follower 2
A
B
C
Celui ayant le log pending le plus récent doit gagner.
Et en cas d'égalité sur les logs committed ?
Follower 1
A
B
C
Follower 2
A
B
C
D
Comment déterminer le leader ?
Problème :
Et en cas de désaccord sur les logs pending ?
Impossible : le leader envoie les messages dans le même ordre à tous.*
Impossible : le leader envoie les messages dans le même ordre à tous.
Et en cas de log committed plus ancien, mais pending plus récent ?
Follower 1
A
B
C
Follower 2
A
B
C
C
C
D
Follower 1
A
B
C1
Follower 2
A
B
C2
*En réalité un peu plus compliqué que ça en cas de gros ralentissements du réseau ; ignoré ici par soucis de simplicité.
Détection de panne du leader
Panne détectée
"Je candidate,
voici mes logs"
Réception d'une première candidature
Remarque : je n'ai qu'un seul vote à donner par élection. Premier arrivé, premier servi.
...étant plus (ou autant) à jour que moi
"Je candidate,
voici mes logs"
"Elle est plus à jour,
je lui donne mon vote"
"Je vote pour toi"
...étant moins à jour que moi
"Je candidate,
voici mes logs"
"Elle est moins à jour,
j'ignore sa candidature."
Réception de votes
Si je reçois une majorité de votes,
Je me considère élu leader !
Problème ?
Un problème...
Et si tout le monde a les mêmes logs, et détecte la panne en même temps ?
Personne n'aura de majorité absolue...
"Je vote
pour toi"
"Je vote
pour toi"
"Je vote
pour toi"
Solution : l'aléatoire !
Les timeouts sont d'une durée aléatoire.
Celui qui timeout en premier a plus de chances d'être élu !
Problème ?
Problème : l'aléatoire !
Et si l'aléatoire ne suffit pas ?
Alors
Personne ne se considèrera élu, donc
Personne n'enverra de heartbeat, donc
Tout le monde va à nouveau timeout.
Autrement dit, les élections s'enchaineront jusqu'à ce qu'un élu soit trouvé.
Chaque processus a une durée de timeout d'élection.
Le leader envoie un heartbeat régulier à tous les followers.
Si je reçois une candidature
Si je suis candidat et reçois une majorité de votes
Résumé
En tant que follower,
Si aucun heartbeat pendant ma durée de timeout
Un follower peut-il avoir un log committed que l'élu n'a pas ?
Un follower peut-il avoir un log pending que l'élu n'a pas ?
Oui, en cas de panne...
Si oui,
Un message Confirm aurait été reçu pour ce log, donc
Le leader aurait reçu une majorité de ACK pour ce log, donc
Une majorité de processus possèderaient ce log, donc
Une majorité de processus n'auraient pas voté pour cet élu.
Donc impossible
Quand tout se complique (?)
LogThis
Il fait ajouter C à tous les followers
Sinon
Il fait retirer C à tous les followers
Le leader est tombé en panne
pendant le traitement de C.
L'ignorer n'est donc pas incohérent.
Problème ?
Ce log ne sera committed chez personne.
Pas de désaccord sur l'état de la machine.
Mais, désaccord possible sur les pending.
Leader
A
B
C
LogThis:C
Panne avant d'avoir envoyé à tout le monde
C sera perdu, mais c'est OK.
Pourquoi ?
Que doit faire le prochain leader ?
S'il avait reçu LogThis:C,
LogThis
Leader
A
B
C
LogThis:C
Panne avant d'avoir envoyé à tout le monde
Le leader demandera à tous les followers
d'écraser leurs logs par les siens.
Risque d'écraser un log committed ?
Risque d'écraser un log pending ?
Non
On a vu qu'aucun follower ne peut
avoir un log committed que le leader n'a pas.
Oui
Si une minorité avait reçu ce log,
il est possible qu'aucune d'entre elles n'ait été élue.
Dans ce cas, ce log sera perdu. C'est OK.
Problème ?
Ce log ne sera committed chez personne.
Pas de désaccord sur l'état de la machine.
Mais, désaccord possible sur les pending.
Que doit faire le prochain leader ?
Confirm
Leader
Confirm:C
Panne avant d'avoir envoyé à tout le monde
Si C est committed chez le nouveau leader
Il demande à tous les followers de le commit, si pas déjà fait.
Problème ?
Une majorité aura reçu LogThis:C,
Donc l'élu aura C parmi ses logs,
Mais peut-être seulement en pending.
A
B
C
Si C est pending chez le nouveau leader
Il demande à tous les followers de le logger, si pas déjà fait.
Puis enverra Confirm:C une fois qu'une majorité lui aura répondu.
Seul un sous-ensemble aura alors appliqué la modification.
Le leader peut crash pendant le broadcast d'un Confirm.
Deux mécanismes
L'élu est donc à jour avec la majorité des processus.
Tout ce qui a été committed chez l'ancien leader est donc committed chez le nouveau aussi.
Pourquoi ?
Et donc rollback sa machine ?
Le leader ne commit que quand une majorité est au courant, et il me faut une majorité pour être élu.
Non, s'il n'a pas ces logs, c'est qu'une majorité ne les avait pas.
Si une majorité ne les avait pas, alors il n'avait pas encore été commit par l'ancien leader.
Refus de candidature
"Si j'ai un log committed
plus récent que la candidature,
je la refuse."
Correction de désaccords
Le nouvel élu écrase les logs des autres par les siens.
Raft est un consensus spécialisé pour la réplication de machine d'état.
Le mécanisme d'élection assure
Un seul leader à la fois
La gestion des absences de majorité (via timeouts aléatoires)
L'élection d'un processus à jour avec la majorité des autres
Le mécanisme de réplication des logs assure
Un consensus sur les logs (via le leader central)
Une reprise par le prochain leader là où l'autre est mort
La limite des ⎡N/2⎤-1 pannes est essentielle
Un log n'est commited que quand une majorité en a connaissance
Une majorité doit accepter les logs d'un candidat pour l'élire
Il suffit donc d'une majorité de processus corrects pour avancer
Progrès uniquement
Un leader ne peut qu'ajouter à ses logs, pas en supprimer. Ce qui est fait est fait.
Unicité du leader
Un seul leader à la fois
Équivalence des logs
Si deux processus on un même log, tous leurs logs précédents sont identiques.
Complétude du leader
Si un leader possède un log committed, les prochains leaders l'auront aussi.
Validité de la machine d'état
Si un leader applique une opération à sa machine d'état, alors aucun autre processus ne peut appliquer une autre opération pour le même log.