Una transazione è un insieme di elaborazioni che – pur eseguite in concorrenza con le elaborazioni di altre transazioni in competizione per l’accesso a risorse condivise, ed in un contesto in cui sono possibili malfunzionamenti – costituiscono un’unità di lavoro indivisibile, che gode di opportune proprietà atte a garantirne la correttezza e la persistenza degli effetti.
Tali proprietà sono in letteratura con l’acronimo ACID (Atomicità, Consistenza, Isolamento, Durata) (Härder e Reuter, 1983).
L’atomicità può essere riguardata come la proprietà di indivisibilità o del “tutto o niente” nei riguardi dei malfunzionamenti (failure atomicity).
L’isolamento può essere riguardato come la proprietà di indivisibilità o del “tutto o niente” di una transazione nei riguardi dell’esecuzione concorrente con altre transazioni in competizione sugli stessi oggetti.
Le proprietà di atomicità e durata richiedono che lo stato degli oggetti condivisi sia ripristinabile in caso di guasti (objects recoverability).
Al momento in cui un server accetta la richiesta di completamento con successo (commit) di una transazione, tutte le modifiche da essa effettuate sugli oggetti devono essere state registrate in memoria non volatile.
In tal modo, in caso di crash improvvisi (ed eventualmente ripetuti) del server per un guasto hardware o per un’anomalia software, sarà prima o poi possibile il ripristino dello stato degli oggetti da parte di un nuovo server.
Un modo per conferire caratteristiche di transazionalità a un server che gestisce oggetti recoverable è di creare un oggetto coordinatore delle transazioni, che implementi la seguente interfaccia:
La transazionalità si ottiene grazie alla cooperazione tra il client, gli oggetti condivisi (e recoverable), ed il coordinatore.
Il client deve racchiudere tutte le operazioni sugli oggetti recoverable condivisi tra una coppia di operazioni sul coordinatore
openTransaction() / closeTransaction(),
oppure
openTransaction() / abortTransaction().
Azioni lato server in caso di crash:
Azioni lato client in caso di crash del server:
Se due o più transazioni producono effetti “corretti” quando sono eseguite in isolamento (nel senso che rispettano la proprietà di consistenza), una loro qualsiasi esecuzione seriale (in cui cioè le transazioni sono eseguite una dopo l’altra, senza che singolarmente siano interrotte) è anch’essa corretta.
Si ha dunque che condizione sufficiente affinché una esecuzione concorrente di tali transazioni sia anch’essa corretta (pur se esse competono per l’accesso ad alcuni oggetti condivisi), è che essa sia equivalente ad una loro qualsiasi esecuzione seriale, cioè produca gli stessi effetti di una esecuzione sequenziale delle transazioni in un qualsiasi ordine.
Naturalmente le possibili esecuzioni sequenziali di un insieme di transazioni non producono tutte gli stessi effetti, in generale.
L’effetto finale su B dovrebbe essere: B=242 (indipendentemente dall’ordine relativo di T e U).
In figura è mostrata una possibile esecuzione concorrente di T1 e T2.
L’effetto finale su Y in tale esecuzione concorrente è Y=22.
Il problema è che Y è una risorsa condivisa, e T1 non si accorge degli aggiornamenti di T2, ed aggiorna Y annullando le modifiche di T2.
Il problema degli aggiornamenti persi (lost update) può presentarsi quando due transazioni leggono il valore di una variabile e successivamente lo usano per calcolarne un nuovo valore.
Il problema dunque non può presentarsi se una transazione è eseguita – per quanto concerne gli accessi alla variabile condivisa – prima dell’altra, perché in tal caso la seconda leggerebbe il valore finale della prima.
Una esecuzione concorrente ma serialmente equivalente di T1 e T2. T1 esegue tutte le sue operazioni sulla risorsa condivisa B prima di T2
I valori iniziali dei conti sono: X=10, Y=10.
T1: trasferisce un importo da X a Y.
T2: calcola la somma dei saldi di tutti i conti della filiale.
Il totale (parziale) di T2 è inconsistente in quanto T1 ha effettuato solo il prelievo da X quando T2 legge i saldi sia di X sia di Y.
Il problema può presentarsi quando le transazioni in sola lettura operano concorrentemente con quelle in modifica.
Non può presentarsi se tutte le letture sono eseguite prima o dopo gli aggiornamenti.
In figura è mostrata una esecuzione serialmente equivalente di V e W.
Due operazioni si dicono confliggenti se il loro effetto combinato dipende dall’ordine relativo secondo cui esse sono eseguite.
Affinché una esecuzione concorrente di due transazioni sia equivalente a una qualsiasi loro esecuzione seriale è necessario e sufficiente che tutte le coppie di operazioni in conflitto delle due transazioni siano eseguite nello stesso ordine per tutti gli oggetti da esse condivisi.
L’equivalenza seriale è utile come criterio per la definizione di protocolli di controllo di concorrenza.
Tre tecniche classiche di controllo di concorrenza sono:
Esempio: i, j: risorse condivise
Transazione T1: A=leggi(X); write(X,5); write(Y,6);
Transazione T2: B=read(Y); write(Y,7); C=read(X);
In figura è mostrata una possibile esecuzione concorrente.
T1 effettua tutti gli accessi a X prima di T2.
T2 effettua tutti gli accessi a Y prima di T1.
L’esecuzione non è equivalente a una esecuzione seriale di T1 e T2, perché l’ordine delle operazioni confliggenti non è lo stesso per tutti gli oggetti.
L’equivalenza seriale richiede in questo caso che:
Un server deve rendere permanenti gli effetti delle transazioni che eseguono il commit ed annullare quelli delle transazioni che abortiscono.
Occorre però anche garantire che l’aborto di una transazione non abbia effetti collaterali negativi su altre transazioni concorrenti.
Alcuni problemi che possono verificarsi a seguito di aborti sono:
La proprietà di isolamento richiede che le transazioni non vedano gli stati non committed delle altre transazioni.
In figura è mostrato l’esempio, Valori iniziali: X=1, A=2, B=3
T1 abortisce, e T2 – che dopo il commit non può più essere abortita – ha letto un valore mai esistito per l’oggetto X (dirty read).
Per evitare il problema delle letture spurie, occorre evitare che una transazione (come T2, nell’esempio) effettui il commit dopo aver visto gli effetti di un’altra transazione (T1) che non è stata ancora completata, e che può quindi ancora essere abortita (dal client o dal server).
Per prevenire letture spurie occorre ritardare il commit di una transazione, eseguendolo dopo il commit di tutte le altre transazioni in modifica delle quali sono stati osservati stati intermedi.
Se una di tali transazioni (come T1) abortisce, anche la transazione “sospesa” (come T2) deve essere abortita.
In una situazione come quella delle letture spurie, l’aborto di una transazione (come T1, nell’esempio) causa l’aborto di un’altra transazione (T2); ciò potrebbe determinare l’aborto di altre transazioni (che a loro volta hanno visto stati intermedi di T2), causando un effetto domino.
Per prevenire aborti a cascata, ogni operazione di lettura (read) su un oggetto x deve essere rinviata a dopo il completamento (commit o abort) di tutte le transazioni che hanno effettuato scritture (write) sullo stesso oggetto x.
Questa condizione è più stringente di quella necessaria per prevenire le letture spurie.
Si tratta di un problema connesso ad aborti in caso di scritture concorrenti sullo stesso oggetto da parte di due o più transazioni.
In figura è mostrato l’esempio: inizialmente X=1.
La serializzabilità è soddisfatta (le transazioni consistono di una sola operazione). Se T1 fa il commit e T2 abortisce, lo stato finale dovrebbe essere X=3. Nel caso duale, dovrebbe aversi X=5.
Il problema nasce dal fatto che tipicamente il ripristino in caso di aborto viene realizzato facendo ricorso ai valori precedenti a tutte le operazioni write della transazione (before images).
Il valore before image di T1 è X0=1, per T2 è X=3.
Perciò se T esegue commit e T2 abortisce, il ripristino si avrà al valore before image di T2: X=5 (corretto, coincide con l’after image di T1).
Se T2 esegue commit e poi T abortisce, il ripristino si avrà al valore before image di T1: X=1 (non corretto, perché annulla il commit di T2 a 5).
Se entrambe abortiscono – nell’ordine T1, poi T2 – , il ripristino si avrà al valore finale X=3 (before image di T2, abortita per ultima), valore chiaramente non corretto (annullando tutti gli effetti si dovrebbe ritornare al valore iniziale X=1).
Le tecniche di ripristino che fanno uso dei valori before image devono dunque rinviare le operazioni write a dopo il completamento (commit o abort) delle transazioni “precedenti” che hanno aggiornato gli stessi oggetti.
Riepilogando:
Si parla di esecuzione stretta se il server ritarda qualunque operazione (lettura o scrittura) su un oggetto x finché tutte le transazioni che hanno in precedenza modificato x sono completate.
L’esecuzione stretta rispetta la proprietà di isolamento delle transazioni.
1. Caratterizzazione dei sistemi distribuiti
2. Modelli di sistemi distribuiti
3. Tempo e sincronizzazione nei Sistemi Distribuiti
4. Stato globale nei Sistemi Distribuiti
5. Problemi di consenso nei sistemi distribuiti
7. Algoritmi di mutua esclusione nei sistemi distribuiti
8. Algoritmi di elezione nei sistemi distribuiti
10. Il Network File System di SUN Microsystems
11. AFS (Andrew File System) e GFS (Google File System)
12. Transazioni e controllo di concorrenza
13. Transazioni
15. Affidabilità (dependability) dei sistemi software distribuiti
16. Affidabilità dei sistemi software distribuiti
17. Software Faults
18. Classificazione e analisi dei difetti software
G. Coulouris et al.: Distributed Systems: Concepts and Design (Cap. XIII §1-5), IV ed., 2005.