RAFT und Replication

Applikationen brauchen häufig eine Datenhaltung. Um eine Datensicherheit zu gewährleisten und Risiken zu mitigieren, kommen deshalb meistens verteilte Datenbanken zum Einsatz. In diesem Beispiel stelle ich RAFT vor, ein Algorithmus zum Erreichen von Konsensus für verteilte Datenbanken.

Datenkbanken und Datensicherheit

Kaum eine Applikation kommt ohne eine Datenhaltung aus. Persistente Daten sind in Applikationen einer der wichtigsten Faktoren, denn: Nicht selten sind Applikationen ohne eine echte Datenhaltung nutzlos. Deshalb muss eine langlebige Speicherung und hohe Erreichbarkeit der Daten jederzeit gewährleistet werden.

Klassischerweise kommen deshalb Datenbanken zum Einsatz, die für die Speicherung und Abfrage von Daten ausgelegt sind. Damit Datenbanken eine hohe Erreichbarkeit aufweisen und die Daten sicher gespeichert werden, bieten Datenbanken eine Möglichkeit der Datenreplikation. Verschiedene Datenbank-Instanzen werden dafür auf verschiedenen Rechnern parallel betrieben. Das passiert z.B. in einem Leader-Follower Setup. Der Leader ist dabei die erste Anlaufstelle für die Operationen und repliziert die Kommandos 1 zu 1 an den Follower. Fällt der Leader aus, so übernimmt der Follower (auch genannt “Hot Standby”).

 Dieses Setup hat jedoch eine Wahl zu treffen, wenn Schreib-Zugriffe (z.B. INSERTS) beim Master eintreffen:

1. Der Leader akzeptiert den Write und schreibt diesen Lokal persistent weg. Die Schreiboperation wird später, asynchron, an einen Follower weitergereicht. Dieser erhält die Schreib-Operation also mit einem Minimalen Delay.
2. Der Leader akzeptiert den Write und leitet ihn an den Follower weiter. Erst wenn dieser den Write bestätigt hat, wird der Write bestätigt und die Daten gelten als persistent gespeichert.

Asynchrone Replikation

Option 1 hat den klaren Vorteil, dass Schreibzugriffe nur vom Leader aus geschrieben werden. Fällt der Follower weg, dann können Daten trotzdem geschrieben werden.

Das Problem dabei: Fällt der Leader weg und der Follower wird der neue Leader, dann können die Daten, die in der Zeit zwischen Schreibe-Operation und Replikation geschrieben worden sind, verloren gehen. Ein No-Go für viele Systeme.

Ein weiteres Problem kann auftreten: Viele Systeme benötigen Linearisierbarkeit. Linearisierbarkeit bedeutet

you need to make it appear as though there is only a single copy of the data, even though there may be copies (replicas, caches) of the data in multiple places.

(vgl. https://martin.kleppmann.com/2015/05/11/please-stop-calling-databases-cp-or-ap.html)

Das bedeutet also, dass wenn Daten im System geschrieben worden sind, diese danach in allen Lese-Operationen gelesen werden können. Angewandt auf einem Beispiel:

Ein Client schreibt den Namen “LARS” in eine Tabelle. Der Datensatz “LARS” wurde noch nicht an einen Follower repliziert, aber vom Leader bestätigt. Der Client sendet darauf eine Anfrage für alle User mit dem Namen “LARS”. Der Request wird vom Follower bearbeitet.

Da die Daten noch nicht da sind, antwortet der Follower mit (NONE). Je nachdem, welcher Knoten angefragt wird, gibt es also eine andere Antwort. Erst jetzt folgt zeitlich die Replikation vom Leader und der Follower kennt den Datensatz “LARS”.

Mit dieser Art der Replikation wird also die Linearisierbarkeit (“Consistency” in CAP) aufgegeben.

Synchrone Replikation

Oft ist das Verhalten von asynchronen Replicas keine Alternative, weshalb die synchrone Replikation (Option 2) bevorzugt wird. Anders als bei der asynchronen Replikation, leidet die synchrone Replikation aber an einer anderen Schwierigkeit: Muss der Leader immer warten, bis der Follower eine Schreibe-Operation bestätigt hat, dann ist das System fragil. Bedeutet: Fällt der Follower weg, können keine Writes mehr bestätigt werden und das System ist nichtmehr Available. In diesem Falle ist das System nichtmehr erreichbar und der Mensch muss den Fehler beheben.

Was fehlt ist also eine Kombination der beiden Ansätze. Ein Ansatz der sowohl Replikation, als auch eine hohe Erreichbarkeit, sowie Linearsierbarkeit aufweist, und keine menschliche Interaktion im Ausfall erfordert. Einer dieser Ansätze ist RAFT.

RAFT

RAFT ist ein Algorithmus für einen verteilten Konsensus. Dieser Konsensus wird erreicht, in dem die Mehrheit von Nodes entscheidet, was der richtige Zustand ist. Damit eine Mehrheit erreicht werden kann, muss ein RAFT-System deshalb immer aus mindestens 3 Knoten im System bestehen. 

Dafür gibt es 3 Rollen: den Leader, den Candidate und den Follower.

Der Leader ist für Schreib- und Lese-Operationen verantwortlich, während der Candidate ein Leader werden kann, sofern der Leader als nicht erreichbar gilt. Der Follower erhält lediglich die Daten des Leaders und nimmt an den Wahlen für den neuen Leader teil. Das Zusammenspiel dieser Rollen ist im RAFT Algorithmus definiert.

Aber funktioniert RAFT also in der Praxis und wozu werden die Rollen benötigt?
Wie verhält sich Raft außerhalb des Happy Paths, also wenn nicht alles glatt läuft?

Schreibe Operation

Die wichtigste Eigentschaft, die RAFT bringt, wenn es um das Schreiben von Daten geht, ist, dass sichergestellt wird, dass der Konsens im System stimmt. Das bedeutet jede Schreibe Operation muss von M-Nodes bestätigt worden sein. Im Falle von 3 Knoten ist M=2.

M = Math.floor(nodes/2) + 1 
== floor(3/2) + 1 
== floor(1.5) + 1 
== 2

Es lässt sich im Bild RAFT Schreib-Prozess erkennen, wie an der Stelle (1) ein Client den Datensatz “LARS” schreiben möchte. Der Leader hat mit dieser Schreibe-Operation bereits eine von 2 nötigen Bestätigungen erhalten, um die Mehrheit des Systems für das Schreiben der Daten zu erhalten. Er muss also dafür sorgen, eine weitere zu erhalten. Dafür leitet der Leader in (2) die Schreib-Operation an beide Follower weiter. Diese schreiben die Daten wie in (3) und (5) gezeigt weg.

Erhält der Leader in der Zwischenzeit genug Bestätigungen um ein Quorum zu erreichen (2 Bestätigungen), dann gilt die Schreibe Operation als erfolgreich, da die Mehrheit der Knoten im Cluster nun die Daten erhalten hat. Der Leader schreibt in (6) somit die Änderung in seine eigene Datenhaltung und bestätigt dem Client die Schreib-Operation in (7).

Es ist nun sicher gestellt, dass die Mehrheit der Knoten im System der Meinung ist, dass der Datensatz “LARS” existiert. Er wurde erfolgreich repliziert.

Lese Operation

Soll der zuvor geschrieben Datensatz gelesen werden, soll RAFT Linearsierbarkeit sicherstellen. Das heißt, nach einer bestätigten Schreibe-Operation, soll dieser Datensatz in der Ergebnismenge bei einer folgenden Lese-Operation vorhanden sein. 

Da nur der Leader weiß, welche Operationen bereits bestätigt wurden, kann deshalb nur dieser Lese-Anfragen bearbeiten. Im Bild 2, zeigt wie ein READ-Request vom Client bei einem Follower ankommt. Da dieser in der Rolle Follower ist, darf dieser Read Requests nicht beantworten (Ok, es gäbe eine Möglichkeit: Follower Reads). Er leitet also den Request weiter an den Leader (3 + 4), um das Ergebnis zu erhalten und an den Client zu senden (5). Wir sehen also, durch RAFT verliert man zunächst die Möglichkeit der READ-Replica, da der Leader alle Anfragen beantworten muss.

Damit sind also die beiden Wichtigsten Operationen, Read und Write abgedeckt. Doch was passiert, wenn Knoten ausfallen oder gar voneinander getrennt/partitioniert werden?

Ein Follower wird partitioniert

Im Bild ist das Szenario skizziert, dass der Knoten #3 ausfällt.

Was würde in diesem Szenario passieren, wolle der Leader etwas schreiben? Da es immernnoch eine weitere Node (Node #2) in seiner Partition existiert, ist es dem Leader möglich ein Quorum zu erreichen. Der Ausfall des Follower der Node #3 ist also ohne Auswirkung auf das Gesamtsystem.

Leader

Ein besonderer Fall ist, wenn der Leader ausfällt oder partitioniert wird.



Im Bild #1 ist es dem Leader nicht möglich Schreib-Operationen auszuführen. Es kann schließlich kein Quorum mehr erreicht werden.

Anders sieht es in der rechtsliegenden Partition von #1 aus. Den beiden Followern ist es möglich gemeinsam ein Quorum zu erreichen. Aufgrund der Write-Bedingung (Die Mehrheit hat den Write bestätigt) können nur zwei Fälle auftreten:

1. ist in dieser Menge immer mindestens ein Follower, der den aktuellsten Stand hat
2. Es kann kein Quorum erreicht werden, da zu wenig Knoten in der Partition sind.

Einer dieser beiden Follower kann deshalb zu einen Candidate werden, wie in #2 gezeigt, sofern er den aktuellsten Stand vom vorherigen Leader besitzt und der Leader als unereichbar-erkannt wird (das passiert z.B. durch heartbeats). Es wird dann ein Vote-prozess gestartet. Erhält der Candidate die Mehrheit der stimmen, ist er dieser nun neue Leader.

Tritt wie in #3 der alte Leader der Partition bei, so muss dieser die Leader-Rolle verlassen. Er ist nun ein Follower des neuen Leader.

RAFT ist also so lange Partition-Sicher, solange sich die Mehrheit aller Knoten in einer Partition befindet.

Zusammenfassung

Ich habe in diesem Beitrag die in meinen Augen wichtigen Eigenschaften von Raft gezeigt und wozu RAFT überhaupt benötigt wird. Zum einen das Setup eines RAFT System, zum anderen die beiden wichtigsten Operationen einer Datenbank: Read und Write und wie diese in einer verteilten Datenbank umgesetzt werden.

Danach hab ich diverse Partitionierungs-Szenarien gedanklich durchgespielt und das dazugehörige RAFT Verhalten erläutert.

Natürlich ist RAFT noch viel komplexer als das Gezeigte. Ich habe hier nicht behandelt, wie beispielsweise der Election-Prozess aussieht, oder was passiert, sollte ein Write von einem Follower bestätigt werden, diese Bestätigung kommt aber niemals beim Leader an. Es sollte hier auch mehr um die Prinzipien von RAFT gehen. Vor allem sollte gezeigt werden, was passiert wenn Knoten wirklich unerreichbar sind und welche Trade-Offs ein RAFT-System eigentlich mitbringt.