Le consensus Raft expliqué : élection du leader et réplication du journal

Chaque cluster Kubernetes stocke son état dans etcd, et etcd se met d'accord sur cet état avec Raft. C'est aussi le cas de Consul, CockroachDB, TiKV, des quorum queues de RabbitMQ et, depuis que Kafka 4.0 a supprimé ZooKeeper, des contrôleurs de Kafka lui-même. Si vous exploitez l'un d'eux, Raft explique des comportements qui paraîtraient sinon arbitraires : pourquoi un cluster de trois nœuds cesse d'accepter les écritures quand deux nœuds tombent, pourquoi les écritures marquent une pause d'une seconde lors d'un changement de leader, et pourquoi un quatrième nœud rend un cluster plus cher sans le rendre plus sûr.

Cet article explique Raft avec un diagramme de la réplication du journal dans un cluster de cinq nœuds : mandats, élection du leader, AppendEntries, règle de commit, pannes, dimensionnement du cluster, lectures et changements de composition.

Le modèle : un journal répliqué

Raft construit une machine à états répliquée. Chaque serveur tient un journal de commandes. Si tous les serveurs appliquent les mêmes commandes dans le même ordre, ils aboutissent au même état. Le rôle de Raft est de garder les journaux identiques, même quand des serveurs plantent et que des messages sont perdus ou retardés.

Chaque serveur est dans l'un de trois états : follower, candidat ou leader. Le temps est découpé en mandats (terms), numérotés 1, 2, 3 et ainsi de suite ; chaque mandat commence par une élection et compte au plus un leader. Un serveur qui voit un mandat supérieur au sien met à jour son mandat et redevient follower : un leader périmé se retire dès qu'il entend parler du plus récent.

Raft n'a besoin que de deux RPC, plus une pour les snapshots :

La conception vient de l'article In Search of an Understandable Consensus Algorithm de Diego Ongaro et John Ousterhout, publié à l'USENIX ATC 2014.

L'élection du leader

Un follower attend des heartbeats réguliers du leader. S'il n'en reçoit aucun avant l'expiration de son délai d'élection, il suppose que le leader a disparu :

1. Il incrémente son mandat, devient candidat et vote pour lui-même.
2. Il envoie RequestVote à tous les autres serveurs, avec l'index et le mandat de sa dernière entrée de journal.
3. Chaque serveur accorde au plus un vote par mandat, et seulement à un candidat dont le journal est au moins aussi à jour que le sien : un dernier mandat plus élevé l'emporte et, à mandat égal, le journal le plus long l'emporte.
4. Un candidat qui recueille les votes d'une majorité devient leader et commence à envoyer des heartbeats.

Si deux candidats se partagent les votes, personne ne gagne et le mandat se termine sans leader. Raft rend ce cas rare en tirant les délais au hasard ; l'article suggère des valeurs comme 150 à 300 ms, si bien qu'un serveur expire généralement le premier et gagne avant que les autres ne commencent.

Les systèmes en production choisissent leurs délais selon leur réseau. etcd utilise par défaut un heartbeat de 100 ms et un délai d'élection de 1 000 ms, et sa documentation indique que le délai d'élection doit valoir au moins dix fois l'aller-retour entre membres. Ces chiffres expliquent pourquoi un plan de contrôle Kubernetes peut mettre une seconde ou plus à accepter de nouveau les écritures après la perte de son leader etcd.

La réplication du journal

Une fois élu, le leader traite chaque écriture :

1. Un client envoie une commande au leader, par exemple SET x=5.
2. Le leader l'ajoute à son propre journal comme nouvelle entrée avec le mandat courant, disons l'index 7 au mandat 3.
3. Le leader envoie à chaque follower un AppendEntries avec la nouvelle entrée, plus l'index et le mandat de l'entrée qui la précède (index 6, mandat 3).
4. Un follower n'accepte que si son journal contient une entrée à l'index 6 avec le mandat 3. Ce contrôle de cohérence garantit que si deux journaux concordent à une position, ils concordent sur tout ce qui précède.
5. Quand une majorité de serveurs, leader compris, stocke l'entrée, le leader la marque comme validée (committed), l'applique à sa machine à états et répond au client.
6. Les followers apprennent le nouvel index de commit au prochain AppendEntries et appliquent l'entrée à leur tour.

Si un follower rejette une entrée parce que son journal diverge, le leader recule d'un index à la fois, ou plus vite avec des optimisations, jusqu'à ce que les journaux concordent, puis écrase les entrées en conflit du follower avec les siennes. Seules des entrées non validées sont écrasées, ce qui est sûr puisque personne ne s'est entendu dire qu'elles avaient réussi.

La règle de commit, et sa subtilité

« Validée dès qu'une majorité la stocke » a une exception, et c'est le détail le plus célèbre de l'article. Un nouveau leader ne doit pas compter les répliques pour valider des entrées héritées de mandats antérieurs. Il les valide indirectement, en validant par-dessus une entrée de son propre mandat. Sans cette règle, une entrée stockée sur une majorité pourrait encore être écrasée par un leader ultérieur. En pratique, un nouveau leader ajoute une entrée vide no-op au début de son mandat pour valider rapidement tout ce qui précède.

La restriction d'élection complète l'argument de sûreté : comme un candidat a besoin des votes d'une majorité et que chaque entrée validée se trouve sur une majorité, tout gagnant possible détient déjà toutes les entrées validées.

Ce qu'un cluster supporte

Un cluster de n serveurs a besoin d'une majorité pour élire un leader et valider les écritures ; il tolère donc la panne de moins de la moitié :

Quatre serveurs tolèrent une panne, comme trois, mais chaque écriture attend désormais trois accusés de réception au lieu de deux. C'est pourquoi les clusters ont des tailles impaires. Cinq est le choix habituel quand on veut survivre à une panne pendant la maintenance planifiée d'un autre nœud.

La latence suit la même arithmétique. Chaque écriture attend que le leader atteigne la majorité la plus rapide et que ces serveurs persistent l'entrée sur disque. Dans un cluster réparti sur trois régions, chaque écriture coûte au moins un aller-retour vers la région voisine la plus proche. Les disques lents font autant de dégâts que les réseaux lents, ce qui explique que la documentation d'etcd consacre autant de place à la latence de fsync qu'aux délais.

Les pannes en pratique

• Le leader plante. Les followers expirent, l'un gagne une élection et les écritures reprennent. Les requêtes en vol peuvent avoir été validées ou non ; les clients doivent donc réessayer, et les commandes qu'ils rejouent doivent être idempotentes.
• Une partition réseau. Le côté majoritaire élit un leader et continue. Un ancien leader du côté minoritaire ne peut rien valider ; une fois la partition résorbée, il voit le mandat supérieur et se retire.
• Un follower lent. Les commits ne l'attendent pas. S'il prend beaucoup de retard, le leader lui envoie un snapshot au lieu de rejouer tout le journal.
• Un serveur perturbateur. Un serveur coupé du leader continue d'expirer et d'augmenter son mandat, ce qui peut forcer des élections inutiles à son retour. Le pre-vote, issu de la thèse d'Ongaro, permet à un candidat de vérifier qu'il pourrait gagner avant d'incrémenter son mandat.

Les lectures ne sont pas gratuites

Un leader ne peut pas répondre aveuglément aux lectures depuis son propre état : un nouveau leader a pu être élu de l'autre côté d'une partition, et l'ancien renverrait des données périmées. Les lectures linéarisables exigent soit un tour de heartbeats pour confirmer le leadership avant de répondre (le ReadIndex de Raft), soit un bail de leader temporel, qui suppose une dérive d'horloge bornée. Les followers peuvent aussi servir des lectures, mais seulement après avoir vérifié l'index de commit du leader, ou en acceptant des résultats périmés. etcd le rend explicite : etcdctl get est linéarisable par défaut, et --consistency=s demande une lecture sérialisable plus rapide, éventuellement périmée.

Changer la composition du cluster

Ajouter ou retirer des serveurs change ce qu'est une majorité, et changer de configuration sans précaution peut créer deux majorités à la fois. Raft gère cela par le joint consensus ou en changeant un seul serveur à la fois. Beaucoup d'implémentations ajoutent aussi les nouveaux serveurs comme learners sans droit de vote, comme le fait etcd, pour qu'un nœud neuf rattrape le journal avant de compter dans la majorité.

Le diagramme de réplication du journal

Comment le lire :

• Le client envoie une commande au leader, S1, au mandat 3. Le leader l'écrit à l'index 7.
• Chaque tableau est le journal d'un serveur : index, mandat et commande. Les lignes identiques d'un tableau à l'autre sont la même entrée.
• Les arêtes AppendEntries vont du leader aux quatre followers. S2 et S3 accusent réception de l'index 7.
• S4 est en retard à l'index 6 et S5 est injoignable à l'index 5. Aucun des deux ne bloque le commit.
• La note montre la règle de commit : trois serveurs sur cinq stockent l'entrée 7, elle est donc validée et le client reçoit sa réponse.

Dessiner des diagrammes de consensus pédagogiques

• Montrez les journaux, pas seulement les serveurs. Les garanties de Raft sont des énoncés sur les journaux. Un diagramme fait de cinq boîtes et de flèches cache tout ce qui est intéressant.
• Écrivez le mandat à côté de chaque entrée. Les mandats expliquent les élections, les conflits et la règle de commit.
• Dessinez un cluster en mauvaise santé. Un follower en retard ou isolé montre mieux qu'un cluster parfait pourquoi les majorités comptent.
• Faites un diagramme par scénario : une élection, la réplication normale et la réparation d'un conflit après un basculement méritent chacune leur propre image.

Pour la place de la réplication dans les architectures de bases de données en général, voyez le diagramme de réplication de base de données. Le diagramme d'architecture Kubernetes montre où se trouve etcd dans un plan de contrôle, et le diagramme d'architecture Kafka traite des contrôleurs KRaft. Des systèmes comme CockroachDB exécutent un groupe Raft par plage de données, ce qui relie le consensus aux idées du diagramme de sharding de base de données.

Le construire dans Archboard

1. Connectez-vous avec Google ou GitHub et créez un diagramme.
2. Ajoutez un Cadre du pack Base pour le cluster et étiquetez-le avec le mandat courant.
3. Ajoutez-y cinq nœuds Tableau du pack Base, un par serveur, avec des colonnes pour l'index, le mandat et la commande. Placez le leader au milieu.
4. Ajoutez hors du cadre une Boîte du pack Base pour le client et reliez-la au leader avec la commande.
5. Dessinez des arêtes AppendEntries du leader vers chaque follower, avec des arêtes d'accusé de réception en pointillé en retour depuis les followers qui ont stocké l'entrée. Signalez le follower injoignable par une arête en pointillé d'une couleur d'alerte.
6. Ajoutez un bloc Markdown du pack Base avec la règle de commit, et une Note à côté du leader indiquant l'index de commit.

L'exemple utilise 8 nœuds de diagramme et reste dans les limites de l'offre Free.

FAQ

Pourquoi les clusters Raft ont-ils un nombre impair de nœuds ? Un cluster a besoin d'une majorité pour fonctionner. Ajouter un quatrième nœud à trois fait passer la majorité de deux à trois sans tolérer davantage de pannes : les tailles paires coûtent de la latence et de l'argent sans ajouter de tolérance aux pannes.

Que deviennent les écritures pendant une élection de leader ? Elles attendent ou échouent jusqu'à l'élection d'un nouveau leader, en général en un ou deux délais d'élection. Les clients doivent réessayer avec des requêtes idempotentes, car une écriture arrivée à expiration a peut-être été validée.

Quelle est la différence entre Raft et Paxos ? Ils résolvent le même problème avec des garanties similaires. Raft a été conçu pour être plus facile à comprendre et à implémenter : il utilise un leader fort, sépare l'élection de la réplication et spécifie les changements de composition.

Les followers peuvent-ils servir des lectures dans Raft ? Oui, s'ils confirment d'abord l'index de commit du leader, ou si l'application accepte des données éventuellement périmées. Lire l'état local d'un follower sans vérification peut renvoyer d'anciennes valeurs.

Raft protège-t-il contre les nœuds malveillants ? Non. Raft tolère les plantages, les redémarrages et les messages perdus ou retardés, mais il suppose que les serveurs suivent le protocole. La tolérance aux pannes byzantines exige d'autres algorithmes et davantage de répliques.

Commencez gratuitement — un siège, sans carte bancaire.