Gestione delle transazioni: controllo di concorrenza...

1

Gestione delle transazioni:controllo di concorrenza

T04Paolo Atzeni, Stefano Ceri

8/05/2003

8/05/2003 T04: P. Atzeni, S. Ceri Gestione delle transazioni: concorrenza

2

Memoriasecondaria

Gestore dellamemoria secondaria

Gestoredel buffer

Gestore deimetodi d’accesso

Gestore diInterrogazioni e aggiornamenti

Gestore delletransazioni

Gestore dellaconcorrenza

Gestore dellaaffidabilità

Gestore degli accessi e delle interrogazioni

Gestoredelle transazioni

2


3

Concurrency control

• Concurrency: highly desired• Measured in tps (transactions per second) - typical values are

tens to hundreds to thousands tps• Typical examples: banks, airline reservation systems

Architecture• Input-output operations on abstract objects x, y, z• Each input-output operation reads secondary memory blocks

into buffer pages or writes buffer pages into secondary memory blocks

• For simplicity: one-to-one mapping from blocks to pages

Problem• Anomalies due to concurrent execution


4

Anomaly 1: Update loss

• Consider two identical transactions: – t 1 : r(x), x = x + 1, w(x)– t 2 : r(x), x = x + 1, w(x)

• Assume initially x=2; after serial execution x=4• Consider concurrent execution:

– Transaction t1 Transaction t2botr1(x)x = x + 1

botr2(x)x = x + 1

w1(x)commit

w2(x)commit

• One update is lost, final value x=3

3


5

Anomaly 2: Dirty read

• Consider the same two transactions, and the followingexecution (note that the first transaction fails):

– Transaction t1 Transaction t2botr1(x)x = x + 1w1(x)

botr2(x)x = x + 1

abortw2(x)commit

• Critical aspect: t2 reads an intermediate state (dirty read)


6

Anomaly 3: Inconsistent read

• t1 repeats two reads:– Transaction t1 Transaction t2

botr1(x)

botr2(x)x = x + 1w2(x)commit

r1(x)commit

• t1 reads different values for x

4


7

Anomaly 4: Ghost update

• Assume the integrity constraint x + y + z = 1000; – Transaction t1 Transaction t2

botr1(x)

botr2(y)

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

r1(z)s = x + y + zcommit

• In the end, s = 110: the integrity constraint is not satisfied• t1 sees a ghost update


8

Anomaly 5: Phantom

– Transaction t1 Transaction t2

botread salaries of employeesin dept Aand compute average

botinsert new employee in Dept Acommit

read salaries of employeesin dept Aand compute averagecommit

5


9

Anomalie

1: Update loss W-W2: Dirty read R-W (o W-W) con abort 3: Inconsistent read R-W4: Ghost update R-W5: Phantom R-W su dato "nuovo"


10

Concurrency control theory

• Transaction: sequence of read or write actions• Each transaction has a unique, system-assigned transaction

identifier• Each transactions is initiated by the start transaction

command and terminated by commit o abort

• Example: t 1 : r1(x) r1(y) w1(x) w1(y)

6


11

Gestore della concorrenza(ignorando buffer e affidabilità)

BD

Gestore dellamemoria secondaria

Gestore deimetodi d’accesso

Gestore delletransazioni

Gestore della concorrenza

read, write begin, commit, abort

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

Tabella dei lock


12

Notion of Schedule

• Represents the sequence of input/output operations presented by concurrent transactions

• Example: S1 : r1(x) r2(z) w1(x) w2(z)• Simplifying assumption: we consider a commit-projection and

ignore the transactions that produce an abort, removing all their actions from the schedule

• This assumption is not acceptable in practice and will be removed

7


13

Foundations of concurrency control

• Objective: refuse the schedules that cause the anomalies• Scheduler: a system that accepts or rejects the operations

requested by transactions• Serial schedule: one in which the actions of all the transactions

appear in sequenceS2 : r0(x) r0(y) w0(x) r1(y) r1(x) w1(y) r2(x) r2(y) r2(z) w2(z)

• Serializable schedule: one that produces the same result as some serial schedule Sj of the same transactions – Requires a notions of equivalence between schedules– Progressive notions: view-equivalence, conflict-equivalence,

two-phase locking, timestamp-based• Observation: a scheduler allows the identification of a more or

less wide-ranging class of acceptable schedules at the cost of testing for equivalence


14

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

8


15

View-Serializability

• Preliminary definitions:– ri(x) reads-from wj(x) in a schedule S when wj(x) precedes

ri(x) in S and there is no wk(x) between ri(x) and wj(x) in S– wi(x) in a schedule S is a final write if it is the last write of the

object x to appear in S• View-equivalent schedules (Si ≈V Sj): if they possess the same

reads-from relation and the same final writes • A schedule is called view-serializable if it is view-equivalent to

some serial schedule • The set of view-serializable schedules is called VSR


16

View-Serializability

• Complexity of view-serializability:– Deciding on the view-equivalence of two given schedules:

done by a polynomial algorithm – Deciding on the view serializability of a generic schedule:

NP-complete problem

9


17

Examples of view serializability

• 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)– S3 is view-equivalent to the serial schedule S4 (thus, it is

view-serializable) – S5 is not view-equivalent to S4, but it is view-equivalent to the

serial schedule S6, and thus this also is view-serializable• S7 : r1(x) r2(x) w2(x) w1(x)

S8 : r1(x) r2(x) w2(x) r1(x)S9 : r1(x) r1(y) r2(z) r2(y) w2(y) w2(z) r1(z)– S7 corresponds to update loss, S8 to inconsistent reads and

S9 to ghost updates; they are not view-serializable


18

Conflict-serializability

• Preliminary definition:– Action ai is in conflict with aj (i≠ j), if both operate on the

same object and at least one of them is a write. Two cases:• read-write conflicts (rw or wr) • write-write conflicts (ww).

• Conflict-equivalent schedules (Si ≈C Sj): if they present the same operations and each pair of operations in conflict is in the same order in both the schedules

• A schedule is therefore conflict-serializable if there is a serial schedule that is conflict-equivalent to it. The set of conflict-serializable schedules is called CSR

• CSR is properly included into VSR

10


19

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


20

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 scritturesono in conflitto i due schedule non sarebbero ≈C

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

11


21

CSR e VSR

ScheduleSeriali

ScheduleScheduleVSR

ScheduleCSR


22

Testing conflict-serializability

• By means of the conflict graph, with;– a node for each transaction ti– an edge from ti to tj if there is at least one conflict between

an action ai and an action aj such that ai precedes aj

• A schedule is in CSR if and only if the graph is acyclic

12


23

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 cipossono 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 “ordinamentotopologico” (cioè una numerazione dei nodi tale che il grafocontiene 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.


24

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

• La tecnica sarebbe efficiente se potessimo conoscere il grafodall’inizio, ma così non è: uno scheduler deve operare“incrementalmente”, cioè ad ogni richiesta di operazionedecidere se eseguirla subito oppure fare qualcos’altro; non è praticabile mantenere il grafo, aggiornarlo e verificarnel’aciclicità ad ogni richiesta di operazione

• Inoltre, la tecnica si basa sull’ipotesi di commit-proiezione• In pratica, si utilizzano tecniche che

– garantiscono la conflict-serializzabilità senza dover costruireil grafo

– non richiedono l’ipotesi della commit-proiezione

13


25

Two-phase locking

• Used by almost all commercial DBMSs• A protocol that guarantees conflict serializability a-

priori• Based on two rules:

– "embed" all read and write operations within locks (to change order to operations)

– impose a constraint on the requests and releases of locks


26

Locks

• Principle: – All read operations preceded by r_lock (shared lock) and

followed unlock– All write operations preceded by w_lock (exclusive lock) and

followed unlockA transaction following these rules is well formed wrt locking

• When a transaction first reads and then writes an object it can:– Use a write lock– Move from shared lock to exclusive lock (lock escalation)

• The lock manager receives these primitives from transactions and grants resources according to conflict table– When the lock is granted, the resource is acquired– At the unlock, the resource is released

14


27

Behavior of the lock manager

• Based on conflict table:Request Resource state

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

– A counter keeps track of the number of readers; the resource is released when the counter is set to zero.

• If a lock request is not granted, the requesting transaction is put in a waiting state

• The waiting ends when the resource is unlocked and becomes available

• The locks already granted are stored in a lock table, managed by the lock manager


28

Two-phase locking

• Locks alone do not guarantee serializability• The 2PL protocol requires that locking satisfies a condition:

– A transaction, after having released a lock, cannot acquire other locks

• Two phases: growing and shrinking• the class of 2PL schedules is the set of the schedules that can

be obtained by allowing:– proper lock management– two-phases within each transaction

15


29

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


30

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 dei tj con i<j; è possibile che compaiano in ordineinvertito in S? no, perché in tal caso tj dovrebbe aver rilasciato la risorsa in questione prima della sua acquisizioneda parte di ti

16


31

Strict two-phase-locking

• We still need to remove the hypothesis of using a commit-projection

• To do so, turn to strict 2PL (by adding a constraint):The locks on a transaction can be released only after having carried out the commit/abort operations

• This version is used by commercial DBMSs; it eliminates the dirty read anomaly


32

CSR, VSR e 2PL

ScheduleSeriali

Schedule

ScheduleVSR Schedule

CSRSchedule2PL

17


33

Concurrency control based on timestamps

• Alternative mechanism based on timestamp: – an identifier that defines a total ordering of

temporal events within a system• Every transaction is assigned a timestamp ts that represents the

time at which the transaction begins• A schedule is accepted only if it reflects the serial ordering of the

transactions based on the value of the timestamp of each transaction


34

Basic timestamp mechanism

• Each scheduler has a counter RTM(x) and WTM(x) for each object• Each scheduler receives timestamped read and write requests

upon objects:– read(x,ts): if ts < WTM(x) then the request is rejected and the

transaction is killed, otherwise the request is accepted and RTM(x) is set equal to the greater of RTM(x) and ts

– write(x,ts): if ts < WTM(x) or ts < RTM(x) then the request is rejected and the transaction is killed, otherwise the request is accepted and WTM(x) is set equal to ts

Under assumption of commit-projection• The method causes the forced abort of a large number of

transactions• To remove the commit-projection assumption, must buffer writes

until commit, and this introduces waiting of transactions

18


35

Example of timestamp-based concurrency control

Request Response New value

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


36

Multiversion concurrency control

• Main idea: writes generate new copies, reads make access to the 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 only one 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 such that 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 by one) with WTMN(x) = ts

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

19


37

Comparison 2PL vs TS

• In 2PL the transactions are put in waiting. In TS they are killed and then restarted

• The serialization order in 2PL is imposed by conflicts, while inTS it is imposed by the timestamps

• The necessity of waiting for the commit of the transaction causes strict 2PL and buffering of writes in TS

• 2PL can give rise to deadlocks (discussed next)• Restarting costs more than waiting: 2PL wins!


38

CSR, VSR, 2PL e TS

Seriali

Tutti

VSR

CSR

2PL

TS

20


39

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


40

Hierarchical locking

• In many real systems locks can be specified at different granularity, 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

21


41

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


42

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

22


43

Deadlocks

• Created by concurrent transactions, each of which holds and waits for resources held by others

• Example: – 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)

– This is deadlock!• Deadlock probability grows linearly with number of transactions

and quadratically with the number of lock requests of each transaction (under suitable uniformity assumptions)


44

Deadlock resolution techniques

• A deadlock is a cycle in the wait-for graph which indicates wait conditions between transactions– (node=transaction, arc=wait condition).

• Three techniques:1. Timeout (problem: choice of timeout with trade-offs)2. Deadlock detection3. Deadlock prevention

• Deadlock detection: performs the search for cycles in a wait-for graph

• Deadlock prevention: kills the transactions that could cause a cycle (thus: it overkills)– Options for choosing the transaction to kill:

• via pre-emptive policies or non-pre-emptive policies

23


45

Isolation levels in SQL:1999 (and JDBC)

• Some transactions are defined as read-only (they can’t request exclusive locks)

• The level of isolation can be set for each transactions• read uncommitted permette dirty read, inconsistent read,

ghost update e phantom• read committed evita dirty read ma permette inconsistent

read, ghost update e phantom• repeatable read evita dirty read, inconsistent read e ghost

update ma permette phantom• serializable evita tutte le anomalie• Nota: update loss è sempre evitata


46

Livelli di isolamento: implementazione

• Sulle scritture si ha sempre il 2PL stretto (e quindi si evita la update loss)

• read uncommitted permettedirty read, inconsistent read, ghost update e phantom:– nessun lock in lettura (e non rispetta i lock altrui)

• read committed evita dirty read ma permette inconsistent read, ghost update e phantom:– lock in lettura (e rispetta quelli altrui), ma senza 2PL

• repeatable read evita dirty read, inconsistent read e ghost update ma permette phantom:– 2PL anche in lettura, con lock sui dati

• serializable evita tutte le anomalie:– 2PL con lock di predicato

24


47

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

25


49

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


50

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

26


51

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


52

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)

27


53

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


54

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) e si nota che uno dei dischi è sovraccarico

Possibili soluzioni• spezzare le transazioni con gli inserimenti• riorganizzare i file, in modo che gli inserimenti si ripartiscano su

tutti i dischi

28


55

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 all'SQL)


56

Caso 9

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

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

29


57

Caso 10

• Una società di servizi emette tutte le bollette a fine mese, conun 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)

Gestione delle transazioni: controllo di concorrenza...

Documents

Transcript of Gestione delle transazioni: controllo di concorrenza...