Ein Konsensalgorithmus, den verteilte Systeme kennen müssen: Raft

1. Überblick über Raft

​Raft-Algorithmus​​​ ist die erste Wahl für die Entwicklung verteilter Systeme​Konsensalgorithmus​​ Beispielsweise sind Etcd und Consul mittlerweile beliebt. ​Raft 算法​​​是分布式系统开发首选的​​共识算法​​。比如现在流行 Etcd、Consul。

如果​​掌握​​​了这个算法，就可以较容易地处理绝大部分场景的​​容错​​​和​​一致性​​需求。比如分布式配置系统、分布式 NoSQL 存储等等，轻松突破系统的单机限制。

Raft 算法是通过一切以领导者为准的方式，实现一系列值的共识和各节点日志的一致。

二、Raft 角色

2.1 角色

跟随者（Follower）：​​普通群众​​，默默接收和来自领导者的消息，当领导者心跳信息超时的时候，就主动站出来，推荐自己当候选人。

候选人（Candidate）：​​候选人​​将向其他节点请求投票 RPC 消息，通知其他节点来投票，如果赢得了大多数投票选票，就晋升当领导者。

领导者（Leader）：​​霸道总裁​

If​​ Sobald Sie diesen Algorithmus beherrschen, können Sie die meisten Szenen problemlos verarbeiten.<code style="background-color: rgb(231, 243, 237); padding: 0px 3px; border-radius : 4px; overflow-wrap: break-word; text-indent: 0px;">​Fehlertoleranz​​​und​​Konsistenz​​ Anforderungen. Beispielsweise können verteilte Konfigurationssysteme, verteilter NoSQL-Speicher usw. die Einschränkungen des Systems auf eine einzelne Maschine leicht überwinden.

Der Raft-Algorithmus erreicht durch alle auf dem Leader basierenden Methoden einen Konsens über eine Reihe von Werten und Konsistenz in den Protokollen jedes Knotens.

2. Raft-Rolle

2.1 Rolle

Follower: ​​Gewöhnliche Leute​​, wenn die Herzschlaginformationen des Kandidaten ablaufen , wird er die Initiative ergreifen und sich als Kandidat vorschlagen.

Kandidat: ​​Kandidaten​ fordern Abstimmungs-RPC-Nachrichten von anderen Knoten an, um andere Knoten zur Abstimmung zu benachrichtigen. Wenn sie die Mehrheit der Abstimmungsstimmen gewinnen, werden sie zum Anführer befördert.

Leader: ​​Überheblicher Präsident​, alles unterliegt mir. Verarbeiten Sie Schreibanfragen, verwalten Sie die Protokollreplikation und senden Sie kontinuierlich Heartbeat-Informationen, um andere Knoten darüber zu informieren, dass „Ich bin der Anführer, ich lebe noch und Sie möchten nicht“ eine neue Wahl initiieren, ohne einen neuen Anführer als Ersatz finden zu müssen Mich.

Wie in der folgenden Abbildung dargestellt, werden drei Arten von Figuren verwendet, um Anhänger, Kandidaten und Führungskräfte darzustellen.

Rolle

3. Einzelknotensystem

3.1 Datenbankserver

Stellen wir uns nun vor, dass es ein Einzelknotensystem gibt, das als Datenbankserver fungiert und einen Wert von X speichert.

Datenbankserver

3.2 Client

Der durchgezogene grüne Kreis auf der linken Seite ist der Client und der durchgezogene blaue Kreis auf der rechten Seite ist Knoten a (Knoten a). „Term“ stellt die Amtszeit dar, auf die später eingegangen wird.

Client

🎜🎜3.3 Der Client sendet Daten an den Server🎜🎜🎜Der Client sendet einen Aktualisierungsvorgang an den Einzelknotenserver und setzt den in der Datenbank gespeicherten Wert auf 8. In einer eigenständigen Umgebung (einzelner Serverknoten) beträgt der Wert, den der Client vom Server erhält, ebenfalls 8. Konsistenz ist sehr einfach sicherzustellen. 🎜🎜🎜🎜🎜Der Client sendet Daten an den Server🎜🎜🎜3.4 Wie stellen mehrere Knoten die Konsistenz sicher? 🎜🎜🎜Aber wie kann die Konsistenz sichergestellt werden, wenn mehrere Serverknoten vorhanden sind? Beispielsweise gibt es drei Knoten: a, b, c. Wie unten gezeigt. Diese drei Knoten bilden einen Datenbankcluster. Wie kann sichergestellt werden, dass die in den drei Knoten gespeicherten Werte konsistent sind, wenn der Client Aktualisierungsvorgänge für diese drei Knoten durchführt? Dies ist ein Problem der verteilten Konsistenz. Der Raft-Algorithmus soll dieses Problem lösen. Natürlich gibt es auch andere Protokolle, die dies garantieren können. Dieser Artikel konzentriert sich nur auf den Raft-Algorithmus. 🎜

Wie stellt der Raft-Algorithmus in einem Cluster mit mehreren Knoten sicher, dass es unter ungewöhnlichen Umständen wie Knotenausfall und Partitionsfehlern gleichzeitig nur einen Anführer im Cluster gibt? Beginnen wir mit der Erklärung des Prozesses der Führerwahl durch den Raft-Algorithmus.

4. Leader-Wahlprozess

4.1 Ausgangszustand

Im Ausgangszustand sind alle Knoten im Cluster Follower.

Wie in der folgenden Abbildung gezeigt, gibt es drei Knoten (Knoten) a, b und c, und der Term (Term) ist 0.

Anfangszustand

4.2 Kandidat werden

Der Raft-Algorithmus implementiert die Funktion eines zufälligen Timeouts, und das Timeout-Intervall, in dem jeder Knoten auf die Heartbeat-Informationen des Leader-Knotens wartet, ist zufällig. Beispielsweise beträgt das Wartezeit-Timeout-Intervall von Knoten A 150 ms, das von Knoten B 200 ms und das von Knoten C 300 ms. Dann kommt es zunächst zu einer Zeitüberschreitung, da nicht auf die Heartbeat-Informationen des Anführers gewartet wird. Wie in der Abbildung unten gezeigt, beginnen die Timeout-Timer für die drei Knoten zu laufen.

Timeout

Wenn das Timeout von Knoten A abläuft, wird Knoten A zum Kandidaten, erhöht seine Termnummer, aktualisiert den Termwert von 0 auf 1 und gibt eine Stimme für sich selbst ab.

• Knoten A: Begriff = 1, Stimmenzahl = 1.
• Knoten B: Term = 0.
• Knoten C:Term=0.

Kandidat werden

4.3 Abstimmen

Mal sehen, wie ein Kandidat zum Anführer wird.

Anführerwahl

• Schritt : Nachdem Knoten A ein Kandidat geworden ist, senden Sie eine RPC-Nachricht mit der Aufforderung zur Abstimmung an andere Knoten und bitten Sie diese, sich selbst als Anführer zu wählen.
• Zweiter Schritt: Nach Erhalt der von Knoten A gesendeten Abstimmungsanforderungsinformationen stimmen Knoten B und Knoten C für Knoten A, ohne während der Amtszeit mit der Nummer 1 abzustimmen, und fügen ihre eigene Amtszeitnummer hinzu.
• Schritt 3: Knoten A erhielt 3 Stimmen und erhielt Stimmen von der Mehrheit der Knoten und wurde in dieser Amtszeit der neue Anführer von einem Kandidaten.
• Schritt 4: Knoten A sendet als Anführer in festgelegten Abständen Heartbeat-Informationen an Knoten B und Knoten C und teilt den Knoten B und C mit, dass ich der Anführer bin, und organisiert andere Anhänger, um Neuwahlen einzuleiten.
• Schritt 5: Knoten B und Knoten C senden Antwortinformationen an Knoten A und teilen Knoten A mit, dass ich normal bin.

4.4 Amtszeit

Das englische Wort ist Amtszeit, und Führungskräfte haben eine Amtszeit.

• Automatisch erhöhen: Nachdem sich der Follower als Kandidat empfohlen hat, nachdem er auf das Timeout der Heartbeat-Informationen des Anführers gewartet hat, wird seine Termnummer erhöht. Wie in der Abbildung oben gezeigt, ist der Term von Knoten A 0. Wenn der Wenn sich der Follower als Kandidat empfiehlt, erhöht sich die Laufzeit auf 1.
• Auf einen größeren Wert aktualisieren: Wenn ein Knoten feststellt, dass seine Termnummer kleiner als die anderer Knoten ist, wird er auf einen größeren Zahlenwert aktualisiert. Beispielsweise ist der Begriff von Knoten A 1 und fordert eine Abstimmung an. Die Abstimmungsnachricht enthält die Begriffsnummer von Knoten A, und die Nummer ist 1. Nachdem Knoten B die Nachricht erhalten hat, aktualisiert er seine Begriffsnummer auf 1.
• Zurück zum Follower: Wenn ein Kandidat oder Leiter feststellt, dass seine Amtszeitnummer kleiner ist als die anderer Knoten, wird er sofort in den Follower-Status zurückgesetzt. Dieses Szenario tritt auf, wenn ein Partitionsfehler behoben wird und der Leader mit Term 3 eine Heartbeat-Nachricht mit Term 4 empfängt, dann kehrt ersterer sofort in den Follower-Status zurück.
• Ablehnungsnachricht: Wenn ein Knoten eine Anfrage für einen kleineren Termnummernwert erhält, lehnt er die Anfrage direkt ab. Beispielsweise erhält Knoten A mit Termnummer 6 eine Abstimmungsanfrage von Knoten B mit Termnummer 5. RPC Nachricht, dann wird Knoten A die Nachricht ablehnen.

4.5 Wahlregeln

• Während einer Amtszeit bleibt der Anführer immer der Anführer, bis ein Problem (z. B. Ausfallzeit) oder ein Netzwerkproblem (Verzögerung) auftritt und andere Knoten eine neue Wahlrunde einleiten.
• Bei einer Wahl gibt jeder Serverknoten höchstens eine Stimme für eine Amtsnummer ab und diese ist nach Abschluss der Abstimmung verschwunden.

4.6 Die meisten

Angenommen, ein Cluster besteht aus N Knoten, dann ist die Mehrheit mindestens N/2+1. Beispiel: Bei einem Cluster mit 3 Knoten sind die meisten 2.

4.7 Heartbeat Timeout

Um zu verhindern, dass mehrere Knoten gleichzeitig eine Abstimmung einleiten, wird jedem Knoten ein zufälliges Wahl-Timeout zugewiesen. Während dieser Zeit kann der Knoten kein Kandidat werden und nur bis zur Zeitüberschreitung warten. Im obigen Beispiel läuft beispielsweise Knoten A zuerst ab und wird zuerst zum Kandidaten. Durch dieses clevere Design initiiert in den meisten Fällen nur ein Serverknoten zuerst die Wahl, anstatt die Wahl gleichzeitig zu initiieren, was die Anzahl von Wahlfehlschlägen aufgrund von Stimmenteilung reduziert.

Kandidat werden

5. Führungsfehler

Wenn der Führungsknoten ausfällt, wird eine neue Wahlrunde ausgelöst. Wie in der folgenden Abbildung dargestellt, wählen Knoten B und Knoten C den Anführer erneut, wenn der Anführerknoten A ausfällt.

Leader-Fehler

• Schritt : Knoten A hat einen Fehler, Knoten B und Knoten C erhalten nicht die Heartbeat-Informationen des Leader-Knotens A und die Wartezeit läuft ab.
• Zweiter Schritt: Zuerst läuft Knoten C ab und Knoten C wird zum Kandidaten.
• Schritt 3: Knoten C initiiert eine Anfrage nach Abstimmungsinformationen an Knoten A und Knoten B.
• Schritt 4: Knoten C antwortete auf die Abstimmung und stimmte für C, während Knoten A aufgrund eines Fehlers nicht in der Lage war, auf die Abstimmungsanfrage von C zu antworten.
• Schritt 5: Knoten C erhält zwei Stimmen (Mehrheit der Stimmen) und wird zum Anführer.
• Schritt 6: Knoten C sendet Heartbeat-Informationen an Knoten A und B. Knoten B antwortet auf die Heartbeat-Informationen. Knoten A antwortet nicht auf die Heartbeat-Informationen, da A fehlerhaft ist.

Zusammenfassung

Der Raft-Algorithmus verwendet die folgenden Methoden zur Durchführung von Führungswahlen und stellt so sicher, dass es in einer Amtszeit nur einen Anführer gibt, wodurch die Zahl der Wahlfehlschläge erheblich reduziert wird.

• Amtszeit
• Leader-Heartbeat-Informationen
• Zufällige Wahl-Auszeit
• First-Come-First-Served-Abstimmungsprinzip
• Most-Voting-Prinzip

In diesem Artikel wird erläutert, wie der Raft-Algorithmus Führungskräfte anhand animierter Grafiken wählt.

Das obige ist der detaillierte Inhalt vonEin Konsensalgorithmus, den verteilte Systeme kennen müssen: Raft. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!