Fragen zur Implementierung von Paxos

StackOverflow https://stackoverflow.com/questions/5850487

  •  27-10-2019
  •  | 
  •  

Frage

Ich implementiere Paxos in einer Cluster -Simulatoranwendung unter Verwendung der in verfügbaren Dokumentation in Wikipedia. Leider bleibt mehrere Türen für die Interpretation offen und liefert nicht viele Informationen zu wichtigen Implementierungsproblemen. Es ist unklar und unvollständig.

  • Angenommen, ein Cluster geteilt in 3 Regionen, die jeweils 3 Knoten (insgesamt = 9 Knoten) enthalten. Was passiert, wenn die Kommunikation zwischen Regionen gebrochen ist? Es gibt keine Möglichkeit, dass ein Führer Quorum erreichen kann (was 5 ist).

Geht Paxos nicht in eine unendliche Schleife? Ich denke, man sollte Paxos nicht initiieren, wenn man nicht mit mindestens einem Quorum von Knoten kommunizieren kann.

  • In Phase 1B: 'Wenn die Vorschlagsnummer N größer ist als jeder frühere Vorschlag, verspricht jeder Akzeptor, keine Vorschläge weniger als N zu akzeptieren, und sendet keine Der Wert, den es zuletzt akzeptiert hat zum Diese Instanz zum Antragsteller'.

Was ist "der letzte Wert, den es akzeptiert"? Ist es eine vorherige Vorschlagsnummer des Antragstellers? Was bezieht sich "Instanz" genau in diesem Fall?

  • In Phase 1A: Fügen Sie einen den Wert ein, der sich der Vorbereitung der Vorbereitung einverstanden macht, oder ist dies auf die Akzeptanz verschoben! Botschaft? Oder ist es wichtig?

  • In Phase 2a: 'Wenn einer der Akzeptoren bereits einen Wert akzeptiert hat, muss der Führer Wählen Sie einen Wert mit der maximalen Vorschlagsnummer n'.

Was ist der Wert hier? Ist es die Vorschlagsnummer? Ich glaube nicht, aber dieser Satz ist unklar.

  • In Phase 2A: "Ansonsten kann der Antragsteller einen Wert aus auswählen". Was bedeutet das? Ein Wert für was? Für die Vorschlagsnummer?

  • Paxos scheint auf einen zunehmenden Wert von N (Vorschlagsnummer) zu arbeiten, um zu arbeiten? Ist das richtig?

  • In dem Wikipedia -Eintrag werden die Anfangswerte, die ein Knoten festgelegt hat, nicht diskutiert, bevor sie an Paxos teilnehmen. Was ist das?

PS: Ich habe nicht genug Ruf, um ein 'Paxos' Tag zu erstellen (irgendein Freiwilliger?)

War es hilfreich?

Lösung

Was ist eine Instanz?

Die Nomenklatur in Paxos ist etwas unintuitiv.

  • Ein Beispiel ist der Algorithmus für die Wahl eines Wert.
  • EIN runden bezieht sich auf den einzelnen Versuch eines Antragstellers einer Phase 1 + Phase 2. Ein Knoten kann mehrere haben Runden in einem (n Beispiel von Paxos. Eine runde ID ist weltweit einzigartig pro Instanz über alle Knoten. Dies wird manchmal genannt Vorschlagsnummer.
  • Ein Knoten kann mehrere Rollen übernehmen; Vor allem Antragsteller und Akzeptor. In meinen Antworten gehe ich davon aus, dass jeder Knoten beide Rollen übernimmt.
  • Phase 1 ist auch als Vorbereitungsphase bekannt.
    • In Phase 1A sendet ein Antragsteller eine Meldung vorbereiten! (Roundid) an die Akzeptoren
    • In Phase 1B antworten die Akzeptoren entweder mit Versprechen! (Roundid, Wert) oder Preparenack! ()
  • Phase 2 ist auch als Akzeptanzphase bekannt.
    • In Phase 2A sendet ein Antragsteller eine Akzeptanz! (Roundid, Wert) Meldung an die Akzeptoren
    • In Phase 2b antworten die Akzeptoren entweder mit akzeptiertem! (...) oder Acceptnack! ()

Angenommen, ein Cluster geteilt in 3 Regionen, die jeweils 3 Knoten (insgesamt = 9 Knoten) enthalten. Was passiert, wenn die Kommunikation zwischen Regionen gebrochen ist? Es gibt keine Möglichkeit, dass ein Führer Quorum erreichen kann (was 5 ist).

Paxos verlangt, dass Sie mindestens ein Quorum erhalten können (5 Knoten in Ihrem Fall). Gehen Sie mit Ihrer Lösung von drei Regionen; Es ist eine sehr schlechte Nachricht, zwei Netzwerkpartitionen zwischen den drei Regionen zu haben. Ich verwende auch eine Version von Paxos, die die Knotenmitglieds von einer Instanz zum nächsten ändern kann. Dies ist nützlich für Partitionen und Knotenfehler.

Geht Paxos nicht in eine unendliche Schleife?

Eine naive Implementierung von Paxos wird nicht garantiert, da mehrere Knoten Phasen vorbereiten können. Es gibt zwei Möglichkeiten, dies umzugehen. Eine davon ist, eine zufällige Backoffs zu haben, bevor Sie neue Vorbereitungsphasen starten. Die zweite besteht darin, alle Anfragen an einen ausgewiesenen Führer weiterzuleiten, der als Antragsteller fungiert (der Führer wird von einer Paxos-Instanz ausgewählt. Siehe auch Multi-Paxos).

In Phase 1B: "Wenn die Vorschlagsnummer n größer als jeder frühere Vorschlag ist, verspricht jeder >> Akzeptor, keine Vorschläge weniger als n zu akzeptieren, und sendet den Wert, den er zuletzt für >> diese Instanz an den Antragsteller akzeptiert."

Was ist "der letzte Wert, den es akzeptiert"? Ist es eine vorherige Vorschlagsnummer des Antragstellers?

Wenn ein Knoten eine Nachricht von Accept! (Roundid, Wert) von einem Antragsteller erhält und Es hat nicht versprochen, den Wert (aufgrund einer Vorbereitung! (Ausstieg) nicht zu akzeptieren, sondern speichert den Wert und den Roundid (ich werde sie anrufen acceptedValue und acceptedRoundId). Es kann über diese aufgrund der nachfolgenden Akzeptanznachrichten schreiben! (...) Nachrichten.

Wenn ein Knoten eine Meldung vorbereiten! (Roundid) von einem Antragsteller erhält, speichert er Roundid als promiseRoundId = max(roundId, promiseRoundId). Es sendet dann a Promise!(acceptedRoundId, acceptedValue) Zurück zum Antragsteller. NB: Wenn ein Knoten keine Akzeptanz erhalten hat! (...) Nachricht, antwortet er mit Promise!(null, null).

In Phase 1A: Fügen Sie einen den Wert ein, der sich der Vorbereitung der Vorbereitung einverstanden macht, oder ist dies auf die Akzeptanz verschoben! Botschaft? Oder ist es wichtig?

Es ist nicht erforderlich, es zu senden. Ich tu nicht.

In Phase 2A: "Wenn einer der Akzeptoren bereits einen Wert akzeptiert hat, muss der Leiter einen Wert mit der maximalen Vorschlagsnummer n 'wählen.

Was ist der Wert hier? Ist es die Vorschlagsnummer? Ich glaube nicht, aber dieser Satz ist unklar.

Der Wert sind die tatsächlichen Daten, auf die der Algorithmus einen Konsens erzielt. Ich werde das umformeln

Um die Akzeptanzphase zu starten, muss der Antragsteller einen Wert auswählen, der je nach den Ergebnissen der Vorbereitungsphase akzeptiert wird. Wenn ein Akzeptor mit Versprechen (RoundID, Wert) antwortete, muss der Antragsteller den Wert verwenden, der mit dem höchsten Roundid verbunden ist. Andernfalls erhielt der Antragsteller nur ein Versprechen (Null, Null) und kann einen Wert auswählen, um an die Akzeptoren zu senden.

NB: Die Vorschlagsnummer hier ist dasselbe wie bei Roundid.

In Phase 2A: "Ansonsten kann der Antragsteller einen Wert aus auswählen". Was bedeutet das? Ein Wert für was? Für die Vorschlagsnummer?

Dies ist der Wert, den Sie Konsens haben möchten. Dies ist in der Regel eine Zustandsänderung über das verteilte System, das möglicherweise durch eine Client -Anfrage ausgelöst wird.

Paxos scheint auf einen zunehmenden Wert von N (Vorschlagsnummer) zu arbeiten, um zu arbeiten? Ist das richtig?

In dem Wikipedia -Eintrag werden die Anfangswerte, die ein Knoten festgelegt hat, nicht diskutiert, bevor sie an Paxos teilnehmen. Was ist das?

Runde IDs (auch bekannt als Vorschlagsnummern) sollte zunehmen und muss Seien Sie einzigartig pro Instanz über alle Knoten. Das Paxos -Papier geht davon aus, dass Sie dies tun können, weil es trivial ist. Hier ist ein Schema, das auf allen Knoten die gleichen Ergebnisse erzielt:

  1. Angenommen, es gibt M -Knoten, die an einer Instanz von Paxos teilnehmen.
  2. Sortieren Sie alle Knoten lexikographisch. Index [Knoten] ist der Index eines Knotens in dieser sortierten Liste.
  3. roundId = i*M + index[node] Wo ich der Rund um diesen Knoten ist, beginnt (das heißt, ich bin einzigartig pro Knoten pro Paxos -Instanz und nimmt monoton zu).

Oder in Pseudo-Code (was eindeutig einige wichtige Optimierungen fehlt):

define runPaxos( allNodesThisPaxosInstance, myValue ) {
    allNodesThisPaxosInstance.sort()
    offset = allNodesThisPaxosInstance.indexOf( thisNode )
    for (i = 0; true; i++) {
        roundId = offset + i * allNodesThisPaxosInstance.size()
        prepareResult = doPreparePhase( roundId )

        if (!prepareResult.shouldContinue?)
            return

        if (prepareResult.hasAnyValue?)
           chosenValue = prepareResult.valueWithHighestRoundId
        else
            chosenValue = myValue

        acceptResult = doAcceptPhase( roundId, chosenValue )

        if (!acceptResult.shouldContinue?)
            return
    }
}

Andere Tipps

Ich habe Folgendes gefunden dokumentieren Erklären Sie Paxos näher. Ich habe den Wikipedia -Eintrag entsprechend aktualisiert.

Die Antworten auf meine Frage, die ich finden konnte, sind:

Geht Paxos nicht in eine unendliche Schleife?

Paxos funktioniert nur, wenn mindestens ein Quorum von Knoten miteinander kommunizieren kann (in unserem Fall 5). Wenn ein Knoten daher nicht mit mindestens einem Quorum von Knoten kommunizieren kann, sollte er Paxos nicht versuchen.

Was ist "der letzte Wert, den es akzeptiert"?

Es ist die zuletzt akzeptierte Satzzahl und den entsprechenden Wert.

Was bezieht sich "Instanz" genau in diesem Fall?

Es bezieht sich auf den Akzeptor.

Enthält man den Wert, der mit der Vorbereitung der Nachricht einverstanden ist, oder wird dies auf die Akzeptanz verschoben! Botschaft? Oder ist es wichtig?

Der Wert ist nicht in der Meldung vorbereiten, sondern wird der Anforderungsnachricht überlassen.

Was ist der Wert hier? Ist es die Vorschlagsnummer? Ich glaube nicht, aber dieser Satz ist unklar.

"Andernfalls kann der Antragsteller einen Wert auswählen". Was bedeutet das? Ein Wert für was? Für die Vorschlagsnummer?

Wenn Akzeptoren bereits einen Vorschlag des Antragstellers akzeptiert haben, können sie die entsprechende Vorschlagsnummer und den Wert zurückgeben, sonst nichts.

Die zweite Frage fällt, da der Wikipedia -Eintrag irreführend war. Man kann einen willkürlichen Wert für einen bestimmten Vorschlag auswählen oder ihn aus Werten ableiten, die zuvor angenommene Vorschläge entsprechen.

Paxos scheint auf einen zunehmenden Wert von N (Vorschlagsnummer) zu arbeiten, um zu arbeiten? Ist das richtig?

Ja. Ein Antragsteller P muss seine Vorschläge zunehmend zählen.

In dem Wikipedia -Eintrag werden die Anfangswerte, die ein Knoten festgelegt hat, nicht diskutiert, bevor sie an Paxos teilnehmen. Was ist das?

Knoten sollten ihre letzte akzeptierte Vorschlagsnummer und schließlich auch den entsprechenden Wert behalten. Sie sollten es bestehen. Wenn Sie sich zum ersten Mal anschließen, sollte die anfängliche Vorschlagsnummer für einen bestimmten Antragsteller null (oder ein Äquivalent) sein.

Paxos seems to rely on an increasing value of N (proposal number) to work? Is this correct?

Jeder Antragsteller verfügt über einen stabilen Speicher. Jeder Antragsteller erinnert sich (in stabiler Speicherung) an den höchsten Vorschlag, den er ausgestellt hat, und beginnt Phase 1 mit einer höheren Vorschlagszahl als alle bereits verwendeten.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top