Paxos

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:

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:

client    Proposer      Acceptor             Learner
  |          |          |   |   |            |   |
  x--------->|          |   |   |            |   |   Request
  |          x--------->|-->|-->|            |   |   Prepare(1)
  |          |<---------x---x---x            |   |   Promise(1, {null, null, null})
  |          !          |   |   |            |   |   !! Propose leader FAILS
  |              |      |   |   |            |   |   !! NEW Propose leader (knows last number was 1)
  |              x----->|-->|-->|            |   |   Prepare(2)
  |              |<-----x---x---x            |   |   Promise(2, {null, null, null})
  |          |   |      |   |   |            |   |   !! OLD Propose leader RECOVER
  |          |   |      |   |   |            |   |   !! OLD leader tries 1, denied
  |          x--------->|-->|-->|            |   |   Accept!(1, Vb)
  |          |<---------x---x---x            |   |   Nack(2)
  |          |   |      |   |   |            |   |   !! OLD leader tries 3
  |          x--------->|-->|-->|            |   |   Prepare(3)
  |          |<---------x---x---x            |   |   Promise(3, {null, null, null})
  |          |   |      |   |   |            |   |   !! NEW leader tries, denied
  |          |   x----->|-->|-->|            |   |   Accept!(2, Va)
  |          |   |<-----x---x---x            |   |   Nack(3)
  |          |   |      |   |   |            |   |   !! NEW leader raises 4
  |          |   x----->|-->|-->|            |   |   Prepare(4)
  |          |   |<-----x---x---x            |   |   Promise(4, {null, null, null})
  |          |   |      |   |   |            |   |   !! OLD leader propose, denied
  |          |   x----->|-->|-->|            |   |   Accept!(3, Vb)
  |          |   |<-----x---x---x            |   |   Nack(4)
  |          |   |      |   |   |            |   |   !! ... and so on ...
  

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.