Olivier Lemer
Pas plus de ⎡N/2⎤-1 pannes simultanné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
La machine d'état elle-même
L'état actuel, toutes opérations appliquées.
Chaque log peut donc être
(pas encore appliqué)
(appliqué)
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
Un algorithme spécialisé
Chaque processus a une durée de timeout d'élection.
Le leader envoie un heartbeat régulier à tous les followers.
En tant que follower,
Si aucun heartbeat pendant ma durée de timeout
Si je reçois une candidature
Si je suis candidat et reçois une majorité de votes
La durée du timeout d'élection est aléatoire pour éviter ce scénario !
A
B
C
D
Leader
moi!
moi!
moi!
moi!
"Déjà voté pour B"
"Déjà voté pour C"
"Déjà voté pour D"
A
B
C
D
Leader
moi!
"Déjà voté pour D"
"Déjà voté pour D"
ok
ok
"Déjà voté pour D"
Ça peut toujours arriver. Dans ce cas, personne ne sera leader, on ne recevra pas de heartbeat, et on relancera donc une élection.
Gestion des incohérences
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 commit/appliqué que quand une majorité est prête
Une majorité doit accepter les logs d'un candidat pour l'élire
Suffit donc d'une majorité de processus corrects pour avancer
Unicité du leader
Un seul leader à la fois
Progrès uniquement
Un leader ne peut qu'ajouter à ses logs, pas en supprimer. Ce qui est fait est fait.
É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.