09 architetture distribuite - CNR 1112/Slides/09... · 2015-06-19 · Architetture distribuite Basi...

Architetture distribuite

Basi di dati: Architetture e linee di evoluzione -Seconda edizioneCapitolo 6

Appunti dalle lezioni

Basi di Dati 2 – Prof. Antonio d’Acierno Architetture distribuite 2

Sommario

� Architetture client-server� Basi di dati distribuite� Basi di dati parallele� Basi di dati replicate


Paradigma client-server

�� Tecnica per Tecnica per strutturare sistemi strutturare sistemi softwaresoftware

�� Viene resa Viene resa "pubblica" una "pubblica" una "interfaccia di "interfaccia di servizi"servizi"

�� Due tipologie di Due tipologie di sistemi:sistemi:

–– CLIENT CLIENT �� richiedono i servizirichiedono i servizi

–– SERVER SERVER �� forniscono i serviziforniscono i servizi

serviziservizi

richiestirichiestidal CLIENTdal CLIENT

svolti daisvolti daiSERVERSERVER


Client-server nei sistemi informativi

� Separazione funzionale ideale– CLIENT

� presentazione dell'informazione

– SERVER � gestione dei dati

– SQL � il linguaggio ideale per separare gli ambienti

� CLIENT – formula query, elabora risultati

� SERVER – esegue query

� RETE � trasferisce i comandi di attivazione (es: di procedure SQL) e i risultati


CLIENTCLIENTcompone richiestecompone richieste

in SQLin SQL

esegue richiesteesegue richiestein SQLin SQL

SERVERSERVER

Architettura client-server classica


CLIENTCLIENT

compone richiestecompone richiestein SQLin SQL

SERVERSERVERAPPLICATIVOAPPLICATIVO

DATABASEDATABASESERVERSERVER

esegue richiesteesegue richiestein SQLin SQL

CLIENTCLIENTCLIENTCLIENTrichiederichiedeapplicazioniapplicazioni

Architettura con server applicativo


Sommario



DB Distribuiti

� Un DB distribuito è una collezione di dati: – Logicamente appartenenti allo stesso sistema.

� I dati hanno cioè caratteristiche tali che li legano insieme cosicché un DB distribuito è diverso da un insieme di DB centralizzati.

– Sono distribuiti su più server collegati in rete.


Motivazioni

� Natura intrinsecamente distribuita delle organizzazioni

� Evoluzione degli elaboratori – Aumento della capacità' elaborativa– Riduzione di prezzo

� Evoluzione della tecnologia dei DBMS– Standard di interoperabilità

� Evoluzione delle reti


DB Distribuiti: Classificazione

� Se su tutti i server è usato lo stesso DBMS si parla di DB omogenei.

� Se i DBMS sono diversi si parla di DB eterogenei.

� E’ anche importante sapere se i vari server sono collegati da una LAN o da una WAN.


Tipici esempi di applicazioni

Sistemi di Sistemi di prenotazioneprenotazioneintegrati, sistemiintegrati, sistemiinterbancariinterbancari

Applicazioni Applicazioni gestionaligestionaliinterfunzionaliinterfunzionali

Eterogeneo

Sistemi di Sistemi di prenotazione,prenotazione,applicazioni applicazioni finanziariefinanziarie

Applicazioni Applicazioni gestionali gestionali e finanziariee finanziarie

Omogeneo

WANLAN


Problemi delle basi di dati distribuite

� Autonomia e cooperazione� Trasparenza� Efficienza� Affidabilità


Autonomia e cooperazione

�� L'esigenza di L'esigenza di autonomiaautonomia::–– Una reazione ai ''Centri EDP'' Una reazione ai ''Centri EDP''

–– Portare competenze e controllo laddove vengono Portare competenze e controllo laddove vengono gestiti i datigestiti i dati

–– Rendere la maggior parte delle applicazioni NON Rendere la maggior parte delle applicazioni NON distribuite (!)distribuite (!)

�� L'esigenza di L'esigenza di cooperazionecooperazione::–– Alcune applicazioni sono intrinsecamente distribuite Alcune applicazioni sono intrinsecamente distribuite

e richiedono l'accesso a pie richiedono l'accesso a piùù basi di datibasi di dati


Frammentazione dei dati

� Posso frammentare lo schema– Vincoli di integrità referenziale non sono più esprimibili in

maniera immediata� Posso frammentare la tabella

– Frammentazione orizzontale� I frammenti sono insiemi di tuple con lo stesso schema.� La relazione originale si ottiene con l’unione.

– Frammentazione verticale� I vari frammenti hanno uno schema ottenuto come sottoinsieme

dello schema della relazione di partenza.� La relazione originale si ottiene con un join.

� La frammentazione deve essere garantire completezza e ricostruibilità.


Frammentazione orizzontale: esempio

� CONTO-CORRENTE (NUM-CC, FILIALE, SALDO)� TRANSAZIONE (NUM-

CC,DATA,PROGR,AMMONTARE, CAUSALE)� 3 filiali� Frammentazione principale

– CONTO1 = σ Filiale=1 (CONTO-CORRENTE)– CONTO2 = σ Filiale=2 (CONTO-CORRENTE)

– CONTO3 = σ Filiale=3 (CONTO-CORRENTE)

� Frammentazione derivata– TR1 = Transazioni relative a conti di CONTO1

– TR2 = Transazioni relative a conti di CONTO2– TR3 = Transazioni relative a conti di CONTO3


Frammentazione verticale: esempio

� Impiegato(CF,Indirizzo, Dipartimento)� Dipartimento(Nome,Città)� AnagraficaImpiegato(CF,Indirizzo)� DipartimentoImpiegato(CF,Dipartimento)

� La chiave è replicata (⇒ la relazione èricostruibile)

� Il vincolo di integrità referenziale si applica ad una sola relazione


Allocazione dei dati

� Ogni frammento è realizzato tramite una o piùtabella in un db allocato su un certo server.

� Allocazione – non ridondante

� ogni frammento o relazione viene allocato su un solo server.

– ridondante � alcuni frammenti o relazioni sono allocati su più server.


Interazione con un DB distribuito

� Livello di trasparenza� Trasparenza di Frammentazione

– Interagiamo con il db distribuito come se fosse centralizzato.� Non ci dobbiamo preoccupare né della eventuale frammentazione

né delle allocazioni.

� Trasparenza di Allocazione– Dobbiamo conoscere come sono frammentati i dati ma

dobbiamo indicarne la allocazione.� Se il sistema è ad allocazione ridondante non dobbiamo indicare a

quale replica ci riferiamo per l’accesso (trasparenza di replicazione)


Livelli di Trasparenza

� Trasparenza di Linguaggio– Dobbiamo indicare sia i frammenti sia la loro

allocazione ma non dobbiamo preoccuparci dei vari dialetti SQL usati dai vari sistemi.

� Assenza di trasparenza– Il sistema è eterogeneo e i dialetti SQL sono diversi e

noi dobbiamo specificare le varie query opportunamente.


Livelli di Trasparenza: Esempio

� Problema: Selezionare il nome di un fornitore dato il suo numero

Fornitore

Fornitore1

Fornitore2

[email protected] (Oracle)

[email protected] (SQLServer)

[email protected] (SQLServer)



� Trasparenza di frammentazione

select nome from fornitore where numero = 125



� Trasparenza di allocazioneselect nomefrom fornitore1where numero = 125

Se non lo trovoselect nomefrom fornitore2where numero = 125



� Trasparenza di linguaggioselect nome intofrom [email protected] numero = 125

Se non lo trovoselect nomefrom [email protected] numero = 123

� Assenza di trasparenza– Bisogna tenere conto dei dialetti SQL nella

formulazione delle query


Transazioni e DB Distribuiti

� Richieste remote– Operazioni di sola lettura indirizzate ad un solo DBMS

� Transazioni remote– Insieme arbitrario di comandi SQL indirizzate ad un solo DBMS

� Transazioni distribuite (2PC)– Indirizzate a più DBMS, ma ogni comando SQL fa riferimento a dati

gestiti da un solo DBMS.

� Richieste distribuite (2PC + Ottimizzazione Distribuita)– Transazioni arbitrarie, in cui il singolo comando SQL può fare

riferimento anche a dati gestiti da più DBMS


Acidità delle transazioni distribuite

� Ragioneremo sulle transazioni distribuite� Consistenza

– Limiti tecnologici impongono che i vincoli imposti siano solo locali.

– Consistenza globale �consistenza locale

� Persistenza– I meccanismi utilizzati per il caso centralizzato

restano validi– La gestione corretta dei log a livello locale �

persistenza globale


Acidità delle transazioni distribuite

� Isolation– Se ogni sistema usa il 2PL stretto la scheduling

globale è serializzabile� Problema del deadlock distribuito

– Se ogni sistema usa il metodo dei timestamps, ed essi sono assegnati in maniera globale alle sottotransazioni,lo scheduling globale èserializzabile.

� Atomicity– È il problema che bisogna affrontare e la cui

soluzione richiede l’introduzione di nuovi record nel file di log.


Commit a 2 fasi (2PC)

� I server vengono denominati:– Resource Manager (RM);– Transaction Manager (TM).

� L’analogia più calzante è quella di un matrimonio con i promessi sposi (i RMs) ed un celebrante (TM).


Commit a 2 fasi (2PC)

� Il celebrante chiede ai partecipanti se vogliono sposarsi (cioè se vogliono concludere positivamente la transazione).– Se tutti i partecipanti sono d’accordo, il

matrimonio si fa.– Se almeno uno dei partecipanti non è d’accordo

il matrimonio si annulla.


Durability

� Ogni DBMS ha ovviamente la capacità di gestire applicazioni in modo autonomo.– Un progetto accurato della distribuzione dovrebbe

garantire che la maggior parte possibile delle applicazioni operino localmente.

� Nel caso di transazioni distribuite sono possibili diversi malfunzionamenti;– Caduta del TM;– Caduta di uno di RM;– Caduta della Rete.

� Nuovi record nei log.


2PC in assenza di guasti

� Rapide scritture su log e scambi di messaggi

TM

RM

prepare

preparemsg

readyreadymsg

globaldecision

decisionmsg

localdecision ack

msg

complete

finestra di incertezza


Nuovi record nel log del TM

� Ai record classici si aggiunge:– Record di prepare

� Il TM scrive sul proprio log l’identificativo dei processi RM partecipanti.

– Record global commit / global abort� Si riporta la decisione presa relativamente alla transazione

in esame.

– Record di complete� Il protocollo è stato portato a termine.


Nuovi record nel log del RM

� Ai record classici si aggiunge il record di ready:– Se accetto:

� Indica l’irrevocabile decisione di partecipare al commitglobale.

� Deve essere scritto quando si è in uno stato stabile (risorse bloccate) e rispettando la WAL e la commit precedenza per il proprio log.

� Una volta scritto questo record, l’RM perde ogni autonomia decisionale.

– Se rifiuto:� Poi vediamo


To be noted …

� Un RM dopo essersi dichiarato “ready” perde la sua autonomia e attende la decisione del TM. Un guasto del TM lascia l’RM in uno stato di incertezza, in cui tutte le risorse acquisite con lock sono bloccate.

� L’intervallo tra la scrittura dei record ready e commit o abort è chiamato finestra di incertezza. Il protocollo èprogettato per minimizzare la sua durata.

� I protocolly di recovery sono svolti dai TM o RM dopo i guasti; ristabiliscono uno stato finale corretto che dipende dalla decisione globale del TM


Cosa accade se ….

� Qualche RM non manda la decisione locale– Allo scadere del time-out si opta per global abort


Cosa accade se ….

� Qualche RM decide l’abort della transazione– Anziché mandare un messaggio di ready, manda un messaggio

di not-ready.� Il processo che gestisce l’RM termina dopo l’abort


Cosa accade se ….

� Cade il TM e l’ ultimo record è prepare– Problema: il messaggio di prepare è arrivato a tutti, a nessuno o

a qualcuno?– Alla ripresa del TM si può decidere per un global abort e

svolgendo la seconda parte del protocollo.

� E’ anche possibile cercare di ripetere la prima fase.


Cosa accade se ….

� Cade il TM e l’ ultimo record è global decision– Quanti RM siano stati avvertiti della decisione?– Bisogna ripetere la seconda riavvertendo tutti gli RM.


Cosa accade se ….

� Un partecipante cade prima del record ready– Non ci sono modifiche sostanziali rispetto al caso centralizzato. – La transazione va disfatta perché la transazione globale è

andata in global abort.


Cosa accade se ….

� Un partecipante cade dopo il record ready– L’ RM deve conoscere la decisione globale.– L’RM interroga il TM oppure il TM reinvia la decisione

ad intervalli regolari


Cosa accade se ….

� Si perde il prepare msg o qualche ready msg– Situazioni indistinguibili (dal punto di vista del TM)– Scatta il timeout sulla prima fase e si decide un global abort.


Cosa accade se ….

� Si perde il global decision msg o qualche ack– Situazioni indistinguibili (dal punto di vista del TM)– Scatta il timeout sulla seconda fase e questa viene ripetuta.


Osservazione

� La possibile ripetizione della seconda fase (scadenza del timeout normalmente o recoverydel TM o dell’RM) fa sì che che l’RM possa ricevere il messaggio di global decision piùvolte.– L’RM ignora i messaggi successivi ma deve sempre

mandare l’ack per consentire la chiusura del protocollo.


Ottimizzazione “read-only”

� Quando un RM ha svolto solo operazioni di lettura, – Risponde read-only al messaggio di prepare

message e esce dal protocollo.– Il TM ignora tutti gli RM “read-only” nella seconda

fase del protocollo.


Protocollo di abort presunto (cenni)

� E’ una ottimizzazione, usata da quasi tutti i sistemi commerciali:

– Se un TM riceve una richiesta di “remote recovery” da una transazione in dubbio che non gli è nota, risponde per default che la transazione ha fatto un “global abort”

� Come conseguenza, se vengono persi “prepare” e “global abort” si ottiene comunque un comportamento corretto

– => non è necessario scriverli in modo sincrono sul log.

� Inoltre, il record “complete” non può essere omesso.� In conclusione, gli unici record che devono essere scritti

in modo sincrono sono: – Ready(RM), global commit e commit locale (TM).


Protocollo di commit a quattro fasi

� Il processo TM viene replicato tramite un processo di backup collocato su un nodo differente. – Il TM informa il backup delle sue decisioni prima di

comunicarle agli RM.

� Se il TM ha un guasto, il backup può intervenire:– Come prima cosa attiva un altro backup.– Successivamente continua la esecuzione del

protocollo di commit.


Protocollo di commit a 4 fasi

P GC

Global Commit CompletePrepare

Ready Commit

partecipante (RM)

coordinatore (TM)

backup

2 fasi aggiunte


Protocollo di commit a tre fasi (cenni)

� Idea: grazie ad una terza fase, ogni partecipante può diventare un TM.

� Il partecipante “eletto” TM guarda il suo log:– Se l’ultimo record è “ready” può imporre un “global

abort”.– Se l’ultimo ready e’ “pre-commit” può imporre un

“global commit”.

� Difetto: il protocollo allunga la finestra di incertezza e può essere scorretto in presenza di partizioni di rete.


Protocollo di commit a 3 fasi (cenni)

Prepare CompletePre-commit Global Commit

LocalCommit

PreCommitReady


Standardizzazione del protocollo (cenni)

� Standard X-open DTP– interfaccia TM:

� definisce i servizi del coordinatore offerti ad un client per eseguire il commit di partecipanti eterogenei

– interfaccia XA: � definisce i servizi di partecipanti passivi che rispondono a

chiamate del coordinatore (offerta da molti DBMS sul mercato)


Caratteristiche X-Open DTP (cenni)

� Gli RM sono passivi: rispondono a remote procedure calls dei TM

� Protocollo: commit a due fasi con ottimizzazioni (abort presunto e read-only)

� Previste decisioni euristiche: dopo un guasto, gli operatori possono forzare abort o commit, se le decisioni forzate sono inconsistenti ciò viene riportato al client.


Interfaccia TM (cenni)

� tm_init e tm_exit iniziano e terminano un dialogo client -TM

� tm_open e tm_term aprono e chiudono unasessione col TM

� tm_begin inizia una transazione� tm_commit richiede un commit globale� tm_abort richiede un abort globale


Interfaccia XA (cenni)

� xa_open e xa_close:– iniziano e terminano un dialogo TM - RM

� xa_start e xa_end– attivano e completano una transazione

� xa_precomm– richiede all’RM di svolgere la prima fase del protocollo

� xa_commit e xa_abort– comunicano la “global decision” all’RM

� xa_recover– inizia una recovery dell’RM; ogni RM risponde alla richiesta con

tre insiemi di transazioni: in dubbio, decise con commit euristico, decise con abort euristico.

– Il TM termina le transazioni in dubbio e indica (xa_forget) all’RMdi dimenticare transazioni decise in modo euristico.


Sommario



Obiettivo: Efficienza

� Ottimizzazione delle query� Modalità di esecuzione

– seriale – parallela


Esecuzione serialeEsecuzione seriale

CONTO2CONTO2

CONTO3CONTO3

CENTROCENTRO

CONTO1CONTO1

FILIALE1FILIALE1

CLIENTCLIENT


Esecuzione parallelaEsecuzione parallela

CLIENTCLIENT

CONTO1CONTO1

FILIALE1FILIALE1

CONTO3CONTO3

FILIALE3FILIALE3

CONTO2CONTO2

FILIALE2FILIALE2


Scalabilità delle applicazioni

� Carico: � insieme di tutte le applicazioni (query)� Scalabilità:

– abilità di conservare prestazioni elevate al crescere del carico

� Dimensioni di crescita :– numero delle query– complessità delle query


Due tipologie di carico

� Transazionale – carico: transazioni brevi– misura: tps (transazioni per secondo)– tempo di risposta: pochi secondi

� Analisi dei dati– carico: query SQL complessa– tempo di risposta: variabile


Parallelismo

� Ottenuto tramite molti processori che cooperano in una unica architettura informatica

� Due tipi di parallelismo– inter-query

� ciascuna query affidata ad un solo processore – per carichi transazionali

– intra-query� ciascuna query affidata a molti processori

� per carichi di analisi dei dati


Architetture a confrontoArchitetture a confronto

SHAREDSHARED--NOTHINGNOTHING

rete velocerete veloce

DISCODISCOMEMORIAMEMORIA

PROCESSOREPROCESSORE

DISCODISCOMEMORIAMEMORIA

PROCESSOREPROCESSORE …………



SHAREDSHARED--MEMORYMEMORY

PROCESSOREPROCESSORE …………PROCESSOREPROCESSORE

MEMORIAMEMORIADISCODISCO DISCODISCO……..



SHAREDSHARED--DISKSDISKS

…………

DISCODISCO DISCODISCO……..

MEMORIAMEMORIA


MEMORIAMEMORIA



Benchmark

� Metodi per confrontare le prestazioni di sistemi diversi (in competizione)

� varie tipologie di carico– transazionale– analisi dei dati– Misto

� standardizzazione: – del database– del carico

� codice transazioni � modalità di invio� frequenza di arrivo

– della modalità di misurazione


Curva di speed-up

� Misura il crescere di efficienza al crescere del numero di processori

tpstps

numero di numero di processoriprocessori

curva curva realereale

....

..


Curva di scale-up

� Misura il crescere di costo unitario complessivo per transazione al crescere del numero di processori

costo costo unitariounitario

numero di numero di processoriprocessori

curva curva realereale.. .. ..


Join distribuito

� E' l'operazione di analisi dei dati più onerosa� consideriamo:

conto correnteconto corrente

JOINJOIN

transazionetransazione


Join distribuito

UNIONEUNIONE

CONTO1CONTO1

TRANS1TRANS1

JOINJOIN

CONTO2CONTO2

TRANS2TRANS2

JOINJOIN

CONTO3CONTO3

TRANS3TRANS3

JOINJOIN


Requisiti per il join distribuito

� I domini degli attributi di join devono essere partizionati e ogni partizione assegnata ad una coppia di frammenti– ad esempio su valori numerici tra

� 1 e 300000:

� da 1 a 100000� da 100000 a 200000

� da 200000 a 300000

� In molti sistemi paralleli i dati vengono inizialmente ridistribuiti sui dischi per ottenere questa distribuzione


Sommario



Replicazione dei dati

� E' un ingrediente fondamentale dei sistemi informativi per garantire:– efficienza– affidabilità– autonomia


Replicazione Asimmetrica

propagazionepropagazione

modifichemodifiche

CopiaPrimaria

CopiaSecondaria


Replicazione Simmetrica


modifichemodifiche

Copia1

Copia2

modifichemodifiche


Trasmissione sincrona delle variazioni

COPIA 1COPIA 1 COPIA 2COPIA 2

transazione transazione mastermaster


Trasmissione asincrona delle variazioni

COPIA 2COPIA 2


transazione di transazione di allineamentoallineamento

COPIA 1COPIA 1

transazione transazione mastermaster


Modalità di allineamento

� RefreshRefresh–– periodicoperiodico

–– a comandoa comando

–– ad accumulo di variazionead accumulo di variazione


INTERO INTERO CONTENUTO CONTENUTO DELLA COPIA 1DELLA COPIA 1


Modalità di allineamento

� Incrementale– Periodico– a comando– ad accumulo di variazione


DELTADELTA--PLUS PLUS DELTADELTA--MINUSMINUS


Trigger di replicazione

CREATE TRIGGER CAPTURE-INSAFTER INSERT ON PRIMARYFOR EACH ROWINSERT INTO DELTA-PLUS VALUES (NEW.*)

CREATE TRIGGER CAPTURE-DELAFTER DELETE ON PRIMARYFOR EACH ROWINSERT INTO DELTA-MINUS VALUES (OLD.*)

CREATE TRIGGER CAPTURE-UPDAFTER UPDATE ON PRIMARYFOR EACH ROWBEGININSERT INTO DELTA-PLUS VALUES (NEW.*)INSERT INTO DELTA-MINUS VALUES (OLD.*)END


Esempio: replicazione in computer mobili

� Computer mobili:– saltuariamente collegati ad una rete

� Copie disconnesse per ore o giorni – intere, poi riconnesse (riconciliazione)

� Applicazione:– agenti di vendita mobili


Allineamento di copie disconnesse

� Richiede spesso la replicazione simmetricaRichiede spesso la replicazione simmetrica

COPIA DEL COPIA DEL VENDITOREVENDITORE

COPIA COPIA CENTRALECENTRALE

modifichemodifiche modifichemodifiche

(con riconciliazione)(con riconciliazione)

09 architetture distribuite - CNR 1112/Slides/09... · 2015-06-19 · Architetture distribuite Basi...

Documents

Transcript of 09 architetture distribuite - CNR 1112/Slides/09... · 2015-06-19 · Architetture distribuite Basi...