Computazione distribuita: modelli e orologi logici

1. Che cosa cambia quando il sistema è distribuito

Un sistema distribuito è un insieme di calcolatori, ciascuno con i propri processori, collegati da una rete di comunicazione. La definizione più citata è una battuta di Leslie Lamport: «sai di avere un sistema distribuito quando il crash di un computer di cui non conoscevi l'esistenza ti impedisce di lavorare».

Ogni sistema distribuito è anche concorrente, non viceversa: interleaving, race condition e deadlock restano, e si aggiungono nuovi vincoli. Le slide elencano perché si sceglie un'architettura distribuita invece di una parallela:

• scalabilità, modularità ed eterogeneità dei componenti;
• condivisione di dati e di risorse;
• struttura geografica del problema (banche, servizi globali);
• affidabilità, perché il guasto di un nodo non ferma gli altri;
• basso costo, con hardware comune al posto di un supercalcolatore.

Il motivo per non distribuire tutto è l'efficienza: aggiornare una cella di memoria resta molto più veloce che inviare un messaggio.

Programmare un sistema distribuito significa scrivere un programma le cui parti girano su nodi diversi e interagiscono solo scambiandosi messaggi in rete. Il modello canonico è un insieme di processi «pesanti» che comunicano con messaggi su canali, ciascuno con più thread che condividono memoria al suo interno. Sopra questo modello si è cercato di riportare i paradigmi tradizionali, con la chiamata di procedura remota (RPC) e gli oggetti distribuiti (CORBA, Java RMI); perché questa trasparenza non funziona, e quali sono le alternative, è il tema del capitolo 19. Qui ci occupiamo dei modelli: come descrivere le esecuzioni e ordinarne gli eventi. Il capitolo 18 li usa negli algoritmi.

2. Le tre assenze

Tre assenze distinguono un sistema distribuito da uno concorrente su una sola macchina, e sono le sfide di ogni algoritmo distribuito.

Il clock. L'informazione impiega tempo a viaggiare, al più alla velocità della luce, e gli orologi accumulano derive: protocolli come NTP sincronizzano solo in modo approssimato. Un timestamp di System.currentTimeMillis() è il tempo di quella macchina, confrontabile con quello di un'altra solo a grana grossa (giorni sì, millisecondi no). Tra nodi diversi resta un solo legame causa-effetto certo: la ricezione di un messaggio viene dopo il suo invio. Da qui nasce la relazione happened-before (sezione 5).

La memoria. Negli attori la memoria non condivisa era una disciplina imposta su una macchina che la memoria la condivide; qui è un fatto fisico. Uno spazio condiviso, come uno spazio di tuple, va costruito sopra la rete come servizio di un middleware.

I guasti. Se la risposta a una richiesta non arriva, il destinatario può essere caduto o il messaggio ancora in viaggio. Per andare avanti si usa un timeout: oltre un certo tempo si assume che l'altro sia guasto. È un'assunzione che può essere sbagliata, e reintroduce una forma di sincronia. Il failure detector del cluster di Pekko, che dà un livello di sospetto anziché un sì/no, ne è un esempio (capitolo 16).

3. Il teorema CAP e la latenza

Il teorema CAP (Brewer, 2000) dice che un sistema in rete che condivide dati può avere al più due di queste tre proprietà:

• C, consistenza: equivale ad avere un'unica copia aggiornata del dato;
• A, alta disponibilità del dato, anche per gli aggiornamenti;
• P, tolleranza alle partizioni di rete.

L'esempio delle slide usa due nodi che replicano lo stesso dato e si ritrovano ai lati opposti di una partizione. Se almeno un nodo accetta aggiornamenti, le due copie divergono: si perde C. Se si vuole preservare C, un lato deve comportarsi come non disponibile: si perde A. Solo finché i nodi comunicano si hanno sia C sia A, ma allora non si sta tollerando nessuna partizione.

Letto con precisione, il teorema non offre tre combinazioni equivalenti. In un sistema distribuito le partizioni capitano, non si scelgono. Quindi il contenuto di CAP è questo: quando c'è una partizione, bisogna rinunciare a C oppure ad A, e la scelta si può fare operazione per operazione. Senza partizioni un sistema può essere sia consistente sia disponibile. «CA» descrive solo un sistema che non tollera partizioni, cioè di fatto non distribuito. Un conto bancario tende a preferire C, rifiutando le operazioni finché la partizione non si risolve; un carrello della spesa o un feed social preferiscono A, rispondendo subito e riconciliando le copie dopo.

La latenza

La latenza è il tempo che un messaggio impiega ad arrivare, o una richiesta a ricevere risposta. Nella formulazione classica CAP la ignora, ma latenza e partizioni sono legate (Brewer, 2012). In pratica la scelta di CAP si presenta durante un timeout, quando il programma deve prendere la decisione di partizione:

• annullare l'operazione, riducendo la disponibilità;
• procedere, rischiando l'inconsistenza.

Pragmaticamente una partizione è quindi un limite di tempo sulla comunicazione: se la consistenza non si raggiunge entro quel limite, per quell'operazione c'è una partizione e bisogna scegliere tra C e A. La domanda progettuale diventa: i due lati stanno andando avanti senza comunicare?

4. Il modello di computazione e l'interleaving

Per ragionare sulle esecuzioni serve un modello, come nella prima parte. Il corso, seguendo il libro di Garg, assume un sistema asincrono: un insieme debolmente accoppiato di processi che si scambiano messaggi su canali unidirezionali, con queste ipotesi.

• I canali hanno buffer infinito e non commettono errori.
• Non si assume nessun ordinamento dei messaggi.
• Ogni messaggio inviato arriva dopo un ritardo arbitrario ma finito.
• Lo stato di un canale è la sequenza dei messaggi inviati e non ancora ricevuti.

Un processo ha un insieme di stati, una condizione iniziale e un insieme di eventi. Ogni evento può cambiare lo stato del processo e lo stato di un canale collegato a esso: gli eventi sono interni, di invio (send) o di ricezione (receive). Il comportamento di un processo si può disegnare come diagramma di stato, ma spesso è più naturale descriverlo con gli eventi.

Le slide distinguono tre modelli, dal più concreto al più astratto:

L'interleaving applicato a due nodi

Il programma della lezione ha due processi su due nodi e un canale ch:

P (nodo N1)                 Q (nodo N2)
p1: A := 1                  q1: print "ready"
p2: send(ch, A)             q2: receive(ch, R)
p3: print "ok"              q3: print R

Si può costruire il diagramma di stato come nella prima parte. Lo stato è la tupla (istruzione di P, istruzione di Q, contenuto di ch, A, R): gli unici elementi condivisi sono i canali, le variabili sono locali. La send è asincrona e non si blocca; la receive su canale vuoto blocca Q. Ogni cammino del grafo è una sequenza totale di eventi, per esempio p1, p2, q1, q2, p3, q3.

Il modello funziona per verificare proprietà, ma ha due limiti. Primo, impone un ordine totale che nella realtà nessuno può osservare: non esiste un osservatore globale che veda tutti gli eventi in sequenza. Secondo, non cattura i guasti: assume che q2, prima o poi, venga eseguita. Se il nodo N2 cade, q2 non avviene mai, e chi la aspettava resta bloccato.

5. Happened-before: l'ordine che si può ricostruire

L'osservazione di Lamport (1978) è che in un sistema veramente distribuito si possono definire solo ordini parziali tra gli eventi. Ogni processo P_i genera una sequenza alternata di stati ed eventi s_i,0 e_i,1 s_i,1 e_i,2 … La relazione happened-before (→) è la più piccola relazione che soddisfa tre regole:

1. Ordine locale: se e ed f sono dello stesso processo ed e precede immediatamente f (e ⋖ f), allora e → f.
2. Messaggio: se e è l'invio di un messaggio ed f è la ricezione dello stesso messaggio su un altro processo (e ↝ f), allora e → f.
3. Transitività: se esiste g con e → g e g → f, allora e → f.

La seconda regola riguarda un messaggio preciso, non una send e una receive qualsiasi: se nel canale ci sono più messaggi, la relazione lega ogni invio solo alla ricezione di quel messaggio. Una run nel modello happened-before è una coppia (E, →), con E l'insieme degli eventi e → un ordine parziale in cui gli eventi di ogni processo sono totalmente ordinati. Graficamente, e → f se e solo se nel diagramma c'è un cammino orientato da e a f. Due eventi non legati in nessuna delle due direzioni sono concorrenti: e ∥ f se né e → f né f → e.

Nell'esempio, p1 → q3 perché p1 → p2 (ordine locale), p2 → q2 (messaggio) e q2 → q3 (ordine locale). Viene spontaneo dire che anche q1 viene prima di p3, ma non è vero: la send di P non aspetta nessuno, quindi P può eseguire p2 e p3 molto prima che Q esegua q1. Nessuna catena collega q1 e p3, e allora sono concorrenti. Lo stesso vale per p1 e q1, per p2 e q1, per p3 e q3. «Prima» non si riferisce a un tempo fisico: è la relazione a dare significato alla parola.

6. Causalità potenziale e scelta del modello

Happened-before ordina totalmente gli eventi di uno stesso processo, ma non tutti hanno un rapporto di causa-effetto. Dentro un processo la vera causalità è un ordine parziale, spesso difficile o costoso da determinare. Si usa allora la causalità potenziale →_p, la più piccola relazione tale che:

1. se un evento e può causare un evento f dello stesso processo, e →_p f;
2. se e è l'invio di un messaggio ed f la sua ricezione, e →_p f;
3. se e →_p f e f →_p g, allora e →_p g.

Due eventi non legati da →_p si dicono indipendenti. Gli esempi delle slide sono due: un processo che riceve due messaggi da porte diverse e con ognuno aggiorna un oggetto diverso, per cui le due ricezioni non si causano a vicenda anche se una è avvenuta prima dell'altra; un processo con due thread che accedono a insiemi di oggetti disgiunti.

Un diagramma di causalità potenziale è l'ordine parziale (E, →_p). Un diagramma happened-before (E, →) è consistente con esso se →_p ⊆ →, e il diagramma di causalità potenziale equivale all'insieme di tutti i diagrammi happened-before consistenti con esso.

Quale modello usare

I tre modelli sono annidati. Un programma distribuito è l'insieme dei diagrammi di causalità potenziale che può generare; ognuno equivale a un insieme di diagrammi happened-before; ognuno di questi equivale a un insieme di sequenze globali di eventi, cioè di interleaving. Quale usare dipende dall'applicazione:

Gli stessi ordini tornano sui messaggi: oltre all'assenza di vincoli ci sono l'ordine FIFO, causale e totale, trattati nel capitolo 18.

7. Orologi logici di Lamport

Dal modello si passa ai meccanismi: come etichettare ogni evento a run time in modo da rispettare happened-before? Lamport propone un orologio logico: una funzione C che assegna a ogni evento a del processo P_i un numero C_i(a) tale che valga la clock condition:

per ogni a ∈ P_i, b ∈ P_j: se a → b allora C_i(a) < C_j(b).

Bastano due condizioni: eventi dello stesso processo hanno valori crescenti; se a è l'invio di m da parte di P_i e b la sua ricezione in P_j, allora C_i(a) < C_j(b). La transitività fa il resto. L'implementazione usa un contatore per processo e tre regole:

ogni evento di Pi:        C := C + 1              -- regola 1
invio di m:               m porta il timestamp Tm := C (piggybacking)   -- regola 2
ricezione di m in Pj:     C := max(C, Tm), poi C := C + 1 (regola 1)    -- regola 3

Esempio della lezione: P ha eseguito quattro eventi e invia un messaggio con timestamp 4. Q, che era a 2, alla ricezione porta il clock a max(2, 4) + 1 = 5, e gli eventi successivi di Q avranno 6, 7… Se Q fosse già stato a 18, sarebbe passato a 19: il clock di chi è «più avanti» non torna indietro.

Il limite è che la condizione vale in una sola direzione: se a → b allora C(a) < C(b), ma C(a) < C(b) non implica a → b. Nel programma della sezione 4, con queste regole p3 ha clock 3 e q3 ha clock 4, eppure p3 ∥ q3. Gli interi sono sempre confrontabili, quindi un singolo numero non può dire «questi due eventi sono concorrenti». Ordinando per clock si ottiene un ordine totale che avrebbe potuto verificarsi, non necessariamente quello che si è verificato.

8. Orologi vettoriali

Gli orologi vettoriali (Fidge e Mattern, 1988) superano il limite tenendo traccia di ciò che ogni processo sa degli altri. Con N processi, ogni processo mantiene un vettore di N contatori: la propria componente conta i propri eventi, le altre registrano il progresso degli altri processi per quanto gli è noto. È il principio che ritroveremo in quasi tutti gli algoritmi distribuiti: con ogni messaggio si propaga anche la conoscenza che si ha degli altri.

ogni evento di Pi:        V[i] := V[i] + 1
invio di m:               m porta una copia di V
ricezione di m in Pj:     per ogni k: V[k] := max(V[k], Vm[k]), poi V[j] := V[j] + 1

I vettori si confrontano componente per componente:

• v ≤ w se v[k] ≤ w[k] per ogni k;
• v < w se v ≤ w e v[j] < w[j] per almeno un j (cioè v ≤ w e v ≠ w).

Con queste regole vale l'equivalenza che mancava: a → b se e solo se V(a) < V(b). Se né V(a) < V(b) né V(b) < V(a), i vettori sono incomparabili e gli eventi sono concorrenti. Per esempio [2,2,1] < [2,4,1], quindi il primo evento è avvenuto prima del secondo; [2,5,4] e [3,3,3] sono incomparabili, quindi i due eventi sono concorrenti.

I limiti sono pratici. Ogni processo deve conoscere il numero N dei processi, e il vettore viaggia in ogni messaggio con dimensione proporzionale a N. Se i processi entrano ed escono dinamicamente, lo schema va esteso, e le varianti per insiemi dinamici sono un tema di ricerca. Un processo che cade smette semplicemente di produrre eventi; se riparte deve ripristinare la propria componente, mentre le altre le riapprende dai messaggi.

Laboratorio: happened-before, Lamport e vettori a confronto

Costruisci un'esecuzione scegliendo eventi interni, invii e consegne, oppure parti dal programma della lezione. Il laboratorio calcola i clock di Lamport e i vettori con le regole appena viste e, per due eventi che scegli, ricava la relazione direttamente dal diagramma, mostrando la catena di eventi quando esiste. Cerca coppie in cui il clock di Lamport è minore ma gli eventi sono concorrenti: i vettori, invece, non sbagliano mai.

Verifica le tue conoscenze