Raft-Konsensalgorithmus (2015)
(raft.github.io)- Raft wurde entwickelt, um das Konsensproblem in verteilten Systemen, bei dem mehrere Server dieselbe Entscheidung treffen müssen, leichter verständlich zu machen, und zielt auf eine mit Paxos vergleichbare Fehlertoleranz und Leistung ab
- Raft teilt die Struktur in Teilprobleme wie Leader-Wahl, Log-Replikation und Sicherheit auf und macht so die Entscheidungspunkte klar, die für die Implementierung einer replizierten Zustandsmaschine nötig sind
- Solange die Mehrheit der Server verfügbar ist, kann das System fortfahren; fällt die Mehrheit aus, stoppt es, ohne falsche Ergebnisse zu liefern, und wahrt so die Sicherheit
- Auf der Website sind der browserbasierte RaftScope, die Visualisierung The Secret Lives of Data, das Raft-Paper, die TLA+-Spezifikation sowie Papers und Vortragsmaterial zu Verifikation und Analyse gesammelt
- Implementierungen in vielen Sprachen wie Rust, Go, Java, C++, C#, Python usw. sind zusammengestellt; je nach Implementierung unterscheidet sich der Umfang der Unterstützung für Leader-Wahl und Log-Replikation, Persistenz, Membership-Änderungen und Log-Kompaktierung
Das von Raft adressierte Konsensproblem
- Raft wurde entworfen, damit ein breiteres Publikum Konsensalgorithmen leichter verstehen kann
- Fehlertoleranz und Leistung sollen auf dem Niveau von Paxos liegen
- Der zentrale Unterschied ist die Struktur
- Das Problem wird in relativ unabhängige Teilprobleme zerlegt
- Komponenten, die für die Implementierung realer Systeme nötig sind, werden getrennt behandelt
- Ziel ist es, konsensbasierte Systeme leichter verständlich zu machen und mit höherer Qualität implementieren zu können
Konsens und replizierte Zustandsmaschinen
- Konsens (consensus) ist ein Grundproblem fehlertoleranter verteilter Systeme
- Mehrere Server einigen sich auf einen Wert, und ein einmal entschiedener Wert wird zum endgültigen Zustand
- Allgemeine Konsensalgorithmen machen Fortschritt, wenn eine Mehrheit der Server verfügbar ist
- Ein Cluster mit 5 Servern kann weiterarbeiten, auch wenn 2 Server ausfallen
- Fallen mehr Server aus, kommt der Fortschritt zum Stillstand
- Auch dann ist wichtig, dass keine falschen Ergebnisse zurückgegeben werden
- Konsens wird meist verwendet, um replizierte Zustandsmaschinen zu bauen
- Jeder Server besitzt eine Zustandsmaschine und ein Log
- Die Zustandsmaschine kann etwa eine Komponente wie eine Hash-Tabelle sein, der Fehlertoleranz verliehen werden soll
- Clients können es so sehen, als würden sie mit einer einzigen zuverlässigen Zustandsmaschine interagieren, selbst wenn einige Server ausfallen
- Jede Zustandsmaschine erhält Befehle aus ihrem eigenen Log als Eingabe
- Im Beispiel mit der Hash-Tabelle würde ein Befehl wie
set x to 3im Log stehen - Der Konsensalgorithmus legt fest, welche Befehle in welcher Reihenfolge in die Server-Logs eingetragen werden
- Wenn eine Zustandsmaschine
set x to 3als n-ten Befehl angewendet hat, muss sichergestellt sein, dass keine andere Zustandsmaschine an derselben Position einen anderen Befehl anwendet
- Im Beispiel mit der Hash-Tabelle würde ein Befehl wie
- Dadurch verarbeiten am Ende alle Zustandsmaschinen dieselbe Befehlsfolge und gelangen zu derselben Folge von Ergebnissen und Zuständen
Visualisierungen zum Verständnis von Raft
- Eine im Browser laufende Visualisierung eines Raft-Clusters lässt sich direkt bedienen
- Links werden 5 Server angezeigt
- Rechts werden die Logs der einzelnen Server angezeigt
- Nutzer können durch Interaktion das Verhalten von Raft beobachten
- RaftScope hat noch einige Ecken und Kanten; Pull Requests sind willkommen
- The Secret Lives of Data ist eine weitere Visualisierung von Raft
- Sie ist stärker geführt und bietet weniger Interaktion
- Für Leser, die das Thema zum ersten Mal sehen, kann sie ein sanfterer Einstieg sein
Paper, Spezifikation und Verifikationsmaterial
- In Search of an Understandable Consensus Algorithm (Extended Version) ist das „Raft-Paper“, das Raft ausführlich behandelt
- Verfasst von Diego Ongaro und John Ousterhout
- Eine etwas kürzere Version erhielt auf der 2014 USENIX Annual Technical Conference den Best Paper Award
- Diego Ongaros Ph.D. dissertation erweitert den Inhalt des Papers deutlich
- Sie enthält einen einfacheren Algorithmus für Änderungen der Cluster-Membership
- Sie umfasst auch eine formale TLA+-Spezifikation von Raft
- Eine leicht aktualisierte Spezifikation ist unter raft.tla zu finden
- Zugehörige Papers behandeln die formale Verifikation von Raft, Frameworks zur Implementierung und Verifikation verteilter Systeme, Codegenerierung aus formalen Modellen und die Protokollanalyse
- 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
Vorträge und Lehrmaterialien
- Es gibt auch eine zusammengestellte Liste einführender Vorträge zu Raft
- John Ousterhouts Vortrag in der CS@Illinois Distinguished Lecture Series, August 2016
- Jin Lis Vortrag zu Raft und zur TLA+-Spezifikation in der Dr. TLA+ Series, Juli 2016
- Vorträge von Diego Ongaro auf Build Stuff 2015, CoreOS Fest 2015, einem Sourcegraph-Meetup, bei LinkedIn, USENIX ATC 2014, CraftConf 2014 und RICON West 2013
- Ben Johnsons Vortrag auf der Strange Loop 2013
- John Ousterhouts Vorlesung zur Raft User Study, März 2013
- Auch in Universitäten und Ausbildungskursen wird Raft für Vorlesungen oder Programmieraufgaben verwendet
- Enthalten sind mehrere Kurse von der University of Copenhagen, der Czech Technical University in Prague, The University of Hong Kong, der University of Virginia, UC San Diego, der Technical University of Munich, UIUC und weiteren
- Einige Kurse bieten Raft-Programmieraufgaben in Go, Java, Erlang usw. an
- MIT 6.824 enthält Vorlesungsnotizen zu Raft und verweist außerdem auf Raft-Texte von Jon Gjengset für Lehrende und Studierende
- Weitere Kurse können im Repository der Website per Pull Request oder Issue ergänzt werden
Fragekanal und Liste der Implementierungen
- Für Fragen zu Raft und seinen Implementierungen wird die raft-dev Google group als geeigneter Ort genannt
- Einige Implementierungen haben eigene Mailinglisten; daher sollte jeweils das README geprüft werden
- Es wird auch eine Liste von Raft-Implementierungen mit öffentlich verfügbarem Quellcode angeboten
- Beliebte oder kürzlich aktualisierte Implementierungen stehen weiter oben in der Tabelle
- Die Informationen können mit der Zeit veralten und lassen sich per Pull Request oder Issue aktualisieren
- Die Tabelle vergleicht pro Implementierung Stars, Name, Hauptautoren, Sprache, Lizenz und unterstützte Funktionen
- Zu den Funktionsspalten gehören Leader-Wahl und Log-Replikation, Persistenz, Membership-Änderungen und Log-Kompaktierung
- Beispiele aus dem oberen Teil der Liste sind:
- TiKV: Rust, Apache-2.0, 16.751★, unterstützt Leader-Wahl und Log-Replikation, Persistenz, Membership-Änderungen und Log-Kompaktierung vollständig
- RethinkDB: C++, Apache-2.0, 27.000★, unterstützt alle wichtigen Funktionen
- Seastar Raft: C++20, AGPL, 15.624★, unterstützt alle wichtigen Funktionen
- hashicorp/raft: Go, MPL-2.0, 9.048★, unterstützt alle wichtigen Funktionen
- hazelcast-raft: Java, Apache-2.0, 6.579★, unterstützt alle wichtigen Funktionen
- Die Liste enthält Implementierungen in vielen Sprachen, darunter Rust, Go, Java, C++, C, Erlang, Python, Scala, C#, JavaScript, Haskell, OCaml, Kotlin, Zig, TypeScript, Elixir, F#, Shell und weitere
1 Kommentare
Hacker-News-Kommentare
In Maelstrom, der Workbench des Jepsen-Autors zum Lernen verteilter Systeme, gibt es eine einfache modellgeprüfte Implementierung von Raft und ein gutes Tutorial zur Implementierung: https://github.com/jepsen-io/maelstrom/
Raft ist ein einfacher Algorithmus, aber das Original-Paper enthält viele Korrektheitsdetails, die in Toy-Implementierungen oft weggelassen werden.
Wenn man Speicher-/Plattenkorruption und Gray Failures realer Hardware, strenge Latenz-SLAs, flexible Quoren und dynamische Cluster-Mitgliedschaft berücksichtigt, wird eine Produktionsimplementierung zu einer langen und anspruchsvollen Aufgabe.
Schon ein Blick in die Commit-Historien von etcd und hashicorp/raft zeigt, dass selbst bei den am besten geprüften Open-Source-Raft-Implementierungen regelmäßig Korrektheitsbugs auftauchen.
Das TigerBeetle-Team behandelt ausführlich die Realität verteilter Systeme mit fehlerhafter Hardware und nicht abstrahierten Systemmodellen und erklärt auch, warum es Viewstamped Replication gewählt hat, das älter als Paxos ist, aber Raft ähnlicher wirkt: https://github.com/tigerbeetle/tigerbeetle/blob/main/docs/DE...
Ich weiß nicht genau, welche Folgen das für Implementierungsüberlegungen hat, aber das Paper selbst ist hervorragend und empfehlenswert.
Es gibt auch einen Vortrag, aber zum Vor- und Zurückblättern finde ich den Text besser: https://www.youtube.com/watch?v=0K6kt39wyH0
Obwohl ich noch nie zuvor einen Konsensalgorithmus gesehen hatte, konnte ich nach ein paar Durchgängen einigermaßen folgen: https://dspace.mit.edu/bitstream/handle/1721.1/71763/MIT-CSA...
Ich habe kürzlich Leader Election und Log-Replikation in Raft implementiert; bis zu Snapshots/Checkpoints bin ich nicht gekommen, aber es gehörte zu den schwierigsten Projekten, die ich bisher gemacht habe.
Das Raft-Paper ist angenehm zu lesen und vermittelt gute Intuitionen.
Selbst wenn man es nicht selbst implementiert, ist die Wahrscheinlichkeit groß, dass man bereits Raft-basierte Software wie etcd, Consul, CockroachDB oder TiDB nutzt.
Die Materialien, die mir bei der Implementierung geholfen haben, habe ich hier gesammelt: https://github.com/eatonphil/goraft#references
Enthalten sind auch Diego Ongaros Dissertation und die TLA+-Spezifikation.
Manche sagen: „Figure 2 aus dem Raft-Paper reicht aus“, aber verglichen mit der TLA+-Spezifikation ist sie viel mehrdeutiger, daher halte ich das nicht für richtig.
Ich empfehle, es mit den Raft-Tests aus der MIT-Vorlesung zu verteilten Systemen zu verknüpfen: https://pdos.csail.mit.edu/6.824/labs/lab-raft.html
Zumindest für Leader Election und Log-Replikation scheint das mit etwas Refactoring machbar zu sein.
Besonders für Leute, die erstmals mit verteilten Algorithmen in Berührung kommen, ist es wirklich empfehlenswert.
Die Implementierungsqualität ist sicher nicht überragend, aber für Interessierte habe ich sie hier hochgeladen: https://github.com/skowalak/fastapi-raft/
Im Paper stehen noch einige weitere konkrete Details, die man bei der Implementierung benötigt.
Wenn ihr euch für Konsensalgorithmen interessiert, ist auch das Buch Reasoning about Knowledge, das wir in einem Theoriekurs zu verteilten Systemen verwendet haben, einen Blick wert: https://mitpress.mit.edu/9780262562003/reasoning-about-knowl...
Man muss ein wenig investieren, um Modallogik zu lernen, aber wenn man darüber hinweg ist, werden die Beweise dafür, warum Raft oder Paxos funktionieren, sehr intuitiv und einfach.
Der Ansatz schiebt die Komplexität des Beweises in die logische Struktur, die für den Beweis verwendet wird, und hat meine Sicht auf Konsens verändert.
„Raft Consensus Algorithm Failure“, Théodore Géricault, 1819: https://classicprogrammerpaintings.com/post/6141087496359280...
Wenn du nicht verstehst, was die Visualisierung zeigt, hilft es zu wissen, dass du einen Knoten anklicken kannst, um einen Ausfall auszulösen.
Besonders interessant ist das beim aktuellen Leader, also dem Knoten, der alle Pakete sendet und empfängt.
Wenn du auf das kleine Pause-Symbol neben dem ersten Schieberegler klickst und es wieder zur Uhr machst, läuft die Simulation weiter.
Was die Tabellenansicht rechts sein soll, weiß ich noch nicht; sie ist immer leer und wirkt daher kaputt.
Die anklickbaren Elemente, die ich bisher gefunden habe, sind die zwei Schieberegler, das Uhr-/Pause-Symbol und die einzelnen Server.
Wenn du den Leader anklickst und
requestauswählst, kannst du das Senden eines Befehls simulieren.Wenn du ein Replikat offline nimmst, kannst du sehen, wie es zurückfällt und nach seiner Rückkehr wieder aufholt.
Vor ein paar Jahren war ich in einer Umgebung, in der ein unter schwerer Last robuster Chubby-ähnlicher Dienst immer geschäftskritisch war; damals nahm man ZooKeeper, wenn Ausfälle nicht tolerierbar waren.
Inzwischen haben Leute, soweit ich weiß, über Jahre sehr schwere Workloads auf Raft-basierte Optionen wie etcd und Consul gelegt.
Ich frage mich, ob eine davon inzwischen zur Standardwahl geworden ist.
Die konzeptionelle Klarheit und Eleganz von Raft scheint sich in Performance und Zuverlässigkeit niederschlagen zu können, aber mein Gefühl für diesen Bereich ist veraltet.
Ich frage mich, was Leute, die 2023 nicht an Google oder GCP gebunden sind, als Best Practice für hochkritische Systeme verwenden.
Ich meine, es gab eine produktionsreife Rust-Raft-Implementierung aus dem TikV-Umfeld, und ein robuster, performanter Lock-Server wirkt wie ein Bereich, der ziemlich gut zu Rust passt; ich frage mich auch, ob so etwas tatsächlich im Einsatz ist.
Wenn das die Antwort auf „Was ist Raft?“ ist, weiß ich es nach dem Lesen immer noch nicht.
„Raft ist ein Konsensalgorithmus, der auf Verständlichkeit ausgelegt ist. In Bezug auf Fehlertoleranz und Performance ist er Paxos gleichwertig. Der Unterschied besteht darin, dass er in relativ unabhängige Teilprobleme zerlegt ist und die wichtigsten für praktische Systeme nötigen Aspekte sauber behandelt. Wir hoffen, dass Raft Konsens einem breiteren Publikum zugänglich macht und dieses Publikum dadurch vielfältigere, hochwertige konsensbasierte Systeme bauen kann als heute.“
Das ist kein Problem nur dieser Leute, aber ich finde es schade, wenn man sich nicht mehr Zeit nimmt, die eigene Arbeit richtig zu erklären.
Denn sie filtert Leser, die die Bedeutung nicht kennen, automatisch aus.
Für jemanden, der verteilte Systeme baut und mehrere Konsensalgorithmen vergleicht, ist das eine einfache und klare Beschreibung; wenn nicht, ist der Algorithmus vermutlich ohnehin nicht relevant.
Allgemein versuchen Konsensalgorithmen das Problem zu lösen, dass es Replikate eines Datenspeichers auf mehreren physischen Geräten gibt und entschieden werden muss, was passiert, wenn einige Geräte oder Verbindungen auf irgendeine Weise ausfallen.
„Konsens“ heißt es, weil sich die Maschinen im Fehlerfall darauf einigen müssen, welche Entscheidung sie über ein Datenstück treffen.
Wenn zum Beispiel drei Server dieselbe SQL-Datenbank replizieren und in der Form
(A) - (B) - (C)angeordnet sind, können A und B, wenn die Netzwerkverbindung zwischen C und den anderen beiden ausfällt, das erkennen und B zum primären Knoten hochstufen.C weiß aber nicht, was passiert ist, und kann weiterhin einige Writes annehmen.
Wenn die Verbindung wiederhergestellt ist, müssen A, B und C entscheiden, was nun geschehen soll.
Da B und C unabhängig voneinander unterschiedliche Mengen von Writes angenommen haben, müssen sich die Server darauf einigen, wie mit den Daten umzugehen ist.
Genau dieses Problem versuchen Raft, Paxos und ähnliche Verfahren auf konsistente und performante Weise zu lösen.
Manche Konzepte sind zu groß, um sie jemandem ohne jedes Vorwissen in einem Absatz vorzustellen.
Trotzdem halte ich den verlinkten Artikel, wenn man weiterliest, für eine hervorragende Einführung.
Als Forscher im Bereich Konsensprotokolle finde ich, dass Konsens durch die Blockchain-Forschung der letzten zehn Jahre deutlich leichter verständlich geworden ist.
Raft liest sich und wird implementiert, insbesondere mit all seinen subtilen Details, im Vergleich dazu wie Griechisch.
Wenn heute jemand Konsensprotokolle neu lernt, würde ich ihn wohl bei Bitcoin anfangen lassen und dann zu Paxos, Tendermint und Simplex weitergehen; Raft würde ich ganz überspringen.
Simplex ist ein Paper von mir, eine vereinfachte Version von PBFT.
Raft wirkt vergleichsweise einfach.
Ich frage mich, was Blockchain bietet, das leichter zu warten und weniger fehleranfällig ist als „einen Leader wählen und ein Log replizieren“.
Ich mag diese Website.
Als wir in einem Kurs zu verteilten Systemen Raft gelernt und implementiert haben, war diese Seite wirklich nützlich.
Auch das Paper selbst ist ziemlich gut lesbar.
Danke, dass ihr Raft so klar verständlich gemacht habt.
Ich frage mich, ob es Konsensalgorithmen gibt, bei denen Änderungen nicht zwingend über den Leader laufen müssen.
In vielen verteilten Systemen möchte man auch die Eingabeverarbeitung verteilen.
Einer davon ist Chord: https://en.m.wikipedia.org/wiki/Chord_(peer-to-peer)
Chord ist ein P2P-Ring, in dem Nodes Werte per Consistent Hashing untereinander aufteilen.
Das Netzwerk nutzt eine sogenannte „finger table“, die im Kern Replikationsinformationen tabellarisch speichert.
Die Informationen in dieser Tabelle können falsch oder veraltet sein, und der angesprochene Peer kann einen an einen anderen Peer weiterverweisen, typischerweise an den nächsten Node oder einen Nachfolger, sodass man fortfährt, bis der Wert gefunden oder nicht gefunden wird.
Der Grund, warum dieser Algorithmus auch ohne „Leader“ verwendet werden kann, ist, dass er auch funktioniert, wenn man einfach zu einem Node geht und alle Nodes linear durchsucht.
Die finger table zur Beschleunigung von Abfragen ist nicht zwingend erforderlich.
Solche Systeme haben in der Regel pro Transaktion einen „Leader“, aber im Normalbetrieb ist diese Rolle nicht umkämpft.
Der Transaktionskoordinator erklärt sich selbst dazu; eine Wahl findet nur statt, wenn der Koordinator aus irgendeinem Grund ausfällt.
Für bestimmte Daten oder Keys können auch mehrere Leader gleichzeitig existieren.
Cassandra entwickelt derzeit Accord, ein leaderloses Protokoll aus dieser Familie.
Tatsächlich nutzt Cassandra bereits ein leaderloses Protokoll für LWT.
Es handelt sich um eine optimierte Variante des klassischen Single-Consensus-Paxos, allerdings mit erheblichem Overhead, wenn konkurrierende Transaktionen für denselben Key gleichzeitig deklariert werden.
Wenn Transaktionen über unabhängige Themenbereiche verteilt sind, kann man die Leader sharden und so die Last verteilen.
Dabei weist man Bereiche des Keyspace unterschiedlichen Leadern zu und koordiniert die Wahlen so, dass jeder Node einen passenden Anteil an Leadership erhält.
Ohne Leader kann man jeden Schreibvorgang faktisch wie eine eigene Wahl aufbauen.
Bei vorläufigen Transaktionen oder großen Transaktionen würde man die Transaktionsanfrage an alle Nodes broadcasten, und wenn man ein Annahme-Quorum erhält, gewinnt sie und wird committed.
Wenn jedoch mehrere Nodes nahezu gleichzeitig Transaktionen versuchen, kann der Konsens viel Zeit kosten.
Wenn es viele Nodes gibt und alle ausstehende Transaktionen zum selben Thema haben, ist es deutlich schneller, einen Leader zu wählen und alle Transaktionen über ihn zu schicken, als für jede Transaktion einen separaten Konsens aufzubauen.
Wenn das Ziel aber eine Verteilung zugunsten des Durchsatzes ist, kann ein Verfahren, das nur einen Leader benötigt, effizienter sein als das von Paxos geforderte Quorum.
Das ist allerdings nur eine Vermutung.
Auch Paxos ist effizienter, wenn Aufrufe jedes Mal an dieselbe Stelle gehen.
Denn dadurch lassen sich Konkurrenz und erneute Abstimmungen vermeiden.
Im Kern hat dabei jeder Shard seinen eigenen Paxos-Konsens.