Transazioni e Concorrenza

Un database è un modello della realtà, e lo schema definisce i vincoli di integrità che ogni stato deve rispettare. Quando la realtà cambia, il modello deve cambiare di conseguenza: lo fa una transazione, cioè un programma che porta la base di dati da uno stato consistente a un altro stato consistente.

Finché le transazioni si eseguono una per volta non ci sono problemi. Ma eseguirle in sequenza sprecherebbe le risorse del sistema: i DBMS le eseguono in parallelo, e allora servono meccanismi che diano a ciascun utente l'illusione di essere solo. Questo modulo studia quei meccanismi.

Transazioni

Le proprietà ACID

Operativamente, una transazione termina con un commit — il DBMS accetta gli effetti e li rende permanenti — oppure con un rollback, che annulla tutto quello che aveva fatto: dopo un rollback la base di dati deve trovarsi nello stato in cui sarebbe stata se la transazione non fosse mai partita.

Operazioni e notazione

Per studiare la concorrenza si astrae quasi tutto. La base di dati è un insieme di oggetti indivisibili x, y, z… e su ciascuno si possono fare solo due operazioni elementari, entrambe atomiche:

• r_i(x) — la transazione T_i legge l'oggetto x;
• w_i(x) — la transazione T_i scrive l'oggetto x.

A queste si aggiungono le operazioni di transazione: b_i (begin), c_i (commit), a_i (abort). Begin e commit di solito non si scrivono: si assumono presenti prima della prima e dopo l'ultima operazione.

---

Le anomalie della concorrenza

Senza controllo, l'intreccio delle operazioni di transazioni diverse produce quattro anomalie classiche. Vale la pena riconoscerle a colpo d'occhio, perché le definizioni formali che seguono servono proprio a escluderle.

Perdita di aggiornamento

Due transazioni incrementano lo stesso oggetto: T₁ = r₁(x)w₁(x) e T₂ = r₂(x)w₂(x), con x che vale 2. Eseguite in sequenza il risultato sarebbe 4. Ma se si intrecciano così:

T₂ legge x prima che T₁ scriva: entrambe leggono 2, entrambe scrivono 3. Un incremento è sparito. La base di dati resta in uno stato che nessuna esecuzione seriale avrebbe prodotto.

Lettura sporca

T₁ scrive x e poi fallisce; nel frattempo T₂ ha letto il valore intermedio:

Il rollback di T₁ cancella la scrittura, ma T₂ ha già portato fuori un dato che non è mai esistito ufficialmente. È l'anomalia che l'ipotesi di commit-proiezione mette da parte, ma che nei sistemi reali va gestita.

Letture inconsistenti

T₁ legge due volte lo stesso oggetto e nel mezzo T₂ lo modifica e conferma:

T₁ vede due valori diversi per lo stesso oggetto durante la propria esecuzione: la sua "fotografia" del database è incoerente.

Aggiornamenti fantasma

Il caso più insidioso, perché nessuna singola lettura è sbagliata. Siano y e z due oggetti legati dal vincolo y + z = 1000. T₂ sposta 100 da y a z (rispettando il vincolo), T₁ legge y prima e z dopo:

T₁ somma il vecchio y con il nuovo z e ottiene 1100: un totale che viola il vincolo pur essendo fatto di due valori entrambi "veri" in momenti diversi.

---

Schedule

Definizione

Uno schedule su un insieme di transazioni è una sequenza che contiene tutte le loro operazioni e che rispetta l'ordine interno di ciascuna transazione. È il modo formale di dire «una possibile esecuzione concorrente».

Date T₁ = r₁(x)w₁(x)w₁(y), T₂ = r₂(x)w₂(y), T₃ = r₃(x)w₃(x), uno schedule possibile è:

Schedule seriali e serializzabili

Uno schedule è seriale se le transazioni non si intrecciano affatto: tutte le operazioni di una prima di qualsiasi operazione dell'altra. Con n transazioni gli schedule seriali sono n! (con tre transazioni, sei).

Gli schedule seriali sono corretti per costruzione: se ogni transazione presa da sola mantiene la consistenza, eseguirle una dopo l'altra la mantiene. Ma sono lenti. Da qui la definizione che conta:

Il problema è che questa definizione non dice come verificarlo. Servono nozioni di equivalenza precise, ed è quello che fanno le due sezioni seguenti.

---

View-equivalenza

Legge-da e scritture finali

Due schedule equivalenti devono (1) lasciare la base di dati nello stesso stato e (2) far leggere alle transazioni gli stessi valori. Si formalizzano con due insiemi.

Scritture finali. Finali(S) contiene, per ogni oggetto, l'ultima scrittura su di esso: sono quelle che determinano lo stato finale.

Relazione legge-da. LeggeDa(S) contiene le coppie (w_i(x), r_j(x)) con i ≠ j tali che la scrittura precede la lettura e fra le due non c'è nessun'altra scrittura su x: dice quale valore ha effettivamente letto ciascuna lettura.

Esempio: in S = r₁(x) r₂(y) w₁(y) r₃(z) w₃(z) r₂(x) w₂(z) w₁(x) si ha Finali(S) = {w₁(x), w₁(y), w₂(z)}.

Schedule view-serializzabili (VSR)

Due schedule sono view-equivalenti se hanno le stesse operazioni, la stessa relazione legge-da e lo stesso insieme di scritture finali. Uno schedule è view-serializzabile se è view-equivalente a qualche schedule seriale.

---

Conflict-equivalenza

Operazioni in conflitto

Esistono quindi conflitti lettura-scrittura e scrittura-scrittura; due letture non sono mai in conflitto. Due schedule sono conflict-equivalenti se hanno le stesse operazioni e ogni coppia di operazioni in conflitto compare nello stesso ordine in entrambi. L'ordine conta: r₁(x)w₂(x) è diverso da w₂(x)r₁(x).

Grafo dei conflitti

Il grafo dei conflitti ha un nodo per ogni transazione e un arco T_i → T_j quando in S c'è un'operazione di T_i che precede ed è in conflitto con una di T_j. Vale il teorema che rende tutto praticabile:

Verificare l'aciclicità costa tempo lineare nel numero di nodi e archi, e un ordinamento topologico del grafo fornisce direttamente lo schedule seriale equivalente.

Verificatore di serializzabilità

Scrivi uno schedule e guarda i conflitti che genera: il verificatore costruisce gli archi, cerca i cicli e, se non ne trova, mostra l'ordine seriale equivalente. Notazione: r1(x), w2(y), c1, separate da spazi.

CSR e VSR a confronto

Vale CSR ⊂ VSR: ogni schedule conflict-serializzabile è anche view-serializzabile, ma non viceversa. Il controesempio classico è

che è view-equivalente al seriale r₁(x) w₁(x) w₂(x) w₃(x) — le letture leggono gli stessi valori e l'ultima scrittura è la stessa — ma ha i conflitti r₁(x)w₂(x) e w₂(x)w₁(x), che creano un ciclo fra T₁ e T₂. In pratica si preferisce la classe più piccola, perché è l'unica verificabile in fretta.

---

Locking e 2PL

Anche la conflict-serializzabilità non basta per costruire uno scheduler reale: il grafo dei conflitti si conosce solo a posteriori, mentre lo scheduler deve decidere operazione per operazione, in tempo reale. La soluzione adottata da tutti i DBMS commerciali è più pragmatica: i lock.

Lock condivisi ed esclusivi

Due lock sullo stesso oggetto, di transazioni diverse, sono in conflitto se almeno uno è esclusivo. Due letture convivono senza problemi; una scrittura esclude tutti.

La regola delle due fasi

Lo scheduler 2PL (two-phase locking) applica tre regole:

1. quando arriva un'operazione, se il lock necessario è in conflitto con uno già concesso, l'operazione viene bloccata e la transazione messa in attesa; altrimenti il lock viene assegnato e l'operazione eseguita;
2. un lock non può essere rilasciato prima che l'operazione corrispondente sia terminata;
3. una volta che una transazione ha rilasciato un lock, non può più acquisirne altri, per nessun oggetto.

La terza è la regola delle due fasi e dà il nome all'algoritmo: ogni transazione ha una fase crescente in cui accumula lock e una fase calante in cui li rilascia, senza tornare indietro.

Perché funziona. Siano T₁ = r₁(x)w₁(y) e T₂ = w₂(x)w₂(y) eseguite così: T₁ legge x e rilascia subito il lock, T₂ scrive x e y, poi T₁ scrive y. Ignorando i lock l'ordine è r₁(x) w₂(x) w₂(y) w₁(y), che ha un ciclo T₁→T₂→T₁: non è in CSR. Il colpevole è il rilascio anticipato di T₁, vietato dalla regola delle due fasi. Uno scheduler 2PL avrebbe messo T₂ in attesa, producendo l'esecuzione seriale T₁ T₂.

2PL stretto

Nella pratica si usa il 2PL stretto: tutti i lock di una transazione sono rilasciati insieme, al termine della transazione (commit o abort). Il motivo è pragmatico: per rilasciare un lock in anticipo lo scheduler dovrebbe sapere che la transazione non toccherà più quell'oggetto e che ha già preso tutti i lock che le serviranno — informazioni che ha con certezza solo alla fine. In più, così si evitano le letture sporche.

Deadlock

Il 2PL elimina le anomalie ma ne introduce una nuova: lo stallo. Due transazioni aspettano ciascuna un lock posseduto dall'altra:

Nessuna delle due può proseguire. Le due strategie standard:

---

Esercizi svolti

Verificare uno schedule

Ragionare sui lock