Was ist eine Instanz?
Die Nomenklatur in Paxos ist ein wenig unintuitiv.
- Eine Instanz ist der Algorithmus zur Auswahl eine Wert.
- A rund bezieht sich auf den einzigen Versuch eines Antragstellers, eine Phase 1 + Phase 2 durchzuführen. Ein Knoten kann mehrere Runden in einem Instanz von Paxos. Eine Round-ID ist pro Instanz global über alle Knoten hinweg eindeutig. Dies wird manchmal als Angebotsnummer .
- Ein Knoten kann mehrere Rollen einnehmen, vor allem die des Antragstellers und des Annehmers. In meinen Antworten werde ich davon ausgehen, dass jeder Knoten beide Rollen übernimmt.
- Phase 1 wird auch als Vorbereitungsphase bezeichnet.
- In Phase 1a sendet ein Antragsteller eine Prepare!(roundId)-Nachricht an die Akzeptoren
- In Phase 1b antworten die Akzeptoren entweder mit Promise!(roundId, value) oder PrepareNack!()
- Phase 2 wird auch als Annahmephase bezeichnet.
- In Phase 2a sendet ein Antragsteller eine Accept!(roundId, value) Nachricht an die Akzeptoren
- In Phase 2b antworten die Annehmenden entweder mit Accepted!(...) oder AcceptNack!()
Angenommen, ein Cluster ist in 3 Regionen unterteilt, die jeweils 3 Knoten enthalten (insgesamt = 9 Knoten). Was passiert, wenn die Kommunikation zwischen den Regionen unterbrochen wird? Es gibt keine Möglichkeit, dass ein Anführer das Quorum (5) erreichen kann.
Paxos erfordert, dass Sie mindestens ein Quorum (in Ihrem Fall 5 Knoten) erreichen können. Bleiben Sie bei Ihrer Lösung mit drei Regionen; zwei Netzwerkpartitionen zwischen den drei Regionen zu haben, ist eine sehr schlechte Nachricht. Ich verwende auch eine Version von Paxos, die die Knotenmitgliedschaft von einer Instanz zur nächsten ändern kann. Dies ist nützlich für Partitionen und Knotenausfälle.
Wird Paxos nicht in eine Endlosschleife geraten?
Bei einer naiven Implementierung von Paxos ist die Beendigung nicht garantiert, da mehrere Knoten die Vorbereitungsphasen überspringen können. Es gibt zwei Möglichkeiten, dies zu umgehen. Die eine besteht darin, einen zufälligen Backoff vor dem Start neuer Prepare-Phasen durchzuführen. Die zweite besteht darin, alle Anfragen an einen designierten Leader weiterzuleiten, der als Proposer fungiert (der Leader wird von einer Paxos-Instanz ausgewählt, siehe auch Multi-Paxos).
In Phase 1b: "Wenn die Vorschlagsnummer N größer ist als jeder vorherige Vorschlag, dann verspricht jeder >>Acceptor, keine Vorschläge unter N zu akzeptieren, und sendet den Wert, den er zuletzt für >>diese Instanz akzeptiert hat, an den Proposer".
Was ist "der letzte akzeptierte Wert"? Handelt es sich um eine frühere Vorschlagsnummer des Antragstellers?
Wenn ein Knoten eine Accept!(roundId, value) Nachricht von einem Proposer erhält et nicht versprochen hat, den Wert nicht zu akzeptieren (aufgrund einer Prepare!(higherRoundId)-Meldung), speichert er den Wert und die roundId (ich nenne sie acceptedValue y acceptedRoundId ). Diese werden möglicherweise durch nachfolgende Accept!(...)-Meldungen überschrieben.
Wenn ein Knoten eine Prepare!(roundId)-Nachricht von einem Vorschlagenden erhält, speichert er roundId als promiseRoundId = max(roundId, promiseRoundId) . Es sendet dann eine Promise!(acceptedRoundId, acceptedValue) zurück an den Antragsteller. NB: Wenn ein Knoten keine Accept!(...)-Nachricht erhalten hat, antwortet er mit Promise!(null, null) .
In Phase 1a: Wird der zu vereinbarende Wert in die Prepare-Nachricht aufgenommen oder wird dies auf die Accept!-Nachricht verschoben? Oder spielt es doch eine Rolle?
Es ist nicht notwendig, sie zu versenden. Ich tue es nicht.
In Phase 2a: "Wenn einer der Annehmenden bereits einen Wert angenommen hat, muss der Anführer einen Wert mit der maximalen Vorschlagszahl N wählen".
Was ist hier der Wert? Ist es die Vorschlagsnummer? Ich glaube nicht, aber diese Formulierung ist unklar.
Der Wert ist die tatsächliche Datenmenge, über die der Algorithmus einen Konsens erzielt. Ich formuliere das um in
Um die Annahmephase zu beginnen, muss der Vorschlagende einen Wert wählen, der je nach den Ergebnissen der Vorbereitungsphase angenommen wird. Wenn ein Akzeptor mit Promise(roundId, value) geantwortet hat, muss der Vorschlagende den Wert mit der höchsten roundId verwenden. Andernfalls hat der Antragsteller nur Promise(null, null) erhalten und kann einen beliebigen Wert wählen, den er an die Akzeptoren sendet.
NB: Die Vorschlagsnummer ist gleichbedeutend mit roundId.
In Phase 2a: "Andernfalls steht es dem Antragsteller frei, einen beliebigen Wert zu wählen". Was ist damit gemeint? Ein Wert für was? Für die Vorschlagsnummer?
Dies ist der Wert, über den Sie einen Konsens erzielen wollen. Dabei handelt es sich in der Regel um eine Zustandsänderung im verteilten System, die vielleicht durch eine Kundenanfrage ausgelöst wird.
Paxos scheint sich auf einen steigenden Wert von N (Vorschlagsnummer) zu verlassen, um zu funktionieren? Ist dies korrekt?
Der Wikipedia-Eintrag diskutiert nicht die Anfangswerte, die ein Knoten setzen sollte, bevor er an Paxos teilnimmt. Wie lauten diese?
Runde IDs (auch Vorschlagsnummern genannt) s steigend sein und muss pro Instanz über alle Knoten hinweg eindeutig sein. Das Paxos-Papier geht davon aus, dass Sie dies tun können, weil es trivial ist, dies zu erreichen. Hier ist ein Schema, das auf allen Knoten die gleichen Ergebnisse liefert:
- Angenommen, es gibt M Knoten, die an einer Instanz von Paxos teilnehmen.
- Sortiert alle Knoten lexikografisch. index[node] ist der Index eines Knotens in dieser sortierten Liste.
roundId = i*M + index[node] wobei i die i-te Runde ist, die dieser Knoten beginnt (d.h. i ist pro Knoten pro Paxos-Instanz eindeutig und monoton steigend).
Oder in Pseudocode (der eindeutig einige wichtige Optimierungen vermissen lässt):
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
}
}
