Contexte
Un système distribué nécessite un consensus sur l’état partagé.
Alternative à Paxos, plus simple à comprendre et implémenter.
Utilisé pour gérer un log répliqué.
Principe du replicated log
graph TB C[Client] --> L[Leader] L --> F1[Follower 1] L --> F2[Follower 2] L --> F3[Follower 3] F1 --> SM1[State Machine 1] F2 --> SM2[State Machine 2] F3 --> SM3[State Machine 3] L --> SML[State Machine Leader]
Chaque serveur maintient un log contenant les mêmes commandes dans le même ordre.
Les state machines traitent les commandes identiques et produisent les mêmes sorties.
Modèle de pannes : messages retardés/perdus, fail-stop (pas Byzantine).
Élection du leader
À tout moment, un seul serveur est leader.
Les autres sont followers et répliquent passivement.
Si le leader échoue, un nouveau leader est élu.
Log Matching Property
Deux propriétés garantissent la cohérence :
Si deux entrées dans des logs différents ont même index et term, elles stockent la même commande.
Si deux entrées ont même index et term, tous les logs sont identiques dans les entrées précédentes.
Gestion des inconsistances
Les crashes peuvent créer des inconsistances de logs :
Leader: [1][2][3][4][5]
Follower: [1][2][3] -- Entrées manquantes
Follower: [1][2][3][4][6] -- Entrée incorrecte
Follower: [1][2][3][4][5][7] -- Entrée non committée en trop
Résolution
Le leader considère son log comme correct.
Force les followers à correspondre en écrasant les entrées conflictuelles.
Envoie les entrées manquantes.
Supprime les entrées non committées.