L’algorithme de consensus Raft (2015)
(raft.github.io)- Raft a été conçu pour rendre le problème du consensus plus facile à comprendre, afin que plusieurs serveurs d’un système distribué puissent prendre la même décision, avec pour objectif une tolérance aux pannes et des performances équivalentes à Paxos
- Raft divise la structure en sous-problèmes comme l’élection du leader, la réplication du journal et la sûreté, afin de rendre plus explicites les points de décision nécessaires à l’implémentation d’une machine à états répliquée
- Tant qu’une majorité des serveurs reste en vie, le système peut progresser, et si la majorité disparaît il s’arrête sans produire de résultat erroné, ce qui préserve la sûreté
- Le site regroupe RaftScope basé sur le navigateur, la visualisation The Secret Lives of Data, l’article Raft, la spécification TLA+, ainsi que des articles et supports de présentation sur la vérification et l’analyse
- Des implémentations dans de nombreux langages, dont Rust, Go, Java, C++, C#, Python, sont répertoriées, avec des différences de prise en charge selon les implémentations pour l’élection du leader et la réplication du journal, la persistance, les changements d’appartenance et la compaction du journal
Le problème de consensus visé par Raft
- Raft a été conçu pour rendre les algorithmes de consensus compréhensibles par un public plus large
- Son objectif est d’atteindre un niveau de tolérance aux pannes et de performance équivalent à Paxos
- La différence essentielle tient à la structure
- le problème est découpé en sous-problèmes relativement indépendants
- les composants nécessaires à l’implémentation d’un système réel sont traités séparément
- Le but est de rendre les systèmes fondés sur le consensus plus faciles à comprendre et à implémenter avec une meilleure qualité
Consensus et machine à états répliquée
- Le consensus est le problème fondamental des systèmes distribués tolérants aux pannes
- Plusieurs serveurs se mettent d’accord sur une valeur, et une fois décidée, cette valeur devient l’état final
- Un algorithme de consensus classique progresse lorsqu’une majorité des serveurs est disponible
- un cluster de 5 serveurs peut continuer à fonctionner même si 2 serveurs tombent en panne
- si davantage de serveurs échouent, la progression s’arrête
- il est alors essentiel de ne pas renvoyer de résultat erroné
- Le consensus est généralement utilisé pour construire une machine à états répliquée
- chaque serveur possède une machine à états et un journal
- la machine à états peut être un composant auquel on veut apporter de la tolérance aux pannes, comme une table de hachage
- le client peut ainsi avoir l’impression d’interagir avec une seule machine à états fiable, même si certains serveurs échouent
- Chaque machine à états reçoit comme entrée les commandes de son propre journal
- dans l’exemple de la table de hachage, une commande comme
set x to 3est inscrite dans le journal - l’algorithme de consensus détermine quelles commandes insérer dans le journal des serveurs et dans quel ordre
- si une machine à états applique
set x to 3comme n-ième commande, il faut garantir qu’aucune autre machine à états n’applique une commande différente à cette même position
- dans l’exemple de la table de hachage, une commande comme
- Au final, toutes les machines à états traitent la même suite de commandes et atteignent la même suite de résultats et le même état
Visualisations pour comprendre Raft
- Il est possible de manipuler directement une visualisation d’un cluster Raft exécuté dans le navigateur
- à gauche, 5 serveurs sont affichés
- à droite, le journal de chaque serveur est affiché
- l’utilisateur peut interagir et observer le fonctionnement de Raft
- RaftScope a encore besoin d’être peaufiné et les Pull Requests sont les bienvenues
- The Secret Lives of Data est une visualisation différente de Raft
- elle est plus guidée et moins interactive
- elle peut constituer un point d’entrée plus doux pour les lecteurs qui découvrent le sujet
Article, spécification et ressources de vérification
- In Search of an Understandable Consensus Algorithm (Extended Version) est l’« article Raft » qui traite Raft en détail
- il est rédigé par Diego Ongaro et John Ousterhout
- une version un peu plus courte a reçu le Best Paper Award à la 2014 USENIX Annual Technical Conference
- La thèse de doctorat de Diego Ongaro développe le contenu de l’article plus en profondeur
- elle inclut un algorithme plus simple de changement d’appartenance du cluster
- elle contient aussi la spécification formelle TLA+ de Raft
- une version légèrement mise à jour de la spécification est disponible dans raft.tla
- Les articles associés traitent de la vérification formelle de Raft, de frameworks pour implémenter et vérifier des systèmes distribués, de génération de code à partir de modèles formels et d’analyse de protocole
- Planning for Change in a Formal Verification of the Raft Consensus Protocol, CPP 2016
- Verdi: A Framework for Implementing and Verifying Distributed Systems, PLDI 2015
- Automatic Distributed Code Generation from Formal Models of Asynchronous Concurrent Processes, PDP 2015
- Raft Refloated: Do We Have Consensus?, SIGOPS Operating Systems Review 2015
- ARC: Analysis of Raft Consensus, University of Cambridge Technical Report 2014
Conférences et ressources pédagogiques
- Une liste de conférences d’introduction à Raft est également fournie
- conférence de John Ousterhout dans la CS@Illinois Distinguished Lecture Series, août 2016
- conférence de Jin Li sur Raft et la spécification TLA+ dans la Dr. TLA+ Series, juillet 2016
- conférences de Diego Ongaro à Build Stuff 2015, CoreOS Fest 2015, Sourcegraph meetup, LinkedIn, USENIX ATC 2014, CraftConf 2014, RICON West 2013
- conférence de Ben Johnson à Strange Loop 2013
- cours de John Ousterhout sur la Raft User Study, mars 2013
- Raft est aussi utilisé dans l’enseignement supérieur et les cursus de formation, sous forme de cours ou de travaux pratiques de programmation
- plusieurs cursus sont mentionnés, notamment à l’University of Copenhagen, la Czech Technical University in Prague, The University of Hong Kong, l’University of Virginia, UC San Diego, la Technical University of Munich et l’UIUC
- certains cursus proposent des travaux pratiques de programmation Raft en Go, Java, Erlang, etc.
- le MIT 6.824 inclut des notes de cours sur Raft et renvoie aussi vers des textes de Jon Gjengset destinés aux enseignants et aux étudiants
- Les cursus supplémentaires peuvent être ajoutés ou mis à jour via une Pull Request ou une issue dans le dépôt du site
Canal de questions et liste d’implémentations
- Pour les questions sur Raft et ses implémentations, le groupe Google raft-dev est indiqué comme l’endroit approprié
- Certaines implémentations ont leur propre mailing list, il faut donc vérifier chaque README
- Une liste d’implémentations de Raft dont le code source est public est également fournie
- les implémentations populaires ou récemment mises à jour sont placées en haut du tableau
- les informations peuvent devenir obsolètes avec le temps et peuvent être mises à jour via une Pull Request ou une issue
- Le tableau compare, pour chaque implémentation, les Stars, le nom, les principaux auteurs, le langage, la licence et la prise en charge des fonctionnalités
- les fonctionnalités comparées sont l’élection du leader et la réplication du journal, la persistance, les changements d’appartenance et la compaction du journal
- Exemples d’implémentations figurant en tête de liste
- TiKV : Rust, Apache-2.0, 16,751★, prise en charge complète de l’élection du leader, de la réplication du journal, de la persistance, des changements d’appartenance et de la compaction du journal
- RethinkDB : C++, Apache-2.0, 27,000★, prise en charge complète des principales fonctionnalités
- Seastar Raft : C++20, AGPL, 15,624★, prise en charge complète des principales fonctionnalités
- hashicorp/raft : Go, MPL-2.0, 9,048★, prise en charge complète des principales fonctionnalités
- hazelcast-raft : Java, Apache-2.0, 6,579★, prise en charge complète des principales fonctionnalités
- La liste comprend des implémentations dans des langages variés, notamment Rust, Go, Java, C++, C, Erlang, Python, Scala, C#, JavaScript, Haskell, OCaml, Kotlin, Zig, TypeScript, Elixir, F#, Shell, etc.
1 commentaires
Avis sur Hacker News
Maelstrom, l’atelier d’apprentissage des systèmes distribués créé par l’auteur de Jepsen, contient une implémentation simple de vérification de modèle de Raft ainsi qu’un bon tutoriel d’implémentation : https://github.com/jepsen-io/maelstrom/
Raft est un algorithme simple, mais l’article original contient beaucoup de détails de correction souvent omis dans les implémentations jouets.
Si l’on prend aussi en compte la corruption mémoire/disque sur du matériel réel, les défaillances grises, des SLA de latence stricts, les quorums flexibles et l’appartenance dynamique au cluster, une implémentation en production devient un travail long et lourd.
Il suffit de regarder l’historique des commits d’etcd et de hashicorp/raft pour voir que même les implémentations open source de Raft les plus éprouvées révèlent régulièrement des bugs de correction.
L’équipe TigerBeetle traite en détail la réalité des systèmes distribués avec du matériel imparfait et des modèles de systèmes non abstraits, et explique aussi pourquoi elle a choisi Viewstamped Replication, plus ancien que Paxos mais qui semble plus proche de Raft : https://github.com/tigerbeetle/tigerbeetle/blob/main/docs/DE...
Je ne sais pas très bien quelles conséquences cela a sur les préoccupations d’implémentation, mais l’article lui-même est excellent et je le recommande.
Il existe aussi une présentation, mais pour faire des allers-retours dans les références, je trouve le texte plus pratique : https://www.youtube.com/watch?v=0K6kt39wyH0
Même sans avoir jamais vu d’algorithme de consensus auparavant, après quelques lectures j’ai pu le suivre dans une certaine mesure : https://dspace.mit.edu/bitstream/handle/1721.1/71763/MIT-CSA...
J’ai récemment implémenté l’élection du leader et la réplication de journal de Raft ; je ne suis pas allé jusqu’aux snapshots/checkpoints, mais c’est l’un des projets les plus difficiles que j’aie réalisés jusqu’ici.
L’article sur Raft est agréable à lire et donne une bonne intuition.
Même sans l’implémenter soi-même, il y a de fortes chances qu’on utilise déjà des logiciels fondés sur Raft comme etcd, Consul, CockroachDB ou TiDB.
J’ai rassemblé ici les ressources qui m’ont été utiles pendant l’implémentation : https://github.com/eatonphil/goraft#references
Cela inclut aussi la thèse de Diego Ongaro et la spécification TLA+.
Certains disent que « la Figure 2 de l’article Raft suffit », mais comparée à la spécification TLA+, elle est beaucoup plus ambiguë, donc je ne pense pas que ce soit vrai.
Je recommande de le brancher sur les tests Raft du cours de systèmes distribués du MIT : https://pdos.csail.mit.edu/6.824/labs/lab-raft.html
Au moins pour l’élection du leader et la réplication du journal, cela semble faisable avec un peu de refactorisation.
Je le recommande vraiment, surtout à ceux qui découvrent les algorithmes distribués.
La qualité de l’implémentation n’est sans doute pas extraordinaire, mais je la mets ici pour les personnes intéressées : https://github.com/skowalak/fastapi-raft/
Il y a dans l’article plusieurs autres détails concrets nécessaires à l’implémentation.
Si les algorithmes de consensus vous intéressent, le livre Reasoning about Knowledge, que nous utilisions dans un cours de théorie des systèmes distribués, vaut aussi le détour : https://mitpress.mit.edu/9780262562003/reasoning-about-knowl...
Il faut investir un peu pour apprendre la logique modale, mais une fois ce cap passé, les preuves expliquant pourquoi Raft ou Paxos fonctionnent deviennent très intuitives et simples.
C’est une manière de pousser la complexité de la preuve dans la structure logique utilisée pour la preuve, et cela a changé ma façon de voir le consensus.
« Raft Consensus Algorithm Failure », Théodore Géricault, 1819 : https://classicprogrammerpaintings.com/post/6141087496359280...
Si vous ne voyez pas ce que montre la visualisation, il suffit de noter qu’on peut cliquer sur un nœud pour provoquer une panne
C’est particulièrement intéressant à faire sur le nœud actuellement leader, celui qui envoie et reçoit tous les paquets
En cliquant sur la petite icône de pause à côté du premier curseur pour la remettre en horloge, la simulation reprend
Je ne sais pas encore à quoi correspond la feuille de calcul à droite, et comme elle est toujours vide, elle donne l’impression d’être cassée
Les éléments cliquables que j’ai trouvés jusqu’ici sont les deux curseurs, l’icône horloge/pause et les serveurs individuels
En cliquant sur le leader puis en choisissant
request, on peut simuler l’envoi d’une commandeSi vous mettez une réplique hors ligne, vous pouvez la voir prendre du retard, puis rattraper son retard lorsqu’elle revient
Il y a quelques années, j’étais dans un environnement où un système de type Chubby robuste sous forte charge critique était toujours important, et à l’époque, quand l’échec n’était pas acceptable, on utilisait ZooKeeper
Mais il me semble qu’aujourd’hui, des gens font tourner depuis des années des charges très lourdes sur des options basées sur Raft comme etcd ou Consul
Je me demande si l’une d’elles est devenue le choix par défaut
La clarté conceptuelle et l’élégance de Raft semblent devoir se traduire en performances et en fiabilité, mais mon intuition dans ce domaine date un peu
Je me demande ce qu’utilisent en 2023, comme bonne pratique par défaut pour des systèmes à forte criticité, les gens qui ne sont pas liés à Google ou à GCP
Il me semble qu’il existait une implémentation Rust de Raft de niveau production côté TiKV, et un serveur de verrous robuste et performant paraît être un domaine assez bien adapté à Rust ; je me demande aussi s’il est réellement utilisé
Si c’est la réponse à « Qu’est-ce que Raft ? », alors même après l’avoir lue, je ne sais toujours pas
« Raft est un algorithme de consensus conçu pour être facile à comprendre. Il est équivalent à Paxos en termes de tolérance aux pannes et de performances. La différence est qu’il est décomposé en sous-problèmes relativement indépendants, et qu’il traite proprement les principaux éléments nécessaires aux systèmes pratiques. Nous espérons que Raft rendra le consensus accessible à un public plus large, et que ce public pourra créer une plus grande variété de systèmes de haute qualité fondés sur le consensus qu’aujourd’hui »
Ce genre de chose n’est pas propre à eux, mais je trouve dommage qu’ils ne prennent pas davantage le temps d’expliquer correctement leur travail
Parce qu’elle filtre automatiquement les lecteurs qui n’en connaissent pas le sens
Pour quelqu’un qui construit des systèmes distribués et compare plusieurs algorithmes de consensus, c’est une explication simple et claire ; sinon, il y a de bonnes chances que ce ne soit de toute façon pas un algorithme pertinent pour lui
En général, les algorithmes de consensus cherchent à résoudre le problème suivant : on a des répliques d’un magasin de données réparties sur plusieurs machines physiques, et il faut décider quoi faire lorsque certaines machines ou certaines connexions échouent d’une manière ou d’une autre
On parle de « consensus » parce qu’en situation de panne, les machines doivent se mettre d’accord sur la décision à prendre concernant un fragment de données
Par exemple, si trois serveurs répliquent la même base de données SQL sous la forme
(A) - (B) - (C), et que la connexion réseau entre C et les deux autres est coupée, A et B peuvent le détecter et promouvoir B comme nœud principalMais C ne sait pas ce qui s’est passé et peut continuer à accepter certaines écritures
Lorsque la connexion est rétablie, A, B et C doivent alors décider quoi faire
Comme B et C ont reçu indépendamment des ensembles d’écritures différents, les serveurs doivent se mettre d’accord sur la manière de traiter les données
C’est précisément le problème que Raft, Paxos, etc. cherchent à résoudre de façon cohérente et performante
Certains concepts sont trop vastes pour être présentés en un seul paragraphe à quelqu’un qui n’a aucune connaissance préalable
Cela dit, je trouve que l’article lié est une excellente introduction si on continue la lecture
En tant que chercheur sur les protocoles de consensus, je pense que la recherche sur la blockchain des dix dernières années a rendu le consensus beaucoup plus facile à comprendre
Raft, surtout si l’on inclut ses subtilités, se lit et s’implémente comme du grec ancien en comparaison
Si quelqu’un découvrait aujourd’hui les protocoles de consensus, je le ferais commencer par Bitcoin, puis passer à Paxos, Tendermint et Simplex, et je lui ferais carrément sauter Raft
Simplex est un article que j’ai écrit, une version simplifiée de PBFT
Raft paraît relativement simple
Je me demande ce que la blockchain apporte qui soit plus facile à maintenir et moins propice aux erreurs que « élire un leader et répliquer le journal »
J’aime beaucoup ce site
Cette page m’a été vraiment utile quand j’ai appris et implémenté Raft dans un cours de systèmes distribués
L’article lui-même est aussi assez facile à lire
Merci d’avoir rendu Raft aussi clair
Je me demande s’il existe des algorithmes de consensus où les changements ne doivent pas forcément passer par le leader
Dans beaucoup de systèmes distribués, on veut aussi distribuer le traitement des entrées
L’un d’eux est Chord : https://en.m.wikipedia.org/wiki/Chord_(peer-to-peer)
Chord est un anneau P2P où les nœuds se répartissent les valeurs par hachage cohérent
Le réseau utilise ce qu’on appelle une « finger table », qui stocke essentiellement les informations de réplication sous forme de table
Les informations de cette table peuvent être erronées ou obsolètes, et le pair contacté peut indiquer d’aller voir un autre pair, généralement le nœud suivant ou un successeur, jusqu’à ce que la valeur soit trouvée ou non
Si cet algorithme peut être utilisé sans « leader », c’est parce qu’il fonctionne même en allant simplement vers un nœud puis en parcourant tous les nœuds linéairement
La finger table, qui sert à accélérer les requêtes, n’est pas indispensable
Dans ces systèmes, il y a généralement un « leader » par transaction, mais en fonctionnement normal ce rôle n’est pas disputé
Le coordinateur de transaction s’auto-déclare ; une élection n’a lieu que si ce coordinateur échoue pour une raison quelconque
Il peut même y avoir plusieurs leaders simultanément pour une donnée ou une clé donnée
Cassandra développe actuellement Accord, un protocole sans leader de cette famille
En fait, Cassandra utilise déjà un protocole sans leader pour les LWT
C’est une variante optimisée du Paxos classique à consensus unique, mais si des transactions concurrentes sur la même clé sont déclarées simultanément, le surcoût devient important
Si les transactions portent sur des sujets indépendants, on peut sharder les leaders pour répartir la charge
Cela consiste à attribuer des plages de l’espace de clés à différents leaders et à ajuster les élections pour que chaque nœud détienne une part appropriée de leadership
Pour fonctionner sans leader, on peut structurer chaque écriture comme une sorte d’élection
Pour une transaction provisoire, ou lorsqu’une transaction est volumineuse, on diffuse la requête de transaction à tous les nœuds ; si l’on obtient un quorum d’acceptation, elle l’emporte et est commitée
Mais si plusieurs nœuds tentent des transactions presque simultanément, parvenir au consensus peut prendre beaucoup de temps
S’il y a beaucoup de nœuds et qu’ils ont tous des transactions en attente sur le même sujet, élire un leader et faire passer toutes les transactions par lui est bien plus rapide que d’établir un consensus séparé pour chaque transaction
Toutefois, si l’objectif est de distribuer pour améliorer le débit, une approche ne nécessitant qu’un seul leader peut être plus efficace que le quorum exigé par Paxos
Ce n’est qu’une supposition
Paxos est aussi plus efficace si les appels vont toujours au même endroit
Parce que cela permet d’éviter la contention et les nouveaux votes, entre autres
En substance, chaque shard dispose de son propre consensus Paxos