Un sistema distribuito è un insieme di calcolatori indipendenti che appaiono all'utente come un unico sistema coerente. Più formalmente, si tratta di computer che contengono molteplici processori connessi da una rete di comunicazione. Leslie Lamport, uno dei padri fondatori del settore, offre una definizione ironica e profonda: «Un sistema distribuito è quello in cui il crash di un computer di cui non hai mai sentito parlare ti impedisce di lavorare.»
Il professore Ricci apre questo modulo sottolineando l'importanza dell'inquadramento concettuale e filosofico dei sistemi distribuiti, non solo dell'aspetto tecnico. Le tecnologie cambiano rapidamente — e con l'avvento dell'IA la parte tecnica di basso livello viene sempre più delegata — ma la comprensione dei principi fondamentali resta essenziale per un ingegnere. Questa lezione si inserisce nel percorso iniziato con il modulo di Omicini sui sistemi distribuiti e con la parte laboratoriale di Giovanni Ciatto, collegando la programmazione concorrente (già studiata nel primo modulo) alla dimensione distribuita.
La differenza fondamentale rispetto ai sistemi paralleli è che nei sistemi distribuiti la comunicazione avviene esclusivamente attraverso lo scambio di messaggi su una rete, non tramite memoria condivisa. Questo cambia radicalmente il modo di progettare e ragionare sui programmi.
Perché adottare un'architettura distribuita? Le ragioni sono molteplici. La scalabilità permette di aggiungere risorse al sistema incrementando la capacità complessiva. La modularità e l'eterogeneità consentono di integrare componenti diversi, potenzialmente di fornitori diversi. La condivisione di dati e risorse è intrinseca al modello distribuito. La struttura geografica del problema spesso richiede una soluzione distribuita: sistemi bancari, piattaforme social, servizi cloud globali. L'affidabilità migliora perché il sistema può tollerare il guasto di alcuni nodi. Il costo ridotto deriva dalla possibilità di usare hardware commodity anziché supercomputer dedicati.
Esiste però un compromesso fondamentale: l'efficienza. Aggiornare una posizione di memoria è ancora molto più veloce che inviare un messaggio attraverso una rete. Questa differenza è alla base di molte delle sfide ingegneristiche del corso.
| Sistemi Paralleli | Sistemi Distribuiti |
|---|---|
| Memoria condivisa (fisica o virtuale) | Nessuna memoria condivisa |
| Orologio comune a tutti i processori | Nessun orologio comune |
| Comunicazione via bus o rete ad alta velocità | Comunicazione via rete a latenza variabile |
| Scalabilità limitata dall'architettura | Scalabilità orizzontale potenzialmente illimitata |
| Guasto dell'intero sistema se un componente critico si rompe | Tolleranza ai guasti: altri nodi subentrano |
Il professore Ricci identifica tre macro-sfide che caratterizzano ogni sistema distribuito, tre «assenze» che definiscono il campo di gioco e impongono vincoli profondi a ogni algoritmo distribuito.
È impossibile sincronizzare perfettamente gli orologi di processori diversi a causa dell'incertezza intrinseca nei tempi di comunicazione. Anche usando protocolli come NTP, rimane sempre una finestra di incertezza. Gli orologi fisici non possono essere usati per sincronizzare eventi in un sistema distribuito: non esiste un «adesso» globale. Questa è la ragione per cui Lamport ha introdotto il concetto di tempo logico, che vedremo nella seconda parte del capitolo.
A differenza dei sistemi concorrenti tradizionali (dove i thread condividono la memoria dello stesso processo), in un sistema distribuito ogni nodo ha la propria memoria privata. È impossibile per un processore conoscere lo stato globale del sistema in un dato istante. Questa assenza rende difficile osservare e verificare proprietà globali del sistema, come la mutua esclusione o l'assenza di deadlock.
In un sistema asincrono (dove non esiste un limite superiore noto al tempo di consegna dei messaggi), è impossibile distinguere tra un processore lento e un processore guasto. Se non riceviamo una risposta entro un certo tempo, non sappiamo se il nodo è caduto o se il messaggio sta semplicemente impiegando più del previsto. Questa incertezza ha implicazioni profonde, come vedremo con il teorema FLP e il problema del consenso nel prossimo capitolo.
Nei sistemi asincroni, l'assenza di un limite superiore al tempo di comunicazione rende teoricamente impossibile risolvere alcuni problemi fondamentali, come il consenso in presenza di guasti. Nella pratica si utilizzano timeout e ipotesi di sincronia parziale per aggirare questa limitazione.
Enunciato da Eric Brewer nel 2000 come congettura e dimostrato formalmente da Gilbert e Lynch nel 2002, il teorema CAP stabilisce che un sistema distribuito che condivide dati può offrire al massimo due delle tre seguenti proprietà:
Il teorema ha implicazioni pratiche immediate. Supponiamo due nodi su lati opposti di una partizione di rete. Se permettiamo ad almeno un nodo di aggiornare lo stato, i nodi diventano inconsistenti (perdiamo C). Se scegliamo di preservare la consistenza, un lato deve comportarsi come se non fosse disponibile (perdiamo A). Solo quando i nodi comunicano possiamo preservare sia C che A (perdendo P).
La scelta tra C, A e P dipende dal contesto applicativo. Un sistema bancario sceglierà consistenza e partizione (CP), sacrificando la disponibilità durante una partizione. Un social media può scegliere disponibilità e partizione (AP), accettando consistenza eventuale. Un sistema monolitico su una singola macchina può scegliere consistenza e disponibilità (CA), ma in questo caso non è veramente distribuito.
Il teorema CAP va interpretato nel contesto delle partizioni di rete. In assenza di partizioni, un sistema può fornire sia C che A. È solo quando si verifica una partizione che si deve scegliere. Brewer stesso, in una retrospettiva del 2012 (CAP Twelve Years Later), ha chiarito che la scelta non è binaria ma riguarda quanta consistenza o disponibilità si è disposti a sacrificare operazione per operazione.
Nell'interpretazione classica, il teorema CAP ignora la latenza, ma nella pratica latenza e partizioni sono profondamente correlate. Brewer stesso, nell'articolo del 2012, ha chiarito questo punto cruciale: operativamente, l'essenza del CAP si manifesta durante un timeout, un periodo in cui il programma deve prendere una decisione di partizione (partition decision).
Le due opzioni sono nette:
Pragmaticamente, una partizione è un limite di tempo sulla comunicazione. Se non si riesce a raggiungere la consistenza entro quel limite, ci si trova di fronte a una partizione e quindi a una scelta tra C e A per quella specifica operazione. Questi concetti catturano il problema progettuale centrale: i due lati del sistema stanno avanzando senza comunicare? In altre parole, il tempo è un fattore determinante. Un sistema che tollera secondi di inconsistenza (DynamoDB, Cassandra) opera diversamente da uno che richiede consistenza immediata (un DB relazionale tradizionale).
La latenza non è solo un problema di prestazioni: è un problema di correttezza. Quando due parti del sistema non possono comunicare entro un tempo accettabile, devono decidere se procedere (rischiando inconsistenza) o bloccarsi (sacrificando disponibilità). Non esiste una scelta giusta in assoluto, solo scelte consapevoli.
Nell'ultima lezione del corso il professore riprende il teorema CAP con un secondo angolo di lettura, utile come sintesi. Qualsiasi sistema che condivide dati in rete può avere al massimo due delle tre proprietà:
Il professore approfondisce un aspetto spesso frainteso: la latenza. Nell'interpretazione classica, il teorema CAP ignora la latenza, ma in pratica latenza e partizioni sono profondamente correlate. Durante un timeout, il programma deve fare una scelta fondamentale: cancellare l'operazione (riducendo la disponibilità) o procedere (rischiando l'inconsistenza).
Il professore spiega che, pragmaticamente, una partizione è un limite di tempo sulla comunicazione. Se non si riesce a raggiungere la consistenza entro quel limite, ci si trova di fronte al partition decision: il bivio tra consistenza e disponibilità. Due nodi che procedono senza comunicare — questo è il dilemma fondamentale.
Questi concetti catturano la questione progettuale centrale riguardo alla latenza: due parti del sistema stanno andando avanti senza comunicazione? La risposta determina se si sta violando la consistenza o la disponibilità.
Il professore ricorda che dal modello (happened-before, potential causality) si passa ai meccanismi: orologi logici e vector clocks per implementare il modello happened-before. Questi meccanismi — trattati nelle sezioni che seguono — sono gli strumenti concreti che i programmatori distribuiti utilizzano per ordinare eventi, rilevare consistenza e costruire algoritmi corretti.
Per ragionare formalmente sui sistemi distribuiti, abbiamo bisogno di modelli di computazione. Il modello adottato in questo corso è semplice ma potente:
Questo modello descrive un sistema distribuito asincrono: non ci sono limiti noti a priori sui tempi di consegna. È il modello più generale e più difficile per cui progettare algoritmi, ma è anche il più realistico per internet e le reti moderne. Il professore sottolinea che questa modellazione serve non solo per descrivere, ma per verificare proprietà di correttezza e per ragionare su tutti i possibili scenari di esecuzione di un programma distribuito.
flowchart LR
subgraph CANALI["Modello di Computazione Distribuita"]
direction LR
P1["Processo P"] -->|"canale (P→Q)"| Q1["Processo Q"]
Q1 -->|"canale (Q→P)"| P1
end
P1 -->|"invio messaggio"| M["messaggio m"]
M -->|"ritardo finito
(arbitrario)"| Q1
Ricordate le assunzioni del modello: canali unidirezionali, buffer infiniti, nessun errore, nessun ordinamento, ritardo arbitrario ma finito. Queste definiscono il contesto in cui gli algoritmi distribuiti che studieremo devono operare.
In questo modello, ogni processo è descritto come un insieme di stati, una condizione iniziale e un insieme di eventi. Ogni evento può modificare lo stato del processo e lo stato di al più un canale incidente a quel processo. Il comportamento di ciascun processo può essere descritto visivamente attraverso diagrammi di transizione di stato.
Nel contesto distribuito, gli eventi si classificano in tre tipi fondamentali: eventi interni (computazione locale, modificano solo lo stato del processo), eventi di send (invio di un messaggio su un canale) ed eventi di receive (ricezione di un messaggio da un canale). La distinzione è importante perché a seconda dell'applicazione può essere più naturale modellare il comportamento in termini di eventi piuttosto che di stati.
Esplorate i diversi tipi di stato che un processo può assumere durante la sua esecuzione nel sistema distribuito usando l'esploratore interattivo.
I diagrammi a eventi (event diagrams) sono spesso più adatti dei diagrammi di stato per catturare l'evoluzione di un sistema distribuito, perché mettono in primo piano le relazioni causali tra eventi che accadono in luoghi diversi.
Il modello interleaving è il più semplice e deriva direttamente dai modelli usati per i sistemi concorrenti tradizionali (quelli del primo modulo del corso). L'idea è di assumere un ordinamento totale tra tutti gli eventi del sistema distribuito, come se le esecuzioni dei vari processi fossero mescolate in una singola sequenza lineare.
Prendiamo l'esempio della lezione: due processi P (nodo N1) e Q (nodo N2). P inizializza A=1 (P1), invia A sul canale CH (P2), stampa ok (P3). Q stampa subito (Q1), riceve da CH ottenendo R (Q2), stampa R (Q3). Nel modello interleaving, una possibile esecuzione è P1, P2, Q1, Q2, P3, Q3. Un'altra: Q1, P1, P2, P3, Q2, Q3. Ogni ordinamento totale è un'esecuzione valida, purché rispetti l'ordine degli eventi all'interno di ciascun processo. Ma il modello interleaving ha limitazioni importanti.
Il modello interleaving non cattura i guasti (failure). Presuppone sempre che, ad esempio, Q2 possa essere eseguita. Ma se il nodo N2 va giù, Q2 non verrà mai eseguita. Per ragionare sui possibili fail serve un modello più astratto. Inoltre, il modello presuppone una sequenza globale osservabile che in realtà non esiste in un sistema distribuito: nessun nodo ha una visione completa di tutti gli eventi.
Il problema fondamentale è che in un sistema distribuito non esiste un osservatore globale in grado di produrre una sequenza totale degli eventi. Qualsiasi ordinamento totale sarebbe un artefatto, non una proprietà intrinseca del sistema. È questa l'osservazione che porta Lamport al modello successivo.
Lamport osservò che in un sistema veramente distribuito si possono definire solo ordinamenti parziali tra gli eventi, usando la relazione di happened-before (→). È una relazione causale: se un evento a potrebbe aver causato un evento b, allora a è accaduto prima di b.
La relazione happened-before (→) è la più piccola relazione che soddisfa:
Due eventi che non sono in relazione happened-before si dicono concorrenti: e || f = non (e → f) e non (f → e).
flowchart LR
subgraph P["Processo P (nodo N1)"]
direction TB
p1["P1: A := 1"] --> p2["P2: send(A, CH)"] --> p3["P3: print ok"]
end
subgraph Q["Processo Q (nodo N2)"]
direction TB
q1["Q1: print ready"] --> q2["Q2: receive(CH, R)"] --> q3["Q3: print R"]
end
p2 -.->|"send → receive
⇝"| q2
Nel diagramma, le frecce continue rappresentano l'ordine all'interno dello stesso processo: P1 → P2 → P3, Q1 → Q2 → Q3. La freccia tratteggiata rappresenta la comunicazione: P2 (send) → Q2 (receive). Per transitività, P1 → Q2 e P2 → Q3. Non c'è invece relazione tra P1 e Q1: sono eventi concorrenti, perché non esiste una catena causale che li connetta.
Una run nel modello happened-before è una tupla (E, →) dove E è l'insieme di tutti gli eventi e → è un ordine parziale su E tale che tutti gli eventi all'interno di un singolo processo sono totalmente ordinati. È questo il modello che useremo come base per gli algoritmi di ordinamento e coordinazione.
La relazione happened-before è stata introdotta da Lamport nel celebre articolo «Time, Clocks, and the Ordering of Events in a Distributed System» (1978). È il fondamento concettuale su cui si basano orologi logici, orologi vettoriali e la maggior parte degli algoritmi distribuiti che studieremo. La transitività è la proprietà chiave che permette di costruire catene causali anche lunghe.
Il modello happened-before assume un ordinamento totale tra gli eventi all'interno dello stesso processo. Tuttavia, non è vero che tutti questi eventi abbiano una relazione causa-effetto reale. Due eventi consecutivi in uno stesso processo potrebbero essere completamente indipendenti, come la ricezione di due messaggi da porte diverse che aggiornano oggetti distinti. L'ordine temporale non implica causalità.
La relazione di causalità reale è un ordine parziale anche all'interno dello stesso processo, ma è spesso difficile o costosa da determinare. Per questo si utilizza la relazione di causalità potenziale (→p), la più piccola relazione che soddisfa:
Due eventi non correlati da →p si dicono indipendenti. Esempio concreto: un processo con due thread che accedono a insiemi di oggetti mutualmente disgiunti. Gli eventi dei due thread non hanno relazione causale tra loro, anche se accadono sullo stesso processo. La causalità potenziale li tratta come indipendenti.
Un diagramma di causalità potenziale è equivalente all'insieme di tutti i diagrammi happened-before che sono consistenti con esso (cioè →p ⊆ →). La causalità potenziale è più astratta e meno vincolante: incorpora un maggior grado di nondeterminismo, il che è utile per applicazioni come il debugging distribuito.
Quale modello usare dipende dall'applicazione. I tre modelli offrono diversi livelli di astrazione e catturano diversi aspetti del comportamento di un sistema distribuito.
Ordinamento: totale tra tutti gli eventi del sistema.
Quando usarlo: per la verifica formale di programmi distribuiti. Per dimostrare proprietà come l'assenza di deadlock, l'interleaving è sufficiente ed è il modello più semplice da trattare analiticamente.
Limitazione: presuppone una sequenza globale osservabile che nei sistemi distribuiti non esiste. Non cattura i guasti.
Ordinamento: parziale tra eventi, totale all'interno di ogni processo.
Quando usarlo: per catturare il comportamento del sistema e verificare se una certa proprietà globale è diventata vera in un'esecuzione. L'osservazione si basa sull'ordinamento causale, non su un tempo globale.
Vantaggio: non richiede un osservatore globale. È il modello più adatto per descrivere esecuzioni in sistemi distribuiti asincroni.
Ordinamento: parziale anche all'interno dello stesso processo.
Quando usarlo: per il debug distribuito, dove ci si chiede se una proprietà globale avrebbe potuto diventare vera in un'esecuzione. È vantaggioso catturare solo gli ordini parziali corrispondenti alla causalità effettiva.
Vantaggio: elimina ordini forzati arbitrariamente, dando il massimo nondeterminismo e quindi il massimo potere espressivo.
La relazione gerarchica è importante: un programma distribuito può essere visto come un insieme di diagrammi di causalità potenziale che può generare. Ogni diagramma di causalità potenziale equivale a un insieme di diagrammi happened-before. Ogni diagramma happened-before equivale a un insieme di sequenze globali (interleaving). La scelta del modello determina quanta complessità viene catturata e quanta viene astratta.
Per implementare concretamente il modello happened-before, Lamport introdusse il concetto di orologio logico (logical clock). L'idea è assegnare un numero (timestamp) a ogni evento in modo tale che la relazione happened-before sia preservata numericamente.
Un orologio logico C assegna a ogni evento a del processo Pi un numero Ci(a) tale che:
∀ a ∈ Pi, b ∈ Pj : se a → b allora Ci(a) < Cj(b)
La Clock Condition è soddisfatta se:
Usando un semplice contatore C per ogni processo:
Usate il simulatore interattivo qui sotto per vedere il funzionamento passo-passo con due processi.
Con gli orologi logici vale: a → b implica C(a) < C(b), ma NON vale il viceversa. C(a) < C(b) non implica a → b. I contatori logici danno un ordinamento totale che avrebbe potuto accadere, non quello che è effettivamente accaduto. Per determinare se due eventi sono in relazione causale o sono concorrenti servono gli orologi vettoriali.
Proposti indipendentemente da Fidge (1988) e Mattern (1988), gli orologi vettoriali assegnano a ogni evento un vettore di dimensione k (numero di processi), tale che:
∀ a, b : a → b ⇔ VC(a) < VC(b)
La relazione è bi-direzionale: non solo la causalità implica un ordine nei vettori, ma l'ordine nei vettori implica causalità. Per due vettori v, w:
Se due vettori sono incomparabili (né v < w né w < v), gli eventi corrispondenti sono concorrenti. È questa capacità di rilevare la concorrenza che rende gli orologi vettoriali superiori a quelli scalari.
L'implementazione estende gli orologi logici: ogni processo Pi mantiene un vettore V di contatori (dimensione = numero processi). V[i] viene incrementato a ogni evento. Il vettore completo viene trasmesso nei messaggi. All'arrivo, il ricevente aggiorna ogni componente con max(Vproprio[k], Vricevuto[k]).
Esempio concreto dalla lezione: tre processi A, B, C partono da [0,0,0]. Dopo alcuni eventi interni, B arriva a [0,2,0] e C a [0,0,1]. Quando B invia un messaggio ad A, il vettore [0,3,0] viene trasmesso. A lo riceve e aggiorna: per ogni k, prende max(A[k], Vricevuto[k]). Così A acquisisce conoscenza dello stato di B e C.
Esplorate l'implementazione nel codice commentato:
La lezione successiva, dedicata agli algoritmi distribuiti, apre con un richiamo a questi modelli di computazione: sono il fondamento su cui poggiano tutti gli algoritmi distribuiti discussi nel prossimo capitolo. La tabella riassume il confronto in forma compatta.
| Modello | Relazione tra eventi | Utilizzo |
|---|---|---|
| Interleaving | Ordine totale globale | Verifica di proprieta |
| Happened-before (→) | Ordine parziale: processi totalmente ordinati, causalita tra messaggi | Osservazione del comportamento |
| Potential causality (→p) | Ordine parziale anche all'interno dello stesso processo | Debugging distribuito |
Il limite degli orologi logici e che non permettono di determinare se due eventi sono concorrenti o in relazione causale. A questo serve il vector clock.
Il vector clock estende l'orologio logico usando un array di N contatori: VC(a) < VC(b) se e solo se a → b. Questo permette di determinare con precisione la relazione causale tra due eventi qualsiasi. La regola di aggiornamento e simile: incremento del componente proprio tra eventi successivi, piggyback del vettore sui messaggi, e componente-wise max al ricevimento.
/* Regole del vector clock */
Pi::
V[i] := V[i] + 1 /* tra eventi successivi */
/* send(m): piggyback V con il messaggio */
/* receive(m): */
for k in 1..N:
V[k] := max(V[k], msg.V[k])I vector clock sono usati dall'algoritmo centralizzato di mutua esclusione, e la loro generalizzazione (matrice di clock) e alla base dell'ordinamento causale — entrambi trattati nel prossimo capitolo.
Assenza di un orologio condiviso, assenza di memoria condivisa, assenza di un rilevamento accurato dei guasti (failure detection).
Un sistema distribuito che condivide dati può offrire al massimo due delle tre proprietà: Consistency (C), Availability (A), Partition Tolerance (P). La scelta dipende dal contesto applicativo.
Perché chiamata locale e chiamata remota hanno differenze sostanziali (latenza, possibili guasti, serializzazione). Nasconderle porta a deadlock, race condition e perdita di controllo. Lo spiega l'articolo di Waldo et al. (1994) «A Note on Distributed Computing».
Interleaving (ordinamento totale), Happened-Before (ordinamento parziale, totale nello stesso processo), Causalità Potenziale (ordinamento parziale anche nello stesso processo). Ogni diagramma di causalità potenziale equivale a un insieme di diagrammi happened-before; ogni happened-before equivale a un insieme di sequenze interleaving.
Ogni processo ha un contatore C. Regola 1: incremento tra eventi. Regola 2: il timestamp C è incluso nei messaggi inviati (piggybacking). Regola 3: alla ricezione, C = max(C, Tm) + 1. Questo garantisce: se a → b, allora C(a) < C(b).
Gli orologi vettoriali permettono di determinare la relazione di causalità in entrambe le direzioni: a → b se e solo se VC(a) < VC(b). Permettono quindi di rilevare la concorrenza tra eventi, impossibile con i contatori scalari.
Ogni processo include il proprio vettore di clock nei messaggi di richiesta. Il coordinatore usa la condizione di eleggibilità per ritardare le richieste finché tutte quelle che le precedono causalmente non sono arrivate. w.v ≤ reqDone garantisce l'ordine causale.
In una rete asincrona, anche con un solo processo che può arrestarsi, il consenso è impossibile da risolvere. L'incapacità di distinguere un processo guasto da uno lento impedisce di garantire terminazione, accordo e integrità simultaneamente.
Non esiste un protocollo f-resiliente per N ≤ 3f (N processi, f guasti bizantini). Serve N ≥ 3f + 1 per tollerare f guasti con comportamento arbitrario.
È un'architettura fault-tolerant dove ogni server ha una macchina a stati e un log replicato. L'algoritmo di consenso (Paxos, Raft) gestisce il log: se un server applica «set x = 3» come n-esimo comando, nessun altro applicherà un comando diverso come n-esimo. Il sistema appare come un'unica macchina a stati affidabile.