Paxos nel suo cuore è molto semplice

L’algoritmo di Paxos, se presentato in parole povere, è molto semplice. — Leslie Lamport 2001

Ho intenzione di provare a spiegare il singolo decreto Paxos in un modo, si spera, che è facile da capire.

Fino ad oggi, IMO, la conferenza di John Ousterhout su Paxos è ancora LA MIGLIORE là fuori. Il materiale in questo post prende in prestito pesantemente dalla lezione del Prof. Ousterhout. Con l’accordo di John Ousterhout, ho usato alcune delle sue diapositive per aiutare a spiegare Paxos.

Consenso

Paxos come protocollo, sta cercando di risolvere il problema del consenso. In parole povere, sta cercando di risolvere un problema che un sistema sceglierà solo un valore quando uno o più server possono proporre valori diversi.

L’esempio del mondo reale sarebbe qualcosa come un’elezione. Le persone possono votare per un presidente diverso. Ma solo un presidente può essere scelto.

Paxos è progettato per gestire fail-stop/crash (non bizantino) e ritardo/perdita dei messaggi. Inoltre c’è un requisito di liveness che alla fine viene scelto un valore proposto finché la maggior parte dei server è in esecuzione. Questo per evitare soluzioni poco interessanti come non accettare mai alcun valore. Se non fate nulla, non farete nulla di male. Allo stesso modo, non vuoi che più di un presidente venga eletto e vuoi avere un presidente alla fine finché le persone votano.

In una nota a margine, ad essere onesti, penso che cercare di usare il voto come esempio per spiegare Paxos, nel documento parlamentare part-Time originale è molto naturale. Ma in qualche modo non ha funzionato molto bene. Lamport ha anche detto lui stesso in un’intervista che è un fallimento totale, il che è sfortunato.

Singolo accettore

Screen-Shot-2018-11-13-at-11.17.43-PM
Con un cluster di server 2F+1, cosa succede se creiamo sempre una certa casella per accettare le proposte. E qualunque proposta venga accettata da quella scatola viene scelta.

Il problema di questo approccio è che una singola casella in basso può rendere il servizio non disponibile. Ma il requisito dice che il servizio deve essere attivo e funzionante finché la maggior parte dei server è in esecuzione (F+1 in questo caso).

Si noti che questo è effettivamente un singolo modello di replica master. E questo è esattamente il motivo per cui i tempi di inattività sono inevitabili con la replica master-slave.

Quorum

Quindi se avere un singolo accettore non funziona, forse dovremmo aspettare fino a quando più server hanno accettato una proposta prima di rivendicare un valore scelto.

Quanti?

Se gli accettori sono fissi ed è <=F, ancora una volta, non riusciamo a tollerare F server in crash. Se gli accettori possono essere qualsiasi server ed è <=F, in un cluster di server 2F+1, potremmo avere due proposte diverse che vanno a due insiemi disgiunti di accettori che causano la scelta di due valori.

Quindi il numero di accettori deve essere >=F+1. Poiché meno accettori sono meglio è, andiamo con F+1. E può essere qualsiasi server F+1 nel cluster.

Abbiamo già fatto qualche progresso! Se una proposta è accettata dai server F+1, viene scelta.

Accettare proposte

Ora vediamo come gli accettatori dovrebbero decidere se accettare una proposta o meno.

Accetta solo la prima proposta?
Screen-Shot-2018-11-13-at-11.17.27-PM

Non funzionerebbe, perché possiamo finire per non avere mai alcun valore scelto come il caso sopra. Ciò viola il requisito di liveness.

Non ha senso dire di accettare una seconda proposta o qualcosa del genere perché non si sa mai se ci sarà mai una seconda proposta.

Quindi dobbiamo accettare la prima proposta, ma forse non solo la prima proposta.

Accetta ogni proposta?
Screen-Shot-2018-11-13-at-11.31.11-PM
Ciò violerebbe il requisito di sicurezza in quanto possiamo avere più di un valore scelto.

Core

Ecco che arriva il trucco, che penso sia LA parte più interessante di Paxos.

Una volta scelto un valore, le proposte future devono proporre lo stesso valore.

Ciò significa che sarebbe necessario un protocollo a due fasi. Nella prima fase, i proponenti devono capire se un valore è già stato scelto. E proporre nella seconda fase.

Se sei un veterano del sistema distribuito devi aver già notato una parola chiave nell’istruzione precedente. Ed è “futuro”. Ho rivisto il tempo e l’ordine prima. Sistema distribuito è tutto di ordinare. “futuro” qui implica l’ordinamento (accadere-prima della relazione). Quindi dobbiamo ordinare tutte le proposte. Quindi nell’esempio seguente, possiamo rifiutare red perché sappiamo che blue è scelto e red è una vecchia proposta.

Screen-Shot-2018-11-13-at-11.39.37-PM

Numero di voto

Un modo semplice per ordinare le proposte è avere un numero di voto unico per ogni proposta sotto forma di <seq_id, server_id>. Per garantire l’ordine, seq_id deve essere persistente cross crash / restart. Quindi deve essere conservato in modo duraturo localmente.

Paxos

Ora siamo tutti pronti per descrivere il vero protocollo Paxos a due fasi. Chiameremo la prima fase la fase prepare e la seconda fase la fase accept. prepare la fase serve a due scopi in un viaggio di andata e ritorno.

  1. imparare su qualsiasi valore che è già scelto
  2. evitare di accettori di accettare qualsiasi tipo di precedenti proposte (molto simile a RISERVA di passaggio in Commit in Due fasi)

Screen-Shot-2018-11-13-at-11.53.52-PM
Accettore è durevole negozio un paio di cose

  • minProposal
  • acceptedProposal
  • acceptedValue
    Si noti che, invece di “broadcast a tutti i server”, dovrebbe essere “broadcast per almeno F+1 server”. E il proponente dovrebbe inviare il messaggio accept allo stesso set di server F+1 come nella fase di preparazione.

Diamo un’occhiata da vicino ad ogni passo.

Prepara la fase

In questa fase, il proponente cerca di ottenere una promessa dall’accettore di non accettare alcuna proposta più vecchia della sua. Allo stesso tempo, gli accettanti informeranno i proponenti quali valori sono già stati accettati finora.

Nei passaggi 3 e 4, un proponente cambierà la sua proposta con l’ultima proposta accettata dagli accettori con cui ha parlato. Sembra essere molto conservatore perché si potrebbe ottenere una proposta accettata che non è scelto e il proponente finisce per rinunciare alla sua proposta. Ma va bene, dato che ci interessa solo il consenso. Nella prima fase, è difficile per il proponente sapere se un valore è scelto o meno. Un valore accettato potrebbe non essere scelto. Ma un valore scelto deve essere accettato dalla maggioranza dei server! E gli accettatori rifiutano le proposte più vecchie (passaggio 6). Con due invarianti, sappiamo che l’ultima proposta accettata è tornata alla proposta nella prima fase o è già stata scelta, o al momento non è stato scelto alcun valore. In entrambi i casi, è sicuro proporre quel valore.

Perché tenere traccia di minProposal?
Ci possono essere due proposte di corsa in fase di preparazione, mentre nulla è stato ancora accettato. Ciò significa che entrambi si sposteranno per accettare la fase. Grazie all’ordine totale che abbiamo per tutte le proposte e al requisito F+1, almeno un accettore vedrà la proposta più recente e rifiuterà il messaggio accept dalla proposta perdente/precedente. L’invariante qui è minProposal >= acceptedProposal.

Screen-Shot-2018-11-14-at-12.28.11-AM

Questo è probabilmente il caso più interessante, poiché il secondo proponente non ha visto il valore accettato precedente e un valore non è stato scelto al momento in fase di preparazione. In questo caso, andrà avanti e invierà accept(Y) ad altri server. Poiché S3 ha promesso che accetterà proposte solo dopo 4.5, rifiuta X. Se non teniamo traccia di minProposal, Xsarà accettato da S3. Quindi sia X che Y sarebbero stati accettati da tre server e considerati scelti, il che viola i requisiti di sicurezza.

Il gioco è fatto. Questo è il decreto unico Paxos. Detto questo, l’implementazione di Paxos ha dimostrato di essere molto molto difficile.

  1. Paxos reso semplice https://lamport.azurewebsites.net/pubs/paxos-simple.pdf ↩︎

  2. Il Parlamento a tempo parzialehttps://lamport.azurewebsites.net/pubs/lamport-paxos.pdf ↩︎

  3. Paxos fatto vivere https://www.cs.utexas.edu/users/lorenzo/corsi/cs380d/papers/paper2-1.pdf ↩︎

Lascia un commento

Il tuo indirizzo email non sarà pubblicato.