Il problema del consenso distribuito
Paxos garantisce che i nodi sceglieranno sempre e solo un singolo valore (quindi garantisce la safety), ma non garantisce che un valore verrà scelto se la maggioranza dei nodi non sono disponibili (progress).
L'algoritmo di PAXOS prende origine dalla storia del parlamento di PAXOS ( Grecia )
- Ciascun membro aveva un registro in cui annotare tutte i decreti approvati.
- I decreti approvati erano numerati (in ordine crescente).
- I parlamentari, così come i messaggeri, potevano entrare ed uscire dal parlamento a piacere.
- I messaggeri potevano anche uscire prima di consegnare un messaggio affidatogli, “magari per un viaggio di sei mesi” o “andar via per sempre e il messaggio non veniva consegnato.
- Ma quando in Camera, parlamentari e messaggeri erano dediti al lavoro ed
eseguivano prontamente i loro compiti.
- C’era molto rispetto e fiducia tanto che si tendeva a far passare ogni decreto proposto
- Ogni legislatore di Paxos mantneva un libro mastro, dove registrava tutto ciò che è succedeva
COME FUNZIONAVA IL PARLAMENTO DI PAXOS
Il documento di PAXOS specifica che all'interno del parlamento Paxos ci sono tre tipi di legislatori: PROPONENTI , ACETTATORI, DISCENTI.
PROPONENTI ( proposer ): sostengono le richieste dei cittadini e portano nuove richieste nel parlamento di PAXON. Un PROPONENTE propone un valore sul quale vuole che ci si metta d’accordo. Lo fa con l’invio di una proposta contenente un valore a l’insieme di tutti gli ACCETTATORI.
ACCETTATORI ( acceptors ): Sono legislatori che votano. Questi decidono se accettare o meno il valore. Ogni ACCETTATORE sceglie un valore in modo indipendente – può ricevere più proposte, ognuna da un PROPONENTE diverso – e trasmette la sua decisione ai DISCENTI
DISCENTI ( Learner ): determinano se un valore è stato accettato.
Nell'algoritmo di PAXOS, Un valore per essere accettato, necessita che una maggioranza di ACCETTATORI (acceptors) deve scegliere lo stesso valore.
Un certo numero di proposer propone un valore agli acceptors. Quando un acceptor accetta un valore esso invia il risultato ai nodi Learners.
PAXOS Step by Step
Ogni round di successo ha due fasi, cioè i Proposer inviano due tipi di messaggi agli acceptors: preparare e accettare.
il PROPONENTE ( proposer ) propone un decreto al parlamento della PAXON. Un decreto ha un numero e un valore.
> Il valore può essere qualsiasi cosa, ma è necessario che il numero associato al decreto sia strettamente CRESCENTE.
Dopo che un decreto è stato proposto, gli accettori discutono.
Ora, se il numero legale o la maggioranza dei legislatori votano sì, il decreto passa e tutti lo registrano su i libri. Non appena il CONSENSO è avvenuto, gli studenti imparano il risultato e poi lasciano l'intera isola facendo sapere a tutti cosa è successo in parlamento.
ANALOGIE NEI SISTEMI DISTRIBUITI
I singoli nodi all'interno di un sistema distribuito sono l'equivalente dei PROPOSER, dal momento che sono coloro il cui compito è servire i cittadini ( l'equivalente dei programmi - client per arrivare al consenso e quindi trasmettere o agire sul risultato).
E lo stato del database distribuito è come la legge corrente approvata dal parlamento.
Una delle principali assunzioni fatte dall'algoritmo di PAXOS è che:
1. i nodi non stanno cercando di sovvertire il protocollo
2. i messaggi sono consegnati senza corruzione.
In altre parole, PaxoS funziona solo per lo scenario fail-stop (il nodo può bloccarsi o non restituire valori) e non tiene conto dei difetti legati alla questione dei nodi Bizantini.
Il risultato di questo è che Paxos è molto veloce, e in pratica viene utilizzato per replicare insiemi di dati di grandi dimensioni.
In Google, Paxos viene utilizzato nel loro servizio di blocco distribuito Chubby, dove è molto importante affinché tutti accettino di consentire solo a un processo di avere accesso in scrittura a un determinato pezzo di dati in un dato momento.
Inoltre Microsoft Bing Autopilot, Heroku, WeChat e WANDisco usano tutti Paxos internamente.
Aprofondimenti http://www.codeido.com/2013/11/problema-del-consenso-distribuito-paxos-step-by-step/
Nota dell'autore. Se sei arrivato fino a qui, grazie ! Se vuoi supportare questo documento ( con note e / o miglioramenti ) oppure mi vuoi suggerire errori e/o omissioni, aggiunte da fare, ti invito a lasciare un commento ed una nota di miglioramento, attraverso l'apposito campo " commenti " .
Ti ringrazio.
Write By Andrea Belvedere
Follow me. https://twitter.com/AndreaBelvedere
