Domande sull'implementazione di Paxos

Question

Sto implementando Paxos in un'applicazione del simulatore cluster, utilizzando la documentazione disponibile in Wikipedia. Sfortunatamente, lascia diverse porte aperte all'interpretazione e non fornisce molte informazioni sui problemi di implementazione chiave. Non è chiaro e incompleto.

• Supponendo un cluster diviso in 3 regioni, ciascuna contenente 3 nodi (totale = 9 nodi). Cosa succede se la comunicazione è spezzata tra le regioni? Non è possibile che nessun leader possa raggiungere il quorum (che è 5).

Paxos non entrerà in un ciclo infinito? Immagino che non si dovrebbe iniziare Paxos se non si può comunicare con almeno un quorum di nodi.

• Nella fase 1b: "Se il numero di proposta n è maggiore di qualsiasi proposta precedente, ogni accettore promette di non accettare proposte inferiori a n e invia il valore che ha accettato l'ultima volta per questa istanza al proponente'.

Qual è "l'ultimo valore accettato"? È un numero di proposta precedente dal proponente? A cosa si riferisce esattamente in questo caso "istanza"?

• Nella Fase 1A: si include il valore da concordare con il messaggio di preparazione o è differito all'Accetto! Messaggio? O è importante?

• Nella fase 2A: "Se qualcuno degli accettori ha già accettato un valore, il leader deve Scegli un valore con il numero di proposta massimo n'.

Qual è il valore qui? È il numero di proposta? Non credo, ma questa frase non è chiara.

• Nella fase 2A: "Altrimenti, il proponente è libero di scegliere qualsiasi valore". Cosa significa questo? Un valore per cosa? Per il numero di proposta?

• Paxos sembra fare affidamento su un valore crescente di N (numero di proposta) per funzionare? È corretto?

• La voce di Wikipedia non discute i valori iniziali che un nodo dovrebbe impostare prima di iniziare a partecipare a Paxos. Cosa sono questi?

PS: non ho abbastanza reputazione per creare un tag "paxos" (qualsiasi volontario?)

Answer 1

Cos'è un'istanza?

La nomenclatura in Paxos è un po 'non intuitiva.

• Un esempio è l'algoritmo per la scelta uno valore.
• UN il giro si riferisce al singolo tentativo di un proponente di fase 1 + fase 2. Un nodo può avere più round in un esempio di paxos. Un ID rotondo è unica globale per istanza in tutti i nodi. Questo a volte viene chiamato Numero di proposta.
• Un nodo può assumere diversi ruoli; in particolare il proponente e l'accettore. Nelle mie risposte, suppongo che ogni nodo assumi entrambi i ruoli.
• La fase 1 è anche nota come fase di preparazione.
  • Nella fase 1a, un proponente invia un messaggio prepara! (Roundid) agli accettori
  • Nella fase 1b, gli accettori rispondono con una promessa! (Roundid, Value) o Preparenack! ()
• La fase 2 è anche nota come fase di accettazione.
  • Nella Fase 2A, un proponente invia un messaggio accetta! (Roundid, Value) agli accettori
  • Nella fase 2b, gli accettori rispondono con accettato! (...) o accettano! ()

Supponendo un cluster diviso in 3 regioni, ciascuna contenente 3 nodi (totale = 9 nodi). Cosa succede se la comunicazione è spezzata tra le regioni? Non è possibile che nessun leader possa raggiungere il quorum (che è 5).

Paxos richiede che tu possa ottenere almeno un quorum (5 nodi nel tuo caso). Vai con la tua soluzione di tre regioni; Avere due partizioni di rete tra le tre regioni è una brutta notizia. Uso anche una versione di Paxos che può modificare l'appartenenza al nodo da un'istanza all'altra. Ciò è utile per partizioni e guasti al nodo.

Paxos non entrerà in un ciclo infinito?

Un'implementazione ingenua di Paxos non è garantita per terminare perché più nodi possono saltare le fasi. Ci sono due modi per aggirare questo. Uno è avere un backoff casuale prima di iniziare nuove fasi di preparazione. Il secondo è quello di instradare tutte le richieste a un leader designato, che funge da proponente (il leader è scelto da un'istanza Paxos. Vedi anche Multi-Paxos)

Nella fase 1b: 'Se il numero di proposta n è maggiore di qualsiasi proposta precedente, ciascun accettore >> promette di non accettare proposte inferiori a n e invia il valore che ha accettato l'ultima volta per >> in questa istanza al proponente'.

Qual è "l'ultimo valore accettato"? È un numero di proposta precedente dal proponente?

Quando un nodo riceve un messaggio accetta! (Roundid, valore) da un proponente e Non ha promesso di non accettare il valore (a causa di un messaggio prepara! acceptedValue e acceptedRoundId). Può scrivere su questi a causa dei successivi messaggi di accettazione! (...).

Quando un nodo riceve un messaggio Prepara! (Roundid) da un proponente, memorizza Roundid come promiseRoundId = max(roundId, promiseRoundId). Quindi invia un file Promise!(acceptedRoundId, acceptedValue) Torna al proponente. NB: Se un nodo non ha ricevuto un messaggio accetta! (...), risponde con Promise!(null, null).

Nella Fase 1A: si include il valore da concordare con il messaggio di preparazione o è differito all'Accetto! Messaggio? O è importante?

Non è necessario inviarlo. Io non.

Nella fase 2A: "Se qualcuno degli accettori ha già accettato un valore, il leader deve scegliere un valore con il numero di proposta massimo n '.

Qual è il valore qui? È il numero di proposta? Non credo, ma questa frase non è chiara.

Il valore sono i dati effettivi su cui l'algoritmo sta raggiungendo il consenso. Lo riformerò a questo

Per iniziare la fase di accettazione, il proponente deve scegliere un valore da accettare a seconda dei risultati della fase di preparazione. Se un accettore ha risposto con promessa (rotonda, valore), il proponente deve utilizzare il valore associato al roundid più alto. Altrimenti, il proponente ha ricevuto solo promesse (null, null) e può scegliere qualsiasi valore da inviare agli accettori.

NB: il numero di proposta qui è la stessa cosa di Roundid.

Nella fase 2A: "Altrimenti, il proponente è libero di scegliere qualsiasi valore". Cosa significa questo? Un valore per cosa? Per il numero di proposta?

Questo è il valore su cui vuoi avere consenso. Questo è in genere una modifica dello stato attraverso il sistema distribuito, forse attivato da una richiesta del client.

Paxos sembra fare affidamento su un valore crescente di N (numero di proposta) per funzionare? È corretto?

La voce di Wikipedia non discute i valori iniziali che un nodo dovrebbe impostare prima di iniziare a partecipare a Paxos. Cosa sono questi?

ID rotondi (alias Numeri di proposta) dovrebbe essere in aumento e dovere Sii unico per istanza in tutti i nodi. Il documento di Paxos presuppone che tu possa farlo perché è banale da raggiungere. Ecco uno schema che produce gli stessi risultati su tutti i nodi:

1. Supponiamo che ci siano m nodi che partecipano a un'istanza di paxos.
2. Ordina tutti i nodi lessicograficamente. L'indice [nodo] è l'indice di un nodo in questo elenco ordinato.
3. roundId = i*M + index[node] dove io è il giro di questo nodo (cioè sono unico per nodo per istanza di paxos ed è monotonicamente in aumento).

O in pseudo-codice (che manca chiaramente alcune grandi ottimizzazioni):

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
    }
}

Answer 2

Ho trovato quanto segue documento Spiegare Paxos in maggiori dettagli. Ho aggiornato la voce di Wikipedia di conseguenza.

Le risposte alla mia domanda che potrei trovare sono:

Paxos non entrerà in un ciclo infinito?

Paxos funziona solo se almeno un quorum di nodi può comunicare tra loro (nel nostro caso 5). Quindi, se un nodo non può comunicare con almeno un quorum di nodi, non dovrebbe provare Paxos.

Qual è "l'ultimo valore accettato"?

È l'ultimo numero di proposizione accettata e valore corrispondente.

A cosa si riferisce esattamente in questo caso "istanza"?

Si riferisce all'accettore.

Uno include il valore da concordare con il messaggio di preparazione o è differito all'Accetta! Messaggio? O è importante?

Il valore non è incluso nel messaggio di preparazione, viene lasciato al messaggio di richiesta accetta.

Qual è il valore qui? È il numero di proposta? Non credo, ma questa frase non è chiara.

"Altrimenti, il proponente è libero di scegliere qualsiasi valore". Cosa significa questo? Un valore per cosa? Per il numero di proposta?

Se gli accettori hanno già accettato una proposta dal proponente, possono restituire il numero e il valore della proposta corrispondenti, altrimenti nulla.

La seconda domanda cade, poiché la voce di Wikipedia è stata fuorviante. Si può scegliere un valore arbitrario per una data proposta o derivarlo da valori corrispondenti alle proposte accettate in precedenza.

Paxos sembra fare affidamento su un valore crescente di N (numero di proposta) per funzionare? È corretto?

Sì. Un proponente P deve numerare le sue proposte sempre più.

La voce di Wikipedia non discute i valori iniziali che un nodo dovrebbe impostare prima di iniziare a partecipare a Paxos. Cosa sono questi?

I nodi dovrebbero mantenere il loro ultimo numero di proposta accettato e, infine, anche il valore corrispondente. Dovrebbero persistere. Quando si collega per la prima volta, il numero di proposta iniziale per un determinato proponente dovrebbe essere nullo (o qualsiasi equivalente).

Answer 3

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

Ogni proponente ha una conservazione stabile. Ogni proponente ricorda (in deposito stabile) la proposta più numerosa che ha cercato di emettere e inizia la fase 1 con un numero di proposta più elevato di quello che ha già utilizzato.