Quando 2 nodi si scambiano messaggi, si devono sincronizzare. Il ricevente deve avere un timestamp che sia maggiore o uguale di quello che riceve. In caso sia rimasto indietro, fa un balzo in avanti e si sincronizza.

Deadlock distribuiti

Non paghi di dover gestire il deadlock in mille modi diversi, ecco che dobbiamo gestirlo anche in sistemi distribuiti.

Al solito, quando ho un nodo che attende un altro che attende un altro che attende il primo, ho un deadlock.

Sistema semplice: metto un time-out. Se ci mette troppo, qualcosa va storto. È in effetti il metodo più usato perché più semplice da implementare.

Altrimenti, posso tentare di rilevare e risolvere i deadlock, attraverso un protocollo asincrono e distribuito, realizzato tramite RPC. C'è sempre il mio grafo di cui devo rilevare la ciclicità, ma in questo caso i nodi sono distribuiti, e devono quindi comunicare tra loro per realizzare un grafo.

Per evitare di inviare una pletora di messaggi, invio solamente le condizioni di attesa verso il nodo da cui attendo.

Una sequenza di attesa ha più o meno questa faccia:

 Ein -> t1,1 -> t2,1 -> Eout
 Ein = evento in ingresso
 t1,1 = transazione 1 sul nodo 1
 t2,1 = transazione 2 sul nodo 1
 Eout = evento in uscita

I nodi inviano verso Eout, cioè il nodo che attendono, solo una condizione di attesa in cui una transazione vecchia sta attendendo una transazione nuova: in termini di id, devo avere che ti > tj.

Il nodo che riceve la sequenza la deve combinare con la sua, e poi inviarla al suo Eout. Nella combinazione, devo collassare tutte le transazioni e far rimanere solamente i nodi, così da poter rilevare il ciclo.

Urge spiegazione migliore e più completa...

Protocolli per il commit distribuito

Questa è un'altra gatta da pelare, perché tutti i nodi devono eseguire insieme il commit.

Il protocollo più diffuso è il two-phase commit, che NON c'entra con il 2PL, anche se ha lo stesso nome.

In questo protocollo, la decisione di fare commit o abort è presa da una terza parte, il cosiddetto transaction manager (TM). Il TM deve gestire i resource manager (RM), ovvero i nodi coinvolti nella transazione distribuita.

Il TM deve mantenere in proprio un log, con questi tre tipi di record:

• prepare = si sta preparando al commit, e salva la lista dei RM coinvolti
• global commit / global abort
• complete = è terminato il 2PC

RM parimenti mantiene un log:

• ready = l'RM ha tutti i lock che gli servono, ed è pronto
• begin, insert, delete, update = relativi alla transazione in atto

Se un RM si dice ready, in quel momento perde la sua autonomia. Deve attendere che TM gli dica che cosa fare. Entra in una fase di incertezza in cui deve attendere che gli altri RM coinvolti comunichino con il TM, e che quindi il TM possa prendere decisioni. Non può fare proprio niente, in questo momento.

Se invece, per qualche motivo, il RM stabilisce di essere non ready, invia comunicazione al TM, e abortisce per conto suo. Infatti, per far abortire una transazione distribuita è sufficiente che 1 RM dica NO. Se è lui stesso a dire NO, ha la certezza che la transazione abortirà, e quindi non attende istruzioni dal TM.

1^a fase:

• il TM manda il PREPARE a tutti i RM, e attende, impostando un timeout
• ogni RM dice READY o NON-READY, e nel secondo caso fa tutto da solo, come abbiamo appena visto
• il TM raccoglie le risposte da tutti, e decide per un GLOBAL COMMIT o GLOBAL ABORT

2^a fase: la decisione del TM deve essere comunicata a tutti

• il RM scrive nel suo log e ivnia un ACK al TM
• RM esegue la sua transazione
• il TM raccoglie gli ACK da tutti. Se un ACK tarda, attende con un nuovo timeout e rimanda la decisione

Siccome stiamo parlando di nodi sulla rete, possono accadere diversi spiacevoli accidenti: possono andare down sia i RM che il TM, perdere messaggi, o addirittura cadere la rete intera.

RM down

Un RM cade, e si presume che prima o poi si risveglierà (se non ci pensa da solo, ci pensa l'admin).

Deve guardare il suo log. Se ha un ready, chiede al TM che cosa fare. Tutte le transazioni dubbie vengono messe in READY, e viene chiesto al TM che cosa fare.

TM down

Anche qui, il TM si riavvia e guarda il log.

Se vede un PREPARE, può:

• mandare un GLOBAL ABORT a tutti i RM coinvolti (come dicevo sopra, nel record PREPARE è salvata la lista di tutti i RM coinvolti), e si prepara alla 2^a fase
• ripetere la 1^a fase

Se vede un GLOBAL COMMIT / ABORT, ripete la 2^a fase.

Se vede un COMPLETE, non c'è problema, vuol dire che è morto dopo aver messo a posto tutti.

Perdita di messaggi

Se scade il timeout della fase 1, il TM non ha modo di determinare se i messaggi persi siano stati un PREPARE o un READY. Nel dubbio, invia un GLOBAL ABORT e si riparte.

Se invece viene perso un GLOBAL oppure un ACK, è il timeout della fase 2 che scade, e quindi viene ripetuta solo lei.

Cade la rete

Quando cade la rete, vuol dire che essa si partiziona in parti che non comunicano. Se TM e i suoi RM stanno nella stessa partizione, ok, vanno avanti lo stesso. Altrimenti, si abortisce tutto.

Ottimizzazioni

2PL è molto pesante, perché si scambia un mucchio di messaggi. Si può cercare di risparmiare un po' qua e là.

Abort presunto: il TM riceve richieste da RM incerti, e non ha nessuna informazione su di essi: invia un GLOBAL ABORT a tutti (che cosa sono i RM incerti?)

Read only: se ho un RM che riceve istruzioni read-only, lo ignoro nella 2^a fase, che tanto non può dare contributo significativo (non interessa il commit di una lettura).

Varianti

C'è il lock distribuito a 4 fasi, in cui c'è un TM di backup. Il TM "normale" comunica tutte le sue decisioni PRIMA al TM di backup, così se va giù c'è il backup che comunque ne sa qualcosa. Ma è pesante...

Poi c'è quello a 3 fasi in cui un nodo fa il sostituto del TM, se quest'ultimo cade. Il problema è che la finestra di incertezza si allunga. Il problema con sto sistema è che se la rete si partiziona, ed ogni partizione elegge il suo TM, è l'anarchia. Ecco perché è poco usato.

Classificazione delle interrogazioni

È una classificazione fatta da IBM, però più o meno vale per tutti.

• richieste remote = transazioni read-only, effettuate ad 1 singolo DBMS remoto
• transazioni remote = tutti i comandi che voglio ma ad 1 DBMS remoto
• transazioni distribuite = tutti i comandi che voglio, ma ad un numero arbitrario di DBMS, però inviando 1 comando per DBMS
• richieste distribuite = come sopra, ma 1 comando può riferirsi a più DBMS

I problemi insorgono quando il DBMS si trova a dover garantire, come fa con DBMS singoli, le proprietà di isolamento ed atomicità. Deve decidere come dividere la query in sub-query, e scambiare i dati tra di essi. L'ottimizzazione che si fa è quella per la banda, perché è quella che costa di più, e poi per uso di CPU.

Serializzabilità globale

Se ho una query divisa in più sub-query, ognuna inviata ad un server, posso avere che questi server singolarmente hanno uno schedule serializzabile, e quindi tutto ok. Ma è possibile anche che invece questi schedule, visti globalmente, NON siano serializzabili.

La serializzabilità globale è una proprietà che mi dice che occorre uno schedule seriale S equivalente a tutti gli schedule locali S_i risultanti ad ogni nodo.

Ciò vuol dire che la proiezione di S sul nodo i deve essere uguale a S_i.

Lo posso ottenere utilizzando il 2PL stretto, che è il 2PL base, con in aggiunta la richiesta che posso rilasciare il lock solo dopo il commit o l'abort. Se ogni DBMS implementa il 2PL stretto, ottengo uno schedule globale conflict-serializzabile.

Un altro modo per ottenere questo effetto è quello di avere un timestamp paragonabile per tutti i nodi, ma il problema è proprio avere un orologio distribuito.

Metodo di Lamport

Tua sorella e tua cugina balzano in avanti

È un metodo per ordinare globalmente tutti gli elementi.

C'è un timestamp con 2 gruppi di cifre: un gruppo è l'id del nodo, l'altro è quello dell'evento.

Quando 2 nodi si scambiano messaggi, si devono sincronizzare. Il ricevente deve avere un timestamp che sia maggiore o uguale di quello che riceve. In caso sia rimasto indietro, fa un balzo in avanti

(:title BDC - Lezione del 21 aprile 2008:)

 :: BDC - Lezione del 21 aprile 2008 ::

Torna alla pagina di BDC

Architetture distribuite

Ci sono diversi paradigmi per distribuire i dati:

• client - server
• db distribuiti: più server usati dalla stessa applicazione
• db paralleli: i compiti sono distribuiti
• db replicati
• data warehouse = gestiscono i dati dedicati al supporto alle decisioni (qualsiasi cosa esso sia)

E abbiamo 2 tipologie di architetture: OLTP e OLAP.

OLTP = OnLine Transaction Processing, ed è un'architettura specializzata nel gestire migliaia di transizioni al secondo secondo le proprietà ACID.

OLAP = OnLine Application Processing, è rivolta alle analisi dei dati per le Data Warehouse di cui sopra.

Ma in generale, i server hanno sia funzioni OLTP che OLAP.

Infine, ci sono delle proprietà che i sistemi distribuiti hanno (o dovrebbero avere):

• portabilità = usando uno standard come SQL posso portare dati da un ambiente all'altro
• interoperabilità = posso far dialogare a run-time sistemi diversi

Client - Server

Il client fa la parte attiva, mentre il server quella passiva, in quanto ascolta le richieste del client e cerca di soddisfarle. In generale, il client vuole sapere poche cose alla volta, e tutte in sequenza.

Usando quest'architettura, è possibile separare fisicamente il client dal server, ottimizzando così entrambe le cose. Ottimizzare per un client significa renderlo il più adatto possibile all'utente. Per quanto riguarda il server, invece, ottimizzare vuol dire che funzioni meglio, consumi meno risorse etc.

L'architettura client - server permette di dividere bene tra i compiti, ed è ben supportata da SQL tramite interrogazioni che vanno dai client ai server, e che tornano risultati dai server ai client. SQL, essendo uno standard, fa sì che queste cose siano portabili ed interoperabili, come volevamo sopra.

Un server multithreaded ha più unità di esecuzione: c'è una coda di ingresso ed una di uscita, ed il dispatcher distribuisce le richieste. Se ho un numero di server che varia in funzione del numero di richieste, allora si dice che si ha una classe di server.

Ci sono altre distinzioni nelle architetture client - server: two-tier e three-tier.

Nel paradigma two-tier ho 2 livelli: il server, ed il client che fa tutto quello che serve per interrogare il server. Si parla quindi di un thick client, perché ha molte funzionalità in quanto deve fare tutto lui (a parte poi le operazioni effettive).

Invece, nel paradigma three-tier c'è un application server che gestisce le applicazioni. Il client si connette all'application server, il quale fa tutte le robe. Il client deve quindi solo comunicare con l'utente. Ecco perché si dice thin client.

BD distribuite

Si ha una base di dati distribuita quando almeno un client interagisce con server distribuiti. I vantaggi sono:

• rispeccha il fatto che spesso le aziende sono fisicamente distribuite qua e là
• è flessibile e modulare
• è affidabile, se replico i dati

Per quanto riguarda i tipi di DBMS usati, le bd distribuite possono essere omogenee (quando tutti i DBMS sono uguali) o eterogenee (quando uso DBMS di tipo diverso). A seconda delle dimensioni, ho distribuzioni locali o geografiche.

Quale che sia la tipologia della bd distribuite, astrattamente essa è una bd unica, e come tale va progettata. In pratica è solo l'implementazione fisica che andrà a spantegarsi su più server: nelle fasi di progettazione è un'entità unica.

Quello che avviene, dopo la progettazione in un pezzo unico, è la frammentazione, cioè la partizione di una relazione in diversi frammenti. Ci sono 2 tipi di frammentazione:

• orizzontale = a livello di tupla. Ogni server mantiene una selezione delle tuple di una certa relazione R, la cui unione restituisce la tupla originaria.
• verticale = a livello di attributi, in cui ogni server mantiene solo alcune colonne della R

Le proprietà che devo garantire si chiamano completezza e ricostruibilità.

• completezza = i dati devono esserci, per quanto spantegati
• ricostruibilità = devo poter ricostruire la tabella iniziale, con chiavi e tutto

Con una frammentazione orizzontale, ho che ogni server mantiene alcune tuple. Quindi, i server NON hanno tuple in comune. Nella frammentazione verticale, invece, divido per attributi. Però, per garantire le proprietà di cui sopra, è neccessario che ogni frammento verticale si porti dietro la chiave della R, altrimenti avrei tuple che non riesco a ricostruire.

Quindi, facendo l'unione dei frammenti orizzontali o il join dei frammenti verticali, devo poter ricostruire la R originaria.

Queste proprietà si cerca di soddisfarle nella fase di normalizzazione, di cui avevamo parlato nel corso di Elementi di Basi di Dati, ma su cui non ci eravamo soffermati.

Una volta che ho individuato i miei frammenti, verticali od orizzontali che siano, devo decidere dove metterli. È lo schema di allocazione che mi dice quale frammento è salvato su quale server.

Questo schema può essere:

• ridondante, ovvero ci sono più copie dello stesso frammento su server diversi
• non ridondante: una copia di un frammento per server.

L'allocazione ridondante è più performante, in generale, perché posso fare riferimento a frammenti locali invece che ripescarli da chissà dove. Il problema è che è difficile da mantenere: infatti, la modifica ad un frammento deve essere replicata su tutti i frammenti in giro per il sistema.

Teniamo quindi bene a mente che allocazione NON È la stesa cosa di frammentazione. La frammentazione è un'operazione concettuale. L'allocazione è un'operazione fisica che serve per realizzare eventualmente una frammentazione.

Tenendo presente questa distinzione, posso avere diversi livelli di trasparenza, che mi dicono quanto un programma applicativo deve conoscere delle frammentazioni e delle allocazioni interne al sistema.

Trasparenza di frammentazione: il programma NON SA NIENTE di frammenti o server, ma vede tutto come una bd unica, e si comporta come tale.

Trasparenza di allocazione: il programma conosce i frammenti, ma non sa dove sono allocati fisicamente.

Trasparenza di linguaggio: il programma è a conoscenza sia dei frammenti che dei server, e deve gestire il tutto da solo.

Assenza di trasparenza: non c'è interoperabilità, nel senso che il linguaggio che si usa è diverso, e quindi ciao.

...continua...

Torna alla pagina di BDC