Migliore risposta
Questo articolo fornisce una spiegazione e una prova sorprendentemente chiare: http://pdos.csail.mit.edu/6.824/papers/paxos-simple.pdf
Cercherò di fornire un riepilogo chiaro qui:
Lobiettivo del Lalgoritmo di Paxos consente a un certo numero di pari di raggiungere un accordo su un valore. Paxos garantisce che se un pari ritiene che un valore sia stato concordato dalla maggioranza, la maggioranza mai daccordo su un valore diverso. Il protocollo è progettato in modo che qualsiasi accordo deve andare attraverso la maggioranza dei nodi. Eventuali futuri tentativi di accordo, in caso di successo, devono passare anche attraverso almeno uno di questi nodi. Pertanto: Qualsiasi nodo che propone dopo che è stata raggiunta una decisione deve comunica con un nodo in maggioranza Il protocollo garantisce che apprenderà il precedente ag reed sul valore di quella maggioranza.
Ecco come funziona:
Supponiamo di avere 3 nodi, A, B e C. A vorrebbe proporre il valore “Foo.”
Lalgoritmo opera in 3 fasi. In ogni fase, deve essere raggiunta laffermazione dalla maggioranza dei nodi.
Innanzitutto, abbiamo la fase di preparazione. A invia una richiesta di preparazione ad A, B e C. Paxos fa affidamento sui numeri di sequenza a raggiungere le sue garanzie. La richiesta di preparazione chiede a un nodo di promettere: “Non accetterò mai alcuna proposta con un numero di sequenza inferiore a quello nella richiesta di preparazione”. I nodi rispondono con qualsiasi valore precedentemente concordato (se presente). (E questo è di fondamentale importanza): Il nodo A deve proporre il valore che riceve con il numero di sequenza più alto. Questa azione fornisce la garanzia che i valori precedentemente concordati verranno preservati.
Successivamente, abbiamo la fase di accettazione. A invia una richiesta di accettazione ad A, B e C. La richiesta di accettazione dichiara: ” Accetti foo? ” Se il numero di sequenza di accompagnamento non è inferiore a quello che il nodo aveva precedentemente promesso o richiesto che il nodo ha precedentemente accettato, accetterà il nuovo valore e numero di sequenza.
Se il nodo A riceve accetta da la maggior parte dei nodi, il valore viene deciso. Questo round di Paxos non accetterà mai un altro valore.
La terza fase non è strettamente necessaria, ma è cruciale ottimizzazione in qualsiasi implementazione Paxos prodotta. Dopo che A ha ricevuto la maggioranza delle accettazioni, invia messaggi decisi a A, B e C. Questi messaggi consentono a tutti i peer di sapere che è stato scelto un valore e accelerano la fine del processo decisionale.
Senza questo messaggio, gli altri colleghi dovrebbero tentare di proporre un valore per apprendere dallaccordo. Nella fase di preparazione, hanno appreso del valore concordato in precedenza. Una volta che laccordo è stato portato a conclusione, il nodo riconoscerebbe laccordo.
Ho sorvolato su alcune questioni chiave qui:
- Tutti i numeri di sequenza devono aumentare in modo monotono e univoco per nodo . Vale a dire, A e B non possono entrambi inviare un messaggio con numero di sequenza k. Tutti i messaggi inviati nel protocollo includono numeri di sequenza. Un nodo deve tenere traccia della richiesta di accettazione più alta che ha visto e del valore più alto che ha promesso nella fase di preparazione.
- Condizioni di errore. È del tutto possibile che un round di Paxos fallisca. In caso di errore, un nodo tenta semplicemente di riproporre con un numero di sequenza più alto.
- Condizioni di terminazione. La versione di Paxos che ho descritto non termina necessariamente. Sono necessarie alcune modifiche per una prova formale della risoluzione.
Risposta
Poiché Paxos ottiene il consenso, può anche essere utilizzato per replicare le scritture in un database distribuito poiché può garantire un ordine coerente degli eventi tra tutti i nodi di un gruppo. Chubby di Google utilizza Paxos per offrire file fortemente coerenti. È da qui che nasce la confusione. Qual è quindi la relazione tra la sincronizzazione della vista e paxos se entrambi possono essere utilizzati per la replica?
Poca storia: Lamport ha introdotto il concetto di replica della macchina a stati allinizio degli anni 80. La replica della macchina a stati significa che un sistema fornisce eventi nello stesso ordine a tutti i nodi e vengono elaborati in modo deterministico garantendo stati coerenti su tutti i nodi del gruppo. Tuttavia, al momento dellintroduzione di questo concetto, implicava tutti i tipi di ipotesi, inclusa la sincronizzazione della rete.Quindi la replica della macchina a stati è rimasta semplicemente uno strumento teorico senza uso pratico. View synchrony è stato introdotto a questo punto e mirava a raggiungere la coerenza non facendo tali presupposti. Lobiettivo era quello di disporre di un sistema pratico che fornisse tali garanzie.
La pubblicazione di Paxos è avvenuta mentre era in corso il lavoro sulla sincronizzazione delle viste. Paxos potrebbe ottenere la replica della macchina a stati poiché le repliche potrebbero ora concordare lordine di esecuzione delle richieste dei client utilizzando questo algoritmo di consenso. Paxos non ha fatto supposizioni sulla rete sincrona o sui guasti. Paxos ha anche fornito un protocollo di appartenenza al gruppo. Le differenze che ora rimanevano tra la sincronia delle viste e Paxos erano solo nel modo in cui venivano formulate le astrazioni. Entrambi forniscono lappartenenza dinamica e gestiscono gli errori in modo simile. Le differenze sono davvero solo nel modello. Alcune differenze che possono essere evidenziate sono:
- Virtual Synchrony ha un semplice protocollo di appartenenza al gruppo rispetto a Paxos. Virtual Synchrony esegue lappartenenza al gruppo come un servizio separato.
- Paxos può fare progressi in alcuni casi di partizione in cui si blocca la sincronizzazione virtuale.
- Virtual Synchrony è più veloce di Paxos contemporanea.
Entrambi i sistemi hanno evoluti e convergenti . Allo stato attuale è molto difficile tracciare differenze significative tra i due.
Lalith spiega chiaramente il protocollo Virtual Synchrony e giustamente fa notare che Paxos o qualsiasi altra variante di consenso può essere utilizzata nella sincronizzazione della vista. Paxos oltre al consenso fornisce lappartenenza al gruppo e altre funzionalità che la sincronizzazione virtuale già fornisce. Poiché sia la sincronia virtuale che Paxos forniscono le stesse garanzie e sono state sviluppate nello stesso periodo, la specifica della sincronia virtuale non utilizza Paxos per il consenso. Il modello di sincronia virtuale tuttavia utilizza il protocollo di invio totalmente ordinato (noto anche come ABCAST) per ottenere la trasmissione atomica e un altro protocollo per aggiornare le viste di gruppo e queste possono essere viste come la variante di consenso utilizza.
Potrebbe essere interessante notare che il modello di runtime ISIS-2 combina il modello Paxos con il modello di sincronia virtuale, non per consenso ma per escludere lappartenenza al gruppo come servizio separato in Paxos. Questo rende Paxos più veloce nei casi in cui lappartenenza non cambia dinamicamente. Combinando Virtual Synchrony e Paxos, ISIS2 è in grado di saltare alcuni passaggi che i tipici Paxos devono eseguire. In sostanza, Paxos e Virtual Synchrony sono modelli diversi per ottenere la stessa funzionalità e possono essere combinati tra loro per ottenere varianti o ottimizzazioni.