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


Due prelevamenti da un conto corrente

• Quanto c'è sul conto?– 1000

• Bene, allora prelevo 200– Ok, il nuovo saldo è 800





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


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


1000 sul conto


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


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



declare s money;

select saldo into sfrom conti where numero = 101;

update conti set saldo = s - 200 where numero = 101;

commit;


Un'altra transazione





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

–


update conti set saldo = saldo + 10.000 where codice = 'A'

rollback


Caratteristiche delle transazioni

• Le proprietà ACIDe – Atomicità– Consistenza– Isolamento– Durabilità (persistenza)


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


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


Durabilità (Persistenza)

• Gli effetti di una transazione andata in commit non vanno perduti ("durano per sempre"), anche in presenza di guasti – "commit" significa "impegno"


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)


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


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"


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


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


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


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


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







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)


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


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


Idea base

• Individuare classi di schedule serializzabili per i quali la proprietà di serializzabilità sia verificabile a costo basso

ScheduleSeriali

ScheduleScheduleSerializzabili


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


Controllo della concorrenza in pratica

• Saltiamo la teoria …

• Le tecniche utilizzate– 2PL (two-phase locking)– multiversion (evoluzione delle tecniche su timestamp)


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


– 1000

• Ho finito con A (unlock)

• Posso leggere B?

– ok


– 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)



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


– 1000

• Posso leggere B?

– ok


– 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)



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


– 1000

• Posso scrivere?

– No, aspetta, qualcuno sta leggendo

• Posso leggere?

– ok


– 1000

• Posso scrivere?

– No, aspetta, qualcuno sta leggendo


Aspetta e … spera!!!


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


• Posso scrivere?– ok, puoi scrivere


•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



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


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


– 1000


– 1000 (il valore all'inizio della transazione)

• OK, abbiamo 2000!





1000 sul conto A1000 sul conto B

Due prelevamenticon multiversioni



• 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


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


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/


http://www.dia.uniroma3.it/~atzeni/

Grazie!


Tecnologie di un database server: la gestione della concorrenza Paolo Atzeni Roma – Rovereto...

Documents

Transcript of Tecnologie di un database server: la gestione della concorrenza Paolo Atzeni Roma – Rovereto...