Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Stefano Russo » 14.Transazioni distribuite


Transazioni distribuite

Una transazione distribuita è una transazione (semplice o composta) che accede a oggetti gestiti da più nodi server.

Nel caso di transazioni distribuite, la proprietà di atomicità richiede che tutti i server coinvolti decidano di completare allo stesso modo (completamento con successo o aborto).

Per raggiungere la decisione comune, i server comunicano tra loro seguendo un opportuno protocollo.

I protocolli di commit prevedono tipicamente che uno dei server assuma il ruolo di coordinatore.

Transazioni distribuite semplici

In una transazione distribuita semplice (flat distributed transaction) il client effettua sequenzialmente richieste di accesso ad oggetti gestiti da più nodi server.
Ogni richiesta è completata prima di passare alla successiva.

Se i server adoperano un controllo di concorrenza pessimistico, una transazione distribuita semplice può essere in attesa di un solo oggetto alla volta.


Transazioni distribuite composte

Una transazione distribuita composta (nested distributed transaction) è una transazione composta le cui sottotransazioni accedono ad oggetti gestiti da più nodi server.

Sottotransazioni di pari livello che operano su server differenti sono eseguite in parallelo.


Transazioni distribuite composte

Esempio: applicazione bancaria.
Due bonifici, 4 c/c su 3 nodi:

  • due depositi;
  • due prelievi.
Esempio: applicazione bancaria.

Esempio: applicazione bancaria.


Coordinatore di transazioni distribuite

Il server che viene contattato da un client con una richiesta openTransaction() assume il ruolo di coordinatore della transazione distribuita, ed è – dal punto di vista del client – il responsabile finale del suo completamento (con successo o insuccesso).

Gli altri server assumono il ruolo di partecipanti, responsabili di cooperare con il coordinatore.

L’identificativo della transazione (TID) deve essere univoco; ad es.: coppia {indirizzo del coordinatore, ID univoco nel coord.}

Il coordinatore gestisce una lista dei partecipanti.

Ogni partecipante ha un riferimento al coordinatore.

Coordinatore di transazioni distribuite

Rispetto al caso di transazioni centralizzate, l’interfaccia del coordinatore esibisce l’ulteriore metodo:
join(Trans, riferimento_al_partecipante)
che informa il coordinatore che un nuovo partecipante si è aggiunto alla transazione.

La conoscenza reciproca dei partecipanti e del coordinatore consente di raccogliere a tempo di commit le informazioni per il completamento della transazione.

Un partecipante può invocare il metodo abortTransaction() del coordinatore per abortire unilateralmente la transazione.

Coordinatore di transazioni distribuite

Esempio

Esempio


Protocolli di commit distribuiti

In linea di principio, un modo per completare una transazione distribuita è di far sì che il coordinatore sia l’unico responsabile di prendere la decisione commit o abort, e la comunichi ai partecipanti finché questi non eseguono la decisione.
Si ha in tal caso un protocollo di commit a una fase.
In pratica tale soluzione è inaccettabile, perché non prevede che un partecipante possa unilaterlamente decidere di abortire. Ciò è invece necessario in molti casi, p. es. se un server usa un controllo di concorrenza pessimistico (locking) e deve abortire la transazione in caso rilevi localmente un deadlock.

Protocolli di commit distribuiti

Il protocollo di commit a due fasi (Gray, 1978) prevede che un server possa decidere di abortire a prescindere dagli altri partecipanti, nel qual caso (per il requisito di atomicità) tutta la transazione deve essere abortita.

Nella prima fase, ogni partecipante vota per il successo o insuccesso della transazione. Dopo il voto, non è consentito a un partecipante cambiare decisione. Se ha votato per il commit, assume la responsabilità di garantire prima o poi il completamento, nonostante malfunzionamenti.

Nella seconda fase, ogni partecipante porta a completamento la decisione congiunta.

Protocolli di commit distribuiti

Il modello dei fallimenti per i protocolli di commit a due fasi prevede che questi operino in sistemi asincroni, in cui i server possono andare in crash, e l’inoltro dei messaggi è inaffidabile. I protocolli di rete possono rimuovere messaggi corrotti o duplicati, ma i messaggi possono comunque essere persi. I processi non sono soggetti a guasti bizantini.

I protocolli di commit a due fasi sono algoritmi di consenso distribuito.

Il two-phase commit raggiunge il consenso anche in sistemi asincroni – perché?

Operazioni per il protocollo di commit a due fasi

canCommit?(trans)-> Yes / No
Invocata dal coordinatore sul partecipante. Il participante risponderà col proprio voto.
doCommit(trans)
Invocata dal coordinatore sul partecipante per comunicare la decisione di commit.
doAbort(trans)
Invocata dal coordinatore sul partecipante per comunicare la decisione di abort.
haveCommitted(trans, participant)
Invocata dal partecipante sul coordinatore per comunicare il completamento (con successo) della propria parte di lavoro.
getDecision(trans) -> Yes / No
Invocata dal partecipante sul coordinatore per chiedere la decisione finale, quando non siano pervenuti nè un doCommit nè un doAbort.

Two-phase commit

Phase 1 (voting phase):

1. Il coordinatore invia il messaggio canCommit? ai partecipanti.
2. Il partecipante vota (Sì o No).

  • Se vota No, abortisce immediatamente.
  • Se vota Sì, prima di rispondere esegue il prepare_to_commit salvando lo stato delle risorse su memoria stabile.

Two-phase commit

Phase 2 (completion according to outcome of vote):

3. Il coordinatore raccoglie i voti.

(a) Se tutti i voti sono decide per il commit e invia il messaggio doCommit ai partecipanti.
(b) Altrimenti decide per l’aborto della transazione e invia il messaggio doAbort (a tutti e soli coloro che hanno votato ).

4. I partecipanti che hanno votato ricevono il doCommit o il doAbort. Nel caso di doCommit, ogni partecipante invia il messaggio haveCommitted dopo il completamento.

Two-phase commit: stati di incertezza

Il protocollo 2PC prevede in più punti che il coordinatore o un partecipante non possano progredire perché in attesa di ricevere messaggi.
Ad es., un partecipante che ha votato Yes resta in attesa di un messaggio del coordinatore con l’esito del voto. In tale fase il partecipante è in uno stato di incertezza.


Two-phase commit: stati di incertezza

Se si è perso il messaggio doCommit, per uscire dallo stato di incertezza il partecipante può invocare il metodo getDecision() del coordinatore. Se questi è andato in crash, occorre attendere il suo sostituto. Se anche il sostituto cade, o se il messaggio si perde ancora, lo stato di incertezza si protrae.
Una strategia alternativa in tali casi è di cooperare con gli altri partecipanti, per es. chiedendo l’esito del voto a uno di essi.

Tuttavia, anche con un protocollo cooperativo, se tutti i partecipanti sono nello stato di incertezza, nessuno di essi potrà progredire finché non riceverà un messaggio con l’esito del voto da parte del coordinatore o di un altro partecipante. In tal caso si possono usare protocolli di commit a tre fasi (3PC).

Two-phase commit: stati di incertezza

Un altro stato di incertezza si ha quando il partecipante ha eseguito tutte le richieste del client in una transazione, ma non ha ancora ricevuto il messaggio canCommit? da parte del coordinatore. Se il client ha eseguito una closeTransaction sul coordinatore, e si perdono i messaggi canCommit?, l’attesa del partecipante si protrae.
Il partecipante può accorgersi di tale stato di incertezza solo se nota che non ci sono state richieste di operazioni nella transazione per lungo tempo, per es. attraverso un timeout su un lock.
Poiché non c’è stata ancora nessuna decisione globale, il partecipante può decidere di abortire unilateralmente e rilasciare il lock.

Prestazioni del protocollo two-phase commit

Nel caso migliore, non si presentano malfunzionamenti (crash o perdite di messaggi), e il protocollo 2PC con N partecipanti si completa con 3N messaggi:

  • N messaggi canCommit? da parte del coordinatore;
  • N risposte di voto da parte dei partecipanti;
  • N messaggi doCommit da parte del coordinatore.

(I messaggi haveCommitted non vanno contati perché non necessari per il protocollo 2PC).
Nel caso peggiore, c’é un numero arbitrario di fallimenti: il 2PC tollera un numero indefinito (ma non illimitato) di essi, ma non è possibile dire quando termina se non è noto tale numero.

Two-phase commit per transazioni distribuite composte

Ogni sottotransazione decide autonomamente per l’aborto o il commit provvisorio.
Tutte le transazioni che hanno effettuato un commit provvisorio partecipano a un protocollo 2PC.

N.B.: Un commit provvisorio è differente dal prepare to commit del protocollo 2PC, in quanto non salva lo stato in memoria permanente -> se il server va in crash, il sostituto non può garantire il commit.


Two-phase commit per transazioni distribuite composte

Il coordinatore di una transazione composta fornisce due ulteriori metodi:

openSubTransaction(trans) -> subTrans
Apre una nuova sottotransazione il cui genitore è una transazione trans e restituisce un unico identificatore della sottotransazione.
N.B.: la sottotransazione fa il join col suo genitore.

getStatus(trans)-> committed, aborted, provisional
Chiede al coordinatore di riportare lo stato della transazione  trans (tipicamente, una transazione genitore). Restituisce uno dei seguenti valori: committed, aborted, provisional.

Deve essere possibile risalire dall’ID di una sottotransazione all’ID del suo genitore.

Two-phase commit per transazioni distribuite composte

Ogni coordinatore di una (sotto)transazione ha una lista delle sue sottotransazioni e del loro stato finale.

NB: T12 e T21 condividono un coordinatore. Una transazione può decidere per il commit anche se una sua sottotransazione ha abortito.
T decide per il commit. Il suo coordinatore esegue il protocollo 2PC.


Two-phase commit per transazioni distribuite composte

Quando una sottotransazione completa con commit provvisorio, informa il suo genitore del suo stato e di quello dei suoi discendenti.
Quando completa con aborto, lo informa solo sul suo stato.
Prima o poi la transazione top-level riceve una lista di tutte le sottotransazioni con il loro stato (esclusi i discendenti di transazioni abortite).


Two-phase commit per transazioni distribuite composte

La transazione top-level T fa da coordinatore del 2PC, cui partecipano tutti i coordinatori di sottotransazioni che hanno eseguito un commit provvisorio e che non hanno antenati abortiti.

Le transazioni che votano per il commit si preparano al commit con scritture del proprio stato su memoria permanente.
Questa fase può svolgersi in modo gerarchico o piatto.

La seconda fase del 2PC per transazioni distribuite composte si svolge come per le transazioni flat: il coordinatore raccoglie i voti e prende la decisione finale.

2PC gerarchico

Nel 2PC gerarchico, il coordinatore della transazione di più alto livello comunica con i coordinatori delle sue sottotransazioni dirette, che a loro volta comunicano con le loro sottotransazioni dirette, e così via.
Ciascun partecipante raccoglie le risposte dai suoi discendenti diretti, e risponde al genitore.
Non occorre inviare i messaggi canCommit? alle sottotransazioni abortite.

Es.:
T invia un messaggio canCommit? al coordinatore di T1;
T1 a sua volta invia il canCommit? al coordinatore di T12.

2PC gerarchico

canCommit?(trans, subTrans) -> Yes / No
contatta un coordinatore per chiedere al coordinatore della sottotransazione figlia se può eseguire il commit una sottotransazione subTrans. Il primo argomento trans è l’identificativo della transazione al livello superiore. Il partecipante replica con il suo voto Sì / No.
Il partecipante che riceve la chiamata canCommit? cerca nella propria provisional commit list le (sotto)transazioni che corrispondono al secondo parametro; si prepara al commit e risponde al coordinatore con il voto Yes. Se non trova alcuna transazione, vuol dire che c’è stato un fallimento dall’esecuzione della/e sottotransazione/i, e pertanto invia al coordinatore il messaggio col voto No.
P.es.: N è il coordinatore sia di T12 sia di T21; quando riceve la chiamata canCommit?(T,T1), dovrà gestire solo il commit di T12.

2PC piatto

Nel 2PC piatto, il coordinatore della transazione di più alto livello comunica con i coordinatori di tutte le sue sottotransazioni (dirette e indirette) che sono presenti nella lista dei commit provvisori.
Ciascun partecipante deve far eseguire il commit di tutti i discendenti della transazione top level che non sono stati abortiti.
A tale scopo, esamina la propria lista di transazioni, cercando quelle che corrispondono al TID della transazione di più alto livello, e che non hanno abortito né hanno antenati abortiti.

Es.:

- T invia il messaggio canCommit? ai coordinatori di T1 e di T12;
- N è il coordinatore sia di T12 sia di T21, che ad N risultano entrambe nella lista dei commit provvisori, ma T21 deve essere abortita perchè T2 ha abortito.

2PC piatto

canCommit?(trans, abortList) -> Yes / No
Il coordinatore contatta il partecipante per chiedere se può eseguire il commit di una transazione. Il partecipante replica con il suo voto Sì / No.

Quando un partecipante riceve un canCommit?:

  • se possiede transazioni discendenti dalla trans. top level che hanno eseguito il commit provvisorio:

    • controlla che non abbiano antenati nella abortList, ed esegue il prepare_to_commit;
    • quelle che hanno antenati nella abortList sono abortite;
    • invia al coordinatore il messaggio col voto Yes.
  • altrimenti vuol dire che c’è stato un fallimento dall’esecuzione della/e sottotransazione/i, e pertanto invia al coordinatore il messaggio col voto No.

Confronto tra 2PC gerarchico e 2PC piatto

Il protocollo gerarchico presenta il vantaggio per il partecipante di dover cercare solo le sottotransazioni del più immediato genitore, laddove il protocollo piatto ha bisogno della abort list per eliminare le transazioni i cui antenati hanno abortito.

Il protocollo piatto presenta il vantaggio di prevedere una comunicazione diretta tra il coordinatore della transazione top level e i partecipanti, laddove il protocollo gerarchico prevede lo scambio di messaggi su e giù per i livelli gerarchici.

Locking per transazioni distribuite

In una transazione distribuita, i lock sugli oggetti sono gestiti da un apposito lock manager locale al server ove essi risiedono.

Il lock manager può decidere autonomamente se accordare un lock o far attendere la transazione che ne fa richiesta, ma non può rilasciare un lock prima di sapere se una transazione distribuita è giunta a completamento (per commit o abort) su tutti i server coinvolti.

Gli oggetti non sono disponibili per altre transazioni durante il 2PC.

Una transazione abortita rilascia i lock al termine della fase 1.

Locking per transazioni distribuite

È possibile che server diversi impongano ordinamenti differenti alle transazioni.

Es.: T1 precede T2 sul nodo X e T2 precede T1 sul server Y.

Gli ordinamenti diversi sui server possono dunque portare a dipendenze cicliche e a situazioni di deadlock distribuito.


Deadlock distribuito

Le tecniche di deadlock detection si basano tipicamente sulla ricerca di cicli nel grafo d’attesa.

In un sistema distribuito, in cui più transazioni accedono a oggetti in diversi server, occorrerebbe costruire un wait-for graph globale, a partire dai grafi locali costruiti dai lock manager dei server coinvolti.

Chiaramente, può esserci un ciclo nel grafo globale senza che vi siano cicli nei grafi locali – si ha allora un deadlock distribuito.

Deadlock distribuito


Deadlock distribuito

Grafo d’attesa globale per l’esempio

Grafo d'attesa globale per l'esempio


Deadlock distribuito

Un modo per costruire il grafo globale è la deadlock detection centralizzata, in cui un server assume il ruolo di detector globale. Periodicamente, ogni server invia il proprio grafo locale al detector globale, che costruisce il grafo globale, rileva eventuali cicli e decide la transazione da abortire.
Gli svantaggi sono quelli tipici di ogni soluzione centralizzata.


Deadlock fantasma

Nella deadlock detection distribuita, si possono presentare falsi positivi: deadlock rilevati ma inesistenti, chiamati deadlock fantasma (phantom deadlocks).
La possibilità di deadlock fantasma è dovuta al fatto che un server può aver già rilasciato un lock presente nel grafo locale, quando il grafo globale viene costruito e analizzato.


Deadlock fantasma

Se le transazioni usano il two-phase lock, non è possibile che si verifichi la situazione dell’esempio precedente: nel 2PL le transazioni non possono richiedere altri oggetti dopo un rilascio.

È però possibile che il GD rilevi un deadlock fantasma dovuto all’aborto di una transazione durante la detection.


  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion