Il problema del consenso distribuito: l’algoritmo Paxos, step-by-step

Nei sistemi distribuiti, una serie di macchine sono in grado di raggiungere un consenso su una decisione che è estremamente importante. I sistemi di database, ad esempio, devono assicurare che tutte le macchine siano d’accorso se effettuare un commit o il rollback di una transazione, in modo che ogni macchina abbia una visione coerente dei dati (si immagini ad esempio il problema sul proprio conto bancario. Una macchina pensa che tu abbia 1000 euro sul tuo conto, ma un’altra macchina crede che tu abbia il conto vuoto).

Il consenso è difficile da raggiungere, perché i messaggi tra le macchine possono essere persi o ritardati in modo indefinito, oppure le macchine stesse possono fallire – come fa una macchina a sapere se un’altra macchina ha elaborato un messaggio?

Solitamente si utilizza il Commit a due fasi (Two-phase commit), ma ha un problema – se il nodo coordinatore di una transazione fallisce, il sistema rimane bloccato fino a quando questo nodo non si riavvia. Il commit a tre fasi risolve questo problema del blocco, ma fa sempre affidamento su un unico coordinatore.

In questo articolo, si discute Paxos, un protocollo distribuito alternativo al commit a due fasi e a quello a tre fasi. 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). Gli algoritmi di consenso hanno come obiettivo la safety, perché non importa se si faccia un commit o un rollback – ma è di fondamentale importanza che una sola risposta sia scelta.

Approccio Generale

Un nodo di Paxos può assume uno solo o tutti e tre i ruoli: proposer, acceptor, e learner. Un proposer 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 acceptors, che decidono se accettare o meno il valore. Ogni acceptor sceglie un valore in modo indipendente – può ricevere più proposte, ognuna da un proposer diverso – e trasmette la sua decisione ai learners, che determinano se un valore è stato accettato. Un valore per essere accettato da Paxos, una maggioranza di acceptors deve scegliere lo stesso valore. Nella pratica, un singolo nodo può assumere molti o tutti questi ruoli, ma negli esempi di questo articolo, ogni ruolo viene eseguito su un nodo separato, come illustrato di seguito.

paxos nodes

Figura 1: architettura Paxos di base. 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

Nell’algoritmo standard di Paxos, i proposers inviano due tipi di messaggi agli acceptors: prepare o accept. Nella prima fase di questo algoritmo un proposer invia una richiesta di prepare ad ogni acceptor, contentente un valore v,  e un numero di round, n.

Il valore proposto può essere commit o rollback, come nell’esempio precedente del database, o può essere un qualsiasi altro valore arbitrario. In questo articolo i nodi di Paxos stanno cercando di raggiungere un consenso su un valore intero. Il numero di round (anche detto numero della proposta) deve essere positivo, crescente e unico, rispetto al numero di round inviato dagli altri proposers [1].

Nell’esempio illustrato di seguito, ci sono due proposers, ed entrambi inviano una richiesta di prepare. La richiesta da parte del proposer A raggiunge gli acceptors X e Y prima della richiesta del proposer B, ma la richiesta del proposer B raggiunge l’acceptor Z prima.

paxos esempio 1

Figura 2: Paxos. I Proposers A e B inviano le richieste di prepare ad ogni acceptor. In questo esempio la richiesta del proposer A raggiunge prima gli acceptor X e Y, e la richiesta del proposer B raggiunge prima Z.

Se l’acceptor che ricevere una richiesta di prepare non ha visto un’altra proposta, l’acceptor risponde con una risposta di prepare che promette di non accettare un’altra proposta con un numero di round inferiore. Questo è illustrato nella figura 3, che mostra le risposte di ciascun acceptor alla prima richiesta di prepare che ricevono.

paxos esempio 2

Figura 3: Paxos. Ogni acceptor risponde alla prima richiesta di prepare che ha ricevuto.

Alla fine, l’acceptor Z riceve la richiesta dal proposer A [2], e gli acceptors X e Y ricevono il messaggio dal proposer B. Se l’acceptor ha già visto una richiesta con un numero di round superiore, la richiesta di prepare viene ignorata, come nel caso del proposer A con l’acceptor Z. Se l’acceptor non ha visto una richiesta con un numero di round più alto, prometterà nuovamente di ignorare eventuali richieste con numeri di round più bassi, e rinvia il messaggio precedente con il numero di round più alto che ha visto, insieme al valore di tale proposta. Questo è il caso della richiesta del proposer B e degli acceptors X e Y, come illustrato di seguito:

paxos esempio 3

Figura 4: Paxos. L’Acceptor Z ignora la richiesta di A perché ha visto che vi è un messaggio con un numero di round superiore (4>2). Gli acceptors X e Y rispondono alla richiesta del proposer B con il messaggio col round più alto precedentemente riconosciuto, e promette di ignorare eventuali altre proposte con numero di round inferiore.

Una volta che un proposer ha ricevuto delle risposte di prepare da una maggioranza di acceptors, può emettere una richiesta di Accept. Siccome il proposer A riceve solo risposte che indicano che non vi erano precedenti proposte,  invia una richiesta di accept ad ogni acceptor con lo stesso numero di round e di valore della proposta iniziale (n=2, v=8). Tuttavia, queste richieste vengono ignorate da ogni acceptor perché hanno tutti promesso di non accettare le richieste con un numero di round inferiore a 4 (in risposta alla richiesta di prepare del proposer B).

Il proposer B invia una richiesta di accept ad ogni acceptor contenente il numero di round usato in precedenza (n=4) e il valore associato con il più alto numero di round  del messaggio di prepare responde ricevuto (v=8)[3]. Da notare che questo non è il messaggio che il proposer B ha inizialmente proposto, ma il valore più alto che ha visto in precedenza.

paxos esempio 4

Figura 5: Paxos. Il proposer B invia una richiesta di accept ad ogni acceptor, con il suo numero di round precedente (4), e il valore della massima proposta che ha visto (8, da [n = 2, v = 8]).

Se un acceptor riceve una richiesta di accept per un numero di round superiore o uguale  a quello che ha già visto, accetta e invia una notifica ad ogni nodo Learner. Un valore è scelto dall’algoritmo di Paxos quando un learner scopre che una maggioranza di acceptors ha accettato un valore, come illustrato di seguito:

paxos esempio 5

Una volta che un valore è stato scelto da Paxos, un’ulteriore comunicazione con gli altri proposers non può modificare questo valore. Se un altro proposer, il proposer C, invia una richiesta di prepare con un numero di round superiore rispetto a quanto è stato precedentemente visto,  e un vlaore diverso (per esempio, n = 6, v = 7), ciascun acceptor risponde con la precedente proposta più alta (n = 4, v = 8). Ciò richiede che il proposer C  invii una richiesta di accept contentente [n = 6, v= 8], che conferma solo il valore che è già stato scelto. Inoltre, se qualche minoranza di acceptors non ha ancora scelto un valore, questo processo assicura che alla fine si raggiungerà il consenso sullo stesso valore.

Vari miglioramenti per aumentare l’efficienza per l’algoritmo standard di Paxos sono discussi nei paper di  Lamport and Baker et al.. Ad esempio, una richiesta di preparare non è necessaria se il proposer sa che è il primo a suggerire un valore. La proposta per una richiesta di questo tipo viene numerata come 0 (zero), in modo che sarà ignorata se qualsiasi richiesta numerata con un numero di round più alto è già stata ricevuta.

 

Utilità generale

Paxos è stato spesso criticato per la sua complessità, in particolar modo per quanto riguarda la difficoltà di una sua reale implementazione. A dispetto di questo, è un interessante esempio di un problema particolarmente impegnativo nei sistemi distribuiti, risolto in modo intelligente e concettualmente pulito.

Se sei interessat0 all’argomento, ti consiglio di leggere degli esempi reali di Paxos e del protocollo di commit a due e tre fasi, a partire dai riferimenti riportati sotto.

Questo articolo è una traduzione ed un miglioramento dell’articolo originale di Angus Macdonald.

 

Riferimenti

 

— 

[1] Il metodo per garantire l’unicità dei numeri di round quando ci sono più proposers non è specificato nell’algoritmo di Paxos.

[2] può non succedere, ma l’algoritmo è resiliente a questo.

[3] Si noti che questo è il più alto numero di round che ha ricevuto dai prepare di risposta. In questo esempio, il proposer B ha un numero di round maggiore nella sua proposta (n = 4) rispetto al proposer A (n = 2), ma ha ricevuto solo la proposta del proposer A in risposta alla sua richiesta di prepare. Se non ci fossero proposte precedenti che sono state state restituite dai messaggi di risposta prepare, il proposer B avrebbe usato la propria proposta (n = 4).

Leave a Reply

Your email address will not be published. Required fields are marked *