Wie verteilte Systeme dank Raft-Algorithmus zusammenarbeiten
Seite 3: Umgang mit Problemen
Im Kern ist das auch schon das Geheimnis von Raft. In einer perfekten Welt könnte das System für immer so weiterarbeiten – spannend wird es erst, weil die Welt eben nicht perfekt ist und allerhand schiefgehen kann. Das gefühlt schwerste Problem ist in einem Raft-Cluster am schnellsten gelöst: der Ausfall eines Leaders. Angenommen, der Admin schaltet den Server für ein Update aus. Die Follower werden diesen Zustand schnell bemerken, weil die regelmäßigen Heartbeat-Nachrichten ausbleiben. Wie schon beim Einrichten des Clusters wird einem Server zuerst der Geduldsfaden reißen und er wird eine Wahl veranstalten. Dafür macht er sich wieder zum Candidate und eröffnet eine neue Term – ob diese Wahl erfolgreich sein kann, ist abhängig von der Größe des Clusters.
Ein typischer Raft-Cluster besteht aus drei oder fünf Servern. Wichtig für das Verständnis: Alle Server haben eine Liste mit allen Beteiligten, kennen also auch die Gesamtgröße des Clusters und wissen somit, wo die Grenze für eine Mehrheit bei Wahlen liegt. In einer Umgebung mit drei Servern ist es kein Problem, wenn mal einer ausfällt, selbst wenn es der Leader ist. Einer der anderen stellt sich zur Wahl, der andere stimmt für ihn und die Wahl endet mit zwei von drei Stimmen, also einer Mehrheit.
Zwei Server gleichzeitig dürfen aber nicht ausfallen, dann könnte der verbliebene keine Mehrheit mehr erzielen. Wirkungslos ist es, einen Dreier-Cluster auf vier Mitglieder zu verstärken. Für eine absolute Mehrheit bräuchten die Server in dem Fall drei Stimmen, es darf also wie im Dreier-Cluster nur einer ausfallen. Aus diesem Grund empfehlen alle Dokumentationen von auf Raft basierender Software ungerade Clustergrößen. Bei fünf Mitspielern dürfen schon zwei gleichzeitig ausfallen, die verbliebenen drei können problemlos wählen. Von Clustern mit mehr als sieben Servern raten Raft-Experten eher ab – dann wird das System nur noch träger und nicht mehr stabiler.
Fehlende Untertanen
Aus einem Zustand ohne Leader kann sich der Cluster in wenigen Millisekunden selbst befreien und mit neuem Leader weiter Clients bedienen. Doch wie sieht es mit dem Ausfall eines Followers aus? Steigt ein solcher aus, fällt das dem Leader spätestens beim nächsten Schreibbefehl auf – und dafür muss man nicht einmal auf einen schreibenden Client warten, denn technisch sind die Heartbeat-Nachrichten auch nur Schreibbefehle (AppendEntries
) ohne Inhalt.
Der Leader wird also sehr bald versuchen, eine Bestätigung für eine AppendEntries
-Nachricht zu erhalten. Bleibt diese aus, wird er es immer wieder versuchen – ein anfragender Client muss auf diese Zeremonie aber nicht warten, er bekommt seine Antwort, sobald die Hälfte der Follower geantwortet hat. Ist ein Follower also mal wegen Netzwerkstörungen oder Neustart ein paar Minuten weg, wird er am Ende eine Liste an Änderungsaufträgen bekommen und diese der Reihe nach abarbeiten. Damit es dabei kein Durcheinander gibt, sind alle Schreibaufträge an die Follower nummeriert und enthalten auch immer die Nummer des zuletzt als committed markierten Auftrags sowie die Nummer der Wahlperiode.
Bevor ein Follower seinem Leader eine Bestätigung schickt, prüft er, ob er die vorangegangene Nachricht erhalten hat. Durch diese Prüfung und die Bestätigung kann jeder Leader eine Liste führen, auf welchem Stand seine Follower sind. Kommt es durch Widrigkeiten des Netzes mal zu einer Abweichung, greift der Leader ein: Er schaut in seiner Liste, bis zu welcher Nachricht der Follower den richtigen Stand kennt, befiehlt dann die Löschung aller späteren Log-Einträge und schickt ihm die Änderungen noch einmal in richtiger Reihenfolge. Sobald er für den letzten Eintrag eine Bestätigung hat, ist der Follower wieder auf Kurs.
Zusätzliche Regeln
Für den Fall von Neuwahlen haben sich die Raft-Autoren einen weiteren Schutzmechanismus einfallen lassen: Bisher hatte jeder Kandidat, der eine Neuwahl ausgerufen hat, die Stimmen seiner Kollegen sicher. Doch eine Einschränkung (die Leader-Completeness-Property) ist nötig, damit nur ein Server zum Leader wird, der den zuletzt als committed bekannten Stand kennt. Dafür schickt jeder Kandidat im Rahmen der RequestVote
-Nachricht die fortlaufende Nummer und die Term-Nummer seines letzten Log-Eintrags mit. Die anderen würden ihm die Stimme verwehren, wenn sie selbst einen Eintrag mit höherer Nummer hätten.
Zwei wesentliche Komponenten von Raft, die Wahl des Leaders und auch das Commit von neuen Log-Einträgen, funktionieren nur mit einer Mehrheit. So verhindert Raft einen Zustand, der in anderen Konsens-Algorithmen durchaus möglich und bei Administratoren gefürchtet ist: das Split-Brain-Szenario, bei dem ein Cluster in zwei Teile zerfällt (zum Beispiel durch eine fehlende Netzwerkverbindung) und in dem beide Teile von sich behaupten, die Wahrheit zu verwalten.
»Durch konsequente Mehrheitswahlen verhindert Raft das bei Clustern gefürchtete Split-Brain-Szenario.«
Beitritte und Austritte
Die letzte große Baustelle, mit der sich die Raft-Autoren befasst haben, ist die Mitgliederverwaltung: Unpraktikabel wäre es, einen Cluster bei Änderungen herunterzufahren und mit neuer Mitgliederliste wieder zu starten – Server soll man im laufenden Betrieb hinzufügen und entfernen können. Um das zu gewährleisten, haben sich Ongaro und Ousterhout dazu entschieden, auch die Mitgliederverwaltung wie die Nutzdaten zu behandeln und mit den Raft-Mechanismen zu replizieren. Sobald eine Änderung der Konfiguration (Hinzufügen oder Entfernen eines Mitglieds) verbreitet ist, beginnen alle Follower damit zu arbeiten.
Für neue Server gibt es aber noch eine sinnvolle Ausnahmeregelung: Sie können in den ersten Minuten noch nicht sinnvoll am Cluster mitwirken, weil sie mit einer komplett leeren State-Machine und leerem Log einsteigen und zunächst vom Leader mit alten Logs bombardiert werden. In dieser Phase sind sie weder aktiv noch passiv wahlberechtigt und dürfen in Ruhe die Daten verarbeiten. Sobald sie den letzten Log-Eintrag verarbeitet haben, steigen sie als wahlberechtigtes Vollmitglied ein.
Log-Bereinigung
Mit diesen überschaubaren Komponenten erfüllt Raft bereits alle Anforderungen in Bezug auf Stabilität und gemeinsame Wahrheit – ein nicht nur kosmetisches Problem bleibt aber: Die Liste an Log-Einträgen wird länger und länger und verbraucht immer mehr Speicherplatz. Zur Verwaltung einer einzigen Zahl in der State-Machine können nach wochenlangem Betrieb gigabyteweise Logs anfallen, zusätzlich aufgebläht mit Milliarden leerer Heartbeat-Nachrichten.
Damit Raft praktikabel bleibt, haben die Autoren Snapshots erfunden, die regelmäßig (abhängig von der Implementierung) angefertigt werden. Ein Snapshot fügt alte Logeinträge zusammen, und anstatt Tausende Änderungswünsche mitzuschleppen, bleibt ein Befehl übrig, der nur das letzte Ergebnis enthält. Die komprimierten Logs werden entsorgt. Die Snapshots entlasten nicht nur die Festplatte, sie machen auch neuen Servern den Einstieg leichter – die bekommen Snapshots vom Leader und sind somit schneller einsatzbereit.