Seite 2: Was der Algorithmus leisten muss

Inhaltsverzeichnis

Ob gemeinsame Datenbank oder System für verteiltes Rechnen, die Anforderungen an ein Verfahren, das die gemeinsame Wahrheit koordiniert, sind in beiden Fällen identisch: Gesucht wird ein Ansatz, der zu jeder Zeit sicherstellt, dass eine Anfrage nur mit der zuletzt geschriebenen Wahrheit beantwortet werden kann. Umgehen muss das System mit den Widrigkeiten, die in jedem verteilten System auftreten können. Verzögerungen im Netzwerk, Paketverluste auf dem Weg sowie doppelte oder vertauschte Netzwerkpakete gehören zum Alltag. Die verteilte Datenbank darf also nicht an Schluckauf im Netzwerk scheitern – bestenfalls muss man die einzelnen Server über Rechenzentren verteilen können, die über das Internet miteinander verbunden sind.

Außerdem sollte der Algorithmus sicherstellen, dass temporäre oder dauerhafte Ausfälle einzelner Cluster-Mitglieder nicht dazu führen, dass das Gesamtsystem keine Anfragen mehr bearbeiten kann oder gar falsche Ergebnisse liefert. Neustarts, Updates oder Stromausfälle kommen vor und müssen folgenlos bleiben. Wären solche Ausfälle ein Problem, hätte man lediglich die Komplexität skaliert, in Sachen Hochverfügbarkeit und Fehlertoleranz aber gar nichts gewonnen. Unschön wäre es auch, wenn alle Server bei jeder lesenden Anfrage all ihre Kollegen im Cluster nach der aktuellen Wahrheit fragen müssten – dann hätte man ein ziemlich lahmes System geplant.

Vertrauen und Verrat

Eine Bedingung versucht Raft ausdrücklich nicht zu erfüllen: den Umgang mit sogenannten byzantinischen Fehlern. So nennt die Forschung in Anlehnung an eine Anekdote mit Generälen aus Byzanz alle Probleme, die durch böswillige Cluster-Mitglieder ausgelöst werden – wenn ein Server im Cluster die anderen anlügt oder Nachrichten mutwillig zurückhält, könnte er die gemeinsame Wahrheit gefährden. Das ist aber in der Praxis kein Problem: Ein Cluster wird für gewöhnlich von einem Administrator aufgesetzt und alle Server werden mit derselben Software ausgestattet.

Eine technische Lösung für byzantinische Umgebungen gibt es abseits von Raft: Blockchains. Auch wenn die Bedingungen in den allermeisten Unternehmensnetzwerken nicht-byzantinisch sind, ist die fixe Idee von Blockchains im Unternehmen bis heute präsent, weil findige Verkäufer erkannt haben, dass Software mit Blockchain interessanter und attraktiver wirkt als Software mit einem vergleichsweise langweiligen Konsens-Algorithmus.

Auftritt von Raft

Erfunden und veröffentlicht haben den Raft-Algorithmus Diego Ongaro und John Ousterhout von der Stanford-University im Jahr 2014. Bemerkenswert ist ihre Herangehensweise, die sie in ihrem wissenschaftlichen Paper "In Search of an Understandable Consensus Algorithm" beschreiben. Schon im Titel taucht die Verständlichkeit als Ziel erstmals auf – und das Thema zieht sich durch den gesamten Artikel. Die zentrale Überzeugung der Autoren bestand darin, dass ein guter Konsens-Algorithmus leicht zu erklären sein muss. Nur dann könne man ihn auch gut und stabil implementieren, verteilte Systeme anständig warten und bei Problemen reagieren. Verständlichkeit soll also Entwicklern und Admins von Raft-Systemen gleichermaßen helfen.

Zu dieser Erkenntnis kamen die beiden Forscher durch schlechte Erfahrungen mit dem damals dominierenden Konsensverfahren namens Paxos oder genauer Multi-Paxos. Das sei, so die Autoren, so vertrackt, dass sie nach zahlreichen Interviews niemanden finden konnten, der Multi-Paxos vollständig und richtig erklären konnte. Die meisten Erklärungsansätze bezögen sich auf den Unterbau Single-Decree-Paxos, der allein schon nicht intuitiv zu verstehen sei – Multi-Paxos legt noch Komplexitätsstufen obendrauf. Kurzum: 2014 war der Stand der Technik ein undurchdringliches Konstrukt, das zu allem Überfluss auch noch immer etwas anders implementiert wurde, gern auch in proprietärer Software ohne öffentlichen Quellcode. Und nicht überall, wo Paxos draufstand, war auch die reine akademische Paxos-Lehre drin.

Anstatt an Paxos herumzudoktern und es zu entschlacken, wie es andere Forscher zuvor versucht hatten, entschieden sich Ongaro und Ousterhout für einen radikalen Neuanfang mit erfrischend wenigen Komponenten. In einem Raft-Cluster kann jeder Server nur einen von drei Zuständen einnehmen: Anführer (Leader), Untertan (Follower) oder Kandidat (Candidate). Im Normalzustand sind diese Rollen klar aufgeteilt: Es gibt immer nur einen Leader, alle anderen Server sind Follower und es gibt keine Candidates. In diesem Zustand arbeitet ein Cluster die meiste Zeit des Tages und kann Lese- und Schreibaufgaben von Clients entgegennehmen.

Wie ein Raft-Cluster arbeitet

Um in diesen Grundzustand zu kommen, ist kein menschliches Eingreifen nötig – beim Einrichten eines Raft-Clusters startet der Administrator einfach mehrere absolut gleichwertige Maschinen und übergibt jeder Maschine eine Liste an Adressen aller anderen Mitspieler. Die wichtigste Bedingung fürs Gelingen: Die Server müssen in einem Netzwerk stecken und einander darüber erreichen, außerdem sollten sie alle dieselbe Uhrzeit haben. Im Original-Paper kommunizieren die Systeme über Remote-Procedure-Calls (RPC), theoretisch könnte man Raft aber auch mit jedem anderen Mechanismus implementieren.

Beim Start erklärt sich jeder Server zunächst zum Follower und wartet auf Anweisungen eines Leaders, genauer auf das sogenannte Heartbeat-Signal, das nur Leader abgeben – das würde aber ewig dauern, weil ein frischer Cluster anfangs führungslos ist. Damit jetzt nicht alle Server dauerhaft warten, erzeugt jeder Server beim Start eine zufällige Wartezeit (Election Timeout genannt), die innerhalb einer in der Implementierung festgelegten Zeitspanne liegt (die Autoren schlagen zwischen 150 und 300 Millisekunden vor). Jedes Mitglied ist also – per Zufall festgelegt – unterschiedlich geduldig.

Wahlverfahren

Derjenige Server, dem zuerst der Geduldsfaden reißt, eröffnet eine neue Wahl, wechselt in die Rolle Candidate und stimmt selbstbewusst schon mal für sich selbst. Dann erhöht er in seinem Speicher die Nummer der Wahlperiode (die sogenannte Term) und sendet allen anderen Cluster-Mitgliedern eine Wahlbenachrichtigung (mit einem RPC vom Typ RequestVote). Einen Wahlkampf gibt es nicht – alle anderen Server, die gerade führungslos vor sich hin warten, nehmen das Angebot dankend an und stimmen umgehend für den ersten Kollegen, der eine Wahl ausgerufen hat, indem sie ihm mit Zustimmung antworten.

Sobald der Candidate die Mehrheit der möglichen Stimmen als Antwort erhalten hat, ernennt er sich zum Leader und beginnt mit seinen Amtsgeschäften: Er versendet Heartbeat-Nachrichten per RPC, alle anderen Server erkennen ihn schlagartig als Leader an und wechseln in den Follower-Zustand. Sollten andere Server durch unglücklichen Zufall parallel eine Wahl angezettelt haben, brechen sie diese bei Erhalt einer Heartbeat-Nachricht sofort ab und folgen ab sofort dem Leader.

Jetzt ist der Cluster bereit, Anfragen von Clients entgegenzunehmen. Beantworten wird solche Anfragen immer nur der Leader, ein unbedarfter Client kennt den aber nicht und beginnt deshalb immer damit, einen zufällig ausgewählten Server zu fragen – der Client braucht also eine Liste aller Server im Cluster. Ist der befragte Server aktuell nicht Leader, muss er die Adresse seines Leaders verraten. Die kann sich der Client erst mal merken und dort künftig nachfragen. Sollte der befragte Server aktuell vom Rest des Clusters getrennt sein, muss der Client sich einen anderen Server zufällig aussuchen und dort anklopfen.

Anführer und Untertanen

Hat der Client den Leader gefunden, darf er ihn befragen. Noch ist der frische Cluster aber leer, es gibt also nicht viel zu erfahren. Als einfaches Beispiel soll das System eine einzige Zahl verwalten – angenommen, es handelt sich um eine Art Kontostand. In diesem fiktiven System kommt nach erfolgreicher Wahl der erste schreibende Befehl beim Leader an: Die Zahl soll auf 100 geändert werden. In einem Raft-System führt jeder Server zwei Datenstrukturen, einmal ein Log, das alle Schreibbefehle enthält, außerdem die State-Machine, die immer die aktuelle Wahrheit verwaltet.

Zunächst schreibt der Leader den eingegangenen Änderungsbefehl in sein Log, dann schickt er einen RPC vom Typ AppendEntries parallel an alle Follower. Die schreiben die Änderung ebenfalls in ihr Log und bestätigen dem Leader den Empfang. Hat dieser Bestätigungen von mehr als der Hälfte der Server, betrachtet er den Befehl als committed, führt den Änderungswunsch (erhöhe die Zahl auf 100) in seiner State-Machine aus und schickt dem Client die Antwort: Neuer Wert ist 100. Erst dann sagt er allen Followern Bescheid, dass die Änderung committed ist und auch sie die Änderung in ihren State-Machines ausführen können. Mit diesem einfachen Abgleich ist schon einmal sichergestellt, dass die State-Machines aller Server meistens denselben Wert enthalten.