In einem der vorherigen Beiträge wurde das Thema Consensus bzw. auch Paxos, der auf die Veröffentlichung von L. Lamport (The Part-Time Parliament) zurückgeht, behandelt. Den Paxos kennzeichnet eine hohe abstrakte Komplexität, was das Realisieren einer stimmigen Softwarelösung erschwert. Aus diesem Grund wurde der so genannte RAFT-Algorithmus entwickelt, den wir uns im folgenden Abschnitt genauer anschauen werden. Ziel war es, einen Mechanismus zu erfinden, der genauso effizient wie ein klassischer Paxos, aber verständlicher und leichter zu programmieren ist.

Ein RAFT-Cluster arbeitet immer mit einem Leader. Das ist eine Instanz, die den Cluster koordiniert. Im ersten Schritt wählt ein Cluster also einen Leader aus der Mitte seiner Instanzen. Dabei warten alle Knoten eine definierte Zeitspanne, ob sich ein Leader bei ihnen meldet. Sollte dies nicht der Fall sein, beginnt ein neuer "Term" mit dem ersten Schritt, der "Leader Election", also der Wahl einer koordinierenden Instanz. Dabei schlagen sich Instanzen des Clusters selbst als "Leader-Kandidaten" vor und fragen die anderen Server nach deren Zustimmung, sofern sie vor der eigenen Kandidatur nicht schon um Zustimmung zur Wahl einer anderen Instanz gefragt wurden. Der Knoten, der durch die Mehrheit (Quorum) des Clusters gewählt wurde, wird zum neuen Leader (alle anderen sind dann sogenannte Follower) und die zweite Phase des "Terms" beginnt.

Durch einen "Heardbeat" prüft der neue Leader nach seiner Wahl regelmäßig, ob und welche Knoten im Verbund online sind. Sollte er sich selbst nicht mehr bei seinen Peers melden, gehen diese davon aus, dass er offline ist. Automatisch beginnt ein neuer Term mit einer weiteren Leader Election. Sollte bei einer Wahl ein Gleichstand von Zustimmungen für zwei zeitgleich verfügbare Leader-Kandidaten entstehen, gibt es keinen Leader. Das Cluster wartet in diesem Fall einfach, bis die definierte Zeitspanne ohne Leader verstrichen ist und beginnt automatisch mit einer neuen Leader Election. Wie verhindert man eine konstante Patt-Situation bei der Wahl? Die Zeitspanne, bis sich ein Knoten zum Leader-Kandidaten erklärt, wird durch ein Zufallsprinzip individuell (im Rahmen eines definierten Intervalls) gewählt. Beträgt die Zeitspanne beispielsweise 5 Sekunden, legt jeder Server per Zufallsprinzip fest, dass er eine Wartezeit zwischen 0 und 5 Sekunden wählt. So wird eine sich wiederholende Patt-Situation extrem unwahrscheinlich. Weiterhin wird sich die Wahl nie vollständig synchron abspielen, denn einzelne Nachrichten zwischen den jeweiligen Instanzen werden nie zum exakt selben Zeitpunkt verarbeitet. Aus diesen beiden Gründen wird früher oder später immer eine Mehrheit für einen Leader gefunden.

Ist ein Leader gewählt, werden Clientanfragen ausschließlich durch diesen im Cluster koordiniert und verteilt. So landen die Anfragen von Anwendungen quasi durch den Leader verteilt im lokalen Speicher (Commitlog) der verbundenen Follower-Instanzen. Sobald ein Quorum der beteiligten Knoten eine Clientanfrage an den Koordinator bestätigt, bekommt der Client durch den Leader ein "O. k." gemeldet. Informationen des Commitlogs dienen in der Leader Election auch als Kriterium der Stimmenvergabe. Verfügt ein "Leader-Kandidat" bei der Wahl nicht über das aktuellste Commitlog (festzustellen über einen Log Index = monoton steigender Zähler der Log-Einträge), bekommt dieser auch nicht die Stimmen derjenigen Knoten, die über einen neueren Stand des Logs im Cluster verfügen. Das heißt, jede Nachricht, die innerhalb des Cluster ausgetauscht wird, enthält neben dem Log Index des letzten Eintrags im Log auch den jeweils aktuellen Term, um sicherzustellen, dass es immer nur einen Leader zum selben Zeitpunkt geben kann.

Aber worin unterscheidet sich nun der klassische Paxos zum RAFT-Algorithmus? Der eigentliche Unterschied ist im Grunde die konkrete Ausprägung des Systemverhaltens. Man könnte mit etwas gutem Willen auch sagen, dass es sich bei RAFT um eine konkretisierte Implementierung der theoretischen Abläufe des Paxos handelt. Was L. Lamport in seinem originalen Artikel beschreibt, ist sehr formal und abstrakt. Ein Programmierer muss sich also selbst überlegen, wie sich ein System konkret verhalten soll, um den formalen Eigenschaften des Paxos gerecht zu werden. Der einzige offensichtliche Unterschied zwischen den beiden Algorithmen ist die explizite Wahl eines Leaders, die beim Paxos nicht vorgesehen ist. In letzter Konsequenz arbeiten die Instanzen beim Paxos sehr ähnlich. Zum Beispiel setzt beim Paxos derjenige Knoten seine Transaktion durch, der mehr als die Hälfte aller Cluster-Stimmen hinter sich versammeln kann. Innerhalb dieser Quorumbildung ist quasi eine Leader Election impliziert, da sich eine Instanz mit ihrem Vorschlag durchgesetzt hat – also „gewählt“ wurde.

Fazit

Wenn Sie sich im Detail mit den unterschiedlichen Consensusverfahren beschäftigen möchten, empfehle ich, sich zunächst mit dem praktischen RAFT-Algorithmus zu befassen und sich dann an den Paxos heranzutasten.