Nell'ambito dei sistemi distribuiti, il consenso è un problema fondamentale. Se abbiamo n processi che eseguono lo stesso protocollo, consenso significa che tutti devono essere d'accordo sulla stessa decisione.

Ma nell'articolo precedente abbiamo visto che i processi possono fallire, in particolare possono andare in crash o essere bizantini. Per questo garantire il consenso non è per niente semplice: come facciamo a mettere tutti d'accordo, se qualche processo muore sempre? Possiamo proseguire anche se una percentuale di processi muore? Come avvisiamo i processi morti resuscitati delle decisioni precedenti? Serve farlo? Cosa succede se troppi nodi falliscono?

Insomma, ci sono una serie di domande a cui ora come ora non sappiamo rispondere, ma procedendo con questo articolo e quelli successivi, avremo un'idea più chiara e potremo darci delle risposte.

Il consenso sta da tutte le parti: quando due client modificano insieme un documento Google, sotto c'è qualche protocollo di consenso; quando usiamo servizi per replicare basi di dati c'è qualche protocollo di consenso; quando navighiamo in giro per Internet e i contenuti ci vengono serviti da una CDN, questa esegue qualche protocollo di consenso.

Ok, belle chiacchiere, ma cosa significa nella pratica consenso?

Ecco, un esempio di problema di consenso è il cosiddetto atomic commit, ovvero una decisione che vogliamo considerare atomica, ma in realtà è composta da varie operazioni. Ad esempio, se siamo più persone e vogliamo scegliere una sola pizza da ordinare potremmo tutti proporre un tipo, ma alla fine ciò che è importante è arrivare a una sola decisione da comunicare al cameriere.

Il nostro ordine quindi diventa atomico, nel senso che le varie proposte individuali non devono più importare perché c'è un'unica decisione finale corretta a cui tutti hanno detto di sì.

Questo problema ha una sua formalizzazione: vediamola.

Atomic commit

  • Tutti i nodi devono essere d'accordo sulla stessa decisione.

  • Non è possibile se il sistema è asincrono e i processi possono fallire (vedremo dopo perché).

  • C'è un processo coordinatore.

  • Ci sono vari processi partecipanti.

  • L'obiettivo è decidere qualcosa su una transazione: commit o abort.

Inoltre abbiamo alcune proprietà:

  • AC1: tutti i processi che raggiungono una decisione, raggiungono la stessa.
  • AC2: un processo non può cambiare idea.
  • AC3: il commit può essere raggiuto solo se tutti i processi hanno votato .
  • AC4: se non ci sono fallimenti e tutti i processi hanno votato , allora la decisione deve essere commit.
  • AC5: dopo una risoluzione dei fallimenti, la transazione deve essere completata (recovery).

Benissimo. Esiste un protocollo per risolvere l'atomic commit? Sì, ed è il commit a due fasi.

2-phase-commit (2PC)

Diagramma di attività del commit a 2 fasi (2PC)

Il protocollo funziona così:

  • Il coordinator manda una richiesta di voto a tutti i participant.
  • Ogni participant risponde al coordinator con o no.
  • Se tutte le risposte sono , allora manda a tutti un commit; altrimenti manda abort.
  • Ogni participant aggiorna il proprio stato con quello ricevuto dal coordinator.

Possiamo notare che se il participant vota no, può già mettersi in stato di abort, perché sa già che la decisione finale sarà quella.

Bene, carino.

Quali sono i possibili problemi di questo protocollo?

  • Se il coordinator fallisce il protocollo non va avanti.
  • Se i nodi falliscono, potremmo non raggiungere mai il commit.

Per far fronte al problema della debolezza del coordinator come punto centrale di fallimento, possiamo usare il cooperative termination protocol, ovvero uno stratagemma per far terminare il protocollo in una certa situazione.

Cooperative termination protocol

Immaginiamo una situazione in cui il coordinator fallisce prima di inviare la decisione finale.

Scenario nel 2PC in cui il coordinator fallisce prima di inviare la decisione finale

Il protocollo non terminerà perché tutti i nodi non riceveranno mai la decisione finale, perché il coordinator si pianta prima di mandarla. Qui c'è poco da fare. Esaminiamo un caso in cui si può fare qualcosa.

Scenario in cui usiamo il cooperative termination protocol insieme al 2PC per propagare la decisione finale

In questa situazione il coordinator fallisce subito dopo aver mandato la decisione finale ad almeno un nodo; ci rendiamo quindi conto che qualcosa si può fare: basta che questo nodo fortunato propaghi la decisione a tutti i suoi amichetti.

Per la precisione, questa propagazione avviene su richiesta: se un nodo è nello stato di incertezza e non riceve nulla dal coordinator, dopo un certo tempo potrà bussare agli altri participant e chiedere se qualcuno di loro ha già la risposta finale.

Con il cooperative termination protocol certamente non risolviamo definitivamente i problemi, ma almeno diamo al protocollo qualche chance in più di terminare con successo.

Recovery

Abbiamo parlato spesso di fallimenti di tipo crash. Ok, cosa fa un nodo quando si risveglia? Sa chi è? Deve chiedere qualcosa agli altri processi? Deve votare di nuovo?

Tutte queste domande possono essere auto-risposte dal nodo, se questo mantiene un suo log locale di tutto ciò che impara. Questo registro è chiamato DTlog, e serve ai nodi per ricostruire gli stati della votazione quando si risvegliano dopo un crash.

Ci sono delle regolette minime di compilazione, ovvero ogni nodo deve scrivere almeno queste informazioni:

  • Il coordinator scrive "start-2pc" all'inizio del protocollo.
  • Quando un participant vota , deve scriverlo prima di mandare il messaggio.
  • Quando un participant vota no, deve scriverlo.
  • Quando un participant riceve una decisione, la scrive.
  • Se il coordinator sceglie commit, deve scriverlo prima di inviare i messaggi.
  • Se il coordinator sceglie abort, deve scriverlo.

Semplice, no?


Concludiamo questo articolo spiegando finalmente perché qui e nel precedente articolo dico che il consenso non si può raggiungere in certe condizioni.

Teorema FLP

Esiste un bel teorema che prende il nome dai suoi inventori: Michael Fischer, Nancy Lynch e Michael Patterson. Questo teorema è anche chiamato FLP impossibility result, ed essenzialmente dice che:

In un sistema distribuito asincrono in cui sono possibili fallimenti di tipo crash, non è possibile avere un protocollo deterministico per raggiungere il consenso.

Questo sembra un po' strano, dato che prima abbiamo visto un semplice protocollo deterministico per realizzare l'atomic commit, che è una forma di consenso; abbiamo anche fatto vedere che in certe situazioni il protocollo può terminare anche se c'è qualche crash. Perché quindi diciamo che non si può raggiungere il consenso?

Beh, perché bisogna capire che queste tre persone hanno definito il concetto di consenso con due proprietà: safety e liveness. In particolare, quando diciamo "raggiungere il consenso" stiamo implicitamente dicendo che lo facciamo in modo safe e live.

In parole semplici, queste due proprietà significano:

  • Safety: la scelta fatta dal protocollo è corretta, nel senso che non è possibile dimostrare (in un momento successivo) che la decisione corretta era un'altra.
  • Liveness: il protocollo consente sempre di raggiungere una decisione (corretta o sbagliata che sia).

Per esempio, il 2PC è banalmente non live, perché se il coordinator fallisce potremmo non riuscire a decidere niente; è invece safe perché una volta collezionati tutti i , la decisione corretta deve necessariamente essere commit.

Per questo spesso leggiamo una versione più esplicita del Teorema FLP, cioè:

In un sistema distribuito asincrono in cui sono possibili fallimenti di tipo crash, non è possibile avere un protocollo di consenso deterministico che sia safe e live.

Possiamo convincerci di questo con una piccola dimostrazione: supponiamo di avere un sistema in cui due nodi devono sempre essere d'accordo su un valore: quindi se un nodo cambia da 0 a 1, anche l'altro deve farlo.

Se ammettiamo la possibilità di avere anche un solo crash, possono accadere due cose:

Dimostrazione grafica del teorema FLP, evidenziando le conseguenze su safety e liveness

  • Nel primo caso un processo cambia il suo valore, ma fallisce prima che l'altro possa accorgersene; a questo punto il processo vivo rimane bloccato perché non sa quale è la scelta corretta. Sacrifichiamo quindi liveness per rimanere safe.
  • Nel secondo caso il processo fallisce prima che l'altro possa accorgersene, ma questo se ne frega e mantiene il proprio valore in nome del progresso; peccato che dopo un po' il morto resuscita e scoprono di essere in disaccordo. Abbiamo sacrificato safety per rimanere live.

Carino eh?

Conclusione

Con questa seconda parte abbiamo affrontato il tema del consenso e capito perché è fondamentale; ci siamo posti delle domande e ci siamo risposti, e abbiamo capito che se i nodi muoiono e siamo in un sistema asincrono, è difficile raggiungere il consenso in modo sia safe che live.

Per esempio il meccanismo di Proof-of-Work che usa Bitcoin per determinare il consenso su un blocco è non-safe e non-live, ma riesce ad essere entrambi con alta probabilità (è infatti non deterministico, ma probabilistico).

Nel prossimo articolo vedremo Paxos, che invece è safe ma non live.


Se hai domande o in generale vuoi dire qualcosa, scrivi un commento :pencil:. Ah, se conosci qualcuno a cui questa roba può essere utile, mandagliela eh :thumbsup: