Kann ein Akzeptor in Paxos einen anderen Wert akzeptieren, nachdem er bereits einen akzeptiert hat?

https://stackoverflow.com/questions/5893944

29-10-2019
|

Frage

Betrachten Sie im Multi-Paxos-Algorithmus diesen Nachrichtenfluss aus der Sicht eines Akzeptors:

empfangen: Vorbereiten (N)

Antwort: Versprechen (N, null)

empfangen: Akzeptieren! (N, V1)

Antwort: Akzeptiert (N, V1)

empfangen: Akzeptieren! (N + 1, V2)

Antwort :?

Wie sollte der Akzeptor in diesem Fall gemäß dem Protokoll reagieren?Sollte es mit Akzeptiert antworten (N + 1, V2) oder sollte es das zweite Akzeptieren ignorieren?

Ich glaube, dass dieser Fall in Multi-Paxos auftreten kann, wenn ein zweiter Antragsteller online geht und glaubt, dass er der Anführer ist (und immer war), daher sendet er seine Annahme ohne Vorbereitung.Oder wenn sein Prepare den Akzeptor einfach nicht erreicht hat.Wenn dieser Fall nicht auftritt, können Sie erklären, warum?

Lösung

Ich bin mit beiden anderen Antworten nicht einverstanden.

Multi-Paxos sagt nicht , dass der Führer der einzige Antragsteller ist; Dies würde dazu führen, dass das System einen einzigen Fehlerpunkt hat. Selbst während Netzwerkpartitionen kann das System möglicherweise keine Fortschritte erzielen. Multi-Paxos ist eine Optimierung, mit der ein einzelner Knoten (der Leader ) einige Vorbereitungsphasen überspringen kann. Andere Knoten, die glauben, der Anführer sei tot, versuchen möglicherweise, die Instanz in ihrem Namen fortzusetzen, müssen jedoch weiterhin das vollständige Basic-Paxos-Protokoll verwenden.
Das Nacking der Akzeptanznachricht verstößt gegen den Paxos-Algorithmus. Ein Akzeptor sollte alle Werte akzeptieren, es sei denn, er hat versprochen, sie nicht zu akzeptieren. (Ignorieren ist zulässig, wird jedoch nicht empfohlen. Dies liegt nur daran, dass verworfene Nachrichten zulässig sind.)
Hierfür gibt es auch eine elegante Lösung. Das Problem liegt in der runden Nummer des Anführers (N + 1 in der Frage).
Hier einige Annahmen:

Sie haben ein Schema, bei dem runde IDs über alle Knoten hinweg disjunkt sind (von Paxos ohnehin erforderlich).
Sie haben eine Möglichkeit zu bestimmen, welcher Knoten der Leader pro Paxos-Instanz ist (erforderlich für Multi-Paxos). Der Leader kann von einer Paxos-Instanz zur nächsten wechseln.
Nebenbei: Das Teilzeitparlament schlägt vor, dass der Anführer eine frühere Paxos-Instanz gewinnt (Abschnitt 3.1) und weist darauf hin, dass er Anführer bleiben kann, solange er lebt oder der reichste ist (Abschnitt 3.3.1). Ich habe einen expliziten ELECT_NEW_LEADER: -Wert, der über Paxos vorgeschlagen wird.
Der Anführer überspringt die Vorbereitungsphase nur in der ersten Runde pro Instanz. und verwendet in den folgenden Runden volle Basic Paxos.
Mit diesen Annahmen ist die Lösung sehr einfach. Der Anführer wählt lediglich eine wirklich niedrige runde ID für die anfängliche Akzeptanzphase aus. Diese ID (die ich INITIAL_ROUND_ID nennen werde) kann beliebig lang sein, solange sie niedriger ist als die runden IDs aller Knoten. Abhängig von Ihrem ID-Auswahlschema funktionieren entweder -1, 0 oder Integer.MIN_VALUE.
Es funktioniert, weil ein anderer Knoten (ich nenne ihn Stewart) das vollständige Paxos-Protokoll durchlaufen muss, um etwas vorzuschlagen, und seine runde ID ist immer größer als INITIAL_ROUND_ID . Es sind zwei Fälle zu berücksichtigen: ob die Annahme-Nachrichten des Anführers einen der Knoten erreicht haben, die die Vorbereitungsnachricht von Stewart ausgeführt hat oder nicht.
Wenn die Akzeptanzphase des Anführers keine Knoten erreicht hat, erhält der Stewart in keinem Versprechen einen Wert zurück und kann wie in regulären Basic-Paxos fortfahren.
Und wenn die Akzeptanzphase des Anführers einen Knoten erreicht hat, erhält der Stewart einen Wert in einem Versprechen zurück, mit dem er den Algorithmus wie in Basic-Paxos fortsetzt.
In beiden Fällen führen langsame Akzeptanznachrichten, die ein Knoten vom Leader empfängt, immer zu einem Nack, da die runde ID des Stewart größer als INITIAL_ROUND_ID ist.
Weder für den Akzeptor noch für den Stewart gibt es eine spezielle Logik. Und minimale spezielle Logik auf dem Leader (nämlich eine wirklich niedrige INITIAL_ROUND_ID auswählen).

Beachten Sie, wenn wir die Frage des OP um ein Zeichen ändern, ist die Selbstantwort des OP korrekt: Nack.

erhalten: Vorbereiten (N)
Antwort: Versprechen (N, null)
erhalten: Akzeptieren! (N, V1)
Antwort: Akzeptiert (N, V1)
erhalten: Akzeptieren! ( N-1 , V2)
Antwort: Nack (N, V1)
Aber so wie es aussieht, bricht seine Antwort den Paxos-Algorithmus; es sollte Akzeptieren sein!

erhalten: Bereiten Sie (N) vor
Antwort: Versprechen (N, null)
erhalten: Akzeptieren! (N, V1)
Antwort: Akzeptiert (N, V1)
erhalten: Akzeptieren! ( N + 1 , V2)
Antwort: Akzeptieren! (N + 1, V2)

Andere Tipps

Die Richtigkeit von Multi-Paxos hängt von der Anforderung ab, dass sich der Leiter ( d. h. , Antragsteller) zwischen aufeinanderfolgenden Paxos-Instanzen nicht ändert. Von Das Teilzeitparlament Abschnitt 3.1 (Das Protokoll des Parlaments mit mehreren Dekreten):

Logischerweise ist das parlamentarische Protokoll [a.k.a. Multi-Paxos] verwendet a separate Instanz des vollständigen Synodenprotokolls [a.k.a. Paxos] für jede Dekretnummer. Jedoch, ein einzelner Präsident [a.k.a. Antragsteller / Leiter] wurde für alle diese Fälle ausgewählt und er führte den ersten durch zwei Schritte des Protokolls nur einmal.
_{[Hervorhebung wurde mir hinzugefügt.]}
Daher geht Multi-Paxos davon aus, dass der von Ihnen beschriebene Fall - wenn ein zweiter Antragsteller online geht und glaubt, er sei (und war immer) führend - niemals eintreten wird. Wenn ein solcher Fall auftreten kann, sollte man Multi-Paxos nicht verwenden. In Bezug auf die zweite Möglichkeit - als der Prepare des zweiten Antragstellers den Akzeptor nicht erreichte - bedeutet die Tatsache, dass der zweite Antragsteller bereits einen Accept! gesendet hat, dass er zuvor einen Prepare gesendet hat, der von einem Quorum von Akzeptoren Promised war. Da die Akzeptoren dem ersten Antragsteller bereits einen runden N versprochen haben, muss der Prepare des zweiten Antragstellers vor dem runden N gesendet worden sein. Daher muss der endgültige Accept!(N+1,V2) einen Zähler kleiner als N haben.
Bearbeiten: Es sollte auch beachtet werden, dass diese Version des Protokolls gegenüber Byzantinischer Fehler :

[Das Protokoll des Paxon-Parlaments] toleriert weder willkürliche, böswillige Fehler noch garantiert es eine zeitlich begrenzte Reaktion.
_{- Das Teilzeit-Parlament , Abschnitt 4.1}

Vielleicht ist es einfacher zu beobachten, dass dies der Fall ist, wenn der Befehl Vorbereiten (N + 1) von einer Mehrheit akzeptiert wurde, die den betreffenden Akzeptor nicht enthielt.

Um dies näher zu erläutern: Sobald ein Anführer weiß, dass eine Mehrheit versprochen hat (N + 1), sendet er Akzeptieren (N + 1, x) an alle Akzeptoren.und selbst wenn eine andere Mehrheit der Akzeptoren mit Akzeptiert (N + 1) antwortet, wurde ein Konsens erreicht.

Dies ist kein ungewöhnliches Szenario.

(Beantwortung meiner eigenen Frage.)

Mein derzeitiges Verständnis ist, dass ich den Wert in N + 1 nicht akzeptieren sollte (dh überhaupt nicht antworten oder einen NACK senden), wodurch der Anführer gezwungen wird, möglicherweise eine weitere Runde mit Prepare zu beginnen (wenn die Mehrheit nicht erreicht hatKonsens noch).Nachdem ich Prepare (N + 2) erhalten habe, werde ich mit Promise (N + 2, V1) antworten und wie gewohnt fortfahren.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow