Wie verteilte Systeme dank Raft-Algorithmus zusammenarbeiten
Computer in einem Cluster brauchen stets eine gemeinsame Wahrheit. Der Raft-Consensus-Algorithmus funktioniert mit Mehrheitswahlen und vermeidet so Konflikte.
(Bild: Michael Vogt)
- Jan Mahn
- Verteilte Systeme können ihre Arbeit nur dann zuverlässig erledigen, wenn sich alle Server jederzeit auf eine gemeinsame Wahrheit einigen können.
- Der Raft-Consensus-Algorithmus stellt Konsens unter Maschinen her, die ihren Anführer demokratisch selbst wählen.
- Server im Cluster können ausfallen, im Netzwerk können Pakete verloren gehen – Raft ist auf solche Probleme vorbereitet.
Wenn Menschen in einer Gruppe zusammenarbeiten sollen, wird es gern mal anstrengend – und es fallen die typischen Sätze, die in jedem Büro zum Alltag gehören: "Das hatte ich doch rumgeschickt!", "Du hast noch die alte Version, die neue liegt doch im Ordner!" und "Ach, da warst du im Urlaub, als wir das geändert haben." All diese Symptome gehören zu einem großen Problem: Wie stellt man sicher, dass sich alle Mitglieder eines Teams eine gemeinsame Wahrheit, also einen Datenstand als Arbeitsgrundlage teilen?
Säule des Internets
Dieses Problem ist nicht uns Menschen vorbehalten; auch für Computer ist es keine triviale Aufgabe, reibungslos im Team zu arbeiten und sich auf eine gemeinsame Wahrheit zu einigen. Dabei haben es Computer untereinander doch vergleichsweise leicht: Sie funktionieren deterministisch, bringen unter identischen Bedingungen also identische Ergebnisse hervor. Auch kennen sie keine Emotionen und menschliche Schwächen wie Neid, Missgunst und krankhaften Ehrgeiz. Einer emotionsfreien Maschine fiele es nicht ein, sich vorzudrängeln oder in fremde Arbeitsbereiche einzumischen.
Es könnte daher so einfach sein, einen Algorithmus zu entwickeln, der eine gemeinsame Wahrheit unter Computern herstellt – und doch hat es Jahrzehnte gedauert, bis sich ein Verfahren durchsetzte, das funktional, robust und leicht zu implementieren ist: der Raft-Konsens-Algorithmus, der heute in vielen verteilten Systemen steckt. Dieser unscheinbare Algorithmus ist zu einer wichtigen Säule des Internets geworden: Die Schlüssel-Werte-Datenbank etcd zum Beispiel arbeitet mit Raft und ist selbst das Fundament für den Container-Orchestrator Kubernetes – und auf dieser Säule wiederum stehen viele große und sehr große Anwendungen. Ohne Raft gäbe es Spotify, Netflix oder Zalando nicht in dieser Form.
Warum ein Konsens-Algorithmus?
Solange ein Computer allein arbeitet, ist alles einfach: Er nimmt Anfragen oder Aufgaben entgegen, beschafft sich die nötigen Daten aus seinem Datenspeicher, nutzt sie für die Bearbeitung und gibt ein Ergebnis zurück. Ein alleinstehender SQL-Datenbankserver zum Beispiel kann lesende und schreibende Anfragen gleichermaßen schnell beantworten und muss sich mit niemandem absprechen. Was er wissen muss, liegt auf seiner Festplatte oder für häufige Fragen im Arbeitsspeicher. Doch ein einzelner Datenbankserver als Rückgrat einer Anwendung hat auch seine Schwächen. Fällt er aus, geht nichts mehr. Und bei höheren Lese- und Schreiblasten bleibt dem Admin nur, immer mehr Hardware in den Einzelgänger zu stecken.
Da wäre es doch schön, wenn man die Daten einem Verbund aus Datenbankservern anvertrauen könnte. Dafür gibt es zwei unterschiedlich komplexe Vorgehensweisen: Im einfachsten Fall ernennt ein Mensch einen Server zum Verantwortlichen (in vielen Anwendungen Master genannt) für alle schreibenden Zugriffe, nur dieser nimmt Schreibaufträge an. Jede Änderung schickt der Master anschließend an weitere replizierende Server, die eine Kopie der Daten pflegen und ausschließlich lesende Zugriffe beantworten oder sogar nur als Reserve für Notfälle bereitstehen. Verteilt man die Lesezugriffe, entlastet das den Master und auch die Stabilität nimmt zu, unter unglücklichen Umständen kann ein Server aber mal veraltete Daten zurückgeben. Außerdem gibt es in einem solchen System eine klare Hierarchie, die ein Mensch erschaffen hat, indem er einen Server zum Anführer und die anderen zu Kopienverwaltern ernannt hat. Hat der Anführer schwerwiegende Probleme, könnte und müsste ein Mensch eingreifen und die Rolle auf einen anderen Server übertragen.
Geteilte gemeinsame Wahrheit
Die Königsdisziplin ist ein Cluster, in dem kein Mensch mehr nötig ist, um Server mit Rollen zu versehen. In einem solchen System sind alle Maschinen gleichberechtigt, und als Anwender kann man sicher sein, dass bei jeder Anfrage die zuletzt gültige Wahrheit in die Bearbeitung einfließt. Eine SQL-Datenbank, die ein solches Konzept umsetzt, ist CockroachDB, die auch in einer quelloffenen Lizenz angeboten wird und die wir bereits ausführlich vorgestellt haben. CockroachDB nutzt im Kern den Raft-Algorithmus fürs Herstellen einer gemeinsamen Wahrheit und baut darauf all die Funktionen auf, die man von einem SQL-Datenbankserver erwartet.
Dass sich verteilte SQL-Datenbanken eine gemeinsame Wahrheit teilen müssen, leuchtet schnell ein. Einen Konsensalgorithmus brauchen aber nicht nur Systeme, auf denen ein verteilter Datenbestand liegen soll, sondern auch solche, die sich Arbeitsaufträge teilen sollen. Angenommen, Sie möchten eine Umgebung bauen, in der man Rechenaufgaben zur Bearbeitung abwirft – zum Beispiel rechenintensive wissenschaftliche Modelle. Ein großes Heer aus leistungsstarken Maschinen (sogenannten Worker-Nodes) soll sich immer eine Aufgabe schnappen und erledigen.
Auch für ein solches System braucht man eine gemeinsame Datenbasis: Sie enthält eine Liste an Aufgaben (sortiert zum Beispiel nach Eingangsdatum oder nach einer Priorität). In dieser Liste muss zuverlässig für jede Aufgabe stehen, ob sie schon ein Worker-Node in Bearbeitung hat und ob sie eventuell schon bearbeitet ist. Nur so ist sichergestellt, dass eine Aufgabe nicht mehrmals bearbeitet wird. Stellen Sie sich das Chaos vor, das in einer Bank entstehen würde, wenn eine Überweisungsaufgabe von mehreren Workern ausgeführt würde, nur weil die Aufgabenliste nicht perfekt synchronisiert wurde.
