Paxos und Floß sind zwei bekannte Konsensprotokolle, die es schon lange gibt und die für das Verständnis der Replikation von Zustandsmaschinen in verteilten Computersystemen von entscheidender Bedeutung sind. Paxos ist eigentlich eine Familie von Protokollen, die sich je nach System auf eine Gruppe unterschiedlicher Annahmen stützen, während Raft ein alternativer Konsens zu Paxos ist, der verständlicher gestaltet wurde.

Das Verständnis von Paxos und Raft ist sehr hilfreich, um das Wissen darüber zu erweitern, wie verteilte Konsensprotokolle in Kryptowährungen funktionieren, z. B. Arbeitsnachweise und praktische byzantinische Fehlertoleranz.

Paxos & amp; Raft-Konsensprotokolle

Hintergrund auf Paxos und Floß

Paxos wurde ursprünglich 1989 vorgeschlagen und zeichnete sich als besonders elegante Methode zum Nachweis der Sicherheit für einen fehlertoleranten verteilten Konsens aus. Trotz seiner anfänglichen Neuheit wird Paxos aufgrund seiner breiten Annahmen und seines komplexen Verhaltens oft als schwierig zu verstehen angesehen.

Raft wurde als verständlichere Alternative zu Paxos entwickelt, die in Bezug auf Leistung und fehlertolerante Garantien im Wesentlichen Paxos entspricht. Sowohl für Paxos als auch für Raft stehen umfangreiche Ressourcen zur Verfügung, die heute in einer Vielzahl von Anwendungen und Systemen untersucht und eingesetzt werden.

Einige der bekannteren praktischen Anwendungen von Paxos befinden sich in der NewSQL-Datenbank von Google Schlüssel und der IBM SAN Volume Controller für Speichervisualisierungsdienste.

Raft hat mehrere Open Source Referenzimplementierungen in mehreren Sprachen, einschließlich Go, Java, C ++ und Rust.

Was ist Paxos??

Ein Konsens in einem verteilten fehlertoleranten System besteht darin, dass eine Gruppe unzuverlässiger Teilnehmer ein Ergebnis erzielt. Paxos ist eine Familie von Konsensalgorithmen, die verschiedene Kompromisse zwischen Annahmen über Prozessoren, Teilnehmer und Nachrichten in einem bestimmten System eingehen. Das Protokoll garantiert Sicherheit und wird häufig dort eingesetzt, wo die Haltbarkeit großer Datenmengen erforderlich ist.

Asynchrone Konsensprotokolle können nicht sowohl Sicherheit als auch Lebensdauer garantieren, daher haben sie alle ihre eigenen Kompromisse. Paxos war eines der ersten verteilten fehlertoleranten Konsensprotokolle, das Sicherheit garantiert und versucht, Lebendigkeit zu erzeugen, indem sichergestellt wird, dass die Gruppe der Teilnehmer in einer Konsensrunde schließlich einen vorgeschlagenen Wert auswählt.

Im Paxos-Konsens gibt es drei Rollen, die als Agenten bezeichnet werden:

  1. Antragsteller
  2. Akzeptoren
  3. Lernende

Ziel des Konsenses ist es, dass eine Gruppe von Teilnehmern eine Einigung über einen einzelnen Wert pro Runde erzielt. Eine Konsensrunde beginnt, wenn ein Antragsteller einen vorgeschlagenen Wert an eine Gruppe von Akzeptoren sendet. Akzeptoren können den vorgeschlagenen Wert von einem bestimmten Antragsteller akzeptieren. Sobald ein bestimmter Schwellenwert erreicht ist, wird dieser Wert vom Netzwerk genehmigt.

Damit der Konsens jedoch korrekt funktioniert, ist die erste Bedingung von Paxos:

“Akzeptoren müssen den ersten vorgeschlagenen Wert akzeptieren, den sie erhalten.”

Dies führt zu dem Problem, dass mehrere Antragsteller vorgeschlagene Werte senden, die von den Akzeptoren akzeptiert werden, aber alle keinen Mehrheitswert akzeptieren, da sie den ersten vorgeschlagenen Wert akzeptieren. Paxos löst dieses Problem, indem jeder vorgeschlagene Wert, den ein Akzeptor erhält, eindeutig indiziert wird, sodass er mehr als einen Vorschlag annehmen kann.

Eine eindeutige Nummer definiert jeden Vorschlag, und das Netzwerk wählt einen Wert aus, sobald ein bestimmter vorgeschlagener Wert von der Mehrheit der Akzeptoren akzeptiert wird gewählt Wert. Es können mehrere Vorschläge ausgewählt werden. Es ist jedoch erforderlich, die Sicherheitseigenschaft zu validieren, indem sichergestellt wird, dass diese Vorschläge alle den gleichen Wert haben. Gemäß Leslie Lamports Definition der erforderlichen zweiten Bedingung von Paxos, die die Sicherheit gewährleistet:

“Wenn ein Vorschlag mit dem Wert v ausgewählt wird, hat jeder Vorschlag mit höherer Nummer, der ausgewählt wird, den Wert v.”

Die Kommunikation im Netzwerk ist asynchron, daher ist es möglich, dass bestimmte Akzeptoren den gewählten Wert nicht erhalten haben. Dies ist in Ordnung, solange die Bedingungen 1 und 2 nicht verletzt werden.

Antragsteller verwenden bestimmte Einschränkungen als Nachrichten an Akzeptorsätze zusammen mit den Werten. Diese nennt man Anfragen vorbereiten und enthalten 2 primäre Anfragen:

  1. Versprich, niemals einen Vorschlag weniger als anzunehmen n (n ist die neue Vorschlagsnummer)
  2. Antworten Sie mit dem Vorschlag mit der höchsten Zahl kleiner als n dass der Akzeptor akzeptiert hat.

Laut Lamport:

„Wenn der Antragsteller die angeforderten Antworten von einer Mehrheit der Akzeptanten erhält, kann er einen Vorschlag mit der Nummer n und dem Wert v ausstellen, wobei v der Wert des Vorschlags mit der höchsten Nummer unter den Antworten ist oder ein vom Antragsteller ausgewählter Wert wenn die Antwortenden keine Vorschläge gemeldet haben. “

Die Antragsteller senden anschließend eine Annahme-Anfrage, die von den Akzeptoren bestätigt wird. Der Antragsteller sendet dann eine Festschreibungsnachricht an die Akzeptoren, die entweder ignorieren (ohne die Sicherheit zu beeinträchtigen) oder den Erfolg der Wertüberschreibung anzeigen können. Sobald ein bestimmter Schwellenwert von Akzeptoren den Wert festgeschrieben hat, wird das Protokoll für diese Konsensrunde beendet und der Wert externalisiert.

Das komplizierte Design von Paxos besteht darin, dass es Werte akzeptieren kann, wenn die Mehrheit der Knoten zustimmt, obwohl andere Knoten einen vorgeschlagenen Wert ignorieren oder ablehnen. Dies unterscheidet sich von früheren Konsensiterationen, bei denen alle Knoten übereinstimmen mussten und das Protokoll aufgrund des Ausfalls einzelner Knoten blockiert wurde.

Solange die Angebotsnummern eindeutig sind, kann Paxos einen Wert auswählen, der die Sicherheit garantiert. Es ist wichtig zu beachten, dass sich ein Akzeptor nur an den Vorschlag mit der höchsten Nummer erinnern muss, den er akzeptiert hat. Umgekehrt kann ein Antragsteller einen Vorschlag jederzeit aufgeben, solange er keinen Vorschlag mit derselben eindeutigen Nummer erneut ausstellt.

Die Rollen des Antragstellers und des Akzeptors im Protokoll sind wie folgt aufgeteilt:

Antragsteller

  • Vorschlag einreichen n Warten Sie, bis die Mehrheit mit der Vorbereitung der Anfrage antwortet.
  • Wenn die Mehrheit der Akzeptanten antwortet, dass sie zustimmen, antworten sie mit dem vereinbarten Wert. Wenn die Mehrheit ablehnt, brechen Sie den Prozess ab und starten Sie ihn neu.
  • Der Antragsteller sendet anschließend eine Festschreibungsnachricht mit n und Wert, wenn die Mehrheit akzeptiert.
  • Wenn die Mehrheit der Akzeptoren die Festschreibungsnachricht akzeptiert, ist die Protokollrunde abgeschlossen.

Akzeptor

  • Empfangen Sie den Vorschlag und vergleichen Sie ihn mit dem bereits vereinbarten Vorschlag mit der höchsten Nummer.
  • Wenn n ist höher als der Vorschlag anzunehmen, wenn n niedriger ist, dann lehne den Vorschlag ab.
  • Akzeptieren Sie nachfolgende Festschreibungsnachrichten, wenn ihr Wert mit einem zuvor akzeptierten Vorschlag übereinstimmt und seine Sequenznummer die höchste vereinbarte Nummer ist.

Vorschläge können mehrere Vorschläge machen, müssen jedoch den Algorithmus für jeden Vorschlag einzeln befolgen.

Schließlich die Rolle der Lernende ist festzustellen, dass eine Mehrheit der Akzeptanten einen Vorschlag der Antragsteller angenommen hat. Es wird ein ausgezeichneter Lernender ausgewählt, der den ausgewählten Wert an die anderen Lernenden im Netzwerk weitergibt. Variationen dieses Prozesses können verwendet werden, wenn entweder alle Akzeptoren die entsprechenden Lernenden über ihre Entscheidungen informieren oder die Akzeptoren auf eine bestimmte Gruppe von Lernenden reagieren, die die Nachricht dann an den Rest der Lernenden weitergeben.

Formal unterscheidet der Paxos-Algorithmus einen Anführer (Antragsteller) für jede Runde, die erforderlich ist, um Fortschritte zu erzielen. Akzeptoren können die Führung eines Antragstellers anerkennen, wodurch Paxos zur Auswahl eines Führers innerhalb eines Knotenclusters verwendet werden kann. Paxos kann ins Stocken geraten, wenn zwei Antragsteller um die Führungsposition konkurrieren, ohne jedoch zu vereinbaren, welcher der Anführer ist. Es ist jedoch unwahrscheinlich, dass dieser Zustand der Nichtbeendigung anhält.

Was ist Floß??

Raft wurde als verständlichere Version von Paxos mit den gleichen Fehlertoleranz- und Leistungsgarantien entwickelt. Raft verbessert auch die Erstellung praktischer Implementierungen von Protokollen. Aufgrund der Komplexität von Paxos ist es nicht sinnvoll, eine solide Grundlage für die Entwicklung zu schaffen. Raft ähnelt Paxos, daher erfordert der Vergleich der beiden eine kurze Beschreibung, wie Raft den Paxos-Prozess vereinfacht.

Raft verwendet ein Leader- und Follower-Modell, das auf der Annahme basiert, dass ein Knotencluster nur einen gewählten Leader hat. Der Leiter verwaltet die Protokollreplikation auf den teilnehmenden Knoten und wird ersetzt, sobald sie fehlschlägt oder die Verbindung trennt.

Ein Führer wird auch gewählt, wenn der Algorithmus beginnt. Um der Auswahl von Führungskräften einen gewissen Kontext zu geben, spielt sie eine wichtige Rolle im Konsens und ist in bestimmten Algorithmen unterscheidbar. Zum Beispiel wird in Nakamoto Proof of Work die Auswahl der Führungskräfte durch den lotterieähnlichen Abbauprozess für jede Runde erreicht, der ungefähr alle 10 Minuten stattfindet. In der praktischen byzantinischen Fehlertoleranz (pBFT) erfolgt die Auswahl der Leiter über ein Round-Robin-Format.

Was ist Nakamoto-Konsens?

Lesen Sie: Was ist Nakamoto-Konsens??

Raft wählt den Anführer durch einen Prozess aus, der von einem Kandidatenknoten initiiert wird. Wenn Kandidaten während einer als Wahlzeitüberschreitung, dann stimmen sie für sich selbst, nachdem sie ihre erhöht haben Termzähler und senden Sie es an die anderen Knoten. Kandidaten werden zu Anhängern anderer Kandidaten, deren Amtszeit mindestens so groß ist wie ihre, und dieser Welleneffekt setzt sich zwischen den Knoten fort, bis ein Kandidat die Mehrheit der Anhänger erhält.

Der Leader steuert die Protokollreplikation zwischen den Knoten, auf denen er die Clientanforderungsbefehle an seine Follower sendet. Wenn die Mehrheit der Follower die Replikation bestätigt, wird die Anforderung festgeschrieben. Follower wenden die Commits auch auf ihre lokalen Zustandsautomaten an.

Raft behält die Fehlertoleranz von Knoten bei, die einem Ausfall oder einem Führungsfehler unterliegen, indem ein neuer Leiter seine Anhänger zwingt, seine eigenen Protokolle zu duplizieren. Alle Einträge, die nicht miteinander übereinstimmen, werden gelöscht, um die Konsistenz der Protokollreplikation zu gewährleisten.

Leader-Kandidaten müssen über ein aktuelleres Protokoll verfügen als Follower-Protokolle. Wenn das Protokoll eines Kandidaten weniger aktuell ist als ein potenzieller Follower (in diesem Zusammenhang ein Wähler), wird der Kandidat abgelehnt.

Insgesamt zerlegt Raft den Konsens in drei einzelne Unterprobleme:

  1. Führerwahl
  2. Protokollreplikation
  3. Sicherheit

Das Konsensprotokoll verwendet a starker Führer, Dies bedeutet, dass der Führungsknoten in Raft einen erheblichen Einfluss auf den Prozess ausübt und gleichzeitig durch die Grenzen des Protokolls eingeschränkt bleibt. Infolgedessen ist Raft einfacher im Design als Paxos.

Fazit

Paxos und Raft sind wichtige Konsensprotokolle, die Kernkomponenten des größeren verteilten Fehlertoleranz-Ökosystems sind. Obwohl in Kryptowährungen nicht direkt verwendet, leiten die in Kryptowährungsnetzwerken verwendeten Konsensprotokolle viele ihrer charakteristischen Annahmen aus dem Design von Paxos und Raft ab.