Transazioni
Una transazione è una sequenza di operazioni sui dati che ha un inizio e una fine.
Una transazione implica l'esecuzione consecutiva di operazioni di lettura e scrittura. La fine di una transazione può essere rappresentata dal salvataggio delle modifiche (commit) o dall'annullamento delle modifiche (rollback). Nel contesto di un database, una transazione consiste in più query trattate come un'unica richiesta.
Le transazioni devono soddisfare le proprietà ACID.
Atomicità. Una transazione deve essere eseguita interamente oppure non deve essere eseguita affatto.
Coerenza. Al termine di una transazione, non devono essere violate le restrizioni imposte sui dati (ad esempio, i vincoli nei database). La coerenza presuppone che il sistema venga portato da uno stato corretto a un altro stato corretto.
Isolamento. Le transazioni eseguite in parallelo non devono influenzarsi reciprocamente, ad esempio cambiando i dati utilizzati da un'altra transazione. Il risultato dell'esecuzione di transazioni parallele deve essere come se fossero eseguite in modo sequenziale.
Durabilità. Dopo il commit, le modifiche non devono andare perse.
Registro delle transazioni
Il registro conserva le modifiche apportate dalle transazioni, garantendo l'atomicità e la resilienza dei dati in caso di guasto del sistema.
Il registro contiene i valori che i dati avevano prima e dopo le modifiche effettuate dalla transazione. La strategia del write-ahead log richiede di aggiungere al registro una registrazione dei valori precedenti prima dell'inizio e dei valori finali dopo il completamento della transazione. In caso di arresto improvviso del sistema, il database legge il log in ordine inverso e annulla le modifiche apportate dalle transazioni. Quando incontra una transazione interrotta, il database la esegue e registra le modifiche nel log. Essendo nello stato al momento del guasto, il database legge il log in ordine diretto e ripristina le modifiche apportate dalle transazioni. In questo modo, si garantisce la resilienza delle transazioni già confermate e l’atomicità delle transazioni interrotte.
Una semplice riesecuzione delle transazioni errate non è sufficiente per il ripristino.
Esempio. L'utente ha 500$ sul suo conto e decide di ritirarli tramite un bancomat. Vengono effettuate due transazioni. La prima legge il valore del saldo e, se il saldo è sufficiente, eroga il denaro all'utente. La seconda sottrae l'importo necessario dal saldo. Supponiamo che si sia verificato un guasto di sistema e la prima operazione non sia riuscita, mentre la seconda è andata a buon fine. In questo caso, non possiamo riemettere denaro all'utente senza riportare il sistema allo stato iniziale con un saldo positivo.
Livelli di isolamento
Lettura dati confermati (Read Committed)
Il problema della lettura sporca (Dirty Read) sta nel fatto che una transazione può leggere un risultato intermedio di un'altra transazione.
Esempio. Il saldo iniziale è 0$. T1 aggiunge 50$ al saldo. T2 legge il valore del saldo (50$). T1 annulla le modifiche e termina. T2 continua l'esecuzione con dati errati sul saldo.
La soluzione consiste nella lettura dei dati fissati (Read Committed), che vieta di leggere i dati modificati da una transazione. Se la transazione A modifica un certo insieme di dati, la transazione B, nel tentativo di accedere a tali dati, deve attendere il completamento della transazione A.
Lettura ripetibile (Repeatable Read)
Problema delle modifiche perse (Lost Updates). T1 salva modifiche sovrascrivendo quelle di T2.
Esempio. Il valore iniziale del saldo è 0$ e due transazioni incrementano simultaneamente il saldo. T1 e T2 leggono un saldo pari a 0$. Poi T2 aggiunge 200$ a 0$ e salva il risultato. T1 aggiunge 100$ a 0$ e salva il risultato. Il risultato finale è 100$ invece di 300$.
Problema della lettura non ripetibile (Unrepeatable read). La rilettura degli stessi dati restituisce valori diversi.
Esempio. T1 legge un valore di saldo pari a 0$. Poi T2 aggiunge 50$ al saldo e si completa. T1 rileggendo i dati 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 set di dati, la transazione B, quando richiede questi dati, deve attendere il completamento della transazione A.
Lettura ordinata (Serializable)
Problema della lettura fantasma (Phantom Reads). Due richieste che selezionano dati in base a una certa condizione restituiscono valori diversi.
Esempio. T1 richiede il numero totale di utenti il cui saldo è maggiore di 0$ ma inferiore a 100$. T2 sottrae 1$ da un utente con un saldo di 101$. T1 esegue nuovamente la richiesta.
Lettura ordinata (Serializable). Le transazioni vengono eseguite come completamente sequenziali. È vietato aggiornare e aggiungere record che rientrano nei criteri di richiesta. Se la transazione A richiede dati dell'intero tavolo, l'intera tabella viene congelata 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 parallele.
Garantisce un certo livello di isolamento. Se il risultato delle operazioni non dipende dalla loro sequenza, queste operazioni sono commutative (Permutabili). Le operazioni di lettura e le operazioni su dati diversi sono commutative. Le operazioni di lettura-scrittura e scrittura-scrittura non sono commutative. Il compito del pianificatore è 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, mirato a prevenire l'insorgere dei conflitti.
Con l'approccio ottimista, più utenti hanno a disposizione copie dei dati. Il primo a completare le modifiche salva le modifiche, mentre gli altri devono unire le modifiche. L'algoritmo ottimista consente il verificarsi di un conflitto, ma il sistema deve riprendersi dopo il conflitto.
In un approccio pessimista, il primo utente che acquisisce i dati impedisce agli altri di ottenere quelle informazioni. Se i conflitti sono rari, è ragionevole scegliere una strategia ottimistica, poiché essa garantisce un livello di parallelismo più elevato.
Blocco (Locking)
Se una transazione ha bloccato i dati, le altre transazioni che tentano di accedervi devono attendere lo sblocco.
Il blocco può essere applicato a un database, una tabella, una riga o un attributo. Il blocco condiviso (Shared Lock) può essere applicato sui dati da più transazioni, consentendo a tutte le transazioni (inclusa quella che ha applicato il blocco) di leggere, ma vietando modifiche e blocchi esclusivi. Il blocco esclusivo (Exclusive Lock) può essere applicato solo da una transazione, consentendo qualsiasi operazione alla transazione che lo ha applicato, ma vietando qualsiasi operazione alle altre.
Una situazione di deadlock si verifica quando le transazioni si trovano in uno stato di attesa che dura indefinitamente.
Esempio. La prima transazione attende lo sblocco dei dati acquisiti dalla seconda, mentre la seconda attende lo sblocco dei dati acquisiti dalla prima.
La soluzione ottimistica per il problema dei deadlock consente che si verifichi un deadlock, ma poi ripristina il sistema annullando una delle transazioni coinvolte nel deadlock.
Con una certa periodicità viene eseguita la ricerca di deadlock. Uno dei modi per individuarli è basato sul tempo, ovvero si considera che un deadlock sia avvenuto se una transazione dura troppo a lungo. Quando viene trovato un deadlock, una delle transazioni viene annullata, permettendo così alle altre transazioni coinvolte di completarsi. La scelta della vittima può basarsi sul costo delle transazioni o sulla loro anzianità (schemi Wait-Die e Wound-wait).
Ad ogni transazione T viene assegnato un timestamp TS che contiene l'ora 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 giovane ha acquisito una risorsa e una più vecchia richiede la stessa risorsa, allora la transazione più anziana può aspettare. Se una transazione più vecchia ha acquisito la risorsa, la transazione giovane che richiede quella risorsa verrà annullata.
Wound-wait.
Se TS(Ti) < TS(Tj), allora Tj rollback e ricomincia con lo stesso timestamp, altrimenti Ti attende.
Se una transazione più giovane acquisisce una risorsa e una transazione più vecchia richiede la stessa risorsa, la transazione giovane verrà annullata. Se una transazione più vecchia acquisisce una risorsa, la transazione più giovane che richiede quella risorsa è autorizzata ad attendere. La scelta della vittima basata sull'età previene l'insorgere di deadlock, ma rollbacka transazioni che non sono in uno stato di deadlock. Il problema è che le transazioni possono essere annullate più volte, poiché una transazione più vecchia può mantenere a lungo la risorsa.
Una soluzione pessimistica al problema dei deadlock non consente l'esecuzione della transazione se c'è il rischio di un deadlock
Per rilevare un deadlock, viene costruito un grafo (grafo di attesa, wait-for-graph), dove i nodi rappresentano le transazioni e gli archi sono orientati dalle transazioni in attesa del rilascio dei dati verso le transazioni che hanno acquisito tali dati. Si considera che ci sia un deadlock se il grafo presenta cicli. La costruzione del grafo di attesa, specialmente in database distribuiti, è un'operazione costosa.
Il locking a due fasi previene i deadlock attraverso l'acquisizione di tutte le risorse utilizzate dalla transazione all'inizio e il rilascio delle stesse alla fine.
Tutte le operazioni bloccanti devono precedere la prima operazione di sblocco. Presenta due fasi: la fase di crescita (Growing Phase) in cui avviene l'accumulo delle acquisizioni, e la fase di riduzione (Shrinking Phase) in cui avviene il rilascio delle acquisizioni. Se non è possibile acquisire una delle risorse, la transazione ricomincia da capo. Può verificarsi la situazione in cui una transazione non riesce ad acquisire le risorse necessarie, ad esempio se più transazioni competono per le stesse risorse.
Il commit a due fasi assicura l'esecuzione del commit su tutte le repliche del database.
Ogni database registra le informazioni sui dati che saranno modificati nel log e risponde al coordinatore con un OK (Fase di Votazione). Una volta che tutti hanno risposto con OK, il coordinatore invia un segnale che obbliga tutti a eseguire il commit. Dopo il commit server rispondono con OK; se anche solo uno non risponde con OK, il coordinatore invia un segnale di annullamento delle modifiche a tutti i server (Fase di Completamento).
Metodo delle timestamp
Una transazione più vecchia viene annullata se tenta di accedere ai dati utilizzati da una transazione più giovane
A ciascuna transazione viene assegnata una timestamp TS che corrisponde al momento di inizio dell'esecuzione. Se Ti è più vecchia Tj, allora TS(Ti) < TS(Tj).
Quando una transazione viene annullata, le viene assegnata una nuova timestamp. Ogni oggetto dati Q coinvolto nella transazione è contrassegnato da due timestamp. W-TS(Q) — la timestamp della transazione più giovane che ha eseguito con successo una scrittura su Q. R-TS(Q) — la timestamp della transazione più giovane che ha eseguito una scrittura di lettura su Q.
Quando la transazione T richiede di leggere i dati Q sono possibili due scenari.
Se TS(T) < W-TS(Q), ovvero i dati sono stati aggiornati da una transazione più giovane, quindi la transazione T viene annullata.
Se TS(T) >= W-TS(Q), quindi la lettura viene eseguita e R-TS(Q) diventa MAX(R-TS(Q), TS(T)).
Quando la transazione T richiede una modifica dei dati Q sono possibili due scenari.
Se TS(T) < R-TS(Q), cioè i dati sono già stati letti da una transazione più giovane e se si effettuano modifiche, si verificherà un conflitto. La transazione T viene annullata.
Se TS(T) < W-TS(Q), cioè la transazione sta cercando di sovrascrivere un valore più recente, la transazione T viene annullata. Negli altri casi, la modifica viene eseguita e W-TS(Q) diventa uguale a TS(T).
Non è necessaria una costosa costruzione del grafo delle attese. 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 rollback a cascata. Se Ti è stata annullata, e Tj ha letto i dati che ha modificato Ti, allora Tj deve essere annullata anch'essa. Se in tal caso Tj era già stata committata, si verificherà una violazione del principio di coerenza.
Una delle soluzioni ai rollback a cascata. La transazione esegue tutte le operazioni di scrittura alla fine, e quindi le altre transazioni devono attendere il completamento di quest'operazione. Le transazioni aspettano il commit prima di leggere.
La regola di scrittura di Thomas — una variazione del metodo degli orari in cui i dati aggiornati da una transazione più giovane non possono essere sovrascritti da una più vecchia
Transazione T richiede una modifica dei dati Q. Se TS(T) < W-TS(Q), ovvero la transazione sta cercando di sovrascrivere un valore più recente, la transazione T non viene annullata come nel metodo dei timestamp.
Fonte: habr.com
