Appunti di Gestione dell'Informazione

Introduzione

Le operazioni di base di un database sono:

• Read_item(X) – operazione di lettura.
  • Trova l’indirizzo del blocco disco che contiene il dato X;
  • Trasferisce (get) il blocco in un buffer in memoria principale (se non è già presente);
  • Copia il dato X nella corrispondente variabile X.
• Write_item(X) – operazione di scrittura
  • Trova l’indirizzo del blocco disco che contiene il dato X;
  • Trasferisce (get) il blocco in un buffer in memoria principale (se non è già presente);
  • Copia il dato X nella corrispondente variabile X;
  • Trasferisce (put) il dato X aggiornato dal buffer nel disco (immediatamente o in qualche momento successivo).

Problemi legati all'accesso concorrente al database

I problemi legati all’accesso concorrente al DB sono di quattro tipi:

• Lost Update (perdita di aggiornamento) – si verifica quando due client che accedono agli stessi dati hanno le loro operazioni eseguite in modo tale che il valore finale di qualche dato risulta errato.
• Dirty read (lettura sporca) – si verifica quando un client C1 aggiorna un dato X e successivamente fallisce, mentre il dato X (temporaneamente) aggiornato da C1 viene letto da un altro client C2 prima che X venga riportato al suo valore originale precedente alla modifica effettuata da C1.
• Incorrect Summary (aggiornamento fantasma) – se un client calcola una funzione aggregata su un insieme di dati su cui esiste un vincolo di integrità mentre un altro client effettua un aggiornamento su alcuni di questi dati, il primo client può calcolare la funzione aggregata considerando alcuni dati prima dell’aggiornamento e alcuni dati dopo l’aggiornamento.
• Unrepeatable read – se un client effettua solamente letture consecutive dello stesso dato e un altro client modifica questo dato nel frattempo, il primo client può leggere valori diversi del dato in letture successive. Invece è bene che un client che effettua letture consecutive dello stesso dato recuperi lo stesso valore dal database, senza risentire degli effetti di altre esecuzioni.

Transazioni

Rappresenta il meccanismo utilizzato per gestire tutte le problematiche di gestione della concorrenza e di resistenza ai guasti. Una transazione è una sequenza di una o più operazioni SQL trattate come un’unità di esecuzione:

• Le transazioni appaiono eseguite in isolamento;
• Se si verificano guasti, le modifiche di ogni transazione sono applicate tutte oppure non sono applicate affatto.

Le operazioni che costituiscono la transazione sono racchiuse fra i comandi START TRANSACTION e END TRANSACTION. Indica la conclusione positiva della transazione COMMIT [WORK] e quindi tutte le modifiche devono essere trascritte nel DB. Indica l’annullamento della transazione e ROLLBACK [WORK] delle sue modifiche (se ad esempio si sono verificate specifiche condizioni).

In ambiente multiutente ogni client esegue sequenze di operazioni SQL considerate come transazioni. Le transazioni devono rispettare le quattro proprietà ACID:

1. Atomicity – se si verifica un crash durante l’esecuzione di una transazione prima del COMMIT, gli effetti parziali della transazione non sono memorizzati nel DB. Sono implementate tecniche di logging per tenere traccia delle azioni eseguite. Quando il sistema riparte c’è un processo che garantisce che tutte le modifiche effettuate da transazioni che erano in esecuzione al momento del crash siano disfatte (UNDO). La cancellazione delle modifiche parziali di una transazione è un processo denominato anche rollback (o abort). Il rollback può essere eseguito dal sistema (in caso di guasti) o essere invocato dal client.
2. Consistency – ogni client in ogni transazione può assumere di lavorare su un DB dove sono verificati tutti i vincoli di integrità, e deve lasciare un DB che soddisfi tutti i vincoli di integrità. Quando il sistema rileva che la transazione sta violando un vincolo, il sistema interviene per annullare la transazione o per correggere la violazione del vincolo. La verifica dei vincoli può avvenire in due modi:
   • Immediate, durante l’esecuzione della transazione si rimuovono gli effetti dell’istruzione che causa la violazione senza imporre un abort della transazione.
   • Deferred, al termine della transazione, dopo che è stato richiesto il commit. Se qualche vincolo viene violato, il commit non va a buon fine e viene eseguito il rollback della transazione.
3. Isolation – si può garantire alternanza nell’esecuzione dei comandi di transazioni diverse conservando uno stato del DB consistente. Le operazioni sono alternate in modo che l’esecuzione sia equivalente a qualche ordine sequenziale (seriale) delle transazioni (nozione di serializzabilità). Viene implementata tramite le tecniche di locking.
4. Durability – se si verifica un crash dopo che una transazione ha eseguito commit, gli effetti della transazione restano nel DB (non vengono persi). Quando il sistema riparte, le modifiche sono nel DB (tecniche di logging implementano questa proprietà).

Scopi di recovery

Per scopi di recovery, il sistema tiene traccia delle seguenti operazioni:

• begin_transaction: inizio della transazione;
• read or write: lettura/scrittura eseguite sui dati nel codice della transazione;
• end_transaction: tutte le operazioni di lettura/scrittura sono state eseguite e l’esecuzione della transazione si è conclusa;
• commit_transaction: indica il completamento con successo della transazione. Tutte le modifiche possono essere memorizzate correttamente nel DB e non saranno perse;
• rollback (or abort): indica che la transazione non ha completato con successo la sua esecuzione e gli eventuali effetti che può aver prodotto sul DB devono essere disfatti (UNDO).

Dopo aver terminato la sua esecuzione, una transazione passa nello stato partially committed, nel quale vengono effettuati ulteriori controlli per assicurare ad esempio che sia possibile memorizzare permanentemente le modifiche sul DB. Se il controllo è positivo, si passa allo stato committed, altrimenti viene annullata (failed). Una transazione committed significa che ha concluso la sua esecuzione con successo e tutte le sue modifiche sono state memorizzate in maniera permanente (non saranno perse neanche in caso di guasti).

Scheduling di transazioni

Uno schedule S è un set di transazioni T1, …, Tn definito come ordinamento delle operazioni delle transazioni, con il vincolo che l’ordine di esecuzione delle operazioni di ognuna delle T è mantenuto. Le operazioni di diverse T di uno schedule possono essere eseguite con interleaving.

Notazione di uno schedule:

Per caratterizzare la correttezza di uno schedule si utilizza la nozione di serializzabilità. Uno schedule S è detto seriale se, per ogni transazione T partecipante, tutte le operazioni di T sono eseguite consecutivamente nello schedule, altrimenti è detto non seriale. Uno schedule è seriale se non alterna le azioni di transazioni differenti. Se n è il numero di transazioni T, allora sono possibili n! schedule seriali diversi, i quali possono produrre stati finali differenti, ma sempre corretti.

Esempio:

Due schedule sono equivalenti quando l’effetto dell’esecuzione del primo è identico all’effetto del secondo. Uno schedule S è detto serializzabile se è equivalente a qualche degli n! possibili schedule seriali. Serializzabile non vuol dire seriale, poiché essere serializzabile implica che:

• Lo schedule sia corretto, ovvero deve lasciare il DB in uno stato consistente;
• Abbia interleaving appropriato, portando ad uno stato finale che potrebbe essere raggiunto anche eseguendo serialmente le transazioni.

Per capire se uno schedule è serializzabile devo avere una tecnica che mi permetta di valutare l’equivalenza tra questo ed uno seriale. Esistono tre tecniche:

1. Result equivalence – due schedule sono chiamati in questo modo se producono lo stesso stato finale del DB (ma è possibile che questo accada anche in casi accidentali!).
2. View equivalence – equivalenza basata sulla nozione di vista. Un’operazione di lettura R_i(X) legge da un’operazione di scrittura W_j(X) se quest’ultima precede R_i(X) e non vi sono altre operazioni di lettura W_k(X) tra esse. Due schedule sono chiamati view equivalent se sono rispettate le seguenti tre condizioni:
   • Lo stesso set di transazioni partecipa in S ed in S’, ed entrambi gli schedule includono le stesse operazioni di queste transazioni;
   • Per ogni operazione di lettura R_i(X) di T_i in S, se il valore di X letto è stato scritto da un’operazione di scrittura W_j(X) (o è il valore di partenza di X prima dell’inizio dello schedule) e la stessa condizione è mantenuta dalle operazioni R_i(X) di T_i in S’;
   • Se l’operazione W_k(Y) di T_k è l’ultima operazione di scrittura di Y in S, allora W_k(Y) di T_k è anche l’ultima operazione di scrittura di Y in S’.

   Determinare la view equivalenza di due schedule è un problema di complessità lineare. S e S’ sono view serializable se S è view equivalent a qualche schedule seriale, ovvero se hanno la stessa vista e la stessa ultima scrittura. Determinare se uno schedule è view equivalent ad uno schedule seriale è un problema NP-hard.

3. Conflict equivalence – tecnica basata sul concetto di conflitto. Due operazioni in uno schedule si dicono in conflitto se:
   • Appartengono a differenti transazioni;
   • Almeno una delle due è un’operazione di scrittura;
   • Accedono agli stessi dati (read o write);

   Vi sono due tipi di conflitto, read-write (rw/wr) o write-write (ww).

   Quindi due schedule S e S’ sono detti conflict equivalent se:

   • Entrambi possiedono lo stesso set di transazioni (con stesso ordine di azioni);
   • Entrambi hanno lo stesso set di operazioni in conflitto.

   Uno schedule è conflict serializable se è conflict equivalent ad uno o più schedule seriali. Ogni schedule conflict serializable è anche view serializable, ma non il viceversa.

   Testare la conflict-serializability di uno schedule:

   • Consideriamo solo le operazioni R(X) e W(X) in S;
   • Costruiamo un grafo delle precedenze (grafo di serializzazione), ovvero un grafo con un nodo per ogni transazione T_i in S ed archi diretti tra loro;
   • Ogni volta che T1 esegue una R(X) dopo che T2 esegue una W(X), traccio un arco T2 → T1;
   • Ogni volta che T1 esegue una W(X) dopo che T2 esegue una R(X), traccio un arco T2 → T1;
   • Ogni volta che T1 esegue una W(X) dopo che T2 esegue una W(X), traccio un arco T2 → T1;
   • Lo schedule S è serializzabile se e solo se il grafo delle precedenze è aciclico.

   Se S è serializzabile, si può creare l’equivalente schedule seriale S’ riordinando le T in modo che per ogni arco da T2 a T1, T2 deve apparire prima di T1.

   Esempi:

   1. Uno schedule seriale S’ equivalente ad uno schedule S conflict serializable può essere ottenuto ordinando le transazioni partecipanti nel grafo per S come segue:
   2. Posta L una lista vuota:
   • Sia T_i un nodo nel grafo senza archi entranti (è possibile poiché il grafo è aciclico);
   • Inserisci T_i in L;
   • Rimuovi T_i e tutti i suoi archi uscenti dal grafo;
   • Ripeti i punti 1, 2, 3 fino a che il grafo non è vuoto.
   3. Esempio di view-serializability vs conflict-serializability:

Verificare la serializzabilità è difficile anche utilizzando il conflict-serializability test, poiché l’interleaving delle operazioni può variare in base allo scheduler di sistema, ed è altrettanto difficile determinare come avviene l’interleaving tra le operazioni in uno schedule. L’approccio pratico utilizzato nei DBMS è basato sull’utilizzo di protocolli (serie di regole) che, se seguite in ogni singola transazione, permette la serializzabilità di tutti gli schedule in cui partecipano le transazioni. I due più usati sono:

• Two-Phase Locking (2PL);
• Timestamp ordering (TO).

L’ordine di scheduling impatta molto sulla ripristinabilità del sistema in caso di guasti. Per alcuni schedule è facile recuperare errori, mentre per altri il processo di recupero può essere impossibile. È importante caratterizzare gli schedule per i quali è possibile una qualche forma di recupero, e quale tra queste è relativamente semplice. Le transazioni fanno commit solo dopo che tutte le T di cui hanno letto le modifiche, fanno commit. Uno schedule S è detto recoverable se nessuna transazione T in S effettua il commit prima che ogni altra transazione T’ (che ha scritto su un elemento X su cui T ha letto) abbia fatto commit. Questa proprietà impone quindi l’esecuzione del commit solo in una particolare situazione. In uno schedule recoverable, nessuna transazione che ha effettuato commit ha bisogno di fare il rollback (proprietà di durability). Gli schedule che non rispettano questo criterio sono chiamati nonrecoverable e possono non essere permessi nei DBMS. Esempi:

Può accadere che una o più transazioni uncommitted debbano effettuare il rollback a causa del fatto di aver letto dati da una transazione fallita (abort), causando un cascading rollback (o abort). Per evitare il rollback a cascata, esistono i cascadeless schedule, nei quali ogni transazione legge solamente la risorsa che è stata scritta da transazioni che hanno effettuato il commit. Ogni schedule cascadeless è anche recoverable. Uno schedule strict implica che al suo interno una qualsiasi transazione non può leggere o scrivere un elemento X fino a che l’ultima transazione che ha scritto X non ha effettuato commit (o abort). Quindi ogni schedule strict è sia cascadeless che serializzabile, ed ovviamente essendo cascadeless è anche recoverable. La procedura di recupero per gli strict schedule è semplice, poiché annullare gli effetti di un’operazione W_i(X) appartenente alla transazione T_i consiste semplicemente nel recuperare il vecchio valore di X, ovvero il suo valore prima della scrittura.

Attenzione al fatto che uno schedule serializzabile non è detto che sia recoverable, poiché ad esempio:

...ed allo stesso modo uno schedule recoverable non è detto che sia serializzabile:

Riassumendo

Riassumendo, gli schedule possono essere caratterizzati sulla serializzabilità e la recoverability, come nel seguente schema:

Protocolli per la serializzazione degli schedule

Nella pratica, nei DBMS vengono utilizzati protocolli (serie di regole) applicati su ogni singola transazione, per garantire la serializzabilità di tutti gli schedule dove le transazioni sono coinvolte. I protocolli sono basati sul locking oppure basati sul timestamp ordering. Il protocollo più utilizzato è il 2PL (Two-Phase Locking protocol).

Lock binario

La tecnica più semplice di lock è il lock binario, il quale è basato sui due stati:

• Locked, Lock(X) = 1;
• Unlocked, Lock(X) = 0.

Ed è associato con ogni dato X nel database. In questo modo è implementata la mutua esclusione nell’accesso ai dati. Le operazioni di lock (in lettura o scrittura) e di unlock di un elemento X sono gestite dal lock manager e sono atomiche. Esse vanno a costruire la lock table, nella quale sono salvate le righe composte da <data_item_name, LOCK, transaction> con in aggiunta una coda per le transazioni in attesa. Con questo tipo di lock ogni transazione deve effettuare il lock della risorsa prima di effettuare ogni operazione di lettura o scrittura sulla risorsa, dopodiché deve rilasciare il lock non appena ha completato l’operazione per cui era stato richiesto.

Lock esclusivo e condiviso

Esistono due tipi di lock:

• Lock Condiviso (shared), ovvero il lock in lettura. Più di una transazione può applicare il read-lock sulla risorsa X per leggerne il valore, ma nessun’altra transazione può applicare il write-lock su X;
• Lock Esclusivo, ovvero il lock in scrittura. Solo una transazione alla volta può applicare il write-lock sulla risorsa X, e nessun’altra transazione può applicare il read-lock.

La risoluzione dei lock sulle risorse è basata su matrici di conflitto, ovvero delle tabelle 2*2 dove vengono esplicitati i lock attivi sulla risorsa. Se la risorsa è bloccata, viene inserita una entry nella tabella avente il seguente schema: L’ultimo campo è composto da una singola transazione se il lock è in scrittura, mentre è composto da una lista di transazioni se è in lettura. È possibile fare l’upgrade e il downgrade del lock, passando da read-lock a write-lock e viceversa, in base alle esigenze della transazione. L’utilizzo di lock esclusivi o condivisi non è garanzia assoluta di serializzabilità degli schedule. Di seguito alcuni esempi:

2PL (Two-Phase Locking Protocol)

Per garantire la serializzabilità è necessario seguire un protocollo aggiuntivo che regoli il posizionamento delle operazioni di lock e unlock per ogni transazione. Una transazione T segue il protocollo 2PL se tutte le operazioni di lock precedono la prima operazione di unlock in T. Risulta quindi che una transazione è suddivisa in due fasi:

• Fase di acquisizione (Growing) – dove T acquisisce il nuovo lock su una o più risorse, impendendone il rilascio;
• Fase di rilascio (Shrinking) – dove T può ora sbloccare i dati precedentemente bloccati.