Paxos made simple

TL; DR:

Paxos ist ein Protokoll, das das Problem löst, dass eine Gruppe von Knoten sich auf einen einzelnen Wert einigen oder einen Konsens erzielen muss.

Zusammenfassung:

In diesem Artikel stellt der Autor Paxos vor, einen fehlertoleranten Algorithmus, der verwendet wird, um einen Konsens zwischen einer Sammlung von Computern im asynchronen und nicht-byzantinischen Modell zu erreichen.

Das Problem des Konsenses besteht darin, eine Sammlung von Computern dazu zu bringen, eine Sache so zu entscheiden, als wären sie ein Computer. Der Hauptunterschied zwischen Konsens- und anderen Vereinbarungsproblemen besteht darin, dass Konsensusprotokolle fehlertolerant sein müssen, was bedeutet, dass es keinen einzigen Fehlerpunkt gibt. Im Gegensatz dazu kann bei Protokollen wie dem zweiphasigen Commit, wenn der Koordinator abstürzt, das gesamte System möglicherweise keine Fortschritte erzielen. Wenn es einen stabilen Anführer gibt, wird der Konsens trivial, da der Anführer selbst eine Gesamtordnung über alle Operationen festlegen und andere Knoten ihm folgen lassen kann. Das Versagen des Führers wird jedoch verhindern, dass das System Fortschritte macht. Darüber hinaus, wenn der Führer Wahlalgorithmus fehlschlägt (was wahrscheinlich im Falle einer Netzwerkpartition passieren wird), könnte es mehrere Führer existieren und verletzt Vereinbarung Eigentum.

Das Papier definiert drei Klassen von Agenten:

1.Proposers (Knoten, die Wert vorschlagen) 2.Akzeptoren(merken Sie sich die vorgeschlagenen Werte) 3.Lernende(entdecken Sie die gewählten Werte).

Dann beschreibt es die folgenden fehlgeschlagenen Versuche, den Konsens zu lösen:

1.Einzelakzeptor-Agent(als Anführer fungieren). Unbefriedigend wegen des Single Point of Failure. 2.Mehrere Akzeptor-Agenten. -acceptors akzeptieren den ersten Wert, den sie erhalten -ein Wert wird gewählt, wenn er von einer Mehrheit akzeptiert wird Acceptors Unbefriedigend, weil wir leicht Fälle konstruieren können, in denen kein Wert von einer Mehrheit von Accepts akzeptiert wird, was gegen die Kündigung verstößt. 3. Akzeptieren Sie mehr als einen Wert unbefriedigend, da die Nachricht möglicherweise nicht in der richtigen Reihenfolge zugestellt wird und gegen die Vereinbarung verstößt.

Paxos-Algorithmus:

Vorbereitungsphase:

Für den Antragsteller wird eine neue Vorschlagsnummer n ausgewählt und eine Vorbereitungsanforderung (einschließlich n) an die Akzeptanten gesendet. Für Acceptor vergleicht es n mit dem akzeptierten Vorschlag mit der höchsten Zahl. Wenn n größer ist, sendet der Akzeptor ein Versprechen zurück, diesem Antragsteller zu folgen, und den Vorschlag mit der höchsten Nummer (und den mit dem Vorschlag verbundenen Wert), den er akzeptiert hat, falls vorhanden.

Akzeptierungsphase:

Nachdem der Antragsteller Antworten von einer Mehrheit der Akzeptanten erhalten hat, sendet der Antragsteller eine Akzeptieranforderung an alle Akzeptanten. Die Accept-Nachricht enthält die Vorschlagsnummer und einen Wert (den Wert des am höchsten nummerierten Vorschlags oder einen beliebigen Wert, wenn alle Akzeptoren keine Antwort erhalten). Wenn ein Akzeptor eine Accept-Anforderung empfängt, akzeptiert er die Anforderung, wenn die Vorschlagsnummer größer oder gleich dem am höchsten nummerierten Vorschlag ist, den er akzeptiert hat. Schließlich, wenn eine Accept-Anforderung von einer Mehrheit der Akzeptanten akzeptiert wird. Der Vorschlag wird ausgewählt(oder entschieden).

Hinweis: 1.Der Akzeptor muss sich an den Vorschlag mit der höchsten Nummer erinnern, den er akzeptiert hat, falls vorhanden, auch wenn er fehlschlägt und wiederhergestellt wird. Der Antragsteller kann seine Vorschläge vergessen, solange er niemals versucht, einen anderen Vorschlag mit derselben Vorschlagsnummer 2 zu unterbreiten.Die Vorschlagsnummer muss global eindeutig und monoton ansteigend sein 3.“Dueling proposers problem“.

Wenn zwei Antragsteller gleichzeitig vorschlagen möchten, können sie versuchen, sich gegenseitig zu blockieren, indem sie Vorschläge mit einer größeren Anzahl als dem vorherigen Vorschlag unterbreiten. Diese Situation könnte ewig andauern und die Kündigung verletzen. Mögliche Lösungen sind Führer Wahl und zufällige Backoff.

Frage:

1. Was ist der Leader-Wahlalgorithmus in Abschnitt 3?

2.Das Papier stellt mehrere Optimierungen vor, erklärt jedoch nicht, warum und wie diese die Leistung von Paxos

verbessern3.As Als ich das Papier las, hatte ich das Gefühl, dass Paxos ohne weitere Optimierungen zu schwierig oder zu kostspielig zu implementieren wäre

4.Die Annahme, dass die Nachrichten nicht beschädigt werden können, scheint zu stark zu sein

5.Das Papier scheint etwas unvollständig. 1.it geht nicht auf das oben beschriebene Problem der duellierenden Antragsteller sowie auf die Lösung ein. 2. Wie wählt man die Vorschlagsnummer, um sie global einzigartig und monoton steigend zu machen? 3.Was ist mit Membership Management?

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht.