Paolo Atzeni, Stefano Ceri, Stefano Paraboschi, Riccardo Torlone “Basi ... · Paolo Atzeni,...

Paolo Atzeni, Stefano Ceri, Stefano Paraboschi, Riccardo Torlone

“Basi Di Dati”, Seconda EdizioneMcGraw-Hill Italia, 1999

Capitolo 9

Tecnologia di un DBMS 1

Transazione

Insieme ordinato di operazioni di lettura e scrittura su un DB.Sintatticamente:• inizia con un BoT (Begin of Transaction)• termina con un EoT (End of Transaction)

All’interno del codice:• Commit work

• La transazione va a buon fine• Rollback work (abort)

• La transazione non ha alcun effetto

Nei sistemi attuali è perlopiù garantito un solo livello di controllo (transazioni flat).


Transazione

Transazione “Ben Formata”:• Inizia con BoT;• Termina con EoT;• Viene eseguito un solo Commit o un solo Abort;• Non avvengono letture e/o scritture dopo il Commit/Abort.

Proprietà garantita dai sistemi.

BoTUpdate CC set saldo = saldo – 25 where ccnum = 26488 Update CC set saldo = saldo + 25 where ccnum = 26000CommitEoT


ACIDi t à de l le Transazion i

Atomicity:• Una transazione è una unità indivisibile.

Consistency:• Una transazione deve lasciare il DB in uno stato

consistente con i vincoli.Isolation:• Una transazione deve agire in maniera indipendente dalle

altre.Durability:• Gli effetti di una transazione che ha effettuato il Commit

non devono mai essere persi.


At om ic i t à

Il modello di esecuzione è tutto-o-niente.Una transazione può non andare a buon fine:• per decisione autonoma;• per decisione del DBMS;• per errori e/o guasti.

L’atomicità ci assicura che, indipendentemente dal momento e dai motivi dell’abort, le eventuali azioni già effettuate vengono disfatte (operazione di undo). Durante l’esecuzione della transazione, le varie operazioni non sono visibili al mondo esterno.Dopo il commit, le operazioni effettuate sono tutte rese visibili al mondo esterno.


Consis t enza

Una transazione lascia il DB in uno stato consistente.Vincoli Immediati:• se è violato un vincolo immediato, il corrispondente

comando ritorna un codice di errore;• se tale errore è gestito dal codice della transazione, questa

può provare a continuare.Vincoli Ritardati:• il controllo sui vincoli deferred avviene quando è effettuato il

commit;• se qualche vincolo è violato, la transazione è uccisa in

extremis.


Iso lam ent o

Per migliorare i tempi medi di risposta (TpS), è necessario eseguire più transazioni in maniera concorrente.La proprietà di isolamento garantisce che:• il risultato di un insieme di transazioni eseguite in maniera

concorrente è in qualche modo equivalente (?) a quello che si otterrebbe se le transazioni fossero eseguite una dopo l’altra.

• venga evitato il Rollback a catena (l’abort di una transazione provoca l’abort di un’altra transazione e così via);• il Rollback a catena sarebbe particolarmente pericoloso qualora

coinvolgesse transazioni che hanno già effettuato il commit.


Durabi l i t y (Pers is t enza)

L’effetto di una transazione che ha effettuato il commit non deve mai essere perso.La persistenza fornisce meccanismi per rispondere ai malfunzionamenti hw/sw del sistema.


Modul i d i un DBMS

Gestore Concorrenza

Buffer Manager

Controllore Affidabilità

Gestore delle Strutture Fisiche di Accesso

Ottimizzatore

Isolamento

Atomicità

Persistenza

Consistenza


Teor ia Del la Conc orrenza

Il gestore della concorrenza è lo strato più interno di un DBMS.Si occupa di trasferire:

blocchi in memoria centrale (read);pagine verso la memoria di massa (write).

Scheduler:gestisce le operazioni di lettura/scrittura.


Equiva lenza d i Sc hedul ing

Si considerino 2 transazioni T1 e T2.Esistono 2 scheduling sequenziali:• T1 T2• T2 T1

Non è detto che essi forniscano lo stesso risultato.

T1BoTUpdate CC set saldo = 0CommitEoT

T2BoTUpdate CC set saldo = saldo + 30CommitEoT


Equiva lenza d i Sc hedul ing

Il risultato di un insieme di transazioni eseguite in maniera concorrente è in qualche modo equivalente (?) a quello che si otterrebbe se le transazioni fossero eseguite una dopo l’altra.La teoria della concorrenza cerca di definire il concetto di equivalenza di scheduling (sequenza di operazioni di I/O) in maniera più o meno indipendente dal risultato che esse producono.Essa, inoltre, fornisce tecniche per evitare le anomalie delle transazioni concorrenti. Transazione• BoT ri(x) ri (y) wi (x) ri (z) wi (y) wi (z) C EoT

Commit Proiezione.


Perdita di Update

T1 T2BoTr(x)x = x+1

BoTr(x)x = x+1w(x)commitEoT

w(x)commitEoT

Update FantasmaT1 T2BoTr(x)

BoTr(y)

r(y)y = y-500r(z)z = z+500w(y)w(z)commitEoT

r(z)somma=x+y+zcommitEoT

Anom al ie de l le Transazion i Conc orrent i


Letture SporcheT1 T2BoTr(x)x = x + 1w(x)


abortEoT

Letture Inconsistenti

T1 T2BoTr(x)


r(x)commitEoT

Anom al ie de l le Transazion i Conc orrent i


V iew Equiva lenza

Legge da: ri(x) legge-da wj(y)• x = y e i<>j;• nello scheduling ri segue wj;• non esiste wk(x) tra le operazioni

Scritture finali:• wk(x) è una scrittura finale se nello scheduling non esiste

alcuna scrittura su x successiva a k.

Due scheduling sono view-equivalenti se, oltre ad effettuare le stesse operazioni, hanno le stesse relazioni legge-da e le stesse scritture finali.


T1BoTUpdate CC set saldo = 0CommitEoT

T2BoTSelect saldo into LsaldoLsaldo = Lsaldo + 30Update CC set saldo = LsaldoCommitEoT

T1 w1(saldo)T2 r2(saldo) W2 (saldo)

S1 = w1(saldo) r2(saldo) w2 (saldo)S2 = r2(saldo) w2 (saldo) w1(saldo)S3 = r2(saldo) w1(saldo) w2 (saldo)


V iew Ser ia l izzabi l i t à

Uno scheduling si dice view serializzabile se è view-equivalente ad almeno uno scheduling seriale.Tale equivalenza è la più generale in assoluto:• due scheduling view-equivalenti producono lo stesso risultato.

Problemi:• verificare se due scheduling sono view-equivalenti è un problema

semplice;• verificare se è uno scheduling e view-serializzabile è un problema

NP-Completo;• le transazioni arrivano a istanti non specificati.


Conf l ic t Equiva lenza

Diminuiamo il numero di schedulingammissibili restringendo il concetto di equivalenza.Conflitto

l’azione ai(x) è in conflitto con l’azione aj(y) sse:• i <> j;• x = y;• almeno une delle due è una write;• (ri(x),wj(x)) (wi(x),wj(x)) (wi(x) rj(x))


Conf l ic t Equiva lenza

Due scheduling sono conflict-equivalenti sse, oltre a presentare le stesse operazioni, hanno gli stessi conflitti.• (ri(x),wj(x)) <> (wj(x) ri(x))

Uno scheduling è conflict- serializzabile se è conflict equivalente ad uno scheduling seriale.Esempio• S0 = r1(x) r2(y) w1(y) r3(y)r3(z)w2(x) w3(z)• (r1(x), w2(x)), (r2(y),w1(y)), (w1(y),r3(y))


T1

T3

T2

• Problemi:– Verificare se un grafo è aciclico è

un problema semplice.– Gestire il Grafo è complicato– Le transazioni arrivano a istanti

non specificati.– Nei casi reali non conosco cosa

vuole fare la transazione.


Una so luzione: i l prot oc o l lo 2PL

Lock:• bloccare una risorsa che vogliamo utilizzare;• lock condiviso (per operazioni di lettura);• lock esclusivo (per operazioni di scrittura);• r_lock, w_lock, unlock.

Lo scheduler diventa un lock manager che riceve richieste di lock e decide il da farsi.Transazione ben formata rispetto al locking:• ogni operazioni di lettura è preceduta da un r_lock e seguita da

un unlock;• ogni operazioni di scrittura è preceduta da un w_lock e seguita da

un unlock;• proprietà garantita di compilatori.


I lock garantiscono che sui dati si operi in maniera mutuamente esclusiva.Non garantiscono in alcun modo la serializzabilità.

errorOK / freeOK / dipendeUnlock

OK / w_lockedNO / w_lockedNO/ r_lockedW_lock

OK / r_lockedNO / W_lockedOK / r_lockedR_lock

FreeW_lockedR_lockedStatoRichiesta


Update Fantasma

T1 T2BoTRL(x) /r(x) /UL(x)

BoTRL(y) / r(y) /UL(y)

RL(y) / r(y) /UL(y)y = y-500RL(z) / r(z) / UL(z)z = z+500WL(y) / w(y) / UL(y)WL(z) / w(z) / UL(z)commitEoT

RL(z) / r(z) / UL(z)somma=x+y+zcommitEoT


Prot oc o l lo d i loc k ing a 2 fas i

Una transazione, dopo aver rilasciato un lock, non può acquisirne altri.In una transazione esiste allora una fase crescente (in cui i lock vengono acquisiti) ed una fase calante, in cui i lock vengono rilasciati.E’ concesso l’incremento di lock.

CSR

VSR

2PL


Letture SporcheT1 T2BoTr(x)w(x)


abortEoT

Perdita di Update

T1 T2BoTr(x)x = x+1


w(x)commitEoT


2PL st ret t o

Il problema è legato all’ipotesi di Commit Proiezione che è alla base della teoria della concorrenza.Nei sistemi reali tale ipotesi deve, per forza di cose, essere abbandonata.2PL stretto:

al 2PL si aggiunge l’ulteriore condizione che le risorse possono essere rilasciate solo dopo il commit/abort.


Deadloc k

Il meccanismo dei lock introduce un problema:• siano T1 e T2 due transazioni;• supponiamo che entrambe operino in scrittura su 2 oggetti

x e y;• T1 blocca x in scrittura;• T2 blocca y in scrittura;• T1 aspetta che T2 liberi y;• T2 aspetta che T1 liberi x.

La situazione può durare all’infinito.


Deadloc k : 3 so luzion i poss ib i l i

Prevention:Tecnica di prevenzione esatta:• le transazione acquisiscono le risorse di cui hanno bisogno

in un colpo solo;• se qualche risorsa non è disponibile, non viene assegnata

nessuna risorsa.

Problemi:• non sempre una transazione sa in partenza ciò di cui avrà

bisogno;• si rischia di bloccare troppi oggetti inutilmente.


PreventionTecnica approssimata:• tutte le transazioni richiedono i lock nello stesso ordine;• non sempre la transazione conosce tutto quello di cui avrà

bisogno; • non tutti i deadlock sono eliminati.

Tecnica approssimata:• ad ogni transazione è associato un timestamp;• se un lock non è concesso, la transazione aspetta solo se

essa è più giovane della transazione che detiene il lock;• non tutti i lock sono eliminati.


Detection:Non si pongono vincoli alle transazioni.Ad intervalli prefissati, o quando succede qualcosa, il contenuto della tabella dei lock è esaminato e comparato con le richieste pendenti.Si costruisce un grafico delle richieste.Se in tale grafico esiste un ciclo, c’è un deadlock.Il ciclo deve essere spezzato uccidendo almeno una transazione.


Time-out:E’ la tecnica più semplice e più usata.Ad richiesta di lock è associato un tempo massimo di attesa.Scaduto tale tempo, la richiesta si intende rifiutata e la transazione uccisa.


Cont ro l lo d i c onc orrenza c on T im est am ps

Ad ogni transazione viene assegnato un identificativo numerico crescente nel tempo

Transazioni successive hanno identificativi via via maggiori.

Ad ogni oggetto del DB viene associatoWTM(x), timestamp dell’ultima transazione che ha scritto l’oggetto.RTM(x) , timestamp dell’ultima transazione che ha letto l’oggetto.


Allo scheduler la transazione con TS ts inviarichieste del tipo read (x,ts) • Se ts < WTM(x), la richiesta non può essere soddisfatta e la

transazione richiedente viene uccisa.• Altrimenti la richiesta è accetta e RTM(x) è posto pari al

massimo tra ts e RTM(x) stesso.

write(x,ts)• Se ts < WTM(x) oppure ts < RTM(x) la transazione viene

uccisa.• Altrimenti la richiesta è accetta, WTM(x) è posto pari a ts.


Funziona solo nell’ipotesi di commit-proiezione.Nei casi reali le scritture vanno bufferizzate in RAM ed eseguite solo dopo il commit.Chi deve leggere deve aspettare il commit (il lock in qualche modo rientra).Vengono uccise molte transazioni.

CSR

VSR

2PL TS


L ive l lo d i iso lam ent o de l le Transazion i

Il livello di isolamento di una transazione determina il comportamento della stessa.Uncommitted Read• La transazione accetta di leggere dati modificati da una

transazione che non ha ancora fatto il commit (ignora i lockesclusivi e non acquisisce lock in lettura).

Committed Read• La transazione non legge dati cambiati da una transazione

che non ha ancora fatto il commit.Se però essa legge due volte lo stesso dato, può trovare dati diversi.


Repeatable ReadSi aggiunge al commited read la caratteristica che, se un dato è letto due volte, si avrà sempre lo stesso risultato.

SerializableSi aggiunge al Repeatable Read la caratteristica che, se una query è fatta due volte, non vengono aggiunte righe.


Unc om m it ed Read

Connection 1 Connection 2SET TRANSACTION ISOLATION LEVELREAD UNCOMMITTED

BEGIN TRAN UPDATE authorsSET au_lname='Smith'

SELECT au_lnameFROM authorsWHERE au_lname='Smith'

ROLLBACK TRAN SELECT au_lnameFROM authorsWHERE au_lname='Smith'


Com m it ed Read

Connection 1 Connection 2SET TRANSACTION ISOLATION LEVELREAD COMMITTED BEGIN TRAN SELECT au_lnameFROM authorsWHERE au_lname='Smith'

UPDATE authorsSET au_lname='Smith'

SELECT au_lnameFROM authorsWHERE au_lname='Smith' COMMIT TRAN


Repeat able ReadConnection 1 Connection 2

SET TRANSACTION ISOLATION LEVELREPEATABLE READ BEGIN TRAN SELECT au_lnameFROM authorsWHERE au_lname='Smith'

UPDATE authorsSET au_lname='Jones' (la query si blocca)

SELECT au_lnameFROM authorsWHERE au_lname='Smith' COMMIT TRAN

SELECT au_lnameFROM authors


Ser ia l izab le (1/2)Connection 1 Connection 2

SET TRANSACTION ISOLATION LEVEL REPEATABLE READ BEGIN TRAN SELECT title FROM titlesWHERE title_id LIKE 'BU%'

INSERT titlesVALUES ('BU2000','Inside SQL Server 2000','popular_comp', '0877', 59.95,5000, 10, 0, null, 'Sep 10, 2000')

SELECT title FROM titlesWHERE title_id LIKE 'BU%' --Risultato diverso!COMMIT TRAN


Ser ia l izab le (2/2)Connection 1 Connection 2

SET TRANSACTION ISOLATION LEVELSERIALIZABLEBEGIN TRAN SELECT title FROM titlesWHERE title_id LIKE 'BU%'

INSERT titlesVALUES ('BU3000','Itzik and His Black Belt SQL Tricks','popular_comp', '0877',39.95, 10000, 12, 15000, null,'Sep 15 2000') (la query si blocca)

SELECT title FROM titlesWHERE title_id LIKE 'BU%' --Risultato uguale!

COMMIT TRAN


Repet eable Read / Ser ia l izab le

Un modo alternativo per comprendere la differenza tra questi livelli di isolamento è guardare alle modifiche possibili una volta che siano stati modificati dati in un’altra transazione.Nel REPEATABLE READ:• Le righe realmente lette non possono essere modificate o cancellate.• Possono però essere aggiunte righe anche nell’intervallo specificato nella

clausola Where della transazione che legge.• Tutti i dati letti sono read_locked;• Un insert non interferisce con questi lock.

Nel SERIALIZABLE:• Una volta che una transazione ha letto dati non sono possibili modifiche su di

essi.• Non sono possibili modifiche neanche all’interno dell’intervallo coperto nella

lettura.• SERIALIZABLE locka intervalli di dati, inclusi quelli di fatto non esistono,

impedendo cioè che vengano effettuati insert.


Durabi l i t y (Pers is t enza)

La Durability consente di reagire a:Guasti di Sistema

Il server ha subito un guasto/malfunzionamento che non ha danneggiato il dispositivo su cui è memorizzato il DB.

Guasti di DispositivoIl dispositivo su cui è memorizzato il DB si è danneggiato.


Log Fi le

La persistenza è assicurata tramite il file di Log.Il Log file è un file sequenziale memorizzato su memoria stabile.In esso esistono due tipi di di record:

Record di Transazione.Record di Sistema.


Rec ord d i Transazione

Registrano le attività di ogni transazione, nell’ordine in cui dette attività sono eseguite.Ad ogni transazione è allora assegnato un identificativo.Record di Begin, Commit, Abort:• Contengono l’identificativo della transazione ed il tipo di

operazione.Record di Update:• Contengono l’identificativo della transazione, l’identificativo

dell’oggetto su cui si effettua l’update, lo stato prima dell’update(BS) e lo stato dopo l’update (AS).

Record di Insert.Record di Delete.


Rec ord d i Sis t em a

Record di dump:• Segnale che è stato effettuato un dump (copia di sicurezza

su memoria stabile) del DB.

Record di checkpoint:• Il checkpoint è una operazione che viene effettuata con una

certa frequenza da un DBMS.• In tale istante vengono riportato su disco le pagine

assegnate a transazioni che hanno effettuato il commit.• Alla fine viene scritto il record di checkpoint in cui si

riportano le transazioni attive a quell’istante.


Ripresa a Caldo

Viene effettuato in risposta ad un guasto di sistema.Si accede all’ultimo blocco del log e si ripercorre il file all’indietro fino all’ultimo record di chekpoint.Si costruiscono due insiemi: Undo e Redo. L’insieme di Redo è inizialmente vuoto mentre l’insieme di Undo contiene le transazioni presenti nel record di chekpoint.


Si ripercorre il log in avanti:• Se si incontra un Commit, la transazione corrispondente

viene spostata da Undo in Redo.• Se si incontra un Begin, la transazione corrispondente

viene inserita nell’insieme di Undo.Si torna all’indietro fino al Begin della transazione più vecchia fra tutte quelle presenti nei 2 insiemi.Si ripercorre il Log all’indietro disfacendo le operazione delle transazioni in UNDOSi ripercorre il Log in avanti rifacendo le operazioni delle transazioni in Redo


Ripresa a Freddo

Viene effettuato in risposta ad un guasto di dispositivo.Si ripristina il DB con l’ultima copia.Si percorre il log in avanti, dall’ultimo dump, rifacendo tutte le operazioni riportate.Si effettua una ripresa a caldo.


E’ essenziale l’idempotenza delle operazioni di ripristino

FunzionamentoNormale

Stop

Ripristino

Guasto

BootBoot OK

Boot KO


Regola WAL e Com m it Prec edenza

Il corretto funzionamento del meccanismo presuppone che:• La parte BS sia scritta nel Log prima di effettuare modifiche

(WAL-Write Ahead Log).• La parte AS sia scritta prima del Commit (Commit

Precedenza)

In genere il record è scritto in un colpo solo prima di effettuare modifiche sulla Base Dati (WAL semplificata) e prima del Commit (Commit Precedenza semplificata).

This document was created with Win2PDF available at http://www.daneprairie.com.The unregistered version of Win2PDF is for evaluation or non-commercial use only.

http://www.daneprairie.com

Paolo Atzeni, Stefano Ceri, Stefano Paraboschi, Riccardo Torlone “Basi ... · Paolo Atzeni,...

Documents

Transcript of Paolo Atzeni, Stefano Ceri, Stefano Paraboschi, Riccardo Torlone “Basi ... · Paolo Atzeni,...