Non c'è bisogno di tanta immaginazione: possiamo dire che un sistema distribuito è composto da una serie di processi che utilizzano lo stesso protocollo per comunicare tra loro, al fine di risolvere un problema comune.

Questi processi possono trovarsi su reti diverse (come in questa immagine) o nella stessa rete. Ciascun processo potrebbe avere ruoli diversi oppure no; questo dipende dal protocollo.

Schema generale e sciapo di un sistema distribuito

In un sistema distribuito non abbiamo un punto centrale di fallimento, certo, ma si apre la porta a tutta un'altra serie di questioni complicate che vanno gestite, ad esempio:

  • Potremmo perdere messaggi.
  • La rete potrebbe essere lenta.
  • Qualche nodo potrebbe morire.
  • Qualche nodo potrebbe comportarsi in modo strano.

Questo ci porta ad una semplicissima classificazione di processi e sistemi.

Tassonomia sistemi e processi

Un sistema può essere:

  • Sincrono: i processi hanno un "orologio" globale e affidabile; esiste un time bound sui tempi dei messaggi.
  • Asincrono: non abbiamo un divino orologio globale; non sappiamo quanto tempo impiegano i messaggi ad arrivare.

Quanto ai processi, possiamo classificarli in base ai modi con cui possono fallire:

  • Crash-faulty: possono andare in crash.
  • Bizantini: buggati o malevoli; inaffidabili.

Obiettivo

In generale l'obiettivo di un sistema distribuito è di procedere sempre verso la corretta decisione, che si traduce in due proprietà che determinano l'efficienza dei protocolli utilizzati:

  • Safety: la decisione scelta è sempre corretta.
  • Liveness: il protocollo consente sempre di raggiungere una decisione.

Come vedremo, nel prossimo articolo c'è un teorema che ci dice che in un sistema asincrono con processi proni a crash non è possibile avere entrambe le proprietà. In base alle necessità, c'è bisogno di un compromesso tra le due.


Diagramma spazio-tempo

Ok, passiamo a qualcosa di un po' più serio: come rappresentiamo graficamente un calcolo distribuito? Si può usare un diagramma che qualcuno chiama diagramma spazio-tempo, che ha questa forma:

Diagramma spazio-tempo per rappresentare un calcolo distribuito

A una prima occhiata cosa capiamo?

  • Ci sono 3 processi chiamati $p_k$.
  • In ogni evento ci sono degli eventi chiamati $e_k^i$, dove $k$ è il numero di processo e $i$ è il numero di evento all'interno di esso.
  • Tutti gli eventi sono etichettati in questo modo.
  • Alcune coppie di eventi hanno una freccia: sono scambi di messaggio; altri eventi non interagiscono con altri processi.
  • Il tempo scorre.

Possiamo da subito fissare queste due regolette:

  • Se $i < j$, allora $e_k^i \rightarrow e_k^j$
  • Se $e$ è un evento di invio del messaggio $m$ e $e'$ è l'evento di ricezione di $m$, allora $e \rightarrow e'$

Tagli del sistema

Abbiamo un sistema distribuito che fa cose, e in un certo momento noi vogliamo in qualche modo conoscerne lo stato: abbiamo bisogno di qualche protocollo per fare uno snapshot, ma prima di parlarne nel dettaglio dobbiamo capire alcuni concetti propedeutici, ovvero:

  • Cos'è un stato globale.
  • Cos'è un stato locale.
  • Cos'è un taglio.
  • Coerenzaa dei tagli.

Ciascun processo ha una storia personale, ad esempio nell'immagine precedente $p_1$ può essere rappresentato da ${e_1^1,e_1^2,e_1^3}$: questo è il suo stato locale. Formalmente, il local state del processo $k$ è definito come $\sigma_k^n = e_k^1, ...,e_k^n$.

Se uniamo tutti gli stati locali dei processi del sistema, sorpresa, otteniamo lo stato globale, definito come $\Sigma = (\sigma_1,...,\sigma_i) \space \forall p_{1,...,n}$.

Un taglio non è altro che un particolare stato globale ad un particolare istante. Quando facciamo uno snapshot, otteniamo un taglio.

Taglio in un sistema sincrono

Un taglio è la rappresentazione grafica dello stato globale: tutto ciò che sta a sinistra è nello stato; ciò che sta a destra non è ancora accaduto.

Nell'immagine c'è una situazione molto fortunata, ovvero in cui il taglio ottenuto è preciso. Questo si può ottenere solo se il sistema è sincrono, ovvero quando tutti i processi hanno un "orologio sincronizzato" sulla quale possono basarsi. Ma noi vogliamo avere a che fare con sistemi asincroni, in cui un tipico taglio potrebbe avere questo aspetto:

Taglio in un sistema asincrono

Questo taglio è problematico, perché è incoerente: abbiamo catturato un evento di ricezione $e_3^2$ ma non il relativo invio $e_1^3$. Un taglio incoerente è un po' come una foto di un evento accaduto, ma senza la causa.

Calcio di rigore

Un taglio incoerente (o stato globale incoerente, inconsistent cut) è un po' come vedere questa foto, ma con la palla ferma sul dischetto: non può succedere. L'intero sistema è nello stato in cui la palla è stata calciata e il portiere si è buttato, ma la foto catturata mostra ancora la palla ferma (lagga).

Formalmente, un taglio $C$ è coerente se $e \rightarrow e' \wedge e' \in C \Rightarrow e \in C$.
Tra amici, se nel taglio hai l'evento di ricezione, devi avere anche quello di invio.


Snapshot coerenti grazie a Chandy e Lamport

Ok, come possiamo fare degli snapshot sempre coerenti? Esiste il bel protocollo di Chandy-Lamport che ce lo garantisce, assumendo che:

  • I canali siano FIFO: $send_i(m) \rightarrow send_i(m') \Rightarrow delivery_j(m) \rightarrow delivery_j(m')$
  • I canali soddisfino la causal delivery: $send_i(m) \rightarrow send_j(m') \Rightarrow deliver_k(m) \rightarrow deliver_k(m')$.

Dove $send$ e $delivery$ sono rispettivamente gli eventi di invio e ricezione.

La causal delivery non è altro che un FIFO tra coppie di processi, e fa quindi in modo che i messaggi vengano valutati nel giusto ordine anche al lato di ricezione.

Effetto della causal delivery nei sistemi distribuiti

Protocollo di snapshot di Chandy-Lamport

Questo protocollo costruisce sempre degli snapshot coerenti, e per semplificare funziona così:

  • C'è un processo monitor che chiamiamo $p_0$.
  • Tutti i processi si conoscono a vicenda.
  • Il monitor fa partire il protocollo mandando in broadcast un messaggio marker, che significa "fai lo snapshot".
  • Ciascun processo, alla ricezione del marker:
    • Se è il primo che riceve, fa lo snapshot e inoltra il marker a tutti gli altri processi.
    • Altrimenti, smette di ascoltare chi glie l'ha mandato, e aggiunge allo snapshot eventuali eventi la cui ricezione è avvenuta tra il marker precedente e quello attuale.

Protocollo di snapshot di Chandy-Lamport

Il motivo per cui questo protocollo costruisce sempre stati globali coerenti è proprio nelle due assunzioni:

  • Canali FIFO.
  • Causal delivery.

Infatti non è possibile avere uno snapshot del genere:

Protocollo di snapshot di Chandy-Lamport: effetto della causal delivery

Proprio perché $e'$ verrebbe escluso dalla foto, perché valutato dopo l'istante in cui $p_1$ esegue lo snapshot.

Vector clock

Ok, tutto bello. Abbiamo parlato di alcuni concetti in modo un po' astratto: ad esempio abbiamo detto che la causal delivery è una regola per cui gli eventi vengono valutati nel giusto ordine anche a lato di ricezione; bellissimo, ma come avviene nella pratica? Come fa un processo a sapere l'ordine degli eventi degli altri processi?

Ecco, un modo figo per farlo consiste nell'utilizzare i vector clock, cioè un sistema efficiente per etichettare gli eventi in modo tale che l'ordine sia univoco e comprensibile tra diversi processi. Possiamo vedere i vector clock come un meccanismo di timestamp.

Timestamp con vector clock degli eventi di un sistema distribuito

È più facile dedurre le regole guardando l'immagine invece che scrivendole formalmente, ma comunque ciascun processo:

  • Mantiene un vettore in cui ogni posizione corrisponde a un processo del sistema.
  • Inizializza tutte le posizioni a $0$.
  • Incrementa la propria posizione ad ogni evento locale.
  • Allega il vettore ad ogni evento di invio.
  • Confronta il vettore ricevuto con quello attuale, e si prende i valori maggiori.

In un certo senso, i vector clock ci dicono cosa ciascun processo conosce di tutti gli altri.

I vector clock ci danno anche sette belle proprietà, le cui più interessanti sono:

Strong clock condition

Sia $VC(e)$ il valore del vettore all'istante dell'evento $e$:

$e \rightarrow e' \Leftrightarrow VC(e) < VC(e')$.

Simple strong clock condition

$e_i \rightarrow e_j \Leftrightarrow VC(e_i)[i] \le VC(e_j)[i]$

Weak gap detection

$VC(e_i)[k] < VC(e_j)[k] \wedge k \ne j \Rightarrow \exists e_k \space | \space e_k \not\rightarrow e_i \wedge e_k \rightarrow e_j$

Informalmente, osservando due vettori in $e_i$ ed $e_j$ sui rispettivi processi distinti $p_i$ e $p_j$, si può capire se c'è stato un evento su un altro processo $p_k$ che $p_j$ conosce ma non $p_i$.


Conclusione

Perfetto, questi sono i concetti di base per poter ragionare sui sistemi distribuiti. Abbiamo capito che lavorare su sistemi asincroni non è banale, e che un esempio di questa difficoltà è l'interrogazione di tutti i processi per capire lo stato globale del sistema.

Questo ci ha portato al concetto di taglio e di coerenza.

Abbiamo visto un protocollo per ottenere snapshot sempre coerenti, che è stato tirato fuori da due personcine chiamate Chandy e Lamport.

Alla fine abbiamo visto un vero meccanismo per etichettare gli eventi tramite vector clock, e alcune proprietà interessanti.

I prossimi articoli riguarderanno il tema del consenso distribuito.


Se hai domande o semplicemente vuoi dire qualcosa, lascia un commento qui sotto. Se vuoi anche rimanere aggiornato sul nuovo materiale trovi un form per iscriverti alle newsletter.