Consensus distribué : Raft, élection du leader et quorum

Informatique de gestion · Master 2

Raft : élection du leader, réplication du journal et rôle du quorum de majorité.

Introduction

Dans un système distribué, plusieurs machines doivent s'accorder sur une valeur ou un ordre d'opérations malgré les pannes et les retards du réseau. C'est le problème du consensus. Il sous-tend les services de coordination, les bases répliquées et la gestion de configuration, où l'on ne peut tolérer deux versions contradictoires de la vérité.

Raft, conçu pour être plus compréhensible que Paxos, décompose le problème en trois parties : l'élection d'un leader, la réplication d'un journal ordonné de commandes, et la sûreté. Les nœuds sont suiveurs, candidats ou leader. En l'absence de signal du leader pendant un délai aléatoire, un suiveur devient candidat pour un nouveau terme et demande des votes ; la majorité l'emporte.

Le quorum de majorité est la clé : toute décision requiert l'accord de plus de la moitié des nœuds, donc deux majorités se recoupent toujours, ce qui interdit deux leaders légitimes dans le même terme. Un groupe de 2f+1 nœuds tolère f pannes. Les limites sont le coût de latence, la perte de disponibilité côté minoritaire en cas de partition, et l'impossibilité de consensus déterministe en système asynchrone avec pannes (résultat FLP).

Objectifs d'apprentissage

Définir le consensus et ses garanties de sûreté et de vivacité
Décrire les rôles et l'élection du leader dans Raft
Expliquer la réplication du journal et la notion de validation (commit)
Justifier la taille d'un groupe par le quorum de majorité
Analyser le comportement lors d'une partition réseau

Concepts clés

Consensus: Accord de tous les nœuds corrects sur une même valeur, qui a été proposée par l'un d'eux, malgré les pannes.
Élection du leader: Un suiveur sans nouvelles du leader devient candidat dans un nouveau terme ; il gagne s'il obtient la majorité des votes.
Réplication du journal: Le leader ajoute les commandes à son journal, les envoie aux suiveurs et les valide dès qu'une majorité les a enregistrées.
Quorum de majorité: Plus de la moitié des nœuds : deux quorums se recoupent toujours, ce qui évite les décisions contradictoires.
Partition réseau: Le côté minoritaire ne peut plus décider ; seul le côté majoritaire continue, ce qui préserve la cohérence au prix de la disponibilité.

Conclusion

Le consensus donne à un ensemble de machines l'apparence d'un seul service cohérent. Raft l'obtient par un leader élu à la majorité, un journal répliqué et validé par quorum, et des termes qui ordonnent les élections.

Le prix est clair : latence de coordination et indisponibilité du côté minoritaire en cas de partition. Choisir la taille du groupe et sa répartition (zones, sites) est un arbitrage de gestion du risque autant que de technique.

Cartes

Quel problème résout un algorithme de consensus ?: Faire s'accorder plusieurs nœuds sur une valeur ou un ordre d'opérations malgré des pannes de nœuds et de réseau.
Quels sont les trois rôles d'un nœud Raft ?: Suiveur (follower), candidat (candidate) et leader.
Qu'est-ce qu'un terme dans Raft ?: Un numéro croissant qui joue le rôle d'horloge logique : chaque élection ouvre un nouveau terme, et un nœud adopte toujours le terme le plus élevé qu'il voit.
Pourquoi les délais d'élection sont-ils aléatoires ?: Pour éviter que plusieurs suiveurs deviennent candidats en même temps et se partagent les votes sans qu'aucun n'obtienne la majorité.
Quand une entrée du journal est-elle validée (committed) ?: Quand le leader l'a répliquée sur une majorité de nœuds ; elle peut alors être appliquée à la machine à états.
Combien de pannes un groupe de cinq nœuds Raft tolère-t-il ?: Deux : la majorité de trois nœuds reste disponible.
Pourquoi utiliser un nombre impair de nœuds ?: Un groupe de 2f+1 tolère f pannes ; passer à un nombre pair ne tolère pas plus de pannes mais ajoute de la charge.
Que se passe-t-il pour le côté minoritaire lors d'une partition ?: Il ne peut pas élire de leader ni valider d'entrées : il perd la disponibilité en écriture, ce qui évite la divergence (split-brain).
Qu'est-ce qu'un split-brain ?: Une situation où deux parties d'un système se croient chacune le leader et acceptent des écritures contradictoires.
Que dit le résultat d'impossibilité FLP ?: Dans un système asynchrone, aucun algorithme déterministe ne peut garantir le consensus si un seul nœud peut tomber en panne ; les protocoles pratiques utilisent donc des délais d'attente.
Quels services reposent couramment sur un protocole de consensus ?: Les services de coordination et de configuration, les annuaires de services et les bases de données répliquées à forte cohérence.

Glossaire

Consensus: Accord des nœuds corrects sur une même décision malgré les pannes.
Leader: Nœud qui reçoit les écritures et ordonne le journal répliqué.
Terme: Numéro croissant qui identifie une période de leadership.
Quorum: Sous-ensemble de nœuds, ici la majorité, dont l'accord est nécessaire pour décider.
Journal répliqué: Suite ordonnée de commandes copiée sur les nœuds.
Split-brain: Division d'un cluster en parties qui agissent comme si chacune était seule maîtresse.