Tecnologie di un database server:
la gestione della concorrenza
Paolo Atzeni
Roma – Rovereto
13/05/2011
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à
13/05/2011
Gestione della concorrenza
2
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
• Quanto c'è sul conto?
– 1000
• Bene, allora prelevo 200
– Ok, il nuovo saldo è 800
• Bene, allora prelevo 100
– Ok, il nuovo saldo è 900
13/05/2011
Gestione della concorrenza
4
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
13/05/2011
Gestione della concorrenza
5
Lettura, scrittura, lettura
1000 sul conto A
1000 sul conto B
•
Quanto c'è sul conto A?
– 1000
•
•
•
Sposta 500 da A a B
– Nuovo saldo A: 500
– Nuovo saldo B: 1500
Quanto c'è sul conto B?
– 1500
Ehi, abbiamo 2500!
13/05/2011
Gestione della concorrenza
6
Lettura prima della conferma (commit)
1000 sul conto
•
Ecco un assegno da 10.000
– Bene, il nuovo saldo è 11.000
•
Quanto c'è sul conto?
•
– 11.000
Abbiamo 11.000 !?!
•
Paperina ha letto un dato sbagliato!
– Ma l'assegno è falso!
– Annulliamo l'operazione
– Il saldo resta 1000
13/05/2011
Gestione della concorrenza
7
Gestione della concorrenza
• La concorrenza va governata:
– va permessa per favorire l'efficienza
– ma limitata, per evitare i problemi
13/05/2011
Gestione della concorrenza
8
Un concetto importante
• Transazione:
– Sequenza di operazioni da considerare indivisibile
("atomica"), corretta anche in presenza di concorrenza e con
effetti definitivi
07/10/2010
Atzeni-Ceri-Paraboschi-Torlone, Basi di dati, Capitolo 1
9
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)
13/05/2011
Gestione della concorrenza
10
Una transazione
• Quanto c'è sul conto?
– 1000
declare s money;
select saldo into s
from conti
where numero = 101;
• Bene, allora prelevo 200
update conti set saldo = s - 200
where numero = 101;
– Ok, il nuovo saldo è 800
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
update conti set saldo = saldo - 500
where codice = 'A'
update conti set saldo = saldo + 500
where codice = 'B'
commit
Gestione della concorrenza
12
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
update conti set saldo = saldo + 10.000
where codice = 'A'
rollback
Gestione della concorrenza
13
Caratteristiche delle transazioni
• Le proprietà ACIDe
– Atomicità
– Consistenza
– Isolamento
– Durabilità (persistenza)
07/10/2010
Atzeni-Ceri-Paraboschi-Torlone, Basi di dati, Capitolo 1
14
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
07/10/2010
Atzeni-Ceri-Paraboschi-Torlone, Basi di dati, Capitolo 1
15
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 ...
16
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 ...
17
Durabilità (Persistenza)
• Gli effetti di una transazione andata in commit non vanno
perduti ("durano per sempre"), anche in presenza di guasti
– "commit" significa "impegno"
31/03/2011
Basi di dati, vol.2 cap.2 Gestione delle transazioni ...
18
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
19
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
20
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
21
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
22
Anomalie e livelli di isolamento
(per le transazioni che leggono)
Perdita di aggiornamento
W-W
• read uncommitted
Lettura sporca
• read committed
R-W (o W-W) con abort
Letture inconsistenti
R-W
• repeatable read
Inserimento fantasma
• serializable
13/05/2011
R-W su dato "nuovo"
Gestione della concorrenza
23
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
24
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
25
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
13/05/2011
Gestione della concorrenza
26
Due prelevamenti da un conto corrente
• Quanto c'è sul conto?
– 1000
• Quanto c'è sul conto?
– 1000
• Bene, allora prelevo 200
– Ok, il nuovo saldo è 800
• Bene, allora prelevo 100
– Ok, il nuovo saldo è 900
13/05/2011
Gestione della concorrenza
27
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
28
Controllo di concorrenza
• Obiettivo: evitare le anomalie
• Schedule seriale:
– le transazioni sono separate, una alla volta
read1(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
29
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
30
Idea base
• Individuare classi di schedule serializzabili per i quali la
proprietà di serializzabilità sia verificabile a costo basso
Schedule
Serializzabili
13/05/2011
Schedule
Seriali
Gestione della concorrenza
Schedule
31
Gestore della concorrenza
Gestore dei
metodi d’accesso
Gestore delle
transazioni
read, write
begin, commit, abort
Gestore della concorrenza
Tabella
dei lock
read, write
(non tutte e in ordine ev. diverso)
Gestore della
memoria secondaria
BD
13/05/2011
Gestione della concorrenza
32
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
33
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;
13/05/2011
Gestione della concorrenza
34
I lock da soli non bastano
•
•
•
Posso leggere A?
– ok
Quanto c'è sul conto A?
– 1000
Ho finito con A (unlock)
•
•
•
•
•
•
•
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)
Posso leggere B?
– ok
Quanto c'è sul conto B?
– 1500
Ho finito con B (unlock)
Ehi, abbiamo 2500!
13/05/2011
Gestione della concorrenza
35
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)
13/05/2011
Gestione della concorrenza
36
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!
•
•
•
13/05/2011
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)
Gestione della concorrenza
37
Stallo (deadlock)
• I lock possono portare a situazioni indesiderate:
– attese incrociate: due transazioni detengono ciascuna una
risorsa e aspettano la risorsa detenuta dall'altra
13/05/2011
Gestione della concorrenza
38
Stallo
•
•
Posso leggere?
– ok
Quanto c'è sul conto?
– 1000
•
•
•
Posso leggere?
– ok
Quanto c'è sul conto?
– 1000
Posso scrivere?
– No, aspetta, qualcuno sta leggendo
•
Posso scrivere?
– No, aspetta, qualcuno sta leggendo
Aspetta e … spera!!!
13/05/2011
Gestione della concorrenza
39
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)
13/05/2011
Gestione della concorrenza
40
2PL, stallo e riavvio
•
•
Posso leggere?
– ok
Quanto c'è sul conto?
– 1000
•
•
•
•
Posso scrivere?
– No, aspetta, qualcuno sta leggendo
•
•
•
•
Posso scrivere?
– no, aspetta, qualcuno sta leggendo
Mi sono stancata di aspettare, smetto
•
•
Posso leggere?
– ok
Quanto c'è sul conto?
– 1000
– ora puoi scrivere
Bene, allora prelevo 100
– ok, il nuovo saldo è 900
Ricomincio. Posso leggere?
– ok
Quanto c'è sul conto?
– 900
Posso scrivere?
– ok, puoi scrivere
Bene, allora prelevo 200
– Ok, il nuovo saldo è 700
13/05/2011
Gestione della concorrenza
41
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
42
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
13/05/2011
Gestione della concorrenza
43
Lettura, scrittura, lettura
con multiversioni
1000 sul conto A
1000 sul conto B
•
Quanto c'è sul conto A?
– 1000
•
•
•
Sposta 500 da A a B
– Nuovo saldo A: 500
– Nuovo saldo B: 1500
Quanto c'è sul conto B?
– 1000 (il valore all'inizio della
transazione)
OK, abbiamo 2000!
13/05/2011
Gestione della concorrenza
44
Due prelevamenti
con multiversioni
•
•
•
Quanto c'è sul conto?
– 1000
•
Quanto c'è sul conto?
– 1000
•
Bene, allora prelevo 100
– Aspetta, qualcuno sta scrivendo
Bene, allora prelevo 200
– Ok, il nuovo saldo è 800
Ho finito (commit)
•
•
13/05/2011
– 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
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