Nello scorso articolo abbiamo visto il tema del consenso e abbiamo capito perché è importante complesso; abbiamo visto i concetti di safety e liveness, fatto qualche esempio, e poi ci siamo lasciati dicendo che nel prossimo articolo (questo) avremmo visto Paxos.

Paxos è un protocollo per raggiungere il consenso in sistemi distribuiti; è safe ma non live, e non tollera nodi bizantini. È stato inventato da quel pazzo genio di Leslie Lamport e regalato al mondo in un paper intitolato The Part-Time Parliament, sotto forma di una falsa ricerca archeologica su una inventata isola greca chiamata Paxos (che poi esiste davvero).

All'inizio di quel paper, Lamport scrive:

Scoperte archeologiche recenti sull'isola di Paxos rivelano che il parlamento funzionava nonostante la "passeggiosa" propensità dei suoi legislatori part-time. I legislatori mantenevano copie coerenti dei registri parlamentari, nonostante le loro frequenti fughe dalla camera e al fatto che i loro messaggi fossero facilmente dimenticati. Il protocollo del parlamento di Paxos ci fornisce un nuovo modo di implementare l'approccio state-machine per progettare sistemi distribuiti.

In pratica Leslie si inventò una finta ricerca archeologica su una civiltà inesistente che aveva un particolare sistema in cui i politici lavoravano part-time. Nessuno ci capì niente di quel paper, tant'è un po' di tempo dopo Lamport pubblicò Paxos Made Simple, e nessuno ci capì niente ugualmente.

Questo - in parte - è un motivo per cui Paxos è così temuto e incompreso. In questo articolo cerchiamo capirci qualcosa.

Funzionamento di Paxos

Paxos è un protocollo che serve a raggiungere il consenso su un valore, e a mantenerlo finché il protocollo è in esecuzione. I nodi che partecipano a Paxos possono avere ruoli diversi, e l'esecuzione del protocollo è suddivisa in turni. Vediamo meglio.

Ruoli dei processi

Abbiamo tre tipi di nodi:

  • Proposer: sceglie un valore da votare e lo propone a tutti.
  • Acceptor: riceve la proposta dal proposer, la vota oppure no.
  • Learner: memorizza il valore votato dalla maggioranza.

Ok, questa è una descrizione molto a grandi linee; ora vedremo meglio come interagiscono tra loro.

Esecuzione del protocollo

Orientativamente, Paxos funziona così:

  1. Un proposer avvia un turno di votazione, inviando a tutti un messaggio che chiamiamo $prepare$.
  2. Gli acceptor che lo ricevono, possono rispondere con una $promise$, impegnandosi quindi a votare per quel turno.
  3. Il proposer sceglie un valore e lo manda a tutti con un $accept$.
  4. Gli acceptor dicono ai learner di imparare quel valore con un $learn$.

In realtà è leggermente più complicato di così, infatti:

  • I messaggi contengono dei dati.
  • Il proposer sceglie il valore in base a una regola.
  • Affinché il valore sia scelto ci deve essere un quorum di acceptor.

Ok, vediamo un esempio.

Esempio 1

Esempio di Paxos

Capiamo prima cosa c'è nell'immagine:

  • P, A, L sono rispettivamente Proposer, Acceptor, Learner.
  • Abbiamo 3 proposer e 5 acceptor, 5 learner.
  • Il grafico mostra le ciò che avviene nel tempo tra proposer, acceptor, learner.
  • Le frecce rappresentano i messaggi scambiati tra nodi.
  • I puntini rappresentano un insieme di messaggi (non disegnati per non fare un delirio grafico)
  • Ogni proposer ha un turno associato:
    • Proposer 1 -> turno 1
    • Proposer 2 -> turno 2
    • Proposer 3 -> turno 3

Ogni proposer in realtà ha più di un turno associato, ad esempio:

  • Proposer 1 -> turno 1,4,7,...
  • Proposer 2 -> turni 2,5,8,...
  • Proposer 3 -> turni 3,6,9,...

Detto questo, vediamo cosa succede nell'esempio:

  1. Il proposer 1 inizia il protocollo e manda a tutti un $prepare(1)$ specificando il turno.
  2. Gli acceptor rispondono con una $promise(1,-,-)$, che contiene:
    • Turno.
    • Ultimo turno a cui ha partecipato (nessuno per ora).
    • Ultimo valore votato (nessuno per ora).
  3. Il proposer riceve più della metà delle $promise$, e può quindi inviare a tutti un $accept(1,5)$, specificando il valore (5) da votare per il turno (1).
  4. Gli acceptor votano inviando ai learner la loro intenzione con $learn(1,5)$.

Carino.

Facciamo una piccola pausa vedendo un po' meglio il formato e il significato dei messaggi.

Messaggi in Paxos

Messaggio Chi A chi Significato
$prepare(r)$ Proposer Acceptor Hey belli, ho avviato una votazione! Il turno (round) attuale è $r$.
$promise(r,lr,lv)$ Acceptor Proposer Egregio proposer, le prometto solennemente di partecipare al suo turno. La informo anche che l'ultima volta che ho votato è stato per il turno $lr$, ed ho votato $lv$. Mi impegno anche a non partecipare a eventuali round $r'$ più vecchi del suo ($r'<r$).
$accept(r,v)$ Proposer Acceptor Ok, il valore che dovete votare per il round $r$ è $v$.
$learn(r,v)$ Acceptor Learner Voto il valore $v$ nel round $r$. Sia scritto nei sacri registri.

Prima di mandare un $accept(r,v)$, il proposer aspetta di ricevere almeno $\frac{n}{2}+1$ $promise(r,lr,lv)$. dove $n$ è il numero di nodi. Questa quantità è chiamata quorum ($q$).

Lo stesso controllo viene fatto dai learner prima di memorizzare il valore mandatogli dagli acceptor.

Esempio 2

Supponiamo di continuare da dove eravamo rimasti nell'esempio precedente. La votazione è andata a buon fine, e il secondo proposer inizia un nuovo turno.

Esempio Paxos 2

Ragioniamo:

  1. Il proposer 2 avvia un nuovo turno con $r=2$.
  2. Gli acceptor ricevono il $prepare(2)$ e decidono di prendere parte a quel turno, quindi rispondono con una $promise(2,1,5)$, cioè indicano di prendere parte al turno $2$, e informano che l'ultima volta che hanno votato era per il turno $1$ ed hanno votato $5$.
  3. Il proposer riceve almeno la metà delle risposte propone un valore, che deve per forza essere $5$ (sorpresa, tra poco spiego).
  4. Gli acceptor ricevono la proposta e mandano il learn ai learner.

Anche in questo esempio tutto va per il meglio:

  • Nessun nodo fallisce.
  • Nessun nodo ha fallito nel turno precedente.

In questo esempio abbiamo anche visto una cosa strana:

Perché il proposer deve per forza scegliere 5? Non può scegliere un altro valore? È un proposer, deve proporre un valore, quindi perché non può inventarselo?

Per rispondere a questa domanda ricordiamoci a cosa serve Paxos:

  • Raggiungere il consenso su un valore.
  • Mantenere il valore raggiunto fino al termine del protocollo.

E ci rendiamo conto che il valore di consenso è stato scelto nel turno precedente, ed è proprio $5$, quindi il proposer mantiene quel valore. Infatti soltanto al primo turno il proposer propne veramente un valore.

Un po' più formalmente, dopo che il proposer riceve almeno la metà delle $promise$, applica questa regola:

  • Se in tutte le $promise$ si ha $lr=-$, significa che questo è il primo turno, quindi sceglie arbitrariamente $v$.
  • Altrimenti, sceglie $value[max(lr)]$, cioè il valore $lv$ associato all'ultimo turno.

Riguardo l'ultimo caso c'è da dire che per come funziona il protocollo, c'è la garanzia che questo valore sarà sempre unico, ovvero non è possibile che nello stesso turno ci sia più di un valore votato.

Ora vediamo un esempio in cui si spacca qualcosa.

Esempio 3

Esempio Paxos 3

Qui un acceptor muore e rimane morto per tutto il turno. La votazione va comunque a buon fine perché c'è il quorum. La cosa interessante avviene nel turno successivo, quando questo acceptor morto si risveglia; vediamo che dice.

Esempio Paxos 3, continuo

Nel turno 3 era morto, nel 4 si risveglia e partecipa alla votazione. A questo punto sarà l'unico nodo che nella $promise$ dirà di aver votato l'ultima volta in un altro turno, ma non cambia niente:

  • Il proposer sceglie il valore associato all'ultimo round, ovvero in questo caso $max(lr)=3 \rightarrow lv=5$.
  • Il nodo morto (in questo caso) già ha il valore di consenso (5), perché era vivo quando è stato raggiunto, e non potrà cambiare.

Esempio 4

Vediamo ora cosa succede quando al primo turno ci sono dei morti.

Esempio Paxos 4

Due acceptor falliscono e rimangono giù per tutto il turno. Gli altri votano tranquillamente il valore $5$. Il quorum c'è, e tutto va bene.

Esempio Paxos 4, continuo

Al turno successivo si svegliano e partecipano alla votazione, e non ci stupiamo di vedere che tutto va comunque bene:

  • Questi acceptor sono gli unici che mandano una $promise(2,-,-)$, dicendo cioè di non aver ancora votato.
  • Il valore scelto è comunque $5$, perché $max(lr)=1 \rightarrow lv=5$

Divertente, vero?

Esempio 5

Ora che siamo diventati bravi, vediamo un caso un po' più rotto.

Esempio Paxos 5

Due acceptor muoiono prima di ricevere $prepare$, e un altro muore prima di ricevere l'$accept$. Non c'è più il quorum, quindi il valore $5$ non viene scritto.

Esempio Paxos 5, continuo

Al turno successivo rimane soltanto un acceptor fallito, tutto va bene, e il valore scelto viene finalmente registrato.

Perfetto.

Safety

All'inizio abbiamo detto che Paxos è safe ma non live. Vediamo perché è safe, cioè che qualunque scelta fatta dal protocollo è corretta; in altre parole, non è possibile che in un turno $r'>r$ si scopra che il valore di consenso scelto nel turno $r$ sia sbagliato.

Come prerequisito, dobbiamo prima essere convinti che una volta scelto e votato con successo un valore, in ogni turno successivo il valore non sarà mai diverso. È abbastanza facile convincersene, grazie alla regola che usa il proposer per scegliere il valore: una volta ricevute le $promise$ necessarie a formare un quorum, il proposer sceglie il valore associato al turno più recente. Per questo, una volta scelto un valore $v$ nel turno $i$, in ogni turno $r'>r$ il proposer sceglierà sempre lo stesso valore $v$, ergo non è possibile che in un turno $r'>r$ si abbia un valore $v' \ne v$.

A questo punto se fissiamo $j=max(lr)$ abbiamo due casi su cui ragionare:

Nessun voto

Se $j=-$ significa che nessuno ha votato; più formalmente, significa che $\forall j \le i-1$ dove $i$ è il turno attuale, non ci sono stati voti.

In questo caso è safe fare un $accept(i,v)$.

Qualcuno ha votato

Se $j\ge1$ significa che qualcuno ha votato. Se $i$ è il turno attuale (e $j\le i$), i nodi che hanno votato in questo turno hanno inviato una $promise(i,lr,lv)$ ed hanno quindi promesso anche di ignorare eventuali messaggi vacanti riferiti a turni $i'<i$.

Questo significa che $\not\exists \space v'\ne v$ votato nella finestra temporale $[j;i-1]$, per cui è safe fare un $accept(i,v)$.


Detto in parole semplici:

  • Dato che il proposer sceglie i valori in base a quella regola, si ha la garanzia che una volta scelto un valore, da quel momento in poi il consenso su quel valore viene mantenuto.
  • Dato che le $promise$ hanno anche il significato di ignorare eventuali voti ancora aperti per turni precedenti, si ha la garanzia che una volta scelto un valore in un turno, questo non cambi durante un altro turno.

Mancanza di liveness

È facile accorgersi che Paxos non è live, cioè che esistono dei casi per cui il protocollo non fa mai una scelta. La chiave è proprio nel significato della $promise(r,lr,lv)$, in cui l'acceptor promette al proposer di votare per il turno $r$, ma anche di ignorare tutti i messaggi relativi a turni $r'<r$.

Infatti può accadere questo:

Mancanza di liveness in Paxos

Cosa succede se un proposer manda un $prepare(r)$ durante la votazione per il turno precedente?

Il protocollo non dice che i proposer devono aspettare il termine di un turno precedente, quindi possono comportarsi come vogliono.

In questo caso un proposer cattivo invia $prepare(2)$ prima che il proposer 1 possa mandare un $accept(1,5)$, e prima quindi che gli acceptor possano votare il valore. Gli acceptor quindi inizieranno a lavorare per il turno 2 e ignoreranno i messaggi del turno 1.

Questa dinamica può andare avanti all'infinito (anche in altre fasi del protocollo), determinando quindi l'assenza di liveness.

Paxos con coordinator

Una possibile variante di Paxos consiste nell'aggiungere un coordinator che gestisce tutti i turni: in pratica fa da proxy tra i proposer e gli acceptor, diventando quindi lo special proposer per ogni turno.

In questo modo si evitano quegli scenari in cui i proposer si fanno i dispetti a vicenda, che determinano la mancanza di liveness.

Ovviamente eleggere un coordinator (leader election) è a sua volta una forma di consenso, quindi ci mordiamo la coda. Quello che in genere si fa è usare un protocollo debole per scegliere il leader, cioè un protocollo che non deve essere safe, ma che ci va bene lo stesso in relazione al nostro obiettivo, ovvero sicuramente eleva un proposer a coordinator.

Flessibilità dei ruoli

Due parole finali su Paxos riguardano i ruoli. Prima abbiamo visto che esistono i ruoli di:

  • Proposer.
  • Acceptor.
  • Learner.

Se ammettiamo la variante vista poco fa, abbiamo anche un Coordinator.

Bene, ma dobbiamo dire che in Paxos i ruoli sono flessibili, cioè in diversi momenti del turno un nodo può assumere anche altri ruoli. Ad esempio lo special proposer di un certo turno, potrà anche essere uno degli acceptor, e sicuramente sarà anche un learner.

Conclusione

Bello, abbiamo visto Paxos e l'abbiamo inquadrato all'interno del contesto più ampio del consenso nei sistemi distribuiti. Abbiamo visto come funziona, quali sono i ruoli dei nodi, e quali messaggi si scambiano e perché; abbiamo fatto alcuni esempi, e visto perché è safe ma non live.

Ci sono alcune estensioni di Paxos, come quella con il coordinatore, ma anche robetta interessante come Multi-Paxos, ovvero un ambiente in cui sono eseguite più istanze di Paxos, ad esempio per gestire il consenso su una sequenza di valori.

Su Multi-Paxos si basa Fast Paxos: un protocollo che introduce un'ottimizzazione nel primo round, a costo di un po' di tolleranza ai fallimenti e un po' di confusione.

Domande? Lascia un commento! Se ti interessa questa roba e vuoi rimanere aggiornato c'è la newsletter 👍