Operazioni
Una transazione è una sequenza di operazioni sui dati che ha un inizio e una fine.
Una transazione è l'esecuzione sequenziale di operazioni di lettura e scrittura. La fine di una transazione può essere il salvataggio delle modifiche (commit) o l'annullamento delle modifiche (rollback). In relazione a un database, una transazione è composta da più richieste che vengono trattate come un'unica richiesta.
Le transazioni devono soddisfare le proprietà ACID
Atomicita. La transazione viene completata completamente o non viene completata affatto.
Consistenza. Quando si completa una transazione, le restrizioni imposte sui dati (ad esempio, vincoli nel database) non devono essere violate. La coerenza implica che il sistema verrà trasferito da uno stato corretto a un altro stato corretto.
Isolamento. Le transazioni eseguite in parallelo non dovrebbero influenzarsi a vicenda, ad esempio modificare i dati utilizzati da un'altra transazione. Il risultato dell'esecuzione di transazioni parallele dovrebbe essere lo stesso che se le transazioni fossero eseguite in sequenza.
Sostenibilità. Una volta eseguite, le modifiche non dovrebbero andare perse.
Registro delle transazioni
Il registro memorizza le modifiche apportate dalle transazioni, garantisce l'atomicità e la stabilità dei dati in caso di guasto del sistema
Il log contiene i valori che avevano i dati prima e dopo essere stati modificati dalla transazione. La strategia di registro write-ahead richiede l'aggiunta di una voce di registro sui valori precedenti prima dell'inizio e sui valori finali dopo il completamento della transazione. In caso di arresto improvviso del sistema, il database legge il log in ordine inverso e cancella le modifiche apportate dalle transazioni. Dopo aver riscontrato una transazione interrotta, il database la esegue e apporta modifiche al registro. Trovandosi nello stato al momento dell'errore, il database legge il registro in ordine successivo e restituisce le modifiche apportate dalle transazioni. In questo modo si preserva la stabilità delle transazioni già impegnate e l'atomicità della transazione interrotta.
La semplice riesecuzione delle transazioni non riuscite non è sufficiente per il ripristino.
Esempio. L'utente ha $ 500 sul suo conto e decide di prelevarli da un bancomat. Sono in corso due transazioni. Il primo legge il valore del saldo e se ci sono fondi sufficienti sul saldo, emette denaro all'utente. Il secondo sottrae l'importo richiesto dal saldo. Diciamo che il sistema si è bloccato e la prima operazione è fallita, ma la seconda è fallita. In questo caso, non possiamo riemettere denaro all'utente senza riportare il sistema allo stato originale con un saldo positivo.
Livelli di isolamento
Leggi Impegnato
Il problema della lettura sporca è che una transazione può leggere il risultato intermedio di un'altra transazione.
Esempio. Il valore del saldo iniziale è $ 0. T1 aggiunge $ 50 al tuo saldo. T2 legge il valore del saldo ($50). T1 scarta le modifiche ed esce. T2 continua l'esecuzione con dati di saldo errati.
La soluzione è leggere i dati fissi (Read Committed), che impedisce la lettura dei dati modificati dalla transazione. Se la transazione A ha modificato un determinato insieme di dati, la transazione B, quando accede a questi dati, è costretta ad attendere il completamento della transazione A.
Lettura ripetibile
Problema degli aggiornamenti persi. T1 salva le modifiche oltre a quelle di T2.
Esempio. Il valore del saldo iniziale è $ 0 e due transazioni ripristinano simultaneamente il saldo. T1 e T2 leggono un saldo di $ 0. T2 poi 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 di lettura irripetibile. La lettura ripetuta degli stessi dati restituisce valori diversi.
Esempio. T1 legge un valore di saldo di $ 0. T2 aggiunge quindi $ 50 al saldo e termina. T1 rilegge i dati e trova una discrepanza con il risultato precedente.
La lettura ripetibile garantisce che una seconda lettura restituirà lo stesso risultato. I dati letti da una transazione non possono essere modificati in altre fino al completamento della transazione. Se la transazione A ha letto un determinato insieme di dati, la transazione B, quando accede a questi dati, è costretta ad attendere il completamento della transazione A.
Lettura ordinata (serializzabile)
Problema di lettura fantasma. Due query che selezionano i dati in base a una determinata condizione restituiscono valori diversi.
Esempio. T1 richiede il numero di tutti gli utenti il cui saldo è maggiore di $ 0 ma inferiore a $ 100. T2 detrae $ 1 da un utente con un saldo di $ 101. T1 riemette la richiesta.
Lettura ordinata (serializzabile). Le transazioni vengono eseguite come completamente sequenziali. È vietato aggiornare o aggiungere record che rientrano nei termini della richiesta. Se la transazione A ha richiesto dati dall'intera tabella, l'intera tabella viene bloccata per altre transazioni fino al completamento della transazione A.
Pianificatore
Imposta l'ordine in cui le operazioni devono essere eseguite durante le transazioni parallele.
Fornisce un livello di isolamento specificato. Se il risultato delle operazioni non dipende dal loro ordine, tali 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 dello scheduler è quello di intercalare le operazioni eseguite da transazioni parallele in modo che il risultato dell'esecuzione sia equivalente all'esecuzione sequenziale delle transazioni.
Meccanismi per il controllo dei lavori paralleli (Concurrency Control)
L'ottimismo si basa sull'individuazione e la risoluzione dei conflitti, il pessimismo si basa sulla prevenzione dell'insorgere dei conflitti.
Nell'approccio ottimistico, più utenti hanno a disposizione copie dei dati. La prima persona che completa la modifica salva le modifiche, mentre gli altri devono unire le modifiche. Un algoritmo ottimistico consente il verificarsi di conflitti, ma il sistema deve riprendersi dal conflitto.
Con un approccio pessimistico, il primo utente che acquisisce i dati impedisce ad altri di riceverli. Se i conflitti sono rari, è saggio scegliere la strategia ottimistica, poiché fornisce un livello più elevato di concorrenza.
Chiusura
Se una transazione ha dati bloccati, le altre transazioni devono attendere finché non vengono sbloccate quando accedono ai dati.
Un blocco può essere sovrapposto a un database, una tabella, una riga o un attributo. Il blocco condiviso può essere imposto sugli stessi dati da più transazioni, consente la lettura di tutte le transazioni (inclusa quella che lo ha imposto), vieta la modifica e l'acquisizione esclusiva. Il blocco esclusivo può essere imposto da una sola transazione, consente qualsiasi azione della transazione imponente, vieta qualsiasi azione da parte di altri.
Un deadlock è una situazione in cui le transazioni finiscono in uno stato in sospeso che dura indefinitamente.
Esempio. La prima transazione attende il rilascio dei dati catturati dalla seconda, mentre la seconda attende il rilascio dei dati catturati dalla prima.
Una soluzione ottimistica al problema del deadlock consente il verificarsi del deadlock, ma poi ripristina il sistema ripristinando una delle transazioni coinvolte nel deadlock.
I deadlock vengono ricercati a determinati intervalli. Uno dei metodi di rilevamento è quello temporale, ovvero considerare che si è verificato un deadlock se la transazione impiega troppo tempo per essere completata. Quando viene rilevato un deadlock, viene eseguito il rollback di una delle transazioni, consentendo il completamento delle altre transazioni coinvolte nel deadlock. La scelta della vittima può essere basata sul valore delle transazioni o sulla loro anzianità (schemi Wait-Die e Wound-wait).
Ogni transazione T viene assegnato un timestamp TS contenente l'orario di inizio della transazione.
Aspetta-muori.
se ST(Ti) < ST(Tj)poi Ti aspetta, altrimenti Ti torna indietro e ricomincia con lo stesso timestamp.
Se una transazione giovane ha acquisito una risorsa e una transazione più vecchia richiede la stessa risorsa, la transazione più vecchia può attendere. Se una transazione precedente ha acquisito una risorsa, verrà eseguito il rollback della transazione più giovane che richiede quella risorsa.
Ferita-aspetta.
se ST(Ti) < ST(Tj)poi Tj torna indietro e ricomincia con lo stesso timestamp, altrimenti Ti in attesa.
Se una transazione più giovane ha acquisito una risorsa e una transazione più vecchia richiede la stessa risorsa, verrà eseguito il rollback della transazione più giovane. Se una transazione più vecchia ha acquisito una risorsa, la transazione più giovane che richiede quella risorsa può attendere. La selezione delle vittime basata sulla precedenza previene i deadlock, ma ripristina le transazioni che non sono in deadlock. Il problema è che le transazioni possono essere ripristinate molte volte perché... una transazione più vecchia potrebbe trattenere la risorsa per un lungo periodo.
Una soluzione pessimistica al problema dello stallo non consente l'avvio dell'esecuzione di una transazione se esiste il rischio di uno stallo.
Per rilevare un deadlock, viene costruito un grafico (grafico di attesa, wait-for-graph), i cui vertici sono transazioni e i bordi sono diretti dalle transazioni in attesa del rilascio di dati alla transazione che ha catturato questi dati. Si ritiene che si sia verificato un deadlock se il grafico presenta un ciclo. Costruire un grafico di attesa, soprattutto nei database distribuiti, è una procedura costosa.
Blocco a due fasi: previene i deadlock sequestrando tutte le risorse utilizzate da una transazione all'inizio della transazione e rilasciandole alla fine
Tutte le operazioni di blocco devono precedere la prima operazione di sblocco. Ha due fasi: fase di crescita, durante la quale le prese si accumulano, e fase di contrazione, durante la quale le prese vengono rilasciate. Se è impossibile catturare una delle risorse, la transazione ricomincia. È possibile che una transazione non riesca ad acquisire le risorse necessarie, ad esempio, se più transazioni competono per le stesse risorse.
Un commit in due fasi garantisce che il commit venga eseguito su tutte le repliche del database
Ogni database inserisce le informazioni sui dati che verranno modificati nel registro e risponde all'OK del coordinatore (fase di votazione). Dopo che tutti hanno risposto OK, il coordinatore invia un segnale obbligando tutti a impegnarsi. Dopo il commit, i server rispondono OK; se almeno uno non risponde OK, allora il coordinatore invia un segnale per annullare le modifiche a tutti i server (Fase di Completamento).
Metodo del timestamp
Viene eseguito il rollback di una transazione precedente quando si tenta di accedere ai dati coinvolti da una transazione più recente
Ad ogni transazione viene assegnato un timestamp TS corrispondente all'ora di inizio dell'esecuzione. Se Ti anziano Tjpoi ST(Ti) < ST(Tj).
Quando viene eseguito il rollback di una transazione, le viene assegnato un nuovo timestamp. Ogni oggetto dati Q coinvolto nella transazione è contrassegnato da due etichette. W-TS(Q) — timestamp della transazione più recente che ha completato con successo un record Q. R-TS(Q) — timestamp della transazione più recente su cui è stato eseguito un record di lettura Q.
Quando la transazione T richieste di lettura dei dati Q sono possibili due opzioni.
se ST(T) < W-TS(Q), ovvero i dati sono stati aggiornati da una transazione più recente, quindi dalla transazione T torna indietro.
se ST(T) >= W-TS(Q), quindi viene eseguita la lettura e R-TS(Q) sta diventando MAX(R-TS(Q), TS(T)).
Quando la transazione T richiede modifiche ai dati Q sono possibili due opzioni.
se ST(T) < R-TS(Q), cioè i dati sono già stati letti da una transazione più giovane e se viene apportata una modifica si creerà un conflitto. Transazione T torna indietro.
se ST(T) < W-TS(Q), ovvero, la transazione tenta di sovrascrivere un valore più recente, la transazione T viene ripristinata. In altri casi, la modifica viene eseguita e W-TS(Q) diventa uguale ST(T).
Non è richiesta la costosa costruzione del grafico di attesa. Le transazioni più vecchie dipendono da quelle più recenti, quindi non ci sono cicli nel grafico di attesa. Non ci sono situazioni di stallo perché le transazioni non vengono attese ma annullate immediatamente. Sono possibili rollback a cascata. Se Ti rotolato via e Tj Ho letto i dati che ho modificato Tipoi Tj dovrebbe anche tornare indietro. Se allo stesso tempo Tj è già stato commesso, allora si verificherà una violazione del principio di stabilità.
Una delle soluzioni ai rollback a cascata. Una transazione completa tutte le operazioni di scrittura alla fine e le altre transazioni devono attendere il completamento di tale operazione. Le transazioni attendono di essere impegnate prima di essere lette.
Regola di scrittura Thomas: una variazione del metodo timestamp in cui è vietato sovrascrivere i dati aggiornati da una transazione più recente da parte di una transazione più vecchia
transazione T richiede modifiche ai dati Q. Se ST(T) < W-TS(Q), ovvero, la transazione tenta di sovrascrivere un valore più recente, la transazione T non viene ripristinata come nel metodo timestamp.
Fonte: habr.com