.. meta:: :language: it :description language=it: paxos :description language=en: paxos :keywords: distributed system, consistency, paxos :author: Luciano De Falco Alfano .. index:: paxos .. _ref_paxos: Paxos =================== .. contents:: :local: *Lezione del 2019-05-29 mer*. *Paxos* sono una famiglia di protocolli completamente distribuiti (non esiste un processo primario che coordina le attività) per la soluzione del problema del consenso. È stato proposto originariamente da Leslie Lamport, e successivamente ripreso e sviluppato da altri autori. Ormai è diffuso in molte applicazioni, dal file system di Google ad Amazon. Il problema del consenso, dato un sistema distribuito, consiste nel fare in modo che i processi del sistema decidano concordemente che azione effettuare. Il problema del consenso, nell'ambito delle repliche, significa che le repliche si accordano sulla prossima operazione da effettuare. Questo assicura che i diversi data store subiranno gli stessi aggiornamenti con la stessa sequenza di attività, mantenendo la loro consistenza. Organizzazione ----------------- Paxos ha i seguenti tipi di processi: * **proposer**, riceve la richiesta, e la propone alla "logica di accettazione"; * **acceptor**, un set di processi che formano la "logica di accettazione"; * **learner**, processi che eseguono l'attività richiesta. Questi processi possono essere eventualmente accorpati in parte o completamente: ovvero un processo può svolgere la funzione di proposer + acceptor + learner. Inoltre l'attività si articola in due fasi: * **prepare**, è la fase in cui si decide cosa accettare, * **accept**, è la fase di esecuzione dell'attività concordata.. Algoritmo ------------- Il flusso benevolo dell'algoritmo è sintetizzato nel seguente diagramma: .. image:: ./images/37_paxos.svg :align: center in cui *V* è il valore da registrare. Come si vede, la richiesta di update viene effettuata da un *client* verso il *proposer*. Questo a sua volta la comunica agli *acceptor* inviando un messaggio *prepare*. Il messaggio di *prepare* è identificato da un numero (il numero 1, in figura). Gli *acceptor* rispondono al *proposer* promettendo che non accetteranno altre *prepare* con identificatori inferiori (messaggio *promise*). Nel momento in cui il proposer rileva un "numero sufficiente" di promesse, invia agli *acceptor* il messaggio di *accept*. Questi ripondono con il messaggio *accepted* al proposer, ed inoltrandolo anche ai *learner*, ovvero ai processi che devono fisicamente eseguire le registrazione. A loro volta i learner, quando ricevono un "numero sufficiente" di messaggi *accepted*, eseguono l'operazione richiesta. Effettuata la registrazione, i *learner* inviano al *client* il messaggio di *ok*. Il "numero sufficiente" precedentemente indicato è pari al 50% degli acceptor. Questo è un protocollo completamente distribuito, in quanto la sua ossatura è formata dagli asseptor (che spesso sono collassati con i learner). Paxos non è usato solo per mantenere consistenza tra le repliche, ma sopratutto per la gestione del fault tolerant. Infatti Paxos funziona fino al guasto del 50% degli acceptor. Aumentare il numero di acceptor aumenta i costi (più macchine) a fronte di un aumento di resistenza ai guasti. Il tipo di fallimento che Paxos prevede è il fault con stop. Ovvero la macchina guasta non dà ulteriori comunicazioni. Se si devono considerare guasti che prevedono l'invio di comunicazioni scorrette, Paxos non è utilizzabile; bisogna utilizzare Byzantine. Duelling proposal ---------------------- Paxos è molto avanzato, ma vi sono alcune condizioni in cui può dare luogo a stalli. Un esempio è il duelling proposal, schematizzato qui di seguito: .. include:: ./txts/duelling_proposal.txt :literal: Nella figura vediamo che gli acceptor effettuano la *Promise(1,..)*. Dopo di che il proposer temporaneamente cade, e ne subentra un secondo. Il secondo proposer sa che gli acceptor non accetteranno nulla più basso di 1, quindi alza la posta e fa *Prepare(2)*, regolarmente accettata dagli acceptor. Supponiamo ora che l'old proposer faccia recovery e tenti di proseguire da dove si era interrotto. La sua richiesata di *Accept!(1)* viene respinta, perché ora vale *Promise(2,...)*. Al che l'old proposer invia una propose(3) per scavalcare il 2. E questo può innescare una contesa con il nuovo leader, come mostrata nella figura, portando allo **stallo** del protocollo. Per risolvere lo stallo è necessario un meccanismo di centralizzazione, decidendo quale dei due proposer è leader. Altre considerazioni ------------------------ Se si pensa alla architettura *blockchain*, che è uno data store distribuito, Paxos presenta caratteristiche di funzionamento che si adattano particolarmente bene a questo contesto. Infatti i nodi della *blockchain* si devono accordare sulla transazione da fare. Essendo un DB distribuito, la blockchain replica il proprio contenuto potenzialmente in tutti i nodi. E quando è necessario effettuare una modifica, questa deve essere estesa a tutti i nodi. Vi è un punto che richiede un adattamento: Paxos è nato conoscendo il numero di acceptors. Nel caso di blockchain questo numero è sconosciuto.