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).
Tecnologia di un DBMS 2
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
Tecnologia di un DBMS 3
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.
Tecnologia di un DBMS 4
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.
Tecnologia di un DBMS 5
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.
Tecnologia di un DBMS 6
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.
Tecnologia di un DBMS 7
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.
Tecnologia di un DBMS 8
Modul i d i un DBMS
Gestore Concorrenza
Buffer Manager
Controllore Affidabilità
Gestore delle Strutture Fisiche di Accesso
Ottimizzatore
Isolamento
Atomicità
Persistenza
Consistenza
Tecnologia di un DBMS 9
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.
Tecnologia di un DBMS 10
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
Tecnologia di un DBMS 11
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.
Tecnologia di un DBMS 12
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
Tecnologia di un DBMS 13
Letture SporcheT1 T2BoTr(x)x = x + 1w(x)
BoTr(x)x = x+1w(x)commitEoT
abortEoT
Letture Inconsistenti
T1 T2BoTr(x)
BoTr(x)x = x+1w(x)commitEoT
r(x)commitEoT
Anom al ie de l le Transazion i Conc orrent i
Tecnologia di un DBMS 14
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.
Tecnologia di un DBMS 15
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)
Tecnologia di un DBMS 16
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.
Tecnologia di un DBMS 17
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))
Tecnologia di un DBMS 18
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))
Tecnologia di un DBMS 19
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.
Tecnologia di un DBMS 20
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.
Tecnologia di un DBMS 21
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
Tecnologia di un DBMS 22
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
Tecnologia di un DBMS 23
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
Tecnologia di un DBMS 24
Letture SporcheT1 T2BoTr(x)w(x)
BoTr(x)x = x+1w(x)commitEoT
abortEoT
Perdita di Update
T1 T2BoTr(x)x = x+1
BoTr(x)x = x+1w(x)commitEoT
w(x)commitEoT
Tecnologia di un DBMS 25
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.
Tecnologia di un DBMS 26
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.
Tecnologia di un DBMS 27
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.
Tecnologia di un DBMS 28
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.
Tecnologia di un DBMS 29
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.
Tecnologia di un DBMS 30
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.
Tecnologia di un DBMS 31
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.
Tecnologia di un DBMS 32
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.
Tecnologia di un DBMS 33
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
Tecnologia di un DBMS 34
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.
Tecnologia di un DBMS 35
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.
Tecnologia di un DBMS 36
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'
Tecnologia di un DBMS 37
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
Tecnologia di un DBMS 38
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
Tecnologia di un DBMS 39
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
Tecnologia di un DBMS 40
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
Tecnologia di un DBMS 41
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.
Tecnologia di un DBMS 42
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.
Tecnologia di un DBMS 43
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.
Tecnologia di un DBMS 44
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.
Tecnologia di un DBMS 45
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.
Tecnologia di un DBMS 46
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.
Tecnologia di un DBMS 47
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
Tecnologia di un DBMS 48
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.
Tecnologia di un DBMS 49
E’ essenziale l’idempotenza delle operazioni di ripristino
FunzionamentoNormale
Stop
Ripristino
Guasto
BootBoot OK
Boot KO
Tecnologia di un DBMS 50
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.
Top Related