Tecnologie di un database server: la gestione della concorrenza Paolo Atzeni Roma – Rovereto...
-
Upload
nicoletta-rosa -
Category
Documents
-
view
215 -
download
2
Transcript of Tecnologie di un database server: la gestione della concorrenza Paolo Atzeni Roma – Rovereto...
Tecnologie di un database server: la gestione della concorrenza
Paolo Atzeni
Roma – Rovereto
13/05/2011
13/05/2011 Gestione della concorrenza 2
Base di dati
• Collezione di dati potenzialmene– grande– persistente – di interesse per molti utenti e applicazioni
• Esempi:– Conti correnti bancari– Prenotazioni aeree o ferroviarie
• La base di dati è spesso una risorsa importante, da gestire con – efficienza– affidabilità
Molte richieste contemporanee o quasi
• Conti correnti bancari, prenotazioni aeree o ferroviarie:• anche centinaia o migliaia di aggiornamenti attivi in un ogni
momento
13/05/2011 Gestione della concorrenza 3
Due prelevamenti da un conto corrente
• Quanto c'è sul conto?– 1000
• Bene, allora prelevo 200– Ok, il nuovo saldo è 800
• Quanto c'è sul conto?– 1000
• Bene, allora prelevo 100– Ok, il nuovo saldo è 900
13/05/2011 Gestione della concorrenza 4
13/05/2011 Gestione della concorrenza 5
Qual è il problema?
• Le operazioni ("transazioni", vediamo fra poco) sono concorrenti:– le azioni si alternano (Paperina, Paperino, Paperina, …) in
modo inaccettabile• Se eseguissimo prima tutte le azioni di Paperina e poi tutte
quelle di Paperino– non ci sarebbe problema
• Potremmo allora separare tutte le operazioni?– no, perché le richieste possono essere tante e
introdurremmo tempi di attesa eccessivi
Lettura, scrittura, lettura
• Quanto c'è sul conto A?
– 1000
• Quanto c'è sul conto B?
– 1500
• Ehi, abbiamo 2500!
• Sposta 500 da A a B
– Nuovo saldo A: 500
– Nuovo saldo B: 1500
13/05/2011 Gestione della concorrenza 6
1000 sul conto A1000 sul conto B
Lettura prima della conferma (commit)
• Quanto c'è sul conto?
– 11.000
• Abbiamo 11.000 !?!
• Paperina ha letto un dato sbagliato!
• Ecco un assegno da 10.000
– Bene, il nuovo saldo è 11.000
– Ma l'assegno è falso!
– Annulliamo l'operazione
– Il saldo resta 1000
13/05/2011 Gestione della concorrenza 7
1000 sul conto
13/05/2011 Gestione della concorrenza 8
Gestione della concorrenza
• La concorrenza va governata:– va permessa per favorire l'efficienza– ma limitata, per evitare i problemi
07/10/2010 Atzeni-Ceri-Paraboschi-Torlone, Basi di dati, Capitolo 1 9
Un concetto importante
• Transazione: – Sequenza di operazioni da considerare indivisibile
("atomica"), corretta anche in presenza di concorrenza e con effetti definitivi
13/05/2011 Gestione della concorrenza 10
Transazioni, in pratica
• Sequenza di operazioni caratterizzata da – un inizio (non sempre esplicitato) e – da una conclusione:
• commit per terminare ed eseguire tutto• rollback per annullare (abortire)
Una transazione
• Quanto c'è sul conto?– 1000
• Bene, allora prelevo 200– Ok, il nuovo saldo è 800
declare s money;
select saldo into sfrom conti where numero = 101;
update conti set saldo = s - 200 where numero = 101;
commit;
13/05/2011 Gestione della concorrenza 11
Un'altra transazione
• Sposta 500 da A a B
– Nuovo saldo A: 500
– Nuovo saldo B: 1500
13/05/2011 Gestione della concorrenza 12
update conti set saldo = saldo - 500 where codice = 'A'
update conti set saldo = saldo + 500 where codice = 'B'
commit
Un'altra ancora
• Ecco un assegno da 10.000
– Bene, il nuovo saldo è 11.000
– Ma l'assegno è falso!
– Annulliamo l'operazione
– Il saldo resta 1000
–
13/05/2011 Gestione della concorrenza 13
update conti set saldo = saldo + 10.000 where codice = 'A'
rollback
07/10/2010 Atzeni-Ceri-Paraboschi-Torlone, Basi di dati, Capitolo 1 14
Caratteristiche delle transazioni
• Le proprietà ACIDe – Atomicità– Consistenza– Isolamento– Durabilità (persistenza)
07/10/2010 Atzeni-Ceri-Paraboschi-Torlone, Basi di dati, Capitolo 1 15
Atomicità
• Una sequenza di operazioni correlate:– trasferimento di fondi da un conto A ad un conto B
• … deve essere eseguita per intero o per niente:– o si fanno il prelevamento da A e il versamento su B – o nessuno dei due
31/03/2011 Basi di dati, vol.2 cap.2 Gestione delle transazioni ... 16
Consistenza
• La transazione rispetta i vincoli di integrità• Conseguenza:
– se lo stato iniziale è corretto– anche lo stato finale è corretto
• Se lo stato finale non è corretto, la transazione deve fallire
31/03/2011 Basi di dati, vol.2 cap.2 Gestione delle transazioni ... 17
Isolamento
• La transazione non risente degli effetti delle altre transazioni concorrenti– l'esecuzione concorrente di una collezione di transazioni
deve produrre un risultato che si potrebbe ottenere con una esecuzione sequenziale
– esempio: • due prelevamenti quasi contestuali
31/03/2011 Basi di dati, vol.2 cap.2 Gestione delle transazioni ... 18
Durabilità (Persistenza)
• Gli effetti di una transazione andata in commit non vanno perduti ("durano per sempre"), anche in presenza di guasti – "commit" significa "impegno"
13/05/2011 Gestione della concorrenza 19
Transazioni e moduli di DBMS
• Atomicità e durabilità – Gestore dell'affidabilità (Reliability manager)
• Isolamento:– Gestore della concorrenza
• Consistenza:– Gestore dell'integrità a tempo di esecuzione (con il supporto
del compilatore del DDL)
13/05/2011 Gestione della concorrenza 20
Controllo di concorrenza, anomalie
• I tre esempi corrispondono a situazioni tipiche– Due prelevamenti sullo stesso conto:
• Perdita di aggiornamento (lost update)• Interferenza fra due scritture
– Lettura prima del commit• Lettura sporca (dirty read)• Interferenza fra scrittura non confermata e lettura
– Scrittura fra le due letture• Letture inconsistenti (inconsistent read)• Interferenza fra lettura e scrittura
13/05/2011 Gestione della concorrenza 21
Anomalie
• Perdita di aggiornamento W-W• Lettura sporca R-W (o W-W) con abort • Letture inconsistenti R-W
Un'altra, che non abbiamo visto• Inserimento fantasma R-W su dato "nuovo"
13/05/2011 Gestione della concorrenza 22
Livelli di isolamento in SQL:1999 (e JDBC)
• Il livello di isolamento può essere scelto per ogni transazione– read uncommitted permette letture sporche, letture
inconsistenti, aggiornamenti fantasma e inserimenti fantasma
– read committed evita letture sporche ma permette letture inconsistenti, aggiornamenti fantasma e inserimenti fantasma
– repeatable read evita tutte le anomalie esclusi gli inserimenti fantasma
– serializable evita tutte le anomalie• Nota:
– la perdita di aggiornamento dovrebbe essere sempre evitata, ma non è così: conviene usare sempre serializable per le transazioni che scrivono
13/05/2011 Gestione della concorrenza 23
Anomalie e livelli di isolamento(per le transazioni che leggono)
Perdita di aggiornamento W-W• read uncommitted
Lettura sporca R-W (o W-W) con abort • read committed
Letture inconsistenti R-W• repeatable read
Inserimento fantasma R-W su dato "nuovo"• serializable
13/05/2011 Gestione della concorrenza 24
Livelli di isolamento, perché?
• La gestione del controllo della concorrenza è costosa, se non serve, possiamo rinunciarci
• Nota bene: per le letture, non per le scritture
13/05/2011 Gestione della concorrenza 25
Livelli di isolamento, esempi
• Una base di dati complessa, in un momento in cui non ci sono aggiornamenti ("tempo morto"):– non c'è bisogno di controllo di concorrenza:
• read uncommitted • Una banca, molti conti correnti, molte piccole modifiche in
corso, ci interessa un dato indicativo sulla media dei saldi dei conti correnti:– le inconsistenze sono tollerabili (perché presumibilmente
piccole):• read committed
• Idem, ma ci interessa sapere qual è il conto con il saldo più alto:– ci serve un valore preciso, non possiamo tollerare
inconsistenze, nemmeno piccole• serializable
13/05/2011 Gestione della concorrenza 26
Controllo di concorrenza
• Esistono libri interi dedicati alla teoria e alla tecnologia, quindi in dieci minuti possiamo vedere solo l'idea di base, accennando alle tecniche
Due prelevamenti da un conto corrente
• Quanto c'è sul conto?– 1000
• Bene, allora prelevo 200– Ok, il nuovo saldo è 800
• Quanto c'è sul conto?– 1000
• Bene, allora prelevo 100– Ok, il nuovo saldo è 900
13/05/2011 Gestione della concorrenza 27
13/05/2011 Gestione della concorrenza 28
Schedule
• Sequenza di operazioni di input/output di transazioni concorrenti (tralasciando le altre operazioni)
• Esempi: – Paperina e Paperino leggono e scrivono lo stesso dato x, il
saldo del conto (con perdita di aggiornamento)
read1(x) read2(x) write1(x) write2(x)
– Paperino scrive fra due letture di Paperina (letture inconsistenti)
read1(x) write2(x) write2(y) read1(y)
13/05/2011 Gestione della concorrenza 29
Controllo di concorrenza
• Obiettivo: evitare le anomalie• Schedule seriale:
– le transazioni sono separate, una alla voltaread1(x) write1(x) read2(x) write2(x)
– uno schedule seriale non presenta anomalie• Schedule serializzabile:
– produce lo “stesso risultato” di uno schedule seriale sulle stesse transazioni e quindi è accettabile
• Controllore di concorrenza (Scheduler): – un sistema che accetta o rifiuta (o riordina) le operazioni
richieste dalle transazioni (mantenendo l'ordine delle azioni in ciascuna transazione)
– deve ammettere solo schedule serializzabili
13/05/2011 Gestione della concorrenza 30
Schedule non serializzabili
• Paperina e Paperino leggono e scrivono lo stesso dato x, il saldo del conto (con perdita di aggiornamento)
read1(x) read2(x) write1(x) write2(x)
– Le due letture vedono lo stesso dato, mentre in caso di schedule seriale la seconda dovrebbe vedere il dato modificato dalla prima e questo ha conseguenze sulla seconda scriuttura
• Paperino scrive fra due letture di Paperina (letture inconsistenti)
read1(x) write2(x) write2(y) read1(y)
– Le due letture vedono, complessivamente, uno stato della base di dati che non esiste e non è mai esistito
13/05/2011 Gestione della concorrenza 31
Idea base
• Individuare classi di schedule serializzabili per i quali la proprietà di serializzabilità sia verificabile a costo basso
ScheduleSeriali
ScheduleScheduleSerializzabili
13/05/2011 Gestione della concorrenza 32
Gestore della concorrenza
BD
Gestore della memoria secondaria
Gestore deimetodi d’accesso
Gestore delle transazioni
Gestore della concorrenza
read, write begin, commit, abort
read, write(non tutte e in ordine ev. diverso)
Tabella dei lock
13/05/2011 Gestione della concorrenza 33
Controllo della concorrenza in pratica
• Saltiamo la teoria …
• Le tecniche utilizzate– 2PL (two-phase locking)– multiversion (evoluzione delle tecniche su timestamp)
13/05/2011 Gestione della concorrenza 34
Lock
• Principio – su ciascun dato:
• si scrive uno per volta • non si può leggere se qualcuno sta scrivendo
• Analogo a quanto accade in altri contesti (ad esempio, file system) ma con una granularità più fine (o comunque flessibile)
• Come si realizza:– Si chiede il permesso
• lo si ottiene se la risorsa (il dato) non è utilizzata, in modo conflittuale, da altri;
• altrimenti si viene messi in attesa;– dopo l'uso, si rilascia la risorsa;
I lock da soli non bastano
• Posso leggere A?
– ok
• Quanto c'è sul conto A?
– 1000
• Ho finito con A (unlock)
• Posso leggere B?
– ok
• Quanto c'è sul conto B?
– 1500
• Ho finito con B (unlock)
• Ehi, abbiamo 2500!
•Posso scrivere A? Posso scrivere B?
– ok, ok
•Sposta 500 da A a B
– Nuovi saldi A: 500, B: 1500
•Ho finito con A e con B (unlock)
13/05/2011 Gestione della concorrenza 35
13/05/2011 Gestione della concorrenza 36
Locking a due fasi (2PL)
• Protezione con lock di tutte le letture e scritture, con– vincolo sulle richieste e i rilasci dei lock:
• una transazione, dopo aver rilasciato un lock, non può acquisirne altri
– meglio ancora, per evitare le letture sporche:• ogni transazione mantiene i propri lock fino alla fine
(cioè fino al commit o al rollback)
Il 2PL risolve
• Posso leggere A?
– ok
• Quanto c'è sul conto A?
– 1000
• Posso leggere B?
– ok
• Quanto c'è sul conto B?
– 1000
• Ho finito con A e con B (unlock)
• OK, abbiamo 2000!
•Posso scrivere A?
– No, aspetta!
– Ora puoi scrivere A
•Posso scrivere B?
– ok
•Sposta 500 da A a B
– Nuovi saldi A: 500, B: 1500
•Ho finito con A e con B (unlock)
13/05/2011 Gestione della concorrenza 37
13/05/2011 Gestione della concorrenza 38
Stallo (deadlock)
• I lock possono portare a situazioni indesiderate:– attese incrociate: due transazioni detengono ciascuna una
risorsa e aspettano la risorsa detenuta dall'altra
Stallo
• Posso leggere?
– ok
• Quanto c'è sul conto?
– 1000
• Posso scrivere?
– No, aspetta, qualcuno sta leggendo
• Posso leggere?
– ok
• Quanto c'è sul conto?
– 1000
• Posso scrivere?
– No, aspetta, qualcuno sta leggendo
13/05/2011 Gestione della concorrenza 39
Aspetta e … spera!!!
13/05/2011 Gestione della concorrenza 40
Risoluzione dello stallo
• La tecnica più semplice:– timeout:
• si fissa un tempo limite per l'attesa da parte di una transazione, dopo di che essa viene annullata (ed eventualmente riparte)
2PL, stallo e riavvio• Posso leggere?
– ok• Quanto c'è sul conto?
– 1000
• Posso scrivere?– No, aspetta, qualcuno sta leggendo
• Mi sono stancata di aspettare, smetto
• Ricomincio. Posso leggere?– ok
• Quanto c'è sul conto?– 900
• Posso scrivere?– ok, puoi scrivere
• Bene, allora prelevo 200– Ok, il nuovo saldo è 700
•Posso leggere?– ok
•Quanto c'è sul conto?– 1000
•Posso scrivere?– no, aspetta, qualcuno sta leggendo
– ora puoi scrivere•Bene, allora prelevo 100
– ok, il nuovo saldo è 900
13/05/2011 Gestione della concorrenza 41
13/05/2011 Gestione della concorrenza 42
Livelli di isolamento: implementazione
• Sulle scritture si ha sempre il 2PL stretto (e nonostante ciò che dicono i manuali non sempre si evita la perdita di aggiornamento; le transazioni in scrittura debbono avere il livello massimo di isolamento)
• read uncommitted:– nessun lock in lettura (e non rispetta i lock altrui)
• read committed:– lock in lettura (e rispetta quelli altrui), ma senza 2PL
• repeatable read:– 2PL stretto anche in lettura, con lock sui dati
• serializable:– 2PL stretto con lock di predicato
13/05/2011 Gestione della concorrenza 43
Controllo di concorrenza basato su multiversioni
• Per le letture:– si legge il valore valido all'inizio della transazione
• Per le scritture:– si usano lock per la sola scrittura e– una transazione T viene annullata se deve scrivere un dato
che è stato modificato da altre transazioni dopo l'inizio di T
Lettura, scrittura, lettura con multiversioni
• Quanto c'è sul conto A?
– 1000
• Quanto c'è sul conto B?
– 1000 (il valore all'inizio della transazione)
• OK, abbiamo 2000!
• Sposta 500 da A a B
– Nuovo saldo A: 500
– Nuovo saldo B: 1500
13/05/2011 Gestione della concorrenza 44
1000 sul conto A1000 sul conto B
Due prelevamenticon multiversioni
• Quanto c'è sul conto?– 1000
• Bene, allora prelevo 200– Ok, il nuovo saldo è 800
• Ho finito (commit)
•Quanto c'è sul conto?– 1000
•Bene, allora prelevo 100– Aspetta, qualcuno sta scrivendo
– Ho provato a scrivere, ma qualcun altro ha modificato il valore nel frattempo, debbo annullare (rollback)
•Ricomincio. Quanto c'è sul conto?– 800
•Bene, allora prelevo 100• Ok, il nuovo saldo è 700
13/05/2011 Gestione della concorrenza 45
Conclusioni
• Il controllo di concorrenza è fondamentale per garantire che le operazioni concorrenti– leggano dati coerenti– non compromettano il contenuto della base di dati
• Il tutto deve essere fatto senza penalizzare troppo l'efficienza• I sistemi offrono buone funzionalità per la gestione della
concorrenza basate su due tecniche– Locking a due fasi (2PL)– Multiversioni
• Permettono anche di "rinunciare" ad un controllo stringente, ma l'utente deve essere consapevole di ciò che ottiene
13/05/2011 Gestione della concorrenza 46
Per approfondire il tutto ci vorrebbe molto più tempo
Molti dettagli in rete o su libri.
Ad esempio il sito del corso di Basi di dati II
e quello dei libri di basi di dati,
link sulla mia pagina:
http://www.dia.uniroma3.it/~atzeni/
13/05/2011 Gestione della concorrenza 47
Grazie!
13/05/2011 Gestione della concorrenza 48