07 gestione concorrenza pratica - CNR
Transcript of 07 gestione concorrenza pratica - CNR
La gestione della concorrenza in pratica
Basi di dati: Architetture e linee di evoluzione -Seconda edizioneCapitolo 2
Appunti dalle lezioni
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 2
Soluzioni possibili
� Uno scheduling è considerato corretto se èequivalente a UNO dei possibili schedulingsequenziali
� Soluzioni disponibili in partica:– Protocollo 2 phase locking (2PL)– Tecnica basata sui timestamps– Tecniche multi-versione– Tecniche ottimistiche
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 3
Lock
� Dato– Un oggetto della base dati
� L’intera base dati, una tabella, una riga, un attributo
� Lock– Una variabile associata ad un dato che ne descrive
lo stato con riferimento alle varie operazioni che ad esso possono essere applicate.
� Lock binari– Due stati: locked/unlocked– Troppo restrittivo
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 4
Lock
� Shared/Exclusive lock:– Permettere a più transazioni di accedere allo stesso
dato per scopi di sola lettura– Se una transazione deve modificare un dato, allora
deve averne il controllo esclusivo
� Primitive:– r_lock– w_lock– unlock.
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 5
La gestione dei lock
� I lock garantiscono che sui dati si operi in maniera mutuamente esclusiva.
� Non garantiscono in alcun modo la serializzabilità.
Richiesta
Stato
errorOK / freeOK / dipendeUnlock
OK / w_lockedNO / w_lockedNO/ r_lockedW_lock
OK / r_lockedNO / W_lockedOK / r_lockedR_lock
FreeW_lockedR_locked
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 6
Esempio: Perdita di Update
T1 T2BoTRL(x)/r(x)/UL(x)x = x+1
BoTRL(x)/r(x)/UL(x)x = x+1WL(x)/w(x)/UL(x)commitEoT
WL(x)/w(x)/UL(x)commitEoT
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 7
Il protocollo 2PL
� Lo scheduler diventa un lock manager che riceve richieste di lock e decide il da farsi.
� Transazione ben formata rispetto al locking:– ogni operazioni di lettura è preceduta da un r_lock e
seguita da un unlock;– ogni operazioni di scrittura è preceduta da un w_lock
e seguita da un unlock;– proprietà garantita di compilatori.
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 8
Il protocollo 2PL
� Una transazione, dopo aver rilasciato un lock, non può acquisirne altri.
� In una transazione esiste– La fase crescente
� i lock vengono acquisiti
– la fase calante� i lock vengono rilasciati.
� E’ concesso l’incremento di lock.
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 9
2PL ⊂⊂⊂⊂ CSR
� Se S ∈ 2PL ⇒ S ∈ CSR� Per assurdo:
– Sia S: ∈ 2PL e ∉ CSR– S ∉ CSR ⇒ nel grafo dei conflitti esiste un ciclo
T1,T2,…,TN– Esiste una risorsa x su cui opera prima T1 e poi T2
� T1 rilascia il lock su x affinché T2 possa procedere
– Esiste una risorsa y su cui opera prima Tn e poi T1� Tn rilascia un lock che è acquisito da T1
– ⇒ T1 non si comporta secondo il 2PL
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 10
2PL ≠ CSR
� S: r1(x) w1(x) r2(x)w2(x)r3(y)w1(y)– S ∉ 2PL– S ∈ CSR
T1
T3
T2
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 11
CSR, VSR e 2PL
VSR
CSR
2PL
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 12
Esempio: Perdita di Update
T1 T2BoTWL(x)/r(x) x = x+1
BoTWL(x)
w(x)/UL(x)
r(x)x = x+1w(x)/UL(x)CommitEoT
CommitEoT
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 13
T1 T2BoTWL(x)/r(x)x=x+1w(x)/Unlock(x)
BoTWL(x)/r(x)x=x+1w(x)/Unlock(x)commitEoT
abortEoT
Letture Sporche non risolte
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 14
2PL stretto
� Il problema è legato all’ipotesi di Commit Proiezione che è alla base della teoria della concorrenza.
� Nei sistemi reali tale ipotesi deve, per forza di cose, essere abbandonata.
� 2PL stretto:– al 2PL si aggiunge l’ulteriore condizione che le
risorse possono essere rilasciate solo dopo il commit/abort.
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 15
Deadlock
� Il meccanismo dei lock introduce un problema:– siano T1 e T2 due transazioni;– supponiamo che entrambe operino in scrittura su 2 oggetti x e
y;
� T1 blocca x in scrittura;� T2 blocca y in scrittura;� T1 aspetta che T2 liberi y;� T2 aspetta che T1 liberi x.� La situazione può durare all’infinito.
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 16
Deadlock: Prevention
� Tecnica di prevenzione esatta:– le transazione acquisiscono le risorse di cui hanno bisogno in
un colpo solo;– se qualche risorsa non è disponibile, non viene assegnata
nessuna risorsa.
� Problemi:– non sempre una transazione sa in partenza ciò di cui avrà
bisogno;
– si rischia di bloccare troppi oggetti inutilmente.
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 17
Deadlock: Prevention
� Tecnica approssimata:– tutte le transazioni richiedono i lock nello stesso ordine;– non sempre la transazione conosce tutto quello di cui avrà
bisogno;
� Tecnica approssimata:– ad ogni transazione è associato un timestamp;
– se un lock non è concesso, la transazione aspetta solo se essa è più giovane della transazione che detiene il lock;
– i deadlock sono eliminati ma possiamo avere starvation� Una transazione viene continuamente uccisa
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 18
Deadlock: Detection
� Non si pongono vincoli alle transazioni.
� Ad intervalli prefissati il contenuto della tabella dei lock è esaminato e comparato con le richieste pendenti.
� Si costruisce un grafo delle richieste.
� Se in tale grafico esiste un ciclo, c’è un deadlock.
� Il ciclo deve essere spezzato uccidendo almeno una transazione.
T1
T6
T3
T5
T7
T2
T8
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 19
Deadlock: Time-Out
� E’ la tecnica più semplice e più usata.� Ad richiesta di lock è associato un tempo
massimo di attesa.� Scaduto tale tempo, la richiesta si intende
rifiutata e la transazione uccisa.
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 20
Granularità dei lock
� I lock entrano in tutti i metodi.� E’ importante gestirli in maniera
efficiente.� Cosa blocco?
– Attributo � Granularità fine– ……– Base Dati � Granularità grossa
� La granularità ottimale dipende dalla transazione che sto eseguendo
� Un DBMS supporta diverse granularità e la possibilità di scegliere (in maniera più o meno trasparente all’utente) cosa bloccare
BD
Table n
Blocco 1
Table 1
Blocco n
…..
Tupla 1 Tupla n
…..
…..
Attributo 1 Attributo n…..
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 21
Lock gerarchici
� IS (Intention Shared)– Saranno richiesti uno o più lock condivisi su qualche nodo
discendente
� IX (Intention Exclusive)– Saranno chiesti uno o più lock esclusivi su qualche nodo
discendente
� SIX (Shared Intension Exclusive)– Si richiede il blocco del nodo corrente in maniera condivisa e si
annuncia che qualche nodo discendente sarà bloccato in maniera esclusiva
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 22
Lock gerarchici
NoNoNoNoNoX
NoNoNoNoOKSIX
NoNoOKNoOKS
NoNoNoOKOKIX
NoOKOKOKOKIS
XSIXSIXISRichiesta
Stato
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 23
2PL a granularità multipla
� Si parte sempre dalla radice dell’albero� Un nodo N può essere bloccato in modalità S o
IS solo se il padre è bloccato in modalità IS o IX� Un nodo N può essere bloccato in modalità X o
IX solo se il padre è bloccato in modalità IX o SIX
� Una transazione può bloccare un nodo solo se non ne ha sbloccato altri
� Una transazione T può sbloccare un nodo N solo se T non blocca nessuno dei figli di N
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 24
Timestamps
� Timestamp– Identificatore numerico assegnato dal DBMS ad ogni
transazione
– TS(T1)<TS(T2) ⇒� T1 è iniziata prima di T2
� Idea base del Timestamp Ordering– Ordinare le transazioni in base ai loro timestamps
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 25
Basic Timestamp ordering
� Ad ogni oggetto X del DB vengono associati– Read_TS
� Valore del TS della transazione più giovane (TS più elevato) tra le transazioni che hanno letto X
– Write_TS� Valore del TS della transazione più giovane (TS più elevato)
tra le transazioni che hanno modificato X
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 26
Basic Timestamp ordering
� La transazione T con timestamp TS chiede di leggere X– Se Write_TS(X) > TS
� T vuole leggere qualcosa scritto da una transazione più giovane� La transazione viene annullata e risottomessa al sistema con un
nuovo timestamp
– Altrimenti� L’operazione di scrittura viene concessa� Read_TS(X) = max {Read_TS(X) ,TS}
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 27
Basic Timestamp ordering
� La transazione T con timestamp TS chiede di scrivere X– Se Read_TS(X) > TS
� Il dato è stato già letto da una transazione più giovane� La transazione viene annullata e risottomessa al sistema con un
nuovo timestamp– Se Write_TS(X) > TS
� Il dato è stato già scritto da una transazione più giovane� La transazione viene annullata e risottomessa al sistema con un
nuovo timestamp– Altrimenti
� L’operazione di scrittura viene concessa� Write_TS(X) = TS
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 28
TS: Esempio
� RTS(x)=UNDEFINED,WTS=UNDEFINED� write(x,4)
– (ok, RTS(x)=UNDEFINED WTS(x)=4) � read(x,7)
– (ok, RTS(x)=7,WTS(x)=4)� read(x,6)
– (ok, RTS(x)=7 WTS(x)=4)� read(x,8)
– (ok, RTS(x)=8 WTS(x)=4) � read(x,9)
– (ok, RTS(x) = 9 WTS(x)=4) � write(x,8)
– (no ⇒ t8 uccisa)� write(x,11)
– (ok, RTS(x) = 9 WTS(x)=11)� read(x,10)
– no ⇒ t10 uccisa
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 29
TS e CSR
� Uno schedule in TS ha conflitti tra Ti e Tj se e solo se i < j– ⇒ il grafo dei conflitti è aciclico– S ∈ TS ⇒ S ∈ CSR
� S: r1(x) w1(x) r2(x)w2(x)r3(y)w1(y)– S ∉ TS– S ∈ CSR
T1
T3
T2
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 30
CSR, VSR e TS
VSR
CSR
TS
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 31
TS e 2PL
� S1: r1(x) w1(x) r2(x) w2(x) r0(y) w1(y)– S1 in TS ma non in 2PL
� S2: r2(x) w2(x)r1(x) w1(x)– S2 in 2PL ma non in TS
� S3: r1(x) r2(y) w2(y) w1(x) r2(x) w2(x)– S3: in TS e in 2PL
� Possiamo solo dire– TS e 2PL hanno una intersezione non nulla
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 32
CSR, VSR, 2PL e TS
Tutti
VSR
CSR
2PLTS
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 33
Strict Timestamp ordering
� La versione basic dell’algoritmo non ci tutela dai rollback a cascata
� Versione “Strict”– L’operazione di lettura o scrittura di T su X viene
ritardata fino a che l’ultima transazione T1 che ha scritto X non è terminata (con un commit o con un abort)
� Tale meccanismo è implementato tramite lock– Non si generano deadlock in quanto T attende
solamente sseTS(T) > TS(T1)
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 34
Tecniche multi-versione (MVCC)
� Ogni volta che un oggetto X viene aggiornato, si tiene traccia anche del suo vecchio valore.
� X ⇔ {X1,X2,… Xn}
� Idea base:� Alcune operazioni di lettura rifiutate, ad esempio con una
tecnica timestamp, potrebbero essere accettate leggendo una versione più vecchia.
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 35
MVCC basato su 2PL
� Il meccanismo di base è lo strict 2PL– Qui, se una transazione ha il WL su un oggetto, le
altre non possono né leggerlo né scriverlo.
� Idea:– Manteniamo, per ogni oggetto X, due versioni
� X1: versione scritta da una transazione che ha eseguito il commit (versione committed)
� X2: create nel momento in cui una transazione T acquisisce il lock in scrittura
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 36
MVCC basato su 2PL
� Mentre T detiene il lock in scrittura– Le altre che vogliono leggere X leggono la versione
committed X1
� Quando T vuole fare il commit deve ottenere un certify lock su ogni elemento su cui ha un WL.– E’ un lock esclusivo
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 37
MVCC basato su timestamps
� X ⇔ {X1,X2,… Xn}� Alla generica copia Xi
– Read_TS(Xi)� TS della transazione più giovane che lo ha letto
– Write_TS(Xi)� TS della transazione che lo ha scritto
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 38
MVCC basato su timestamps
� T richiede di leggere X– Il valore letto è l’ Xi tale che
� Il suo Write_TS(Xi) è il più grande che sia anche minore o uguale di TS(T)
– La richiesta è sempre accettata
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 39
MVCC basato su timestamps
� T richiede di scrivere X– Sia Xi :
� Il suo Write_TS(Xi) è il più grande che sia anche minore o uguale di TS(T)
– Se TS(T) < Read_TS(Xi)� Abort di T
– Altrimenti� Crea una nuova copia di X (Xn+1) � Read_TS(Xn+1) = Write_TS(Xn+1) = TS(T)
� Ancora una volta si presenta il problema dei rollback a catena per cui bisogna prevedere meccanismi di ritardo.
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 40
Tecniche ottimistiche
� Tecniche di validazione o certificazione.� Non si attua alcun controllo durante la
transazione. � Particolarmente efficaci per:
– Transazioni con basso livello di interferenza.– Molte transazioni che leggono soltanto.
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 41
Tecniche ottimistiche
� Fase di lettura:– Si leggono valori committed e le modifiche vengono applicate a
copie locali.
� Se la transazione chiede il commit:– Fase di validazione:
� Ci si assicura che applicare le modifiche non violi la serializzabilità.– Fase di scrittura:
� Se la validazione è superata, le modifiche vengono riportate alla base dati.
� Altrimenti le modifiche sono scartate e la transazione è riavviata.
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 42
Fase di validazione: esempio
� Ad ogni transazione viene associato un timestamp.
� Per ogni transazione si mantiene anche:– L’istante di inizio e di fine delle tre fasi.– Il write-set
� L’elenco degli oggetti che essa vuole scrivere o ha scritto
– Il read-set� L’elenco degli oggetti che essa legge
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 43
Cioè ….
Read
Modifiche su copie Locali
t
Validazione
Write
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 44
Fase di validazione di T
� Sia TC l’insieme delle transazioni che– Ha effettuato il commit
� E’ in fase di validazione
� Entra in validazione– TC = TC ∪ T– T viene confrontata con ogni Tj ∈ TC:
� T ≠Tj
� Passare la fase di validazione significa passare la validazione nei confronti di ogni Tj
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 45
Fase di validazione di T verso T j
� La validazione di T verso Tj è passata se:– Tj completa la sua fase di scrittura prima che T inizi la sua
fase di lettura– Se Tj completa la sua fase di scrittura prima che T inizi la sua
fase di scrittura � WS(Tj) ∩ RS(T) = ∅
– Se Tj completa la sua fase di lettura prima che T completi la sua fase di lettura
– WS(Tj) ∩ RS(T) = WS(Tj) ∩ WS(T) = ∅
� Altrimenti– T viene uccisa e riavviata.
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 46
Livello di isolamento delle Transazioni
� Il livello di isolamento di una transazione determina il comportamento della stessa.
– Io posso decidere di accettare alcune anomalie per andare piùveloce
� Uncommitted Read� Committed Read� Repeatable Read� Serializable� Sono da intendersi come requisiti al negativo
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 47
Uncommitted Read
� La transazione accetta di leggere dati modificati da una transazione che non ha ancora fatto il commit
� Se usiamo il 2PL:– Ignora i lock esclusivi in lettura– Non acquisisce i lock in lettura.– Deve però acquisire i lock in scrittura
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 48
Committed Read
� La transazione non legge dati cambiati da una transazione che non ha ancora fatto il commit.
� Se però essa legge due volte lo stesso dato, può trovare dati diversi.– Non blocca i dati che legge
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 49
Repeatable Read
� Si aggiunge al commited read la caratteristica che, se un dato è letto due volte, si avrà sempre lo stesso risultato.
– Si applica il 2PL stretto
� Le righe realmente lette non possono essere modificate o cancellate.
� Possono però essere aggiunte righe anche nell’intervallo specificato nella clausola where della transazione che legge.
� Tutti i dati letti sono read_locked;� Un insert non interferisce con questi lock
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 50
Serializable
� Si aggiunge al repeatable read la caratteristica che, se una query è fatta due volte, non vengono aggiunte righe.
� Non sono possibili modifiche neanche all’interno dell’intervallo coperto nella lettura.
� Il SERIALIZABLE blocca cioè intervalli di dati, inclusi quelli di fatto non esistono, impedendo cioè che vengano effettuati insert.
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 51
Gestione della concorrenza in PostgreSQL 9.0
� Capitolo 13 del manuale– Data consistency is maintained by using a multi-version model.
– This means that while querying a database each transaction sees a snapshot of data (a database version) as it was some time ago, regardless of the current state of the underlying data.
– This protects the transaction from viewing inconsistent data that could be caused by (other) concurrent transaction updates on the same data rows, providing transaction isolation for each database session.
– MVCC, by eschewing explicit locking methodologies of traditionaldatabase systems, minimizes lock contention in order to allow for reasonable performance in multiuser environments.
– The main advantage of using the MVCC rather than locking is that in MVCC locks acquired for reading data do not conflict with locks acquired for writing data, and so reading never blocks writing and writing never blocks reading.
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 52
Isolation Levels in PostgreSQL 9.0
� You can request any of the four standard transaction isolation levels.
� Internally, there are only two distinct isolation levels, which correspond to the levels Read Committed and Serializable.
– When you select the level Read Uncommitted you really get Read Committed
– When you select Repeatable Read you really get Serializable, so the actual isolation level might be stricter than what you select.
� This is permitted by the SQL standard: – the four isolation levels only define which phenomena must not
happen, they do not define which phenomena must happen.– The reason that PostgreSQL only provides two isolation levels is that
this is the only sensible way to map the standard isolation levels to the multiversion concurrency control architecture.
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 53
Isolation Levels in PostgreSQL 9.0
� Read Committed is the default isolation level in PostgreSQL
� start transaction isolation level read uncommitted;� start transaction isolation level read committed;� start transaction isolation level read committed;� start transaction isolation level read committed;� set transaction isolation level read uncommitted;� set transaction isolation level read committed;� set transaction isolation level read committed;� set transaction isolation level read committed;
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 54
Locks in PostgreSQL 9.0
� Table- and row-level locking facilities are also available in PostgreSQL for applications that cannot adapt easily to MVCC behavior.
� However, proper use of MVCC will generally provide better performance than locks.
� In addition, application-defined advisory locks provide a mechanism for acquiring locks that are not tied to a single transaction.
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 55
Locks in PostgreSQL 9.0
� Locks a livello di tabella– LOCK [ TABLE ] [ ONLY ] name [, ...] [ IN lockmode MODE ] [
NOWAIT ]– lockmode:
� ACCESS SHARE | ROW SHARE | ROW EXCLUSIVE | SHARE UPDATE EXCLUSIVE| SHARE | SHARE ROW EXCLUSIVE | EXCLUSIVE | ACCESS EXCLUSIVE
� ACCESS SHARE� ACCESS EXCLUSIVE� Non esiste l’Unlock!
Basi di Dati 2 – Prof. Antonio d’Acierno Isolation: pratica 56
Locks in PostgreSQL 9.0
� Locks a livello di riga– SELECT FOR SHARE …..– SELECT FOR UPDATE ….
� Non esiste l’Unlock!