Raft-Konsens erklärt: Leader-Wahl und Log-Replikation

Jeder Kubernetes-Cluster speichert seinen Zustand in etcd, und etcd einigt sich über diesen Zustand mit Raft. Genauso Consul, CockroachDB, TiKV, die Quorum Queues von RabbitMQ und, seit Kafka 4.0 ZooKeeper entfernt hat, Kafkas eigene Controller. Wenn du eines davon betreibst, erklärt Raft Verhalten, das sonst willkürlich wirkt: warum ein Cluster mit drei Knoten keine Schreibzugriffe mehr annimmt, wenn zwei Knoten ausfallen, warum Schreibzugriffe bei einem Leader-Wechsel eine Sekunde pausieren und warum ein vierter Knoten einen Cluster teurer macht, ohne ihn sicherer zu machen.

Dieser Beitrag erklärt Raft mit einem Diagramm der Log-Replikation in einem Cluster mit fünf Knoten: Terms, Leader-Wahl, AppendEntries, die Commit-Regel, Fehlerfälle, Clustergröße, Lesezugriffe und Mitgliedschaftsänderungen.

Das Modell: ein repliziertes Log

Raft baut eine replizierte Zustandsmaschine. Jeder Server führt ein Log von Befehlen. Wenden alle Server dieselben Befehle in derselben Reihenfolge an, landen sie im selben Zustand. Rafts Aufgabe ist es, die Logs identisch zu halten, auch wenn Server abstürzen und Nachrichten verloren gehen oder sich verzögern.

Jeder Server ist in einem von drei Zuständen: Follower, Kandidat oder Leader. Die Zeit ist in Terms eingeteilt, nummeriert mit 1, 2, 3 und so weiter; jeder Term beginnt mit einer Wahl und hat höchstens einen Leader. Ein Server, der einen höheren Term als seinen eigenen sieht, übernimmt diesen Term und wird Follower, sodass ein veralteter Leader zurücktritt, sobald er vom neueren hört.

Raft braucht nur zwei RPCs, plus einen für Snapshots:

Das Design stammt aus dem Paper In Search of an Understandable Consensus Algorithm von Diego Ongaro und John Ousterhout, veröffentlicht auf der USENIX ATC 2014.

Leader-Wahl

Ein Follower erwartet regelmäßige Heartbeats vom Leader. Kommt innerhalb seines Election Timeouts keiner an, nimmt er an, dass der Leader weg ist:

1. Er erhöht seinen Term, wird Kandidat und stimmt für sich selbst.
2. Er schickt RequestVote an alle anderen Server, mit Index und Term seines letzten Log-Eintrags.
3. Jeder Server vergibt höchstens eine Stimme pro Term, und nur an einen Kandidaten, dessen Log mindestens so aktuell ist wie das eigene: Ein höherer letzter Term gewinnt, bei gleichem Term gewinnt das längere Log.
4. Ein Kandidat, der Stimmen von einer Mehrheit sammelt, wird Leader und beginnt, Heartbeats zu schicken.

Teilen sich zwei Kandidaten die Stimmen, gewinnt niemand, und der Term endet ohne Leader. Raft macht das selten, indem es die Timeouts zufällig wählt; das Paper schlägt Werte wie 150 bis 300 ms vor, sodass meist ein Server zuerst in den Timeout läuft und gewinnt, bevor andere starten.

Produktionssysteme wählen Timeouts passend zu ihrem Netzwerk. etcd nutzt standardmäßig einen Heartbeat von 100 ms und einen Election Timeout von 1.000 ms, und laut seiner Dokumentation sollte der Election Timeout mindestens das Zehnfache der Round Trip Time zwischen den Mitgliedern betragen. Diese Zahlen sind der Grund, warum eine Kubernetes-Control-Plane nach dem Verlust ihres etcd-Leaders eine Sekunde oder länger brauchen kann, bis sie wieder Schreibzugriffe annimmt.

Log-Replikation

Nach der Wahl verarbeitet der Leader jeden Schreibzugriff:

1. Ein Client schickt dem Leader einen Befehl, zum Beispiel SET x=5.
2. Der Leader hängt ihn als neuen Eintrag mit dem aktuellen Term an sein eigenes Log an, etwa Index 7 in Term 3.
3. Der Leader schickt jedem Follower AppendEntries mit dem neuen Eintrag sowie Index und Term des Eintrags direkt davor (Index 6, Term 3).
4. Ein Follower akzeptiert nur, wenn sein Log an Index 6 einen Eintrag mit Term 3 hat. Diese Konsistenzprüfung garantiert: Stimmen zwei Logs an einer Position überein, stimmen sie auch in allem davor überein.
5. Wenn eine Mehrheit der Server, den Leader eingeschlossen, den Eintrag speichert, markiert der Leader ihn als committed, wendet ihn auf seine Zustandsmaschine an und antwortet dem Client.
6. Follower erfahren den neuen Commit-Index aus dem nächsten AppendEntries und wenden den Eintrag ebenfalls an.

Lehnt ein Follower einen Eintrag ab, weil sein Log abweicht, geht der Leader Index für Index zurück, mit Optimierungen schneller, bis die Logs übereinstimmen, und überschreibt dann die widersprüchlichen Einträge des Followers mit seinen eigenen. Überschrieben werden nur nicht committete Einträge, was sicher ist, weil niemandem gesagt wurde, dass sie erfolgreich waren.

Die Commit-Regel und das knifflige Detail

„Committed, sobald eine Mehrheit ihn speichert“ hat eine Ausnahme, und sie ist das berühmteste Detail des Papers. Ein neuer Leader darf nicht Repliken zählen, um Einträge aus früheren Terms zu committen. Er committet sie indirekt, indem er einen Eintrag aus seinem eigenen Term darauf committet. Ohne diese Regel könnte ein Eintrag, der auf einer Mehrheit gespeichert ist, trotzdem von einem späteren Leader überschrieben werden. In der Praxis hängt ein neuer Leader zu Beginn seines Terms einen leeren No-op-Eintrag an, um alles davor schnell zu committen.

Die Wahlbeschränkung vervollständigt das Sicherheitsargument: Weil ein Kandidat Stimmen einer Mehrheit braucht und jeder committete Eintrag auf einer Mehrheit liegt, hat jeder mögliche Gewinner bereits jeden committeten Eintrag.

Was ein Cluster übersteht

Ein Cluster aus n Servern braucht eine Mehrheit, um einen Leader zu wählen und Schreibzugriffe zu committen, also toleriert er den Ausfall von weniger als der Hälfte:

Vier Server tolerieren wie drei einen Ausfall, aber jeder Schreibzugriff wartet jetzt auf drei Bestätigungen statt auf zwei. Deshalb haben Cluster ungerade Größen. Fünf ist die übliche Wahl, wenn du einen Ausfall überstehen willst, während ein anderer Knoten in geplanter Wartung ist.

Die Latenz folgt derselben Rechnung. Jeder Schreibzugriff wartet darauf, dass der Leader die schnellste Mehrheit erreicht und diese Server den Eintrag auf die Platte schreiben. In einem Cluster über drei Regionen kostet jeder Schreibzugriff mindestens einen Round Trip in die nächstgelegene andere Region. Langsame Platten schaden genauso wie langsame Netze, weshalb die etcd-Dokumentation der fsync-Latenz genauso viel Raum gibt wie den Timeouts.

Fehlerfälle in der Praxis

• Der Leader stürzt ab. Follower laufen in den Timeout, einer gewinnt eine Wahl, und die Schreibzugriffe gehen weiter. Requests, die gerade unterwegs waren, sind vielleicht committed, vielleicht nicht, also müssen Clients es erneut versuchen, und die Befehle, die sie wiederholen, sollten idempotent sein.
• Eine Netzwerkpartition. Die Seite mit der Mehrheit wählt einen Leader und macht weiter. Ein alter Leader auf der Minderheitsseite kann nichts committen; sobald die Partition heilt, sieht er den höheren Term und tritt zurück.
• Ein langsamer Follower. Commits warten nicht auf ihn. Fällt er weit zurück, schickt der Leader einen Snapshot, statt das ganze Log erneut abzuspielen.
• Ein störender Server. Ein vom Leader abgeschnittener Server läuft immer wieder in den Timeout und erhöht seinen Term, was nach seiner Rückkehr unnötige Wahlen erzwingen kann. Pre-Vote aus Ongaros Dissertation lässt einen Kandidaten prüfen, ob er gewinnen könnte, bevor er seinen Term erhöht.

Lesezugriffe sind nicht umsonst

Ein Leader kann Lesezugriffe nicht blind aus seinem eigenen Zustand beantworten: Auf der anderen Seite einer Partition könnte ein neuer Leader gewählt worden sein, und der alte würde veraltete Daten liefern. Linearisierbare Lesezugriffe brauchen entweder eine Runde Heartbeats, um die Führung vor der Antwort zu bestätigen (Rafts ReadIndex), oder einen zeitbasierten Leader-Lease, der von begrenzter Uhrenabweichung abhängt. Auch Follower können Lesezugriffe bedienen, aber nur nach Prüfung des Commit-Index des Leaders oder unter Inkaufnahme veralteter Ergebnisse. etcd macht das explizit: etcdctl get ist standardmäßig linearisierbar, und --consistency=s verlangt einen schnelleren, möglicherweise veralteten serialisierbaren Lesezugriff.

Mitgliedschaft ändern

Server hinzuzufügen oder zu entfernen ändert, was eine Mehrheit ist, und ein unvorsichtiger Wechsel der Konfiguration kann zwei Mehrheiten gleichzeitig erzeugen. Raft löst das mit Joint Consensus oder indem immer nur ein Server auf einmal geändert wird. Viele Implementierungen fügen neue Server außerdem als nicht stimmberechtigte Learner hinzu, wie etcd, damit ein frischer Knoten das Log aufholt, bevor er zur Mehrheit zählt.

Das Diagramm der Log-Replikation

So liest du es:

• Der Client schickt einen Befehl an den Leader S1 in Term 3. Der Leader schreibt ihn an Index 7.
• Jede Tabelle ist das Log eines Servers: Index, Term und Befehl. Übereinstimmende Zeilen über Tabellen hinweg sind derselbe Eintrag.
• AppendEntries-Kanten gehen vom Leader zu den vier Followern. S2 und S3 bestätigen Index 7.
• S4 hinkt hinterher bei Index 6, und S5 ist nicht erreichbar bei Index 5. Keiner von beiden blockiert den Commit.
• Die Notiz zeigt die Commit-Regel: Drei von fünf Servern speichern Eintrag 7, also ist er committed und der Client bekommt seine Antwort.

Konsensdiagramme zeichnen, die etwas beibringen

• Zeig die Logs, nicht nur die Server. Rafts Garantien sind Aussagen über Logs. Ein Diagramm mit fünf Kästen und Pfeilen versteckt alles Interessante.
• Schreib den Term neben jeden Eintrag. Terms erklären Wahlen, Konflikte und die Commit-Regel.
• Zeichne einen ungesunden Cluster. Ein hinterherhinkender oder abgetrennter Follower zeigt besser als ein perfekter Cluster, warum Mehrheiten wichtig sind.
• Nutze ein Diagramm pro Szenario: Eine Wahl, normale Replikation und eine Konfliktreparatur nach einem Failover verdienen jeweils ein eigenes Bild.

Wie Replikation allgemein in Datenbankarchitekturen passt, zeigt das Datenbank-Replikationsdiagramm. Das Kubernetes-Architekturdiagramm zeigt, wo etcd in einer Control Plane sitzt, und das Kafka-Architekturdiagramm behandelt KRaft-Controller. Systeme wie CockroachDB betreiben eine Raft-Gruppe pro Datenbereich, was Konsens mit den Ideen im Datenbank-Sharding-Diagramm verbindet.

In Archboard nachbauen

1. Melde dich mit Google oder GitHub an und leg ein Diagramm an.
2. Füge einen Rahmen aus dem Basis-Pack für den Cluster hinzu und beschrifte ihn mit dem aktuellen Term.
3. Füge darin fünf Tabelle-Nodes aus dem Basis-Pack hinzu, eine pro Server, mit Spalten für Index, Term und Befehl. Setz den Leader in die Mitte.
4. Füge außerhalb des Rahmens einen Kasten aus dem Basis-Pack für den Client hinzu und verbinde ihn mit dem Befehl mit dem Leader.
5. Zeichne AppendEntries-Kanten vom Leader zu jedem Follower, mit gestrichelten Bestätigungskanten zurück von den Followern, die den Eintrag gespeichert haben. Markiere den nicht erreichbaren Follower mit einer gestrichelten Kante in einer Warnfarbe.
6. Füge einen Markdown-Block aus dem Basis-Pack mit der Commit-Regel hinzu und neben dem Leader eine Notiz mit dem Commit-Index.

Das Beispiel nutzt 8 Diagramm-Nodes und bleibt damit im Free-Plan.

FAQ

Warum haben Raft-Cluster eine ungerade Zahl von Knoten? Ein Cluster braucht eine Mehrheit, um zu funktionieren. Einen vierten Knoten zu dreien hinzuzufügen, hebt die Mehrheit von zwei auf drei, ohne mehr Ausfälle zu tolerieren; gerade Größen kosten also Latenz und Geld, ohne Fehlertoleranz zu bringen.

Was passiert mit Schreibzugriffen während einer Leader-Wahl? Sie warten oder scheitern, bis ein neuer Leader gewählt ist, typischerweise innerhalb von ein oder zwei Election Timeouts. Clients sollten mit idempotenten Requests erneut versuchen, weil ein Schreibzugriff, der in einen Timeout lief, committed sein könnte.

Was ist der Unterschied zwischen Raft und Paxos? Beide lösen dasselbe Problem mit ähnlichen Garantien. Raft wurde so entworfen, dass es leichter zu verstehen und zu implementieren ist: Es nutzt einen starken Leader, trennt Wahl und Replikation und spezifiziert Mitgliedschaftsänderungen.

Können Follower in Raft Lesezugriffe bedienen? Ja, wenn sie zuerst den Commit-Index des Leaders bestätigen oder wenn die Anwendung möglicherweise veraltete Daten akzeptiert. Den lokalen Zustand eines Followers ohne Prüfung zu lesen, kann alte Werte liefern.

Schützt Raft vor bösartigen Knoten? Nein. Raft toleriert Abstürze, Neustarts und verlorene oder verzögerte Nachrichten, setzt aber voraus, dass die Server dem Protokoll folgen. Byzantinische Fehlertoleranz braucht andere Algorithmen und mehr Repliken.

Kostenlos starten — ein Seat, keine Kreditkarte.