Basi di dati vol.2 Capitolo 2 Gestione delle...

1

Basi di dati vol.2Capitolo 2

Gestione delle transazioni

26/05/2005

26/05/2005 Basi di dati, vol.2 cap.2 Gestione delle transazioni 2

Esempio di sistema informativoEsempio di sistema informativo

GESTIONEGESTIONEIMPIANTIIMPIANTI

ELENCHIELENCHIABBONATIABBONATI

IMMISSIONE DI IMMISSIONE DI ORDINI DI ORDINI DI SERVIZIOSERVIZIO

GESTIONEGESTIONERETERETE

AMMINISTRAZIONEAMMINISTRAZIONE

GESTIONE GESTIONE ELENCHI ELENCHI ABBONATIABBONATI

CLIENTICLIENTI

BOLLETTEBOLLETTECOMMUTAZIONECOMMUTAZIONE

RISORSE E RISORSE E MANUTENZIONEMANUTENZIONE

2


Esempio di transazioneEsempio di transazione

ELENCHIELENCHIABBONATIABBONATI

GESTIONEGESTIONEIMPIANTIIMPIANTI

IMMISSIONE DI IMMISSIONE DI ORDINI DI ORDINI DI SERVIZIOSERVIZIO

GESTIONEGESTIONERETERETE

AMMINISTRAZIONEAMMINISTRAZIONE

GESTIONE GESTIONE ELENCHI ELENCHI ABBONATIABBONATI

CLIENTICLIENTI

BOLLETTEBOLLETTECOMMUTAZIONECOMMUTAZIONE

RISORSE E RISORSE E MANUTENZIONEMANUTENZIONE

11

33

22

66

55

88

77

1111

1010

99

44


DEFINIZIONE DI TRANSAZIONE

• Transazione: parte di programma caratterizzata da un inizio (begin-transaction, start transaction in SQL), una fine (end-transaction, non esplicitata in SQL) e al cui interno deve essere eseguito una e una sola volta uno dei seguenti comandi– commit work per terminare correttamente– rollback work per abortire la transazione

• Un sistema transazionale (OLTP) e’ in grado di definire ed eseguire transazioni per conto di un certo numero di applicazioni concorrenti

3


DIFFERENZA FRA APPLICAZIONE E TRANSAZIONE

begin T1

begin T2

end T1

end T2

TRANSAZIONE T2

TRANSAZIONE T1

PROGRAMMAAPPLICATIVO

AZIONI

AZIONI


Una transazione

start transaction;update ContoCorrente

set Saldo = Saldo + 10 where NumConto = 12202;update ContoCorrenteset Saldo = Saldo – 10 where NumConto = 42177;

commit work;

4


Una transazione con varie decisioni

start transaction;update ContoCorrente

set Saldo = Saldo + 10 where NumConto = 12202;update ContoCorrenteset Saldo = Saldo – 10 where NumConto = 42177;

select Saldo into A from ContoCorrentewhere NumConto = 42177;

if (A>=0) then commit workelse rollback work;


Transazioni in JDBC

• Scelta della modalità delle transazioni: un metodo definito nell'interfaccia Connection:

setAutoCommit(boolean autoCommit)

• con.setAutoCommit(true)

– (default) "autocommit": ogni operazione è una transazione

• con.setAutoCommit(false)

– gestione delle transazioni da programmacon.commit()con.rollback()

– non c'è start transaction

5


Il concetto di transazione

• Una unità di elaborazione che gode delle proprietà"ACIDE" – Atomicità– Consistenza– Isolamento– Durabilità (persistenza)


Atomicità

• Una transazione è una unità atomica di elaborazione• Non può lasciare la base di dati in uno stato intermedio

– un guasto o un errore prima del commit debbono causare l'annullamento (UNDO) delle operazioni svolte

– un guasto o errore dopo il commit non deve avere conseguenze; se necessario vanno ripetute (REDO) le operazioni

• Esito– Commit = caso "normale" e più frequente (99% ?)– Abort (o rollback)

• richiesto dall'applicazione = suicidio• richiesto dal sistema (violazione dei vincoli, concorrenza,

incertezza in caso di fallimento) = omicidio

6


Consistenza

• La transazione rispetta i vincoli di integrità• Conseguenza:

– se lo stato iniziale è corretto– anche lo stato finale è corretto


Isolamento

• La transazione non risente degli effetti delle altre transazioniconcorrenti– l'esecuzione concorrente di una collezione di transazioni

deve produrre un risultato che si potrebbe ottenere con una esecuzione sequenziale

• Conseguenza: una transazione non espone i suoi stati intermedi– si evita l' "effetto domino"

7


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)

8


Memoriasecondaria

Gestore dellamemoria secondaria

Gestoredel buffer

Gestore deimetodi d’accesso

Gestore di Interrogazioni e aggiornamenti

Gestore delletransazioni

Gestore dellaconcorrenza

Gestore dellaaffidabilità

Gestore degli accessi e delle interrogazioni

Gestoredelle transazioni


Gestore dell'affidabilità

• Gestisce l'esecuzione dei comandi transazionali– start transaction (B, begin)– commit work (C)– rollback work (A, abort)e le operazioni di ripristino (recovery) dopo i guasti :– warm restart e cold restart

• Assicura atomicità e durabilità• Usa il log:

– Un archivio permanente che registra le operazioni svolte– Due metafore:

• il filo di Arianna • i sassolini e le briciole di Hansel e Gretel

9


Architettura del controllore dell'affidabilità

BD

Log


Gestoredel buffer



Gestore della affidabilità

fix, unfix begin, commit, abort

fix, unfix, force(pagine BD e log)

read, write


Persistenza delle memorie

• Memoria centrale: non è persistente• Memoria di massa: è persistente ma può danneggiarsi• Memoria stabile: memoria che non può danneggiarsi (è una

astrazione):– perseguita attraverso la ridondanza:

• dischi replicati• nastri• …

10


Modello di riferimento

• Una transazione è costituita da una sequenza di operazioni di input-output su oggetti astratti x, y, z (ignoriamo la semantica delle applicazioni)


Il log

• Il log è un file sequenziale gestito dal controllore dell'affidabilità, scritto in memoria stabile

• “Diario di bordo:” riporta tutte le operazioni in ordine• Record nel log

– operazioni delle transazioni • begin, B(T) • insert, I(T,O,AS) • delete, D(T,O,BS)• update, U(T,O,BS,AS) • commit, C(T), abort, A(T)

– record di sistema • dump• checkpoint

11


Struttura del log

CK CrashB(T1) B(T2) C(T2) B(T3)

U(T3,…)U(T1,…)U(T2,…)

dumpU(T2,…)

U(T3,…)U(T1,…)

CK


Log, checkpoint e dump: a che cosa servono?

• Il log serve “a ricostruire” le operazioni• Checkpoint e dump servono ad evitare che la ricostruzione

debba partire dall'inizio dei tempi– si usano con riferimento a tipi di guasti diversi

12


Undo e redo

• Undo di una azione su un oggetto O: – update, delete: copiare il valore del before state (BS)

nell'oggetto O– insert: eliminare O

• Redo di una azione su un oggetto O:– insert, update: copiare il valore dell' after state (AS) into

nell'oggetto O – delete: reinserire O

• Idempotenza di undo e redo: – undo(undo(A)) = undo(A) – redo(redo(A)) = redo(A)


Dump

• Copia completa (“di riserva,” backup) della base di dati– Solitamente prodotta mentre il sistema non è operativo– Salvato in memoria stabile– Un record di dump nel log indica il momento in cui il log è

stato effettuato (e dettagli pratici, file, dispositivo, …)

13


Checkpoint

• Operazione che serve a "fare il punto" della situazione, semplificando le successive operazioni di ripristino:– ha lo scopo di registrare quali transazioni sono attive in un

certo istante (e dualmente, di confermare che le altre o non sono iniziate o sono finite)

• Paagone (estremo):– la "chiusura dei conti" di fine anno di una amministrazione:

• dal 25 novembre (ad esempio) non si accettano nuove richieste di "operazioni" e si concludono tutte quelle avviate prima di accettarne di nuove


Checkpoint (2)

• Varie modalità, vediamo la più semplice:– si sospende l'accettazione di richieste di ogni tipo (scrittura,

inserimenti, …, commit, abort)– si trasferiscono in memoria di massa (tramite force) tutte le

pagine sporche relative a transazioni andate in commit– si registrano sul log in modo sincrono (force) gli identificatori

delle transazioni in corso (“record di checkpoint”)– si riprende l'accettazione delle operazioni

• Così siamo sicuri che – per tutte le transazioni che hanno effettuato il commit i dati

sono in memoria di massa– le transazioni "a metà strada" sono elencate nel checkpoint

14


Esito di una transazione

• L'esito di una transazione è determinato irrevocabilmente quando viene scritto il record di commit nel log in modo sincrono, con una force– una guasto prima di tale istante può portare (se necessario)

ad un undo di tutte le azioni, per ricostruire lo stato originario della base di dati

– un guasto successivo non deve avere conseguenze: lo stato finale della base di dati deve essere ricostruito, con redo (se necessario)

• record di abort possono essere scritti in modo asincrono


Regole fondamentali per il log

• Write-Ahead-Log:– si scrive sul giornale (il BS) prima che nella basi di dati

• consente di disfare le azioni• Commit-Precedenza:

– si scrive sul giornale (AS) prima del commit• consente di rifare le azioni

• Quando scriviamo nella base di dati?– Varie alternative

15


Scrittura nel log e nella base di dati

(c)

(a)

(b)

Scritture nel log

Scritture nella base di dati

t

t

t

w(x) w(y)

w(y) w(x)

w(x) w(y)

B(T) U(T,X,BS,AS) U(T,Y,BS,AS) C




Modalita’ immediata

• Il DB contiene valori AS provenienti da transazioni uncommitted• Richiede Undo delle operazioni di transazioni uncommited al

momento del guasto• Non richiede Redo

dump CK Crash

T3

T1

T4

T2

T5

Niente NienteNiente

UndoUndo

16


Modalita’ differita

• Il DB non contiene valori AS provenienti da transazioni uncommitted

• In caso di abort, non occorre fare niente• Rende superflua la procedura di Undo. Richiede Redo

dump CK Crash

T3

T1

T4

T2

T5

Niente RedoRedo

NienteNiente


Esiste una terza modalita’:modalità mista

• La scrittura puo’ avvenire in modalita’ sia immediata che differita• Consente l’ottimizzazione delle operazioni di flush• Richiede sia Undo che Redo

dump CK Crash

T3

T1

T4

T2

T5

Redo

Redo

UndoUndo

Niente

17


Ottimizzazioni

• Diversi record di log in una pagina• Diversi record di log scritti insieme in modo sincrono subito

prima del commit• Commit di diverse transazioni in contemporanea (group commit)• Parallelismo nella scrittura dei log


Guasti

• Guasti "soft": errori di programma, crash di sistema, caduta di tensione– si perde la memoria centrale– non si perde la memoria secondariawarm restart, ripresa a caldo

• Guasti "hard": sui dispositivi di memoria secondaria– si perde anche la memoria secondaria– non si perde la memoria stabile (e quindi il log)cold restart, ripresa a freddo

18


Modello "fail-stop"

Fail

FailStop

Boot

Restart

Normal

Restartcompletato


Processo di restart

• Obiettivo: classificare le transazioni in– completate (tutti i dati in memoria stabile)– in commit ma non necessariamente completate (può servire

redo)– senza commit (vanno annullate, undo)

19


Ripresa a caldo

Quattro fasi:• trovare l'ultimo checkpoint (ripercorrendo il log a ritroso)• costruire gli insiemi UNDO (transazioni da disfare) e REDO

(transazioni da rifare) • ripercorrere il log all'indietro, fino alla più vecchia azione delle

transazioni in UNDO e REDO, disfacendo tutte le azioni delle transazioni in UNDO

• ripercorrere il log in avanti, rifacendo tutte le azioni delle transazioni in REDO


Esempio di warm restartB(T1)B(T2)U(T2, O1, B1, A1)I(T1, O2, A2)B(T3)C(T1)B(T4)U(T3,O2,B3,A3)U(T4,O3,B4,A4)CK(T2,T3,T4)C(T4)B(T5)U(T3,O3,B5,A5)U(T5,O4,B6,A6)D(T3,O5,B7)A(T3)C(T5)I(T2,O6,A8)

CK Crash

T4

T1

T2

T3

T5

C

A

C

C

20


1. Ricerca dell’ultimo checkpointB(T1)B(T2)U(T2, O1, B1, A1)I(T1, O2, A2)B(T3)C(T1)B(T4)U(T3,O2,B3,A3)U(T4,O3,B4,A4)CK(T2,T3,T4)C(T4)B(T5)U(T3,O3,B5,A5)U(T5,O4,B6,A6)D(T3,O5,B7)A(T3)C(T5)I(T2,O6,A8)

CK Crash

T4

T1

T2

T3

T5

C

A

C

C


2. Costruzione degli insiemi UNDO e REDO

B(T1)B(T2)U(T2, O1, B1, A1)I(T1, O2, A2)B(T3)C(T1)B(T4)U(T3,O2,B3,A3)U(T4,O3,B4,A4)CK(T2,T3,T4)

1. C(T4)2. B(T5)

U(T3,O3,B5,A5)U(T5,O4,B6,A6)D(T3,O5,B7)A(T3)

3. C(T5)I(T2,O6,A8)

0. UNDO = {T2,T3,T4}. REDO = {}

1. C(T4) UNDO = {T2, T3}. REDO = {T4}

2. B(T5) UNDO = {T2,T3,T5}. REDO = {T4}

3. C(T5) UNDO = {T2,T3}. REDO = {T4, T5}

Setup

21


3. Fase UNDO

B(T1)B(T2)

8. U(T2, O1, B1, A1)I(T1, O2, A2)B(T3)C(T1)B(T4)

7. U(T3,O2,B3,A3)U(T4,O3,B4,A4)CK(T2,T3,T4)

1. C(T4)2. B(T5)6. U(T3,O3,B5,A5)

U(T5,O4,B6,A6)5. D(T3,O5,B7)

A(T3)3. C(T5)4. I(T2,O6,A8)

0. UNDO = {T2,T3,T4}. REDO = {}

1. C(T4) UNDO = {T2, T3}. REDO = {T4}

2. B(T5) UNDO = {T2,T3,T5}. REDO = {T4}

3. C(T5) UNDO = {T2,T3}. REDO = {T4, T5}

4. D(O6)

5. O5 =B7

6. O3 = B5

7. O2 =B3

8. O1=B1

Undo

Setup


4. Fase REDO

B(T1)B(T2)

8. U(T2, O1, B1, A1)I(T1, O2, A2)B(T3)C(T1)B(T4)

7. U(T3,O2,B3,A3)9. U(T4,O3,B4,A4)

CK(T2,T3,T4)1. C(T4)2. B(T5)6. U(T3,O3,B5,A5)10. U(T5,O4,B6,A6)5. D(T3,O5,B7)

A(T3)3. C(T5)4. I(T2,O6,A8)

0. UNDO = {T2,T3,T4}. REDO = {}

1. C(T4) UNDO = {T2, T3}. REDO = {T4}

2. B(T5) UNDO = {T2,T3,T5}. REDO = {T4}

3. C(T5) UNDO = {T2,T3}. REDO = {T4, T5}

4. D(O6)

5. O5 =B7

6. O3 = B5

7. O2 =B3

8. O1=B1

9. O3 = A4

10. O4 = A6

Undo

Redo

Setup

22


Ripresa a freddo

• Si ripristinano i dati a partire dal backup• Si eseguono le operazioni registrate sul giornale fino all'istante

del guasto• Si esegue una ripresa a caldo


Memoriasecondaria


Gestoredel buffer


Gestore di Interrogazioni e aggiornamenti


Gestore dellaconcorrenza

Gestore dellaaffidabilità

Gestore degli accessi e delle interrogazioni

Gestoredelle transazioni

23


Controllo di concorrenza

• La concorrenza è fondamentale: decine o centinaia di transazioni al secondo, non possono essere seriali

• Esempi: banche, prenotazioni aeree

Problema• Anomalie causate dall'esecuzione concorrente, che quindi va

governata


Perdita di aggiornamento

• Due transazioni identiche: – t1: r(x), x = x + 1, w(x)– t2 : r(x), x = x + 1, w(x)

• Inizialmente x=2; dopo un'esecuzione seriale x=4• Un'esecuzione concorrente:

t1 t2

r1(x)x = x + 1

r2(x)x = x + 1

w1(x)commit

w2(x)commit

• Un aggiornamento viene perso: x=3

24


Lettura sporca

t1 t2

r1(x)x = x + 1w1(x)

r2(x) abort

• t2 ha letto uno stato intermedio ("sporco") e lo può comunicare all'esterno


Letture inconsistenti

• t1 legge due volte x :t1 t2

r1(x)r2(x)x = x + 1w2(x)commit

r1(x)commit

• t1 legge due valori diversi per x !

25


Aggiornamento fantasma

• Supponiamo che y + z = 1000; t1 t2

r1(y)r2(y)y = y - 100r2(z)z = z + 100w2(y)w2(z)commit

r1(z)s = y + zcommit

• s = 1100: ma la somma y + z non è mai stata “davvero” 1100:– t1 vede uno stato non esistente (o non coerente)


Inserimento fantasma

t1 t2

"legge gli stipendi degli impiegatidel dip A e calcola la media"

"inserisce un impiegato in A"commit

"legge gli stipendi degli impiegatidel dip A e calcola la media"commit

26


Anomalie

• Perdita di aggiornamento W-W• Lettura sporca R-W (o W-W) con abort• Letture inconsistenti R-W• Aggiornamento fantasma R-W• Inserimento fantasma R-W su dato "nuovo"


Gestore della concorrenza (ignorando buffer e affidabilità)

BD




Gestore della concorrenza

read, write begin, commit, abort

read, write(non tutte e in ordine ev. diverso)

Tabella dei lock

27


“Teoria” del controllo di concorrenza

• Transazione: sequenza di letture e scritture (senza ulteriore semantica)

• Notazione: ogni transazione ha un identificatore univoco• Esempio:

– t 1 : r1(x) r1(y) w1(x) w1(y)• Ipotesi semplificativa (che rimuoveremo in futuro, in quanto non

accettabile in pratica):– ignoriamo le transazioni che vanno in abort (e quindi non

scriviamo commit e abort)


Schedule

• Sequenza di operazioni di input/output di transazioni concorrenti• Esempio:

S1 : r1(x) r2(z) w1(x) w2(z)• A seguito dell’ipotesi semplificativa:

– consideriamo la commit-proiezione degli schedule reali, in quanto ignoriamo le transazioni che vanno in abort, rimuovendo tutte le loro azioni dallo schedule

28


Controllo di concorrenza

• Obiettivo: evitare le anomalie• Scheduler: un sistema che accetta o rifiuta (o riordina) le

operazioni richieste dalle transazioni (mantenendo l'ordine delle azioni in ciascuna transazione)

• Schedule seriale: le transazioni sono separate, una alla voltaS2 : r0(x) r0(y) w0(x) r1(y) r1(x) w1(y) r2(x) r2(y) r2(z) w2(z)

– uno schedule seriale non presenta anomalie• Schedule serializzabile: produce lo “stesso risultato” di uno

schedule seriale sulle stesse transazioni– richiede una nozione di equivalenza fra schedule


Idea base

• Individuare classi di schedule serializzabili che siano sottoclassi degli schedule possibili, siano serializzabili e la cui proprietà di serializzabilità sia verificabile a costo basso

ScheduleSeriali

ScheduleScheduleSerializzabili

29


View-Serializzabilità

• Definizioni prelilminari:– ri(x) legge-da wj(x) in uno schedule S se wj(x) precede ri(x)

in S e non c'è wk(x) fra ri(x) e wj(x) in S– wi(x) in uno schedule S è scrittura finale se è l'ultima

scrittura dell'oggetto x in S• Schedule view-equivalenti (Si ≈V Sj): hanno la stessa relazione

legge-da e le stesse scritture finali – nota: le operazioni di una transazione debbono mantenere

l'ordine• Uno schedule è view-serializzabile se è view-equivalente ad

un qualche schedule seriale• L'insieme degli schedule view-serializzabili è indicato con VSR


View serializzabilità: esempi

S2 : r2(x) w0(x) r1(x) w2(x) w2(z)S3 : w0(x) r2(x) r1(x) w2(x) w2(z)S4 : w0(x) r1(x) r2(x) w2(x) w2(z)S5 : w0(x) r1(x) w1(x) r2(x) w1(z)S6 : w0(x) r1(x) w1(x) w1(z) r2(x)

– S2 non è view-equivalente a S3

– S3 è view-equivalente allo schedule seriale S4 (e quindi èview-serializzabile)

– S5 è view-equivalente allo schedule seriale S6

30


View serializzabilità: esempi (2)

S7 : r1(x) r2(x) w1(x) w2(x) (perdita di aggiornamento)S8 : r1(x) r2(x) w2(x) r1(x) (letture inconsistenti)S9 : r1(x) r1(y) r2(z) r2(y) w2(y) w2(z) r1(z)

(aggiornamento fantasma)

• S7, S8, S9 non sono view-serializzabili


View serializzabilità

• Complessità:– la verifica della view-equivalenza di due schedule dati:

• polinomiale– decidere sulla View serializzabilità di uno schedule:

• problema NP-completo• Non è utilizzabile in pratica

31


Conflict-serializzabilità

• Definizione preliminare:– Un'azione ai è in conflitto con aj (i≠ j), se operano sullo

stesso oggetto e almeno una di esse è una scrittura. Due casi:

• conflitto read-write (rw o wr) • conflitto write-write (ww).

• Schedule conflict-equivalenti (Si ≈C Sj): includono le stesse operazioni e ogni coppia di operazioni in conflitto compare nello stesso ordine in entrambi

• Uno schedule è conflict-serializable se è conflict-equivalente ad un qualche schedule seriale

• L'insieme degli schedule conflict-serializzabili è indicato con CSR


CSR e VSR

• Ogni schedule conflict-serializzabile è view-serializzabile, ma non necessariamente viceversa

• Controesempio per la non necessità:

• r1(x) w2(x) w1(x) w3(x)

– view-serializzabile: • view-equivalente a r1(x) w1(x) w2(x) w3(x)

– non conflict-serializzabile

• Sufficienza: vediamo

32


CSR implica VSR

• CSR: esiste schedule seriale conflict-equivalente• VSR: esiste schedule seriale view-equivalente• Per dimostrare che CSR implica VSR è sufficiente dimostrare

che la conflict-equivalenza ≈C implica la view-equivalenza ≈V , cioè che se due schedule sono ≈C allora sono ≈V

• Quindi, supponiamo S1 ≈C S2 e dimostriamo che S1 ≈ V S2I due schedule hanno:– stesse scritture finali: se così non fosse, ci sarebbero

almeno due scritture in ordine diverso e poiché due scritture sono in conflitto i due schedule non sarebbero ≈C

– stessa relazione “legge-da”: se così non fosse, ci sarebbero scritture in ordine diverso o coppie lettura-scrittura in ordine diverso e quindi, come sopra, sarebbe violata la ≈C


CSR e VSR

ScheduleSeriali

ScheduleScheduleVSR

ScheduleCSR

33


Verifica di conflict-serializzabilità

• Per mezzo del grafo dei conflitti:– un nodo per ogni transazione ti– un arco (orientato) da ti a tj se c'è almeno un conflitto fra

un'azione ai e un'azione aj tale che ai precede aj

• Teorema– Uno schedule è in CSR se e solo se il grafo è aciclico


CSR e aciclicità del grafo dei conflitti

• Se uno schedule S è CSR allora è ≈C ad uno schedule seriale.Supponiamo le transazioni nello schedule seriale ordinate secondo il TID: t1, t2, …, tn . Poiché lo schedule seriale ha tutti i conflitti nello stesso ordine dello schedule S, nel grafo di S ci possono essere solo archi (i,j) con i<j e quindi il grafo non può avere cicli, perché un ciclo richiede almeno un arco (i,j) con i>j.

• Se il grafo di S è aciclico, allora esiste fra i nodi un “ordinamento topologico” (cioè una numerazione dei nodi tale che il grafo contiene solo archi (i,j) con i<j). Lo schedule seriale le cui transazioni sono ordinate secondo l’ordinamento topologico èequivalente a S, perché per tutti i conflitti (i,j) si ha sempre i<j.

34


Controllo della concorrenza in pratica

• Anche la conflict-serializabilità, pur più rapidamente verificabile (l'algoritmo, con opportune strutture dati richiede tempo lineare), è inutilizzabile in pratica

• Sarebbe efficiente se potessimo conoscere il grafo dall’inizio, ma così non è: uno scheduler deve operare “incrementalmente”, cioè ad ogni richiesta di operazione decidere se eseguirla subito oppure fare qualcos’altro; non è praticabile mantenere il grafo, aggiornarlo e verificarne l’aciclicità ad ogni richiesta di operazione

• Inoltre, si basa sull’ipotesi di commit-proiezione


Controllo della concorrenza in pratica, 2

• In pratica, si utilizzano tecniche che– garantiscono la conflict-serializzabilità senza dover costruire

il grafo– non richiedono l’ipotesi della commit-proiezione

• Le tecniche utilizzate– 2PL (two-phase locking)– timestamp

35


Lock

• Principio: – Tutte le letture sono precedute da r_lock (lock condiviso) e

seguite da unlock– Tutte le scritture sono precedute da w_lock (lock esclusivo)

e seguite da unlock• Quando una transazione prima legge e poi scrive un oggetto,

può:– richiedere subito un lock esclusivo– chiedere prima un lock condiviso e poi uno esclusivo (lock

escalation)• Il lock manager riceve queste richieste dalle transazioni e le

accoglie o rifiuta, sulla base della tavola dei conflitti


Gestione dei lock

• Basata sulla tavola dei conflittiRiochiesta Stato della risorsa

free r_locked w_lockedr_lock OK / r_locked OK / r_locked NO/ w_lockedw_lock OK / w_locked NO / r_locked NO / w_lockedunlock error OK / depends OK / free

– Un contatore tiene conto del numero di "lettori"; la risorsa èrilasciata quando il contatore scende a zero

• Se la risorsa non è concessa, la transazione richiedente è posta in attesa (eventualmente in coda), fino a quando la risorsa non diventa disponibile

• Il lock manager gestisce una tabella dei lock, per ricordare la situazione

36


Locking a due fasi

• Usato da quasi tutti i sistemi• Garantisce "a priori" la conflict-serializzabilità• Basata su due regole:

– protezione con lock di tutte le letture e scritture– vincolo sulle richieste e i rilasci dei lock:

• una transazione, dopo aver rilasciato un lock, non può acquisirne altri


2PL e CSR

• Ogni schedule 2PL e’ anche conflict serializzabile, ma non necessariamente viceversa

• Controesempio per la non necessita’:

r1(x) w1(x) r2(x) w2(x) r3(y) w1(y)

– Viola 2PL– Conflict-serializzabile

• Sufficienza: vediamo

37


2PL implica CSR

• S schedule 2PL• Consideriamo per ciascuna transazione l’istante in cui ha tutte le

risorse e sta per rilasciare la prima• Ordiniamo le transazioni in accordo con questo valore

temporale e consideriamo lo schedule seriale corrispondente• Vogliamo dimostrare che tale schedule è equivalente ad S:

– allo scopo, consideriamo un conflitto fra un’azione di ti e un’azione di tj con i<j; è possibile che compaiano in ordine invertito in S? no, perché in tal caso tj dovrebbe aver rilasciato la risorsa in questione prima della sua acquisizione da parte di ti


Concorrenza e fallimento di transazioni

• Rimuoviamo l’ipotesi di “commit-proiezione”• Le transazioni possono fallire:

– rollback a cascata (“effetto domino”):• se Ti ha letto un dato scritto da Tk e Tk fallisce, allora

anche Ti deve fallire– letture sporche:

• se Ti ha letto un dato scritto da Tk e Tk fallisce, ma nel frattempo Ti è andata in commit, allora abbiamo l’anomalia

38


Evitiamo effetto domino e letture sporche

• letture sporche:– una transazione non può andare in commit finché non sono

andate in commit tutte le transazioni da cui ha letto;– schedule che soddisfano questa condizione sono detti

recuperabili (recoverable)• rollback a cascata (“effetto domino”)

– una transazione non deve poter leggere dati scritti da transazioni che non sono ancora andate in commit


Locking a due fasi stretto (S2PL)

• Evita sia le letture sporche sia l’effetto domino• 2PL con una condizione aggiuntiva:

– I lock possono essere rilasciati solo dopo il commit o abort

39


CSR, VSR e 2PL

ScheduleSeriali

ScheduleScheduleVSR Schedule

CSRScheduleS2PLSchedule

2PL


Controllo di concorrenza basato su timestamp

• Tecnica alternativa al 2PL• Timestamp:

– identificatore che definisce un ordinamento totale sugli eventi di un sistema

• Ogni transazione ha un timestamp che rappresenta l'istante di inizio della transazione

• Uno schedule è accettato solo se riflette l'ordinamento seriale delle transazioni indotto dai timestamp

40


Dettagli

• Lo scheduler ha due contatori RTM(x) e WTM(x) per ogni oggetto• Lo scheduler riceve richieste di letture e scritture (con indicato il

timestamp della transazione):– read(x,ts):

• se ts < WTM(x) allora la richiesta è respinta e la transazione viene uccisa;

• altrimenti, la richiesta viene accolta e RTM(x) è posto uguale al maggiore fra RTM(x) e ts

– write(x,ts): • se ts < WTM(x) o ts < RTM(x) allora la richiesta è respinta e la

transazione viene uccisa, • altrimenti, la richiesta viene accolta e WTM(x) è posto uguale a

ts• Vengono uccise molte transazioni• Per funzionare anche senza ipotesi di commit-proiezione, deve

"bufferizzare" le scritture fino al commit (con attese)


Esempio

RTM(x) = 7WTM(x) = 4

Richiesta Risposta Nuovo valore

read(x,6) okread(x,8) ok RTM(x) = 8read(x,9) ok RTM(x) = 9write(x,8) no, t8 uccisawrite(x,11) ok WTM(x) = 11read(x,10) no, t10 uccisa

41


Multiversion concurrency control

• Main idea: writes generate new copies, reads make access tothe correct copy

• Writes generate new copies each with a WTM. At any time, N >1 copies of each object x are active, with WTMN(x). There is onlyone global RTM(x)

• Mechanism: – read(x,ts): is always accepted. xk selected for reading such

that: if ts > WTMN(x), then k = N, otherwise k is taken suchthat WTMk(x) < ts < WTMk+1(x)

– write(x,ts): if ts < RTM(x) the request is refused, otherwise a new version of the item of data is added (N increased byone) with WTMN(x) = ts

• Old copies are discarded when there are no read transactionsinterested in their values


2PL vs TS

• Sono incomparabili

– Schedule in TS ma non in 2PLr1(x) w1(x) r2(x) w2(x) r0(y) w1(y)

– Schedule in 2PL ma non in TSr2(x) w2(x)r1(x) w1(x)

– Schedule in TS e in 2PLr1(x) r2(y) w2(y) w1(x) r2(x) w2(x)

42


CSR, VSR, 2PL e TS

Seriali

Tutti

VSR

CSR

2PL

TS


2PL vs TS

• In 2PL le transazioni sono poste in attesa• In TS uccise e rilanciate• Per rimuovere la commit proiezione, attesa per il commit in

entrambi i casi• 2PL può causare deadlock (vedremo)• Le ripartenze sono di solito più costose delle attese:

– conviene il 2PL

43


Lock management

• Interface: – r_lock(T, x, errcode, timeout)– w_lock(T, x, errcode, timeout)– unlock(T, x)

T: transaction identifierX: data elementtimeout: max wait in queue

• If timeout expires, errcode signals an error, typically the transaction rolls back and restarts


Hierarchical locking

• In many real systems locks can be specified at differentgranularity, e.g. tables, fragments, tuples, fields. These are organized in a hierarchy (possibly a directed acyclic graph)

• 5 locking modes:– 2 are shared and exclusive, renamed as:

• XL: exclusive lock• SL: shared lock

– 3 are new:• ISL: intention shared lock• IXL: intention exclusive lock• SIXL: shared intention-exclusive lock

• The choice of lock granularity is left to application designers;– too coarse: many resources are blocked– too fine: many locks are requested

44


Hierarchical locking protocol

• Locks are requested from the root to descendents in a hierarchy• Locks are released starting at the node locked and moving up

the tree• In order to request an SL or ISL on a node, a transaction must

already hold an ISL or IXL lock on the parent node• In order to request an IXL, XL, or SIXL on a node, a transaction

must already hold an SIXL or IXL lock on the parent node• The new conflict table is shown in the next slide


Conflicts in hierarchical locking

Resource stateRequest

ISL IXL SL SIXL XLISL OK OK OK OK NoIXL OK OK No No NoSL OK No OK No NoSIXL OK No No No NoXL No No No No No

45


Stallo (deadlock)

• Attese incrociate: due transazioni detengono ciascuna una risorsa e aspetttano la risorsa detenuta dall'altra

• Esempio: – t1: read(x), write(y)– t2: read(y), write(x)– Schedule:

r_lock1(x), r_lock2(y), read1(x), read2(y) w_lock1(y), w_lock2(x)


Risoluzione dello stallo

• Uno stallo corrisponde ad un ciclo nel grafo delle attese (nodo=transazione, arco=attesa)

• Tre tecniche1. Timeout (problema: scelta dell'intervallo, con trade-off)2. Rilevamento dello stallo 3. Prevenzione dello stallo

• Rilevamento: ricerca di cicli nel grafo delle attese• Prevenzione: uccisione di transazioni "sospette" (può

esagerare)

46


Livelli di isolamento in SQL:1999 (e JDBC)

• Le transazioni possono essere definite read-only (non possono richiedere lock esclusivi)

• 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 è sempre evitata


Anomalie

Perdita di aggiornamento W-W• read uncommitted

Lettura sporca R-W (o W-W) con abort• read committed

Letture inconsistenti R-WAggiornamento fantasma R-W

• repeatable read

Inserimento fantasma R-W su dato "nuovo"• serializable

47


Livelli di isolamento: implementazione

• Sulle scritture si ha sempre il 2PL stretto (e quindi si evita la perdita di aggiornamento)

• 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 anche in lettura, con lock sui dati

• serializable:– 2PL con lock di predicato


Lock di predicato

• Caso peggiore:– sull'intera relazione

• Se siamo fortunati:– sull'indice

48


Casi di studio per il tuningdi basi di dati

dal testo:D. Shasha.Database Tuning: a principled approach.Prentice-Hall, 1992


Caso 1

• Abbiamo una base di dati con dieci relazioni su due dischi: cinque e cinque; su un disco c'è anche il log.

• Compriamo un nuovo disco; che cosa ci mettiamo?

Possibile risposta• Il log

49


Caso 2

• Il tempo di risposta è variabile, in particolare ci sono rallentamenti quando vengono eseguite operazioni DDL

Possibile motivazione• Le operazioni DDL richiedono lock in scrittura sul catalogo


Caso 3

• Transazioni così organizzate sono insoddisfacenti:attribuzione di un nuovo numero di praticarichiesta di informazioni interattiveeffettuazione dell'inserimento

Possibile soluzione• transazione troppo lunga; vanno riordinati i passi, e nella

transazione ci devono essere solo il primo e il terzo

50


Caso 4

• Una transazione così organizzata eseguita a fine mese, di sera, è inefficiente:

per ogni conto stampare tutte le info ...

Possibile soluzione• essendo di sola lettura, di sera (tempo morto) potrebbe essere

senza lock (Read Uncommitted)


Casi 5 e 6

• Nell'ambito di una transazione, si calcola lo stipendio medio per ciascun dipartimento. Contemporaneamente si fanno modifiche su singoli stipendi.

• Le prestazioni sono insoddisfacenti. Possibili soluzioni• si può eseguire in un tempo morto (senza aggiornamenti) senza

lock (Read Uncommitted)• se sono tollerate (leggere) inconsistenze, si può procedere

senza lock (Read Uncommitted)• si può fare una copia e lavorare su di essa (dati non attuali)• se nessuna delle alternative è praticabile (non ci sono tempi

morti e si vogliono dati attuali e consistenti) si può provare con Repeatable Read (non c'è rischio di "phantom")

51


Caso 7

• Un'applicazione prevede:– migliaia di inserimenti ogni ora– centinaia di migliaia di piccoli aggiornamenti ogni ora

• Gli inserimenti arrivano in transazioni grandi ogni mezz'ora e durano 5 minuti. In queste fasi le prestazioni sono inaccettabili (tempo di risposta 30 sec, rispetto a mezzo secondo)

Possibili soluzioni• spezzare le transazioni con gli inserimenti• riorganizzare i file evitando strutture ordinate


Caso 8

• Un'applicazione che prevede un'istruzione SQL all'interno di un ciclo è lenta (e usa molto tempo di CPU)

Possibile soluzione• usare bene il cursore (facciamo fare i cicli e soprattutto i join

all'SQL)

52


Caso 9

• Un disco è inefficiente anche se non pieno. Ci sono relativamente pochi inserimenti e molte letture lunghe (scansioni)

Possibili soluzioni• separare il log su un disco a sé• riorganizzare i file in modo contiguo


Caso 10

• Una società di servizi emette tutte le bollette a fine mese, con un programma che ha bisogno di tutta la notte, impedendo cosìl'esecuzione di altri programmi batch che sarebbero necessari

Possibili soluzioni• è proprio necessario che le bollette siano emesse tutte insieme?• se è proprio necessario, magari facciamolo durante il week-end

(tempo morto più lungo)

Basi di dati vol.2 Capitolo 2 Gestione delle...

Documents

Transcript of Basi di dati vol.2 Capitolo 2 Gestione delle...