Konsens Algorithmus Raft als Fundament für einen stabilen Betrieb verteilter Systeme

Systeme können entweder auf Datenhaltungsebene oder auf Prozessing-Ebene verteilt sein. Apache Kafka oder verteilte Datenbankmodi von Datenbanken bieten eine verteilte Datenhaltung und zählen daher zur Datenhaltungsebene. Bei der Datenhaltung ist jeweils ein Anführer notwendig, der die Abläufe bei der Ablage von Daten überwacht und managed, um eine konsistente Datenhaltung zu bewahren.
Um die Ausfallsicherheit zu erhalten, ist es hierbei wichtig keinen Single-Point-of-Failure aufzubauen, der über die Verfügbarkeit des Gesamtsystems entscheidet. Hierfür muss das verteilte System eigenständig die Bestimmung eines Anführers durchführen und im Notfall auf unerwartete Zustände, wie den Ausfall des Anführers oder ein Split-Brain-Szenario (mehrere Anführer), reagieren können.
Diese Aufgabe erfüllen Konsens Algorithmen, welche durch alle Teilnehmer des Systems implementiert und ausgeführt werden müssen. Paxos, Zab und Raft sind populäre Beispiele für solche Konsens Algorithmen. Apache Kafka arbeitet z.B. mit Apache Zookeeper, welches auf Zab als Algorithmus basiert. Raft ist in einigen Projekten wie beispielsweise Consul im Einsatz.

Im Video von meinem Senacor StreamedCon-Vortrag findet ihr eine bildliche Erklärung des Algorithmus Raft und die Vorteile dieses Algorithmus gegenüber anderen Algorithmen, welche unter anderem bei Krypto-Währungen zum Einsatz kommen.
Wer lieber eine kurze Zusammenfassung der Inhalte lesen möchte, einfach unter dem Video weiterlesen…

Allgemein

Raft baut auf zwei grundlegenden Konzepten auf: Das erste Konzept ist die Wahl eines Anführers für einem bestimmten Zeitraum bzw. Term (Leader Election). Nach der Wahl eines Anführers folgen alle anderen Komponenten dem Anführer bis zu einer erneuten Wahl. Der bestimmte Zeitraum oder Term ist dabei eine Zahl, welche inkrementell erhöht wird. Bei einer Leader Election muss ein Anführer zudem mindestens 50% der Stimmen erhalten.
Das zweite Konzept ist die Log Replication. Hierfür werden alle Änderungen oder Aktionen an Daten in einem Log abgelegt. Dieser Log kann nur durch den Anführer angepasst werden und wird auf die verschiedenen Teilnehmer repliziert.

Leader Election

Eine Leader Election für die Wahl eines neuen Anführers des Systems findet in den meisten Fällen beim  Start des Systems oder beim Ausfall des Anführers statt. Zu diesem Zeitpunkt wird ein neuer Zeitraum oder Term gestartet. Der Auslöser für einen neuen Term ist die fehlende Kommunikation in einem definierten Zeitraum (election timeout) zwischen dem Anführer und einem Teilnehmer des Systems. Dadurch wird der betreffende Teilnehmer zu einem Kandidaten für den Posten des Anführer in einem neuen Term.
Hierfür sendet dieser Teilnehmer an alle anderen Teilnehmer des Systems eine Anfrage zur Wahl eines neuen Anführers und schlägt sich selbst als Anführer vor. Die anderen Teilnehmer bestätigen den Anführer für diesen Term. Dadurch ist ein neuer Anführer für den Term gewählt und für die Verarbeitung von Anfragen zuständig.
Eine Split-Brain-Situation kann bei der Wahl aufgrund der folgenden Einschränkungen nicht entstehen (Netzwerk- / Kommunikation-Probleme ausgeschlossen):

• Jeder Teilnehmer kann pro Term nur eine Stimme abgeben
• Eine einfache Mehrheit ist für die Wahl eines Teilnehmers zum Anführer notwendig
• Der höchste Term ist immer der Aktuellste. Wenn ein Teil des Systems in einem kleineren Terms arbeitet als die anderen Teile des Systems, so müssen diese sich dem Teil mit dem aktuellsten Term anschließen.

Log Replication

Der Anführer eines Systems ist für die Log Replication verantwortlich. Dadurch dürfen Änderungen an einem Log nur durch den Anführer durchgeführt werden, um Dateninkonsistenzen zu verhindern. Ein Log bildet die historische Änderungen an einem System oder Daten ab. Jeder Teilnehmer des Systems verwaltet sein eigenes Log. Der Master ist für die Konstanz der Logs aller Teilnehmer zuständig.
Ein Log ist beispielsweise die Historie von Änderungen an einem bestimmten Datensatz wie das Konto eines Kunden. Hierbei werden alle Änderungen (Einzahlungen oder Abhebungen) sequentiell basierend auf dem vorherigen Datenstand aufgebaut. Ein spezifischer Log eines Kunden wird über einen Großteil der Teilnehmer eines Systems verteilt, um eine Ausfallsicherheit zu erhalten. Für die Replikation des Logs ist der Anführer zuständig und bestätigt auch die Anfrage eines Clients zur Änderung von Daten erst wenn ein Großteil der Teilnehmer die Änderungen am Log durchgeführt haben.

Zusammenfassung

Konsens Algorithmen sind ein wichtiger und notwendiger Bestandteil von verteilten Systemen und somit in vielen Projekten essentiell für einen stabilen Betrieb vieler Anwendungen bei beispielsweise Finanzinstituten. Hierbei ist das Ziel des Algorithmus eine konstante Datenhaltung oder Prozessierung über mehrere physische oder virtuelle Einheiten zu ermöglichen. Dadurch wird die Ausfallsicherheit eines Gesamtsystems erhöht und die Last auf alle Einheiten eines Systems verteilt.
Raft ist ein gut verständlicher Konsens Algorithmus, besitzt allerdings auch noch eine gewisse Komplexität bei der Implementierung. Im Vergleich zu anderen Konsens Algorithmen ist Raft aber deutlich einfacher umzusetzen und dadurch in vielen OpenSource-Projekten, welche auf verteilte Systemen aufbauen, in Verwendung.