Transazioni
Una transazione è una sequenza di operazioni sui dati che ha un inizio e una fine.
Una transazione si compone dell'esecuzione sequenziale di operazioni di lettura e scrittura. La conclusione di una transazione può essere o il salvataggio delle modifiche (commit) o il ripristino delle modifiche (rollback). In riferimento ai database, una transazione è composta da più query trattate come un'unica richiesta.
Le transazioni devono soddisfare le proprietà ACID.
Atomicità. Una transazione viene eseguita completamente oppure non viene eseguita affatto.
Coerenza. Al termine della transazione non devono essere violati i vincoli imposti sui dati (ad esempio, i constraints nei database). La coerenza implica che il sistema venga portato da uno stato corretto a un altro stato corretto.
Isolamento. Le transazioni eseguite in parallelo non devono influenzarsi a vicenda, per esempio modificando i dati utilizzati da un'altra transazione. Il risultato dell'esecuzione di transazioni parallele deve essere tale da sembrare che siano state eseguite in modo sequenziale.
Durabilità. Dopo il commit, le modifiche non devono andare perse.
Registro delle transazioni.
Il registro conserva le modifiche effettuate dalle transazioni e garantisce l'atomicità e la durabilità dei dati in caso di guasto del sistema.
Il registro contiene i valori che i dati avevano prima e dopo le loro modifiche da parte della transazione. La strategia del write-ahead log richiede di registrare i valori precedenti all'inizio della transazione e i valori finali al termine della transazione. In caso di un arresto improvviso del sistema, il database legge il log in ordine inverso e annulla le modifiche apportate dalle transazioni. Incontrando una transazione interrotta, il database la esegue e registra le relative modifiche nel log. In presenza dello stato al momento del guasto, il database legge il log in ordine diretto e ripristina le modifiche apportate dalle transazioni. In questo modo si preserva la durabilità delle transazioni già confermate e l'atomicità della transazione interrotta.
Una semplice ripetizione delle transazioni errate non è sufficiente per il ripristino.
Esempio. L'utente ha 500$ sul proprio conto e decide di prelevarli tramite un bancomat. Vengono eseguite due transazioni. La prima legge il valore del saldo e, se ci sono fondi sufficienti, eroga denaro all'utente. La seconda sottrae l'importo necessario dal saldo. Supponiamo che si sia verificato un errore di sistema e la prima operazione non sia riuscita, mentre la seconda sì. In questo caso, non possiamo riemettere il denaro all'utente senza ripristinare il sistema allo stato iniziale con un saldo positivo.
Livelli di isolamento
Lettura dei dati fissi (Read Committed)
Il problema della lettura sporca (Dirty Read) consiste nel fatto che una transazione può leggere un risultato intermedio di un'altra transazione.
Esempio. Valore iniziale del saldo 0$. T1 aggiunge 50$ al saldo. T2 legge il valore del saldo (50$). T1 annulla le modifiche e si conclude. T2 continua l'esecuzione avendo dati errati sul saldo.
La soluzione consiste nella lettura dei dati fissi (Read Committed) che vieta la lettura dei dati modificati da una transazione. Se la transazione A ha modificato un certo insieme di dati, allora la transazione B, richiedendo questi dati, deve attendere la conclusione della transazione A.
Lettura ripetibile (Repeatable Read)
Il problema delle modifiche perse (Lost Updates). T1 salva le modifiche sopra le modifiche di T2.
Esempio. Valore iniziale del saldo 0$ e due transazioni aumentano simultaneamente il saldo. T1 e T2 leggono un saldo pari a 0$. Successivamente T2 aggiunge 200$ a 0$ e salva il risultato. T1 aggiunge 100$ a 0$ e salva il risultato. Il risultato finale è 100$ anziché 300$.
Il problema della lettura non ripetibile (Unrepeatable read). La lettura ripetuta dei medesimi dati restituisce valori diversi.
Esempio. T1 legge un valore di saldo pari a 0$. Poi T2 aggiunge 50$ al saldo e si conclude. T1 legge di nuovo i dati e scopre una discrepanza rispetto al risultato precedente.
La lettura ripetibile (Repeatable Read) garantisce che la lettura ripetuta restituisca lo stesso risultato. I dati letti da una transazione non possono essere modificati da altre fino al completamento della transazione. Se la transazione A ha letto un certo insieme di dati, allora la transazione B, richiedendo questi dati, deve attendere la conclusione della transazione A.
Lettura ordinata (Serializable)
Il problema della lettura fantasma (Phantom Reads). Due richieste che selezionano dati in base a determinate condizioni restituiscono valori diversi.
Esempio. T1 richiede il numero totale degli utenti il cui saldo è maggiore di 0$ ma minore di 100$. T2 sottrae 1$ da un utente con saldo di 101$. T1 esegue nuovamente la richiesta.
Lettura ordinata (Serializable). Le transazioni vengono eseguite come completamente sequenziali. Non è consentito aggiornare o aggiungere record che ricadono sotto le condizioni di richiesta. Se la transazione A richiede dati dall'intera tabella, allora l'intera tabella viene bloccata per le altre transazioni fino al completamento della transazione A.
Pianificatore (Scheduler)
Stabilisce l'ordine in cui devono essere eseguite le operazioni durante le transazioni che avvengono in parallelo.
Garantisce un livello di isolamento stabilito. Se il risultato dell'esecuzione delle operazioni non dipende dal loro ordine, tali operazioni sono commutative (Permutable). Sono commutative le operazioni di lettura e le operazioni su dati diversi. Le operazioni di lettura-scrittura e scrittura-scrittura non sono commutative. Il compito del pianificatore è quello di alternare le operazioni eseguite da transazioni parallele in modo che il risultato sia equivalente all'esecuzione sequenziale delle transazioni.
Meccanismi di controllo della concorrenza (Concurrency Control)
Ottimista basato sulla rilevazione e risoluzione dei conflitti, pessimista sulla prevenzione della comparsa di conflitti.
Con l'approccio ottimista, più utenti ottengono a disposizione copie dei dati. Il primo che completa le modifiche salva le modifiche, mentre gli altri devono eseguire una fusione delle modifiche. L'algoritmo ottimista consente il verificarsi di conflitti, ma il sistema deve recuperarsi dopo il conflitto.
Con l'approccio pessimista, il primo utente che acquisisce i dati impedisce agli altri di accedervi. Se i conflitti sono rari, è ragionevole scegliere una strategia ottimista, in quanto garantisce un livello più elevato di parallelismo.
Bloccaggio (Locking)
Se una transazione ha bloccato i dati, le altre transazioni devono attendere lo sblocco quando accedono ai dati.
Un blocco può essere applicato a un database, una tabella, una riga o un attributo. Il blocco condiviso (Shared Lock) può essere applicato sulle stesse informazioni da più transazioni, consentendo a tutte le transazioni (inclusa quella che ha imposto il blocco) di leggere, ma vietando le modifiche e il blocco esclusivo. Il blocco esclusivo (Exclusive Lock) può essere imposto solo da una transazione, consentendo qualsiasi azione alla transazione che ha imposto il blocco e vietando qualsiasi azione alle altre.
Il deadlock è la situazione in cui le transazioni rimangono in attesa per un tempo indefinito.
Esempio. La prima transazione aspetta il rilascio dei dati bloccati dalla seconda, mentre la seconda aspetta il rilascio dei dati bloccati dalla prima.
Una soluzione ottimistica al problema dei deadlock consente al deadlock di verificarsi, ma recupera il sistema tornando indietro a una delle transazioni coinvolte nel deadlock.
Con una certa periodicità, si cerca il deadlock. Uno dei metodi di rilevamento è basato sul tempo, cioè si considera che si sia verificato un deadlock se una transazione impiega troppo tempo. Quando viene trovato un deadlock, una delle transazioni viene annullata, permettendo alle altre transazioni coinvolte nel deadlock di completarsi. La scelta della vittima può essere basata sui costi delle transazioni o sulla loro anzianità (schemi Wait-Die e Wound-wait).
A ogni transazione T viene assegnato un timestamp TS che contiene il tempo di inizio dell'esecuzione della transazione.
Wait-Die.
Se TS(Ti) < TS(Tj), allora Ti aspetta, altrimenti Ti viene annullata e inizia di nuovo con lo stesso timestamp.
Se una transazione più giovane ha bloccato una risorsa, e una più vecchia richiede la stessa risorsa, allora alla transazione più anziana è permesso attendere. Se una transazione più anziana ha bloccato una risorsa, allora la transazione più giovane che richiede quella risorsa verrà annullata.
Wound-wait.
Se TS(Ti) < TS(Tj), allora Tj viene annullata e inizia di nuovo con lo stesso timestamp, altrimenti Ti aspetta.
Se una transazione più giovane ha acquisito una risorsa, e una transazione più vecchia richiede la stessa risorsa, la transazione più giovane verrà annullata. Se una transazione più vecchia ha acquisito la risorsa, alla transazione più giovane che richiede questa risorsa è permesso attendere. La selezione della vittima basata sull'anzianità previene l'emergere di blocchi reciproci, ma annulla transazioni che non si trovano in uno stato di blocco reciproco. Il problema è che le transazioni possono essere annullate più volte, poiché una transazione più vecchia può trattenere a lungo la risorsa.
Una soluzione pessimistica al problema dei blocchi reciproci non consente a una transazione di iniziare l'esecuzione se c'è il rischio di un blocco reciproco.
Per rilevare un blocco reciproco viene costruito un grafo (grafo di attesa, wait-for-graph), i cui vertici sono le transazioni e i lati sono diretti dalle transazioni in attesa di liberare dei dati verso la transazione che ha acquisito questi dati. Si considera che ci sia un blocco reciproco se il grafo presenta ciclicità. La costruzione del grafo di attesa, soprattutto nelle Basi Dati distribuite, è una procedura costosa.
Il blocco in due fasi previene i blocchi reciproci acquisendo tutte le risorse utilizzate dalla transazione all'inizio della transazione e rilasciandole alla fine.
Tutte le operazioni di blocco devono precedere la prima operazione di sblocco. Ha due fasi: la Fase di Crescita in cui avviene l'accumulo delle acquisizioni e la Fase di Riduzione in cui avviene il rilascio delle acquisizioni. In caso di impossibilità di acquisire una delle risorse, la transazione ricomincia da capo. È possibile che una transazione non riesca ad acquisire le risorse richieste, ad esempio se più transazioni competono per le stesse risorse.
Il commit in due fasi garantisce l'esecuzione del commit su tutte le repliche del database.
Ogni database registra informazioni sui dati che verranno modificati nel log e risponde al coordinatore con un OK (Fase di Voto). Dopo che tutti hanno risposto OK, il coordinatore invia un segnale obbligando tutti a eseguire il commit. Dopo il commit server rispondono OK; se anche uno solo non risponde OK, il coordinatore invia un segnale di annullamento delle modifiche a tutti i server (Fase di Completamento).
Metodo dei timestamp
Una transazione più vecchia viene annullata quando tenta di accedere ai dati coinvolti da una transazione più giovane.
Ad ogni transazione viene assegnato un timestamp TS che corrisponde al momento di inizio dell'esecuzione. Se Ti è più vecchio Tj, allora TS(Ti) < TS(Tj).
Quando la transazione viene annullata, le viene assegnato un nuovo timestamp. Ogni oggetto dati Q coinvolto nella transazione è contrassegnato da due timestamp. W-TS(Q) — il timestamp della transazione più giovane che ha effettuato una scrittura su Q. R-TS(Q) — il timestamp della transazione più giovane che ha effettuato una lettura su Q.
Quando la transazione T richiede la lettura dei dati Q sono possibili due scenari.
Se TS(T) < W-TS(Q), ossia se i dati sono stati aggiornati da una transazione più giovane, la transazione T viene annullata.
Se TS(T) >= W-TS(Q), allora la lettura viene eseguita e R-TS(Q) diventa MAX(R-TS(Q), TS(T)).
Quando la transazione T richiede una modifica ai dati Q sono possibili due scenari.
Se TS(T) < R-TS(Q), vale a dire che i dati sono già stati letti da una transazione più giovane e se si tenta di effettuare una modifica, si verificherà un conflitto. La transazione T viene annullata.
Se TS(T) < W-TS(Q), cioè se la transazione tenta di sovrascrivere un valore più nuovo, la transazione T viene annullata. In tutti gli altri casi, la modifica viene eseguita e W-TS(Q) diventa uguale a TS(T).
Non è necessario costruire un costoso grafo di attesa. Le transazioni più vecchie dipendono da quelle più nuove, quindi nel grafo delle attese non ci sono cicli. Non ci sono deadlock, poiché le transazioni non aspettano, ma vengono annullate immediatamente. Possono verificarsi annullamenti a cascata. Se Ti è stata annullata, e Tj ha letto i dati che ha modificato Ti, allora Tj deve anch'essa essere annullata. Se nel frattempo Tj è già stata impegnata, si verificherà una violazione del principio di resilienza.
Una delle soluzioni per gli annullamenti a cascata. La transazione esegue tutte le operazioni di scrittura alla fine, mentre le altre transazioni devono aspettare il completamento di quest'operazione. Le transazioni aspettano il commit prima di leggere.
Regola di scrittura di Thomas — una variazione del metodo dei timestamp in cui i dati aggiornati da una transazione più giovane non possono essere sovrascritti da una più vecchia.
La transazione T richiede una modifica ai dati QSe TS(T) < W-TS(Q), ossia se la transazione tenta di sovrascrivere un valore più nuovo, la transazione T non viene annullata come nel metodo dei timestamp.
Fonte: habr.com
