Proprietà ACID/Controllo di concorrenza

Il controllore di concorrenza è una componente fondamentale dei DBMS per l'esecuzione di transazioni in ambienti software affollati e con transazioni in concorrenza. Per motivi di efficienza il DBMS non può eseguire una transazione alla volta in modo seriale, si rende necessario (in particolare nelle architetture multiprocessore) eseguire le transazioni in modo non seriale, ma seriale equivalente, cioè con gli stessi effetti che avrebbero se fossero eseguite in modo seriale.

lezione Proprietà ACID/Controllo di concorrenza
	Tipo: lezione
	Materia: Basi di dati 2
	Avanzamento: lezione completa al 100%

Indichiamo con $r_{1}(x)$ un'operazione elementare di lettura sulla risorsa x da parte della transazione 1.

Indichiamo con $w_{3}(y)$ un'operazione elementare di scrittura sulla risorsa y da parte della transazione 3.

Anomalie di concorrenza

L'esecuzione in concorrenza può portare a diverse anomalie:

aggiornamento perso (lost update): avviene quando una transazione scrive dopo la lettura da parte di un'altra transazione e quest'ultima utilizzerà ancora il dato in questione. Per fare chiarezza:

r_{1}(x)\ r_{2}(x)\ w_{1}(x)\ w_{2}(x)

In questo caso la scrittura $w_{1}(x)$ è persa e non può avere effetto sulla base di dati perché sovrascritta da $w_{2}(x)$

lettura sporca (dirty read): è uno scenario in cui una transazione effettua una modifica a una risorsa e poi effettua rollback:

r_{1}(x)\ w_{1}(x)\ r_{2}(x)\ rollback_{1}\ w_{2}(x)

in questo esempio la transazione 2 ha letto un valore che è come se non fosse mai esistito nella base di dati (proprietà del comando rollback).

lettura non ripetibile (unrepeatable read): ad ogni transazione bisogna garantire di leggere lo stesso valore della stessa risorsa per tutta la sua durata. Esempio che viola questa condizione:

r_{1}(x)\ r_{2}(x)\ w_{2}(x)\ r_{1}(x)

aggiornamento fantasma (phantom update): questa anomalia porta il database (visto da una transazione) in uno stato inconsistente, cioè che viola delle condizioni logiche imposte.

Esempio: si immagini che in una base di dati le risorse x,y,z debbano rispettare la seguente condizione: $x+y+z=10$ . Prima dell'esecuzione delle transazioni ipotizziamo la base di dati consistente con i valori: $x=1,\ y=5,\ z=4$ . Siano eseguite ora le transazioni $t_{1}$ e $t_{2}$ nel seguente ordine:

r_{1}(x)\ r_{1}(y)\ r_{2}(x)\ r_{2}(z)\ w_{2}(x)\ w_{2}(z)\ r_{1}(z)

se l'esecuzione della transazione $t_{2}$ è (ad esempio) $x=x+2$ , $z=z-2$ (formalmente corretto a livello di consistenza) allora la transazione $t_{1}$ vedrà uno stato della base di dati inconsistente (per lei $x=1,\ y=5,\ z=2$ invece di $x=1,\ y=5,\ z=4$ ).

inserimento fantasma (phantom insert): questa anomalia si crea quando una transazione effettua delle operazioni con dati aggregati (come media, somma, ecc.) e durante la sua esecuzione un'altra transazione effettua una insert.

Definizioni

Prima di addentrarci nel controllo di concorrenza per evitare i problemi sopra citati, definiamo i seguenti termini:

schedule (o schedulazione, poco usato): sequenza di operazioni input/output appartenenti a transazioni eseguite in modo concorrente;
- schedule seriale: uno schedule in cui le azioni di ogni transazione sono eseguite in una sequenza contigua. Ad esempio:
  $r_{1}(x)\ r_{1}(y)\ w_{1}(x)\ r_{1}(z)\ w_{1}(y)\ r_{2}(z)\ w_{2}(z)\ r_{3}(y)\ w_{3}(z)\ r_{3}(y)\ w_{3}(x)$
- schedule serializzabile: uno schedule che produce gli stessi effetti sulla base di dati che avrebbe lo schedule seriale;

schedulatore: un componente che accetta o rifiuta le operazioni delle transazioni e decide in quale ordine dovranno essere eseguite È il componente che produce lo schedule.
legge-da: un'operazione $r_{i}(x)$ si dice legge-da un'operazione $w_{j}(x)$ se $w_{j}(x)$ precede $r_{i}(x)$ e non ci sono $w_{k}(x)$ tra le due;
scrittura finale: un'operazione $w_{i}(x)$ si dice in scrittura finale se è l'ultima scrittura sulla risorsa x.

Il compito dello schedulatore può non essere banale: mentre a posteriori di un commit è relativamente facile capire se uno schedule è corretto (secondo determinate politiche) o meno, lo schedulatore ha il compito di effettuare le decisioni real-time.

View-Serializzabilità

Due schedule si dicono view-equivalenti (indicato con $S_{1}\ \approx _{V}\ S_{2}$ ) se:

hanno le stesse operazioni;
ogni relazione legge-da del primo schedule, è anche una relazione nel secondo schedule;
ogni relazione scrittura-finale del primo schedule, è anche una relazione nel secondo schedule.

Uno schedule è detto view-serializzabile se è view-equivalente a uno schedule seriale. Indichiamo con $VSR$ la classe dei schedule view-serializzabili (quindi $S\in VSR$ )

Note di complessità:

decidere se due schedule dati sono view-equivalenti può essere fatto in tempo polinomiale;
decidere la view-serializzabilità di un generico schedule è un problema NP-Completo.

Conflict-Serializzabilità

Due azioni elementari di uno schedule $a_{i},a_{j}$ si dicono in conflitto se entrambe le operazioni agiscono sulla stessa risorsa (cioè dato) e almeno uno di loro è un'operazione di scrittura. Definiamo quindi due tipi di conflitto (con ovvio significato):

conflitto w-r o r-w
conflitto w-w

Due schedule si dicono conflict-equivalenti (indicato con $S_{1}\ \approx _{C}\ S_{2}$ ) se:

hanno le stesse operazioni;
hanno gli stessi tipi di conflitto ed essi compaiono nello stesso ordine.

Uno schedule $S$ è detto conflict-serializzabile se è conflict-equivalente a uno schedule seriale della stessa transizione. Indichiamo con $CSR$ la classe degli schedule conflict-serializzabili (quindi $S\in CSR$ ).

N.B.:

CSR\subset VSR

Test della conflict-serializzabilità

Per verificare se uno schedule appartiene o meno alla classe $CSR$ si può utilizzare il grafo dei conflitti costruito nel seguente modo:

si inserisce un nodo per ogni transazione presente
si inserisce un arco orientato tra i nodi $t_{i}$ e $t_{j}$ per ogni conflitto del tipo $a_{i},a_{j}$ solo se $a_{i}$ precede $a_{j}$ .

Si può dimostrare che è condizione necessaria e sufficiente che se il grafo è aciclico allora lo schedule appartiene alla classe $CSR$ .

Esempio 1

Si consideri il seguente schedule:

w_{0}(x)r_{2}(x)r_{1}(x)r_{0}(y)w_{2}(y)r_{0}(x)w_{1}(z)r_{2}(z)w_{2}(x)

E si indichi per ogni risorsa le operazioni effettuate:

$x:\ w_{0},r_{2},r_{1},r_{0},w_{2}$
$y:\ r_{0},w_{2}$
$z:\ w_{1},r_{2}$

Allora il grafo sarà:

che risulta aciclico, quindi lo schedule è conflict-serializzabile e quindi view-serializzabile.

Esempio 2

Si consideri il seguente schedule:

w_{0}(x)r_{2}(x)r_{1}(x)r_{0}(y)w_{2}(y)w_{3}(x)r_{0}(x)w_{1}(z)r_{2}(z)r_{3}(y)

E si indichi per ogni risorsa le operazioni effettuate:

$x:\ w_{0},r_{2},r_{1},w_{3},r_{0}$
$y:\ r_{0},w_{2},r_{3}$
$z:\ w_{1},r_{2}$

Allora il grafo sarà:

che risulta ciclico, quindi lo schedule non è conflict-serializzabile. Non è possibile stabilire con questo metodo se è o meno view-serializzabile.

Locking

È il metodo più comune utilizzato nei sistemi commerciali. Consiste nell'utilizzare i cosiddetti lock con un meccanismo simile alle mutex in programmazione.

L'idea di base è consiste in:

una transazione che vuole leggere un dato, deve far precedere all'operazione di read un r_lock o un w_lock e far seguire all'operazione un unlock della risorsa bloccata;
una transazione che vuole scrivere su un dato, deve far precedere all'operazione di write un w_lock e far seguire all'operazione un unlock della risorsa bloccata;

Una transazione che rispetta i requisiti sopra citati è detta ben lock-formata.La sequenza di lock-unlock dipende dal tipo di algoritmo utilizzato, alcuni spiegati in seguito.

I lock:

r_lock: lock condiviso di lettura, cioè una transazione può condividere il lock con altre transazioni;
w_lock: lock esclusivo di scrittura, nessun altro tipo di lock può coesistere sulla stessa risorsa.

Possiamo quindi affermare che un w_lock attivo su una risorsa garantisce alla transazione che ne ha il possesso, che nessuna altra transazione possa leggere o scrivere sulla risorsa bloccata. Invece un r_lock attivo su una risorsa, garantisce a tutte le transazioni che hanno acquisito il lock, che nessuna altra transazione possa scrivere sulla risorsa bloccata (mentre la lettura è libera).

Compatibilità tra lock
Tipo di lock	read-lock	write-lock
read-lock	compatibile	non compatibile
write-lock	non compatibile	non compatibile

Se una transazione tenta di acquisire un lock bloccato, rimarrà in attesa che il lock venga liberato.

Si definisce lock escalation un upgrade da un r_lock a un w_lock di una transazione che deve scrivere su un dato di cui ha acquisito il permesso di lettura.

Locking a due fasi (2PL)

Confronto tra il locking 2PL e il locking 2PL stretto (ideale)

Il locking a due fasi 2PL (2 Phase Locking) è un algoritmo di acquisizione dei lock che rispetta la seguente condizione:

"una transazione non può più acquisire lock se ne ha già rilasciato almeno uno"

La transazione è formata quindi da tre fasi:

fase crescente: la transazione acquisisce i lock di tutte le risorse necessarie;
fase stabile: la transazione non acquisisce nè rilascia lock. In questa fase effettua le operazioni necessarie sulle risorse;
fase calante: la transazione rilascia i lock acquisiti.

Si può dimostrare^[1] che qualsiasi schedule 2PL è view-serializzabile e conflict-serializzabile (condizione sufficiente ma non necessaria). Il locking 2PL (come le classi CSR e VSR) soffre però del problema della lettura sporca, per questo può essere migliorato con il locking a due fasi stretto.

Locking a due fasi stretto (STRICT2PL)

Il locking a due fasi stretto (STRICT2PL) è una modifica al 2PL che obbliga la transazione a rilasciare tutti i lock "contemporaneamente" (cioè senza ulteriori operazioni sulla base di dati tra un rilascio e l'altro) solo dopo aver effettuato COMMIT o ROLLBACK. In questo modo si ovvia al problema della lettura sporca, costringendo le transazioni ad attendere il termine (con successo o meno) della transazione che ha acquisito il lock. Questo è uno dei metodi più usati nei DBMS odierni.

Lo STRICT2PL presenta anch'esso però un problema: non può impedire l'anomalia dell'inserimento fantasma, infatti non abbiamo introdotto alcun lock relativo alle "nuove tuple" di una relazione.

Lock di predicati

Per ovviare ai problemi con le operazioni INSERT e UPDATE, in particolare l'inserimento fantasma, si utilizzano le tecniche dei predicate locks. Questi lock bloccano le tuple interessate (o l'intera relazione) in modo che nessuna transazione possa causare problemi con questi dati.

Non vengono molto utilizzati nei DBMS commerciali^[2], in quanto si preferisce adottare una tecnica gerarchica.

Lock gerarchico

Nei DBMS reali a differenza dei lock visti fino ad ora, non sempre si vuole o si può effettuare il lock su una risorsa generica indipendentemente dalla tipologia della stessa (tupla, relazione, ecc.). Si introducono quindi i cosiddetti lock gerarchici (o Multiple granularity locking), dove è possibile gestire i lock a livelli. Possiamo immaginare il dabatase relazionale come un albero la cui radice è il DB stesso, il primo livello sono le relazioni (cioè tabelle), il secondo le tuple, ecc. L'idea è che effettuando un lock su un elemento dell'albero, il lock viene esteso a tutti i suoi figli ricorsivamente.

La possibilità di specificare questo tipo di lock è detta granularità dei lock e consente di eseguire azioni su quantità di dati piccole e quantità di dati grandi, bloccando solamente le risorse effettivamente utilizzate.

Questa tecnica prevede altri 3 tipi di locking in aggiunta al lock di lettura (chiamato SL Shared Lock) e al lock di scrittura (chiamato XL Exclusive Lock):

ISL Intentional Shared Lock: indica l'intenzione di bloccare in modo condiviso uno dei nodi figlio del corrente;
IXL Intentional Exclusive Lock: indica l'intenzione di bloccare in modo esclusivo uno dei nodi figlio del corrente;
SIXL Shared Intentional Exclusive Lock: blocca il nodo corrente in modo condiviso e indica l'intenzione di bloccare in modo esclusivo uno dei nodi figlio del corrente.

Rispetto al 2PL si introducono ora i seguenti limiti:

Una transazione che vuole bloccare in modo condiviso (SL o ISL) un generico nodo $n_{i}$ deve prima possedere ISL o IXL di ${\text{parent}}(n_{i})$ .
Una transazione che vuole bloccare in modo esclusivo (XL o IXL o SIXL) un generico nodo $n_{i}$ deve prima possedere IXL o SIXL di ${\text{parent}}(n_{i})$ .

Questi limiti non si applicano al nodo radice e ai nodi gia' bloccati: se ${\text{parent}}(n_{i})$ è bloccato da SL o XL anche tutti i suoi figli (e quindi anche $n_{i}$ ) saranno bloccati con la stessa modalità.

Per chiarire il procedimento si osservi la tabella di acquisizione del lock:

Tabella di acquisizione
Richiesta\Stato	SL	XL	ISL	IXL	SIXL
SL	compatibile	non compatibile	compatibile	non compatibile	non compatibile
XL	non compatibile	non compatibile	non compatibile	non compatibile	non compatibile
ISL	compatibile	non compatibile	compatibile	compatibile	compatibile
IXL	non compatibile	non compatibile	compatibile	compatibile	non compatibile
SIXL	non compatibile	non compatibile	compatibile	non compatibile	non compatibile

In questo modo partendo dalla radice è possibile bloccare tramite ISL o IXL o SIXL i vari nodi fino ad arrivare alla granularità richiesta (che si noti viene fornita dal progettista della transazione e non dal sistema) e bloccare con richieste XL o SL i dati richiesti.

Problemi

Il problema principale dei sistemi a locking è dato dal deadlock. Il deadlock è facilmente trovabile avendo il grafo "wait-for" che rappresenta quale transazione sta attendendo l'altra. Purtroppo questo grafo non può essere disponibile in tempo reale dallo schedulatore (per via dei problemi distribuiti) che quindi dovrà adottare altre tecniche di prevenzione o risoluzione.

Alcuni meccanismi di prevenzione di un deadlock sono:

restrizione delle risorse: ogni transazione può richiedere tutte le risorse solo in una volta adottando un approccio atomico nell'acquisizione dei lock;
identificatore incrementale: ad ogni transazione è associato un id incrementale. Ogni transazione che vuole attendere un lock lo può fare solo se l'id della transazione che ha il lock ha un id minore, altrimenti viene uccisa.

Alcuni meccanismi di riconoscimento e risoluzione di un deadlock sono:

timeout: il più semplice, ogni transazione ha un tempo massimo di esecuzione, superato il quale viene uccisa;
algoritmo di Obermark: un algoritmo per trovare il grafo "wait-for" in ambiente distribuito e quindi scoprire la presenza di cicli.

Update lock

Per ridurre la probabilità di deadlock si introduce un lock chiamato Update Lock UL, in cui si impedisce a una transazione che possiede SL di fare lock escalation per portarsi a XL. UL lavora come stato sostitutivo a SL indicando che la transazione ha intenzione di trasformarsi in XL successivamente.

Compatibilità tra lock con UL
Tipo di lock	RL	UL	WL
RL	compatibile	compatibile	non compatibile
UL	compatibile	non compatibile	non compatibile
WL	non compatibile	non compatibile	non compatibile

Metodi a timestamp

I metodi a timestamp sono alternative al lock 2PL, più semplici da implementare ma meno efficienti. Ogni transazione possiede un timestamp cioè un identificativo della data/ora di inizio. Si accettano gli schedule solo se l'ordine di esecuzione delle transizioni rispecchia l'ordine dei timestamp.

Ad ogni risorsa vengono assegnarti due contatori: WTM(x) e RTM(x). Il primo rappresenta il timestamp in cui l'oggetto è stato scritto l'ultima volta, il secondo il timestamp della transazione più grande che ha letto l'oggetto l'ultima volta.

Sia $t_{r}$ il tempo in cui arriva una richiesta di lettura e $t_{w}$ il tempo in cui arriva una richiesta di scrittura. Lo scheduler ragiona nel seguente modo:

READ: se $t_{r}<WTM(x)$ un ABORT viene eseguito sulla transazione che ha effettuato la lettura;
WRITE: se $t_{w}<WTM(x){\text{ or }}t_{w}<RTM(x)$ un ABORT viene eseguito sulla transazione che ha effettuato la scrittura;
negli altri casi la richiesta viene accettata ed eventualmente aggiornati i contatori.

Questo garantisce che una transazione non possa leggere/scrivere su dati gia' letti o scritti da altre transazioni con timestamp superiore. Il problema di metodi a timestamp è l'elevato numero di kill che lo schedulatore deve fare rispetto ad altri come 2PL, però si guadagna in semplicità dell'implementazione.

Gli schedule TS possono essere anche 2PL ma non necessariamente.

Metodi a timestamp multipli

I metodi a timestamp multipli (TS-multi) consistono nel creare più versioni dei dati su cui operano in contemporanea delle transazioni. Questo metodo riduce il numero di kill effettuati, garantendo sempre che le operazioni di read vengano eseguite e mai uccise^[3].

A differenza dei TS-Mono, le condizioni di approvazione dello schedule segue le seguenti regole:

READ: sempre consentita;
WRITE: se $t_{w}<RTM(x)$ un ABORT viene eseguito sulla transazione che ha effettuato la scrittura;
negli altri casi la richiesta viene accettata ed eventualmente aggiornati i contatori. Nel caso della scrittura una nuova versione della risorsa viene creata.

Riepilogo tassonomia delle classi

Note

↑ Transaction Management - Concurrency Control - Bin Zhou - Simon Fraser University
↑ Transactions and Isolation Levels 2 - Alan Fekete - University of Sidney
↑ Si noti che una transazione può sempre suicidarsi dando rollback.

Collegamenti esterni

(IT) Serializzabilità di Schedule Università di Crema.

[1] Transaction Management - Concurrency Control - Bin Zhou - Simon Fraser University

[2] Transactions and Isolation Levels 2 - Alan Fekete - University of Sidney

[3] Si noti che una transazione può sempre suicidarsi dando rollback.

[1]

[2]

[3]