Der Raft-Konsens-Algorithmus ist ein von Diego Ongaro und John Ousterhout von der Stanford-University im Jahr 2014 entwickelter Algorithmus, welcher es verteilten Systemen erlaubt, sich jederzeit und zuverlässig auf eine sogenannte gemeinsame Wahrheit zu einigen. Er stellt einen Konsens unter Server-Knoten eines Clusters her, die ihren Anführer (Master) selbst bestimmen. Es können Server ausfallen oder Netzwerkpakete verloren gehen. Raft kann dies ausgleichen. Raft-Cluster bestehen aus 3, 5 oder maximal 7 Serverknoten.
Raft ermöglicht moderne Clustersoftware als Basis (Raft) für verteilte Key-Value-Datenbanken wie etcd oder SQL-Datenbanken wie Cockroach-DB und MongoDB. Auf etcd basieren wiederum Container-Orchestratoren wie Kubernetes und Docker Swarm, welche die Grundlage verteilter Cloud-Software sind.
Server kennen nach dem Raft-Algorithmus drei Rollen beziehungsweise Status. Sie können Leader, Candidate oder Follower sein. Statt Leader wird manchmal auch die nicht mehr ganz politisch korrekte Bezeichnung Master und statt Follower das noch weniger korrekte Slave verwendet. In einem neu aufgesetzten Cluster wissen alle Server, welche anderen Server-Knoten zum Cluster gehören. Die Information über die Liste der Mitglieder wird selbst mit Raft verwaltet, damit dynamisch Knoten hinzugefügt oder entfernt werden können. Sie starten im Follower-Modus und fragen alle anderen Server, wer Leader sei. Existiert schon ein Leader wird das dem anfragenden Server mitgeteilt. Wenn nicht, gehen die Knoten nach einer unterschiedlichen, zufälligen Wartezeit in den Kandidaten-Modus über. Der Knoten, bei dem zuerst die Wartezeit abläuft setzt sich selbst in den Kandidatenmodus und veranstaltet damit eine Leader-Wahl, indem er dies den anderen Knoten mitteilt. Die anderen Knoten nehmen den Vorschlag des Kandidaten an, der dadurch zum Leader wird. Danach schickt der Leader regelmäßig ein Heartbeat-Signal welches den Followern die Existenz des Leaders anzeigt.
Fällt der Leader zu einem späteren Zeitpunkt aus, erfolgt die Wahl nur unwesentlich komplizierter, denn es muss ermittelt werden, welcher der anderen Server den neusten Stand der Daten (Leader-Completness-Property) hat.
Lese- und Schreib-Aufträge werden von einem Client nur an den Leader gestellt und auch nur von diesem beantwortet. Da der Client aber erst einmal nicht wissen kann, wer Leader ist, kann er dies von jedem Knoten auf Anfrage beantortet bekommen.
Jeder mit Raft arbeitende Server pflegt zwei Datenstrukturen: ein Log mit Schreibaufträgen und einen State-Maschine, welche immer den aktuellen Zustand der Wahrheitsdaten enthält. Bei einem Schreib-Request trägt der Leader den neuen Wert in sein Log ein und teilt dies auch allen Followern mit. Diese bestätigen den Erhalt des Requests. Nachdem der Leader für mehr als die Häfte der Knoten die Bestätigung erhalten hat, trägt er den Wert in seiner Zustandsmaschine ein, bestätigt das Schreiben dem Client und schickt erst danach eine Mitteilung an alle Follower, dass auch diese den Wert in ihre Zustandsmaschine schreiben. Das sort dafür, dass immer eine Mehrheit der Knoten den aktuellen Wert hat. Über Plausibilisierungen im Log kann auch immer festgestellt werden, wenn Schreibaufträge bei einzelnen Knoten fehlen und können vom Leader wieder ergänzt werden.
Da das Log mit der Zeit immer länger wird und ausfallende Server so lange brauchen würden die Daten zu verarbeiten, existiert auch ein Snapshot-Mechanismus. Mit einem Snapshot schreiben die Server einen commiteten Version der gesamten Zustandsmaschine weg und können so das Log verkürzen. Ein ausgefallener Server kann so mit dem Snapshot und dem verkürzten Log nachgefahren werden.
